# Distributed Nesterov gradient methods over arbitrary graphs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jan 2019.

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

- [Distributed saddle point problems for strongly concave-convex functions](https://mlsanity.com/paper/2202.05812/) (2022)
- [Variance reduced stochastic optimization over directed graphs with row and column stochastic weights](https://mlsanity.com/paper/2202.03346/) (2022)
- [Asynchronous Parallel Incremental Block-Coordinate Descent for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03263/) (2022)
- [Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2601.11435/) (2026)
- [Accelerated Distributed Aggregative Optimization](https://mlsanity.com/paper/2304.08051/) (2023)
- [Row-Stochastic Matrices Can Provably Outperform Doubly Stochastic Matrices in Decentralized Learning](https://mlsanity.com/paper/2511.19513/) (2025)

## Abstract (arXiv)

In this letter, we introduce a distributed Nesterov method, termed as ABN, that does not require doubly-stochastic weight matrices. Instead, the implementation is based on a simultaneous application of both row- and column-stochastic weights that makes this method applicable to arbitrary (strongly-connected) graphs. Since constructing column-stochastic weights needs additional information (the number of outgoing neighbors at each agent), not available in certain communication protocols, we derive a variation, termed as FROZEN, that only requires row-stochastic weights but at the expense of additional iterations for eigenvector learning. We numerically study these algorithms for various objective functions and network parameters and show that the proposed distributed Nesterov methods achieve acceleration compared to the current state-of-the-art methods for distributed optimization.