Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
arXiv:2003.02818
Abstract
In centralized settings, it is well known that stochastic gradient descent (SGD) avoids saddle points and converges to local minima in nonconvex problems. However, similar guarantees are lacking for distributed first-order algorithms. The paper studies distributed stochastic gradient descent (D-SGD)--a simple network-based implementation of SGD. Conditions under which D-SGD avoids saddle points and converges to local minima are studied. First, we consider the problem of computing critical points. Assuming loss functions are nonconvex and possibly nonsmooth, it is shown that, for each fixed initialization, D-SGD converges to critical points of the loss with probability one. Next, we consider the problem of avoiding saddle points. In this case, we again assume that loss functions may be nonconvex and nonsmooth, but are smooth in a neighborhood of a saddle point. It is shown that, for any fixed initialization, D-SGD avoids such saddle points with probability one. Results are proved by studying the underlying (distributed) gradient flow, using the ordinary differential equation (ODE) method of stochastic approximation, and extending classical techniques from dynamical systems theory such as stable manifolds. Results are proved in the general context of subspace-constrained optimization, of which D-SGD is a special case.
References in corpus (17)
- Adam: A Method for Stochastic Optimization
- Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
- Federated Optimization:Distributed Optimization Beyond the Datacenter
- A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
- A Variational Perspective on Accelerated Methods in Optimization
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization
- Non-convex Optimization for Machine Learning
- Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
- DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
- Efficient approaches for escaping higher order saddle points in non-convex optimization
- Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
- Gradient Descent Can Take Exponential Time to Escape Saddle Points
- On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
- Adaptation and learning over networks under subspace constraints -- Part I: Stability Analysis
- Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
- Decentralized Langevin Dynamics
Cited by in corpus (8)
- An improved convergence analysis for decentralized online stochastic non-convex optimization
- A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
- Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
- A Stochastic Proximal Gradient Framework for Decentralized Non-Convex Composite Optimization: Topology-Independent Sample Complexity and Communication Efficiency
- A fast randomized incremental gradient method for decentralized non-convex optimization
- Distributed Gradient Methods for Nonconvex Optimization: Local and Global Convergence Guarantees
- On the Convergence of NEAR-DGD for Nonconvex Optimization with Second Order Guarantees
- Asymptotic Properties of - Method with Diminishing Stepsize