Summary
This paper studies some statistical properties of stochastic gradients, with a particular focus on their covariance.
The 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.
EDIT: I have read the author's rebuttal, which partially addressed my concerns. However, some points still require clarification or a more precise analysis.
Strengths
This paper studies a very important and central problem.
Besides 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.
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. As a side remark, the Gaussianity "rate" cannot be larger than 95% as the significance level (rate of false rejections) is 0.05.
The 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.
Finally, 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.
Let 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).
Typos:
- Figure 5: spectrums -> spectra
- line 226: eliminate "which"
- The caption of Figure 13 wrongly states that Adam preserves the power law
In general, the quality of the English could be improved.
[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.
[2] Papyan, Vardan. "Traces of class/cross-class structure pervade deep learning spectra." The Journal of Machine Learning Research 21.1 (2020): 10197-10260.
[3] Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of the Hessian in deep learning: Singularity and beyond. arXiv preprint arXiv:1611.07476, 2016.
[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.
Questions
What is being plotted in Figure 1? On what are the $\chi^2$-KS tests exactly computed?
What are the authors trying to show with the study of the eigengaps?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
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.