On the Overlooked Structure of Stochastic Gradients
Authors: Zeke Xie
Qian-Yuan Tang
Mingming Sun
Ping Li
Venue: NeurIPS 2023 poster (2023)
Keywords: Gradient Noise
SGD
Deep Learning
Heavy Tails
TL;DR: We revisit the heavy-tail phenomenon and report the overlooked power-law covariance structure of stochastic gradients.

Abstract: Stochastic gradients closely relate to both optimization and generalization of deep neural networks (DNNs). Some works attempted to explain the success of stochastic optimization for deep learning by the arguably heavy-tail properties of gradient noise, while other works presented theoretical and empirical evidence against the heavy-tail hypothesis on gradient noise. Unfortunately, formal statistical tests for analyzing the structure and heavy tails of stochastic gradients in deep learning are still under-explored. In this paper, we mainly make two contributions. First, we conduct formal statistical tests on the distribution of stochastic gradients and gradient noise across both parameters and iterations. Our statistical tests reveal that dimension-wise gradients usually exhibit power-law heavy tails, while iteration-wise gradients and stochastic gradient noise caused by minibatch training usually do not exhibit power-law heavy tails. Second, we further discover that the covariance spectra of stochastic gradients have the power-law structures overlooked by previous studies and present its theoretical implications for training of DNNs. While previous studies believed that the anisotropic structure of stochastic gradients matters to deep learning, they did not expect the gradient covariance can have such an elegant mathematical structure. Our work challenges the existing belief and provides novel insights on the structure of stochastic gradients in deep learning.

