Accelerated Distributed Nesterov Gradient Descent

By Guannan Qu, Na Li. 2017

263 citations recorded by the source corpus.

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 method. When the objective function is convex and <inline-formula><tex-math notation="LaTeX">$L$</tex-math></inline-formula>-smooth, we show that it achieves a <inline-formula><tex-math notation="LaTeX">$O(\frac{1}{t^{1.4-\epsilon }})$</tex-math></inline-formula> convergence rate for all <inline-formula><tex-math notation="LaTeX">$\epsilon \in (0,1.4)$</tex-math></inline-formula>. We also show the convergence rate can be improved to <inline-formula><tex-math notation="LaTeX">$O(\frac{1}{t^2})$</tex-math></inline-formula> if the objective function is a composition of a linear map and a strongly convex and smooth function. When the objective function is <inline-formula><tex-math notation="LaTeX">$\mu$</tex-math></inline-formula>-strongly convex and <inline-formula><tex-math notation="LaTeX">$L$</tex-math></inline-formula>-smooth, we show that it achieves a linear convergence rate of <inline-formula><tex-math notation="LaTeX">$O([ 1 - C (\frac{\mu }{L})^{5/7} ]^t)$</tex-math></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$\frac{L}{\mu }$</tex-math></inline-formula> is the condition number of the objective, and <inline-formula><tex-math notation="LaTeX">$C>0$</tex-math></inline-formula> is some constant that does not depend on <inline-formula><tex-math notation="LaTeX">$\frac{L}{\mu }$</tex-math></inline-formula>.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

Robust and Communication-Efficient Collaborative Learning (2019, methodology): “…choices for the convex setting are distributed gradient descent-type methods (Nedic and Ozdaglar, 2009; Jakovetic et al., 2014; Yuan et al., 2016; Qu and Li, 2017), augmented Lagrangian algorithms (Shi et al., 2015a,b; Mokhtari and Ribeiro, 2016), distributed variants of the alternating…”
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, background): “Furthermore, improved analysis of convergence rates over an undirected graph is available in [40] and [41].”
Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks (2019, background): “In a follow up paper, Qu and Li (2017) also considered an acceleration of their algorithm and achieved a linear convergence rate O(exp(−k/Θ(κ5/7))) to the optimal solution.”
A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks (2018, methodology): “We compare the performance of Algorithm 5 with the distributed accelerated method proposed in [68] for non-strongly convex functions (AccDNGD-NSC) for a fixed regularization value μ̂ = 1 · 10−6.”
Optimization over time-varying directed graphs with row and column-stochastic matrices (2018, methodology): “Accelerated methods can be found in [34]–[36], while non-convex problems are considered in [37].”