# Optimal Gradient Tracking for Decentralized Optimization

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Oct 2021.

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

- [DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization](https://mlsanity.com/paper/2208.00779/) (2022)
- [Optimal and Efficient Algorithms for Decentralized Online Convex Optimization](https://mlsanity.com/paper/2402.09173/) (2024)
- [An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2212.02387/) (2022)
- [Distributed Random Reshuffling Methods with Improved Convergence](https://mlsanity.com/paper/2306.12037/) (2023)
- [On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2402.02569/) (2024)
- [Achieving Linear Speedup with ProxSkip in Distributed Stochastic Optimization](https://mlsanity.com/paper/2310.07983/) (2023)
- [OledFL: Unleashing the Potential of Decentralized Federated Learning via Opposite Lookahead Enhancement](https://mlsanity.com/paper/2410.06482/) (2024)
- [Fully First-Order Methods for Decentralized Bilevel Optimization](https://mlsanity.com/paper/2410.19319/) (2024)
- [Decentralized Optimization with Topology-Independent Communication](https://mlsanity.com/paper/2509.14488/) (2025)
- [Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Steps](https://mlsanity.com/paper/2407.02689/) (2024)
- [A Double Tracking Method for Optimization with Decentralized Generalized Orthogonality Constraints](https://mlsanity.com/paper/2409.04998/) (2024)
- [Distributed Learning over Arbitrary Topology: Linear Speed-Up with Polynomial Transient Time](https://mlsanity.com/paper/2503.16123/) (2025)
- [Decentralized Stochastic Nonconvex Optimization under the (L0,L1)-Smoothness](https://mlsanity.com/paper/2509.08726/) (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)
- [Provably Convergent Decentralized Optimization over Directed Graphs under Generalized Smoothness](https://mlsanity.com/paper/2601.03566/) (2026)
- [Local adapt-then-combine algorithms for distributed nonsmooth optimization: Achieving provable communication acceleration](https://mlsanity.com/paper/2602.16148/) (2026)
- [S3LDBO: A Snapshot Single-Loop Algorithm for Decentralized Bilevel Optimization](https://mlsanity.com/paper/2605.31311/) (2026)

## Abstract (arXiv)

In this paper, we focus on solving the decentralized optimization problem of minimizing the sum of n objective functions over a multi-agent network. The agents are embedded in an undirected graph where they can only send/receive information directly to/from their immediate neighbors. Assuming smooth and strongly convex objective functions, we propose an Optimal Gradient Tracking (OGT) method that achieves the optimal gradient computation complexity Oleft(√kappalogfrac1εright) and the optimal communication complexity Oleft(√frackappaθlogfrac1εright) simultaneously, where kappa and frac1θ denote the condition numbers related to the objective functions and the communication graph, respectively. To our knowledge, OGT is the first single-loop decentralized gradient-type method that is optimal in both gradient computation and communication complexities. The development of OGT involves two building blocks which are also of independent interest. The first one is another new decentralized gradient tracking method termed "Snapshot" Gradient Tracking (SS-GT), which achieves the gradient computation and communication complexities of Oleft(√kappalogfrac1εright) and Oleft(frac√kappaθlogfrac1εright), respectively. SS-GT can be potentially extended to more general settings compared to OGT. The second one is a technique termed Loopless Chebyshev Acceleration (LCA) which can be implemented "looplessly" but achieve similar effect with adding multiple inner loops of Chebyshev acceleration in the algorithms. In addition to SS-GT, this LCA technique can accelerate many other gradient tracking based methods with respect to the graph condition number frac1θ.