On Nonconvex Decentralized Gradient Descent
Top Cited Papers
- 21 March 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 66 (11) , 2834-2848
Abstract
Consensus optimization has received considerable attention in recent years. A number of decentralized algorithms have been proposed for convex consensus optimization. However, to the behaviors or consensus nonconvex optimization, our understanding is more limited. When we lose convexity, we cannot hope that our algorithms always return global solutions though they sometimes still do. Somewhat surprisingly, the decentralized consensus algorithms, DGD and Prox-DGD, retain most other properties that are known in the convex setting. In particular, when diminishing (or constant) step sizes are used, we can prove convergence to a (or a neighborhood of) consensus stationary solution under some regular assumptions. It is worth noting that Prox-DGD can handle nonconvex nonsmooth functions if their proximal operators can be computed. Such functions include SCAD, MCP, and ℓ quasi-norms, q ∈ [0,1). Similarly, Prox-DGD can take the constraint to a nonconvex set with an easy projection. To establish these properties, we have to introduce a completely different line of analysis, as well as modify existing proofs that were used in the convex setting.Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (61603162, 11501440, 61772246, 61603163)
- NSF (DMS-1720237, ECCS-1462398, N00014171216)
This publication has 52 references indexed in Scilit:
- Optimal Resource Allocation in Coordinated Multi-Cell SystemsFoundations and Trends® in Communications and Information Theory, 2013
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methodsMathematical Programming, 2011
- Distributed Stochastic Subgradient Projection Algorithms for Convex OptimizationJournal of Optimization Theory and Applications, 2010
- Nearly unbiased variable selection under minimax concave penaltyThe Annals of Statistics, 2010
- Lower Bound Theory of Nonzero Entries in Solutions of $\ell_2$-$\ell_p$ MinimizationSIAM Journal on Scientific Computing, 2010
- Consensus in Ad Hoc WSNs With Noisy Links—Part I: Distributed Estimation of Deterministic SignalsIEEE Transactions on Signal Processing, 2007
- On the convergence of the proximal algorithm for nonsmooth functions involving analytic featuresMathematical Programming, 2007
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle PropertiesJournal of the American Statistical Association, 2001
- Sur la géométrie semi- et sous- analytiqueAnnales de l'institut Fourier, 1993
- Distributed asynchronous deterministic and stochastic gradient optimization algorithmsIEEE Transactions on Automatic Control, 1986