mlsanityData to 7 Oct 2026

Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks

arXiv 2106.07243 ↗First posted 14 Jun 2021math.OC cs.DC cs.LGcited by 10

Not on the map. Why?

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.

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

Builds on

36 of 69 references.

References · 36

  1. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 561
  2. 2017Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Trainingcited by 471
  3. 2018Sparsified SGD with Memorycited by 373
  4. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
  5. 2019Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communicationcited by 218
  6. 2014EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimizationcited by 160
  7. 2016Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphscited by 149
  8. 2020On Biased Compression for Distributed Learningcited by 140
  9. 2019Distributed Learning with Compressed Gradient Differencescited by 110
  10. 2019Decentralized Deep Learning with Arbitrary Communication Compressioncited by 109
  11. 2018Distributed Stochastic Gradient Tracking Methodscited by 106
  12. 2019DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compressioncited by 98
24 more
  1. 2020Acceleration for Compressed Gradient Descent in Distributed and Federated Optimizationcited by 90
  2. 2018Communication Compression for Decentralized Trainingcited by 87
  3. 2013Distributed optimization over time-varying directed graphscited by 77
  4. 2017A decentralized proximal-gradient method with network independent step-sizes and separated convergence ratescited by 51
  5. 2018Push-Pull Gradient Methods for Distributed Optimization in Networkscited by 45
  6. 2018Optimal Algorithms for Non-Smooth Distributed Optimization in Networkscited by 41
  7. 2018An Exact Quantized Decentralized Gradient Descent Algorithmcited by 34
  8. 2019A Double Residual Compression Algorithm for Efficient Distributed Learningcited by 31
  9. 2018A Dual Approach for Optimal Algorithms in Distributed Optimization over Networkscited by 27
  10. 2015Fast Convergence Rates for Distributed Non-Bayesian Learningcited by 26
  11. 2018A linear algorithm for optimization over directed graphs with geometric convergencecited by 25
  12. 2020Linear Convergent Decentralized Optimization with Compressioncited by 22
  13. 2019textttDeepSqueeze: Decentralization Meets Error-Compensated Compressioncited by 21
  14. 2020On Communication Compression for Distributed Optimization on Heterogeneous Datacited by 18
  15. 2021Distributed Learning Systems with First-order Methodscited by 17
  16. 2016ADD-OPT: Accelerated Distributed Directed Optimizationcited by 13
  17. 2021Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergencecited by 12
  18. 2016On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regressioncited by 9
  19. 2015Distributed Learning Algorithms for Spectrum Sharing in Spatial Random Access Wireless Networkscited by 8
  20. 2021Quantized Distributed Gradient Tracking Algorithm with Linear Convergence in Directed Networkscited by 7
  21. 2015ExtraPush for convex smooth decentralized optimization over directed networkscited by 4
  22. 2019Nested Distributed Gradient Methods with Adaptive Quantized Communicationcited by 3
  23. 2017Optimal Algorithms for Distributed Optimizationcited by 1
  24. 2018Fast Convergence Rates of Distributed Subgradient Methods with Adaptive Quantizationcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 1; 2023: 1; 2024: 0; 2025: 4; 2026: 1.

10 papers.

  1. 2023CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergencecited by 9
  2. 2021Decentralized Composite Optimization with Compressioncited by 7
  3. 2022DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexitycited by 5
  4. 2021Scalable Average Consensus with Compressed Communicationscited by 3
  5. 2025Compressed Decentralized Momentum Stochastic Gradient Methods for Nonconvex Optimizationcited by 2
  6. 2021Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphscited by 1
  7. 2025Modular Distributed Nonconvex Learning with Error Feedbackcited by 0
  8. 2025Pareto-optimal Trade-offs Between Communication and Computation with Flexible Gradient Trackingcited by 0
  9. 2025Adaptive Decentralized Federated Learning for Robust Optimizationcited by 0
  10. 2026SPADE-DFL: Communication-Efficient Decentralized Federated Learning via Derivative-Free Linearized ADMMcited by 0