Non-Gaussianity of Stochastic Gradient Noise

Introduction

Stochastic Gradient Descent (SGD) algorithm robbins1951stochastic and its variants are workhorses of modern deep learning, e.g. Bottou_Nocedal ; goodfellow2016deep . Not only does SGD allow efficient training of Neural Networks (a non-convex optimization problem) achieving small training loss, it also achieves good generalization, often better compared to Gradient Descent (GD). While striking progress has been made in theoretical understanding of highly over-parameterized networks in recent years, for realistic settings we lack satisfactory understanding. In particular, what property of the distribution of the small-batch gradients arising in SGD is responsible for the efficacy of SGD?

Considerable effort has been expended on understanding SGD for Neural Networks. In particular, there have been attempts to relate SGD to a discretization of a continuous time process via Stochastic Differential Equations (SDEs), e.g., mandt2016variational ; raginsky2017non ; zhang2017hitting ; hu2017diffusion ; jastrzkebski2017three ; zhu2018anisotropic . The Stochastic Gradient (SG) can be written as Gradient + Stochastic Gradient Noise (SGN). mandt2016variational ; hu2017diffusion ; jastrzkebski2017three ; zhu2018anisotropic assume that SGN is approximately Gaussian when the batch size $b$ is large enough, assuming the Central Limit Theorem (CLT) conditions, which we discuss in the next section. raginsky2017non ; zhang2017hitting add explicit gaussian noise to stochastic gradients in each iteration. One can analyze these algorithms by approximating them with the continuous time process in the form of Langevin diffusion, and one can show that the Markov process exhibited by the continuous time iterates is ergodic with its unique invariant measure whose log-density is proportional to the negative of the objective function roberts2002langevin . Therefore, SGD can be seen as a first-order Euler-Maruyama discretization of the Langevin dynamics jastrzkebski2017three ; li2017stochastic .

Since the gradient vectors are very high-dimensional, the number of samples required in the application of the CLT, so that a multivariate Gaussian distribution provides a sufficiently accurate approximation, may be very high, raising doubts about the applicability of the CLT for SGN computed using small batch size. For SGD training of neural networks, the assumption of SGD noise being Gaussian-like was contested recently in tail-index . They argue that the SGN instead follows a stable distribution with infinite variance obtained by the application of the Generalized Central Limit Theorem (GCLT). They provided experimental evidence for their claim. Furthermore, they provided arguments based on the properties of the associated continuous time process which can then be viewed as an SDE with the stochastic term being a Levy motion.

Preliminaries

SGD update rule is given by $\mathbf{w}^{(t+1)}\leftarrow\mathbf{w}^{(t)}-\eta\nabla_{\mathbf{w}}f(\mathbf{w}^{(t)},B_{t}),$ where $\mathbf{w}^{(t)}$ denotes the iterate at time $t\geq 0$, $\eta>0$ denotes the learning rate, and $B_{t}\subseteq{\left[n\right]}$ denotes a batch of training examples of size $b\leq n$ picked at time $t$. A random SGN vector at time $t$ is then given by $f(\mathbf{w}^{(t)};B_{t})-f(\mathbf{w}^{(t)};[n])$.

Perhaps not as well-known as the scalar CLT, there is a CLT for vector-valued random variables showing that the appropriately scaled sums of i.i.d. random variables with finite covariance matrix tends to multivariate Gaussian in distribution. A useful fact about multivariate Gaussians is that if for a random vector $\mathbf{X}$, all its one-dimensional marginals are univariate Gaussians then $\mathbf{X}$ must be multivariate Gaussian (see, e.g., Exercise 3.3.4 in vershynin_book ).

Stable distribution.

