Harnessing Smoothness to Accelerate Distributed Optimization
Top Cited Papers
- 26 April 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Control of Network Systems
- Vol. 5 (3) , 1245-1260
Abstract
There has been a growing effort in studying the distributed optimization problem over a network. The objective is to optimize a global function formed by a sum of local functions, using only local computation and communication. The literature has developed consensus-based distributed (sub)gradient descent (DGD) methods and has shown that they have the same convergence rate $O(\frac{\log t}{\sqrt{t}})$ as the centralized (sub)gradient methods (CGD), when the function is convex but possibly nonsmooth. However, when the function is convex and smooth, under the framework of DGD, it is unclear how to harness the smoothness to obtain a faster convergence rate comparable to CGD's convergence rate. In this paper, we propose a distributed algorithm that, despite using the same amount of communication per iteration as DGD, can effectively harnesses the function smoothness and converge to the optimum with a rate of $O(\frac{1}{t})$ . If the objective function is further strongly convex, our algorithm has a linear convergence rate. Both rates match the convergence rate of CGD. The key step in our algorithm is a novel gradient estimation scheme that uses history information to achieve fast and accurate estimation of the average gradient. To motivate the necessity of history information, we also show that it is impossible for a class of distributed algorithms like DGD to achieve a linear convergence rate without using history information even if the objective function is strongly convex and smooth.Keywords
All Related Versions
Funding Information
- NSF ECCS (1608509)
- NSF CAREER (1553407)
This publication has 25 references indexed in Scilit:
- Distributed Optimization Over Time-Varying Directed GraphsIEEE Transactions on Automatic Control, 2014
- Fast Distributed Gradient MethodsIEEE Transactions on Automatic Control, 2014
- On Distributed Convex Optimization Under Inequality and Equality ConstraintsIEEE Transactions on Automatic Control, 2011
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of MultipliersFoundations and Trends in Machine Learning, 2011
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network ScalingIEEE Transactions on Automatic Control, 2011
- Distributed multi-agent optimization with state-dependent communicationMathematical Programming, 2011
- Distributed Stochastic Subgradient Projection Algorithms for Convex OptimizationJournal of Optimization Theory and Applications, 2010
- Convergence Speed in Distributed Consensus and AveragingSIAM Journal on Control and Optimization, 2009
- Expander graphs and their applicationsBulletin of the American Mathematical Society, 2006
- Communication complexity of convex optimizationJournal of Complexity, 1987