# Accelerated Distributed Optimization with Compression and Error Feedback

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 57 references that are in the map.
- First posted on arXiv 11 Mar 2025.

## Builds on (most cited first, 30 of 44)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Hierarchical Text-Conditional Image Generation with CLIP Latents](https://mlsanity.com/paper/2204.06125/) (2022)
- [Zero-Shot Text-to-Image Generation](https://mlsanity.com/paper/2102.12092/) (2021)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [Deep Learning with Limited Numerical Precision](https://mlsanity.com/paper/1502.02551/) (2015)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization](https://mlsanity.com/paper/1905.13727/) (2019)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [Distributed Learning with Compressed Gradient Differences](https://mlsanity.com/paper/1901.09269/) (2019)
- [Decentralized Deep Learning with Arbitrary Communication Compression](https://mlsanity.com/paper/1907.09356/) (2019)
- [Natural Compression for Distributed Deep Learning](https://mlsanity.com/paper/1905.10988/) (2019)
- [Scaling Distributed Machine Learning with In-Network Aggregation](https://mlsanity.com/paper/1903.06701/) (2019)
- [Linearly Converging Error Compensated SGD](https://mlsanity.com/paper/2010.12292/) (2020)
- [FedNL: Making Newton-Type Methods Applicable to Federated Learning](https://mlsanity.com/paper/2106.02969/) (2021)
- [Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback](https://mlsanity.com/paper/1905.10936/) (2019)
- [Error Compensated Distributed SGD Can Be Accelerated](https://mlsanity.com/paper/2010.00091/) (2020)
- [Rethinking gradient sparsification as total error minimization](https://mlsanity.com/paper/2108.00951/) (2021)
- [Optimal Gradient Compression for Distributed and Federated Learning](https://mlsanity.com/paper/2010.03246/) (2020)
- [A Survey on Large-scale Machine Learning](https://mlsanity.com/paper/2008.03911/) (2020)

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

- [Greedy Low-Rank Gradient Compression for Distributed Learning with Convergence Guarantees](https://mlsanity.com/paper/2507.08784/) (2025)
- [Evolution of Optimization Methods: Algorithms, Scenarios, and Evaluations](https://mlsanity.com/paper/2604.12968/) (2026)
- [Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions](https://mlsanity.com/paper/2603.23472/) (2026)
- [Communication Compression for Distributed Learning with Aggregate and Server-Guided Feedback](https://mlsanity.com/paper/2512.22623/) (2025)

## Abstract (arXiv)

Modern machine learning tasks often involve massive datasets and models, necessitating distributed optimization algorithms with reduced communication overhead. Communication compression, where clients transmit compressed updates to a central server, has emerged as a key technique to mitigate communication bottlenecks. However, the theoretical understanding of stochastic distributed optimization with contractive compression remains limited, particularly in conjunction with Nesterov acceleration -- a cornerstone for achieving faster convergence in optimization. In this paper, we propose a novel algorithm, ADEF (Accelerated Distributed Error Feedback), which integrates Nesterov acceleration, contractive compression, error feedback, and gradient difference compression. We prove that ADEF achieves the first accelerated convergence rate for stochastic distributed optimization with contractive compression in the general convex regime. Numerical experiments validate our theoretical findings and demonstrate the practical efficacy of ADEF in reducing communication costs while maintaining fast convergence.