# Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 47 references that are in the map.
- First posted on arXiv 14 May 2021.

## Builds on (most cited first, 15 of 15)

- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates](https://mlsanity.com/paper/1704.07807/) (2017)
- [Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development](https://mlsanity.com/paper/1702.05122/) (2017)
- [A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!](https://mlsanity.com/paper/2011.01697/) (2020)
- [An Exact Quantized Decentralized Gradient Descent Algorithm](https://mlsanity.com/paper/1806.11536/) (2018)
- [Quantized Decentralized Stochastic Learning over Directed Graphs](https://mlsanity.com/paper/2002.09964/) (2020)
- [Moniqua: Modulo Quantized Communication in Decentralized SGD](https://mlsanity.com/paper/2002.11787/) (2020)
- [Linear Convergent Decentralized Optimization with Compression](https://mlsanity.com/paper/2007.00232/) (2020)
- [On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication](https://mlsanity.com/paper/1902.11163/) (2019)
- [Quantized Distributed Gradient Tracking Algorithm with Linear Convergence in Directed Networks](https://mlsanity.com/paper/2104.03649/) (2021)

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

- [EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization](https://mlsanity.com/paper/2205.04180/) (2022)
- [Finite-Bit Quantization For Distributed Algorithms With Linear Convergence](https://mlsanity.com/paper/2107.11304/) (2021)
- [Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks](https://mlsanity.com/paper/2106.07243/) (2021)
- [CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence](https://mlsanity.com/paper/2301.05872/) (2023)
- [DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2202.00255/) (2022)
- [Towards Faster Decentralized Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2405.20114/) (2024)
- [Scalable Average Consensus with Compressed Communications](https://mlsanity.com/paper/2109.06996/) (2021)
- [On Arbitrary Compression for Decentralized Consensus and Stochastic Optimization over Directed Networks](https://mlsanity.com/paper/2204.08160/) (2022)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)
- [Jointly Computation- and Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2508.15509/) (2025)
- [Communication-Efficient Distributed Learning with Differential Privacy](https://mlsanity.com/paper/2604.02558/) (2026)
- [Compressed Proximal Federated Learning for Non-Convex Composite Optimization on Heterogeneous Data](https://mlsanity.com/paper/2603.07654/) (2026)

## Abstract (arXiv)

Information compression is essential to reduce communication cost in distributed optimization over peer-to-peer networks. This paper proposes a communication-efficient linearly convergent distributed (COLD) algorithm to solve strongly convex optimization problems. By compressing innovation vectors, which are the differences between decision vectors and their estimates, COLD is able to achieve linear convergence for a class of δ-contracted compressors. We explicitly quantify how the compression affects the convergence rate and show that COLD matches the same rate of its uncompressed version. To accommodate a wider class of compressors that includes the binary quantizer, we further design a novel dynamical scaling mechanism and obtain the linearly convergent Dyna-COLD. Importantly, our results strictly improve existing results for the quantized consensus problem. Numerical experiments demonstrate the advantages of both algorithms under different compressors.