# The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2019.

## Built on by (most cited first, 14 of 14)

- [Fast Federated Learning in the Presence of Arbitrary Device Unavailability](https://mlsanity.com/paper/2106.04159/) (2021)
- [Rethinking gradient sparsification as total error minimization](https://mlsanity.com/paper/2108.00951/) (2021)
- [FedShuffle: Recipes for Better Use of Local Work in Federated Learning](https://mlsanity.com/paper/2204.13169/) (2022)
- [NET-FLEET: Achieving Linear Convergence Speedup for Fully Decentralized Federated Learning with Heterogeneous Data](https://mlsanity.com/paper/2208.08490/) (2022)
- [Clip21: Error Feedback for Gradient Clipping](https://mlsanity.com/paper/2305.18929/) (2023)
- [On the effectiveness of partial variance reduction in federated learning with heterogeneous data](https://mlsanity.com/paper/2212.02191/) (2022)
- [Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delays](https://mlsanity.com/paper/2106.12261/) (2021)
- [The Minimax Complexity of Distributed Optimization](https://mlsanity.com/paper/2109.00534/) (2021)
- [Intrinisic Gradient Compression for Federated Learning](https://mlsanity.com/paper/2112.02656/) (2021)
- [Learning from straggler clients in federated learning](https://mlsanity.com/paper/2403.09086/) (2024)
- [Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions](https://mlsanity.com/paper/2603.23472/) (2026)
- [How to Attain Communication-Efficient DNN Training? Convert, Compress, Correct](https://mlsanity.com/paper/2204.08211/) (2022)
- [On the Stability Analysis of Open Federated Learning Systems](https://mlsanity.com/paper/2209.12307/) (2022)
- [Theoretical Foundations of Communication-Efficient, Robust, and Practical Distributed and Federated Optimization](https://mlsanity.com/paper/2608.06563/) (2026)

## Abstract (arXiv)

We analyze (stochastic) gradient descent (SGD) with delayed updates on smooth quasi-convex and non-convex functions and derive concise, non-asymptotic, convergence rates. We show that the rate of convergence in all cases consists of two terms: (i) a stochastic term which is not affected by the delay, and (ii) a higher order deterministic term which is only linearly slowed down by the delay. Thus, in the presence of noise, the effects of the delay become negligible after a few iterations and the algorithm converges at the same optimal rate as standard SGD. This result extends a line of research that showed similar results in the asymptotic regime or for strongly-convex quadratic functions only. We further show similar results for SGD with more intricate form of delayed gradients -- compressed gradients under error compensation and for local~SGD where multiple workers perform local steps before communicating with each other. In all of these settings, we improve upon the best known rates. These results show that SGD is robust to compressed and/or delayed stochastic gradient updates. This is in particular important for distributed parallel implementations, where asynchronous and communication efficient methods are the key to achieve linear speedups for optimization with multiple devices.