The geometric properties of loss surfaces, such as the local flatness of a solution, are associated with generalization in deep learning. The Hessian is often used to understand these geometric properties. We investigate the differences between the eigenvalues of the neural network Hessian evaluated over the empirical dataset, the Empirical Hessian, and the eigenvalues of the Hessian under the data generating distribution, which we term the True Hessian. Under mild assumptions, we use random matrix theory to show that the True Hessian has eigenvalues of smaller absolute value than the Empirical Hessian. We support these results for different SGD schedules on both a 110-Layer ResNet and VGG-16. To perform these experiments we propose a framework for spectral visualization, based on GPU accelerated stochastic Lanczos quadrature. This approach is an order of magnitude faster than state-of-the-art methods for spectral visualization, and can be generically used to investigate the spectral properties of matrices in deep learning.
This paper analyzes the spectrum of the Hessian matrix of large neural networks, both from the theoretical and the empirical perspective. The main contributions are (1) a theoretical analysis of the max/min eigenvalues, showing that the max/min are larger/smaller for empirical Hessians compared to "true" Hessians, and (2) an empirical analysis and visualization of spectra using a Lanczos quadrature approach for a variety of training methods and architectures.
Generally, analyzing the local curvature of (approximate) optima is an important problem for building a better understanding of neural network loss surfaces and for shedding light on how that geometry might be related to generalization performance. Therefore, I find the topic of this paper salient, and the questions analyzed are sure to be of interest to a broad range of theoretically-minded and practically-minded deep learning researchers.
However, I did not find the theoretical analysis to be especially novel, deep, or informative. I also did not find the conclusions reached to be particularly compelling, especially insofar as they related to how the geometry might affect generalization performance. For these reasons, I think this paper is a bit below the bar for acceptance, and I'd encourage the authors to add more content and depth to their analysis in a future submission.
Let me elaborate on my above comments in slightly more detail.
On the Theoretical analysis:
The general observation being made here is that adding more data will tighten the spectrum. This behavior is well-known, e.g. simply adjusting the aspect ratio of the Marcenko-Pastur distribution gives the same effect. Similar behavior is known in more complicated models. The result in Theorem 1 is not especially novel and is probably available in the literature in some form (I didn't find an immediate reference, but even without one, and even if the precise result isn't presented formally in prior work, this type of result is quite well-known). 
Some of the assumptions are very strong, especially the independence of the entries in \epsilon. While I actually suspect that the overall conclusion of spectral broadening may be fairly robust, the argument in section 4.3 did not convince me. There could be very strong correlations in \epsilon that get induced by the architecture and learned weights, and these correlations could become larger as the dataset size grows, leading to big discrepancies with the predictions. This would probably be most pronounced when transitioning from the under-parameterized to over-parameterized regimes.
On the Empirical analysis:
As the authors note, the main Lanczos quadrature method being utilized was introduced in several prior works, and the "improvement" offered here is basically a small tweak (reducing the number of random vectors). The argument in section 5.2 for reducing this number to one was not particularly compelling, and if the author's regarded this modification as an important contribution, I would have appreciated a more thorough variance analysis, both from the theoretical and empirical perspectives.
Additionally, related to error analysis, the method utilized in this work (and in the prior works that this work build upon) does not really have a robust way of reliably measuring the error in the spectral density estimation. There is no guarantee that the estimate will be accurate. Such an error estimate should depend on the ground-truth spectrum, and if the ground-truth spectrum is particularly pathological (say, having a large density near zero and a sizable number of large outliers  [which may in fact be the case that may happen in practice!]), the estimate may be quite bad. So I'm actually not completely convinced that the results presented here are accurate estimates of the actual spectrum.
Finally, I found the method for generating the "True Hessian" to be quite ad-hoc and likely severely biased. To what extent are the results skewed by the particular data augmentation procedure being utilized? Any effort to control for this kind of bias would be an important addition to this paper. Additionally, it might have been useful to corroborate some of the main claims with regard to the True Hessian (vs Empirical Hessian) by utilizing a synthetic data distribution from which unbiased samples could be drawn. Lastly, even though the number of augmented samples was large, it was not very large compared to the number of parameters. Perhaps studying a regime in which the ratio was farther from one would have been useful.
On the conclusions:
One of the main important motivations for this analysis is to understand how curvature might relate to generalization. This motivation was put forward in the introduction and was the basis for the experiments comparing the Normal and Overfit model classes. However, I found this single type of comparison to provide very weak evidence in favor of the conclusion that flat minima generalize better. A more compelling argument in this direction would have included substantially more empirical evidence, or (perhaps in better keeping with the main perspectives of this paper) additional theoretical analysis of this particular point.
_____________
Overall, I think the problem studied in this paper is quite interesting, but I did not find the theoretical or empirical contributions to be sufficiently novel, deep, or informative to merit publication in their present form.