On the Overlooked Structure of Stochastic Gradients
Zeke Xie', Qian- Yuan Tang?, Mingming Sun' and Ping Li'
CCognitive Computing Lab, Baidu Research 'Department Physics, Hong Kong Baptist University
Correspondence: xiezeke @ comiuu.com, @ ekbu.edu.hk
Abstract
Stochastic gradients closely relate both optimization and generalization of deep neural networks (DNNs). Some works attempted to explain the success of stochastic optimization for deep learning by the arguably heavy-tail properties of gradient noise, while other works presented theoretical and empirical evidence against the heavy-tail hypothesis on gradient noise. Unfortunately, formal statistical tests for analyzing the structure and heavy tails of stochastic gradients in deep learning are still under-explored. In this paper, we mainly make two contributions. First, conduct formal statistical tests the distribution of stochastic gradients and gradient noise across both parameters and iterations. Our statistical tests reveal that dimension-wer wise gradients usually exhibit power-law heavy tails, while iteration-ve wise gradients and stochastic gradient noise caused by minibatch training usually do not exhibit power-law heavy tails. Second, further discover that the covariance spectra of stochastic gradients have the power-law structures overlooked by previous studies and present its theoretical implications for training of DNNs. While previous studies believed that the anisotropic structure of stochastic gradients matters deep learning, they did not expect the gradient covariance have such an elegant mathematical structure. Our work challenges the existing belief and provides novel insights on the structure of stochastic gradients in deep learning.
Introduction
Stochastic optimization methods, such as Stochastic Gradient Descent (SGD), have been highly successful and even necessary in the training of deep neural networks (LeCun et al. 2015). is widely believed that stochastic gradients as well as stochastic gradient noise (SGN) significantly improve both optimization and generalization of deep neural networks (DNNs) (Hochreiter and Schmidhuber!
1995 1997; Hardt et al.] 2016, Wu et al., 2021 Smith et al., 2020; Wu et al.) 2020; Xie al.
2021a Sekhari et al. 202. Amir et al.) 2021). 1). SGN, defined as the difference between full-batch gradient and stochastic gradient, has attracted much attention in recent years. People studied its
type (Simsckli et al. 2019 Panigrahi et al. 2019 Hodgkinson and Mahoney 2021 Li et al. 2021a), its magnitude (Mandt al. 2017;
al. 2021), its structure (Daneshmand al. 2018 hu et al.
2019, Chmiel et al. 2020) Xie et al. 2021b Wen et al. 2020), and its manipulation (Xie et al. (021c). Among them, the noise type and the noise covariance structure are two core topics.
Topic The arguments on the type and the heavy-tailed property of SGN. Recently, a line of research (Simsekli et al.) 2019 Panigrahi et al. 2019 Gurbuzbalaban et al. 2021 Hodgkinson and Mahoney 2021) argued that SGN has the heavy-tail property due to General ized Central Limit
Theorem (Gnedenko et al. 1954). (Simsekli et al. (2019) presented statistical evidence showing that
SGN looks closer to an a- stable distribution that has power-law heavy tails rather than a Gaussian distribution. (Panigrahi et al. 2019) also presented the Gaussianity tests. However, their statistical tests were actually not applied to the true SGN that caused by minibatch sampling. Because, in this line of research, the abused notation "SGN" is studied as stochastic gradient at some iteration
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

rather than the difference between full-batch gradient and stochastic gradient. Another line of research (Xie et al. 2021b 2022b; Li al.) 2021a) pointed out this issue and suggested that the arguments in Siisseli et al. 2019) rely on a hidden strict assumption that SGN must be isotropic and does not hold for all parameters was studied in Simsekli et al.] (2019). In contrast, SGN could be well approximated as an multi-variant Gaussian distribution in experiments at least when batch size is not too small, such as B Z 128 (Xie et al. 2202 lb. Panigrahi et al. 2019). Another work (Li et al. 202 la) further provided theoretical evidence for supporting the anisotropic Gaussian approximation of SGN. Nevertheless, none of these works conducted statistical tests on the Gaussianity or heavy tails of the true SGN.
and anisotropic Gaussian noise. This is why one tail-index for
Contribution 1. To our knowledge, we are the first to conduct formal statistical tests on the distribution of stochastic gradients/SGN across parameters and iterations. Our statistical tests reveal that dimension-wise gradients (due to anisotropy) exhibit power-law heavy tails, while iteration- wise gradient noise (which is the true SGN due to minibatch sampling) often has Gaussian-like light tails. Our statistical tests and notations help reconcile recent conflicting arguments on Topic
Topic 2. The covariance structure of stochastic gradients/SGN. A number of works (Zhu et al. 2019; Xie et al. 202lb HaoChen et al. 202T Liu et al. 202T; Ziyin al., 2022) demonstrated that the anisotropic structure and
magnitude of SGN can help escape sharp minima efficiently. Moreover, some works theoretically demonstrated (Jastrzkebski
al. 2017: Zhu et al.) 2019) and empirically verified (Xie et al.) 2021b 2022b; Daneshmand et al. (2118) that the covariance of SGN is approximately equívalent to the Hessian near minima. However, this approximation is only applied to minima and along flat directions corresponding to nearly-zero Hessian eigenvalues. The quantitative structure of stochastic gradients itself still largely overlooked by previous studies.
We surprisingly discover that the covariance of stochastic gradients has the power- law spectra in deep learning, which is overlooked by previous studies. While previous studies believed that the anisotropic structure of stochastic gradients matters to deep learning, they did not expect the gradient covariance can have such an elegant power-law structure. The power-law gradient covariance may help understand the success of stochastic optimization for deep learning.
Contribution 2.
Preliminaries
Notations. Suppose neural network fa has n model parameters as t. We denote the training dataset as {(z, y)} ((z), y, ) drawn from the data distribution S and the loss function over one data sample {(T). as 1(0, Uz)) We denote the training loss L(l) 2 Ee= I(0, (2z, 85))-
N
We compute the gradients of the training loss with the batch size B and the learning rate for T iterations. We let (()) represent the stochastic gradient at the f-th iteration. We denote the Gradient History Matrix as G = 1,(g))/(1 gg²).... ..... .g. gg( an n x T matrix where the column vector G. represents the dimension-wii wise gradients ((*) for n model parameters, the row vector Gs,, represents the iteration-
wise gradients 9; for T' iterations, and the element G.,1 gi (c) at the t-th iteration for the parameter 0, We analyze G for a given model without updating the model parameter O. The Gradient History Matrix G plays a key role in reconeiling the conflicting arguments on Topic Because the defined dimension- wise SGN (due to anisotropy) is the abused "SGN" in one line of research (Simsekli et al.
2019 Panigrahi et al.
2019; Gurbuzbalaban et al., 2021 Hodgkinson and Mahoney| [202]]. while iteration -iiee SGN (due to minibatch sampling) is the true SGN as another line of research (Xie
ct al. 20216 2022b Li al. 2021a) suggested. Our notation mitigates the abused "SGN".
We further denote the second moment as Cm = Eggg ] for stochastic gradients and the covariance as C = E[(g- - (g "] for SGN, where g = E[g] is the full-batch gradient. We denote the descending ordered cigenvalues of a matrix, such as the Hessian H/ and the covariance C, as A2......., } and denote the corresponding spectral density function as p()).
Goodness-of-Fit Test. In statistics, various Goodness-of of- Fit Tests have been proposed for measuring the goodness of empirical data fitting to some distribution. In this subsection, we introduce how to conduct the Kolmogonov-Sminoo the goodness of fitting a plwer-law distribution and the Pearson's 's x² Test (Plackett 1983) for measuring the goodness of fitting a Gaussian distribution. We present more details in Appendix B
(KS) Test (Massey Jr. 1951 Goldstein et al. (004) for measuring

---

Table I: The KS and x² statistics and the hypothesis acceptance rates of the gradients over dimensions and iterations, respectively. Model: LeNet. Batch Size: 100. In the second column "random" means randomly initialized models, while "pretrain" " means pretrained models.
Dataset
Training
SG Type
due
d.
Power-Law Rate
p-value
Gaussian Rate
MNIST MNIST
Random
Dimension
0.0355
0.0430
76.6%
4.11 x 10-
0.18%
Random
Iteration
0.191
0.0430
0.0788%
0.321
66.1%
MNIST MNIST
Pretrain
Dimension
0.0401
0.0430
60.6%
5.77 10 0.306
0.24%
Pretrain
lteration
0.179
0.0430
0.052%
62.0%
CIFAR-10 10
Random
Dimension
0.0330
0.0430
1,03 x 10
0.3%
CIFAR-10
Random
Iteration
0.574
0.0430
0%
0.337
66.8%
CIFAR-10 CIFAR-10
Pretrain
Dimension
0.0381
0.0430
09.2%
4.01 10
0%
Pretrain
Iteration
0.654
0.0430
0%
0.275
56.6%
100
100
Dimension herat on
Dimeraton
Powe-Lave Rate
Baration
Acceplance Rate
80
Gaussian tate
Magnitude
Magnitude
10 -1
60-
10-1
40
10-2
20
10-2
109
10
10
10
10a
10
10
10a
900
10a
10'
10a
Rank
Rank
Batch Size
Figure 1: Magnitude of gradients w.r.t. magnitude rank. The dimension-wise gradients (one column vector of G) have power- law heavy tails, while the iteration-wis gradients (one row vector of G) have no power-law heavy tails. Model: (Randomly Initial- ized) LeNet. Dataset: MNIST and CIFAR-10.
Figure 2: The power-law rates and Gaussian rates w.r.t. batch size. Increasing batch size sig- nificantly improves the Gaus- sianity of SGN. Model: LeNet.
When we say set of random variables (the elements or eigenvalues) is approximately power- law/Gaussian in this paper, we mean the tested set of data points can pass KS Tests for pawer-law distributions or x² Test for Gaussian distributions at the Significance Level 0.05. We note that, in all statistical tests of this paper, we set the Significance Level as 0.05.
In KS Test, we state the power-law hypothesis that the tested set of elements is power-law. If the KS distance d&s is larger than the critical distance de, the KS test will reject the power-law hypothesis. In contrast, if the KS distance des is less than the critical distance de, the KS test will support (not reject) the power-law hypothesis. The smaller d,s is, the better the goodness-of of of--ower--lww is.
In x² Test, we state the Gaussian hypothesis that the tested set of elements is Gaussian. If the estimated p-value is larger than 0.05, the x² test will reject the Gaussian hypothesis. If the estimated p-value is less than 0.05, the x² test will support (not reject) the Gaussian hypothesis. The smaller p-value is, the better the goodness-of -aassssintty is.
The Gaussianity test consists of Skewness Test and Kurtosis Test (Cain et al. 2017) (Pleas see Appendix BB for more details. Skewness is a measure of symmetry. A distribution or dataset is symmetric if the distribution on either side of the mean is roughly the mirror image of the other. Kurtosis is a measure of whether the data are heavy-tailed or light-tailed relative to normal distribution. Empirical data with high (respectively, low) kurtosis tend to have heavy (respectively, light) tails. Thus, 2 Test can reflect both Gaussianity and heavy tails.
3 Rethink Heavy Tails in Stochastic Gradients
In this section, we try to reconcile the conflicting arguments on Topic by formal statistical tests.
The plwer-law distribution. Suppose that we have the set of k random variables (Ai, A2...., Aa3 that obeys a power-law distribution. We may write the probability density function of a power-law distribution as
p(A) = --
(1)
3

---

2x
2x
Durionsion Iteation
maneen
mmmnsio theatonn
10-1
Magnitude
Magnitude
10-1
Magnitude
10-1
6x 10
60"10-2
4x 10-2
4x 10
3x 10-
3 10
x 10
10
16
10
10a
2 x 10"2
10
10'
10
10a
10-2
10a
10a
10a
10a
Rank
Rank
(a) Random FCN on MNIST
(b) Random ResNet18 on CIFAR-10 (c) Random ResNet18 on CIFAR-
100
2x10
Dimension Beration
Dimersonn Rerstion
Dimaraan Haration
10-1
10
Magnitude
10-3
Magnitude
Magnitude
6
4
3x10
2x10-
10P
10
10a
107
10
10
10a
10a
2
10a
10
10
10a
(d) Pretrained FCN on MNIST
(e) Pretrained R on CIFAR-(1) (f) Pretrained ResNet18 on CIFAR-
10
100
Figure 3: We plot the magnitude of gradients with respect to the magnitude rank for FCN and ResNet18 on MNIST, CIFAR-10, and CIFAR-100. The dimension-wiss gradients have power-law heavy tails, while the iteration-wise gradients have no power-law heavy tails.
where Z is the normalization factor. The finite-sample power law, also known as Zipf's law, can also be approximately written as
A \
we let s = 8-1 denote the power exponent of Zipf'ss ' law (Visser 2013). well-known property of power laws is that, when the power-law variables and their corresponding rank orders are scattered in log-log scaled plot, straight line may fit the points well (Clauset et al. al.] (009)).
1
Dimension-wise gradients are usually power-law, while iteration gradients are usually Gaussian. In Figure D we plot dimension-wise gradients and iteration-wise gradients of LeNet on MNIST and CIFAR over 5000 iterations with fixing the model parameters. We leave experimental details in Appendix A the extensive statistical test results in Appendix C In Figure [ while some points slightly deviate from the fitted straight line, we may casily observe the straight lines approximately fit the red points (dimension wise gradients). The observations indicate that dimension-win gradients have power-law heavy tails while iteration- gradients have such heavy tails.
gradients) but fail to fit the blue points (iteration-
Table T shows the mean KS distance and the mean p-value over dimensions and iterations well as the power-law rates and the Gaussian rates. We note that the power-law/Gaussicn rate means the percentage of the tested points that are not rejected for the power-law/Gaussian hypothesis via KS/X² tests. Dimension wise gradients and iteration wise gradients show significantly different preferences for the plwer-law rate and the Gaussian rate. For example, LeNet on CIFAR-1O has 62006 model parameters. Dimension- wise gradients of the model are power-law for 81.8% iterations and are Gaussian for only 0.3% iterations. In contrast, iteration-wise gradients of the model are Gaussian for 66.8% dimensions (parameters) and are power-law for no dimension.
The observation and the statistical test results Table both indicate that dimension- wise gradients usually have power-law heavy tails while iteration wise gradients are usually approximately Gaussian (with light tails) for most dimensions. The conclusion holds for both pretrained models and random models on various datasets. Similarly, we also observe power-law limension-wise gradients and non- llw-power-law iteration-wise gradients for FCN and ResNet18 in Figure 3 as well as Table 5 Appendix C
in

---

According to Central Limit Theorem, the Gaussianity of iteration- gradients should depend on the batch size. We empirically studied how the Gaussian rate of iteration-wis gradients depends on the batch size. The results in Figure and 4 (see Appendix) support that the Gaussianity of iteration-wise gradients indeed positively correlates to the batch size, which consistent with the Central Limit Theorem. In the common setting that B 2 30, the Gaussianity of SGN can be statistically more significant than heavy tails for most parameters of DNNs, according to x² Tests.
10
10
Aandom Petraied
10-1
Elgenvalus
Eigenvalos
Eigenvalue
10º
10-1
10-1
10-4
10-1
10-4
10-5
10-2
10a
10a
10a
10a
10a
10a
10a
10a
10
10a
10a
10a
Eigenvalue Rank
Eigenvalue Rank
Eigenvalue Rank
(a) MNIST
(b) CIFAR-10
(c) MNIST
Figure 4: The gradient spectra are highly similar and exhibit power laws for both random models and pretrained models. Model: LeNet and 2-Layer FCN. Dataset: MNIST and CIFAR-10.
Reconciling the confficting arguments on Topic 1. We argue that the power-law tails of dimension- wise gradients and the Gaussianity of iteration-wise gradients may well explain the conflicting arguments on Topic 1. On the one hand, the evidences proposed by the first line of research are mainly for describing the elements of one column vector of G which represent the dimension wise gradient at a given iteration. Thus, the works in the first line of research can only support that the distribution of (dimension-wisee stochastic gradients has power-law heavy tail, where heavy tails are mainly caused by the gradient covariance (See Section 4 instead of minibatch training.
On the other hand, the works in the second line of research pointed out that the type of SGN is actually decided by the distribution of iiteration-wise stochastic gradients due to minibatch sampling, which is usually Gaussian for a common batch size B 2 30. Researchers care more about the true SGN, the difference between full-batch gradients and stochastic gradients, mainly because SGN essentially matters to implicit regularization of SGD and deep learning dynamics (Jastrzkebski et al. 2017 Zhu al. 2019 Xie al. 2021b Li et al., 2021b). While previous works in the second line of research did not conduct statistical tests, our work fills the gap.
In summary, while it seems that the two lines of research have conflicting arguments Topic 1, their evidences are actually not contradicted. We may easily reconcile the conflicts as long as the first line of research clarifies that the heavy-tail property describes dimension- -iise gradients (not SGN), which corresponds to the column vector of G instead of the row vector of G.
We notice that the Gaussian rates (the rates of not rejecting the Gaussian hypothesis) do not approach to a very high level (e.g. 95%) even under relatively large batch sizes (e.g.. B = 1000), while they have nearly zero power-law rates (the rates of not rejecting the power-law hypothesis). While the Gaussian rate is low under small batch sizes, the power-law rate is still nearly zero. This may indicate that SGN of a small number of model parameters or under small batch sizes may have novel properties beyond the Gaussianity and the power-law heavy tails that previous works expected.
4 The Overlooked Power-Law Structure
In this section, we study the covariance/sccond-moooe moment structure of stochastic gradients. Despite the reconciled conflicts Topic 1, another question arises that why dimension-wis stochastic gradients may exhibit power laws in deep learning. We show that the covariance not only explains why power-law gradients arise but also surprisingly challenges conventional knowledge on the relation between the covariance (of SGN) and the Hessian (of the training loss).
The power-law covariance spectrum. We display the covariance spectra for various models on MNIST and CIO Figure[showw the covariance spectra for pretrained models and random models are both power-law despite several slightly deviated top eigenvalues. The KS test results are shown in Table 2 To our knowledge, we are the first to discover that the covariance spectra are usually power-law for deep learning with formal empirical & statistical evidences.
5

---

Table 2: KS statistics of the covariance spectra of LeNet and FCN.
Datasct
Model
Training
dks
de
Power-Law
MNIST
LeNet
Pretrain
0.0206
0.043
Yes
1.302
MNIST
LeNet
Random
0.0220
0.043
Yes
1.428
CIFAR-I0
LeNet
Pretrain
0.0201
0.043
Yes
1.257
CIFAR-10 10
LeNet
Random
0.0214
0.043
Yes
1.300
MNIST
FCN
Pretrain 0.0415
0.043
Yes
0.866
MNIST
FCN
Random
0.0418
0.043
Yes 0.864
The relation between gradient covariances and Hessians. Both SGN and Hessian essentially matter optimization and generalization of deep learning (Li al. [2000] Ghorbani et al. 2019 Zhao et al. 2019; Jacot et al. 2019: Yao et al. 2018 Dauphin et al. [014]] Byrd et al. 2011) A conventional belief is that the covariance is approximately proportional to the Hessian near minima, namely
C(0) x (0) (Jastrzkebski et al. 2017 Zhu et al. 2019 Xie et al. 2021b 2022b Daneshmand
al. 2018 Liu et al. 2021). Near a critical point, we have
((0) ~ B
N E
Vi(0, (2,,,,))))))))) v;)) (x),);5)
FIM(0) ~ [()),
B
B
where (IM is the observed Fisher Information matrix, referring to Chapter of Pawitan (001)) and Zhu et al. 2019). The first approximation holds when the expected gradient is small near minima, and the second approximation hold because FIM is approximately equal to the Hessian near minima.
Some works (Xie et al. 202 20226) empirically verified Eq. (3) and further argued that Eq. (3) approximately holds even for random models (which are far from minima) in terms of the flat directions corresponding to small eigenvalues of the Hessian. Note that the most eigenvalues of the Hessian are nearly zero. The gradients along these flat directions are nearly zero as the approximation in Eq. is particularly mild along these directions.
The common PCA method, well the related low-rank matrix approximation, actually prefers to remove or ignore the components corresponding to small cigenvalues. Because the top eigenvalues and their corresponding eigenvectors can reflect the main properties of a matrix. Unfortunately, previous works (Xie et al., 2021b 2022b only empirically studied the small eigenvalues of the covariance and the Hessian and missed the most important top eigenvalues. The missing evidence for verifying the top eigenvalues of the covariance and the Hessian can be a serious flaw for the
well-known approximation Eq. (3). number of works (Sagun et al. 2016 2017 Wu et al. 2017 Pennington and Bahri 2017 |enningtonn and Worah 2018 Papyan 2018 2019; Jacot al. 2019 Fort and Scherlis 2019 Singh et al. 2021] Liao and Mahoney 2021 1 Xie et 2022a) tried to analyze the Hessian structure of deep loss landscape. However, they did not formally touch the structure of stochastic gradients. In this paper, we particularly compute the top thousands of eigenvalues of the Hessian and compare them to the corresponding top cigenvalues of the covariance.
In Figure 5 we discover that, surprisingly, the top eigenvalues of the covariance can significantly deviate from the corresponding eigenvalues of the Hessian sometimes by more than one order of magnitude near or far from minima. This challenges the conventional belief on the proportional relation between the covariance and the Hessian near minima.
We also note that the covariance and the second- moment matrix have highly similar spectra in the log-scale plots. For simplicity of expressions, when we say the spectra of gradient noise/gradients in the following analysis, we mean the spectra of the covariance/the second moment, respectively.
For pretrained models, especially pretrained FCN, while the magnitudes of the Hessian and the corresponding covariance are not even close, the straight lines fit the Hessian spectra and the covariance spectra well. Moreover, the fitted straight lines have similar slopes. Our results also support very recent finding (Xie et al. (022a) that the Hessians have lawer-law spectra for well-trained DNNs but significantly deviate from power laws for random DNNs.
For random models, while the Hessian spectra are not power-law, the covariance spectra surprisingly still exhibit plwe distributions. This is beyond the existing work expected. It not surprising that the Hessian and the covariance have close relation without pretraining. However, we report

---

1
Eigenvalue
10
Eigenvalue
10-3
10-3
Gradient Gradient Noise
Gradient Gradient Noise
Hesslan
Hesslan
10
-5
10-5
10
10
10a
10
103
10
10
10a
10a
Eigenvalue Rank
Eigenvalue Rank
(a) Pretrained LeNet
(b) Random LeNet
10a
10a
Gradient
Gradient Noise
Gradient Gradient Noise
Eigenvalue
10a
Hessian
10a
Hassian
Eigenvalue
10
100
10
10
10-2
10
-2
100
101
102
103
100
101
10a
Rank
Eigenvalue Rank
(c) Pretrained FCN
(d) Random FCN
Figure 5: The spectra of gradients (Uncentered Covariance), gradient noise (Centered Covariance), and Hessians for random models and pretrained models. Model: LeNet and FCN, Dataset: MNIST.
that the power-law covariance spectrum seems to be universal property, and it is more general than the power-law Hessian spectrum for DNNs.
Robust and low-dimensional learning subspace. May power-law covariance spectra theoretically imply any novel insight? The answer is affirmative. A number of papers (Gur-Ari et al. 2018 Ghorbani et al. 2019; Xie et al. 2021b) reported that deep learning (via SGD) mainly happens in a low-dimensional space spanned by the eigenvectors corresponding large eigenvalues during the whole training process. Note that the low-dimensional learning space implicitly reduces deep models' complexity. These studies indicated that the intrinsic dimension of learning space is much lower than the original model dimensionality, resulting in improved generalization and low complexity of deep models. However, existing work cannot explain why the learning space is low-dimensional and robust during training. In this paper, robust space means that the space's 's dimensions are stable during training. We argue that the power-law structure can mathematically explain why low-dimensional and robust learning space exists.
We try to mathematically answer this question by studying the gradient covariance eigengaps. We define the k-th eigengap as oμ = A Ae+1. According to Eq. (2), we have dg approximately meeting
k
5z = Tr( (k - (k 1) 2 = Av 1
(4)
where Zz - k- 8 the normalization factor. Interestingly, it demonstrates that eigengaps also approximately exhibit power-law distribution. We present the empirical evidences of the power-law eigengaps in Figure a6 3o Appendix We observe that the eigengaps decay faster than the eigenvalue. This is not surprising. For example, under the approximation R 1, we have an approximate power-law decaying
8% TH(C) (I: (1) (c--1)
(5)
with larger power exponent as +
Based on the Davis-Kahan @i) Theorem DDaiis and Kahan 1970). we use the angle of the original eigenvector uy and the perturbed eigenvector uy, namely (ug, Uk), measure the robustness of
7

---

space's dimensions. We apply Theorem I useful variant of Kavis-Kahan Theorem Yu et al. 2015). the gradient covariance deep learning, which states that the eigenspace (spanned by eigenvectors) robustness can be well bounded by the corresponding eigengap.
Theorem (Eigengaps Bound Eigenspace Robustness (Yu et al. 2013)). Suppose the true gradient covariance is C, the perturbed gradient covariance C' = C + eM, the i-th eigenvector of C is
U4 and its corresponding perturbed eigenvector is üg Under the conditions of the Davis-Kahan Theorem, we have
2 lop
sin(uk: ūz} S
min ( Ak, AR+1))
where |M is the operator norm of M.
As we have small number of large eigengaps corresponding the large eigenvalues, the correspond- ing learning space robustness has tight upper bound. For example, given the power-law eigengaps in Eq. (5) the upper bound of eigenvector robustness can be approximately written as
M (lp + 1)
sup (in uz)
(6)
A
when 8 is close to one. Obviously, the bound is relatively tight for top dimensions (small k) but becomes very loose for tailed dimensions (large k). A similar conclusion also holds given Eq. (4)
without 1. This indicates that non-top eigenspace can highly unstable during training, because 5g can decay to nearly zero for large k. To the best of our knowledge, we are the first to demonstrate that the robustness
now-dimensional learning space directly depends on the eigengaps.
Note that the existence of top large eigenvalues does not necessarily indicate their gaps are also statistically large. Previous papers failed to reveal that top eigengaps also dominate tailed eigengaps in deep learning. Fortunately, we numerically demonstrate that, as rank order increases, both eigenvalues and eigengaps decay. Eigengaps even decay faster than eigenvalues due to the larger magnitude of the power exponent. Our analysis partially explains the foundation of learning space robustness in deep learning.
Empirical Analysis and Discussion
In this section, we empirically studied the covariance spectrum for DNNs in extensive experiments. We particularly reveal that when the power-law covariance for DNNs appears or disappears. We leave experimental details in Appendix A
Batch Size. Figure 6 shows that the power-law covariance exists in deep learning for various batch sizes. Moreover, the top cigenvalues are indeed approximately inverse to the batch size as Eq. (3) suggests, while the proportional relation between the Hessian and the covariance is weak.
10
Clean Labels
Label Noise
Eigenvalue
10-2
Eigenvalue
10
Random Labels
Label Noise 80%
10
B=10000
10 3
B-1000
10-6
B-10
10
8
10a
B=1
10a
1
10a
10 -5
109
10
102
10a
Eigenvalue Rank
Eigenvalue Rank
Figure 6: Power-law covariance is approximately inverse to the batch size in deep learning. Model: LeNet. Dataset: MNIST.
Figure 7: Comparison of the gradient spectra MNIST with clean labels, noisy labels, and ran- dom labels. Model: LeNet.
Learning with Noisy Labels and Random Labels. Recently, people usually regarded learning with noisy labels (Han et al. 2020) as important setting for exploring the overfitting and general-
ization of DNNs. Previous papers (Martin and Mahoney 2017 Han et al. 2018) demonstrated that
DNNs may casily overfit noisy labels and even have completely random labels during training, while

---

10
Depth=1 Depth=2
Witth=10
Wi
100
W0
Eigenvalue
10a
Eigenvalue
10-1
10-1
10-2
10-2
10
10
10a
10a
10
10
10a
10a
Eigenvalue Rank
Eigenvalue Rank
Figure 8: Large enough width (e.g., Width2 70) matters to the goodness of power-law covariance, while the depth does not. Left: FCN with various depths. Right: FCN with various widths.
convergence speed is slower compared with learning with clean labels. Is this caused by the structure of stochastic gradients? It seems no. We compared the covariance spectrum under clean labels, 40% noisy labels, 80% noisy labels, and completely random labels in Figure 7 We surprisingly discovered that memorization of noisy labels matters little to the power-law structure of stochastic gradients.
3. Depth and Width. In this paper, we also study how the depth and the width of neural networks affect the power-law covariance. Figure and the KS tests in Table Appendix (C support that certain width (e.g.. Width2 70) often required for supporting the power-law hypothesis, while the depth seems unnecessary. Even one-layer FCN may still exhibit the power-law covariance.
10a
10a
10
Gradient
Gradient Gradient Nolua
10a
Grudiint
10a
Eigenvalue
10
Nisa
Eigenvalue
10a
10-1
10a
10-1
10
10-2
10-1
10-3
10-3
10-2
10-1
10c
10a
102
10
10
10t
10a
10a
109
10t
102
10a
Eigenvalue Rank
Elgenvalue Rank
Eigenvalue Rank
(a) LNN
(b) LNN+BatchNorm
(c) LNN+ReLU
Figure 9: The pawer-law gradients appear LNNs with BatchNorm or ReLU, but disappear fully LNNs. Dataset: MNIST.
Linear Neural Networks (LNNs) and Nonlincarity. What is the simplest model that shows the power-law covariance? We study covariance spectra for fully LNNs, LNNs with BatchNorm, and LNNs with ReLU (FCN w/o BatchNorm) in Figure Obviously, fully LNNs may not learn minima with pawer-law Hessians. Layer-wise nonlinearity seems necessary for the power-law Hessian spectra (Xie et al. 2022a). However, even the simplest two-layer LNN with no nonlinearity still exhibits power-law covariance.
5. The Outliers, BatchNorm, and Data Classes. We also report that there sometimes exist a few top covariance eigenvalues that significantly deviate from power laws or the fitted straight lines. Figure shows that, the outliers are especially significant for LeNet, a Convolution Neural Network, but less Significant for FCN. We also note that LeNet does not apply BatchNorm, while the used FCN applics BatchNorm. What is the real factor that determines whether top outliers are significant or not? Figures 9 and I0 support that it is BatchNorm that makes top outliers less significant rather than the convolution layers. Because even the simplest LNNs, which have no convolution layers and nonlinear activations, still exhibit significant top outliers. This may explain why BatchNorm helps training of DNNs.
Suppose there are classes in the dataset, where 10 for CIFAR- and MNIST. We observe that the number of outliers is usually e 1 in Figures IT and 12 It supports that the gradients of DNNs indeed usually concentrate in a tiny top space as previous work suggested (Gur-Ari et al.) 2018). because the ninth eigenvalue may be larger than the tenth eigenvalue by one order of magnitude. However, this conclusion may not hold similarly well without BatchNorm.

---

10a
FCI
FCN wi fatcnMm
10a
10-1
CITAR-10 CIFAR-10
NINST
10"
Eigenvalue
Elgenvalue
Eigenvale
10.2
10-1
10
10
Ietrahee Randem Loket Wetrained Fch
10a7
10
10-5 10a
10a
104
10a
10a
10a
10
10a
10a
10a
10
10a
Eigenvalue Rank
Eigenvalue Rank
Eigenvalue Rank
Figure 10: BatchNorm can make the outliers less signifi- cant. Model: FCN with/without BatchNorm.
Figure 11: The number of out- liers is usually c-1. The outliers the FCN gradient spectrum is much less significant than that LeNet. Dataset: MNIST.
Figure 12: The outliers in the
power-law spectrum mainly de- pends on the the number data classes rather than the number of model outputs (logits).
10-3
Homantum
10
Dp:1
RCM
kzam
0p-01
10P
Eigenvalus us
Weight Decsy
Eigenvalue
Elgenvalive
10-3
10
10-1
10-5
-0
10a
10a
10a
10a
10
10
10
10a
10a
10-2
10"
10
102
10a
Eigenvalue Rank
Elgenvalue Rank
Eigenvalue Rank
Figure 13: Momentum and Weight Decay does not signifi- cantly affect the power-law co- variance, while Adam does.
Figure 15: The power-law gradi- ents appear on non-image nat- ural datasets. Dataset: Avila. Model: FCN.
Figure 14: The power-law covariance holds with Gradi- ent Clipping. Model: LeNet. Dataset: CIFAR-10.
Is it possible that the number of outliers depends the number of model outputs (logits) rather than the number of data classes? In Figure [2] we climinate the possibility by training LeNet with 100 logits CIFAR-10 10, denoted by CIFAR-10*. The number of outliers will be constant even if we increase the model logits.
6. Optimization Techniques. Previous papers report that Weight Decay, Momentum, and Adam may significantly affect gradient noise (Sutskever al. 2013] Daneshmand et al., 20188] Xie et al., 2023). In Figure 13 we discover that Weight Decay and Momentum do not affect the power-law structure, while Adam obviously breaks the power-law structure due to adaptive gradients. Gradient Clipping is popular method for stabilizing and accelerating the training of language models (Zhang et al. 2019). Figure [4 shows Gradient Clipping does not break the power-law structure.
7. Non-image Data. Natural images have special statistical properties (oorrllba and Oliva 2003). May the power-law covariance be caused by the statistical properties of natural images? In Figure [5] on non-image UCI dataset, Avila, which is simple classification dataset with only ten input features, the power-law gradients of DNNs are more general than natural image statistics.
6 Conclusion
In this paper, we revisit two essentially important topics about stochastic gradients in deep learn- ing. First, we reconciled recent conflicting arguments on the heavy-tail properties of SGN. We demonstrated that dimension-wise gradients usually have power-law heavy tails, while iteration-wise gradients or SGN have relatively high Gaussianity. Second, our knowledge, we are the first to report that the covariance of gradients usually has surprising power-law structure in even simple neural networks. The heavy tails of dimension-we wise gradients could be explained as natural result of the plwer-law covariance. We further analyze the theoretical implications and how various settings affect the power-law gradient structure in deep learning. The main limitations of our work lie lacking (1) theoretically explaining why the power-law covariance generally exists in deep learning and (2) models. We leave the theoretical explanation
scaling the experiments larger Transformer-basse and the results of large Transformer-bar based models as future work.
10

---

Acknowledgement
We thank Ms. Zheng He for reproducing core experimental results. This work supported by the Early Career Scheme (ECS) from the Research Grants Council (RGC) of Hong Kong (No. 22302723).
References
Alstott, J., Bullmore, E., and Plenz, D. (2014), powerlaw: python package for analysis of heavy- tailed distributions. PloS one, 91):e85777.
Amir, I., Koren, T., and Livni, R. (2021). Sgd generalizes better than gd (and regularization doesn't t help). Conference on Learning Theory, pages 63-92. PMLR.
Byrd, R. H., Chin, G. M., Neveitt, W., and Nocedal, J. (2011). On the use of stochastic hessian information in optimization methods for machine learning. SIAM Journal on Optimization, 21(3):977-995.
Cain, M. K., Zhang, Z., and Yuan, K.-H. (2017). Univariate and multivariate skewness and kurtosis for measuring nonnormality: Prevalence, influence and estimation. Behavior research methods, 1916:1776-
Chmiel, B., Brn-Uri, L., Shkolník, M., Hoffer, E., Banner, R., and Soudry, D. (2020). Neural gradients are near-lognormal: improved quantized and sparse training. In International Conference on Learning Representations.
Clauset, A., Shalizi, C. R., and Newman, M. E. (2009). Power-law distributions in empirical data. SIAM review, (14):6611-
Daneshmand, H., Kohler, J., Lucchi, A., and Hofmann, T. (2018). Escaping saddles with stochastic gradients. In International Conference on Machine Learning, pages 1155-1164.
Dauphin, Y. N., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., and Bengio, Y. (2014). Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. Advances in Neural Information Processing Systems, 27:2933-299
Davis, C. and Kahan, W. M. (1970). The rotation of eigenvectors by perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1-46.
De Stefano, C., Maniaci, M., Fontanella, F., and di Freca, A. S. (2018). Reliable writer identification in medieval manuscripts through page layout features: The "avila" bible case. Engineering Applications of Artificial Intelligence, 72:99-110.
Fort, and Scherlis, A. (2019). The goldilocks zone: Towards better understanding of neural network loss landscapes. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 3574-3581.
Ghorbani, B., Krishnan, S., and Xiao, Y. (2019). An investigation into neural net optimization via hessian eigenvalue density. In International Conference on Machine Learning, pages 2232-2241. PMLR.
Gnedenko, B., Kolmogorov, A., Gnedenko, B., and Kolmogorov, A. (1954). Limit distributions for sums of independent. Am. J. Math, 105.
Goldstein, M. I.,, Morris, S. A., and Yen, G. G. (2004). Problems with fitting the power-law distribution. The European Physical Journal B- C-Cndenneed Matter and Complex Systems, (2):2255 258.
Gur-Ari, G., Roberts, D. A., and Dyer, E, (2018). Gradient descent happens in a tiny subspace. arXiv preprint arXiv: 18/2.04754
Gurbuzbalaban, M., Simsekli, U., and Zhu, (2021). The heavy-tail phenomenon in sgd. In International Conference Machine Learning, pages 3964-3975. PMLR.

---

Han, B., Yao, Q.. Liu, T., Niu, G., Tsang, I. W., Kwok, J. T., and Sugiyama, M. (2020). A survey of label-noise representation learning: Past, present and future. arXiv preprint arXiv:2011.0444
Han, B., Yao, Q.. Yu, X., Niu, G., Xu, M., Hu, W., Tsang, I., and Sugiyama, M. (2018). Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Advances in neural information processing systems, pages 8527-8537.
HaoChen, J. Z.., Wei, C., Lee, J., and Ma, (2021). Shape matters: Understanding the implicit bias of the noise covariance. In Conference on Learning Theory, pages 2315-2357, PMLR.
Hardt, M., Recht, B., and Singer, Y. (2016). Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1225-1234.
He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778.
Hochreiter, S. and Schmidhuber, J. (1995). Simplifying neural nets by discovering flat minima. In Advances in neural information processing systems, pages 529-536.
Hochreiter, S. and Schmidhuber, J. (1997). Flat minima. Neural Computation, 9(1):1-42.
Hodgkinson, L. and Mahoney, M. (2021). Multiplicative noise and heavy tails in stochastic optimiza- tion. In International Conference on Machine Learning, pages
PMLR.
Jacot, A., Gabriel, F., and Hongler, C. (2019). The asymptotic spectrum of the hessian of dnn throughout training. In International Conference on Learning Representations.
Jastrzkebski, S., Kenton, Z., Arpit, D., Ballas, N., Fischer, A., Bengio, Y., and Storkey, A. (2017). Three factors influencing minima in sgd. arXiv preprint /rxiv:/711.044:
Kingma, D. P. and Ba, J. (2015). Adam: A method for stochastic optimization. 3rd International Conference on Learning Representations, ICLR 2015.
Krizhevsky, A. and Hinton, G. (2009). Learning multiple layers of features from tiny images.
LeCun, Y. (1998). The mnist database of handwritten digits. http://yann. lecun. comfexdb/mnist/.
LeCun, Y., Bengio, Y., and Hinton, G. (2015). Deep learning. nature, 521(7553):436.
LeCun, Y., Bottou, L.,, Bengio, Y., and Haffner, P. (1998). Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11 (6(11))2278-2324,
Li, X., Gu, Q.. Zhou, Y., Chen, T., and Banerjee, A. (2020). Hessian based analysis of sgd for deep nets: Dynamics and generalization. In Proceedings of the 2020 SIAM International Conference on Data Mining, pages 190-198. SIAM.
Li, Z., Malladi, S., and Arora, (2021a). On the validity of modeling SGD with stochastic differential equations (SDEs). In Thirty-Fifth Conference on Neural Information Processing Systems.
Li, Z., Malladi, S., and Arora, S. (2021b). On the validity of modeling sgd with stochastic differential equations (sdes). arXiv preprint 2rXiv:2102.122400
Liao, Z. and Mahoney, M. W. (2021). Hessian eigenspectra of more realistic nonlinear models. Advances in Neural Information Processing Systems, 34.
Liu, K., Ziyin, L., and Ueda, M. (2021). Noise and fluctuation of finite learning rate stochastic gradient descent. In International Conference on Machine Learning, pages 7045-7056. PMLR.
Ma, Y. Yu, D., Wu, T. and Wang, (2019). Paddlepaddle: An open-source deep learning platform from industrial practice. Frontiers of Data and Domputing, 101):
Mandt, S., Hoffman, M. D., and Blei, D. M. (2017). Stochastic gradient descent as approximate bayesian inference. The Journal of Machine Learning Research, 18(1):487344907.
Martin, C. H. and Mahoney, M. W. (2017). Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behavior. arXiv preprint arXiv:
12

