Towards understanding the true loss surface of deep neural networks using random matrix theory and iterative spectral methods
Authors: Diego Granziol
Timur Garipov
Dmitry Vetrov
Stefan Zohren
Stephen Roberts
Andrew Gordon Wilson
Venue:  (2020)
Keywords: Random Matrix theory
deep learning
deep learning theory
hessian eigenvalues
true risk

Abstract: 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.

Under review as a conference paper at ICLR 2020
TOWARDS UNDERSTANDING THE TRUE LOSS SURFACE OF DEEP NEURAL NETWORKS USING RANDOM MATRIX THEORY AND ITERATIVE SPECTRAL METHODS
Anonymous authors Paper under double-blind review
ABSTRACT
The geometric properties of loss surfaces, such the local flatness of 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 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-ar methods for spectral visualization, and can be generically used to investigate the spectral properties of matrices in deep learning.
INTRODUCTION
The extraordinary success of deep learning in computer vision and natural language processing has
been accompanied by an explosion of theoretical (Choromanska et al. 2015a b. Pennington & Bahri
2017) and empirical interest in their loss surfaces, typically through the study of the Hessian and its
eigenspectrum (Ghorbani et al. 2019 Li et al. 2017 Sagun et al. 2016 2017 Wu et al. 2017).
Exploratory work on the Hessian, and its evolution during training (e.g.. Dastrzzbkt et al. 2018). attempts understand why optimization procedures such as SGD can discover good solutions for training neural networks, given complex non-convex loss surfaces. For example, the ratio of the largest to smallest eigenvalues, known as the condition number, determines the convergence rate for first-order optimization methods on convex objectives (Nesterov) 2013). The presence of negative eigenvalues indicates non-convexity even at local scale. Hessian analysis has also been a primary tool in further explaining the difference in generalization of solutions obtained, where under Bayesian complexity frameworks, flatter minima, which require less information to store, generalize better than sharp minima (Hochreiter & Schmidhuber,, 1997). Further work has considered how large batch vs small batch stochastic gradient descent (SGD) alters the sharpness of solutions (Keskar et al. 2016),, with smaller batches leading to convergence to flatter solutions, leading to better generalization. These geometrical insights have led to generalization procedures, such as taking the Cesàro mean of the weights along the SGD trajectory (Garipov et al. 2018 Izmailov et al. 2018), and algorithms that optimize the model to select for local flatness (Chaudhari et al. 2016). Flat regions of weight space are more robust under adversarial attack (Yao et al. 2018). Moreover, the Hessian defines the curvature of the posterior over weights in the Laplace approximation for Bayesian neural networks (MacKay 1992 2003), and thus crucially determines its performance.
In this paper we use random matrix theory to analyze the spectral differences between the Empirical Hexsian, evaluated via finite data sample (hence related to the empirical risk) and what we term the True Hessian, given under the expectation of the true data generating distribution TT]
We consider loss surfaces that correspond to risk surfaces in statistical learning theory terminology.

---

