# Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks

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

## Key facts

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

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

- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [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)
- [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)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [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)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression](https://mlsanity.com/paper/1905.05957/) (2019)
- [Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization](https://mlsanity.com/paper/2002.11364/) (2020)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013)
- [A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates](https://mlsanity.com/paper/1704.07807/) (2017)
- [Push-Pull Gradient Methods for Distributed Optimization in Networks](https://mlsanity.com/paper/1810.06653/) (2018)
- [Optimal Algorithms for Non-Smooth Distributed Optimization in Networks](https://mlsanity.com/paper/1806.00291/) (2018)
- [An Exact Quantized Decentralized Gradient Descent Algorithm](https://mlsanity.com/paper/1806.11536/) (2018)
- [A Double Residual Compression Algorithm for Efficient Distributed Learning](https://mlsanity.com/paper/1910.07561/) (2019)
- [A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks](https://mlsanity.com/paper/1809.00710/) (2018)
- [Fast Convergence Rates for Distributed Non-Bayesian Learning](https://mlsanity.com/paper/1508.05161/) (2015)
- [A linear algorithm for optimization over directed graphs with geometric convergence](https://mlsanity.com/paper/1803.02503/) (2018)
- [textttDeepSqueeze: Decentralization Meets Error-Compensated Compression](https://mlsanity.com/paper/1907.07346/) (2019)
- [Linear Convergent Decentralized Optimization with Compression](https://mlsanity.com/paper/2007.00232/) (2020)
- [On Communication Compression for Distributed Optimization on Heterogeneous Data](https://mlsanity.com/paper/2009.02388/) (2020)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [ADD-OPT: Accelerated Distributed Directed Optimization](https://mlsanity.com/paper/1607.04757/) (2016)
- [Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence](https://mlsanity.com/paper/2105.06697/) (2021)
- [On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regression](https://mlsanity.com/paper/1606.03000/) (2016)

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

- [CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence](https://mlsanity.com/paper/2301.05872/) (2023)
- [Decentralized Composite Optimization with Compression](https://mlsanity.com/paper/2108.04448/) (2021)
- [DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2202.00255/) (2022)
- [Log-Scale Quantization in Distributed First-Order Methods: Gradient-based Learning from Distributed Data](https://mlsanity.com/paper/2406.00621/) (2024)
- [Scalable Average Consensus with Compressed Communications](https://mlsanity.com/paper/2109.06996/) (2021)
- [Compressed Decentralized Momentum Stochastic Gradient Methods for Nonconvex Optimization](https://mlsanity.com/paper/2508.04950/) (2025)
- [Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs](https://mlsanity.com/paper/2107.12065/) (2021)
- [Modular Distributed Nonconvex Learning with Error Feedback](https://mlsanity.com/paper/2503.14055/) (2025)
- [Pareto-optimal Trade-offs Between Communication and Computation with Flexible Gradient Tracking](https://mlsanity.com/paper/2509.18129/) (2025)
- [Adaptive Decentralized Federated Learning for Robust Optimization](https://mlsanity.com/paper/2512.02852/) (2025)
- [Distributed TD Tracking with Linear Function Approximation over Directed Communication Networks](https://mlsanity.com/paper/2605.04466/) (2026)
- [SPADE-DFL: Communication-Efficient Decentralized Federated Learning via Derivative-Free Linearized ADMM](https://mlsanity.com/paper/2609.29446/) (2026)

## Abstract (arXiv)

In this paper, we propose two communication efficient decentralized optimization algorithms over a general directed multi-agent network. The first algorithm, termed Compressed Push-Pull (CPP), combines the gradient tracking Push-Pull method with communication compression. We show that CPP is applicable to a general class of unbiased compression operators and achieves linear convergence rate for strongly convex and smooth objective functions. The second algorithm is a broadcast-like version of CPP (B-CPP), and it also achieves linear convergence rate under the same conditions on the objective functions. B-CPP can be applied in an asynchronous broadcast setting and further reduce communication costs compared to CPP. Numerical experiments complement the theoretical analysis and confirm the effectiveness of the proposed methods.