# On Arbitrary Compression for Decentralized Consensus and Stochastic Optimization over Directed Networks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 36 references that are in the map.
- First posted on arXiv 18 Apr 2022.

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

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Adaptive Federated Optimization](https://mlsanity.com/paper/2003.00295/) (2020)
- [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)
- [Federated Optimization:Distributed Optimization Beyond the Datacenter](https://mlsanity.com/paper/1511.03575/) (2015)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding](https://mlsanity.com/paper/1610.02132/) (2016)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [Decentralized Deep Learning with Arbitrary Communication Compression](https://mlsanity.com/paper/1907.09356/) (2019)
- [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)
- [Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs](https://mlsanity.com/paper/1406.2075/) (2014)
- [A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks](https://mlsanity.com/paper/1809.00710/) (2018)
- [Quantized Decentralized Stochastic Learning over Directed Graphs](https://mlsanity.com/paper/2002.09964/) (2020)
- [Communication-efficient SGD: From Local SGD to One-Shot Averaging](https://mlsanity.com/paper/2106.04759/) (2021)
- [Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence](https://mlsanity.com/paper/2105.06697/) (2021)
- [Nonasymptotic Convergence Rates for Cooperative Learning Over Time-Varying Directed Graphs](https://mlsanity.com/paper/1410.1977/) (2014)
- [Communication-efficient Distributed Cooperative Learning with Compressed Beliefs](https://mlsanity.com/paper/2102.07767/) (2021)
- [Scalable Average Consensus with Compressed Communications](https://mlsanity.com/paper/2109.06996/) (2021)

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

- [D-SVM over Networked Systems with Non-Ideal Linking Conditions](https://mlsanity.com/paper/2304.06667/) (2023)

## Abstract (arXiv)

We study the decentralized consensus and stochastic optimization problems with compressed communications over static directed graphs. We propose an iterative gradient-based algorithm that compresses messages according to a desired compression ratio. The proposed method provably reduces the communication overhead on the network at every communication round. Contrary to existing literature, we allow for arbitrary compression ratios in the communicated messages. We show a linear convergence rate for the proposed method on the consensus problem. Moreover, we provide explicit convergence rates for decentralized stochastic optimization problems on smooth functions that are either (i) strongly convex, (ii) convex, or (iii) non-convex. Finally, we provide numerical experiments to illustrate convergence under arbitrary compression ratios and the communication efficiency of our algorithm.