Back to Search
Start Over
An Improved Convergence Analysis for Decentralized Online Stochastic Non-Convex Optimization
- Source :
- IEEE Transactions on Signal Processing. 69:1842-1858
- Publication Year :
- 2021
- Publisher :
- Institute of Electrical and Electronics Engineers (IEEE), 2021.
-
Abstract
- In this paper, we study decentralized online stochastic non-convex optimization over a network of nodes. Integrating a technique called gradient tracking in decentralized stochastic gradient descent, we show that the resulting algorithm, GT-DSGD , enjoys certain desirable characteristics towards minimizing a sum of smooth non-convex functions. In particular, for general smooth non-convex functions, we establish non-asymptotic characterizations of GT-DSGD and derive the conditions under which it achieves network-independent performances that match the centralized minibatch SGD . In contrast, the existing results suggest that GT-DSGD is always network-dependent and is therefore strictly worse than the centralized minibatch SGD . When the global non-convex function additionally satisfies the Polyak-Ċojasiewics (PL) condition, we establish the linear convergence of GT-DSGD up to a steady-state error with appropriate constant step-sizes. Moreover, under stochastic approximation step-sizes, we establish, for the first time, the optimal global sublinear convergence rate on almost every sample path, in addition to the asymptotically optimal sublinear rate in expectation. Since strongly convex functions are a special case of the functions satisfying the PL condition, our results are not only immediately applicable but also improve the currently known best convergence rates and their dependence on problem parameters.
- Subjects :
- FOS: Computer and information sciences
Computer Science - Machine Learning
Mathematical optimization
Linear programming
Sublinear function
Computer science
Machine Learning (stat.ML)
Systems and Control (eess.SY)
02 engineering and technology
Stochastic approximation
Electrical Engineering and Systems Science - Systems and Control
Machine Learning (cs.LG)
Statistics - Machine Learning
Convergence (routing)
FOS: Mathematics
FOS: Electrical engineering, electronic engineering, information engineering
0202 electrical engineering, electronic engineering, information engineering
Computer Science - Multiagent Systems
Electrical and Electronic Engineering
Mathematics - Optimization and Control
020206 networking & telecommunications
Asymptotically optimal algorithm
Stochastic gradient descent
Rate of convergence
Optimization and Control (math.OC)
Signal Processing
Convex function
Multiagent Systems (cs.MA)
Subjects
Details
- ISSN :
- 19410476 and 1053587X
- Volume :
- 69
- Database :
- OpenAIRE
- Journal :
- IEEE Transactions on Signal Processing
- Accession number :
- edsair.doi.dedup.....32f8635ffcc840573e72348e44531d7a