An Investigation into Neural Net Optimization via Hessian Eigenvalue Density

“For our analysis, we study a variety of Resnet and VGG [26] architectures on both CIFAR-10 and ImageNet.”

“The original batch normalization paper [14] observed that the normalization parameters of BN, σ B and µ B , have to be computed (and back-propagated through) using the mini-batch.”

“We use Lanczos algorithm (Lanczos, 1950) (with full re-orthogonalization) to perform this computation in a numerically stable manner.”

“Examples of such work, where some surrogate is defined for the curvature, include the debate on flat vs sharp minima [16, 5, 29, 15], explanations of the efficacy of residual connections [19] and batch normalization [25], the construction of low-energy paths between different local minima [6],…”

“Finally, Li et al. [19] recently hypothesized that adding residual connections significantly smooths the optimization landscape, producing a series of compelling two-dimensional visualizations.”

“…include the debate on flat vs sharp minima [16, 5, 29, 15], explanations of the efficacy of residual connections [19] and batch normalization [25], the construction of low-energy paths between different local minima [6], qualitative studies and visualizations of the loss surface [11], and…”

“The algorithm we use is due to Golub and Welsch [10].”

“Examples of such work, where some surrogate is defined for the curvature, include the debate on flat vs sharp minima [16, 5, 29, 15], explanations of the efficacy of residual connections [19] and batch normalization [25], the construction of low-energy paths between different local minima [6],…”

“Scaling it to run on a 27 million parameter Inception V3 [27] on ImageNet (where we performed our largest scale experiments) requires a significant engineering effort.”

“This is in accordance with the ideas of Li et al. [18], who hypothesize that the loss surface has low intrinsic dimensionality, and also with results of Sagun et al. on toy models.”

