Escaping Saddles with Stochastic Gradients

2018/03/15 by Hadi Daneshmand, Jonas Köhler, Daneshmand, Hadi +5 · 8 citations
Computer Science · Mathematics · Engineering · #Stochastic Gradient Optimization Techniques #Markov Chains and Monte Carlo Methods #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1803.05999

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.

Citations

• Gradient Descent Converges to Minimizers
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient\n Descent on Non-Convex Functions
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Neon2: Finding Local Minima via First-Order Oracles
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Cited by

• Distributed Learning in Non-Convex Environments—Part I: Agreement at a Linear Rate
• Nullspace-preserving high-index saddle dynamics method for degenerate multiple solution problems
• A Stochastic Algorithm for Searching Saddle Points with Convergence Guarantee
• Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
• Finding Local Minima via Stochastic Nested Variance Reduction
• Unveiling m-Sharpness Through the Structure of Stochastic Gradient Noise
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
• Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validation

Related

• Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods
• Second-Order Guarantees of Stochastic Gradient Descent in Non-Convex Optimization
• Almost Sure Saddle Avoidance of Stochastic Gradient Methods without the Bounded Gradient Assumption
• A Theoretical Analysis of Noise Geometry in Stochastic Gradient Descent
• The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects