Accelerated Distributed Nesterov Gradient Descent
arXiv:1705.07176 · doi:10.1109/TAC.2019.2937496
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 -smooth, we show that it achieves a convergence rate for all . We also show the convergence rate can be improved to 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 -smooth, we show that it achieves a linear convergence rate of , where is the condition number of the objective, and is some constant that does not depend on .
arXiv comment55 pages, 8 figures
References in corpus (8)
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- Harnessing Smoothness to Accelerate Distributed Optimization
- Multi-Agent Distributed Optimization via Inexact Consensus ADMM
- A linear algorithm for optimization over directed graphs with geometric convergence
- Accelerated Distributed Nesterov Gradient Descent
- ADD-OPT: Accelerated Distributed Directed Optimization
- ExtraPush for convex smooth decentralized optimization over directed networks
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