Quasi-potential theory for escape problem: Quantitative sharpness effect on SGD's escape from local minima

Hikaru Ibayashi, Masaaki Imaizumi

TL;DR

This paper introduces classical quasi-potential theory from large deviation theory to analyze the "escape problem" of Stochastic Gradient Descent (SGD) from local minima. The authors prove that while sharp loss geometry inherently increases the barrier to escape, SGD’s anisotropic, Hessian-aligned gradient noise dramatically weakens this barrier, enabling exponentially faster escape from sharp minima compared to isotropic noise.

What Problem Does This Paper Address?

In deep learning, models trained with SGD often settle into "flat" local minima that generalize well, avoiding sharp minima that tend to overfit. A prominent hypothesis is that SGD dynamically escapes sharp minima much more readily than flat ones.

However, existing theoretical analyses of this escape problem have several notable gaps:

  1. They often assume SGD reaches a stationary distribution before escaping (which can take exponentially many steps).
  2. They introduce implicit auxiliary variables that obscure the exact relationship between escape time and loss curvature.
  3. They typically study continuous-time diffusions and omit the discretization error inherent in actual, discrete SGD updates.

This paper tackles these issues by establishing a rigorous, explicit formula for the mean exit time from a basin without requiring stationary distribution assumptions.

Methods

The authors build their framework using the Freidlin–Wentzell quasi-potential theory from Large Deviation Theory:

  • Trajectory Steepness & Action Functional: The authors define the steepness (action functional) $S_{0T}(\varphi)$ of an escape trajectory $\varphi$, measuring the work required for SGD to move against the negative gradient field under noise covariance $C(\theta)$.
  • Quasi-Potential via Hamilton–Jacobi: The easiest path out of a local minimum $\theta^*$ defines the quasi-potential $V(\theta) = \inf_{T, \varphi} S_{0T}(\varphi)$, which solves a Hamilton–Jacobi PDE: $$\frac{1}{2}\nabla V(\theta)^\top C(\theta)^{1/2} \nabla V(\theta) - \nabla L(\theta)^\top \nabla V(\theta) = 0$$
  • Exit Time Derivation: The mean exit time $\mathbb{E}[\tau]$ out of an $r$-neighborhood $D$ scales as $\exp\left[\frac{B}{\eta} V_0\right]$, where $V_0 = \min_{\theta \in \partial D} V(\theta)$, $B$ is the batch size, and $\eta$ is the learning rate.
  • Discrete Correction: The authors adapt boundary-correction techniques for stopped diffusions (Gobet & Menozzi, 2010) to rigorously bound the difference between continuous-time SGD and discrete SGD steps.

Datasets

  • AVILA Dataset: A real-world UCI benchmark dataset based on medieval manuscript features.
  • The authors train a multi-layer perceptron (MLP) with mean squared error and $\ell_2$ regularization on AVILA, then re-scale coordinates ($\theta \mapsto \sqrt{\alpha}\theta$) to vary minimum sharpness $\alpha \sim \lambda$ and measure empirical escape times over 1,000 independent trials.
  • No new benchmark datasets were introduced.

Key Insights and Ideas

  • Sharpness Slows Down Pure Geometry: Under an isotropic noise model ($C(\theta) = I$), increasing curvature $\lambda = \lambda_{\min}(H^*)$ exponentially increases the exit time: $$\mathbb{E}[\tau_{\text{isoSGD}}] = \exp\left[ \frac{2B}{\eta} r^2 \lambda \right]$$ Geometrically, steeper walls mean a higher potential barrier to climb.

  • Anisotropic Noise Cancels the Penalty: Because mini-batch gradient covariance naturally aligns with the Hessian ($C(\theta) \approx H^*$), gradient noise is strongest along the steepest directions. Solving the Hamilton–Jacobi equation reveals that the quasi-potential drops from scaling with $\lambda$ to $\lambda^{1/2}$: $$\mathbb{E}[\tau_{\text{SGD}}] = \exp\left[ \frac{2B}{\eta} r^2 \lambda^{1/2} \right]$$ Consequently, SGD escapes sharp minima exponentially faster than isotropic noise by a factor of $\exp[\lambda^{1/2}]$.

  • Discrete Updates Do Not Break the Physics: The discrete mean exit time satisfies $\mathbb{E}[\nu_{\text{SGD}}] = \mathbb{E}[\tau_{\text{SGD}}] + \mathcal{O}(\sqrt{\eta})$, validating continuous SDE models as faithful approximations for step-based optimization.

