mlsanityData to 7 Oct 2026

Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs

arXiv 2107.12065 ↗First posted 26 Jul 2021math.OC cs.DC cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

We consider the decentralized optimization problem, where a network of n agents aims to collaboratively minimize the average of their individual smooth and convex objective functions through peer-to-peer communication in a directed graph. To tackle this problem, we propose two accelerated gradient tracking methods, namely APD and APD-SC, for non-strongly convex and strongly convex objective functions, respectively. We show that APD and APD-SC converge at the rates Oleft(frac1k2right) and Oleft(left(1 - C√fracμLright)kright), respectively, up to constant factors depending only on the mixing matrix. APD and APD-SC are the first decentralized methods over unbalanced directed graphs that achieve the same provable acceleration as centralized methods. Numerical experiments demonstrate the effectiveness of both methods.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 35 of its 69 references that are in the map. First posted on arXiv 26 Jul 2021.

Builds on

35 of 69 references.

References · 35

  1. 2014Convex Optimization: Algorithms and Complexitycited by 569
  2. 2014EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimizationcited by 160
  3. 2013On the Convergence of Decentralized Gradient Descentcited by 158
  4. 2016Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphscited by 149
  5. 2016NEXT: In-Network Nonconvex Optimizationcited by 107
  6. 2018Distributed Stochastic Gradient Tracking Methodscited by 106
  7. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 81
  8. 2013Distributed optimization over time-varying directed graphscited by 77
  9. 2014Linear Coupling: An Ultimate Unification of Gradient and Mirror Descentcited by 58
  10. 2017A decentralized proximal-gradient method with network independent step-sizes and separated convergence ratescited by 51
  11. 2018Push-Pull Gradient Methods for Distributed Optimization in Networkscited by 45
  12. 2020Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimizationcited by 43
23 more
  1. 2017Communication-Efficient Algorithms for Decentralized and Stochastic Optimizationcited by 42
  2. 2015Fast Convergence Rates for Distributed Non-Bayesian Learningcited by 26
  3. 2018A linear algorithm for optimization over directed graphs with geometric convergencecited by 25
  4. 2017Accelerated Distributed Nesterov Gradient Descentcited by 24
  5. 2020Linear Convergent Decentralized Optimization with Compressioncited by 22
  6. 2016Convergence Rate of Distributed ADMM over Networkscited by 16
  7. 2018Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient trackingcited by 14
  8. 2016ADD-OPT: Accelerated Distributed Directed Optimizationcited by 13
  9. 2016Linear convergence in optimization over directed graphs with row-stochastic matricescited by 12
  10. 2020Revisiting EXTRA for Smooth Distributed Optimizationcited by 12
  11. 2020S-ADDOPT: Decentralized stochastic first-order optimization over directed graphscited by 12
  12. 2018Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimizationcited by 11
  13. 2019Distributed stochastic optimization with gradient tracking over strongly-connected networkscited by 11
  14. 2021Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimizationcited by 11
  15. 2021Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networkscited by 10
  16. 2016On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regressioncited by 9
  17. 2019Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networkscited by 9
  18. 2015Distributed Learning Algorithms for Spectrum Sharing in Spatial Random Access Wireless Networkscited by 8
  19. 2019Accelerated Primal-Dual Algorithms for Distributed Smooth Convex Optimization over Networkscited by 7
  20. 2014Convex Optimization for Big Datacited by 4
  21. 2013Explicit Convergence Rate of a Distributed Alternating Direction Method of Multiplierscited by 3
  22. 2015On the Distributed Optimization over Directed Networkscited by 3
  23. 2018Fully Asynchronous Push-Sum With Growing Intercommunication Intervalscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noisecited by 1