# Distributed Learning with Compressed Gradient Differences

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

## Key facts

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

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

- [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)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Momentum Provably Improves Error Feedback!](https://mlsanity.com/paper/2305.15155/) (2023)
- [A Survey on Efficient Federated Learning Methods for Foundation Model Training](https://mlsanity.com/paper/2401.04472/) (2024)
- [3PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregation](https://mlsanity.com/paper/2202.00998/) (2022)
- [Distributed Second Order Methods with Fast Rates and Compressed Communication](https://mlsanity.com/paper/2102.07158/) (2021)
- [Fed-ensemble: Improving Generalization through Model Ensembling in Federated Learning](https://mlsanity.com/paper/2107.10663/) (2021)
- [Can 5th Generation Local Training Methods Support Client Sampling? Yes!](https://mlsanity.com/paper/2212.14370/) (2022)
- [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)
- [FedShuffle: Recipes for Better Use of Local Work in Federated Learning](https://mlsanity.com/paper/2204.13169/) (2022)
- [Federated Optimization Algorithms with Random Reshuffling and Gradient Compression](https://mlsanity.com/paper/2206.07021/) (2022)
- [DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization](https://mlsanity.com/paper/2202.01268/) (2022)
- [AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms](https://mlsanity.com/paper/2310.20452/) (2023)
- [Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning](https://mlsanity.com/paper/2111.01847/) (2021)
- [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)
- [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)
- [BROADCAST: Reducing Both Stochastic and Compression Noise to Robustify Communication-Efficient Federated Learning](https://mlsanity.com/paper/2104.06685/) (2021)
- [Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks](https://mlsanity.com/paper/2106.07243/) (2021)
- [Communication-Compressed Adaptive Gradient Method for Distributed Nonconvex Optimization](https://mlsanity.com/paper/2111.00705/) (2021)
- [FLIX: A Simple and Communication-Efficient Alternative to Local Methods in Federated Learning](https://mlsanity.com/paper/2111.11556/) (2021)
- [Federated Random Reshuffling with Compression and Variance Reduction](https://mlsanity.com/paper/2205.03914/) (2022)
- [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)
- [Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation](https://mlsanity.com/paper/2206.03588/) (2022)
- [CompressedScaffnew: The First Theoretical Double Acceleration of Communication from Local Training and Compression in Distributed Optimization](https://mlsanity.com/paper/2210.13277/) (2022)
- [Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2305.07612/) (2023)

## Abstract (arXiv)

Training large machine learning models requires a distributed computing approach, with communication of the model updates being the bottleneck. For this reason, several methods based on the compression (e.g., sparsification and/or quantization) of updates were recently proposed, including QSGD (Alistarh et al., 2017), TernGrad (Wen et al., 2017), SignSGD (Bernstein et al., 2018), and DQGD (Khirirat et al., 2018). However, none of these methods are able to learn the gradients, which renders them incapable of converging to the true optimum in the batch mode. In this work we propose a new distributed learning method -- DIANA -- which resolves this issue via compression of gradient differences. We perform a theoretical analysis in the strongly convex and nonconvex settings and show that our rates are superior to existing rates. We also provide theory to support non-smooth regularizers study the difference between quantization schemes. Our analysis of block-quantization and differences between ℓ2 and ℓ∞ quantization closes the gaps in theory and practice. Finally, by applying our analysis technique to TernGrad, we establish the first convergence rate for this method.