For a real-valued random variable $X$, let $X_{1}$ and $X_{2}$ denote its i.i.d. copies. $X$ is said to be stable if for any $a,b>0$, random variable $aX_{1}+bX_{2}$ has the same distribution as $cX+d$ for some constants $c>0$ and $d$. Stable distributions are a four parameter family $S(\alpha,\beta,\gamma,\delta)$ of univariate probability distributions. There is no closed form formula known for these distributions in general, instead they are defined using their characteristic function. We do not include that definition here since we will not need it. Instead, we will just note the properties of stable distributions that are relevant for us. See nolan for more information. The special case of $S(\alpha,0,1,0)$ is represented as $\mathcal{S}\alpha\mathcal{S}$ distribution, and can be considered as the symmetric, centered and normalized case of stable distribution. $\alpha\in(0,2]$ is the stability parameter; we omit the discussion of other parameters. This family includes the standard Gaussian distribution ($S(2,0,1,0)$), and standard Cauchy distribution ($S(1,0,1,0)$). Interest in stable distributions comes from the Generalized Central Limit Theorem (see nolan ) which informally states that the distribution of appropriately scaled sums of i.i.d. random variables with infinite variance tends to a stable distribution. This was the basis of the suggestion in tail-index that SGN vectors follow a stable distribution with infinite variance. More specifically, tail-index posited that the coordinates of SGN vectors are i.i.d. stable random variables. In parallel with multivariate Gaussians, there is a notion of multivariate stable distributions (see nolan ) which satisfies the property that one-dimensional marginals are univariate stable. A more general hypothesis for SGN vectors could be that they are multivariate stable.

Method, Experiments and Observations

Gaussianity testing is a well-studied problem in statistics; we use tests due to Shapiro and Anderson . These were found to be the top two tests in a comparison study Razali . Both of the tests assume the null hypothesis that the given set of scalar examples come from a Gaussian distribution. A small $p$-value implies that the null hypothesis is likely to be false. We follow the following steps to perform statistical tests on stochastic gradient noises (SGN).

We train a model using minibatch SGD and consider SGN vectors for $1000$ independent minibatches, which are of the same size as the training batch-size and randomly sampled with replacement, at multiples of $100$ iterations.

We project each SGN vector along $1000$ random unit vectors, and perform Gaussianity tests on the projections along each direction. We plot the average confidence value across the dimensions, as given by Shapiro–Wilk test Shapiro , and the fraction of directions accepted by the Anderson Wilk test Anderson and compare with the case when actual Gaussian data is fed to the tests.

We conduct experiments on different models, namely a $3$-layer fully connected network, Alexnet, Resnet18 and VGG16 model, with and without batch-normalization (BN), and different data-sets, namely CIFAR10 and MNIST CIFAR ; MNIST ; Krizhevsky ; He ; Simonyan . All the layers were initialized with Xavier initialization glorot2010understanding . The models were trained with constant learning rate mini-batch SGD, where mini-batch-size was varied from $32$, $256$ and $4096$, on cross entropy loss. The learning rates were varied in $10^{\left\{-1,-2,-3\right\}}$.

2 Observations and Conclusion

We first perform sanity checks to see how well the hypothesis tests do on generated $\mathcal{S}\alpha\mathcal{S}$ samples. It can be seen in 1(a) that for $0.2\lesssim\alpha\lesssim 1.8$ the tests very confidently and correctly declare that the distribution is not Gaussian. As $\alpha\to 2$, we expect the distribution to become closer to Gaussian, and for very small $\alpha$ the tails become very heavy. Thus the behavior of the statistical tests on $\mathcal{S}\alpha\mathcal{S}$ distribution is as expected.

We see that SGN looks Gaussian to statistical tests in Fig 2(a) for Resnet18 throughout the training for batch-size $4096$. In contrast, in Fig. 2(c) the behavior is not Gaussian anywhere for batch-size $32$. For intermediate batch-sizes such as $256$, behavior was Gaussian at the beginning of the training, and later becomes non-Gaussian. We observe this behavior consistently across different architectures, data-sets, and larger batch-sizes. This is in contrast with the results in tail-index , which suggests stable distribution right from the start for batch-size $500$. When the behavior is Gaussian in $1000$ random directions, by the characterization of multivariate Gaussian mentioned above, this suggests—though does not definitively prove—that SGN vectors are multivariate Gaussians early on in the training. For batch-size $32$ is it possible that the SGN distribution here is stable? This is unlikely because by GCLT we would expect this behavior at higher batch-sizes, but we observe Gaussian behavior.

We briefly explain possible reasons why our results do not agree with those in tail-index . They use the estimator of Mohammadi to estimate $\alpha$. The application of this estimator in tail-index suffers from 2 errors: (1) In Mohammadi , the estimator is shown to give a good estimate of $\alpha$ under the assumption that the random variable is indeed $\alpha$-stable; it makes no claims about the estimate when this assumption is not satisfied. tail-index seems to tacitly assume stability. (2) The estimator assumes that the coordinates of SGN vector are i.i.d. This assumption is invalid in the typical over-parameterized setting.

References

Appendix A Appendix

Here we present the various plots for the remaining data-sets and models.