mlsanityData to 7 Oct 2026

Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation

arXiv 2110.07751 ↗First posted 14 Oct 2021cs.LG stat.MLcited by 7

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 31 of its 40 references that are in the map. First posted on arXiv 14 Oct 2021.

Builds on

31 of 40 references.

References · 31

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
  3. 2019Advances and Open Problems in Federated Learningcited by 3,021
  4. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 561
  5. 2018Sparsified SGD with Memorycited by 373
  6. 2021A Field Guide to Federated Optimizationcited by 312
  7. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
  8. 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 253
  9. 2018The Convergence of Sparsified Gradient Methodscited by 228
  10. 2017Gradient Sparsification for Communication-Efficient Distributed Optimizationcited by 199
  11. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 179
  12. 2016QSGD: Communication-Efficient SGD via Gradient Quantization and Encodingcited by 147
19 more
  1. 2020On Biased Compression for Distributed Learningcited by 140
  2. 2018ATOMO: Communication-efficient Learning via Atomic Sparsificationcited by 135
  3. 2016Distributed Mean Estimation with Limited Communicationcited by 134
  4. 2019Distributed Learning with Compressed Gradient Differencescited by 110
  5. 2018LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learningcited by 95
  6. 2020Breaking the Communication-Privacy-Accuracy Trilemmacited by 68
  7. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 64
  8. 2021Adaptive Quantization of Model Updates for Communication-Efficient Federated Learningcited by 60
  9. 2015Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequalitycited by 50
  10. 2020A Better Alternative to Error Feedback for Communication-Efficient Distributed Learningcited by 42
  11. 2016Randomized Distributed Mean Estimation: Accuracy vs Communicationcited by 39
  12. 2019Communication-Efficient Distributed Learning via Lazily Aggregated Quantized Gradientscited by 32
  13. 2019A Double Residual Compression Algorithm for Efficient Distributed Learningcited by 31
  14. 2020rTop-k: A Statistical Estimation Approach to Distributed SGDcited by 27
  15. 2021Time-Correlated Sparsification for Communication-Efficient Federated Learningcited by 25
  16. 2014On Communication Cost of Distributed Statistical Estimation and Dimensionalitycited by 24
  17. 2019RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimizationcited by 23
  18. 2019LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learningcited by 9
  19. 2020LASG: Lazily Aggregated Stochastic Gradients for Communication-Efficient Distributed Learningcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 1; 2025: 1; 2026: 2.

7 papers.

  1. 2023Adaptive Compression in Federated Learning via Side Informationcited by 6
  2. 2023Correlation Aware Sparsified Mean Estimation Using Random Projectioncited by 3
  3. 2023Collaborative Mean Estimation over Intermittently Connected Networks with Peer-To-Peer Privacycited by 2
  4. 2024Privacy Preserving Semi-Decentralized Mean Estimation over Intermittently-Connected Networkscited by 2
  5. 2026Communication-Efficient Federated Learning by Exploiting Spatio-Temporal Correlations of Gradientscited by 1
  6. 2026Collaborative Compressors in Distributed Mean Estimation with Limited Communication Budgetcited by 1
  7. 2025Efficient Covariance Estimation for Sparsified Functional Datacited by 0