---

Massey Jr, F. J. (1951). The kolmogorov-smirnoy test for goodness of fit. Journal of the American statistical Association, 46(253):68-75
Myung, J. (2003). Tutorial on maximum likelihood estimation. Journal mathematical Psychology. 47(1):90-100.
Panigrahi, A., Somani, R., Goyal, N., and Netrapalli, P. (2019). Non-gaussianity of stochastic gradient noise. arXiv preprint arXiv:1910.0663 1910.0962..
Papyan, V. (2018). The full spectrum of deepnet hessians at scale: Dynamics with sgd training and sample size. arXiv preprint arXiv: /81 1.07062.
Papyan, V. (2019). Measurements of three-level hierarchical structure in the outliers in the spectrum of deepnet hessians. In International Conference on Machine Learning, pages 5012-5021. PMLR.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. (2019). Pytorch: An imperative style, high- tegh-performnce deep learning library. In Advances in neural information processing systems, pages 8026-8037.
Pawitan, Y. (2001). In all likelihood: statistical modelling and inference using likelihood. Oxford University Press.
Pennington, J. and Bahri, Y. (2017). Geometry of neural network loss surfaces via random matrix theory. In International Conference on Machine Learning, pages 2798-2806. PMLR.
Pennington, J. and Worah, P. (2018). The spectrum of the fisher information matrix of single- hidden-layer neural network. In NeurlPS, pages 5415-5424.
Plackett, R. L. (1983). Karl pearson and the chi-squared test. International statistical review/revue internationale de statistique, pages 59-72.
Reuveni, S., Granek, R., and Klafter, J. (2008). Proteins: coexistence of stability and flexibility. Physical review letters, 100(20):208101.
Sagun, L., Bottou, L., and LeCun, Y. (2016). Eigenvalues of the hessian in deep learning: Singularity and beyond. arXiv preprint arXiv:1611.07476.
Sagun, L., Evci, U., Guney, V. U., Dauphin, Y., and Bottou, L. (2017). Empirical analysis of the hessian of over-parametrized neural networks. arXiv preprint arXiv:1706.0444
Sekhari, A., Sridharan, K., and Kale, S. (2021). Sgd: The role of implicit regularization, batch-size and multiple-epochs. Advances in Neural Information Processing Systems, 34.
Simsekli, U., Sagun, L., and Gurbuzbalaban, M. (2019). A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, pages 5827- 5837.
Singh, S. P., Bachmann, G., and Hofmann, T. (2021). Analytic insights into structure and rank of neural network hessian maps. Advances Neural Information Processing Systems, 34:23914- 23927.
Smith, S. L., Dherin, B., Barrett, D., and De, S. (2020). On the origin of implicit regularization in stochastic gradient descent. International Conference on Learning Representations.
Stringer, C., Pachitariu, M., Steinmetz, N., Carandini, M., and Harris, K. D. (2019). High-dimensional geometry of population responses in visual cortex. Nature, (7767765)33113365
Sutskever, I., Martens, J., Dahl, G., and Hinton, G. (2013). On the importance of initialization and momentum in deep learning. In International conference on machine learning.
Tang, Q.-Y. and Kaneko, K. (2020). Long-range correlation in protein dynamics: Confirmation by structural data and normal mode analysis. PLoS computational biology, 16(2)xe10076))
Torralba, and Oliva, A. (2003). Statistics of natural image categories. Network: computation in neural systems, 14(3):391.
13

