Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation
arXiv:2110.07751
Abstract
We study the problem of estimating at a central server the mean of a set of vectors distributed across several nodes (one vector per node). When the vectors are high-dimensional, the communication cost of sending entire vectors may be prohibitive, and it may be imperative for them to use sparsification techniques. While most existing work on sparsified mean estimation is agnostic to the characteristics of the data vectors, in many practical applications such as federated learning, there may be spatial correlations (similarities in the vectors sent by different nodes) or temporal correlations (similarities in the data sent by a single node over different iterations of the algorithm) in the data vectors. We leverage these correlations by simply modifying the decoding method used by the server to estimate the mean. We provide an analysis of the resulting estimation error as well as experiments for PCA, K-Means and Logistic Regression, which show that our estimators consistently outperform more sophisticated and expensive sparsification methods.
Accepted to NeurIPS 2021
References in corpus (14)
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
- Communication-Efficient Learning of Deep Networks from Decentralized Data
- QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
- Sparsified SGD with Memory
- Error Feedback Fixes SignSGD and other Gradient Compression Schemes
- Distributed Mean Estimation with Limited Communication
- Distributed Learning with Compressed Gradient Differences
- Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
- The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
- Communication-Efficient Distributed Learning via Lazily Aggregated Quantized Gradients
- On Communication Cost of Distributed Statistical Estimation and Dimensionality
- On Biased Compression for Distributed Learning
- Breaking the Communication-Privacy-Accuracy Trilemma
- A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning