Logarithmic landscape and power-law escape rate of SGD

Takashi Mori, Ziyin Liu, Kangqiao Liu, Masahito Ueda

Abstract

Stochastic gradient descent (SGD) undergoes complicated multiplicative noise for the mean-square loss. We use this property of SGD noise to derive a stochastic differential equation (SDE) with simpler additive noise by performing a random time change. Using this formalism, we show that the log loss barrier $\Delta\log L=\log[L(\theta^s)/L(\theta^*)]$ between a local minimum $\theta^*$ and a saddle $\theta^s$ determines the escape rate of SGD from the local minimum, contrary to the previous results borrowing from physics that the linear loss barrier $\Delta L=L(\theta^s)-L(\theta^*)$ decides the escape rate. Our escape-rate formula strongly depends on the typical magnitude $h^*$ and the number $n$ of the outlier eigenvalues of the Hessian. This result explains an empirical fact that SGD prefers flat minima with low effective dimensions, giving an insight into implicit biases of SGD.
BibTeX
@inproceedings{mori2022logarithmic,
  author = {Takashi Mori and Ziyin Liu and Kangqiao Liu and Masahito Ueda},
  title = {{Logarithmic landscape and power-law escape rate of SGD}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=rqolQhuq6Hs},
}

Loading related content...

Figure