“…Resnet-32 with no batch normalization, a small ball around 0 accounts for almost 50% of the total L 1 energy of the Hessian eigenvalues for a converged model (the L 1 reflects the loss function Thus to achieve successful optimization, we are forced to optimize these slowly converging directions 6 .”

“Examples of such work, where some surrogate is defined for the curvature, include the debate on flat vs sharp minima [16, 5, 29, 15], explanations of the efficacy of residual connections [19] and batch normalization [25], the construction of low-energy paths between different local minima [6], qualitative studies and…”

“Explicit representation of the Hessian matrix is infeasible when n is large, but using Pearlmutter’s trick [22] we are able to compute Hessian-vector products for any chosen vector.”

“Sagun et al. [23, 24] study the spectrum of the Hessian for small two-layer feed-forward networks.”

“It turns out that if the integrand were a polynomial g of degree d , with d small enough compared to m , it is possible to compute the integral exactly, Theorem 2.1 ([9] Chapter 6) .”

“Throughout the optimization, we observe that almost all of the gradient energy is concentrated in these outlier subspaces (Figure 11), reproducing an observation of Gur-Ari et al. [12] 7 .”

“…explanations of the efficacy of residual connections [19] and batch normalization [25], the construction of low-energy paths between different local minima [6], qualitative studies and visualizations of the loss surface [11], and characterization of the intrinsic dimensionality of the loss [18].”

“Sagun et al. [23, 24] study the spectrum of the Hessian for small two-layer feed-forward networks.”

“The underlying algorithm is extremely elegant, and has been known in the numerical analysis literature for decades (Bai et al., 1996) (based on foundational work by Golub and Welsch (1969)); here we introduce it to the machine learning community, and build (and release) a system to run it at modern deep learning scale.”

“Examples of such work, where some surrogate is defined for the curvature, include the debate on flat vs sharp minima [16, 5, 29, 15], explanations of the efficacy of residual connections [19] and batch normalization [25], the construction of low-energy paths between different local minima [6],…”

“Previous studies on the Hessian have focused on small models, or are limited to computing only a few eigenvalues [23, 24, 30].”

“There is an extensive literature regarding estimating the eigenvalues distribution of large matrices (for a small survey, see [20]).”

“There exists an extensive literature on bounding this error; [28] prove that under suitable conditions that where ρ > 1 .”

“We perform a thorough comparison of our work to the recent proposal of [2] in Appendix D. Batch Normalization (BN) [14] is one of the most influential innovations in optimizing deep neural networks as it substantially reduces the training time and the dependence of the training on initialization.”

“During the preparation of this paper, [21] appeared on Arxiv which briefly introduces the same spectrum estimation methodology and studies the Hessian on small subsamples of MNIST and CIFAR-10 at the end of the training.”

“The following lemma is one result on the concentration of quadratic forms: Lemma A.1 (Concentration of Quadratic Forms, [3]) .”

“Making this connection quantitative will require a characterization of the Hessian spectrum [Pap18, GKX19, GARD18].”

“Meanwhile, generally, we have x of Hessian matrix in deep networks are much smaller than one which is well observed in many works, e.g., fully connected networks, AlexNet, VGG and ResNet [49], [59], [60], [61] and our experimental results on ResNet50 and ViT-small in Fig.”

“Ghorbani et al. (2019) visualized the Hessian eigenvalue spectrum by using the Lanczos quadrature algorithm for full batch.”

“Ghorbani et al. [32] numerically found that for networks without BatchNorm, there are large isolated eigenvalues, while for networks with BatchNorm this phenomenon does not occur.”

“Moreover, the work of [9] measured the Hessian ESD, based on the stochastic Lanczos”

“[73] used stochastic Lanczos quadrature algorithm to estimate the spectrum density for large-scale problems such as 32-layer ResNet on ImageNet.”

“[73] Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao,”

“The established interpretation for this phenomenon attributes it to a poorly scaled loss function J , which results in an ill-conditioned Hessian matrix hess( J ) close to the minimum [18, 19, 20].”

“These results have been largely confirmed in large scale studies (Ghorbani et al., 2019), but note they depend to some extent on architecture and (absence of) batch normalization (Ioffe & Szegedy, 2015).”

“Previous work has studied either variations of the weights (13) or the landscape of the loss function (7, 17) but not the strong relation between the two that is discovered here.”

“am matrix to study convergence in neural network empirical loss. Pennington & Worah (2017) study the concentration properties of a similar covariance matrix formed from the output of the network. Ghorbani et al. (2019) investigate the Hessian eigenspectrum and Papyan (2019) show how it is related to the gradient c…”

“Here, we consider eigenanalysis of the Hessian, which provides a powerful tool for studying various aspects of deep neural networks [59, 60, 61, 62].”

“However, in the context of deep neural networks, the eigenvalue with the smallest absolute value of the Hessian matrix is almost zero, which renders the computation of the condition number both algorithmically and numerically unstable [15].”

“Afterward, several papers [13], [14] further uncovered that BN is beneficial to improving the Hessian conditioning, which can help to accelerate the convergence.”

“…Finally, our precise characterization of the behavior of the sharpness during full-batch gradient descent adds to a growing body of work that empirically investigates the Hessian spectrum of neural networks (Sagun et al., 2017; Ghorbani et al., 2019; Li et al., 2020a; Papyan, 2018; 2019; 2020).”

“Ghorbani et al. (2019) show that without batch normalization, mini-batch gradients are largely contained in the subspace spanned by the top eigenvectors of noncentered K .”

“By the definition of MRC, for any weights ( θ ′ − θ ) ∈ C θ , we have: Thus, for the optimized weights: it satisfies Such that the proof ends.”

“Large eigenvalues can impede neural network training [12].”

“This closely matches the estimated eigenspectrum of the Hessian of a convolutional network (see Figure 9 and Appendix E.4), and is also consistent with recent work finding heavy tailed eigenspectra of neural network Hessians [Ubaru et al., 2017, Ghorbani et al., 2019].”

“A key term in Equation 24 is the overlap between the eigenvectors and the stochastic gradient, shown to be large in practice (Ghorbani et al., 2019; Gur-Ari et al., 2018).”

“Furthermore, some differences in the convergence behavior can be explained by looking at the spectrum of the Hessian of the objective function (Ghorbani, Krishnan, and Xiao 2019; Sagun et al. 2018; Yao et al. 2018).”

“, [94] and [95], that attempted to understand the Hessian matrices of NNs.”

“Similarly, the empirical observations of Papyan (2018), Sagun et al. (2017), and Ghorbani et al. (2019) demonstrate that even for extremely wide neural networks, the Hessian is not constant through training.”

“Recent research [29, 30, 2, 7], consistent with our own observations, show that the exact Hessian after training is rarely positive definite in deep learning.”

“These specifically corresponds to the contributions associated with the maximally nonlinear point of the parameter path, corresponding to the largest (positive or negative) eigenvalues of the Hessian of the predictor function [21].”

“Another challenge comes from recent experimental studies of deep neural network Hessians [Pap18; GKX19; Gra20; Gra+19] which reveal spectra with several large outliers and considerable rank degeneracy, deviating significantly from the Gaussian Orthogonal Ensemble semi-circle law implied by a spin…”

“This argument has been further investigated by computing the spectrum of the Hessian for a large-scale dataset [13].”

“A similar phenomenon may explain why normalization helps smoothing the loss surface and speed up training (Santurkar et al., 2018; Ghorbani et al., 2019).”

“We extend the NTK analysis by examining the maximum eigenvalue of the Hessian matrix H to analyze the convergence behavior of the models [72, 73, 74, 75, 76, 77].”

“Recent works have observed this phenomenon in small networks [7, 8, 9], as well as large networks [10, 11].”

“Numerous works studying the spectrum of the Hessian on neural networks have found that this spectrum shares many characteristics with the limiting spectral distributions discussed below including compact support, a concentration of eigenvalues near 0, and a stable top eigenvalue [Behrooz et al., 2019, Dauphin et al.,…”

“Many researchers believe that such spectral features, once better understood, will provide clues to improvements in deep learning training or classifier performance (LeCun et al., 1998; Dauphin et al., 2014; Sagun et al., 2016, 2017; Gur-Ari et al., 2018; Ghorbani et al., 2019; Yao et al., 2019).”

“Prior work [40, 59, 36] focusing on the Hessian empirical spectral density has utilised fast Hessian vector products [62] in conjunction with Lanczos [57] methods.”

“However, in the context of deep learning, the conditioning analysis suffers from several barriers: 1) the model is over-parameterized and whether the direction with respect to small/zero eigenvalues contributes to the optimization progress is unclear [38,35]; 2) the memory and computational costs are extremely high [3…”

“In the case of neural network training, we observed clustering of the Hessian spectrum in our numerical experiments, in agreement with other numerical experiments [2, 11, 35].”

“Outliers are extensively empirically observed [41, 42, 20, 48, 49].”

“5.2 except for the parameter sensitivity analysis section, where we carefully tuned the values of α and T to show their effect on the learning performance.”

“Such a coarser channel-wise normalization might in turn lead to a less effective use of model capacity and a degradation of the conditioning of the loss landscape [62, 64].”

“In deep learning, information on how the spectrum of a weight matrix differs from its random initialization can give hints about model convergence and generalization [PSG18, MM19], and Hessian eigenvalues are useful in optimization [GKX19].”

“The framework of calculating the loss value with varying magnitude of disturbance on the best pretrained weight is shown in Algorithm To further investigate local flatness and convergence properties, a qualitative analysis using the maximum eigenvalue of the Hessian is necessary [69].”

“…several interesting phenomena of the Hessian, e.g., the gradient during training converges to the top eigenspace of Hessian (Gur-Ari et al., 2018; Ghorbani et al., 2019), and the eigenspectrum of Hessian contains a “spike” which has about c − 1 large eigenvalues and a continuous “bulk” (Sagun et…”

“, 2020), but the areas around critical points may be unusually flat, with the bulk of Hessian eigenvalues near 0, and only a few larger outliers (Ghorbani et al., 2019), meaning that many local minima are actually connected within a single basin of attraction (Sagun et al.”

“Empirically, small negative eigenvalues arise even with small training loss, which seems to indicate that the model is at a saddle point instead of a minimum (Sagun et al., 2017b; Ghorbani et al., 2019).”

“The study of spectral properties of these very large models is made possible thanks to improved tools (Ghorbani et al., 2019) and more precise theoretical models (Jacot et al., 2019; Pennington & Worah, 2017).”

“A quantity that will control the speed of convergence of SGD will be the ratio between the curvature due to the signal component and the maximum curvature of the noise ζ(`) = (2)m(2)[`]/σ(2) max(m(2)) [29].”

“The distorted shape of the eigenvalue spectrum is consistent with empirical reports (LeCun et al., 1998; Sagun et al., 2017; Papyan, 2019; Ghorbani et al., 2019).”

“Sagun et al. [40], Papyan [41], Ghorbani et al. [42] demonstrated the spectrum has a bulk of values near zero plus a small number of larger outliers.”

“The distorted shape of the eigenvalue spectrum is consistent with empirical reports (LeCun et al., 1998; Sagun et al., 2017; Papyan, 2019; Ghorbani et al., 2019).”

“Multiple papers studying the Hessian in neural network training objectives (Chaudhari et al., 2017; Papyan, 2018; Ghorbani et al., 2019; Li et al., 2019) find that the spectrum is dominated by a small number of outlier eigenvalues that far exceed the bulk of eigenvalues, which are concentrated close…”

“It has been well established that increasing model and dataset complexity increases the largest eigenvalue of the Hessian of the loss function [14, 15].”

“However, neural network Hessians are generally singular, especially in the overparameterized case [44, 18], meaning the kernel is non-trivial, and so neither class of methods can guarantee convergence to critical points.”

“Some machine-learning algorithms use the Hessian of the error function to optimize backpropagation itself, allowing for both more efficient and effective training (for one example, see [30, 43]).”

“…dependence on small eigenvalue directions by computing ‖P (θt+1 − θt)‖2/‖(θt+1 − θt)‖2, where P is a projection onto eigenvectors associated with the largest (in absolute value) 10 eigenvalues and θt represents the model parameters at iteration t (a method proposed in (Ghorbani et al., 2019)).”

“1 More generally, studies investigating the loss’s Hessian spectrum can be traced back to (Bourrely, 1989; Bottou, 1991) with a number of follow-up works (LeCun et al., 2012; Sagun et al., 2016, 2017; Yao et al., 2018; Ghorbani et al., 2019; Yuan et al., 2019).”

“In machine learning literature, it has been shown that the spectrum of the Hessians of neural networks share many characteristics with the limiting spectral distributions found in classical random matrix theory (Dauphin et al., 2014; Papyan, 2018; Sagun et al., 2016; Behrooz et al., 2019; Martin and Mahoney, 2018).”

“Despite much recent work [3, 22, 9, 28], it is still not completely understood how normalization influences the training process.”

“This is contrary to the generally accepted narrative that Batch Normalization improves the smoothness of the loss surface [6, 26], though not without precedent as Yang et al. [32] demonstrates settings for which Batch Normalization can cause exploding gradients.”

“, more concentrated on small eigenvalues) represents flatter slopes around in the loss landscape [89], we follow [89], [90] to estimate the Hessian spectrum of the minima using the Lanczos”

“Through out this paper, we largely follow the notation of [17], using the stochastic Lanczos quadrature algorithm.”

“…of thousands of random vectors to guarantee a reasonable guarantee on fractional error (Granziol et al., 2018b) with authors typically using a vastly reduced number of random vectors in practice (Granziol et al., 2019; 2018b;a; Granziol & Roberts, 2017; Papyan, 2018; Ghorbani et al., 2019).”

“9 can be considered the approximation of the Hessian function obtained via random sampling.”

“Solving for k we have, 2 ln( ρ/ 2) = 1 + ρ 2 / 8 σ 2 + ln(4) − ln( c ( ρ 2 − 1)) 2 ln( ρ ) If σ 2 = 10 − 5 as suggested in (Ghorbani et al., 2019), then k must be exceedingly large for the bound to provide any meaningful convergence gurantee; even for an extremely weak bound of c = 1 / 2 , we…”

“…matrix A (2.6) and plot its normalized eigenvalues in Figure 3 (left) to observe that most of the eigenvalues are clustered near zero, in accordance with the fact that Hessians (which are correlated with A ) for neural networks have a large number of (near) zero eigenvalues (Ghorbani et al., 2019).”

“Additionally, Hessian information has been used widely to give improved algorithms and better understand model performance [18, 44].”

“That subspace, spanned by the logit gradients, intersects with the top-C eigenvectors of the Hessian [4, 7].”

“Dissecting the properties of the Hessian by Eigenanalysis allows us to gain useful insights about the behavior of neural networks (Erichson et al., 2021, Ghorbani et al., 2019, Hochreiter and Schmidhuber, 1997, Lechner and Hasani, 2020, Sagun et al., 2017).”

“Since ∇ f ( w (cid:63) ) ≈ 0 , the Hessian ∇ 2 (cid:96) ( w (cid:63) ) has multiple nearly zero eigenvalues [25, 26].”

“Other popular applications of implicit trace estimation include counting triangles and computing the Estrada Index in graphs [4, 5], approximating the generalized rank of a matrix [6], and studying non-convex loss landscapes from the Hessian matrix of large neural networks (NNs) [7, 8].”

“In this case the input vector is and the output , which is a one-hot vector, with all components equal to 0 except a single component if and only if k is the correct class label for input x . k y Consider a L -layer fully connected network with ReLU activation function after each linear layer.”

“By integrating these perspectives, our framework provides actionable insights for model design, optimization, and generalization, applicable to tasks such as image classification and regression (Sagun et al., 2017; Ghorbani et al., 2019).”

“Although [34] made use of the Hessian matrix of the loss function to understand the dynamics of neural network optimization, and deeply researched into the eigenvalues of the Hessian, the research results are not yet implemented in a real-world case study.”