# Linearly Converging Error Compensated SGD

arXiv: https://arxiv.org/abs/2010.12292 · HTML: https://mlsanity.com/paper/2010.12292/

## Key facts

- Cited by 61 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2020.

## Built on by (most cited first, 30 of 61)

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimization](https://mlsanity.com/paper/2503.12645/) (2025)
- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed](https://mlsanity.com/paper/2102.02888/) (2021)
- [What Do We Mean by Generalization in Federated Learning?](https://mlsanity.com/paper/2110.14216/) (2021)
- [FedNL: Making Newton-Type Methods Applicable to Federated Learning](https://mlsanity.com/paper/2106.02969/) (2021)
- [Rethinking gradient sparsification as total error minimization](https://mlsanity.com/paper/2108.00951/) (2021)
- [A Guide Through the Zoo of Biased SGD](https://mlsanity.com/paper/2305.16296/) (2023)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices](https://mlsanity.com/paper/2103.03239/) (2021)
- [Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning](https://mlsanity.com/paper/2207.04338/) (2022)
- [Permutation Compressors for Provably Faster Distributed Nonconvex Optimization](https://mlsanity.com/paper/2110.03300/) (2021)
- [Momentum Provably Improves Error Feedback!](https://mlsanity.com/paper/2305.15155/) (2023)
- [3PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregation](https://mlsanity.com/paper/2202.00998/) (2022)
- [1-bit LAMB: Communication Efficient Large-Scale Large-Batch Training with LAMB's Convergence Speed](https://mlsanity.com/paper/2104.06069/) (2021)
- [Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization](https://mlsanity.com/paper/2102.07245/) (2021)
- [Preserved central model for faster bidirectional compression in distributed settings](https://mlsanity.com/paper/2102.12528/) (2021)
- [Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks](https://mlsanity.com/paper/2106.04469/) (2021)
- [Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox](https://mlsanity.com/paper/2207.03957/) (2022)
- [GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity](https://mlsanity.com/paper/2210.16402/) (2022)
- [Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy](https://mlsanity.com/paper/2302.01463/) (2023)
- [EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization](https://mlsanity.com/paper/2205.04180/) (2022)
- [EControl: Fast Distributed Optimization with Compression and Error Control](https://mlsanity.com/paper/2311.05645/) (2023)
- [MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization](https://mlsanity.com/paper/2106.03056/) (2021)
- [ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks](https://mlsanity.com/paper/2102.09234/) (2021)
- [Secure Distributed Training at Scale](https://mlsanity.com/paper/2106.11257/) (2021)
- [Communication-Compressed Adaptive Gradient Method for Distributed Nonconvex Optimization](https://mlsanity.com/paper/2111.00705/) (2021)
- [Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning](https://mlsanity.com/paper/2301.00944/) (2023)

## Abstract (arXiv)

In this paper, we propose a unified analysis of variants of distributed SGD with arbitrary compressions and delayed updates. Our framework is general enough to cover different variants of quantized SGD, Error-Compensated SGD (EC-SGD) and SGD with delayed updates (D-SGD). Via a single theorem, we derive the complexity results for all the methods that fit our framework. For the existing methods, this theorem gives the best-known complexity results. Moreover, using our general scheme, we develop new variants of SGD that combine variance reduction or arbitrary sampling with error feedback and quantization and derive the convergence rates for these methods beating the state-of-the-art results. In order to illustrate the strength of our framework, we develop 16 new methods that fit this. In particular, we propose the first method called EC-SGD-DIANA that is based on error-feedback for biased compression operator and quantization of gradient differences and prove the convergence guarantees showing that EC-SGD-DIANA converges to the exact optimum asymptotically in expectation with constant learning rate for both convex and strongly convex objectives when workers compute full gradients of their loss functions. Moreover, for the case when the loss function of the worker has the form of finite sum, we modified the method and got a new one called EC-LSVRG-DIANA which is the first distributed stochastic method with error feedback and variance reduction that converges to the exact optimum asymptotically in expectation with a constant learning rate.