Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper provides several results on the rank of the Hessian of neural networks. The main results are:

(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.
(B) a conjectured formula for the exact Hessian rank that matches experiments, and is also quite close to the upper bounds.
(C) experimental evidence that these results essentially hold for neural networks with nonlinear activations as well, even after training.
(D) for 1-hidden layer nonlinear networks, under a mild assumption a very weak (but still nontrivial) bound on the rank is obtained.

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.

I 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.

* 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?

* 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?

* Line 295, you write “An implication of this result is that our upper bounds on the Hessian rank remain valid throughout the training”.
Why 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.

* 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?

Typos
* Line 93, “where the l-th layer map F^l” -> “where the l-th layer map is F^l”
* Line 214, “input-covariance has rank” -> “input-covariance has full rank”
* Line 218, “all layer-widths have been” -> “all layer-widths have all been”
* The bibliography seems to be missing from the supplementary materials. For example, I could not find reference [61].
* Line 323, “While these bounds” -> “These bounds”

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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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. 

On the other hand, I have the following concerns:
1. 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.
2. 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. 

Update 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.

References:
[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).
[2] Ji, Ziwei, and Matus Telgarsky. "Gradient descent aligns the layers of deep linear networks." arXiv preprint arXiv:1810.02032 (2018).
limitations_and_societal_impact: The limitations are discussed above.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
main_review: 1. The paper is well written and easy to understand. 
2. The paper derives a closed form expression for the Hessian rank that comes with a tightness guarantee for deep linear networks. 
3. 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. 
4. 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.
5. The authors empirically show that the rank (derived for the linear case) also captures the numerical rank when the activation functions are non-linear. 

The 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. 
limitations_and_societal_impact: The work is largely theoretical, so considerations about societal impact do not directly apply.

But 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). 

I 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_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: Significance:

It 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:

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

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

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

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

Theory:

- 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).

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

Experiments:

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

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

Clarity:

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

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

Minor Comments:

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

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

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

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

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

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

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

Related Works:

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

[1] Fort, Stanislav, and Surya Ganguli. "Emergent properties of the local geometry of neural loss landscapes." arXiv preprint arXiv:1910.05929 (2019).
[2] Papyan, Vardan. "Traces of class/cross-class structure pervade deep learning spectra." Journal of Machine Learning Research 21.252 (2020): 1-64.

Typos:

- Line 214: "Fact. (7)" -> "Fact 7"
- 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.

---------------------Update--------------------------

I 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:

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

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

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

- 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.
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_title: null

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)