mlsanityData to 7 Oct 2026

Optimal Gradient Compression for Distributed and Federated Learning

arXiv 2010.03246 ↗First posted 7 Oct 2020cs.LG math.OCcited by 37

Not on the map. Why?

Abstract (arXiv)

Communicating information, like gradient vectors, between computing nodes in distributed and federated learning is typically an unavoidable burden, resulting in scalability issues. Indeed, communication might be slow and costly. Recent advances in communication-efficient training algorithms have reduced this bottleneck by using compression techniques, in the form of sparsification, quantization, or low-rank approximation. Since compression is a lossy, or inexact, process, the iteration complexity is typically worsened; but the total communication complexity can improve significantly, possibly leading to large computation time savings. In this paper, we investigate the fundamental trade-off between the number of bits needed to encode compressed vectors and the compression error. We perform both worst-case and average-case analysis, providing tight lower bounds. In the worst-case analysis, we introduce an efficient compression operator, Sparse Dithering, which is very close to the lower bound. In the average-case analysis, we design a simple compression operator, Spherical Compression, which naturally achieves the lower bound. Thus, our new compression schemes significantly outperform the state of the art. We conduct numerical experiments to illustrate this improvement.

Key facts. Cited by 37 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 10; 2023: 6; 2024: 4; 2025: 3; 2026: 2.

37 papers.

Sort:

  1. 2021Distributed Learning in Wireless Networks: Recent Progress and Future Challengescited by 125
  2. 2021What Do We Mean by Generalization in Federated Learning?cited by 62
  3. 2021Rethinking gradient sparsification as total error minimizationcited by 41
  4. 2021Layer-wise Adaptive Model Aggregation for Scalable Federated Learningcited by 35
  5. 2021FedHM: Efficient Federated Learning for Heterogeneous Models via Low-rank Factorizationcited by 31
  6. 2022Communication-Efficient Device Scheduling for Federated Learning Using Stochastic Optimizationcited by 28
  7. 2021Federated Learning with Spiking Neural Networkscited by 22
  8. 2022EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimizationcited by 17
  9. 2022Recycling Model Updates in Federated Learning: Are Gradient Subspaces Low-Rank?cited by 16
  10. 2022Optimizing the Communication-Accuracy Trade-off in Federated Learning with Rate-Distortion Theorycited by 14
  11. 2021MURANA: A Generic Framework for Stochastic Variance-Reduced Optimizationcited by 13
  12. 2022Federated Learning with Flexible Controlcited by 12
25 more
  1. 2024LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compressioncited by 11
  2. 2023Asynchronous Federated Learning with Bidirectional Quantized Communications and Buffered Aggregationcited by 10
  3. 2021Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniquescited by 9
  4. 2021Sparsified Secure Aggregation for Privacy-Preserving Federated Learningcited by 8
  5. 2022QUIC-FL: Quick Unbiased Compression for Federated Learningcited by 7
  6. 2022Shifted Compression Framework: Generalizations and Improvementscited by 6
  7. 2022Privacy-Aware Compression for Federated Learning Through Numerical Mechanism Designcited by 6
  8. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  9. 2021Distributed Online Learning for Joint Regret with Communication Constraintscited by 5
  10. 2022Addressing Client Drift in Federated Continual Learning with Adaptive Optimizationcited by 5
  11. 2021Wyner-Ziv Gradient Compression for Federated Learningcited by 3
  12. 2022Towards cost-effective and resource-aware aggregation at Edge for Federated Learningcited by 3
  13. 2023TAMUNA: Doubly Accelerated Distributed Optimization under Partial Participationcited by 3
  14. 2023Divide-and-Conquer the NAS puzzle in Resource Constrained Federated Learning Systemscited by 3
  15. 2024Quantized and Asynchronous Federated Learningcited by 3
  16. 2024Problem-dependent convergence bounds for randomized linear gradient compressioncited by 3
  17. 2025Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participationcited by 3
  18. 2021Intrinisic Gradient Compression for Federated Learningcited by 2
  19. 2023Federated Automatic Differentiationcited by 2
  20. 2024Theoretical Analysis of Privacy Leakage in Trustworthy Federated Learning: A Perspective from Linear Algebra and Optimization Theorycited by 2
  21. 2025Accelerated Distributed Optimization with Compression and Error Feedbackcited by 2
  22. 2025Communication-Efficient Device Scheduling for Federated Learning Using Lyapunov Optimizationcited by 1
  23. 2026BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Trainingcited by 1
  24. 2023FedAgg: Adaptive Federated Learning with Aggregated Gradientscited by 0
  25. 2026On Gossip Algorithms for Machine Learning with Pairwise Objectivescited by 0