On Nonconvex Decentralized Gradient Descent
Preprint
Abstract
Consensus optimization has received considerable attention in recent years. A number of decentralized algorithms have been proposed for convex consensus optimization. However, on consensus optimization with \emph{nonconvex} objective functions, our understanding to the behavior of these algorithms is limited. When we lose convexity, we cannot hope for obtaining globally optimal solutions (though we still do sometimes). Somewhat surprisingly, we retain most other properties from the convex setting for the decentralized consensus algorithms DGD and Prox-DGD, such as convergence to a (neighborhood of) consensus stationary solution and the rates of convergence when diminishing (constant) step sizes are used. It is worth noting that the Prox-DGD algorithm can handle nonconvex nonsmooth functions assume that their proximal operators can be computed. To establish some of these properties, the existing proofs from the convex setting need changes, and some results require a completely different line of analysis.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Parallel Multi-Block ADMM with o(1 / k) ConvergenceJournal of Scientific Computing, 2016
- A consensus-based decentralized algorithm for non-convex optimization with application to dictionary learning2015
- An Approximate Dual Subgradient Algorithm for Multi-Agent Non-Convex OptimizationIEEE Transactions on Automatic Control, 2012
- Convergence of a Multi-Agent Projected Stochastic Gradient Algorithm for Non-Convex OptimizationIEEE Transactions on Automatic Control, 2012
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methodsMathematical Programming, 2011
- Decentralized Online Convex Programming with local information2011
- Performance Evaluation of the Consensus-Based Distributed Subgradient Method Under Random Communication TopologiesIEEE Journal of Selected Topics in Signal Processing, 2011
- Distributed Stochastic Subgradient Projection Algorithms for Convex OptimizationJournal of Optimization Theory and Applications, 2010
- Distributed Subgradient Methods for Multi-Agent OptimizationIEEE Transactions on Automatic Control, 2009
- On the convergence of the proximal algorithm for nonsmooth functions involving analytic featuresMathematical Programming, 2007