# Accelerated Distributed Nesterov Gradient Descent

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 May 2017.

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

- [Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks](https://mlsanity.com/paper/2106.04469/) (2021)
- [Activated Gradients for Deep Neural Networks](https://mlsanity.com/paper/2107.04228/) (2021)
- [ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks](https://mlsanity.com/paper/2102.09234/) (2021)
- [Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization](https://mlsanity.com/paper/2104.02596/) (2021)
- [Provable Convergence of Nesterov's Accelerated Gradient Method for Over-Parameterized Neural Networks](https://mlsanity.com/paper/2107.01832/) (2021)
- [Adaptive Federated Learning with Auto-Tuned Clients](https://mlsanity.com/paper/2306.11201/) (2023)
- [An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2212.02387/) (2022)
- [Peer-to-Peer Deep Learning for Beyond-5G IoT](https://mlsanity.com/paper/2310.18861/) (2023)
- [Log-Scale Quantization in Distributed First-Order Methods: Gradient-based Learning from Distributed Data](https://mlsanity.com/paper/2406.00621/) (2024)
- [Decentralized Stochastic Variance Reduced Extragradient Method](https://mlsanity.com/paper/2202.00509/) (2022)
- [QC-ODKLA: Quantized and Communication-Censored Online Decentralized Kernel Learning via Linearized ADMM](https://mlsanity.com/paper/2208.02777/) (2022)
- [DeceFL: A Principled Decentralized Federated Learning Framework](https://mlsanity.com/paper/2107.07171/) (2021)
- [Quasi-Newton Updating for Large-Scale Distributed Learning](https://mlsanity.com/paper/2306.04111/) (2023)
- [Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs](https://mlsanity.com/paper/2107.12065/) (2021)
- [Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping](https://mlsanity.com/paper/2111.02949/) (2021)
- [Distributed optimization: designed for federated learning](https://mlsanity.com/paper/2508.08606/) (2025)
- [Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2601.11435/) (2026)
- [Adaptive Stochastic ADMM for Decentralized Reinforcement Learning in Edge Industrial IoT](https://mlsanity.com/paper/2107.00481/) (2021)
- [Accelerated Distributed Aggregative Optimization](https://mlsanity.com/paper/2304.08051/) (2023)
- [MUSIC: Accelerated Convergence for Distributed Optimization With Inexact and Exact Methods](https://mlsanity.com/paper/2403.02589/) (2024)
- [A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques](https://mlsanity.com/paper/2403.11163/) (2024)
- [High-Dimensional Sparse Data Low-rank Representation via Accelerated Asynchronous Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/2408.16592/) (2024)
- [Distributed Optimization via Energy Conservation Laws in Dilated Coordinates](https://mlsanity.com/paper/2409.19279/) (2024)
- [A distributed semismooth Newton based augmented Lagrangian method for distributed optimization](https://mlsanity.com/paper/2602.23854/) (2026)
- [On the Oracle Complexity of Interpolation-Based Gradient Descent](https://mlsanity.com/paper/2606.19878/) (2026)

## Abstract (arXiv)

This paper considers the distributed optimization problem over a network, where the objective is to optimize a global function formed by a sum of local functions, using only local computation and communication. We develop an Accelerated Distributed Nesterov Gradient Descent (Acc-DNGD) method. When the objective function is convex and L-smooth, we show that it achieves a O(frac1t1.4-ε) convergence rate for all ε∈(0,1.4). We also show the convergence rate can be improved to O(frac1t2) if the objective function is a composition of a linear map and a strongly-convex and smooth function. When the objective function is μ-strongly convex and L-smooth, we show that it achieves a linear convergence rate of O([ 1 - C (fracμL)5/7 ]t), where fracLμ is the condition number of the objective, and C>0 is some constant that does not depend on fracLμ.