Lossy Compression for Sparse Aggregation

We consider the problem of transmitting sparse local updates to the server in a distributed learning system. Specifically, the system consists of $n$ clients, each possessing a $k$-sparse $d$-dimensional local model, and a central server responsible for aggregating the clients’ models into a global model. The goal is to characterize the tradeoff between the communication cost in the transmission from the clients to the server and the accuracy in aggregating the global model. We propose a compression scheme for sparse local models by concatenating a covering method and a sketching method. We also present a converse based on f-divergence, which strengthens the conventional Fano-type lower bounds. The proposed lower bound is tight for the frequency estimation case, that is, each coordinate takes values in a binary alphabet. For general alphabets, the proposed achievable schemes remain suboptimal relative to the converse bounds, indicating that a complete characterization of the communication-accuracy tradeoff requires further investigation.