# Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 79 references that are in the map.
- First posted on arXiv 6 Apr 2021.

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

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Towards Federated Learning at Scale: System Design](https://mlsanity.com/paper/1902.01046/) (2019)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [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)
- [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)
- [A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates](https://mlsanity.com/paper/1704.07807/) (2017)
- [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)
- [Optimal Algorithms for Non-Smooth Distributed Optimization in Networks](https://mlsanity.com/paper/1806.00291/) (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)
- [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)
- [Distributed Nonconvex Constrained Optimization over Time-Varying Digraphs](https://mlsanity.com/paper/1809.01106/) (2018)
- [Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions](https://mlsanity.com/paper/1811.03982/) (2018)
- [Multi-consensus Decentralized Accelerated Gradient Descent](https://mlsanity.com/paper/2005.00797/) (2020)
- [Decentralized Proximal Gradient Algorithms with Linear Convergence Rates](https://mlsanity.com/paper/1909.06479/) (2019)
- [An Optimal Algorithm for Decentralized Finite Sum Optimization](https://mlsanity.com/paper/2005.10675/) (2020)
- [Convergence Rate of Distributed ADMM over Networks](https://mlsanity.com/paper/1601.00194/) (2016)
- [Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization](https://mlsanity.com/paper/1512.08122/) (2015)
- [Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2009.04373/) (2020)
- [ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks](https://mlsanity.com/paper/2102.09234/) (2021)
- [Revisiting EXTRA for Smooth Distributed Optimization](https://mlsanity.com/paper/2002.10110/) (2020)

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

- [Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks](https://mlsanity.com/paper/2106.04469/) (2021)
- [Optimal Algorithms for Decentralized Stochastic Variational Inequalities](https://mlsanity.com/paper/2202.02771/) (2022)
- [DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization](https://mlsanity.com/paper/2208.00779/) (2022)
- [Optimal Complexity in Non-Convex Decentralized Learning over Time-Varying Networks](https://mlsanity.com/paper/2211.00533/) (2022)
- [Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs](https://mlsanity.com/paper/2107.12065/) (2021)
- [Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks](https://mlsanity.com/paper/2405.18031/) (2024)
- [Time-varying Mixing Matrix Design for Energy-efficient Decentralized Federated Learning](https://mlsanity.com/paper/2512.24069/) (2025)
- [Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization](https://mlsanity.com/paper/2606.07496/) (2026)
- [MUSIC: Accelerated Convergence for Distributed Optimization With Inexact and Exact Methods](https://mlsanity.com/paper/2403.02589/) (2024)
- [Distributed Optimization via Energy Conservation Laws in Dilated Coordinates](https://mlsanity.com/paper/2409.19279/) (2024)
- [A Stochastic Approximation Approach for Efficient Decentralized Optimization on Random Networks](https://mlsanity.com/paper/2410.18774/) (2024)

## Abstract (arXiv)

Decentralized optimization over time-varying graphs has been increasingly common in modern machine learning with massive data stored on millions of mobile devices, such as in federated learning. This paper revisits the widely used accelerated gradient tracking and extends it to time-varying graphs. We prove that the practical single loop accelerated gradient tracking needs O((fracγ1-σγ)2√fracLε) and O((fracγ1-σγ)1.5√fracLμlogfrac1ε) iterations to reach an ε-optimal solution over time-varying graphs when the problems are nonstrongly convex and strongly convex, respectively, where γ and σγ are two common constants charactering the network connectivity, L and μ are the smoothness and strong convexity constants, respectively, and one iteration corresponds to one gradient oracle call and one communication round. Our convergence rates improve significantly over the ones of O(frac1ε5/7) and O((fracLμ)5/7frac1(1-σ)1.5logfrac1ε), respectively, which were proved in the original literature of accelerated gradient tracking only for static graphs, where fracγ1-σγ equals frac11-σ when the network is time-invariant. When combining with a multiple consensus subroutine, the dependence on the network connectivity constants can be further improved to O(1) and O(fracγ1-σγ) for the gradient oracle and communication round complexities, respectively. When the network is static, by employing the Chebyshev acceleration, our complexities exactly match the lower bounds without hiding any poly-logarithmic factor for both nonstrongly convex and strongly convex problems.