An Alternative View: When Does SGD Escape Local Minima?

Abstract

Stochastic gradient descent (SGD) is widely used in machine learning. Although being commonly viewed as a fast but not accurate version of gradient descent (GD), it always finds better solutions than GD for modern neural networks. In order to understand this phenomenon, we take an alternative view that SGD is working on the convolved (thus smoothed) version of the loss function. We show that, even if the function $f$ has many bad local minima or saddle points, as long as for every point $x$, the weighted average of the gradients of its neighborhoods is one point convex with respect to the desired solution $x^{\ast }$, SGD will get close to, and then stay around $x^{\ast }$ with constant probability. More specifically, SGD will not get stuck at "sharp" local minima with small diameters, as long as the neighborhoods of these regions contain enough gradient information. The neighborhood size is controlled by step size and gradient noise. Our result identifies a set of functions that SGD provably works, which is much larger than the set of convex functions. Empirically, we observe that the loss surface of neural networks enjoys nice one point convexity properties locally, therefore our theorem helps explain why SGD works so well for neural networks.

References in corpus (4)

• Adam: A Method for Stochastic Optimization
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Train longer, generalize better: closing the generalization gap in large batch training of neural networks
• A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics

Cited by in corpus (19)

• Surrogate Modeling for Fluid Flows Based on Physics-Constrained Deep Learning Without Simulation Data
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Mind Mappings: Enabling Efficient Algorithm-Accelerator Mapping Space Search
• Real-time Plant Health Assessment Via Implementing Cloud-based Scalable Transfer Learning On AWS DeepLens
• On exponential convergence of SGD in non-convex over-parametrized learning
• Stochastic AUC Maximization with Deep Neural Networks
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• The Impact of Local Geometry and Batch Size on Stochastic Gradient Descent for Nonconvex Problems
• Robust and On-the-fly Dataset Denoising for Image Classification
• Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory
• Intelligence plays dice: Stochasticity is essential for machine learning
• Communication-efficient Decentralized Machine Learning over Heterogeneous Networks
• On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimization
• Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models
• Trajectory Normalized Gradients for Distributed Optimization
• Loss Landscape Dependent Self-Adjusting Learning Rates in Decentralized Stochastic Gradient Descent
• Adaptive Minimax Regret against Smooth Logarithmic Losses over High-Dimensional ${\ell }_1$-Balls via Envelope Complexity