Collaborative Compressors in Distributed Mean Estimation with Limited Communication Budget
Preprint
Abstract
Distributed high dimensional mean estimation is a common aggregation routine used often in distributed optimization methods. Most of these applications call for a communication-constrained setting where vectors, whose mean is to be estimated, have to be compressed before sharing. One could independently encode and decode these to achieve compression, but that overlooks the fact that these vectors are often close to each other. To exploit these similarities, recently Suresh et al., 2022, Jhunjhunwala et al., 2021, Jiang et al, 2023, proposed multiple correlation-aware compression schemes. However, in most cases, the correlations have to be known for these schemes to work. Moreover, a theoretical analysis of graceful degradation of these correlation-aware compression schemes with increasing dissimilarity is limited to only the $\ell_2$-error in the literature. In this paper, we propose four different collaborative compression schemes that agnostically exploit the similarities among vectors in a distributed setting. Our schemes are all simple to implement and computationally efficient, while resulting in big savings in communication. The analysis of our proposed schemes show how the $\ell_2$, $\ell_\infty$ and cosine estimation error varies with the degree of similarity among vectors.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Magnitude Matters: Fixing signSGD Through Magnitude-Aware Sparsification and Error Feedback in the Presence of Data HeterogeneityIEEE Transactions on Signal Processing, 2024
- vqSGD: Vector Quantized Stochastic Gradient DescentIEEE Transactions on Information Theory, 2022
- Communication-Efficient and Byzantine-Robust Distributed Learning With Error FeedbackIEEE Journal on Selected Areas in Information Theory, 2021
- Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressorInformation and Inference: A Journal of the IMA, 2021
- Lossy Compression via Sparse Linear Regression: Computationally Efficient Encoding and DecodingIEEE Transactions on Information Theory, 2014
- Lossy Compression via Sparse Linear Regression: Performance Under Minimum-Distance EncodingIEEE Transactions on Information Theory, 2014
- Chernoff-Type Bounds for the Gaussian Error FunctionIEEE Transactions on Communications, 2011
- Agnostically Learning HalfspacesSIAM Journal on Computing, 2008
- Hardness of Learning Halfspaces with Noise2006
- Least squares quantization in PCMIEEE Transactions on Information Theory, 1982