Accelerated Distributed Nesterov Gradient Descent

Abstract

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

55 pages, 8 figures

References in corpus (4)

• Harnessing Smoothness to Accelerate Distributed Optimization
• A linear algorithm for optimization over directed graphs with geometric convergence
• Accelerated Distributed Nesterov Gradient Descent
• ADD-OPT: Accelerated Distributed Directed Optimization

Cited by in corpus (10)

• Accelerated Distributed Nesterov Gradient Descent
• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• Recent theoretical advances in decentralized distributed convex optimization
• Optimal Distributed Optimization on Slowly Time-Varying Graphs
• Fourier Synthetic Aperture-based Time-resolved Terahertz Imaging
• A Decentralized Primal-Dual Framework for Non-convex Smooth Consensus Optimization
• Accelerated Dual Averaging Methods for Decentralized Constrained Optimization
• Automatic Performance Estimation for Decentralized Optimization
• Non-Smooth Setting of Stochastic Decentralized Convex Optimization Problem Over Time-Varying Graphs
• Accelerated Stochastic Gradient Method with Applications to Consensus Problem in Markov-Varying Networks