---

Virtanen, P., Gommers. R., Oliphant, T. E.,, Haberland, M., Reddy, T., Couraapeau, D., Burovski, E.. Peterson, P.. Weekesser. W., Bright, J., et al. (2020). Scipy 1.0: fundamental algorithms for scientific computing in python. Nature methods, 17(3):261-272.
Visser, M. (2013). Zipf"s law, power laws and maximum entropy. New Journal of Physics, 15(4):043021.
Wen, Y., Luk, K., Gazeau, M., Zhang, G., Chan, H., and Ba, J. (2020). An empirical study of stochastic gradient descent with structured covariance noise. In Chiappa, S. and Calandra, R., editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 3621-3631. PMLR.
Wu, J., Hu, W., Xiong, H., Huan, J., Braverman, V., and Zhu, Z. (2020). On the noisy gradient descent that generalizes as sgd. In International Conference on Machine Learning, pages 10367-10376. PMLR.
J., Zou, D., Braverman, V., and Gu, Q. (2021), Direction matters: On the implicit regularization effect of stochastic gradient descent with moderate learning rate. International Conference on Learning Representations.
Wu, L., Zhu, Z., et al. (2017). Towards understanding generalization of deep learning: Perspective of loss landscapes. arXiv preprint arXiv: 10239.
Xie, Z., He, F., Fu, S., Sato, I., Tao, D., and Sugiyama, M. (2021a). Artificial neural variability for deep learning: On overfitting, noise memorization, and catastrophic forgetting. Neural Computation, 33(8).
Xie, Z.,, Sato, I., and Sugiyama, M. (2021b). A diffusion theory for deep learning dynamics: Stochastic gradient descent exponentially favors flat minima. In International Conference on Learning Representations.
Xie, Z., Tang. Q.-Y., Cai, Y., Sun, M., and Li, P. (2022a). On the power-law spectrum in deep learning: A bridge to protein science. arXiv preprini arXiv:2201. 13011.
Xie, 7., Wang, X., Zhang, Sato, I., and Sugiyama, M. (2022b). Adaptive inertia: Disentangling the effects of adaptive learning rate and momentum. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 24430-24459.
Xie, Z., Xu, Z., Zhang, J., Sato, I., and Sugiyama, M. (2023). On the overlooked pitfalls of weight decay and how to mitigate them: A gradient-norm perspective. In Thirty-seventh Conference on Neural Information Processing Systems.
Xie, Z., Yuan, L., Zhu, Z., and Sugiyama, M. (2021c). Positive-negatiie momentum: Manipulating stochastic gradient noise to improve generalization. In International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 11448-11458 PMLR.
Yao, Z., Gholami, A., Lei, Q., Keutzer, K., and Mahoney, M. W. (2018). Hessian-based analysis of large batch training and robustness to adversaries. In Advances Neural Information Processing Systems, pages 4949-4959.
Yu, Y., Wang. T., and Samworth, R. J. (2015). useful variant of the davis-kahan theorem for statisticians. Biometrika, 102(2)315-323,
Zhang, J., He, T., Sra, S., and Jadbabaie, A. (2019). Why gradient clipping accelerates training: theoretical justification for adaptivity. In International Conference on Learning Representations.
Zhao, P., Chen, P.-Y,, Das, P., Ramamurthy, K. N., and Lin, X. (2019). Bridging mode connec- tivity in loss landscapes and adversarial robustness. In International Conference on Learning Representations.
Zhu, Z., Wu, J., Yu, B., Wu, L., and Ma, J. (2019). The anisotropic noise in stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects. In ICML, pages 7654-7663.
Ziyin, L.,, Liu, K., Mori, T., and Ueda, M. (2022). Strength of minibatch noise in SGD, In International Conference on Learning Representations.
14

