Escaping Saddles with Stochastic Gradients

By Hadi Daneshmand, Jonas Köhler, Aurélien Lucchi, Thomas Hofmann. 2018

176 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Learning explanations that are hard to vary (2020, positive): “2Similar results hold for SGD [Daneshmand et al., 2018, Kushner and Yin, 2003], momentum [Jin et al., 2017], and adaptive methods including Adam [Barakat and Bianchi, 2019] and Adagrad [Ward et al., 2019].”
A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks (2019, unknown): “SGD is widely used in deep learning with a great success in its computational efficiency (Bottou, 2010; Bottou & Bousquet, 2008; Daneshmand et al., 2018).”
Demystifying Dropout (2019, background): “Besides, a number of works (Ge et al., 2015; Jin et al., 2017; Zhang et al., 2017; Daneshmand et al., 2018) have theoretically justified that noise does be helpful for SGD to escape from saddle points.”
Adaptive norms for deep learning with regularized Newton methods (2019, methodology): “What makes SGD so attractive is its simplicity and per-iteration cost that is independent of the size of the training set ( n ) and scale linearly in the dimensionality ( d ).”
Ellipsoidal Trust Region Methods and the Marginal Value of Hessian Information for Neural Network Training (2019, methodology): “For neural network training, a recent line of research proclaims the effectiveness of SGD but the results usually come at the cost of fairly strong assumptions such as heavy overparametrization and Gaussian inputs [28, 12, 50, 29, 5].”
Escaping Saddle Points with Adaptive Gradient Methods (2019, methodology): “Most relevant to our work is that of Daneshmand et al. [2018], who prove convergence of SGD with better rates than Ge et al. [2015].”
Noise against noise: stochastic label noise helps combat inherent label noise (2021, background): “In terms of escaping from sharp minima, there are previous works (Zhu et al., 2019; Daneshmand et al., 2018) that study the inheret noise in SGD, showing that the noise covariance containing curvature information performs better.”
The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Minima and Regularization Effects (2018, background): “In non-convex settings, the characterization of how SGD escapes from stationary points, including saddle points and local minima, was analyzed in [4, 10, 8].”
The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects (2018, background): “In non-convex settings, the characterization of how SGD escapes from stationary points, including saddle points and local minima, was analyzed in (Daneshmand et al., 2018; Jin et al., 2017; Hu et al., 2017).”