# Distributed learning with compressed gradients

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

## Key facts

- Cited by 55 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2018.

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

- [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)
- [FedNL: Making Newton-Type Methods Applicable to Federated Learning](https://mlsanity.com/paper/2106.02969/) (2021)
- [BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compression](https://mlsanity.com/paper/2201.13320/) (2022)
- [A Guide Through the Zoo of Biased SGD](https://mlsanity.com/paper/2305.16296/) (2023)
- [SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression](https://mlsanity.com/paper/2206.09888/) (2022)
- [Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning](https://mlsanity.com/paper/2207.04338/) (2022)
- [3PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregation](https://mlsanity.com/paper/2202.00998/) (2022)
- [Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applications](https://mlsanity.com/paper/2202.12396/) (2022)
- [Distributed Second Order Methods with Fast Rates and Compressed Communication](https://mlsanity.com/paper/2102.07158/) (2021)
- [CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression](https://mlsanity.com/paper/2107.09461/) (2021)
- [FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type Method for Federated Learning](https://mlsanity.com/paper/2206.08829/) (2022)
- [Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization](https://mlsanity.com/paper/2102.07245/) (2021)
- [Federated Optimization Algorithms with Random Reshuffling and Gradient Compression](https://mlsanity.com/paper/2206.07021/) (2022)
- [Adaptive Compression for Communication-Efficient Distributed Training](https://mlsanity.com/paper/2211.00188/) (2022)
- [AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms](https://mlsanity.com/paper/2310.20452/) (2023)
- [EControl: Fast Distributed Optimization with Compression and Error Control](https://mlsanity.com/paper/2311.05645/) (2023)
- [Faster Rates for Compressed Federated Learning with Client-Variance Reduction](https://mlsanity.com/paper/2112.13097/) (2021)
- [Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?](https://mlsanity.com/paper/2305.16297/) (2023)
- [Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning](https://mlsanity.com/paper/2301.00944/) (2023)
- [Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Rates](https://mlsanity.com/paper/2310.09804/) (2023)
- [FL_PyTorch: optimization research simulator for federated learning](https://mlsanity.com/paper/2202.03099/) (2022)
- [DARE the Extreme: Revisiting Delta-Parameter Pruning For Fine-Tuned Models](https://mlsanity.com/paper/2410.09344/) (2024)
- [IntSGD: Adaptive Floatless Compression of Stochastic Gradients](https://mlsanity.com/paper/2102.08374/) (2021)
- [Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques](https://mlsanity.com/paper/2106.03524/) (2021)
- [Linear Stochastic Bandits over a Bit-Constrained Channel](https://mlsanity.com/paper/2203.01198/) (2022)
- [Communication-Efficient Distributed Optimization with Quantized Preconditioners](https://mlsanity.com/paper/2102.07214/) (2021)
- [EF21 with Bells & Whistles: Six Algorithmic Extensions of Modern Error Feedback](https://mlsanity.com/paper/2110.03294/) (2021)
- [Improving Accelerated Federated Learning with Compression and Importance Sampling](https://mlsanity.com/paper/2306.03240/) (2023)
- [Shifted Compression Framework: Generalizations and Improvements](https://mlsanity.com/paper/2206.10452/) (2022)

## Abstract (arXiv)

Asynchronous computation and gradient compression have emerged as two key techniques for achieving scalability in distributed optimization for large-scale machine learning. This paper presents a unified analysis framework for distributed gradient methods operating with staled and compressed gradients. Non-asymptotic bounds on convergence rates and information exchange are derived for several optimization algorithms. These bounds give explicit expressions for step-sizes and characterize how the amount of asynchrony and the compression accuracy affect iteration and communication complexity guarantees. Numerical results highlight convergence properties of different gradient compression algorithms and confirm that fast convergence under limited information exchange is indeed possible.