---

A Experimental Settings
Computational environment. The experiments are conducted computing cluster with NVIDIA V100 GPUs and Intel Xeon @ CPUs. We can produce/reproduce the main experiments using PaddlePaddle (Ma et al. 2019) and PyTorch (Paszke et al. 2019).
Model:
LeNet (LeCun et al. 1998). Fully Connected Networks (FCN), and ResNet18 (He et al.
2016). Dataset: MNIST (LeCun 1998). CIFAR-10/100 (Krizhevsky and Hinton 2009), and
Avila De Stefano et al. 2018). Avila is a non-image dataset.
A.1
Gradient History Matrices
In this paper, we compute the Gradient History Matrices and the covariance for multiple models on multiple datasets. Then, we use the elements in Gradient History Matrices and the eigenvalues the to evaluate the goodness of fitting Gaussian distributions or power-law distributions via x² tests and KS tests.
The Gradient History Matrix is an n x T matrix. For the experiment of LeNet and FCN, we compute the gradients for T = 5000 iterations at a fixed randomly initialized position ((0) or pretrained position 0* Due limit of memory capacity, for the experiment of ResNet18, compute the gradients for T 200 iterations at ((() or 0**
Gradient History Matrix can be used compute the covariance or the second moment of stochastic gradients for neural network. Note that a covariance matrix is an x matrix, which is extremely large for modern neural networks. Thus, we mainly analyze the gradient structures of LeNet and FCN at an affordable computational cost.
A.2 Models and Datasets
Models: LeNet (LeCun et al., 1998), Fully Connected Networks (FCN), and ResNet18 (He et al. 2016). We mainly used two-layer FCN which has 70 neurons for each hidden layer, ReLu activations, and BatchNorm layers, unless we specify otherwise.
Datasets: MNIST (LeCun 1998) and CIFAR-10/100
(Krizhevsky and Hinton 2009), and non-image
Avila (De Stefano al.) 2018).
Optimizers: SGD, SGD with Momentum, and Adam (Kingma and Ba 2015
A.3 Image classification on MNIST
We perform the common per-pixel zero-mean varianaee normalization as data preprocessing for MNIST.
Pretraining Hyperparameter Settings: We train neural networks for epochs on MNIST for obtaining pretrained models. For the learning rate schedule, the learning rate is divided by 10 at the epoch of 40% and 80%. We use 7) = 0.1 for SGD/Momentum and r) = 0.001 for Adam. The batch size is set to 128. The strength of weight decay defaults to À = 0.0005 for pretrained models. We set the momentum hyperparameter 3, 0.9 for SGD Momentum. As for other optimizer hyperparameters, we apply the default settings directly.
Hyperparameter Settings for G: We use 77 0.1 for SGD/Momentum and n 0.001 for Adam. The batch size is set to 1 and no weight decay is used, unless we specify them otherwise.
A.4 Image classification on CIFAR-10 and CIFAR-100
Data Preprocessing For CIFAR-10 and CIFAR-100: We perform the common per-pixel zero-mean unit-variance normalization, horizontal random flip, and 32 x 32 random crops after padding with 4 pixels each side.
Pretraining Hyperparameter Settings: In the experiments on CIFAR-I0 and CIFAR-100: 1/ = for Vanilla SGD; 0.1 for SGD (with Momentum); schedule, the learning rate is divided by 10 the epoch of (80, 160) for CIFAR-10 and {100, 150) for CIFAR- 100, respectively. The batch size is set to 128 for both CIFAR- 10 and CIFAR- 100. The
0.001 for Adam. For the learning rate
15

---

batch size is set to 128 for MNIST, unless we specify it otherwise. The strength of weight decay defaults to 0.0005 as the baseline for all optimizers unless we specify it otherwise. We set the momentum hyperparameter 31 0.9 for SGID and adaptive gradient methods which involve in Momentum. As for other optimizer hyperparameters, we apply the default settings directly.
Hyperparameter Settings for G: We use = 1 for SGD, 0.1 for SGD with Momentum, and " 0.001 for Adam. The batch size is set and no weight decay is used, unless we specify them otherwise.
A.5 Learning with noisy labels
We trained LeNet via SGD (with Momentum) on corrupted MNIST with various (asymmetric) label noise. We followed the setting of Han et al. (2018) for generating noisy labels for MNIST. The symmetric label noise is generated by flipping every label to other labels with uniform flip rates (40%, 80%]. In this paper, we used symmetric label noise.
For obtaining datasets with random labels which have little knowledge behind the pairs of instances and labels, we also randomly shuffle the labels of MNIST to produce Random MNIST.
B offdness-of-Fit Tests
B.1 Kolmogorov-Smirnov Test
In this section, we introduce how to conduct the Salmogoorv--Sminnoe Gfoddeessoo-Fil Test.
We used Maximum Likelihood Estimation (MLE) (Myung) 2003 Clauset et al. 2009) for estimating the parameter 3 of the fitted power-law distributions and the Kolmogorov-Smimme
Test (KS Test)
(Massey Jr 195I, Goldstein al. 2004) for statistically testing the goodness of fitting power-law distributions. The KS test statistic is the KS distance dıs between the hypothesized (fitted) distribution and the empirical data, which measures the goodness of fit. is defined as
dys= sup (A) F())),
where (A) is the hypothesized cumulative distribution function and F(A) is the empirical cumula- tive distribution function based on the sampled data (Goldstein et al., 2004). The estimated power exponent via MLE (Clauset et al. 2009) can be written
K In
8-1+K K
Amin
where K is the number of tested samples and we set Amin = Ag. In this paper, we choose the top K 1000 data points for the power-law hypothesis tests, unless specify it otherwise. We note that the Powerlaw library (Alstott et al. 2014) provides a convenient tool to compute the KS distance,
dis. and estimate the power exponent.
According the practice of Kolmogorov-Sminng Smirnov Test (Massey Jr 1951). we state the null hy- pothesis that the tested spectrum is not power-law. We state the alternative hypothesis, called the power-law hypothesis, that the tested spectrum is pawer-law. dies higher than the critical value d, at the = 0.05 significance level, we would accept the null hypothesis. In contrast, if des is lower than the critical value de at the a = 0.05 significance level, we would reject the null hypothesis and accept the plwer-law hypothesis.
For each KS test in this paper, we select top k 1000 data points from dimension- wise gradients and iteration-wis gradients and top t: = 1000 covariance eigenvalues as the tested sets to measure the goodness of power laws. We choose the largest data points for two reasons. First, focusing on relatively large values is very reasonable and common in various fields' power-law studies (Stringer ct al. 2019 Reuveni et al. 2008 Tang and Kaneko 2020). as real-world distributions typically follow power laws only after/large than some cutoff values (Clauset et al. 2009) for ensuring the convergence of the probability distribution. Second, researchers are usually more interested in significantly large eigenvalues due to the low-rank matrix approximation.
16

---

