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

Hikaru Ibayashi, Masaaki Imaizumi

Abstract

Deep learning models often generalize well despite the presence of numerous local minima. This paper investigates the mechanism by which Stochastic Gradient Descent (SGD) avoids "sharp" minima in favor of "flat" ones. By leveraging Large Deviation Theory (LDT), we provide a theoretical framework that quantifies escape efficiency in the non-stationary regime. We demonstrate that SGD escapes sharp minima exponentially faster than flat ones, driven by the anisotropic nature of gradient noise.

Introduction

A fundamental question in deep learning is why SGD consistently finds solutions that generalize well. The loss landscapes of deep neural networks are complex and contain many local minima. Conventional wisdom suggests that "flat" minima generalize better than "sharp" ones. However, previous theoretical explanations often assumed SGD reaches a stationary distribution, which is impractical for high-dimensional models. This work addresses the escape problem in the non-stationary regime, providing a mathematical basis for why SGD "loves" flat minima.

Theoretical Framework: Quasi-potential and Steepness

The authors utilize Large Deviation Theory (LDT) to bridge the gap between optimization and the physics of stochastic systems. Central to this is the concept of quasi-potential ($V_0$), which represents the minimum "effort" or cost for the optimizer to exit a local basin.

Loss surface trajectories illustrating steepness and the paths taken by the optimizer.

The difficulty of climbing the loss surface along a specific path is defined as "steepness." By comparing the actual SGD system, characterized by anisotropic noise, to a proximal system with isotropic noise, the authors derive an expression for escape efficiency: $$\text{Escape efficiency} \sim \exp \left[ -\frac{B}{\eta} \Delta L \lambda_{\max}^{-1/2} \right]$$ where $B$ is batch size, $\eta$ is learning rate, $\Delta L$ is the depth of the minimum, and $\lambda_{\max}$ is the sharpness (maximum eigenvalue of the Hessian).

Experimental Validation

The theory was validated using standard deep learning architectures and datasets. The authors tracked sharpness dynamics using a VGG network on CIFAR-10 and measured "mean exit times" from local minima using an MLP on the AVILA dataset.

Sharpness dynamics during training (left) and a conceptual 3D loss landscape showing SGD escaping sharp valleys (right).

In numerical validations, the Pearson correlation coefficients between theoretical predictions and experimental exit times were remarkably high (e.g., -0.992 for learning rate and 0.986 for the depth of the minimum), confirming the strong linear correlation between the log of the mean exit time and $1/\sqrt{\lambda_{\max}}$.

Key Insights

  1. Sharpness-Induced Escape: The exponential dependence on $\lambda_{\max}^{-1/2}$ implies that even a slight increase in sharpness leads to a massive increase in escape efficiency. Consequently, SGD spends negligible time in sharp regions and naturally gravitates toward flat ones.
  2. Anisotropic Noise Advantage: The structured noise in SGD, rather than being mere interference, actively reduces the quasi-potential barrier, effectively lowering the "walls" of the local minimum and accelerating escape.
  3. Hyperparameter Influence: The derived formula explains why high learning rates and small batch sizes favor generalization—they effectively increase noise magnitude, making it easier for the optimizer to "jump" out of sharp traps.

Conclusion

This paper provides a rigorous mathematical bridge between optimization dynamics and generalization. By proving that the selection for flat minima occurs throughout the non-stationary training process, it offers a deeper understanding of SGD's success in deep learning. Future work may extend this to non-Gaussian, heavy-tailed noise distributions and more complex, non-quadratic loss landscapes.

Summary updated

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},
}
Figure