mlsanityData to 7 Oct 2026

Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression

arXiv 2206.03665 ↗First posted 8 Jun 2022cs.LG math.OCcited by 33

Not on the map. Why?

Abstract (arXiv)

Recent advances in distributed optimization and learning have shown that communication compression is one of the most effective means of reducing communication. While there have been many results on convergence rates under communication compression, a theoretical lower bound is still missing. Analyses of algorithms with communication compression have attributed convergence to two abstract properties: the unbiased property or the contractive property. They can be applied with either unidirectional compression (only messages from workers to server are compressed) or bidirectional compression. In this paper, we consider distributed stochastic algorithms for minimizing smooth and non-convex objective functions under communication compression. We establish a convergence lower bound for algorithms whether using unbiased or contractive compressors in unidirection or bidirection. To close the gap between the lower bound and the existing upper bounds, we further propose an algorithm, NEOLITHIC, which almost reaches our lower bound (up to logarithm factors) under mild conditions. Our results also show that using contractive bidirectional compression can yield iterative methods that converge as fast as those using unbiased unidirectional compression. The experimental results validate our findings.

Key facts. Cited by 33 papers in the map (data through 7 Oct 2026). Builds on 62 of its 98 references that are in the map. First posted on arXiv 8 Jun 2022.

Builds on

62 of 98 references.

References · 62

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  3. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  4. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  5. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  6. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 561
  7. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 496
  8. 2017Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Trainingcited by 471
  9. 2018Sparsified SGD with Memorycited by 373
  10. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
  11. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  12. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
38 more
  1. 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 253
  2. 2019PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimizationcited by 234
  3. 2018The Convergence of Sparsified Gradient Methodscited by 228
  4. 2017Gradient Sparsification for Communication-Efficient Distributed Optimizationcited by 199
  5. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 179
  6. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 178
  7. 2014EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimizationcited by 160
  8. 2013On the Convergence of Decentralized Gradient Descentcited by 158
  9. 2018Stochastic Gradient Push for Distributed Deep Learningcited by 152
  10. 2018D2: Decentralized Training over Decentralized Datacited by 140
  11. 2020On Biased Compression for Distributed Learningcited by 140
  12. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 131
  13. 2017Lower Bounds for Finding Stationary Points Icited by 125
  14. 2019DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compressioncited by 98
  15. 2018LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learningcited by 95
  16. 2019Natural Compression for Distributed Deep Learningcited by 88
  17. 2018Communication Compression for Decentralized Trainingcited by 87
  18. 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 77
  19. 2018Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimizationcited by 76
  20. 2021Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Datacited by 69
  21. 2022An Improved Analysis of Gradient Tracking for Decentralized Machine Learningcited by 68
  22. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 64
  23. 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 59
  24. 2020Optimal Complexity in Decentralized Trainingcited by 59
  25. 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 55
  26. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 55
  27. 2021Exponential Graph is Provably Efficient for Decentralized Deep Trainingcited by 55
  28. 2020An improved convergence analysis for decentralized online stochastic non-convex optimizationcited by 53
  29. 2020Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressorcited by 45
  30. 2020Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guaranteescited by 45
  31. 2020Error Compensated Distributed SGD Can Be Acceleratedcited by 45
  32. 2021A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learningcited by 43
  33. 2021Rethinking gradient sparsification as total error minimizationcited by 41
  34. 2022BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compressioncited by 41
  35. 2021DecentLaM: Decentralized Momentum SGD for Large-batch Deep Trainingcited by 40
  36. 2019The Complexity of Making the Gradient Small in Stochastic Convex Optimizationcited by 33
  37. 2021Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGDcited by 28
  38. 2020CSER: Communication-efficient SGD with Error Resetcited by 27

50 most cited of 62 All 62 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 8; 2024: 7; 2025: 7; 2026: 8.

33 papers.

Sort:

  1. 2023Stochastic Controlled Averaging for Federated Learning with Communication Compressioncited by 100
  2. 2023Momentum Provably Improves Error Feedback!cited by 31
  3. 2022Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimizationcited by 22
  4. 2023Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?cited by 14
  5. 2023EControl: Fast Distributed Optimization with Compression and Error Controlcited by 14
  6. 2024LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compressioncited by 11
  7. 2023CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergencecited by 9
  8. 2024Efficient Federated Learning against Heterogeneous and Non-stationary Client Unavailabilitycited by 9
  9. 2025Greedy Low-Rank Gradient Compression for Distributed Learning with Convergence Guaranteescited by 9
  10. 2022Optimal Complexity in Non-Convex Decentralized Learning over Time-Varying Networkscited by 4
  11. 2023Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitzcited by 4
  12. 2023Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compressioncited by 4
21 more
  1. 2024Towards Faster Decentralized Stochastic Optimization with Communication Compressioncited by 4
  2. 2024Problem-dependent convergence bounds for randomized linear gradient compressioncited by 3
  3. 2022Sublinear Algorithms for Hierarchical Clusteringcited by 2
  4. 2023Compressed Regression over Adaptive Networkscited by 2
  5. 2024Communication-Efficient Distributed Learning with Local Immediate Error Compensationcited by 2
  6. 2025Accelerated Distributed Optimization with Compression and Error Feedbackcited by 2
  7. 2025On the Gradient Complexity of Private Optimization with Private Oraclescited by 2
  8. 2026Distributed Online Convex Optimization with Efficient Communication: Improved Algorithm and Lower boundscited by 2
  9. 2024Byzantine-Robust and Communication-Efficient Distributed Learning via Compressed Momentum Filteringcited by 1
  10. 2025Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimizationcited by 1
  11. 2026BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Trainingcited by 1
  12. 2026Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applicationscited by 1
  13. 2024MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizescited by 0
  14. 2025Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Constructioncited by 0
  15. 2025From PowerSGD to PowerSGD+: Low-Rank Gradient Compression for Distributed Optimization with Convergence Guaranteescited by 0
  16. 2025An All-Reduce Compatible Top-K Compressor for Communication-Efficient Distributed Learningcited by 0
  17. 2026SA-PEF: Step-Ahead Partial Error Feedback for Efficient Federated Learningcited by 0
  18. 2026Decentralized Non-convex Stochastic Optimization with Heterogeneous Variancecited by 0
  19. 2026Don't Let a Few Network Failures Slow the Entire AllReducecited by 0
  20. 2026Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimizationcited by 0
  21. 2026Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compressioncited by 0