B.2 x2 Test
In this section, we introduce how we conduct X2 Test to evaluate the Gaussianity.
We directly used the x2 Normal Test implemented by the classical Python- based scientific computing package, Scipy (Virtanen al. 2020), to evaluate the Gaussianity of empirical data. Note that need to normalize the empirical data via whitening (zero-mean and unit-variance) before the tests.
The Gaussianity test statistic, p-value, is returned by the squared sum of the statistics of Skewness Test and Kurtosis Test (Cain et al.) 2017). Skewness a measure of symmetry. A distribution or dataset is symmetric if it looks the same to the left and right of the center. Kurtosis is measure of whether the data are heavy-tailed or light-tailed relative to a normal distribution. Empirical data with high kurtosis tend to have heavy tails. Empirical data with low kurtosis tend to have light tails. Thus, x" Test can reflect both Gaussianity and heavy tails. this paper, we randomly choose K 100 data points for the Gaussian hypothesis tests, unless specify it otherwise.
We may write the p-value return by x2 Test as
25 2k +
where 2ş is the Skewness Test statistic and ²K the Kurtosis Test statistic. There are number of ways to compute 2 and 2x in practice. It is convenient to use the default two-sided setting in Virtanen al. (020). Please refer to Virtanen al. (2020) and the source code of stats skeesss and kuuls.kkrrii losislest for the detailed implementation.
For each x² test in this paper, we randomly select k 100 data points from both dimension-wise gradients and iteration-wise gradients as the tested set to measure the Gaussianity. The returned test statistic, value, is classical indicator of the relative goodness of Gaussianity for two types of gradients.
C Statistical Test Results
We present the statistical test results of the eigengaps of the gradient covariances in Table visualized results in Figure 16
3 and the
10
10
Egenvalue or Eggngga
Elgenaats Diperpap
Egengap
Egemata Egergep
10
10
@genvaluv
10-1
1
10-2
10-3
10
10a
10a
10a
10:
10:
10a
10a
Figure 16: The eigengaps of stochastic gradient covariances also approximately pawer-laws. Dataset: MNIST. Model: FCN. Left figure displays the eigengaps by original rank indices sorted by eigenvalues. Right figure displays the eigengaps by rank indices re-sorted by eigengaps.
Table 3: KS statistics of the covariance eigengaps of LeNet and FCN.
Dataset
Model
Training
dic
de
Power-Law
MNIST
LoNet
Pretrain
0.0205
0.043
Yes 5,111
MNIST
LeNet
Rundom
0.0221
0.043
Yes
2.232
MNIST MNIST
PCN
Pretrain
0.0219
0.043
1.668
FCN
Random
0.0251
0.043
Yes
1.668
We present the statistical test results of dimension wise gradients and iteration-wist gradients of LeNet and ResNet18 on various datasets in Tables and
We conducted the KS Tests for all of our studied covariance spectra. We display the KS test statistics and the estimated power exponents & in the tables. For better visualization, we color accepting the pawer-law hypothesis blue and color accepting the null hypothesis (and the cause) in red. The KS Test statistics of the covariance spectra are shown in Tables 6
10 and
17

---

Table 4: The KS and x2 statistics and the hypothesis acceptance rates of iteration-win gradients with respect to the batch size. Model: LeNet. Dataset: MNIST
Type
Training
Setting
dx.
d.
Power-Law Rate
p-value
Gaussian Rate
Iteration
Random
B 1
0.428
0.0430
0.067%
0.047
12.6%
Iteration
Random
B 3
0.385
0.0430
0.17%
0.089
21.5%
Iteration
Random
10
0.267
0.0430
0.25%
0.173
28.5%
Iteration
Random
30
0.249
0.0430
0.16%
0.240
50.9%
Iteration
Random
100
0.191
0.0430
0.079%
0.321
65.1%
Iteration
Random
0.119
0.0430
0.033%
01.882
74.5%
Iteration
Random
1000
0.120
0.0430
0.041%
0.388
75.5%
Dimension
Random
0.0306
0.0430
90.6%
4.51
10
0%
Dimension
Random
3
0.0358
0.0430
74.5%
9.07
10
0.02%
Dimension
Random
B 10
0.0392
0.0430
65.3%
1.78
10
0%
Dimension
Random
30
0.0379
0.0430
68.9%
2.29
10
0.14%
Dimension
Random
0.0355
0.0430
76.6%
4.11
10
0.18%
Dimension Random
300
0.0269
0.0430
97.5%
1.21
10
0.48%
Dimension
Random 1000
0.0309
0.0430
90.6%
1.43
10
0%
Table 5: The KS and x² statistics and the hypothesis acceptance rates of the gradients over dimensions and iterations, respectively. Model: ResNer18. Batch Size: 100. In the second column "random" means randomly initialized models, while "pretrain" means pretrained models.
Dataset
Training
SG Type
des
de
Power-Law Rate
f-value
Gaussian Rate
CIFAR-I0
Random
Dimension
0.0924
0.0962
54.3%
1.73 x 10 0.495
6.4%
CIFAR-10
Random
Iteration
0.141
0.0962
1.32%
93.4%
CIFAR-10
Pretrain
Dimension
0.0717
0.0962
82.6%
1.1 x 10-2 0.497
3.2%
CIFAR-10
Pretrain
Iteration
0.140
0.0962
1.38%
93.5%
CIFAR-100
Random
Dimension
0.0631
0.0962
92.4%
8.55 x 10 0.496
3%
CIFAR-100
Random
Iteration
0.141
0.0962
1.36%
93.2%
CIFAR-100 100
Pretrain
Dimension 0.0637
0.0962
88.5%
8.11 x 10 33
3.4%
CIFAR-100
Pretrain
Iteration
0.140
0.0962
1.37%
0.496
93.1%
Table 6: The KS statistics of the recond-moment spectra of dimension-wise gradients for LeNet on MNIST.
Dataset
Model
Training
Batch
Sample size
Setting
dus
de
Power-Law
MNIST
LeNet
Pretrain
1000
0.0206
0.0430
Yes
1,302
MNIST
LeNet
Pretrain
10
1000
0.0244
0.0430
Yes
1.313
MNIST
LeNet
Pretrain
100
1000
0.0171
0.0430
Yes
1,390
MNIST
LeNet
Pretrain
1000
1000
0.0173
0.0430
Yes
1,314
MNIST
LeNet
Pretrain
10000
1000
0.0204
0.0430
Yes
1.290
MNIST
LeNet
Pretrain
60000
1000
0.106
0.0430
No
0.206
MNIST
LeNet
Random
1000
0.0220
0.0430
Yes
1.428
MNIST
LeNet
Random
10
1000
0.0223
0.0430
Yes
1.334
MNIST
LeNet
Random
100
1000
0.0228
0.0430
Yes
1.313
MNIST
LeNet
Random
1000
1000
0.0198
0.0430
Yes
1.423
MNIST
LeNet
Random
10000
1000
0.0213
0.0430
Yes
1.284
MNIST
LeNet
Random
60000
1000
0.203
0.0430
No
0,271
18

---

Table 7: The KS statistics of the covariance spectra of dimension wise gradients for LeNet on MNIST.
Dataset
Model
Training
Batch
Sample size
Setting
dua
de
Power-Law
MNIST
LeNet
Randorn
1000
0.0226
0.0430
Yes
1,425
MNIST
LeNet
Random
10
1000
0.0227
0.0430
Yos
1,331
MNIST
LeNet
Random
100
1000
0.0230
0.0430
Yes
1.311
MNIST
LeNet
Random
1000
0.0200
0.0430
Yes
1.423
MNIST
LeNet
Random
10000
1000
0.0287
0.0430
Yos
1.320
MNIST
LeNet
Pretrain
1000
0.0206
0.0430
Yes
1.299
MNIST
LoNet
Pretrain
1000
0.0247
0.0430
Yes
1.310
MNIST
LeNel
Pretrain
100
0.0171
0.0430
1.386
MNIST
LeNet
Pretrain
1000
1000
0.0174
0.0430
Yes
1.312
MNIST
LeNet
Premain
10000
1000
0.0223
0.0430
Yes
1.331
MNIST
LeNel
Pretrain
Label Noise 40%
0.0289
0.0430
1,453
MNIST
LeNet
Pretrain
1000
Label Noise 80%
0.0138
0.0430
Yes
11.442
MNIST
LeNet
Pretrain
1000
Random Label
0.0129
0.0430
Yes
1.374
MNIST MNIST
LeNel
Pretrain
GradClip=1 GradClip=0.1
0.0226
0.0430
1.323
LeNet
Pretrain
1000
0.0261
0.0430
Yes
1.343
Table 8: MNIST.
The KS statistics of the second-moment spectra of dimension-wise gradients for FCN on
Datasct
Model
Training
Batch
Sample
Sctting
dus
de
Power-Law
MNIST 2Layer-FCN
Pretrain
10
1000
0.0415
0.0430
Yes
0.866
MNIST
Random
10
1000
0.0418
0.0430
Yes
0.864
MNIST
2Layer-FCN
Random
10
1000
Noise
0,0427
0.0430
Yes 0.862
MNIST
2Laycr-FCN
Pretrain
1000
Wi
0.0415
0.0430
0.866
MNIST
2Layer-FCN
Pretrain
Width=30
0.0425
0.0430
0.869
MNIST
2Layer-FCN
Pretrain
Width=10
0.0486
0.0430
No
MNIST
2Laycr-FCN
Random
1000
Width=70
0.0418
0.0430
0.864
MNIST
2LNyer-FCN
Random
1000
Width=30
0.0488
0.0430
No
MNIST
21 2layer-FCN
Random
10
1000
1idth=
0.0491
0.0430
No
MNIST
ICaycr-FCN
Random
0.0384
0.0430
1.357
MNIST
ICayer-FCN
Pretrain
0.0384
0.0430
1.355
Table 9: The KS statistics of the second-moment spectra of dimension-wise gradients for LNN on MNIST.
Dataset
Model
Training
Batch
Sample size
Setting
dya
de
Power-Law
MNIST
4Layer-LNN
Pretrain 10
1000
0.0445
0.0430
No
1.629
MNIST
4Laycr-LNN
Pretruin
10
1000
BatchNorm
0.0268
0.0430
Yes
0.955
MNIST
4Layer-LNN
Pretrain
10
1000
ReLU
0.0154
0.0430
Yes
1.074
Table 10: The KS statistics the covariance spectra of dimension-wise gradients for LeNet on CIFAR-10.
Dataset
Model
Training
Batch
Sample size
Setting
du.
d,
Power-Law
CIFAR-10
LeNet
Pretrain
1000
0.0201
0.0430
Yes
1.257
CIFAR-10
LeNet
Random
1000
0.0214
0.0430
Yes
1,300
CIFAR- 10
LeNet
Pretrain
1000
GradClip=0.1
0.0244
0.0430
Yes
1.348
CIFAR-10
LeNet
Random
100
1000
SGD
0.00818
0.0430
Yes
1.305
CIFAR-10 10
LeNet
Random
100
1000
Weight Decay
0.0107
0.0430
Yes
1.300
CIFAR-10
LeNet
Random
100
1000
Momentum
0.00806
0.0430
Yes
1.262
CIFAR-10
LeNet
Random
100
1000
Adam
0.0634
0.0430
No
19

---

Table 11: The KS statistics of the covariance spectra of LeNet on CIFAR-100.
Dataset
Model
Training
Batch
Sample size
Setting
dax
Power-Law
CIFAR-100
LeNet
Pretrain
1000
0.0287
0.0430
Yes
1.276
CIFAR-100
LeNet
Random
1000
0.0307
0.0430
Yes
1.229
CIFAR-100
LeNet
Pretrain
1000
0.0197
0.0430
1.076
20