Key Results

  • Continuous and Discrete Exit Times: The paper delivers exact asymptotic formulas for the mean exit time across batch size $B$, learning rate $\eta$, basin radius $r$, and minimum eigenvalue $\lambda$:
  • Continuous SGD: $\mathbb{E}[\tau_{\text{SGD}}] = \exp\left[\frac{2B}{\eta} r^2 \lambda^{1/2}\right]$
  • Discrete SGD: $\mathbb{E}[\nu_{\text{SGD}}] = \exp\left[\frac{2B}{\eta} r^2 \lambda^{1/2}\right] + \mathcal{O}(\sqrt{\eta})$
  • Generalized Covariance Bounds: Under a relaxed noise assumption $C(\theta) = H^* G$ (where $c_1 \le \lambda(G) \le c_2$), the exit time remains tightly bounded: $$\exp\left[\frac{2B}{\eta} \frac{r^2}{\sqrt{c_2}} \lambda^{1/2}\right] \le \mathbb{E}[\tau_{\text{SGD}}] \le \exp\left[\frac{2B}{\eta} \frac{r^2}{\sqrt{c_1}} \lambda^{1/2}\right]$$
  • Empirical Validation: Experiments on an MLP trained on the AVILA dataset confirm that empirical exit times scale exponentially with sharpness $\alpha$, radius $r$, and the inverse noise magnitude $\sqrt{B/\eta}$.

Limitations and Future Work

  • Locally Quadratic Loss: The analysis relies on a locally quadratic assumption around the minimum ($L(\theta) \approx \frac{1}{2}(\theta - \theta^*)^\top H^* (\theta - \theta^*)$), which may not capture highly non-linear or non-smooth saddle regions.
  • Gaussian Noise Assumption: The central limit theorem justifies Gaussian gradient noise for large batches, but recent empirical works suggest that small-batch SGD often exhibits heavy-tailed (Lévy-type) noise.
  • Asymptotic Regime: The theoretical guarantees strictly apply when $\eta / B$ is sufficiently small. Extending results to aggressive, large learning-rate regimes remains open.

Summary updated

Abstract

We develop a quantitative theory on the escape problem of stochastic gradient descent (SGD) and investigate the effect of the sharpness of loss surfaces on escape. Deep learning has achieved tremendous success in various domains, however, it has opened up theoretical problems. For instance, it is still an ongoing question as to why an SGD can find solutions that generalize well over non-convex loss surfaces. An approach to explain this phenomenon is the escape problem, which investigates how efficiently the SGD escapes from local minima. In this paper, we develop a novel theoretical framework for the escape problem using ``quasi-potential," the notion defined in a fundamental theory of stochastic dynamical systems. We show that quasi-potential theory can handle the geometric property of loss surfaces and a covariance structure of gradient noise in a unified manner through an eigenvalue argument, while previous research studied them separately. Our theoretical results imply that sharpness contributes to slowing down escape, but the SGD’s noise structure cancels the effect, which ends up exponentially accelerating its escape. We also conduct experiments to empirically validate our theory using neural networks trained with real data.
BibTeX
@inproceedings{ibayashi2022quasi,
  author = {Hikaru Ibayashi and Masaaki Imaizumi},
  title = {{Quasi-potential theory for escape problem: Quantitative sharpness effect on SGD's escape from local minima}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=vLz0e9S-iF3},
}

Loading related content...

Figure