# Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs

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

## Key facts

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

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [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)
- [Communication-Efficient Algorithms for Decentralized and Stochastic Optimization](https://mlsanity.com/paper/1701.03961/) (2017)
- [Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2006.11773/) (2020)
- [Fast Convergence Rates for Distributed Non-Bayesian Learning](https://mlsanity.com/paper/1508.05161/) (2015)
- [Accelerated Distributed Nesterov Gradient Descent](https://mlsanity.com/paper/1705.07176/) (2017)
- [A linear algorithm for optimization over directed graphs with geometric convergence](https://mlsanity.com/paper/1803.02503/) (2018)
- [Linear Convergent Decentralized Optimization with Compression](https://mlsanity.com/paper/2007.00232/) (2020)
- [Convergence Rate of Distributed ADMM over Networks](https://mlsanity.com/paper/1601.00194/) (2016)
- [ADD-OPT: Accelerated Distributed Directed Optimization](https://mlsanity.com/paper/1607.04757/) (2016)
- [Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking](https://mlsanity.com/paper/1808.02942/) (2018)
- [S-ADDOPT: Decentralized stochastic first-order optimization over directed graphs](https://mlsanity.com/paper/2005.07785/) (2020)
- [Linear convergence in optimization over directed graphs with row-stochastic matrices](https://mlsanity.com/paper/1611.06160/) (2016)
- [Revisiting EXTRA for Smooth Distributed Optimization](https://mlsanity.com/paper/2002.10110/) (2020)
- [Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks](https://mlsanity.com/paper/2106.07243/) (2021)
- [Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimization](https://mlsanity.com/paper/1803.10359/) (2018)
- [Distributed stochastic optimization with gradient tracking over strongly-connected networks](https://mlsanity.com/paper/1903.07266/) (2019)
- [Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization](https://mlsanity.com/paper/2104.02596/) (2021)
- [On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regression](https://mlsanity.com/paper/1606.03000/) (2016)
- [Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks](https://mlsanity.com/paper/1910.08701/) (2019)
- [Distributed Learning Algorithms for Spectrum Sharing in Spatial Random Access Wireless Networks](https://mlsanity.com/paper/1507.05664/) (2015)

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

- [Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2601.11435/) (2026)

## 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.