# Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Aug 2018.

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

- [Decentralized Federated Averaging](https://mlsanity.com/paper/2104.11375/) (2021)
- [RelaySum for Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2110.04175/) (2021)
- [Momentum Tracking: Momentum Acceleration for Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2209.15505/) (2022)
- [Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence](https://mlsanity.com/paper/2305.11420/) (2023)
- [Decentralized Federated Learning with Gradient Tracking over Time-Varying Directed Networks](https://mlsanity.com/paper/2409.17189/) (2024)
- [Locally Differentially Private Gradient Tracking for Distributed Online Learning over Directed Graphs](https://mlsanity.com/paper/2310.16105/) (2023)
- [Parallel Momentum Methods Under Biased Gradient Estimations](https://mlsanity.com/paper/2403.00853/) (2024)
- [Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum](https://mlsanity.com/paper/2406.13041/) (2024)
- [Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs](https://mlsanity.com/paper/2107.12065/) (2021)
- [Asynchronous Distributed Optimization with Delay-free Parameters](https://mlsanity.com/paper/2312.06508/) (2023)
- [Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2601.11435/) (2026)
- [Distributed Finite-Sum Constrained Optimization subject to Nonlinearity on the Node Dynamics](https://mlsanity.com/paper/2203.14527/) (2022)
- [Accelerated Distributed Aggregative Optimization](https://mlsanity.com/paper/2304.08051/) (2023)
- [Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum](https://mlsanity.com/paper/2504.12742/) (2025)

## Abstract (arXiv)

We study distributed optimization to minimize a global objective that is a sum of smooth and strongly-convex local cost functions. Recently, several algorithms over undirected and directed graphs have been proposed that use a gradient tracking method to achieve linear convergence to the global minimizer. However, a connection between these different approaches has been unclear. In this paper, we first show that many of the existing first-order algorithms are in fact related with a simple state transformation, at the heart of which lies the AB algorithm. We then describe textitdistributed heavy-ball, denoted as ABm, i.e., AB with momentum, that combines gradient tracking with a momentum term and uses nonidentical local step-sizes. By simultaneously implementing both row- and column-stochastic weights, ABm removes the conservatism in the related work due to doubly-stochastic weights or eigenvector estimation. ABm thus naturally leads to optimization and average-consensus over both undirected and directed graphs, casting a unifying framework over several well-known consensus algorithms over arbitrary strongly-connected graphs. We show that ABm has a global R-linear rate when the largest step-size is positive and sufficiently small. Following the standard practice in the heavy-ball literature, we numerically show that ABm achieves accelerated convergence especially when the objective function is ill-conditioned.