Escaping Saddles with Stochastic Gradients

Abstract

We analyze the variance of stochastic gradients along negative curvature directions in certain non-convex machine learning models and show that stochastic gradients exhibit a strong component along these directions. Furthermore, we show that - contrary to the case of isotropic noise - this variance is proportional to the magnitude of the corresponding eigenvalues and not decreasing in the dimensionality. Based upon this observation we propose a new assumption under which we show that the injection of explicit, isotropic noise usually applied to make gradient descent escape saddle points can successfully be replaced by a simple SGD step. Additionally - and under the same condition - we derive the first convergence rate for plain SGD to a second-order stationary point in a number of iterations that is independent of the problem dimension.

References in corpus (14)

• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• How to Escape Saddle Points Efficiently
• Gradient Descent Converges to Minimizers
• The Power of Normalization: Faster Evasion of Saddle Points
• Neon2: Finding Local Minima via First-Order Oracles
• A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
• A Generic Approach for Escaping Saddle points
• Learning Halfspaces and Neural Networks with Random Initialization
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation

Cited by in corpus (35)

• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
• Efficiently escaping saddle points on manifolds
• On the different regimes of Stochastic Gradient Descent
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions
• Finding Local Minima via Stochastic Nested Variance Reduction
• Positive-Negative Momentum: Manipulating Stochastic Gradient Noise to Improve Generalization
• On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
• Escaping Saddle Points Faster with Stochastic Momentum
• Replica Exchange for Non-Convex Optimization
• Spherical Motion Dynamics: Learning Dynamics of Neural Network with Normalization, Weight Decay, and SGD
• Exit Time Analysis for Approximations of Gradient Descent Trajectories Around Saddle Points
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
• On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization
• Student Specialization in Deep ReLU Networks With Finite Width and Input Dimension
• The loss landscape of deep linear neural networks: a second-order analysis
• On the Convex Behavior of Deep Neural Networks in Relation to the Layers' Width
• E2-Train: Training State-of-the-art CNNs with Over 80% Energy Savings
• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
• Enhance Diffusion to Improve Robust Generalization
• Stochastic Approximation for Online Tensorial Independent Component Analysis
• Improve SGD Training via Aligning Mini-batches
• Mixing of Stochastic Accelerated Gradient Descent
• Binary Search and First Order Gradient Based Method for Stochastic Optimization
• On the Second-order Convergence Properties of Random Search Methods
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Score-Aware Policy-Gradient and Performance Guarantees using Local Lyapunov Stability
• Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
• Characterization of Excess Risk for Locally Strongly Convex Population Risk
• SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points
• Noise-induced degeneration in online learning
• Second-Order Convergence of Asynchronous Parallel Stochastic Gradient Descent: When Is the Linear Speedup Achieved?
• Adaptive norms for deep learning with regularized Newton methods
• Continuous-time Models for Stochastic Optimization Algorithms
• One-dimensional System Arising in Stochastic Gradient Descent