# Adaptive Compression for Communication-Efficient Distributed Training

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 53 references that are in the map.
- First posted on arXiv 31 Oct 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Large Batch Optimization for Deep Learning: Training BERT in 76 minutes](https://mlsanity.com/paper/1904.00962/) (2019)
- [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)
- [FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization](https://mlsanity.com/paper/1909.13014/) (2019)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [FjORD: Fair and Accurate Federated Learning under heterogeneous targets with Ordered Dropout](https://mlsanity.com/paper/2102.13451/) (2021)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [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)
- [Adaptive Quantization of Model Updates for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2102.04487/) (2021)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Closing the convergence gap of SGD without replacement](https://mlsanity.com/paper/2002.10400/) (2020)
- [Distributed learning with compressed gradients](https://mlsanity.com/paper/1806.06573/) (2018)
- [Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees](https://mlsanity.com/paper/2006.14591/) (2020)
- [Adaptive Gradient Quantization for Data-Parallel SGD](https://mlsanity.com/paper/2010.12460/) (2020)
- [A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2006.11077/) (2020)
- [DAdaQuant: Doubly-adaptive quantization for communication-efficient Federated Learning](https://mlsanity.com/paper/2111.00465/) (2021)
- [Randomized Distributed Mean Estimation: Accuracy vs Communication](https://mlsanity.com/paper/1611.07555/) (2016)
- [Communication-Efficient Distributed Learning via Lazily Aggregated Quantized Gradients](https://mlsanity.com/paper/1909.07588/) (2019)

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

- [Momentum Provably Improves Error Feedback!](https://mlsanity.com/paper/2305.15155/) (2023)
- [EControl: Fast Distributed Optimization with Compression and Error Control](https://mlsanity.com/paper/2311.05645/) (2023)
- [Loss Landscape Characterization of Neural Networks without Over-Parametrization](https://mlsanity.com/paper/2410.12455/) (2024)
- [Accelerating Distributed ML Training via Selective Synchronization](https://mlsanity.com/paper/2307.07950/) (2023)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Queuing dynamics of asynchronous Federated Learning](https://mlsanity.com/paper/2405.00017/) (2024)
- [Private Federated Learning with Autotuned Compression](https://mlsanity.com/paper/2307.10999/) (2023)
- [Towards Faster Decentralized Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2405.20114/) (2024)
- [Optimizing Asynchronous Federated Learning: A Delicate Trade-Off Between Model-Parameter Staleness and Update Frequency](https://mlsanity.com/paper/2502.08206/) (2025)
- [FAVANO: Federated AVeraging with Asynchronous NOdes](https://mlsanity.com/paper/2305.16099/) (2023)
- [Layer-wise Quantization for Quantized Optimistic Dual Averaging](https://mlsanity.com/paper/2505.14371/) (2025)
- [Tight analyses of first-order methods with error feedback](https://mlsanity.com/paper/2506.05271/) (2025)
- [Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions](https://mlsanity.com/paper/2603.23472/) (2026)
- [Gradient Projection onto Historical Descent Directions for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2511.05593/) (2025)
- [Optimization Trade-offs in Asynchronous Federated Learning: A Stochastic Networks Approach](https://mlsanity.com/paper/2603.26231/) (2026)
- [CIERA: Cross-Iteration Exponent Reuse for Lossless Allgather in Sharded MoE Training](https://mlsanity.com/paper/2609.04609/) (2026)

## Abstract (arXiv)

We propose Adaptive Compressed Gradient Descent (AdaCGD) - a novel optimization algorithm for communication-efficient training of supervised machine learning models with adaptive compression level. Our approach is inspired by the recently proposed three point compressor (3PC) framework of Richtarik et al. (2022), which includes error feedback (EF21), lazily aggregated gradient (LAG), and their combination as special cases, and offers the current state-of-the-art rates for these methods under weak assumptions. While the above mechanisms offer a fixed compression level, or adapt between two extremes only, our proposal is to perform a much finer adaptation. In particular, we allow the user to choose any number of arbitrarily chosen contractive compression mechanisms, such as Top-K sparsification with a user-defined selection of sparsification levels K, or quantization with a user-defined selection of quantization levels, or their combination. AdaCGD chooses the appropriate compressor and compression level adaptively during the optimization process. Besides i) proposing a theoretically-grounded multi-adaptive communication compression mechanism, we further ii) extend the 3PC framework to bidirectional compression, i.e., we allow the server to compress as well, and iii) provide sharp convergence bounds in the strongly convex, convex and nonconvex settings. The convex regime results are new even for several key special cases of our general mechanism, including 3PC and EF21. In all regimes, our rates are superior compared to all existing adaptive compression methods.