Escaping Saddles with Stochastic Gradients

Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, Thomas Hofmann

TL;DR

This paper demonstrates that the inherent noise in vanilla Stochastic Gradient Descent (SGD) is naturally "smart" enough to escape saddle points in non-convex optimization. By introducing the Correlated Negative Curvature (CNC) assumption, the authors provide the first convergence rates to second-order stationary points that are entirely independent of the problem's dimensionality, explaining why SGD remains effective even for models with millions of parameters.

What Problem Does This Paper Address?

In the world of non-convex optimization—which describes almost all modern deep learning—the landscape is littered with saddle points. These are regions where the gradient is zero, but you aren't at a local minimum; instead, there are specific directions (negative curvature) where the loss could still decrease.

Standard Gradient Descent (GD) often gets stuck or crawls painfully slowly near these points. To fix this, researchers previously proposed "perturbed" versions of GD and SGD that add explicit, artificial isotropic noise (noise that spreads equally in all directions) to "kick" the optimizer out of the saddle. However, isotropic noise has a major drawback: as the number of dimensions ($d$) increases, the noise gets spread so thin that the time required to escape a saddle point grows with $d$. In a neural network with millions of parameters, this dependency is a dealbreaker.

The authors ask a fundamental question: Do we actually need to add this artificial noise, or does the "natural" noise already present in SGD (due to sampling mini-batches) do the job better?

Methods

The authors introduce a new theoretical framework based on the Correlated Negative Curvature (CNC) assumption. Unlike isotropic noise, which is uniform, CNC assumes that the stochastic gradient has a significant variance component specifically along the directions of negative curvature (the eigenvectors of the Hessian matrix with negative eigenvalues).

They analyze two main algorithms:

  1. CNC-PGD: A hybrid approach where standard GD is used most of the time, but if the gradient becomes small, a single SGD step is used as a perturbation to escape potential saddles.
  2. CNC-SGD: A version of vanilla SGD that periodically increases the step size. This amplification of inherent noise allows the optimizer to exploit negative curvature without any external noise injection.

The key mathematical contribution is proving that under the CNC assumption, these algorithms reach a second-order stationary point (a point where the gradient is near zero and there is no significant negative curvature) in a number of iterations that does not depend on the dimension $d$.

Datasets

The authors validated their theories using:

  • Learning Half-spaces: A fundamental machine learning problem (related to Perceptrons and SVMs) where they mathematically proved the CNC assumption holds.
  • MNIST: They used feed-forward neural networks of varying widths and depths trained on the MNIST digit classification task to empirically test if the CNC assumption holds in more complex, realistic settings.

Key Insights and Ideas

  • SGD Noise is "Landscape-Aware": The most striking finding is that stochastic gradients aren't just noisy; their noise is structured. The variance of this noise is proportional to the magnitude of the negative eigenvalues. In other words, the "kick" provided by SGD is strongest in the directions where the loss can decrease the most.
  • Escaping the Curse of Dimensionality: Because SGD noise is concentrated along useful directions rather than being spread thin across all $d$ dimensions, the convergence rate becomes dimension-free. This provides a theoretical justification for why simple SGD works so well for massive deep learning models.
  • Implicit Regularization: The authors note that since variance scales with eigenvalues, SGD might naturally avoid overfitting by having lower noise along "non-principal" directions of the data.

Key Results

  • Dimension-Free Convergence: The authors derived the first convergence rates for plain SGD to second-order stationary points that are independent of $d$.
  • Empirical Robustness: As shown in Figure 1, while the variance of isotropic noise along negative curvature directions vanishes as $O(1/d)$ as networks get wider or deeper, the variance of stochastic gradients remains significant and independent of the network's size.
Comparison of stochastic gradient variance vs. isotropic noise
  • Faster Escape: In experiments on learning half-spaces (Figure 2), stochastic methods (SGD and CNC-PGD) escaped saddle points much faster than standard GD.
Methods escaping a saddle point
  • Correlation with Curvature: Figure 3 confirms that the variance of stochastic gradients increases linearly with the magnitude of the negative eigenvalues, supporting the "smart noise" hypothesis.
Variance vs. magnitude of negative eigenvalues

Limitations and Future Work

  • Theoretical Rates: While the convergence is dimension-free, the dependency on the accuracy parameter $\epsilon$ for vanilla SGD is $O(\epsilon^{-10})$, which is theoretically slower than some methods that use explicit perturbations.
  • Step-size Schedules: The CNC-SGD algorithm requires a specific periodic step-size increase to guarantee escape. While adaptive step sizes are common in practice (like Adam or cyclical learning rates), the exact schedule proposed here is more of a theoretical tool.
  • Generalization: The authors hint that the structure of SGD noise might be linked to the superior generalization of deep networks, but proving this connection remains an open and exciting area for future research.

Summary updated

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.
BibTeX
@inproceedings{daneshmand2018escaping,
  author = {Hadi Daneshmand and Jonas Kohler and Aurelien Lucchi and Thomas Hofmann},
  title = {{Escaping Saddles with Stochastic Gradients}},
  booktitle = {International Conference on Machine Learning},
  year = {2018},
  url = {https://openreview.net/forum?id=ryW-IiWuZr},
}
Figure