Analytic Insights into Structure and Rank of Neural Network Hessian Maps
Authors: Sidak Pal Singh
Gregor Bachmann
Thomas Hofmann
Venue: NeurIPS 2021 Poster (2021)
Keywords: hessian
rank
neural networks
overparameterization
degeneracy
singularity
loss landscape
degrees of freedom

Abstract: The Hessian of a neural network captures parameter interactions through second-order derivatives of the loss. It is a fundamental object of study, closely tied to various problems in deep learning, including model design, optimization, and generalization. Most prior work has been empirical, typically focusing on low-rank approximations and heuristics that are blind to the network structure.  In contrast, we develop theoretical tools to analyze the range of the Hessian map, which provide us with a precise understanding of its rank deficiency and the structural reasons behind it. This yields exact formulas and tight upper bounds for the Hessian rank of deep linear networks --- allowing for an elegant interpretation in terms of rank deficiency. Moreover, we demonstrate that our bounds remain faithful as an estimate of the numerical Hessian rank, for a larger class of models such as rectified and hyperbolic tangent networks. Further, we also investigate the implications of model architecture (e.g.~width, depth, bias) on the rank deficiency. Overall, our work provides novel insights into the source and extent of redundancy in overparameterized neural networks.

Analytic Insights into Structure and Rank of Neural Network Hessian Maps
Sidak Pal Singh*
Gregor Bachmann"* and Thomas Hofmann
ETH Zürich
Max Planck ETH Center for Learning Systems
Abstract
The Hessian a neural network captures parameter interactions through second- order derivatives of the loss. It is fundamental object of study, closely tied to various problems in deep learning, including model design, optimization, and generalization. Most prior work has been empirical, typically focusing low-rank approximations and heuristics that are blind to the network structure. In contrast, we develop theoretical tools to analyze the range of the Hessian map, which provide us with a precise understanding of its rank deficiency and the structural reasons behind it. This yields exact formulas and tight upper bounds for the Hessian rank of deep linear networks - allowing for an elegant interpretation in terms of rank deficiency. Moreover, we demonstrate that our bounds remain faithful as an estimate of the numerical Hessian rank, for a larger class of models such rectified and hyperbolic tangent networks. Further, we also investigate the implications of model architecture (e.g. width, depth, bias) on the rank deficiency. Overall, our work provides novel insights into the source and extent of redundancy in overparameterized neural networks.
Introduction
Since the very infancy of neural networks, the Hessian matrix has been a central object of study. This is because the Hessian captures pairwise interactions of parameters via second-order derivatives of the loss function. As result, the Hessian was productively employed, for instance, (quasi- Newton) optimization methods [1, 2], model design and pruning [3-5], generalization [6], network calibration [7], automatically tuning hyper-parameters [8]. But, from outset the main practical challenge has been its size, scaling quadratically with the model dimensionality. This makes the problem severe for today's 's DNNs which have millions or even billions of parameters [9, 10].
Consequently, most prior work has focused on designing scalable Hessian approximations, which either take the route of Hessian-vector products (R-operator) [11-13] or employ positive definite without
approximations by appealing to the Fisher information matrix. Additional approximations exception are needed on top, such as diagonal approximations [3. 14] the former or K-FAC [15- 17], restricted to layerwise or arbitrary blocks on the diagonal [18-20]. in the latter.
"Detailed list of contributions holds experimentally high fidelity, thus kick-starting the project. Sidak came up with the proof technique and proved Thcorems 3, 9, 12. Sidak wrote essentially the entire paper and noted the rank-deficiency interpretation. Gregor proved Lemma 8, assisted in a part of Theorem 3, empirically observed the eventual formula for the Hessian rank, and essentially ran all the experiments for the final submission and made the corresponding figures. Correspondence sidak. singh@inf.... ethz. ch.
Sidak first discovered that the Hessian rank formula, in carly form,
'The most recent version of our paper can he found at https: /ttp////xvvvvv////a//ee/e//ae wtrg/abs/21000 16225 and the code corresponding to the experiments is located at https: /tttts::/gitee //github. http//aaaabbhhhaiieee rank.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The goal of this paper is to advance the analytical understanding of the Hessian map of neural network. We pursue the fundamental question of how the model architecture induces structural properties of the Hessian. In particular, we analyze the dimension of its range (i.e., the rank) and identify the sourees of rank deficiency. Understanding the range of the Hessian map, in turn, delivers insights into the important aspect of how gradients change between iterations.
A reason why such an important direction currendy re- mains sidelined is that non-linearities in a neural network result in an increased dependence on the data distribution, making a suitable theoretical analysis seem intractable, Following Saxe al. [21]. Kawaguchi [22], who deliv-
120
1391
ered useful general insights on neural networks by looking at the linear case, we take a step back and rigorously char- acterize the range of the Hessian map and determine the resultant rank deficiency for deep linear networks. The key result of our paper is exact formula along with tight upper bound on the rank of the Hessian - which effectively depend the sum of hidden-layer widths. This stands opposed to the total number of parameters which proportional to the sum of squared layer widths, thus implying a significant redundancy in the parameterization of neural networks (see Fig. 1).
-20
Figure 1: Hessian spectrum of linear and ReLU networks at initialization. Dashed lines indicate our rank predictions. Results have heen averaged over 3 runs.
The exact quantification of the Hessian rank gives a precise yet interpretable ballpark on the inherent complexity of neural networks since rank naturally measures the effective number of parameters (as best illustrated by the case of a quadratic minimization problem). This relationship is further reinforced by connection to the classical complexity measure of Gull [23], MacKay [24], which equivalent to rank for a sufficiently small constant controlling the prior. Therefore, this sheds a novel perspective on the nature and degree of overparameterizztion in neural networks, and opens up interesting avenues for future investigation.
Contributions. The main contributions of our paper can be summarized as follows: (i) Section 3: We characterize the structure of the Hessian range by exhibiting it via matrix derivatives. (ii) Section 4: We prove tight upper bounds and provide exact formulas on the Hessian rank that are neatly interpretable. To the best of our knowledge, this is the very first time that such formulas and bounds are made available for neural networks. (iii) Section 5.2: In the non- non-linear case, we show that our (linear) rank formulae faithfully capture the numerical rank. (iv) Section 6: We demonstrate via experiments and theory that such rank bounds also hold throughout the course of training. (v) Section 7.1: In the non-linear case, we also provide pessimistic yet non-trivial bound, which provably establishes degeneracy of the Hessian at the minimum. (vi) Section 7.2, 5.1: We extend our rank results to the case of bias and investigate the effects of architectural components (such as width, depth, bias) on rank. (vii) Appendix S8: As a by-produce our analysis also reveals interesting properties of the Hessian spectrum, and we prove the presence of additional redundancies due repeated eigenvalue plateaus.
Related work. The study of the Hessian, in recent times, has been re-invigorated by the empirical observations of Sagun et al. [25, 26] who noted a high degree of degeneracy experimentally, and characterized the spectrum as being composed of a bulk around zero and few outlier eigenvalues. Since then, works such as [27, 28] have scaled the empirical analysis to bigger networks via efficient spectral density calculations and better explained the observations in [26]. However, drawback is that due to their empirical nature, it remains hard to uncover the exact level of degeneracy via these methods [29], and neither the exact factors that affect the rank deficiency discerned. Another approach has been to fit models from random matrix theory to match the observed Hessian spectrum in neural networks [29, 30J. however, such methods do not properly capture the sharp peak at zero observed in empirical spectra [31]. Yet others have investigated the properties of the spectrum in the asymptotic C regime [32, 33]. but the bounds, if any, are quite coarse (see Fig. 4). Moreover, a common issue underlying most of these approaches that they are blind to the layerwise compositional structure of neural networks, and are often motivated by a black-box decomposition of the Hessian.
In regards to indicating the parameter redundancy neural networks, we are far from being the first work. Prior empirical studies have long reported similar observations, like in the form

---

of, post-training pruning [3, 4, 19, 20, 34] or inherently contained sub-networks (Lottery Ticket
Hypothesis [35]) or intrinsic dimension of the loss landscape [36]. Recently [37] have experimentally
argued for the effective dimensionality from [23, 24] to be good predictor of double descent [38].
Nevertheless, determining the precise extent of redundancy - and showing it provably - well as the structural reasons behind it have remained illusory in such approaches.
2 Setup and Formalism
We use the shorthand, W to refer to the matrix product chain W W when k > L. When k < I, W will stand for the transposed product chain W ... w Besides, denotes the Kronecker product of two matrices, vec, indicates the row-wise vectorization of matrices, rk refers to the rank of matrix, and I is the identity matrix of size k x k.
General notation.
Deep Neural Networks (DNNs). A feedforward DNN is composition of maps, i.c., F F o o F1, where the 1-th layer map F' RM-1 + RM, with imput dimension := Mo. output dimension K := Mr. total number of hidden neurons M := Ei=l Mr. Each layer map is parameterized by weight matrix W' and applies an elementwise activation function of. So we have,
='=o' W with W MRMM and a' IR R.
For the sake of tractability, will often investigate linear DNNs where a' = id, and F(x) WLi1x. For compactness, we also represent the entire set of parameters by 0 == (W1 ... W and where emphasis requires, will subscript the DNN map F with it and write Fg.
Next, assume that we are given a dataset S {(x, y: yi) of /V input-output pairs, drawn i.i.d from an underlying distribution Px.y. Our focus will be on the squared loss (MSE), y (0) lly y1? y
and its residual 6x.y
06x,x where ý Fx is the DNN prediction. The population dy
82
loss, L is: (()) = E pxy 1 Finally, we will analyze the Hessian matrix H 00 ae
Backpropagation in matrix derivatives. As all parameters collected into matrices, often work with matrix-matris derivatives by vectorizing row-wise in the numerator (Jacobian) layout, i.e.
OY
① vec, (Y)
see [39] and Appendix S2.5. Alongside this, we use the following rule:
OX
vec, (X)
0AWB
OF WLi++ 8 x T Tiik-1 E K
8 B egg.
(I)
dw
OWk
By the usual chain rule (backpropagation) one has for a linear DNN, at a sample (x, y):
dlx,y
W 5x.
1:1 x
W WL1 xxT - -yx W
(2)
OW
backward ER Mrg
forward ER
The above gradient with respect to W is first order W itself and second order in the other weight matrices. Lastly, let us setup the following shorthand, Ω E [6x.y x E 1 xx" yx
Σxx = E xx I] and Eyx E [yyx"] which we will use throughout the paper.
3 Hessian Maps of Linear DNNs
3.1 Hessian structure
The Hessian map has natural block structure defined by the layers and their dimensionality. In order to leverage this structure, we directly take the derivative of the loss gradient matrix-by-matrii fashion. First, consider the k-th diagonal block of the Hessian, which is independent of y and is given by,
PC
H kk
W
W Exx 1
OW
This follows from the matrix-derivatin rule in Eq. (1) along with the Eq. (2) and taking expectation. The calculation of the off-diagonal Hessian blocks (kl-th block of size Mj M x M, Mi-1)
3

---

involves the product rule. Note that the two occurrences of a weight matrix W in Eq. (2), are once non-transe con-transposed (in W xxx and once transposed (in W W respectively for k or k > 1). For simplicity, let us express these parts without adding them and directly write the other Hessian contribution with respect to the transposed matrix, giving:
8C
44 1
H2
W 1a++1
W
E Exx W
(3)
OWO
SC
kk < H
= W
W E
Ω W
T
w1++1
(4)
OW
OW
0 L
A
H
Whi Ω OW
W
(5)
oW OW
Equivalence to Gauss-Newton Decomposition. A common approach is to look at the Hessian map from the perspective of the Hessian chain rule, where we have that, H = H. + Hy. with
K
H.- = E Pxiy (x)
[xbx)] Vo and Hj
E Px.y
10lxyle V Fo(())
For the MSE loss, the Gauss-Newton decomposition fact equivalent to what we discussed before (see details in Appendix S1), where H, contains the blocks H and H while H2 consists of H (although with the non-transposed matrix). Henceforth, will refer to the first term H, the outer-product Hessian, while we coin the second-term y as the functional Hessian.
3.2 Range of the Hessian map
Assuming local Taylor-scries approximation of the loss' gradient, we have that for ||00|| Ve+ C Re V A0. This indicates how the gradients will change over any local perturbation AO. Also, this holds over successive iterations of an optimization algorithm such gradient descent. As a result, this serves to show the significance of the Hessian range as since its dimension (i.e., rank) will dictate the dimension of the space where gradients evolve something which has been discussed only empirically before [40].
Moving to best highlight the layer-wise structure present in the Hessian range, let us multiply the two parts of the Hessian with a vector A0, which we decompose as Ae (vec,(AW!) ... (AW
Range of the outer-product H. The product of the k-th row-block H cor- responding to the 1t layer, with AO can be written succinetly as, H A0 vec, (W++1:L, A Exx Wi:-1), where Á EL WL++1 AWI wi-11 Rxd This es- sentially follows from the identity, vec, AXB (A @ BT) vec, X (see proof in Appendix $2.5). Note that A represents the net change on the prediction map induced by changes to the weight matrices the forward pass. We see that: (1) A0 is linearly compressed into highly interpretable matrix A with Kd entries. (2) The same compressed A is shared across all result blocks as it is independent of the row block index Overall, this already hints that there is a significant intrinsic structure in the Hessian that constrains its range.
Range of the functional Hessian H, AO except that consider AW! instead of AW Then the product corresponding to t layer is, H AO = vec, (W++I:L 2 A skj + [A>$]T 52 w where < := I W1+1 AW W1-1:1 and A A>* Et WL++1 AW' wi-1k++ Notice that the range of H, is also inherently constrained like in the case of H but there are two important differ- ences. First, the data dependent part is now the covariance Ω = E [ōx.y _T]. Clearly, if this matrix is low rank (say 8), this will directly impact the rank Hy. The other significant difference is that the weight matrix product is split at layer h: This reflects the fact that upstream and downstream layers have a different effect. We will see ahead that these factors will neatly gives rise to a dependence on the sum of hidden-layer widths.
Here we multiply with Ao, which similar to

---

4 Main result: Analysis of the Hessian rank
Preliminaries. Let denote the rank of the uncentered covariance Σxx E [ by If r < d, then without loss of generality, consider Σxx := (Exx) rxr, which is always possible by pre-processing the input. Thus, Σxx O, always. Also, in such case, we take W RM,x xr Further, the only assumption we make in our analysis is AI, which is in fact guaranteed at typical initialization almost surely (c.f. Appendix S2.6). In Section 6, we see what happens while training.
Assumption A1. Maximal Rank: VI E [L], W E MR has rank equal to min(M,, M1-).
Lastly, the omitted proof's in the coming subsections are located in Appendices S2, S3, S4 respectively,
4.1 Analytical tool
The key idea of our analysis technique is to reduce the rank of involved matrices the rank of certain special kind of matrix (or its variant), Z, as shown below:
L D
Z
with C E RRxx DE RPX.
(6)
I,
This row-partitioned matrix has characteristic structure, where an identity matrix alternates between the two sides of the Kronecker product. Such matrices are in fact omnipresent in the Hessian structure, and importantly for our purpose, they possess additional properties properties and our analysis, is the use of generalized inverse [41] and oblique (non-orthogonal) projector matrices. The following Lemma from [42] details such result:
their rank. Inherent to these
Lemma 1, Let Z be a matrix as in Eq. (6). Then, rk(Z) = rk (C) + n rk(D) - rk(C) rk(D).
4.2 Rank of the outer-product Hessian
Consider the following decomposition of Ho, which reveals its 'outer-product nature: where B, = Ix & Exx E kdxkd, I Wlit-1) E RRdxp
Proposition 2. For deep linear network, =, WLi+1 @ Wii-1
and A (WL22 Ia
where p is the number of parameters. A straightforward consequence is that if there is bottleneck in between, i.e., hidden-layer with width M, min(K, d), then the matrix B, will control the rank of H,. Hence, as a first upper bound we get, rk(H.) min (rk(A.))rk(BB) = rk(..) rk(Ix) rk(Exx)=Kr.
Such a decomposition is however not new (see [43]), but this only forms an initial step of our analysis and the current bound can be loose in the bottleneck case (e.g., auto-encoder). Let define the minimum dimension to be beq = min(r, M,, MM-1, K). Our main theorem can then be stated as:
Theorem 3. Consider the matrix A, mentioned in Proposition 2. Under the assumption Al, rk(A.) (rrk(W2:)) + K (W 111) rk( rk(w2:1) rk( WW1-11) = (r
q)
Now, from Theorem 3, it is evident that we can simply upper bound the rank of Ho, by the rank of A. But actually, it is possible to show an equality (using Lemma 18), as described below:
Corollary 4. Under the setup of Theorem the rank of H, given by rk rk(H.) = q (r + q)
Remark. It should be emphasized that this analysis not only delivers the rank of the outer-product Hessian but also of Neural Tangent Kernel [44] (see Appendix S9.5), Fisher information matrix, network Jacobian, due to their underlying intimate relationship, unaltered through the lens of rank.
4.3 Rank of the functional Hessian
For analyzing the rank of the functional Hessian H y, we will continue operating by having one of the derivatives with respect to a transposed weight matrix (here, W ), since rank does not change with column or row permutations. We denote this modification of the functional Hessian by Hy. Then from Eqs. (4. 5). we can observe that there is a common structure within the blocks contained in the column I. Namely, all the weight matrix-chain have either / - 1 or / + 1 as their right indices. So our approach will be to bound the rank of the individual column blocks, as formalized below:
5

---

Theorem 5. For a deep linear network, the rank l- column-block, Hy. ofthe the matrix f. under
the assumption Al is given as rk(H)) q M q Mi- q² for 1 [ ,L- 11. When I 1. we have rk HH)) = q M1 + qqs -222...02 32nd when 1 = L. we have rk / = - + qs g². Here, q =- min(r, ,, M,..... M K, min(q, s) and
rk( (1 1).
The upper bound on the rank of H follows by combining the above result over all the columns: Corollary 6. Under the setup of Theorem 5, the rank of H2 can be upper bounded as, rk(H,) & M + - - LQ where M - M,.
Although the above result is an upper bound, empirically this is precisely the formula at initialization, and thus we have the rightest upper bound on the rank of the functional Hessian. Besides, general, we find that at initialization s = min(r, K), hence 7 = q and we will just use q hereafter for simplicity,
Block-column independence. A surprising element of the above analysis is that just adding the ranks of the block-columns, corresponding to the respective layers, gives the rank of the entire H, which is tight. This phenomenon quite straightforward to see in a 2-layer network and there Corollary 6 is an equality. However, the more interesting observation is that this holds even for arbitrary depth and also extends to networks with non- mon-riinesssiess such as ReLU and Tanh. This implies that the column spaces associated with the layerwise block-columns do not overlap. Thus. H2 is similar a block diagonal matrix, and it should be possible to uncover the similarity transformation. But this is beyond the current scope, and we leave it as an open question.
4.4 Overall bound on the Hessian Rank
Finally, in order get an upper bound on the rank of the entire Hessian, we simply use rk A + B) S rk(A) + rk(B), along with the Corollary 4 and Corollary 6 (with q 9 as noted above), to obtain:
rk(Hc) S rk(H,) + rk(H,) S 2 L + 2 q + q (r + K K- q)
24 M l.q² q(r + K) Fact 7. The following equality holds empirically: rk rk(Hz))
This implies that our upper bound is off by just a constant additive factor of 2gs q2, which is another startling finding. Thus, revealing that the intersection of the H., H column spaces has s, then our upper bound
rather small dimension. E.g., take the typical case of no bottlenecks, exceeds the true rank by a small constant q², i.e., minimum dimension squared. This suggests that the direct sum of their column spaces is not too far-fetched as an approximation to the column space of H.. Previously, [30] empirically noted a similar observation for 1-hidden layer networks and [33] showed high degree of mutual orthogonality in the asymptotic regime. Our result shows similar consequence in the finite case.
Alternative interpretation. Besides the above result, that the rank of the Hessian is proportional to the sum of widths, there is an alternate way of viewing this. Let us calculate the rank deficiency in the network when (uncentered) input-covariance has rank, i.e., = d. Using Fact. (7) this comes
out to rank dankiieficiincyyHE.. (Hc) = Σ (M, (M++1 - q), whereas the number of parameters is ==0
equal to p ΣE= M, M,+1. Hence this lends an elegant interpretation to our formula, whereby the amount of rank deficiency is equal to the number of parameters of a hypothetical network whose all layers have been subtracted by the minimum layer-width of the original network.
4.5 Hessian Rank as effective # of parameters
Consider a quadratic optimization problem, argminge Ry 0 MO, where assume the matrix M has a reduced rank < p and is in rank normal form, M but reduced problem argming, ERr 0, M, 0, of size < p. where 0,, is the vector containing the first r parameters. More generally, we can reparameterize ~ UT where U contains the (top-r) eigenvectors of M. Thus, here it is strikingly clear that rank provides the effective number of parameters. Further, we can go to the case of neural networks by simply utilizing the 2nd order Taylor series expansion of the loss -- and the Hessian He plays the role of M. Overall, this suggests that the above results on the Hessian rank can provide insights into the effective # of parameters in neural networks, or in other words, into the inherent complexity of neural networks.
[M; 0). As a result, we get an equivalent

---

5 Empirical Results
5.1 Verification of Rank formulas and their behaviour
(a) Rank vs samples N
(b) Rank vs minimal width M.
minimal width M.
paraams
Figure 2: Behaviour of rank and rank/#params on CIFARIO using MSE, with hidden layers: 50, 20, 20, 20 (Fig. 2a) and Ma, M. (Fig. 2h, 2c). The lines indicate the value and circles denote formula predictions.
Setup. We test our results on a variety of datasets: MNIST [45], FaSHionMNIST [46]. CIFARIO [47]; for various loss rypes: MSE, cross-entropy. cosh; across several initialization schemes: Glorot [48], uniform, orthogonal [21]. Our theory extends to all these settings. However, due to space constraints we only show a subset of experiments here, but the rest can be found in the Appendix $9.
Procedure. To verify the prediction of our theoretical results, we perform an exact calculation of the rank by computing the full Hessian and the corresponding singular value decomposition (SVD). The available iterative schemes for rank approximation (c.f. [49]), although more memory-efficiee are only effective for well-separated spectra and thus cannot provide useful approximations in the case of neural network Hessians. Besides the exact Hessian computation, we also utilize FLOAT- 64 precision to ensure 'true' rank calculation, resulting in increased memory costs. Hence, we downscale the image resolution to d = 64 to test on more realistic networks.
Results. We study how the rank varies function of the sample size N and the network architecture (for varying widths). Fig. shows this for a linear network on CIFAR10 10 with MSE loss. First, in Fig 2a, observe that predictions match the true rank exactly across all sample sizes as the dependence on is only exhibited in the rank of the empirical covariance Exx, confirming that rank is largely a distributiooniindeeedden quantity. So, for the rest of our experiments, we sufficiently subsample to ensure that the empirical and true covariance have the same rank. Next, in Fig. 2b, we see that our rank formulas hold for arbitrary-sized network architectures. To contextualize the growth of rank with increasing width, in Fig. 2c, we normalize it by # params p. We notice that rank/# params, which intuitively captures the fraction of effective parameters, saturates down to small level - signalling the extent of redundancy present in the network parameterization (similar plots across depth and simulation of rank/# params larger settings can be found in $9.1, S9.2).
5.2 The case of non-linearities
Although the linear nature of the neural network was crucial our analysis, in this section we show experimentally that our results also extend to the non-linear setting - as numerical rank [50].
1.0
Figure 3: Spectrum of the loss Hessian Hr (left), functional Hessian Hj (middle) and outer product H., (right), for linear and non-linear networks. Black dashed lines are the predictions of the bulk size via our rank formulas. We use 2 hidden layers of size 30, 20 with Tanh activation on MNIST.
7

---

Visual comparison of the Hessian spectra. Let us first understand how non- con-lineassties affect the Hessian spectrum relative the spectrum of linear networks. Fig. 3 compares the spectra of H Hy, H, in these two scenarios (linear vs Tanh), with a zoomed-in inset near the cut-off obtained from rank formulas corresponding to the linear case. We can observe the presence of numerous tiny, but not exactly zero, eigenvalues in the non-linear case. So, if we were to measure the rank with threshold up to machine precision - as we did in the linear case -ase--tie this would result in an inflation of the rank measurement for the non-linear scenario. From practical point of view, tiny but non-zero eigenvalues hold little significance, so a more relevant quantity is the numerical rank [50] that uses a reasonable threshold to weed out such extraneous eigenvalues. The numerical rank, altermatively the size of bulk around zero, for the non- non-linear case, indeed seems to be captured by our (linear) rank formulas to high fidelity, evident from Fig. 3. Similar results for other non- cooo--iinaiittss.... loss functions, datasets can be found in the Appendix $9.4.
Los Hoaie H.
Quantitative measure of the fidelity of Rank formulas. To complement the visual grounds presented above, we now quantitatively measure the (in)ssgnificance of such spuriously tiny eigenvalues, in terms of the re- construction error incurred by excluding them. Hence, we perform a low-rank approximation via the SVD and measure the (relative) reconstruction error at the value of
3+-00%
3e-30(%))
Rounstvatien
rank from our formulas of the linear case. Fig. 4 displays the reconstruction еиrоr a function of the # of top eigen- vectors employed, for a ReLU network. As a reference, consider the empirical rank measurement obtained at machine precision in this case.
Figure 4: Hessian reconstruction error for ReLU network of hidden layer sizes 30, 20 with cross-enroppy loss, as the rank of the ap- proximation is increased. The dashed vertical lines indicate the cut-off at various values of the rank: first line at the prediction based on the linear model. second line at the empirical mcasurement of rank.
We find that using the linear rank value provides an cellent reconstruction, hence demonstrating the fidelity of our rank formulas to serve as measure of numerical rank in the other non-lincarities and losses, which we highlight in the Appendix S9.3. Consequently, iterative Hessian estima- tion procedures, e.g. in second-order optimization methods [16, 51], could benefit from the linear rank as guiding criterion for their design of Hessian approximation. Besides, these experiments also indicate that previous bounds, such as those by Jacot et al. [33], on the rank of outer-product Hessian and functional Hessian are quite coarse to be of much use (i.e., even > # parameters). This is because these bounds have a linear dependence on the product of: # of samples N and # of classes K. For the same reason, other works [16, 52] that bound the rank of the outer-product Hessian H., trivially, based on the of samples N are of little use.
case. The same observation extends to
Evolution of Rank during training
The upper bounds on the Hessian rank detailed before inherently depend on the rank of the weight matrices. While initialization guarantees them to be of maximal rank, the rank of weight matrices might possibly decrease during training, thus bringing about a decrease in the Hessian rank. Under some additional assumptions, Lemma shows that this does not happen and the rank remains constant.
Lemma 8. For a deep linear network, consider the gradient flow dynamics W = -1 (0)) o. Assume: (a) Centered classes: TV Eisc=1 X; = O, Vc EEE [I. (b) Balancedness at initialization: W wh++ w W (c) Square weight-matrices: Vt 00.
W E MMM, 1I and K =d= d= M. Then for all layers rk(w!) = rk(W)),
Balancedness is a common assumption that has been used in many previous works, like Arora et al. [53]. Centered classes can easily be enforced via pre-processing step, however empirically this is not required. While the proof (see Appendix S5) holds for square case, empirically we also find this to be true for non-square matrices (Fig. 5, left) and non- linearities shown in Fig. S2.
Consequence. An implication of this result that our upper bounds on the Hessian rank remain valid throughoul the truining. Even if the rank of the weight matrices were to decrease, say in the rectangular case, the Hessian rank would only decrease and our bounds would still be valid. The other avenue for a decrease in rank is narning-driven and as Z E [8xx x + 0, the functional Hessian
8

---

Capee
1200
14
10
Figure 5: Rank dynamics for a linear network with hidden layer sizes 25, 20, 15, trained using linear teacher. We show the evolution of (left) the rank of the weights with usual Glorot initialization (guaranteeing maximal rank) and (right) the rank of the Hessians, alongside the upper bounds, function of training time.
Hy 0 (as it has an explicit dependence on the residual ōx.y) So, if the learning architecture is powerful enough, the rank of H, will approach O, as well as leading to a decrease in the rank of Hc, and so rk(H)) + rk(H.).
other words, the loss Hessian is completely captured through the outer product Hessian at convergence. We demonstrate this empirically via Fig. (right) where we train a linear network using a linear teacher and visualize the rank dynamics as well as our upper bounds. We provide more details as well as experiments for the non-linear case in the Appendix S5.
7
Further results
7.1 Provable Hessian degeneracy with non-linearities
From Section 5.2, is clear that our upper bounds faithfully estimate the numerical rank in the non-linear case, despite the numerous tiny eigenvalues which cause inflated rank measurements. This might raise the question it is possible to establish, in this non-linear case, that the Hessian has provable degeneracy and not just approximate? The challenge is that here the data distribution manifests additionally via the activations at each layer, thus a theoretical analysis seems intractable without imposing strong assumptions. For a l-hidden layer network, F(x) ( x). we show it is still possible to get pessimistic yet non con-trivial upper bound with the following (mild) assumption:
Assumption A2. For each active hidden neuron i, the weighted input covariance has the same rank as the overall input covariance, i.e., rk(E [ax xx T) rk(E = r, with 0xx = o' w
Theorem 9. Consider 1-hidden layer network with non- non-linearity such that (22 o' (z)z and let M be the of active hidden neurons (i.e., probability of activation > 0). Then, under assumption Al and A2, rank of H. is given as, rk(H,) ) S rM + MK- M.
Assumption A2 is rather mild, i.c., in the finite-sample case, it holds as soon the # of samples N > 2d, for typical initialization of parameter weights. Besides, the class of non- non-linearities which satisfy the
condition includes e.g., ReLU, Beaky-ReLU. Further, this result extends to H
Corollary 10. At convergence to the minimum, the rank of the loss Hessian Hy, for the same setup as Theorem 9, upper bounded by: rk(H2) S rM + MK -M.
Contrast this with the view from [54], who claim the spectrum to be generically non-degenerate. Or, unlike [55), we establish this without any assumptions on particular kind of overparameteriizaton.
Fact 11. For multiple Salden--ayyrs. the following generalization of Theorem 9 holds empirically, rk(H.) S p- (d-r) (d-r)- -!-
J.-1 Mj, where p is the # of parameters and assuming no dead neurons.
While these bounds are likely to be quite loose as noticeable from Section 5.2, but more importantly they help establish provable degeneracy of the Hessian the minimum, with the number of 'absolutely- flat' directions (ie., those in the Hessian null space) in proportion to the sum of hidden-layer sizes.
7.2 Effect of bias on the rank of Hessian
Now, we see how the Hessian rank changes when bias enabled throughout a deep linear network. We make the following simplifying assumption, which is actually standard convention in practice.

---

Assumption A3. The input data has zero mean, i.e., X Px is such that E [x] -2]=0 -.
Theorem 12. Under the assumption Al and A3, for a deep linear network with bias, the rank of H. is upper bounded as, rk(Ho) I q(r + K q) + K, where := min(r, M1, ... MMM-1, K).
The proof can be found in the Appendix S7. Empirically, we do not require the input be mean zero and our upper bound actually holds with equality. Also, we list rank formulas for functional Hessian and the overall loss Hessian Appendix S7, in the non-bottleneck case. E.g.,
Fact 13. rk (H2)= 2 M + o' K) Lay2 L4', where of = min(r+ M1, ML-1, K).
Here too, rank deficiency has cleaner interpretation of being equal to the # of parameters in a hypo- thetical network with bias enabled, but with the minimum dimension of (that reflects the homogeneous
1-1 Σ (M +1 - (M)++ - -)).
coordinate at input) subtracted: rank-deficiency (Hc)
8 Conclusion
Summary, Our paper provides a precise understanding of how the neural network structure constrains the Hessian range and the resulting rank deficiency. In contrast to the number of parameters which are proportional to layer-widths squared, we obtain that rank is proportional to layer-width. The proof strategy relies on bounding the rank of the two parts of the Hessian separately, i.c., the outer- product Hessian H, and the functional Hessian y,, both of which are replete with the special Z-like structure. The analysis also reveals several striking properties of the Hessian, such surprisingly small overlap in the column spaces of H. and ,, and independence of the layer-wise column blocks in Hy. While our results were derived assuming linear activations, we demonstrate that, even with non-iinearities, our formulas faithfully capture the numerical rank.
All in all, by providing fundamental insights into the rank of the Hessian map which ultimately point to the sources and extent of redundancy in overparameterized neural networks, as a result of its compositional structure our work paves the way to exciting avenues for future research.
Discussion. In particular, our results merit discussion on some important aspects of deep learning:
(i) Overparameterization:: Modern DNNs, with billions of parameters, are in stark contrast to the traditional statistical viewpoint of having # of parameters approximately equal to the # of samples. While several works have argued for measuring model complexity instead through weight norms [56], margins [57], compressibility [58]. yet it remains hard to get an interpretable ballpark on the model complexity of neural networks. Since rank intuitively captures the notion of effective parameters, it could be a possible alternative to benchmark overparameterization, e.g. for double descent [38].
(ii) Flatness: growing number of works [59-61] correlate the choice of regularizers, optimizers, or hyperparameters, with the additional flatness brought about by them at the minimum. However, the significant rank degeneracy of the Hessian, which we have provably established, also points to another source of flatness that exists the initialization itself. Thus, a prospective avenue of future work would be to compare different architectures based this inherent kind of flatness.
virtue of the compositional model structure from
(iii) Generalization: An interesting observation available from our work is that factors such as width, depth, enabling bias - commonly observed to improve generalization also result in decreasing the rank/# parameters rutio, see Fig. S8b, S8c, S3. In a similar vein, recent work of [62] has provided a lower bound to the generalization error of statistical estimators in terms of the rank of the Fisher (which is intimately related to the Hessian) divided by of parameters. Practically, one could use a further relaxation of rank nuclear norm normalized by the spectral norm, in scenarios with spurious rank inflation. Overall, this suggests the relevance of studying the link between rank and generalization.
Limitations. Although empirically our (linear) rank results faithfully capture the behaviour of Hessian rank with linearitiiss we still lack rigorous theoretical characterization of the same (which will likely require incorporating additional distribution -sarbbitiooospiiiicccci specific assumptions). Besides, our analysis limited to the case of fully-connected networks, and would be interesting to extend this to other architectures such as convolutional networks, residual networks, etc. Lastly, it still needs to be shown theoretically that our upper-boune on the rank of the functional Hessian holds with equality, despite that this is what we observe in practice.
10

---

Acknowledgments and Disclosure of Funding
We would like thank Nicolò Ruggeri for reviewing a first draft of the paper. Further, we would like to thank the members of DA lab and Bernhard Schölkopf for useful comments. Sidak Pal Singh would also like to acknowledge the financial support from Max Planck ETH Center for Learning Systems.
References
[1] Ciyou Zhu, Richard Byrd. Peihuang Lu, and Jorge Nocedal. Algorithm 778: L-bfgs-b: Fortran subroutines large-scale bound-constrained optimization. ACM Transactions on Mathematical Software (TOMS), 200)550050,, 1997.
[2] Rudy Setiono and Lucas Chi Kwong Hui. Use of quasi-newton method in a feedforward neural network construction algorithm. JEEE Transactions on Neural Nenworks, 6(1):273-277 1995.
[3] Yann LeCun, John S Denker, and Sara Solla. Optimal brain damage. In Advances in neural information processing systems, pages 598 605,6 1990.
[4] Babak Hassibi and David Stork. Second order derivatives for network pruning: Opti- mal brain surgcon. In NIPS, pages 164-171, 1992. URL http://papers pwpppperrsnips................pp .ips. cc/paper/ 647-secona order- deriarrvesivaaiiss-eeeeeeeee for- for-foo--ttto network -ew.orr-rruunng-g cetesppptmmmlbblee
surgeon.
[5] Sepp Hochreiter and Jürgen Schmidhuber. Simplifying neural nets by discovering flat minima. In Advances in neural information processing systems, pages 529-536, 1995.
[6] David J. C. MacKay. A Practical Bayesian Framework for Backpropagation Networks. Neural 4(3):448-72,, 05 1992. ISSN 0899-7667. doi: 10. 11611662cco..o. 1994.4.3.48. URL httpt://///oo.. org/ 1162/neco... 1992. 4. 3488.
Neural Computation,
[7] John S. Denker and Yann LeCun. Transforming neural-net output levels to probability distributions. In Proceedings of the 3rd International Conference Neural Information Processing Systems. 91PS' page 853-859, San Francisco, CA, USA, 1990. Morgan Kaufmann Publishers Inc. ISBN 1558601 848.
[8] Y. LeCun, P. Simard, and Barak A. Pearlmutter. Automatic learning maximization by on-line estimation of the hessian's 's cigenvectors. In NIPS 1992, 1992.
[9] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Deep residual learning for image recognition. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
[10] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirec- tional transformers for language understanding. Proceedings of NAACL-HLT, 2019.
[11] Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1):147-160, 1994.
[12] James Martens and Ilya Sutskever. Learning recurrent neural networks with hessian-free optimization. In ICML, 2011.
[13] Frédéric Bastien, Pascal Lamblin, Razvan Pascanu, James Bergstra, Ian Goodfellow, Arnaud Bergeron, Nicolas Bouchard, David Warde-Farley, and Yoshua Bengio. Theano: new features and speed improve- ments, arXiv preprint 12Xiv:1211.55 1.5590, 2012.
[14] Tom Schaul, Sixin Zhang, and Yann LeCun. No more pesky learning rates, 2013.
[15] James Martens and Roger Grosse. Optimizing neural networks with fronecker-factoree approximate curvature, 2020.
[16] Aleksandar Botev, Hippolyt Ritter, and David Barber. Practical gauss-newton optimisation for deep learning. In International Conference Machine Learning, pages 557-565. PMIR, 2017.
[17] Donald Goldfarb, Yi Ren, and Achraf Bahamou. Practical quasi-newton methods for training deep neural networks. arXiv preprint arXiv:2006.08877 2020.
[18] César Laurent, Thomas George, Xavier Bouthillier, Nicolas Ballas, and Pascal Vincent. An evaluation of fisher approximations beyond kronecker factorization, 2018. URL https: https:///penrrevieee net ffoum?? id-ryVC6tkw6.

---

[19] Xin Dong. Shangyu Chen, and Sinno Jialin Pan. Learning to prune deep neural networks via layer-wise optimal brain surgeon, 2017.
[20] Sidak Pal Singh and Dan Alistarh. Woodfisher: Efficient second-order approximation for neural network compression, 2020.
[21] Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions the nonlinear dynamics of learning in deep linear neural networks, 2014.
[22] Kenji Kawaguchi. Deep learning without poor local minima, 2016.
[23] Stephen F. Gull. Developments in Maximum Entropy Data Analysis, pages 53-71. Springer Netherlands, Dordrecht, 1989. ISBN 978-94-015--860-8.
doi: 10.1007/978-94-000 00.1007/978-94-005--86---4 4. URL https://ddo
org/10. 1907/908-7990 -00--99-------8888 7860-8446.._.
[24] David MacKay. Bayesian model comparison and backprop nets. In J. Moody, S. Han- son, and R. P. Lippmann, editors, Advances in Neural Information Processing Systems, vol- 4. Morgan-Kaufmann, 1992. URI. httpa://proceedingg. woo.ceddingg..euriippsseeees.e www.wpp..ccppppee/eeee/.e. cccpapper/999//110 c3c59e5f (115598f88aee77331144446666.e. Pap.aao----pppp.p...
[25] Levent Sagun, Leon Bottou, Yann LeCun. Eigenvalues of hessian in deep learning: Singularity and beyond. arXiv preprint arXiv: (1611.0077666 2016.
[26] Levent Sagun, Utku Evci, Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the hessian of over- wer-parametrized neural networks. arXiv preprint arXiv: 04454. 2017.
[27] Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via bessian eigenvaluc density, In International Conference Machine Learning, pages 2232-2241 PMLR, 2019.
[28] Vardan Papyan. Measurements of three-level hierarchical structure in the outliers in the spectrum of deepnet hessians. arXiv preprint arXiv:1901.02244 2019.
[29] Diego Granziol, Timur Garipov, Dmitry Vetrov, Stefan Zohren, Stephen Roberts, and Andrew Gordon Wilson. Towards understanding the true loss surface of deep neural networks using random matrix theory and iterative spectral methods, 2020. URL httpss:/openrree wtwp//veervvie..eeee/ee/e. wwt/forunninneccc -eteiidd-Hiae HeiiddHHHgggat tza.NNt....
[30] Jeffrey Pennington and Yasaman Bahri. Geometry of neural network loss surfaces via random matrix theory. In Doina Precup and Yee whye Tch, editors, Proceedings the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2798-2806. PMLR, 06-11 Aug 2017. URL http: /ttp::///pocceeingga mlr wwwpsrrssseee. grress/v0//fe http://////nnnnnooononoaoooo
[31] Diego Granziol. Beyond random matrix theory for deep networks. ArXiv, abs/2006.07721, 2020.
[32] Ryo Karakida, Shotaro Akaho, Shun ichi Amari. Universal statistics fisher information in deep neural networks: Mean field approach, 2019.
[33] Arthur Jacot, Franck Gabriel, and Clément Hongler. The asymptotic spectrum of the hessian of dnn throughout training. arXiv preprint arXiv: 1910.02855, 2019.
[34] Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding, 2016.
[35] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv: Learning, 2019.
[36] Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. arXiv preprint 1rXiv:1804.0885 2018.
[37] Wesley Maddox, Gregory Benton, and Andrew Gordon Wilson. Rethinking parameter counting: Effective dimensionality revisted. arXiv preprint arXiv:2003.02.39, 2020.
[38] Mikhail Belkin, Daniel Hsu. Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learinn practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116: 15849 15854, 2019.
[39] Jan R Magnus and Heinz Neudecker. Matrix differrntiall calculus with applications in statistics and econometrics. John Wiley & Sons, 2019.
12

---

[40] Guy Gur-Ari, Daniel A. Roberts, and Ethan Dyer. Gradient descent happens in tiny subspace, 2018.
[41] C. Radhakrishna Rao. Generalized inverse of a matrix and its applications. In Vol. / Theory of Statistics, pages 601-620. University of Califoria Press, 1972.
[42] Jianjun Chuai and Yongge Tian, Rank equalities and inequalities for kronecker products of matrices with applications. Applied Mathemarics and Computation, 150(1):129 137, 2004. ISSN 0096-3000 doi: httpa: http://wwwwwwww.wwttttttcto www/ccoo//cc//o /cinncee
[43] Alberto Bernacchia, Mate Lengyel, and Guillaume Hennequin. Exact natural gradient in deep linear networks and its application to the nonlincar case. In S. Bengio, H. Wallach, H. Larochelle, K. Grau- man, N. Cesa- Dasa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: httppa//pprreee http///poceeeenn/eeeeeeeeeeeeeee neurips. cttppppp..cppppe///1/../ pdf.
[44] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint XI0.:/000000772, 2018.
[45] Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010.
[46] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017.
[47] Alex Krizhevsky, Learning multiple layers features from tiny images. 2009.
[48] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Yee Whye Teh and Mike Titterington, editors, Proceedings of the Thirteenth Interna- tional Conference on Artificial Intelligence and Statistics, volume of Proceedings of Machine Learn- ing Research, pages 256, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR. URL http: /pppce//pcccccinn... mlr press/v9/ glwgoooooaaa.. html.
[49] Shashanka Ubaru and Yousef Saad. Fast methods estimating the numerical rank large matrices. page 468-48 477, 2016.
[50] Gene H. Golub, Virginia C. Klema, and Gilhert W. Stewart. Rank degeneracy and least squares prohlems. Technical report, Stanford, CA. USA, 1976.
[51] Jonathan Lacotte, Yifei Wang. and Mert Pilanci. Adaptive newton sketch: Linear-time optimization with quadratic convergence and effective hessian dimensionality, 2021.
[52] Hao Shen. Towards a mathematical undorstanding of the difficulty in learning with feedforward neural networks, 2016.
[53] Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks, 2019.
[54] Jeffrey Pennington and Pratik Worah. The spectrum of the fisher information matrix of a single- hidden-layer neural network. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors. Advances in Neural Information Processing Systems. volume 31. Curran Associates, Inc., 2018. URL htttps:/pproeedingg wwwpeediiinnnnnuriiieeeeeee wttp./aa...pppppe////////... cctpappe//01///11222 Paper -
[55] Tomaso Poggio, Kenji Kawaguchi. Qianli Liao, Brando Miranda, Lorenzo Rosasco, Xavier Boix, Jack Hidary, and Hrushikesh Mhaskar. Theory of deep learning iii: explaining the non-overfitting puzzle, 2018
[56] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theary, volume 40 of Proceedings of Machine Learning Research, pages 1376-1401, Paris, France, 03-06 html.
Jul 2015. PMLR. URL
.wr. www.-prrsssvvee grress/v40//eyshabur
[57] Peter Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectraalyy margin bounds for neural networks, 2017.
[58] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach, 2018.
[59] 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.0m 04836, 2016.
13

---

[60] Stanislaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Finding flatter minima with sgd, 2018. URL httpa////ppeeeeeeeeeee/eeoooooee r1VF9dCUG.
[61] Carlo Baldassi, Fabrizio Pittorino, and Riccardo Zecchina. Shaping the learning landscape in neural networks around wide flat minima. Proceedings of the National Academy Sciences. 117(1):161-170. 2020.
[62] Inbar Seroussi and Ofer Zeitouni. Lower bounds on the generalization error of nonlinear learning models. arXiv preprint arXiv:2103. 147233, 2021.
[63] George Matsaglia George H. Styan. Equalities and inequalities for ranks of matrices, Linear and Multilineur Algebru, 2(3):269-292, 1974. doi: 10.1080/0308 1087408817070. URL https://doi /rrg////////////////////// 10. 00010000000008700888100000
[64] Anil K. Jain. Fundamentals of Digital Image Processing. Prentice- Hall, Inc., USA, 1989. ISBN 0133361659.
[65] Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameteriiation. International Conference on Machine Learning (ICML). 2018.
[66] Jan R. Magnus and Heinz Neudecker. Matrix Disferential Calculus with Applicatioos Statistics and Econometrics. John Wiley, second edition, 1999. ISBN 047 04471986321 9780471986322 047198660 147198633X 9780471986331.
14


Reviews:
[{"review_id": "ZTuaRX3BsrP", "reviewer": "Reviewer_bE99", "summary": "This paper analyzes the rank of the Hessian matrix of fully connected neural networks. Theoretically, for a linear fully-connected neural network with square loss, the authors provided an upper bound for the rank of Hessian with respect to the population loss. They also did many experiments for small neural networks on MNIST and CIFAR-10 to show that their upper bound is almost tight, and works for different types of non-linear activations, losses, and initializations.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "Significance:\n\nIt is interesting to study the actual rank of the neural network Hessian matrix. However, my major concern about this is that the justification for studying the rank itself may be a bit unclear. The exact rank of such a huge matrix is not robust to noise and doesn't necessarily carry much information. I will explain this in more detail in the following paragraphs:\n\n- People have empirically found that the neural network Hessian eigenspectrum usually contains a \"spike\" which has very few large eigenvalues and a \"bulk\" with a lot of small eigenvalues. In this case, the rank is approximately the size of the bulk, so it loses the information about the spike, which can be significant in capturing gradient change, measuring flatness, etc. In Section 5.2, line 252, the authors also claimed that \"tiny but non-zero eigenvalues hold little significance\" (similar statements at line 306), but they do not eliminate these eigenvalues for the linear case, which seems confusing.\n\n- The exact rank of a huge matrix is not robust to noise, and noise always exists in the case of neural network training. For instance, the input data may contain some noise, so the second-moment matrix $\\Sigma_{xx}$ of the input can become full rank with a small amount of noise even when the \"true\" input only lies in a low-rank subspace. Noises can also come from the finite sampling of the training data, the selection of mini-batches, and even the machine computation. All these factors might potentially inject noise into the Hessian matrix and make its rank change significantly. The authors do not seem to discuss the influences of these noises on their results, which makes their results somewhat restrictive.\n\n- Given the two reasons mentioned above, it might be a bit unclear how the rank of Hessian could measure the effective number of parameters or inherent complexity of neural networks, both of which should intuitively be robust to the noises mentioned above.\n\n- The implication from the rank to the structure of the Hessian might be a bit weak. The authors in this paper showed empirically that the ranges of different parts of Hessian rarely intersect, but the corresponding eigenvalues of these spaces are not analyzed. It's possible that they are random directions in high-dimensional space and parts of the bulk in Hessian eigenspectrum, but it's also possible that some directions are part of the spike but others are bulk.\n\nTheory:\n\n- The setting of the theoretical part in this paper is somewhat limited. The analysis only works for a linear fully-connected neural network with square loss and requires the weight matrices to be full rank (which is true at initialization but not necessarily true during training or at minima).\n\n- The techniques used by the authors are specific, e.g., they seem to rely heavily on the rank formula for the \"Z-like\" matrices (Lemma 1). These techniques seem hard to generalize to other settings, which may limit the generalization of their results to other scenarios.\n\nExperiments:\n\n- The experimental settings are kind of restricted. The experiments are done on (Fashion-)MNIST and CIFAR-10 with small neural networks (number of parameters at most a thousand or so), and the input images are downscaled. These restrictions make the experimental setting not very realistic and the empirical results not so convincing.\n\n- The description of how the authors calculate the exact rank of the full Hessian might be a little vague. Since the eigenspectrum is not well-separated, it's unclear how the authors choose the threshold to decide whether a singular value is 0 or not and how to justify this procedure. It might be better if the authors could talk more about how they \"utilize FLOAT-64 precision\" and handle the numerical errors when computing the Hessian and the corresponding SVD.\n\nClarity:\n\n- Generally, this paper is well-structured. However, the figures in this paper are small, especially the legend. It's hard to read the legend on a printed copy of this paper. Besides, the figures are not very friendly to black and white printers.\n\n- Some statements and terms in this paper might be a bit vague. For instance, at line 148, the notation $(\\Sigma_{xx})_{r\\times r}$ is not defined. More details about these potentially vague statements/terms will be provided in the following \"Minor Comments\" section.\n\nMinor Comments:\n\n- There might be a mismatch between the settings for the theory and experiments in the paper about the number of parameters. For the theoretical part, as also mentioned at the end of the abstract, the rank deficiency and parameter redundancy are more significant for over-parameterized networks, but the experiments were done on under-parameterized networks.\n\n- The Hessian matrix of neural networks depends on the input data and their labels. The arguments in this paper seem to work well at the initialization and the global minimum where the Hessian is (almost, in some sense) independent of the labels. However, it is not very clear whether they still work during training since the functional Hessian may have some non-trivial correlations with the outer-product Hessian.\n\n- In line 216, the authors provided an interpretation to their formula, i.e., they construct a hypothetical network whose width for all layers are subtracted by the minimum width, but did not explain how this hypothetical network relates to the original network. It may be better if the authors could provide more justifications on this.\n\n- In the caption of Figure 3, the authors use \"predictions of the bulk size\", but I did not find where this is defined. It might be better if the authors could explain this more clearly.\n\n- At line 240, the authors claimed that rank/#params \"intuitively captures the fraction of effective parameters\", which might be confusing because rank is some (potentially non-robust) second-order information about the parameters and not very directly related to the parameters themselves.\n\n- In Figure 4, the authors showed that the linear rank value prediction provides a reconstruction of the Hessian with only 0.002% error. However, since there is no significant eigengap at or near that linear rank value, it is possible that using a much smaller value, e.g., 200, will also result in a good reconstruction of the Hessian. Therefore, it is a little unclear why the linear rank value is significant in this case.\n\n- At line 317 (Corollary 10), the \"minimum\" might not be formally defined. Does it mean \"global minimum with respect to the population loss\"? I think this corollary may need the rank of functional Hessian to be of rank 0.\n\nRelated Works:\n\n- The related works are generally properly cited. There are some other papers that might be relevant to this paper. [1] provided a theoretical model for the Hessian of neural network and use that to explain the existence of C large eigenvalues of Hessian where C is the number of classes, and [2] proposes \"class/cross-class structure\" and analyzes the Hessian eigenspectrum in a more fine-grained way.\n\n[1] Fort, Stanislav, and Surya Ganguli. \"Emergent properties of the local geometry of neural loss landscapes.\" arXiv preprint arXiv:1910.05929 (2019).\n[2] Papyan, Vardan. \"Traces of class/cross-class structure pervade deep learning spectra.\" Journal of Machine Learning Research 21.252 (2020): 1-64.\n\nTypos:\n\n- Line 214: \"Fact. (7)\" -> \"Fact 7\"\n- Line 165: In Line 147 the authors already assume $\\Sigma_{xx}$ is an $r\\times r$ matrix, but here it's still $d\\times d$. This abuse of notation may confuse the readers.\n\n---------------------Update--------------------------\n\nI have read all the other reviews and the authors' responses, and I have decided to increase my score by 1. The detailed reasons why I increase my score is attached below:\n\n- Thank the authors for their very detailed responses. I understand from their response that the rank of Hessian is more robust to noise than I originally thought, so it makes more sense to consider this rank as the inherent complexity measure of neural networks.\n\n- It is interesting to see from the \"Validity of rank results during training\" section in their general response that their results hold during training and might empirically become tighter throughout training. This addressed one of my minor concerns which is about the interactions between functional Hessian and outer-product Hessian.\n\n- It is still a bit unclear how the Hessian rank can imply the effective number of parameters in neural networks. The authors take the quadratic problem as an example, but the quadratic approximations for neural networks may not be very accurate since the optimization landscapes of neural networks are always highly non-convex and non-smooth.\n\n- The authors computed the \"energy\" of the spike and the bulk for a small network with K=7, and these 7 large eigenvalues contribute even more energy than the sum of energy contributed by hundreds of bulk eigenvalues. Therefore, the importance of the \"bulk\" of the Hessian eigenspectrum may still be limited.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not seem to explicitly discuss the limitations or societal impact in their paper. I do not immediately see any potential negative societal impacts of this work, but it might be better if the authors could talk about the limitations of their work, perhaps in the discussion section.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "XbIpmqlg9YT", "reviewer": "Reviewer_hhmf", "summary": "This paper provides several results on the rank of the Hessian of neural networks. The main results are:\n\n(A) upper bounds on the rank of the Hessian of a linear neural network (i.e., identity activations). These are proved by separating the Hessian into the sum of the “outer-product Hessian” and the “functional Hessian”, and bounding the rank of these separately.\n(B) a conjectured formula for the exact Hessian rank that matches experiments, and is also quite close to the upper bounds.\n(C) experimental evidence that these results essentially hold for neural networks with nonlinear activations as well, even after training.\n(D) for 1-hidden layer nonlinear networks, under a mild assumption a very weak (but still nontrivial) bound on the rank is obtained.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "The paper is well-structured and clear. As far as I can tell, the proofs are correct. The takeaway of the results that I find most interesting is the following: let the network layers be of width M_0, M_1,…,M_L. Then the rank of the Hessian of a linear network is upper-bounded by O((min_i M_i) * (sum_{i=0}^L M_i)). This is an improvement over the trivial O(sum_{i=1}^L M_i M_{i-1}), which is the number of parameters. Furthermore, the proofs demystify this low-rank phenomenon: it is due to the compositional structure of the neural network map. Most of the paper is dedicated to proving these facts about the rank of the Hessian and confirming empirically that they generalize to networks with nonlinear activations. At the end, there is an interesting discussion of some the implications of these findings.\n\nI have some questions about the results, but overall found the paper to be a pleasant read and think that it would be informative to attendees and a good fit for the conference.\n\n* Could you elaborate on the remark on Lines 176-178. Is this supposed to be a rigorous statement? If so, can you give a reference?\n\n* Lines 194-195: “This phenomenon is quite straightforward to see in a 2-layer network and there 195 Corollary 6 is an equality.” Please add a discussion of this to the supplementary materials?\n\n* Line 295, you write “An implication of this result is that our upper bounds on the Hessian rank remain valid throughout the training”.\nWhy is this an implication of the result? It seems that the upper bounds in Theorem 3 and in Theorem 5 should still holds even when the matrices W^l are not maximal-rank during training. So it seems that the only implication of this result is that the outer-product Hessian rank stays constant.\n\n* Lines 354-355, (i) Overparametrization. “Since rank intuitively captures the notion of effective parameters, it could be a possible alternative to benchmark overparameterization, e.g. for double descent”. <— I have a few questions about this: (1) this paper seems to show that the rank is roughly the square root of the number of parameters, so wouldn’t this still be much more than the number of data points for some large network architectures? (2) Can you make this sentence more precise? How is the rank of the Hessian capturing the amount of effective parameters besides the  fact that minima are flat, which is discussed in the next paragraph Lines 356-361?\n\nTypos\n* Line 93, “where the l-th layer map F^l” -> “where the l-th layer map is F^l”\n* Line 214, “input-covariance has rank” -> “input-covariance has full rank”\n* Line 218, “all layer-widths have been” -> “all layer-widths have all been”\n* The bibliography seems to be missing from the supplementary materials. For example, I could not find reference [61].\n* Line 323, “While these bounds” -> “These bounds”\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not have a section with the limitations of their work, but I am not sure it is necessary due to the theoretical nature of the paper and the clarity of the presentation of the results.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "QQwgFiV46Fm", "reviewer": "Reviewer_8A13", "summary": "This paper derives tight upper bounds on the Hessian rank for deep linear networks. They show that these rank formulae (derived for the linear case) faithfully capture the numerical rank in the non-linear regime. They also demonstrate that these rank bounds hold during the course of training.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "1. The paper is well written and easy to understand. \n2. The paper derives a closed form expression for the Hessian rank that comes with a tightness guarantee for deep linear networks. \n3. Using the above expression, the authors show that the rank effectively depends on the sum of hidden layer widths while the number of parameters is proportional to the sum of hidden layer widths squared. \n4. Using the rank as a proxy for the effective number of parameters, the work can prove to be useful to understand the links between generalization and flatness of minima. And also to understand various phenomenon related to overparametrization such as double descent.\n5. The authors empirically show that the rank (derived for the linear case) also captures the numerical rank when the activation functions are non-linear. \n\nThe paper addresses an important problem, is well written and provides an interesting new perspective on the effective number of parameters for deep neural networks. I recommend acceptance. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work is largely theoretical, so considerations about societal impact do not directly apply.\n\nBut there is no discussion on the limitations of their method except that it is theoretically unable to capture the Hessian rank with non-linear activation functions (although empirical results suggest that it is able to capture the same). \n\nI believe that the limitations of the current work will hold for all the methods (i.e. not specifically for this paper) that analyze the linear case and extend it to the non-linear case. A discussion about the same should be added to the paper for completeness. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "0-J3VYfjwdM", "reviewer": "Reviewer_9bPu", "summary": "This paper studies the rank of Hessian for deep linear networks. Theoretically, with squared loss, and assuming the weight matrices are full-rank, this paper provides rank upper bound for outer-product, functional and full Hessian, and empirically verifies that the bounds are almost tight. This paper further shows empirically that the numerical rank with nonlinear networks can still be captured by the linear rank bound, and that the Hessian rank decreases during training. Finally, Hessian degeneracy results for 1-hidden-layer networks and extension to the case with bias are also provided.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "I think the rank bounds for deep linear networks are very nice, and it is also amazing that in Figure 2, the true ranks match the predictions so well. \n\nOn the other hand, I have the following concerns:\n1. As also mentioned in this paper, in many settings, not only the rank matters and we also need to consider the size of eigenvalues. For example, Figure 4 tries to show that using the given rank formula, we can reconstruct the Hessian with 0.002% error; however from the same graph, we can get a small reconstruction error as long as we use more than 500 eigenvalues, while the rank formula gives a value between 1000 and 1500. Therefore I think the evidence is not strong enough to support the claim that the rank formula truly captures the numerical rank in practice.\n2. Moreover, I think the tightness of the rank bounds may be partly due to random initialization. For example, as shown in Figure 5, even though the rank of each weight matrix stays constant, the Hessian rank drops a lot. I think this may suggest something like the eigenvalues of each weight matrix become more concentrated; in fact such a result has been shown for linearly separable data with the exp or logistic loss [1,2]. In other words, I am worried that the Hessian rank formula may soon become inaccurate during training. \n\nUpdate after rebuttal: Thank you for your response. It is nice that the analysis can still be applied throughout training, and the empirical results look promising. I will increase my score by 1.\n\nReferences:\n[1] Gunasekar, Suriya, Jason Lee, Daniel Soudry, and Nathan Srebro. \"Implicit bias of gradient descent on linear convolutional networks.\" arXiv preprint arXiv:1806.00468 (2018).\n[2] Ji, Ziwei, and Matus Telgarsky. \"Gradient descent aligns the layers of deep linear networks.\" arXiv preprint arXiv:1810.02032 (2018).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are discussed above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper gives an exact characterization on the rank of the Hessian for linear networks, and show that in many settings the rank can be much smaller than the number of parameters. The paper then verify these claims empirically in nonlinear networks and show that the Hessian is still approximately low rank. Although the reviewers had some concerns initially, their opinions have improved during the author response period where it became clear that the result holds throughout training (not just for minima) and has interesting empirical observations. The authors should really incorporate all the comments given by the reviewers to improve the paper, including explaining why the rank of the Hessian is intuitively related to the number of parameters and explaining connections with related works.
Decision: Accept (Poster)