Reviews:
[{"review_id": "mC5DJcddax", "reviewer": "Reviewer_HTRt", "summary": "This paper makes two contributions. First, it conducts certain formal statistical tests on the distribution of stochastic gradients and gradient noise across both the parameters and iterations. Second, it  further discover that the covariance spectra of stochastic gradients have the power-law structures overlooked by previous studies and present its theoretical implications for training of DNNs.", "questions": "A theoretically explanation as to why the power-law covariance generally exists in deep learning should be provided. Furthermore, when is this statement true and when is it false?\n", "limitations": "The two theoretical results are important and significant. The authors should invesigate how these results can applied in the deep learning architectures. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper conduct the formal  statistical tests to show that dimension-wise gradients usually exhibit power-law heavy tails, while iteration-wise gradients and stochastic gradient noise caused by minibatch training usually do not exhibit power-law heavy tails. It further discover that the covariance spectra of stochastic gradients have the power-law structures and present its theoretical implications for training of DNNs. These results are quite significant for pratical applications. ", "weaknesses": "The experimental results are not so sufficient. The models utilized in the experiments are LeNet (LeCun et al., 1998), Fully Connected Networks (FCN), and ResNet18 (He et al., 2016). However, it is better to conduct the xperiments on other network structures, such as LSTM and Transformer.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate Reviewer HTRt’s kind support and constructive comments.\n\nWe duly respond to your comments as follows.\n\nQ1: The experimental results are not so sufficient. The models utilized in the experiments are LeNet (LeCun et al., 1998), Fully Connected Networks (FCN), and ResNet18 (He et al., 2016). However, it is better to conduct the experiments on other network structures, such as LSTM and Transformer.\n\nA1: Thanks for the suggestion. We will add more experiments in the revision. We also note that the overlooked structure of stochastic gradients is general and interesting as it emerges in even very simple neural networks. \n\nQ2: A theoretical explanation as to why the power-law covariance generally exists in deep learning should be provided. Furthermore, when is this statement true and when is it false?\n\nA2: We frankly admit that we currently have no formal theory for explaining why the power-law stochastic gradient (SG) structure exist. The SG structure is beyond the understanding of existing theories and has been overlooked until our work. We will leave formal theoretical analysis for explaining the SG structure as future work.\n\nHowever, in this work, we have tried hard to develop theoretical implication of the novel SG structure for explaining and understanding deep learning behaviors. For example, we formulate theoretical analysis for explaining and analyzing robust and low-dimensional learning subspace of DNNs via the SG structure and Davis-Kahan Theorem. \n\nQ3: The two theoretical results are important and significant. The authors should investigate how these results can applied in the deep learning architectures.\n\nA3: Thanks again for the constructive suggestion and recognizing the value of our theoretical results. We agree that your suggestion will be a promising exploration direction. For example, the robust and low-dimensional learning subspace may inspire novel low-rank efficient training method, while this is beyond the main scope of this work. We will actively explore related topics in future.\n"}, {"review_id": "uAp5bsc9sS", "reviewer": "Reviewer_jrig", "summary": "This paper studies some statistical properties of stochastic gradients, with a particular focus on their covariance.\nThe main finding is that the stochastic gradients have an approximately Gaussian distribution whose covariance spectrum follows a power law, which is robust to several changes in the setting.\n\nEDIT: I have read the author's rebuttal, which partially addressed my concerns. However, some points still require clarification or a more precise analysis.", "questions": "What is being plotted in Figure 1? On what are the $\\chi^2$-KS tests exactly computed?\n\nWhat are the authors trying to show with the study of the eigengaps?", "limitations": "One limitation of the work is that it is restricted to relatively small-scale experiments, mostly limited to small networks and/or datasets. See weaknesses for a few suggestions for scaling up the experiments.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 4, "strengths": "This paper studies a very important and central problem.\nBesides the finding that the gradient covariance has a power-law structure, it makes several interesting observations, notably the fact that it persists with random labels and that it occurs in a linear network as soon as one adds batch normalization.", "weaknesses": "One main weakness is that I find it hard to understand what exactly is being plotted in Figure 1. The distinction between rows and columns of the gradient history matrix is clear. However, I don't understand how the collection of rows/columns is being mapped to a single scatter plot. The authors should add a precise description of the considered quantity, perhaps in the form of an equation.\n\nThe authors claim that the stochastic gradient noise across iterations is Gaussian. I disagree with this claim, as it seems to me that stochastic gradient noise should be defined for a batch size of 1, as the difference between the gradient computed on a *single* data point and the full-batch gradient. The Gaussianity here seems to only come from averaging with a sufficiently large batch size, as shown in Figure 2. So the Gaussianity is not an inherent statistical property of stochastic gradients, but only an outcome of the central limit theorem. I think this distinction is important and should be clarified in the text. As a side remark, the Gaussianity \"rate\" cannot be larger than 95% as the significance level (rate of false rejections) is 0.05.\n\nThe power-law fits for ResNet are erroneous: they should be corrected or removed (see limitations). One issue is that this figure considers only 200 timesteps. It implies that eigenvalues beyond the top, say, 100, are not well estimated, which makes the presence of a power law difficult to assess. The authors acknowledge the memory costs of storing the large $n \\times n$ covariance matrix. However, they seem to have missed that one can compute the eigenvalues of the covariance from the singular values of the much smaller $n \\times T$ gradient history matrix. The large number of parameters $n$ could also be reduced by considering gradients with respect to a single layer, which can be expected to also show a power law structure. I am not necessarily requesting that this be added in this paper, which already has enough results to be intesting, but the limitation of the ResNet results should be acknowledged by the authors.\n\nFinally, I do not see the point of the study of the eigengaps. The experiments amount to showing that the derivative of a power law is another power law, with an index one lower, which is elementary. I am also not convinced by the \"stability\" analysis. The authors define stable as being roughly invariant during training, but they do not study the evolution of the Hessian as the parameters remain frozen in their experiments. Besides, the fact that the eigenvectors associated with small and/or close eigenvalues are unstable to perturbations is a well-known general fact, which has nothing to do with stochastic gradient descent or power laws.\n\nLet me suggest some relevant references. The work of Papyan [1,2] studies the spectrum of the Hessian and shows the presence of outliers created by the class structure of the cross-entropy loss. These works are relevant to the discussion in paragraph 5. of Section 5. The work of Sagun et al. [3, 4] is an early investigation into the eigenvalues of the Hessian, noting in particular that it has many small eigenvalues at the end of training (the power law was not observed due to the linear scaling of the axes in the scree plots).\n\nTypos:\n- Figure 5: spectrums -> spectra\n- line 226: eliminate \"which\"\n- The caption of Figure 13 wrongly states that Adam preserves the power law\n\nIn general, the quality of the English could be improved.\n\n[1] Papyan, Vardan. \"Measurements of Three-Level Hierarchical Structure in the Outliers in the Spectrum of Deepnet Hessians.\" International Conference on Machine Learning. PMLR, 2019.\n\n[2] Papyan, Vardan. \"Traces of class/cross-class structure pervade deep learning spectra.\" The Journal of Machine Learning Research 21.1 (2020): 10197-10260.\n\n[3] Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of the Hessian in deep learning: Singularity and beyond. arXiv preprint arXiv:1611.07476, 2016.\n\n[4] Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the Hessian of over-parametrized neural networks. arXiv preprint arXiv:1706.04454, 2017.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate Reviewer jrig’s kind support and constructive comments.\n\nWe duly address your concerns as follows.\n\nQ1: One main weakness is that I find it hard to understand what exactly is being plotted in Figure 1. The distinction between rows and columns of the gradient history matrix is clear. However, I don't understand how the collection of rows/columns is being mapped to a single scatter plot. Or what are the $\\chi^{2}$-KS Test exactly computed. \n\nA1: We apologize for the confusion. A scatter point in Figure 1 indicates an element of a dimension-wise or iteration-wise gradient vector. The vertical axis indicates the magnitude of a gradient element, and the horizontal axis indicates the rank order of the gradient element. As visualizing the whole matrix G is not clear and informative, we visualize and statistically analyze only one dimension-wise gradient vector and one iteration-wise gradient vector in Figure 1. Other figures have no such confusion, because we only visualize and statistically analyze the eigenvalues. We will make this point more clear in the revision.\n\nQ2: The authors claim that the stochastic gradient noise across iterations is Gaussian. I disagree with this claim, as it seems to me that stochastic gradient noise should be defined for a batch size of 1, as the difference between the gradient computed on a single data point and the full-batch gradient. The Gaussianity here seems to only come from averaging with a sufficiently large batch size, as shown in Figure 2. So the Gaussianity is not an inherent statistical property of stochastic gradients, but only an outcome of the central limit theorem. I think this distinction is important and should be clarified in the text.\n\nA2: We agree that the Gaussianity of stochastic gradient noise (SGN) mainly come from Central Limit Theorem. However, we also note that, a large body of related works usually discuss SGN with arbitrarily large or small batch sizes, as long as the optimizer is SGD not GD. Thus, it is not false to claim that SGN across iterations can be approximately Gaussian (due to Central Limit Theorem). We mentioned this point in Lines 140-145. We will follow your suggestion and make the distinction more clear.\n\nQ3: The power-law studies of ResNet are limited. One issue is that this figure considers only 200 timesteps. Authors seem to have missed that one can compute the eigenvalues of the covariance from the singular values of the much smaller gradient history matrix. The large number of parameters could also be reduced by considering gradients with respect to a single layer, which can be expected to also show a power law structure. I am not necessarily requesting that this be added in this paper, which already has enough results to be interesting, but the limitation of the ResNet results should be acknowledged by the authors.\n\nA3: We sincerely appreciate the constructive comment. We will acknowledge the limitation of the current ResNet18 experiment in the paper. We agree that it is possible to calculate a more precise eigenspectrum corresponding to a larger gradient history matrix G for ResNet18 with some computational tricks. We will also try to scale our analysis up to larger network architectures in the revision.\n\nQ4: I do not see the point of the study of the eigengaps. I am also not convinced by the \"stability\" analysis. The authors define stable as being roughly invariant during training, but they do not study the evolution of the Hessian as the parameters remain frozen in their experiments. Besides, the fact that the eigenvectors associated with small and/or close eigenvalues are unstable to perturbations is a well-known general fact, which has nothing to do with stochastic gradient descent or power laws.\n\nA4: We respectfully argue that the study of the eigengaps can help us understand robust and low-dimensional learning subspace of DNNs reported in previous studies, because learning subspace directly relates to the gradient structure. Our discussion aims at the gradient structure rather than the Hessian structure. \n\nWe understand that the existence of small eigengaps is common. However, it is not well known until our work that the eigengaps of stochastic gradients exhibit power laws which indicate the existence of certain top eigengaps. Moreover, the top eigengaps ``happen” to correspond to top eigenvalues, where learning dynamics mainly happens. These evidences together can support our analysis of robust and low-dimensional learning space.\n\nWithout the power-law gradient structure, there are other possibilities: (1) large eigengaps do not exist, so no learning subspace is stable; (2) large eigengaps exist but do not correspond to large eigenvalues, so learning dynamics happens in other unstable subspace instead of the much more stable subspace. \n\nQ5: Some relevant references.\n\nA5: Thanks for providing these references on the Hessian structures. The Hessian structure and the gradient structure are indeed closely related. We will discuss the references in the paper.\n\nQ6: Typos.\n\nA6: Thanks again for pointing out the typos. We will correct them.\n\nWe gratefully thank Reviewer jrig again for recognizing the significant contribution of our work to the community and the very helpful suggestions."}, {"review_id": "AGgKHQBB5d", "reviewer": "Reviewer_8wue", "summary": "This paper looks at the structure of stochastic gradient noise (SGN).  They show that the noise for a single parameter, across minibatches/iterations is light-tailed, while looking across parameters, the noise is heavy-tailed.  Further, they show that the spectrum across parameters is heavy-tailed.", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Interesting collection of empirical results.", "weaknesses": "* In many settings, the proposed power-law structure is violated, with N-1 large and similarly-sized eigenvalues, where N is the number of image classes.  There is no theory on this point.\n* In several settings, there are large deviations between the Hessian and FIM.  There is no theory on this point.\n* The theory in \"Robust and low-dimensional learning subspace.\" is problematic.  It starts from the observation of power-law gradients.  However, by far the most important theory, in the context of this paper, would explain the emerge of power-law gradients.\n* The fact that the power-law gradients seem to emerge only at sufficient width strongly suggests that theory is possible.\n\nThis is bizarre.  \n> Is it possible that the number of outliers depends on the number of model outputs (logits) rather than the number of data classes? In Figure 12, we eliminate the possibility by training a LeNet with 100 logits on CIFAR-10, denoted by CIFAR-10⋆. The number of outliers   will be constant even if we increase the model logits.\nI'm not at all sure that it is meaningful to have more logits than classes, and as such, the conclusion is not supportable.\n\nUltimately the AC decision will come down to whether such a collection of empirical results, with no theory describing how or why they might emerge should be published.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate Reviewer 8wue for hard work and recognizing main contributions of our work.\n\nWe notice that Reviewer 8wue agrees on the contribution of our finding and the associated empirical and statistical evidences, while the main concern about lacking of theory is posted. \n\nWe frankly admit that we currently have no formal theory for explaining why the power-law stochastic gradient (SG) structure exist. The SG structure is beyond the understanding of existing theories and has been overlooked until our work. We will leave formal theories for explaining the SG structure as future work.\n\nHowever, in this work, we have tried hard to (1) develop theoretical implication of the novel SG structure for explaining and understanding deep learning behaviors and (2) how various settings of DNNs can empirically affect the SG structure. \n\nFor example, we formulate theoretical analysis for explaining and analyzing robust and low-dimensional learning subspace of DNNs via the SG structure and Davis-Kahan Theorem. We empirically revealed how the SG structure behaves differently under extensive experimental settings. We think our empirical and theoretical contributions are much more than simply reporting existence of the novel SG structure.\n\nMost importantly, we and even all five reviewers consistently believe that the overlooked structure of stochastic gradients is indeed novel and important for our community. \n\nWe also duly address your main concerns as follows.\n\nQ1: In many settings, the proposed power-law structure is violated, with N-1 large and similarly-sized eigenvalues, where N is the number of image classes. There is no theory on this point. \n\nA1: We agree that no improper theory is available yet in our work or related work. Our contribution on this finding (Section 5.5) is that the number of large outliers not only closely depends on the number of data classes. It is the number of data classes rather than the number of the final layer’s logits that decide the number of large outliers. We further show that BatchNorm can make the large outliers less significant. This may also explain why BatchNorm can stabilize training and work with a large learning rate. This finding is also valuable.\n\nQ2: In several settings, there are large deviations between the Hessian and FIM. There is no theory on this point. \n\nA2: We respectfully argue that large deviations between the Hessian and FIM can be explained by falsely assuming that the model is near a critical point. \n\nOur empirical results actually suggest that the approximation of Hessian and FIM is very weak along the \"sharp\" directions corresponding to large eigenvalues, while previous works suggest the approximation is robust along the ``flat” directions corresponding to small eigenvalues. The assumption that the model is near a critical point is only mild for those flat directions. \n\nQ3: The theory in \"Robust and low-dimensional learning subspace.\" is problematic. It starts from the observation of power-law gradients. However, by far the most important theory, in the context of this paper, would explain the emerge of power-law gradients. \n\nA3: It indeed does not explain emergence of the SG structure. We respectfully argue that, in this section, we only aim at explaining and analyzing robust and low-dimensional learning subspace via the SG structure. We think the relations of the SG structure to other behaviors of DNNs are important.\n\nQ4: The fact that the power-law gradients seem to emerge only at sufficient width strongly suggests that theory is possible.\n\nA4: We sincerely thank for the constructive suggestion. We will explore its theoretical mechanism and implication given the observed relations to width and nonlinearity. \n\nQ5: About Figure 12 in Section 5.5. I'm not at all sure that it is meaningful to have more logits than classes, and as such, the conclusion is not supportable.\n\nA5: We respectfully argue that the experiment of Figure 12 is meaningful, because the backpropagated gradients always start from the final layer’ logits. While Figure 11 suggests that $C-1$ large outliers exist in the spectra, where $C$ is the number of data classes, this phenomenon may also depend on the final network layer’s logits. Thus, it is meaning full to have this further ablation study, where the backpropagated gradients also start from all 100 logits but the number of data classes is still 10. \n"}, {"review_id": "2o3LxTkRmM", "reviewer": "Reviewer_tTSf", "summary": "This paper focuses on investigating the stochastic gradient noise (SGN), defined as the difference between the full-batch gradient and the stochastic gradient. The authors conduct formal statistical tests to examine the distribution of SGN across both parameters and iterations. Their analysis reveals that dimension-wise SGN often demonstrates power-law heavy tails, while iteration-wise SGN resulting from mini-batch training generally lacks such heavy tails. Additionally, the authors discover power-law structures in the covariance spectra of stochastic gradients. By means of formal statistical tests and covariance spectra analysis, the authors contribute to a deeper comprehension of the behavior and properties of stochastic gradients within the context of deep neural networks.", "questions": "1. Is the plot made based on multiple runs or just a single run?\n2. Is the plot shown at initialization, in the middle of the training, or at the end of training (close to a local minima)?The authors have discussed the potential limitation of this work.\n\n\n", "limitations": "The authors have discussed the potential limitation of this work.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Distinguishing between two distinct types of SGNs is important, providing a clearer understanding of distribution regarding to SGN.\n\n2. The power-law behavior observed in the covariance spectrum, along with the theoretical implications and insights it offers regarding the low-dimensional learning space of deep neural networks (DNNs), is very interesting.\n\n", "weaknesses": "1. The experiments conducted in this study primarily focus on LeNet (a CNN with approximately 60,000 parameters) and FCN models, especially when analyzing the covariance spectrum due to limited computational source. It is important to note that the observations made on these relatively simple DNN models may not necessarily apply to more complex architectures such as ResNet or Transformer.\n\n2. I also believe that the authors have missed an important line of research that examines the eigenvalue spectrum of the Hessian and the gradient covariance, accompanied by empirical findings. I find that their empirical results are closely connected to the discoveries presented in this paper, particularly regarding the power-law nature of the covariance spectrum.\n\n[1] Sagun, Levent, et al. \"Empirical analysis of the hessian of over-parametrized neural networks.\" arXiv preprint arXiv:1706.04454 (2017).\n[2] Papyan, Vardan. \"The full spectrum of deepnet hessians at scale: Dynamics with sgd training and sample size.\" arXiv preprint arXiv:1811.07062 (2018).\n[3] Papyan, Vardan. \"Measurements of three-level hierarchical structure in the outliers in the spectrum of deepnet hessians.\" arXiv preprint arXiv:1901.08244 (2019).\n[4] Li, Xinyan, et al. \"Hessian based analysis of sgd for deep nets: Dynamics and generalization.\" Proceedings of the 2020 SIAM International Conference on Data Mining.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate Reviewer tTSf for kind support and helpful comments.\n\nWe duly address your concerns as follows.\n\nQ1: The experiments conducted in this study primarily focus on LeNet (a CNN with approximately 60,000 parameters) and FCN models, especially when analyzing the covariance spectrum due to limited computational source. It is important to note that the observations made on these relatively simple DNN models may not necessarily apply to more complex architectures such as ResNet or Transformer.\n\nA1: Thanks for the suggestion. Due to memory and computation capacity, we indeed mainly conducted experiments on CNNs and FCNs, while the gradient structure of ResNet18 is presented in Figure 3. We sincerely acknowledge your suggestion. We will try to scale our experiments to larger models. \n\n\nQ2: I also believe that the authors have missed an important line of research that examines the eigenvalue spectrum of the Hessian and the gradient covariance, accompanied by empirical findings. I find that their empirical results are closely connected to the discoveries presented in this paper, particularly regarding the power-law nature of the covariance spectrum.\n\nA2: Thanks for providing these references (mainly on the Hessian structures). The Hessian structure and the gradient structure are indeed closely related. We will discuss the references in the paper.\n\nQ3: Is the plot made based on multiple runs or just a single run?\n\nA3: We have run the experiments for multiple times and obtain consistent conclusions on the gradient structure. The visualized plots are mainly based a single run. Because, as we visualize the magnitude and the magnitude rank in the plots, averaging over multiple runs may break the meaning of the eigenvalues’ magnitude rank. \n\nQ4: Is the plot shown at initialization, in the middle of the training, or at the end of training (close to a local minima)?\n\nA4: We analyzed randomly initialized models and pretrained models (terminated at the end of training and close to a minimum). The gradient structure holds very similarly. Please see Figures 3-4 and Tables 1-2. Moreover, we believe it will hold similarly to models in the middle training phase, as this middle phase simply interpolates between the two studied training phase.\n"}, {"review_id": "2uhfrMnCmB", "reviewer": "Reviewer_AgKN", "summary": "This paper studies two overlooked structures of stochastic gradients in deep learning. Specifically, the first part of the study conducts formal statistical tests on the distribution of stochastic gradients across parameters and iterations, and empirically showed that dimension-wise gradients exhibit power-law heavy tails, while iteration-wise gradient noise often has Gaussian-like light tails. Then, the second part of the study discovers that the covariance of stochastic gradients has the power law spectra in deep learning, which is overlooked by previous studies. The power-law gradient covariance may help understand the success of stochastic optimization for deep learning.", "questions": "1. It seems that the main observations of this paper also hold for random initialized deep models. While this shows that these structures may be a fundamental and common structure of deep networks, does it imply that these structures may not be induced by the SGD training?\n\n2. How is the gradient matrix G computed for random initialized models and pre-trained models? Do you train these models for some iterations and compute the G?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper conducts comphrehensive deep learning experiments to reveal the structures of stochastic gradients and the corresponding covariance matrix. \n\nThe experiments show that dimension-wise gradients exhibit power-law heavy tails, while iteration-wise gradient noise often has Gaussian-like light tails. This addresses an existing conflict arguments on the distribution of stochastic gradients in the existing literature.\n\nThese new empirical observations may help understand the success of stochastic optimization for deep learning and may inspire new theoretical developments.", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer AgKN for kind support and comments.\n\nWe also duly address your questions as follows.\n\nQ1: It seems that the main observations of this paper also hold for random initialized deep models. While this shows that these structures may be a fundamental and common structure of deep networks, does it imply that these structures may not be induced by the SGD training?\n\nA1: Thanks for the question. We think these structures are induced by both stochastic training and network architectures. Because, without SGD training, the full-batch gradient has no such structure; without proper network architectures, the power-law gradient structure may be broken. Interestingly and similarly, the success of deep learning can also attribute to both stochastic training and network architectures. \n\nQ2: How is the gradient matrix G computed for random initialized models and pre-trained models? Do you train these models for some iterations and compute the G?\n\nA2: Thanks for the question. We present the details in Appendix A.1, Lines 12-15. We freeze the model weights at some given point and only compute the gradients for $T$ iterations. The gradients over $T$ iterations can form the $n\\times T$ matrix $G$.  \n\nThe reviewer definitely recognized how the contributions of our work can significantly inspire the community. We gratefully hope the reviewer can insist on your opinions.\n"}]

Author rebuttal:

Meta-review: This paper studies stochastic gradient descent in trianing deep neural networks. with a particular focus on their covariance. The authors perform statistical tests on the distribution of stochastic gradients, and then demonstrate that the covariance spectrum of stochastic gradients follows a power law, which is robust to several changes in the setting. The results are solid and all reviewers have recommended acceptance.
Decision: Accept (poster)