First exit time analysis of stochastic gradient descent under heavy-tailed gradient noise

Thanh Huy Nguyen; Umut Şimşekli; Mert Gürbüzbalaban; Gaël Richard

Conference paper, 2019

First exit time analysis of stochastic gradient descent under heavy-tailed gradient noise

Thanh Huy Nguyen, Umut Şimşekli, Mert Gürbüzbalaban, Gaël Richard

Advances in Neural Information Processing Systems (NeurIPS), 2019.

Publisher page arXiv:1906.09069

In brief

Models SGD under heavy-tailed gradient noise as a stochastic differential equation driven by an α-stable Lévy process and analyzes how long it takes to leave a basin of the loss. The exit time depends polynomially on the width of the basin rather than exponentially on its depth, so heavy-tailed SGD leaves narrow minima quickly and settles in wide ones; the analysis also controls the gap between the SDE and the discrete SGD iteration.

Go further

The playground Heavy tails and basin exits lets you try the ideas of this paper in the browser.

The research note Why heavy-tailed SGD leaves narrow basins explains the paper informally.

Topics

Heavy tails in SGD

Cite

@inproceedings{nguyen2019exittime,
  title   = {First exit time analysis of stochastic gradient descent under heavy-tailed gradient noise},
  author  = {Thanh Huy Nguyen and Umut Şimşekli and Mert Gürbüzbalaban and Gaël Richard},
  year    = {2019},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  url     = {https://proceedings.neurips.cc/paper/2019/hash/a97da629b098b75c294dffdc3e463904-Abstract.html},
  note    = {arXiv:1906.09069},
}