Under review as a conference paper at ICLR 2020
In particular, we show that the differences in extremal eigenvalues between the True Hessian and the Empirical Hessian depend on the ratio of model parameters to dataset size and the variance per element of the Hessian. Moreover, we show that that the Empirical Hessian spectrum, relative to that of the True Hessian, is broadened; i.e. the largest eigenvalues are larger and the smallest smaller. We support this theory with experiments on the CIFAR- 10 and CIFAR-100 R-00 datasets for different learning rate schedules using a large modern neural network, the 110 Layer PreResNet.
It is not currently known if key results, such as (1) the flatness or sharpness of good and bad optima, (2) local non-convexity at the end of training, or (3) rank degeneracy hold for the True Hessian in the same way as for the Empirical Hessian. We hence provide an investigation of these foundational questions.
RELATED WORK, CONTRIBUTIONS AND PAPER STRUCTURE
Previous work has used random matrix theory to study the spectra of neural network Hessians under assumptions such as normality of imputs and weights, to show results such as the decreasing difference in loss value between the local and global minima (Choromanska et al. 2015a) and the fraction of negative eigenvalues at final points in training (Pennington& & Bahri 2017). To the authors knowledge no theoretical work has been done on the nature of the difference in spectra between the True Hessian and Empirical Hessian in machine learning. Previous empirical work on neural network loss surfaces (Ghorbani et al., 2019 Papyan 2018 Sagun et al. 2017] 2016 Jastrzębski et al. 2018)) has also exclusively focused on the Empirical Hessian or a sub-sample thereof.
The work closest in spirit to our work is the spiked covariance literature, which studies the problem of learning the true covariance matrix given by the generating distribution. from the noisy sample covariance matrix. This problem is studied in mathematics and physics (Baik & Silverstein, 2004 Bloemendal et al. 2016b a) with applications leading to extensively improved results in both sparse Principal Component Analysis (Johnstone & Lu 2004), portfolio theory (Laloux al. 1999) and
Bayesian covariance matrix spectrum estimation (Everson & Roberts (000). A key concept from this literature, is the ratio of parameters to data samples and its effect on the observed spectrum; this ratio is mentioned in (Pennington & Bahri 2017), but it is not used to determine the perturbation between the Empirical Hessian and True Hessian. (Kunstner et al., 2019) consider cireumstances under which the Empirical Fisher information matrix is a bad proxy to the True Fisher matrix, but do not use a random matrix theory to characterise the spectral perturbations between the two. We list our main contributions below.
We introduce the concept of the True Hessian, discuss its importance and investigate it both theoretically and empirically.
We use random matrix theory to analytically derive the eigenvalue perturbations between the True Hessian and the Empirical Hessian, showing the spectrum of the Empirical Hessian to be broadened.
We visualize the True Hessian spectrum by combining a GPU accelerated stochastic Lanc- zos quadrature (Gardner et al. 2018) with nuta-augmentation Our spectral visualization technique is an order of magnitude faster than recent iterative methods (Ghorbani et al.. 2019 [aayyan| 2018). requires one the observed moment information. This procedure can be generically used to compute the spectra of large matrices (e.g., Hessians, Fisher information matrices) in deep learning.
less hand-tuned hyper-paramett and is consistent with
3 PROBLEM FORMULATION
For an input æ E &d and output y E IR we have given prediction function h(:::): :R x RRP Rdy, we consider the family of prediction functions parameterised by weight vector w, i.e..
H = (h(-; w) w E Re} with given loss {h((:; w), y) dd. R44 + RR Ideally we would vary w such that we minimize the loss over our data generating distribution ((x y), known as the true risk.
Rerue(w) = 1
E(h(a; w), d) y) = (1(()((;w) y))
(1)
JRds x
2

---

Under review as a conference paper at ICLR 2020
with corresponding gradient gtrue (w)) V Rerue (w) and Hessian H (w) VV Veruu (w) If the loss is negative log likelihood, then the true risk is the expected negative log likelihood per data point under the data generating distribution. However, given a dataset of size N, only have access to the empirical or full risk
N
1
Remp (empp()) =
N Σ ((h(a,
and the gradients gemp (w) and Hessians H Hmmp(w) thereof. The Hessian describes the curvature that point in weight space w and hence the risk surface can be studied through the Hessian. Weight vectors which achieve low values of (quation2]de do not necessarily achieve low values of equation Their difference is known as the generalization gap. We rewrite our Empirical Hessian as
Hemp( (w) = H + e(w)
where ((w) = (wm) - H ( (w). A symmetric matrix with independent normally distributed elements of equal variance is known the Gaussian Orthogonal Ensemble (GOE) and matrix with independent non Con-Gasssian elements of equal variance is known as the Wigner ensemble.
3.1 FLATNESS AND GENERALIZATION WITH THE EMPIRICAL HESSIAN
By the spectral theorem, we can rewrite Hemp in terms of its eigenvalue, eigenvector pairs, [A,, Φı]:
H Hemp
Σ A.O.T.
(4)
The magnitude of the eigenvalues represent the magnitude of the curvature in the direction of the corresponding cigenvectors. Often the magnitude of the largest eigenvalue A1, or the Frobenius norm (given by the square root of the sum of all the eigenvalues squared (E x/)1/22, used to define the sharpness of an optimum (e.g., Jastrzbbski et al., 2018 2017). The normalized mean value of the spectrum, also known as trace p-1 Σ X² has also been used (Dinh et al. 2017). In all of these cases larger value indicates greater sharpness. Other definitions of flatness have looked at counting the number of 0 (Sagun et al. 20166). or close to (Chaudhari et al. 2016), eigenvalues.
It is often argued that flat solutions provide better generalization because they are more robust to shifts between the train and test loss surfaces (e.g., Keskar et al. 2016) that exist because statistical differences between the training and test samples. It is then compelling understand whether flat solutions associated with the True Hessian would also provide better generalization, since the True Hessian is formed from the full data generating distribution. If so, there may be other important reasons why flat solutions provide better generalization.
Reparametrization can give the appearance of flatness sharpness from the perspective of the Hessian. However, common practice to hold the parametrization of the model fixed when comparing the Hessian at different parameter settings, or evaluated over different datasets.
ANALYZING THE TRUE RISK SURFACE USING RANDOM MATRIX THEORY
We show that the elementwise difference between the True and Empirical Hessian converges to zero mean normal random variable, assuming Lipshitz bounded gradient. Moreover, we derive a precise analytic relationship between the values of the extremal values for both the Empirical and True Hessians, showing the eigenvalues for the Empirical Hessian to be larger in magnitude. This result indicates that the true risk surface flatter than its empirical counterpart.
4.1 REGULARITY CONDITIONS
We establish some weak regularity conditions on the loss function and data, under which the elements of & (w) converge to zero mean normal random variables.
For fixed dataset, the perturhing matrix E(w) can be seen fixed instance of random variable.
3

---

Under review as a conference paper at ICLR 2020
Lemma 1. For an L--Lpshhiz--onniimonn gradient and almost everywhere twice differentabll loss function E(((x; w).y), the True Hessian elements are strictly bounded in the range - -VPL z H, S VLL.
Proof. By the fundamental theorem of calculus and the definition of Lipshitz continuity Xmaz L
P
Tr(H²)
H Jik
J= +
Σ HHA
3.k
1k==1
(5)
H k= S Σ X & PT?
- -VPL S Hj=y S VPL
Lemma 2. For unbiased independent samples drawn from the data generating distribution and an L-Lipshitz loss the difference between the True Hessian and Empirical Hessian converges element-wit wise to a zero mean, normal random variable with variance & 1/N.
Proof. The difference between the Empirical and True Hessian E(w) is given
0 ((((x; w). v)
O
VVVRarue (w) VV Rempem Öw,ow
f(b(a,; w), ys)
ow, dw,dws
By Lemma [ the Hessian elements are bounded, hence the moments are bounded and using indepen- dence and the central limit theorem, equation converges almost surely to normal random variable P(ujkk (N))
Remark. For finite P and N oc, i.e. g P/N 0, |e(w)] 0 recover the True Hessian. Similarly in this limit our empirical risk converges almost surely to our true risk, i.c. we eliminate the generalization gap. However, in deep learning typically the network size eclipses the dataset size by orders of magnitude
4.2 A RANDOM MATRIX THEORY APPROACII
In order to derive analytic results, we move to the large Dimension limit, where P, -> oo but P/N - q 0 and employ the machinery of random matrix theory derive results for the perturbations on the eigenspectrum between the True Hessian and Empirical Hessian. This differs from the classical statistical regime where q + We primarily focus on the regime when > In order to make the analysis tractable, we introduce two further assumptions on the nature of the elements Eww).
Assumption 1. The elements of e(ur) are identically and independently Gaussian distributed (0, of) up to the Hermitian condition.
Assumption 2. Htrue is of low rank < P.
Under assumption I e(w) becomes a Gaussian Orthogonal Ensemble (GOE) and for the GOE we prove the following Lemma 3 We discuss the necessity of the assumptions in Section 4.3
Lemma 3.
The extremal eigenvalues [X, Xp] of the matrix sum A + B/VP, where A E PxP matrix of finite rank with extremal eigenvalues [A1, and B E PxP a GOE matrix with element variance o² are given by
X1
A
Xp
Ap+
<
20c.
otherwise
-20e:
otherwise
CCIFAR datasets, which have 50, 000 examples, are routinely used to train networks with about 50 million parameters.
4

---

Under review as a conference paper at ICLR 2020
Proof. See Appendix.
Theorem 1. The extremal eigenvalues XX,Xp) of the matrix sum Hemp where X 2 Xz... 2 Xp and are satisfied), where Herue has extremal eigenvalues [Λ1, Apl, are
(such that assumptions given by
A1 11t P if /
}.
P a N Ap
if - -vRo.
Ap
X1
otherwise {
Xp
S
(8)
2 fo
2 No
otherwise
Proof. The result follows directly from Lemmas and 3
Remark. This result shows that the extremal eigenvalues of the Empirical Hessian are larger in magnitude than those of the True Hessian: Although we only state this result for the extremal eigenvalues, it holds for any number of well separated outlier eigenvalues. This spectral broadening effect has already been observed empirically when moving from (larger) training to the (smaller) test set (Papyan 2018). Intuitively variance of the Empirical Hessian eigenvalues variance of the True Hessian eigenvalues plus the variance of the Hessian, as we show in Appendix We also note that if the condition |Ai] >> /P/No, not met, the value of the positive and negative extremal eigenvalues are completely determined by the noise matrix.
be seen the
4.3 NOTE ON GENERALIZING ASSUMPTIONS
For Assumption T we note that the results for the Wigner ensemble (of which the GOE is a special case) can be extended to non-identical element variances TTo 2012) and element dependence (Götze ct al. 2012 Schenker & Schulz-Baldes 2005). Hence, similarly to Pennington & Bahri (2017), under
extended technical conditions we expect our results to hold more generally. Assumption 2 can be relaxed if the number of extremal eigenvalues is much smaller than P, and the bulk of H true (w)'s eigenspectra also follows a Wigner ensemble which is mutually free with that of (ww). Furthermore, corrections to our results for finite scale as P-1/1 for matrices with finite 4 4'th moments and p-2/5 for all finite moments (Bai 2008).
EFFICIENT COMPUTATION OF HESSIAN EIGENVALUES
In order perform spectral analysis on the Hessian typical neural networks, with tens of millions of parameters, we avoid the infeasible O(P*) eigen-decomposition and use the stochastic Lanczos quadrature (SLQ) algorithm, conjunction with GPU acceleration. Our procedure in this section is general-purpose
general- purpose approach for efficiently computing the spectra of large matrices in deep learning.
5.1 STOCHASTIC LANCZOS QUADRATURE
The Lanczos algorithm (Meurant Strakos 2006) a power iteration algorithm variant which by enforcing orthogonality and storing the Krylov subspace, Km (H, v) = (v, Hv,., H")v,, opti- mally approximates the extremal and interior eigenvalues (known as Ritz values). It requires Hessian vector products, for which O(NP), where N is the dataset size and P is the number of parameters. Hence for m steps the total computational complexity including re-orthogonalisation is ON Pm) and memory cost of O(Pm). In order to obtain accurate spectral density estimates we re-orthogonalise at every step (Meurant Strakoš 2006). We exploit the relationship between the Lanezos method and Gaussian quadrature, using random vectors to allow us to learn discrete approximation of the spectral density, quadrature rule is relation of the form.
the Pearlmutter trick (Pearlmutter) 1994) with computational cost
M S" [())d(()) Ep:((t))++ + R[J
for function f. such that its Riemann- Riemann-Stieltjes integral and all the moments exist the measure dp(A), on the interval [a, b] and where R[f] denotes the unknown remainder. The nodes t, of the Gauss quadrature rule are given by the Ritz values and the weights (or mass) Pj by the squares of the
5

---

Under review as a conference paper at ICLR 2020
first elements of the normalized eigenvectors of the Lanczos tri tri-diagonal matrix (Golub & Meurant 1994). For zero mean, unit variance random vectors, using the linearity of trace and expectation
Σ xT -
Tr('" v) = TriE (vv H Tr(
(10)
hence the measure on the LHS of equation 9 corresponds to that of the underlying spectral density. The error between the expectation over the set of all zero mean, unit variance vectors u and the Monte Carlo sum used in practice can be bounded (Hutchinson, 1990 [Roosta-Khorasan & Ascher 2013). but the bounds are too loose to be of any practical value (Granziol & Roberts 2017). However, in the high dimensional regime N + DC, we expect the squared overlap of each random vector with an eigenvector of H, j0" 0, 1 ~ Vi. with high probability (Cai et al. 2013). This result can be seen intuitively by looking at the normalized overlap squared between two random Rademacher vectors, where each element is drawn from the distribution +1 with equal probability, which gives 1/P. The Lanezos algorithm can also be easily parallelized, since largely involves matrix multiplications major advantage for computing eigenvalues of large matrices in deep learning. We exploit GPU parallelization in performing Lanczos (Gardner et al. 2018), for significant acceleration.
5.2
WHY TO AVOID MULTIPLE RANDOM VECTORS AND KERNEL SMOOTHING
In recent work using SLQ for evaluating neural network spectra Paayynn 2018 Ghorbani et al. 2019), the Hessian vector product is averaged over a set of random vectors, typically x 10. The resulting discrete moment matched approximation to the spectra in equation 9 smoothed using Gaussian kernel N (AA,, o²). The use of multiple random vectors can be seen as reducing the variance of the vector overlap in geometric equivalent of the central limit theorem. Whilst this may be desirable for general spectra, we believe the spectra to be composed of outliers and a bulk as is empirically observed (Sagun al., 2016: 2017). then the same self eelf-averaging procedure happens with the bulk. We converge to the spectral outliers quickly using the Lanczos algorithm, as shown in the Appendix by the known convergence theorem 3 Hence all the spectral information we need can be gleaned from a single random vector. Furthermore, it has been proven that kernel smoothing biases the moment information obtained by the Lanezos method (Granziol al., 2018). We hence avoid smoothing (and the problem of choosing σ), along with the 2 10x increased computational cost, by plotting the discrete spectral density implied by equation 9 for single random vector, in the form of stem plot.
5.3 WEAKNESSES OF STOCHASTIC LANCZOS QUADRATURE
is possible to determine what fraction of eigenvalues is near the origin by evaluating the weight of the Ritz value(s) closest to the origin. But due to the discrete nature of the Ritz values, which give the nodes of the associated moment-matched spectral density in equation 9 it is not possible to see exactly whether the Hessian of neural networks is rank degenerate. It is also not possible to exactly determine what fraction of eigenvalues are negative. Furthermore, smoothing the density and using quadrature has the problems discussed in Section 5.2 Instead, we determine the fraction of negative eigenvalues as the weight of negative Ritz values which are well separated from the smallest magnitude Ritz value(s), to avoid counting split of the degenerate mass.
6 EXPERIMENTS
In order to test the validity of our theoretical results in Section 4.2 we control the parameter P/N by applying data-augmentation and then running GPU powered Lanczos method (Gardner al.) 2018) on the augmented dataset at the final set of weights final at the end of the training procedure. We use random horizontal flips, 4 x padding with zeros and random 32 x 32 crops. We neglect the dependence of the augmented dataset on the input dataset in our analysis, but we would expect the effective number of data points Ness < N due to degeneracy in the samples. For the Emprical Hessian, we use the full training and test dataset N = 50, 000 with no augmentation. We use py PoToch (Paszke et al., 2017). We train a 110 layer pre-activated ResNet (He et al., 2016) neural network architecture and data- iitiaaaagmenttttionn.. We include further plots and detail the training procedure for the VGG-16 2014) in Appendix
CIFAR-10 and CIFAR-100 using SGD with momentum set at p 0.9
(Simonyan & Zisserman

---

Under review as a conference paper at ICLR 2020
Spectrs Derest
10
10
11.53
Figure I: Empirical Hessian spectrum for CIFAR-100 SGD.
Spectal Dereity
10
10:4
Eigervalue
Figure 2: Empirical Hessian spectrum for CIFAR-10 SGD.
In order to investigate whether empirically observed phenomena for the Empirical Hessian such as sharp minima generalizing more poorly than their flatter counterparts also hold for the True Hessian, we run two slightly different SGD decayed learning rate schedules (equation on a 110-Layer ResNet (Izmailov et al. 2018).
00:
if + 0.5
ao (1-r1($-0.5)
0f < $ 0.9 otherwise
(11)
agT,
For both schedules we use 0.01. For the Normal schedule we use 0.1 and T = 225 whereas for the Overfit schedule we use op 0.001 and T 1000.
We plot the training curves in the Appendices B C and include the best training and test accuracies and losses, along with the extremal eigenvalues of the Empirical Hessian and Augmented Hessian in [orr CIFAR-100 (00 and Table CIFAR-10. The Normal schedule achieves a best test accuracy of [77.24/95. 32] on CIFAR-IO0/CIES 100/CIFAR-III 10 respectively and best training accuracy of 199.85/99 /99.98) The Overfit schedule achieves best test accuracy of [56.85/86.4] respectively and best training accuracy [99.62/ /99.91/...91].
CIFAR-100/CIEE
We then run SLQ with to the spectrum for both schedules on the full 50, 000 training set (i.e the Empirical Hessian) and with 80 denote the Augmented Hessian. The 110-Layer ResNet has 1, 169, 972 146, 842 parameters for respectively, hence for both we have 1. We primarily comment the extremal eigenvalues of the Augmented Hessian and their deviation from those of the Empirical Hessian. We also investigate the spectral density the origin and the change in negative spectral mass. A sharp drop in negative spectral mass, indicates due to Theorem | that most of the negative spectral mass due to the perturbing GOE.
100 the final set of training weights to compute approximation
augmented 1, 500, 000 data-set
proxy for the True Hessian, which
6.1
NORMAL SGD SCHEDULE EMPIRICAL AND AUGMENTED HESSIAN ANALYSIS
Speetral Deesky
20-1
-
h0-0
1
10-1
-1.37
-0.11
0.56
-6.41
-0.014 3.026 Figerwalue Size
Eigenvalue Size
Figure 3: Augmented 1, 500, 000 data Hes- sian spectrum for CIFAR-I0 SGD.
Figure 4: Augmented 1, 500, 000 data Hes- sian spectrum for CIFAR- 100 SGD.
7

---

Under review as a conference paper at ICLR 2020
We plot the Empirical Hessian spectrum for the end of training for CIFAR-100 in Figure 1 and the Augmented Hessian in Figure [4] We plot the same discrete spectral density plots for the Empirical Hessian for CIFAR-10 in Figure and the Augmented Hessian in Figure 3 We note that the effeets predicted by Theorem are empirically supported by the differences between the Empirical and Augmented Hessian. For CIFAR-100 the extremal eigenvalues shrink from [-6.54, 20.56] (Figure I for the full dataset to [-0.014, 3.026] (Figure for the Augmented dataset. The Empirical Hessian has 43/100 negative Ritz values with negative spectral mass total of 0.05. The Augmented Hessian has 5/80 negative Ritz values with total negative spectral mass of 0.00016. For CIFAR-10 the extremal eigenvalues shrink from 1-334, 6.821] (Figure 2 [-0.0061, 0.5825] (Figure 3). The fraction of negative Ritz values shrinks from 35/ 100 with total weight 0.09 to 3/ 3/80 with total mass 0.03.
6.2
OVERFITTING SGD SCHEDULE EMPIRICAL AND AUGMENTED HESSIAN ANALYSIS
Dersity
10
10-1
10-4
10
185.1
Eigenvalue Size
Figure 5: Empirical Hessian Spectrum C100 OverFit SGD,
Spectral Deneny
10.1
10
59.7
122.2
184.8
Eigenvalue Size
Figure 6: Empirical Hessian Spectrum C10 OverFit SGD.
As can be seen from the spectral plots of the full Hessians for both CIFAR- 100 and CIFAR-10
in Figures 6 & (5 and their respective Augmented Hessian 7 & g we also observe extreme spec- tral shrinkage, with the largest eigenvalue decreasing from 281 .2, 184.4) to [45.68, 15.6) and the smallest increasing from [-7.33, -29) to X 10 -9 10 respectively for
10. We note that despite reasonably extreme spectral shrinkage, the sharpest values of the Overfit schedule augmented Hessians still significantly larger than those of the Normal schedule, hence the intuition of sharp minima generalizing poorly still holds for the True Hessian. The fraction of negative Ritz values for the Empirical Hessian is 43/100, with relative negative spectral mass of 0.032. For the Augmented Hessian, the number of negative Ritz values is O. For the CIFAR- 10 Overfit Augmented Hessian, there is one negative Ritz value very close the origin with large relative spectral mass 0.086, hence it could also be part of the spectral peak at the origin.
Deraty
10
10-3
10.5
10-1
0.00
22.
45.88
-0.07.15.8
Eigervalue Size
Eigenvalue Size
Figure 7: Augmented Data 500, 000 Hes- sian Spectrum C100 OverFit SGD.
Figure Augmented Data 1, 500, 000 Hes- sian Spectrum C10 OverFit SGD.
6.3 RANK DEGENERACY AND RIGHT SKEW
The vast majority of eigen- dicenddiettions of the Augmented Hessian are, like those of the Empirical Hessian, locally extremely close to flat. We show this by looking at the 3 Ritz values of largest weight
8

---

and Fisher information Under review as a conference paper at ICLR 2020
for all learning rate schedules and datasets, shown in Table 3 The majority of the spectral bulk is carried by the 3 closest weights (<= 0.99) to the origin for all learning rate schedules and datasets. In instances (CIFAR- 100 SGD OverFit) where it looks like the largest weight has been reduced, the second largest weight (which is close in spectral distance) is amplified massively.
We further note that, to right skew bulk. Both have a significant spike near the origin. This experimentally corroborates the result derived in (Pennington & Bahri] 2017), where under normality of weights, inputs and further assumptions the symmetric bulk is given by the Wigner semi-circle law and the right skew bulk is given by the Marcenko- Pastur. The huge spectral peak near the origin, indicates that the result lies in a low effective dimension.
move from the q > regime
1, move from having symmetric
For all Augmented spectra, the negative spectral mass shrinks drastically and we see for the Overfit Schedule for CIFAR-100 that there is no spectral mass below 0 and for CIFAR-10 there is one negative Ritz value (and 79 positive). This Ritz value X, -0.00093 has a weight of p = 0.085 compared to the largest spike at À 0.0001 with weight 0.889, hence we cannot rule out that both values belong to a true spectral peak at the origin.
DISCUSSION
The geometric properties of loss landscapes deep learning have a profound effect on generalization performance. We introduced the True Hessian to investigate the difference between the landscapes for the true and empirical loss surfaces. We derived analytic forms for the perturbation between the extremal eigenvalues of the True and Empirical Hessians, modelling the difference between the two as a Gaussian Orthogonal Ensemble. Moreover, we developed a method for fast eigenvalue computation and visualization, which used in conjunction with data augmentation approximate the True Hessian spectrum.
We show both theoretically and empirically that the True Hessian has smaller variation in eigenvalues and that its extremal eigenvalues are smaller in magnitude than the Empirical Hessian. We also show under framework that expect the Empirical Hessian to have greater negative spectral density than the True Hessian and our experiments support this conclusion. This result may provide some insight as why first order (curvature blind) methods perform so well on neural networks. Reported non-convexity and pathological curvature is far worse for the empirical risk than the true risk, which what we wish to descend.
The shape of the true risk is particularly crucial for understanding how to develop effective procedures for Bayesian deep learning. With a Bayesian approach, we not only want to find a single point that optimizes a risk, but rather to integrate over loss surface to form Bayesian model average. The geometric properties of the loss surface, rather than the specific location of optima, therefore greatly influences the predictive distribution in Bayesian procedure. Furthermore, the posterior representation for neural network weights with popular approaches such as the Laplace approximation has curvature directly defined by the Hessian.
In future work, one could also replace the GOE noise matrix (ww) with a positive semi-definite white Wishart kernel in order to derive results for the empirical matrices, which are by definition positive semi-definite and are commonly employed in second order deep learning (Martens & Grosse 2015). Our approach to efficient eigenvalue computation and visualization can be used as a general-purpose tool to empirically investigate spectral properties of large matrices in deep learning, such the Fisher information matrix.
REFERENCES
Zhi Dong Bai. Convergence rate of expected spectral distributions of large random matrices part i: Wigner matrices. In Advances In Statistics, pp. 60-83. World Scientific. 2008.
Jinho Baik and Jack W Silverstein. Figenvalues of large sample covariance matrices of spiked population models. arXiv preprint math/0408165, 2004.
Alex Bloemendal, Antti Knowles, Horn--Tzer Yau, and Jun Yin. On the principal components of sample covariance matrices. Probability theory and related fields, 164(1-2):459-552 2016a.
9

---

Under review as a conference paper at ICLR 2020
Alex Bloemendal, Bälint Virág, et al. Limits of spiked random matrices ii. The Annals of Probability, (1119):2226-77699 2016b.
Johl Bun, Jean-Philippe Bouchaud, and Marc Potters. Cleaning large correlation matrices: tools from random matrix theory. Physics Reports, 666:1-109, 2017.
Tony Cai, Jianqing Fan, and Tiefeng Jiang. Distributions of angles in random packing on spheres. The Journal of Machine Learning Research, 14()):1837-184, 2013.
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-SGD: Biasing gradient descent into wide valleys. arXiv preprint 1xXi::6611.08838 2016.
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial Intelligence and Statistics, pp. 192-204 2015a.
Anna Choromanska, Yann LeCun, and Gérard Ben Arous. Open problem: The landscape of the loss surfaces of multilayer networks. In Conference on Learning Theory, pp. 1756-1 1760, 2015b.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In Proceedings of the 34th International Conference on Machine Learning Volume 70, pp. 1019-1028. JMLR. org, 2017.
Richard Everson and Stephen Roberts. Inferring the eigenvalues of covariance matrices from limited, noisy data. IEEE transactions on signal processing, 48(7):2083-209) 2000.
Jacob Gardner, Geoff Pleiss, Kilian Q Weinberger, David Bindel, and Andrew Wilson. Gpytorch: Blackbox matrix-matrix Gaussian process inference with GPU acceleration. In Advances in Neural Information Processing Systems, pp. 7576-7586, 2018.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew Wilson. Loss surfaces, mode connectivity, and fast ensembling of DNNs. In Advances in Neural Information Processing Systems. pp. 9789,8798, 2018.
Behrooz Ghorbani, Shankar Krishman, and Ying Xiao. An investigation into neural net optimization via Hessian eigenvalue density. arXiv preprint arXiv: 1rX1v:1901.10159, 2019.
Gene H Golub and Gérard Meurant. Matrices, moments and quadrature. Pitman Research Notes in Mathematics Series, pp. 105-105, 1994.
Gene H Golub and Charles F Van Loan. Matrix computations, volume 3. JHU press, 2012.
Friedrich Götze, A Naumov, and A Tikhomirov. Semicircle law for class of random matrices with dependent entries. arXiv preprint arXiv:1211.038% 2012.
Diego Granziol and Stephen J. Roberts. Entropic determinants of massive matrices. In 2017 IEEE International Conference on Big Data, BigData 2017, Boston, MA, USA, December 11-14, 2017, pp. 88 88-93, 2017.
Diego Granziol, Binxin Ru, Stefan Zohren, Xiaowen Dong, Michael Osborn,, and Stephen Roberts. Entropic spectral learning for large-scale graphs. arXiv preprint arXiv: arXiv: 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Computation, 9(1):1-42, 1997.
Michael F Hutchinson. A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Communications in Statistics-Simulation and Computation, 19(2):43344) 1990.
Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wilson. Av- eraging weights leads to wider optima and better generalization. arxiv preprint arXiv: 2018.
10

---

Under review as a conference paper at ICLR 2020
Stanistaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima SGD. arXiv preprint arXiv:1711.0460 0.622,,, 2017.
Stanistaw Jastrzebski, Zachary Kenton, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. On the relation between the sharpest directions of DNN loss and the SGD step length. 2018.
lain M Johnstone and Arthur Yu Lu. Sparse Principal Components Analysis. Unpublished manuscript, 7, 2004.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609, 169.04669 2016.
Frederik Kunstner, Lukas Balles, and Philipp Hennig. Limitations of the empirical Fisher approxima- tion. arXiv preprint arXiv: 1999999555.... 2019.
Laurent Laloux, Pierre Cizeau, Jean- Phinlpilipppe Bouchaud, and Mare Potters. Noise dressing of financial correlation matrices. Physical review letters, 83(7):1467, 1999.
Olivier Ledoit and Michael Wolf. A well-conditioned estimator for large-dimensional covariance matrices. Journal of multivariate analysis, 88(2):365-41,, 2004.
Hao Li, Zheng Xu, Gavin Taylor, and Tom Goldstein. Visualizing the loss landscape of neural nets. arXiv preprint 1rXiv:1712.09911 2017.
David JC MacKay. Bayesian methods for adaptive models. PhD thesis, California Institute of Technology, 1992.
David JC MacKay, Information theory, inference and learning algorithms. Cambridge university press, 2003.
James Martens and Roger Grosse. Optimizing neural networks with Kronecker-factored approximate curvature, In International conference on machine learning, pp. 2408-2417, 2015.
Gérard Meurant and 7denčk Strakoš. The Lanczos and conjugate gradient algorithms in finite
precision arithmetic. Acta Numerica, 15:471-542. 2006.
Yurii Nesterov. Introductory lectures on convex optimization: basic course, volume 87. Springer Science & Business Media, 2013.
Vardan Papyan. The full spectrum of deep net Hessians at scale: Dynamics with sample size. arXiv preprint 181 1.00062, 2018.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary De Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in Pytorch. 2017.
Barak A Pearlmutter. Fast exact multiplication by the Hessian. Neural computation, 6(1):147-160 1994.
Jeffrey Pennington and Yasaman Bahri. Geometry of neural network loss surfaces via random matrix theory. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp- 2798-2806. JMLR. org, 2017.
Farbod Khorasann and Uri Ascher. Improved bounds sample size for implicit matrix trace estimators. Foundations of Computational Mathematics, 15(5):118--1211 2015.
Levent Sagun, Léon Bottou, and Yann LeCun. Figenvalues of the Hessian in deep learning: Singularity and beyond. arXiv preprint arXiv: 1.07477, 2016.
Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis the arXiv:1706.0444 (eee/776.444444 04454, 2017.
Hessian of over-parametrized neural networks. arXiv preprint arXiv:
11

---

Under review as a conference paper at ICLR 2020
Jeffrey H Schenker and Hermann Schulz-Baldes Semicircle law and freeness for random matrices with symmetries or correlations. arXiv preprint ph/th- 2005.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409. 1556, 2014.
Terence Tao. Topics random matrix theory, volume 132. American Mathematical Soc., 2012.
Lei Wu, Zhanxing Zhu, et al. Towards understanding generalization of deep learning: Perspective of loss landscapes. arXiv preprint arXiv:1706.102333 2017.
Zhewei Yao, Amir Gholami, Qi Lei, Kurt Keutzer, and Michael W Mahoney. Hessian- analysis of large batch training and robustness to adversaries. In Advances in Neural Information Processing Systems, pp. 4959-4959, 2018.
A
TABLE SUMMARIES
Schedule
X
X,
A
An
Test Acc
Train Acc
Test Loss
Train Loss
Normal 20.56
-6.54
3.025
-0.014
77.24
99.85
0.99
0.021
Overfir 281.32
-7.33
45.68
2 x 10-3
56.85
99.62
1.85
0.026
Table 1: CIFAR-100 statistics table including extremal eigenvalues of the Empirical Hessian [X4, X,,, the True Hessian (Y1, An] and test/train accuracies and losses.
Schedule X
X/
An
Test Acc
Train Acc
Test Loss
Train Loss
Normal 6.82
-1.37
3.025
-0.014
95.32
99.98
0.18
0.0034
Overfit 184.4
-2.9
15.6
-9
10m4
86.46
99.91
1.85
0.026
Table 2: CIFAR-10 10 statistics table including extremal eigenvalues of the Empirical Hessian M,].
the True Hessian [A1, Aa] and test/train accuracies and losses
Learning Schedule DataSet
[Po, Au]
[P1, A1]
[p2, Az]
CIFAR- 100 SGD Normal
[0.92,0.0014]
[0.05,-0.03]
[0.018,0.06]
CIFAR-100 SGD Normal (Augmented)
(0.84,0.0017]
[0.1,-0.000]]
[0.045,0.003]
CIFAR-10 10 SGD Normal
[0.88,0.007]
[0.085,-0.01]
[0.023.0.02]
CIFAR-10 SGD Normal (Augmented)
[0.88.-3.87c-6]
[0.073.0.0006]
[0.03,-0.0007]
CIFAR- 100 SGD Overfit
[0.65.-0.026]
[0.34,0.05]
[0.006,0.58]
CIFAR-100 100 SGD Overfit (Augmented)
(0.86.1.67-55)
[0.1,0.0039]
[0.019.0.018]
CIFAR-10 SGD Overfit
[0.77.0.01]
[0.22,-0.04]
[0.005,0.32]
CIFAR- SGD Overfit (Augmented)
[0.89,0.00013]
[0.086.-0.00044]
[0.016,0.0058]
Table 3: Largest 3 weight Ritz values for different learning schedules and datasets. [p,, Ar] denotes the weight and corresponding eigenvalue Po P1.... 2 pp.
12

---

Under review as a conference paper at ICLR 2020
B
SGD TRAINING CURVES
Figure 9: SGD CIFAR-100 training and test curves
100
triin loss
test loss
M
50
100
150
200
(a) Test and Training accuracy c100 SGD
(b) Test and Training loss c100 SGD
Figure 10: SGD CIFAR-10 training and test curves
100
1:50
train loss
1.00
0.75
M4y 2./ Mmm Mm
0.50
acturacy test accurcc
0.25
0.00
50
100
150
250
50
120
150
200
(a) Test and Training accuracy c10 SGD
(b) Test and Training loss c10 SGD
C
OVERFIT TRAINING CURVES
Figure 11: OverFitSGI CIFAR-100 training and test curves
tain loss
accuracy
leat loss
50
600
200
400
600
800
1000
(a) Test and Training accuracy c100 OverFitSGD
(b) Test and Training loss c100 OverFitSGD
Figure 12: OverFitSGD CIFAR-10 training and test curves
100
train less
twxt
trais accuracy testaccurso
0.0
200
400
600
1000
200
400
800
1000
(a) Test and Training accuracy c10 OverFitSGD
(b) Test and Training loss c10 OverFitSGD
13

---

Under review as a conference paper at ICLR 2020
D RANDOM MATRIX THEORY
Following the notation of (Bun et al. 2017) the resolvent of a matrix H is defined as
(= = (=IN H)-
(12)
with r + in E C. The normalised trace operator of the resolvent, in the N - oc limit
N [T) N=20, S(z) / p(u) du
Sx(z)
(13)
is known as the Stieltjes transform of p. The functional inverse of the Siteltjes transform, is denoted the blue function B(S(z)) The R transform is defined
R(w) = B(w)
(14)
erucially for our calculations, it is known that the R transform of the Wigner ensemble is
(w a²=
(15)
Definition D.1. Let {Yi} and {Ziz Sisiss be two real-valued families of zero mean, i.i.d random variables, Furthermore suppose that 1,7,222 and for each h E N
max marrEE/Zi,,11 E| <0
(16)
Consider X symettric matrix Mn. whose entries are given by
(1, Y; (i, = Zis = Mn(j,i), if 2 1
(17)
The Matrix M, is known real symmetric Wigner matrix.
Theorem 2. Let (M,) ] be sequence of Wigner matrices, and for each n denote X, = Mn/ Vn. Then Mx,.> converges weakly, almost surely to the semi circle distribution,
d(r)dr
V x21 m|52
(18)
2T
the property of freeness for non commutative random matrices can be considered analogously to the moment factorisation property of independent random variables. The normalized trace operator, which is equal to the first moment of the spectral density
N
v (H) =
1 TrH =
1
Σ
/ du(A)A
(19)
N
N
XED
1=1
We say matrices A&B for which (AA) = (BB) with & N+
are free if they satisfy for any integers ni...ig
= w ((
(20)
E DERIVATION
The Stijeles transform of Wigners semi circle law, can be written as (Too 2012)
Sw(z) 2 + / 2
(21)
202
from the definition of the Blue transform, hence have
2 Bw (2) + v By (2) 4
202
(20² Bw Byy (2) 40
(22)
1
:. Bw(z)= = 1 +
Rw(2) = 022
"We always consider the transform 1
14

---

Under review as a conference paper at ICLR 2020
Computing the R transform of the rank matrix Heree with largest non-trivial eigenvalue 3, on the effect of the spectrum of a matrix A, using the Stieltjes transform we easily find following (Bun et al. 2017) that
1 N
1
(1
1
B
S Serree (u)
(1-N)
(23)
N
N
We can use perturbation theory similar in equation equation 22 leading order gives
find the blue transform which to
B
Biteree (w) = + N(1 wB)
+ +O(N22)
(24)
8
Rerre (w) N(1 - w3) +(N-2
setting w = SM (z)
8
2 BHeoee (Sar(z)) N(1 - 3Sm + O(N-2)
(25)
using the ansatz of (2) So(z) S1())
O(N-2) find that So(z) = Se(w) (2) and using
that (2) (2) conclude that
BS <(w) (2)
Si(z)
(26)
Se(w) (z)3
and hence
3S <(ww) (x)
SM (z) ~ (z)
(27)
N 1 (w)) (2)
and hence the large N limit the correction only survives S Sc(w) = 1/3
Selw) (2) 1
B
202
B 2 + V22 2
4
(28)
0²
3
3
clearly for 3 + -B we have
-3
(29)
F AN INTUITIVE EXPLANATION OF THE KEY RESULT
An extensive linear algebraic and geometric discussion about spectral broadening for sample co- variance matrices can found (Ledoit & Wolf 2004) and whilst the Hessian a covariance matrix (the generalized Gauss-Newtor or Fisher matrices can be seen co-variance of gradients), identical arguments will hold here | The dispersion of the Empirical Hessian eigenvalues around their mean will equal the dispersion of the True Hessian eigenvalues around their mean plus the variance of the Empirical Hessian (from its true value), which is in general > 0. Our theoretical derive analytic results for this broadening. Our
assumptions in sections 4.1 and 4.2 allow assumptions are significantly stricter than those (Ledoit & Wolf 2004) and hence automatically fulfil their requirements.
'he proof of Lemmal
(Ledoit Wolf 2004) does not depend on the matrix being PSD
15

---

Under review as a conference paper at ICLR 2020
G LANCZOS ALGORITHM
In order to empirically analyse properties of modern neural network spectra with tens of millions of parameters N O(10"), use the Lanczos algorithm (Meurant & Strakoš 2006) with Hessian vector products using the Pearlmutter trick (Pearlmutter 1994) with computational cost (N)T)), where N the dataset size and
the number of Lanczos steps. The main properties of the Lanezos
algorithm are summarized in the theorems 34
Theorem 3. Let HNXN be a symmetric matrix with eigenvalues \ .. An and corresponding orthonormal eigenvectors znn- If0, ... Om are the eigenvalues of the matrix T obtained after m Lanczos steps and 41 the corresponding Ritz eigenvectors then
(A1 An (81)
A1 01
A1
(cx-1 2p1))²
(30)
(A1 - An) (01)
An 0g S Am +
(ck-1(1 + 2p1))²
where Gp is the chebyshev polyomial of order k
Proof: see Golub Van Loan 2012).
Theorem 4. The eigenvalues Th
the TT are the nodes t, of the Gauss quadrature rule, the weights wy are the squares of the first elements of the normalized eigenvectors of TT
Proof: See (Golub & Meurant 1994). The first term on the RHS of equation Jusing Theorem 4 can be seen discrete approximation to the spectral density matching the first moments o² """ (Golub & Meurant 1994, Golub & Van Loan| 2012), where e is the initial seed vector. Using the
expectation of quadratic forms, for zero mean, unit variance random vectors, using the línearity of trace and expectation
Σ A - N J Adp(A)
E, Tr(w H") = TrE, Hm) = Tr(H"))
(31)
AED
The error between the expectation over the set of all zero mean, unit variance vectors and the monte carlo sum used in practice can be bounded (Hutchinson 1990, Roosta- Khooassan Ascher 2015). However in the high dimensional regime N + oc, we expect the squared overlap of each random vector with an eigenvector of H, |v Φb N Vi, with high probability. This result can be seen by computing the moments of the overlap between Rademacher vectors, containing elements P(u. +1) = 0.5. Further analytical results for Gaussian vectors have been obtained (Cai et al.
2013
H SPECTRAL PLOTS- CIFAR- 100 PRERESNET
Spectral Denaity
10
10-4
10
-0.77
2.52
5.81
9.11
12.40
Eigenvalue Size
Figure 13: Augmented CIFAR-100 PreResNet 110 Eigenspectrum Epoch 300, 5 million samples and m 10 Lanezos steps
16

---

Under review as a conference paper at ICLR 2020
Spectral Deeatyy
20-3
1.00
10:71
Eggenvalue
Figure 14: CIFAR-100 PreResNetl 10 O'th epoch full dataspectrum
Spectra Drevity
20-2
20-h
20
-1.501
0.147
1.795
3.445
5.093
5.742
E Eggenvalue Size
Figure 15: CIFAR 100 PreResNetl 10 25' epoch full dataspectrum
10'
Speettll Denely
20-4
20
-3.34
2.85
5.04
7.34
Eigenvalue Size
Figure 16: CIFAR- 100 PreResNetl 10 50' epoch full dataspectrum
Speetral Davatt
10
20
10
20-2
Figure 17: CIFAR- 100 PreResNetl 10 75'th epoch full dataspectrum
Spectra Denalty
1.04
20-9.
-224
0.31
2.87
5.42
7.98
10.54
Eigeenoolaa
Figure 18: CIFAR- 100 PreResNet110 125'th epoch full dataspectrum
10'
Speectel Deealty
20-2
20r4
-6.37
5.17
10.95
70
22.47
Eigenvalue Size
Figure 19: CIFAR-100 PreResNet1 150'th epoch full dataspectrum
17

---

Under review as a conference paper at ICLR 2020
Specteel Deenity
20-2
10-4
-6.37
-0.60
5.17
10.95
16. 70
22.47
Elgenvaluc Size
Figure 20: CIFAR-100 PreResNet1 10 150'th th epoch full dataspectrum
18

---

Under review as a conference paper at ICLR 2020
I SPECTRAL PLOTS- CIFAR-100 VGG16BN
The number of Parameters in the VGG 16 network is P = 15291300 so our augmentation procedure unable probe the limit The training procedure is identical the PreResNet except for an initial learning rate of 0.05 and T 300 epochs. Here we also see a reduction in both extremal eigenvalues.
Spedtrll Derett
20-2
20-4
1or4
10:4.
-6.59
-052
5.54
11.61
17.67
23.73
Figure 21: CIFAR-100 VGG16BN 300'th th epoch full dataspectrum
2014
20-1
20-4
5,321
Egennvalee
Figure 22: Augmented CIFAR-100 VGG16BN Eigenspectrum Epoch 300, 5 million samples and m 10 Lanezos steps
epoch Full Data Spectrum.pdf
107
Spectrl Dersty
20-9
Figure 23: CIFAR-100 100 VGGI6BN 0'th epoch full dataspectrum
107
Spertral Denety
20-3
-..95
2:110
2.786
Eiguniollae Size
Figure 24: CIFAR-100 VGG16BN 25'th epoch full dataspectrum
19

---

Under review as a conference paper at ICLR 2020
10"
2..7
Spectal
10:3
1014
20:4
-0.330
0.499
1.308
2.126
2.945
3.753
Esgannallo
Figure 25: CIFAR-100 VGGI6BN 50'th epoch full dataspectrum
Spectro Dee
2.03
20
-0.312
0.254
0.820
1.385
1.952
2.518
Figure 26: C10AR-100 VGGI6BN 75'th epoch full dataspectrum
Spectra Denelty
2.-4
20:9
20-9
-0.635
0.367
1.368
2.369
3.370
4.372
Elgenvaluc Size
Figure 27: CIFAR-100 VGG16BN 125'th epoch full dataspectrum
Spectral Deneity
10-2
20-4
10:4
-1.522
0.43
2.382
4.335
6.877
8.239
Eigenvalue Size
Figure 28: CIFAR-100 VGG16BN 150'th epoch full dataspectrum
10"
Spertral Denwity
10-2
20:9
20-0
-6.37
-0.0
5.17
30.93
36,70
22.47
Eigenvalue Size
Figure 29: 100 VGG16BN 150'th epoch full dataspectrum
SPECTRAL PLOTS CIFAR-10 10 PRERESNET
20
Spectted
10-4
10-0
-2.273
-3.736
0.802
2.340
3.878
5.416
Elgenvalue Size
Figure 30: CIFAR-10 PreResNet110 50'th epoch full dataspectrum
20

---

Under review as a conference paper at ICLR 2020
SpectniDre-hh
10-1
10:4
10-9
-3.03
-054
1.55
4.44
6.94
9.43
Eggenaalee
Figure 31: CIFAR-10 10 PreResNetl 10 300'th epoch full dataspectrum
K SPECTRAL PLOTS - CIFAR- 10 VGGI6BN
Spertal Devdta
1.
3,762
Figure 32: CIFAR-10 VGG16BN O'th epoch full dataspectrum
Specnal Deesty
10-2
20-4
-1.110
2.017
Eigenvaluc
Figure 33: CIFAR-10 10 VGGI6BN 300'th epoch full dataspectrum
21


Reviews:
[{"review_id": "S1eNmT16KH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper compares the true hessian and the empirical hessian of the loss function, showing the spectrum of the Empirical Hessian is generally broadened, and proposes a way to visualize the spectrum. The paper is well written with sound theoretical reasoning and empirical validation. However, the reviewer has the following concerns:\n\nAs to the assumption in this paper, it is too strong to assume independence between different elements of Hessian, Wigner ensemble seems to be a better model, since the only independence only comes from samples instead of the elements of the Hessian. This would require a completely different analysis to deal with.\nFurthermore, it seems that Lemma 1 and Theorem 1 are asymptotic results. I don’t see how these are related to the empirical validation, since in experiments the compared dataset are CIFAR-10/CIFAR-100 and augmented CIFAR-10/CIFAR-100, which only differs in the number of samples. It makes more sense to have a non-asymptotic analysis here.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HygJKX5cYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nIn this paper, the authors uses the random matrix theory to study the spectrum distribution of the empirical Hessian and true Hessian for deep learning, and proposed an efficient spectrum visualization methods. The results obtained in the paper can shed some lights on the understanding of existing optimization algorithms (e.g., first order methods).\n\nWhile this paper is quite interesting, I kind of feel that it has limited value to the research community due to the following concerns.\n\n1)\tThe work is based on some assumptions, which is however not very reasonable.  Assumptions 1 and 2 are too strong – it is difficult to know and to guarantee that the elements of \\epsilon are i.i.d. Gaussian distributed, and it is not guaranteed that the true Hessian is of low rank. I feel these assumptions are key to the proof, but they make the impact of the work lowers on practical situations where we have no knowledge and guarantee on the true Hessian and its relationship with the empirical Hessian. Although the authors made some discussions on generalizing the assumptions, it is unclear from the limited discussions whether the same theoretical results could be obtained in the generalized setting.\n\n2)\tThe experimental verification of the theoretical results is not indirect and somehow not very convincing. Because the true Hessian is hard to obtain, the authors compared the empirical Hessian with respect to different sizes of the training data as a proxy. However, this is not convincing since we do not know whether the same results can still be observed if further increasing the data scale, and which is the trend with respect to the increasing scale. A better way would be to design a simulation experiments, in which we know the data distribution (and thus can compute the true Hessian). \n\n3)\t The experiments were only done on the CIFAR datasets – not at large scale and not for diverse applications. So it is hard to generalize the experimental results to the entire space of “deep learning” (as indicated by the title). \n\n4)\tThe practical value of the work in not very clear to me. The authors only made limited discussions on this – it can be used to explain why first-order optimization algorithms work well in practice. However, this is what we already know. It would be much better if some practical guidelines can be derived which can improve (but not just explain) the optimization process of deep learning.\n\n**I read the author response, however, I do not think I am convinced to change my rating.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJev2S5DFH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nGenerally, 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.\n\nHowever, 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.\n\nLet me elaborate on my above comments in slightly more detail.\n\n\nOn the Theoretical analysis:\n\nThe 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). \n\nSome 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.\n\n\nOn the Empirical analysis:\n\nAs 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.\n\nAdditionally, 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.\n\nFinally, 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.\n\n\nOn the conclusions:\n\nOne 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.\n\n_____________\n\nOverall, 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.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all appreciated the importance of the topic: understanding the local geometry of loss surfaces of large models is viewed as critical to understand generalization and design better optimization methods.

However, reviewers also pointed out the strength of the assumptions and the limitations of the empirical study. Despite the claim that these assumptions are weaker than those made in prior work, this did not convince the reviewers that the conclusion could be applied to common loss landscapes.

I encourage the authors to address the points made by the reviewers and submit an updated version to a later conference.
Decision: Reject