A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks

By Umut Simsekli, Levent Sagun, Mert Gurbuzbalaban. International Conference on Machine Learning, 2019

354 citations recorded by the source corpus.

The gradient noise (GN) in the stochastic gradient descent (SGD) algorithm is often considered to be Gaussian in the large data regime by assuming that the classical central limit theorem (CLT) kicks in. This assumption is often made for mathematical convenience, since it enables SGD to be analyzed as a stochastic differential equation (SDE) driven by a Brownian motion. We argue that the Gaussianity assumption might fail to hold in deep learning settings and hence render the Brownian motion-based analyses inappropriate. Inspired by non-Gaussian natural phenomena, we consider the GN in a more general context and invoke the generalized CLT (GCLT), which suggests that the GN converges to a heavy-tailed $\alpha$-stable random variable. Accordingly, we propose to analyze SGD as an SDE driven by a Levy motion. Such SDEs can incur `jumps', which force the SDE transition from narrow minima to wider minima, as proven by existing metastability theory. To validate the $\alpha$-stable assumption, we conduct extensive experiments on common deep learning architectures and show that in all settings, the GN is highly non-Gaussian and admits heavy-tails. We further investigate the tail behavior in varying network architectures and sizes, loss functions, and datasets. Our results open up a different perspective and shed more light on the belief that SGD prefers wide minima.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/5ed4952b4581beb3732da862dfb6d4747a5bffd8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

On the Generalization Benefit of Noise in Stochastic Gradient Descent (2020, neutral): “The linear scaling rule may not hold if the noise is long tailed or one of the other assumptions above is not satisfied (Shallue et al., 2018; Simsekli et al., 2019).”
On Learning Rates and Schrödinger Operators (2020, background): “To widen the scope of this framework, it is important to extend our results to the setting where the gradient noise is heavy-tailed [SSG19].”
AN EMPIRICAL STUDY (2022, positive): “4 We then test the distributions against 1) multivariate Gaussian, 2) univariate Laplace (on weight marginals), and 3) for cases which could be multivariate Gaussian, we estimate the heaviness of the tails of the distribution (α) as per [33] (via [45]).”
Towards Theoretically Understanding Why SGD Generalizes Better Than ADAM in Deep Learning (2020, methodology): “This work extends [23, 28] from SGD on the over-simplified one-dimensional problems to much more complicated adaptive algorithms on high-dimensional problems.”
Disentangling feature and lazy learning in deep neural networks: an empirical study (2019, background): “Further study of the structure of r can be found at [Simsekli et al., 2019].”
Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances (2019, background): “[SSG19] Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban.”
Why ADAM Beats SGD for Attention Models (2019, methodology): “Our work differs in two important ways: ﬁrst , we treat the noise as a high dimensional vector, while (Simsekli et al., 2019) treat deviations in each coordinate as scaler noises to estimate tail index.”
On the Intrinsic Privacy of Stochastic Gradient Descent (2019, background): “The properties of SGD have since become an object of study [6], [39], [45], with particular focus on the generalisation performance of the solutions it ﬁnds [14], [22], [25].”
Why are Adaptive Methods Good for Attention Models? (2020, methodology): “To our knowledge, [19, 25, 26] start the topic and observe heavy tailed noise in network training.”
A Diffusion Theory for Deep Learning Dynamics: Stochastic Gradient Descent Escapes From Sharp Minima Exponentially Fast (2020, background): “We tend to believe Simsekli et al. (2019) provides a better empirical analysis on stochastic gradient noise under the isotropic assumption.”