# Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 62 of its 98 references that are in the map.
- First posted on arXiv 8 Jun 2022.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [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)
- [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)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [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)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations](https://mlsanity.com/paper/1906.02367/) (2019)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression](https://mlsanity.com/paper/1905.05957/) (2019)
- [LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning](https://mlsanity.com/paper/1805.09965/) (2018)
- [Natural Compression for Distributed Deep Learning](https://mlsanity.com/paper/1905.10988/) (2019)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)

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

- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [Momentum Provably Improves Error Feedback!](https://mlsanity.com/paper/2305.15155/) (2023)
- [Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2210.07863/) (2022)
- [EControl: Fast Distributed Optimization with Compression and Error Control](https://mlsanity.com/paper/2311.05645/) (2023)
- [Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?](https://mlsanity.com/paper/2305.16297/) (2023)
- [LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression](https://mlsanity.com/paper/2403.04348/) (2024)
- [Greedy Low-Rank Gradient Compression for Distributed Learning with Convergence Guarantees](https://mlsanity.com/paper/2507.08784/) (2025)
- [CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence](https://mlsanity.com/paper/2301.05872/) (2023)
- [Efficient Federated Learning against Heterogeneous and Non-stationary Client Unavailability](https://mlsanity.com/paper/2409.17446/) (2024)
- [Towards Faster Decentralized Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2405.20114/) (2024)
- [Optimal Complexity in Non-Convex Decentralized Learning over Time-Varying Networks](https://mlsanity.com/paper/2211.00533/) (2022)
- [Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitz](https://mlsanity.com/paper/2310.14616/) (2023)
- [Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compression](https://mlsanity.com/paper/2310.19059/) (2023)
- [Accelerated Distributed Optimization with Compression and Error Feedback](https://mlsanity.com/paper/2503.08427/) (2025)
- [Problem-dependent convergence bounds for randomized linear gradient compression](https://mlsanity.com/paper/2411.12898/) (2024)
- [Sublinear Algorithms for Hierarchical Clustering](https://mlsanity.com/paper/2206.07633/) (2022)
- [Compressed Regression over Adaptive Networks](https://mlsanity.com/paper/2304.03638/) (2023)
- [Communication-Efficient Distributed Learning with Local Immediate Error Compensation](https://mlsanity.com/paper/2402.11857/) (2024)
- [On the Gradient Complexity of Private Optimization with Private Oracles](https://mlsanity.com/paper/2511.13999/) (2025)
- [Distributed Online Convex Optimization with Efficient Communication: Improved Algorithm and Lower bounds](https://mlsanity.com/paper/2601.04907/) (2026)
- [Byzantine-Robust and Communication-Efficient Distributed Learning via Compressed Momentum Filtering](https://mlsanity.com/paper/2409.08640/) (2024)
- [MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes](https://mlsanity.com/paper/2412.17082/) (2024)
- [Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization](https://mlsanity.com/paper/2501.03222/) (2025)
- [BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Training](https://mlsanity.com/paper/2601.12400/) (2026)
- [Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications](https://mlsanity.com/paper/2604.09276/) (2026)
- [Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction](https://mlsanity.com/paper/2506.23836/) (2025)
- [From PowerSGD to PowerSGD+: Low-Rank Gradient Compression for Distributed Optimization with Convergence Guarantees](https://mlsanity.com/paper/2509.11254/) (2025)
- [An All-Reduce Compatible Top-K Compressor for Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2510.26709/) (2025)
- [SA-PEF: Step-Ahead Partial Error Feedback for Efficient Federated Learning](https://mlsanity.com/paper/2601.20738/) (2026)
- [Decentralized Non-convex Stochastic Optimization with Heterogeneous Variance](https://mlsanity.com/paper/2602.11789/) (2026)

## Abstract (arXiv)

Recent advances in distributed optimization and learning have shown that communication compression is one of the most effective means of reducing communication. While there have been many results on convergence rates under communication compression, a theoretical lower bound is still missing. Analyses of algorithms with communication compression have attributed convergence to two abstract properties: the unbiased property or the contractive property. They can be applied with either unidirectional compression (only messages from workers to server are compressed) or bidirectional compression. In this paper, we consider distributed stochastic algorithms for minimizing smooth and non-convex objective functions under communication compression. We establish a convergence lower bound for algorithms whether using unbiased or contractive compressors in unidirection or bidirection. To close the gap between the lower bound and the existing upper bounds, we further propose an algorithm, NEOLITHIC, which almost reaches our lower bound (up to logarithm factors) under mild conditions. Our results also show that using contractive bidirectional compression can yield iterative methods that converge as fast as those using unbiased unidirectional compression. The experimental results validate our findings.