mlsanityData to 13 Oct 2026

Distributed Methods with Absolute Compression and Error Compensation

arXiv 2203.02383 ↗First posted 4 Mar 2022math.OC cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

Distributed optimization methods are often applied to solving huge-scale problems like training neural networks with millions and even billions of parameters. In such applications, communicating full vectors, e.g., (stochastic) gradients, iterates, is prohibitively expensive, especially when the number of workers is large. Communication compression is a powerful approach to alleviating this issue, and, in particular, methods with biased compression and error compensation are extremely popular due to their practical efficiency. Sahu et al. (2021) propose a new analysis of Error Compensated SGD (EC-SGD) for the class of absolute compression operators showing that in a certain sense, this class contains optimal compressors for EC-SGD. However, the analysis was conducted only under the so-called (M,σ2)-bounded noise assumption. In this paper, we generalize the analysis of EC-SGD with absolute compression to the arbitrary sampling strategy and propose the first analysis of Error Compensated Loopless Stochastic Variance Reduced Gradient method (EC-LSVRG) with absolute compression for (strongly) convex problems. Our rates improve upon the previously known ones in this setting. Numerical experiments corroborate our theoretical findings.

Key facts. Cited by 4 papers in the map (data through 13 Oct 2026). Builds on 27 of its 37 references that are in the map. First posted on arXiv 4 Mar 2022.

Builds on

27 of 37 references.

References · 27

  1. 2020Language Models are Few-Shot Learnerscited by 32,320
  2. 2020Scaling Laws for Neural Language Modelscited by 6,494
  3. 2019Advances and Open Problems in Federated Learningcited by 3,040
  4. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,470
  5. 2018Sparsified SGD with Memorycited by 376
  6. 2015Deep Learning with Limited Numerical Precisioncited by 372
  7. 2019Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communicationcited by 220
  8. 2019SGD: General Analysis and Improved Ratescited by 206
  9. 2020On Biased Compression for Distributed Learningcited by 140
  10. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 131
  11. 2019Distributed Learning with Compressed Gradient Differencescited by 111
  12. 2019DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compressioncited by 99
15 more
  1. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
  2. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  3. 2019Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loopcited by 68
  4. 2015Perturbed Iterate Analysis for Asynchronous Stochastic Optimizationcited by 67
  5. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 65
  6. 2019Scaling Distributed Machine Learning with In-Network Aggregationcited by 64
  7. 2020Linearly Converging Error Compensated SGDcited by 61
  8. 2020Error Compensated Distributed SGD Can Be Acceleratedcited by 45
  9. 2021Rethinking gradient sparsification as total error minimizationcited by 41
  10. 2015Variance Reduced Stochastic Gradient Descent with Neighborscited by 39
  11. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  12. 2020Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimizationcited by 36
  13. 2019On the Discrepancy between the Theoretical Analysis and Practical Implementations of Compressed Communication for Distributed Deep Learningcited by 32
  14. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  15. 2018Improved asynchronous parallel optimization analysis for stochastic incremental methodscited by 30

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 2; 2024: 0; 2025: 1.

4 papers.

  1. 2023A Guide Through the Zoo of Biased SGDcited by 39
  2. 2025Smoothed Normalization for Efficient Distributed Private Optimizationcited by 2
  3. 2022Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Topcited by 0
  4. 2023Unified analysis of SGD-type methodscited by 0