Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper discusses the phenomenon of double descent in the framework of finite width neural networks trained with various loss functions. The analysis of the authors relies on the use of influence functions. They provide intuition on the dependence of double descent on the number of samples in the overparametrized regime and on the number of parameters (in the under parametrized regime) by highlighting the dependence of the population loss on the inverse of the smallest eigenvalue of the Hessian. By adding some additional assumption on the initialization and relying on random matrix theory, they are then able to express this smallest eigenvalue as proportional to the square of the difference between the number of training points and the number of parameters which matches the blow up observed numerically at the so-called interpolation threshold. 

main_review: The paper is very well written, very clear and it is well aware of the current state of research and the literature. The contribution is worth publication.  
summary_of_the_review: Introduction 

- I would remove the sentence “as well as can cater to the idiosyncrasies that arise with the usage of neural networks”. It is so unclear that you have to explain it right after with the id est. Stick to  what you do, this is good enough: I would replace the entire paragraph with something like “We develop a theoretical analysis of double descent in the finite width framework and study how this phenomenon is impacted by changes in the loss function” or something similar
- “by utilizing the tool of influence functions” —> ”by relying on influence functions which are commonly used in robust statistics” or if you really want “by using the notion of influence functions from ..” 
-  In the last paragraph, “starkly” might be a bit strong. I would replace with “clearly” or “which has a clear influence”

Section 2.1.

- When you use not only at the beginning of a paragraph, you should invert : “Not only they have useful properties” —> “Not only do they have useful properties” 

Section 2.2. 

- Why would you need regularity conditions to exchange the order of the expectation and the derivatives. This is not clear to me. Expand or remove. 

Section 3

- The sentence “the change in loss and which we leverage” should be changed to “the change in loss which we leverage”
- The sentence “this quantity is inconsequential ” is not very clear. Why not replace the remark with a clear explanation of the form : “Although the first term on the RHS of (1)  is not the exact training loss, it only deviates from that loss by a negligible quantity related to the difference of the training losses for two distinct training sets. When training for sufficiently long, both losses vanish and the difference thus becomes negligible. ” or something similar


Section 4

- A reference on the decomposition of the Hessian into The outer product Hessian and the functional Hessain would be good
- I would replace the constant $A_{\theta_0}$ and $B_{\theta_0}$ with simpler symbols such as lower case letter or $c_0$ and $c_1$ or 
- Do we really use the term external regularization to denote the absence of any regularization?

Section 4.2.

- The key result (to me) which formalizes the double descent phenomenon is really corollary 5. I think it would be good to have that result appear somewhere earlier. For example in an informal form in the introduction. 

Section 4.3.

- You provide a lower bound on the population loss, however, from the plot you give in section 4.3. it seems that one could also derive an upper bound (although probably not at the interpolation threshold). I.e. Would such an upper bound more difficult to derive given your proof technique?
- page 7, “we can be thoroughly assure of the accuracy” should be replace by “thoroughly assured” or “we “can thoroughly assure”

Section 5

- The first plot in Figure 3 is unclear. What do you mean by Test error in this case, how does it vary with respect to the population loss as highlighted by the double descent curve shown in red ? 
- The explanation of the binary cross entropy loss is not very clear (double check)
- What do you mean by “Note, this is not the case that networks were not trained long enough — rather, we run them for 40, 000 epochs” ? It would be more clear to replace the sentence with something like “Note that the networks were trained for long enough”

Section 6

- In the first paragraph, the sentence “which avoids the need to retrain training set size many models” is unclear. What do you mean ?
- In the statement of Theorem 7, I think you forgot the sentence “Consider the particular case of the ordinary least-squares ” which appears in the appendix. it would be more clear to add in section 6 as well. 
- Generally speaking, it is not clear how section 6 relates to the rest of the paper. Is there a direct implication w.r.t double descent ? If I understand well we are not discussing the over parametrization regime as we consider inverting X^TX ? Although we still have a bound in the inverse of the Hessian. What prevents a bound similar to 
- Last paragraph : “raises an important aspect”. You don’t really raise an aspect. I would replace with “which highlights an important downside of first order influence functions” or even simpler “which confirms the suboptimality of first order influence functions when used in the leave one out framework”. 


A couple of additional comments and/or typos:

- In the introduction “frequently employed deep networksand” —> “networks and”
- In the introduction: “And while the connection … provides interesting parallels, but ultimately its applicability … is unclear.” —>  I would remove the but ultimately
- third paragraph of the introduction, I would remove the “strive” which is not really appropriate here and replace it with the simpler "we develop” (why complicate things when they can be simple?)
- I would the term “function output” this makes the statements less clear. I would stick with “the function $f$”
- Statement of Corollary 5: “For MSE loss” —> “For the MSE loss”
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the double-descent phenomenon in a very general scenario: general loss functions which include but are not limited to MSE and cross-entropy, and general finite-width neural networks (i.e not limited to linearized -- NTK / RF-- regimes). The main tool here is a clever use of *influences* function (from classical robust statistics), which allows the authors to study (in principle) double-descent curves for the risk of estimators defined only implicitly via MLE optimization problems, say. The end result is that the authors manage to lower-bound the population risk by a term which depends on the trace of the inverse of the hessian of the loss function at the optimum. When then this hessian becomes singular, the aforementioned trace-of-inverse explodes to infinity, and a double-descent curve occurs. The location of this double-descent curve is accurately predicted by this paper.
main_review: Review for "PHENOMENOLOGY OF DOUBLE DESCENT IN FINITE-WIDTH NEURAL NETWORKS"
===

Typos
---
- 2nd paragraph:networksand ==> networks and
- "And while the connection of (infinite-width) neural networks to Neural Tangent Kernel (Jacot et al., 2018) provides interesting parallels, but ultimately its applicability to finite-width neural networks — i.e., models of practical significance — is unclear." <== Please rephrase.
- Please choose between use of "double descent" and "double-descent".
- "Add-one-in procedure ." ==> "Add-one-in procedure." (remove stray space)

Other minor issues
---
- "Thanks to the influence function of the parameter estimate (Eq. 4 for D = D_n)" <== Eq. 4
is in the appendix. It should already appear as an equation in Propositoon 2 of the main
manuscript, then reference it.
- A1: $\ell(f_{\theta_\star}(x), y)$ is not a function, it is a number...
- A4: Doesn't look good. The justification given by the authors is not satisfactory either. Indeed, the authors claim that A4 can be met at the price of a $\lambda_\min(\Sigma)$ factor in the bounds. The issue is that lambda_min(Sigma) that as long as there isn't a sensible lower-bound on $\lambda_\min(\Sigma)$, say in the case of neural networks, then all bets are off. At the very least, the authors should formally / rigorously justify this step.
- In the appendix, results shouldn't be restarted under labels / names different from those used in the main paper. Makes the proof difficult / impossible to follow. For example, Corollary 5 in the paper is called Corollary 13 in the appendix, without any reference to one another; Theorem 3 has become Theorem 10 in the appendix (again without any reference to one another...).

Major issues
----
- Assumption. One of my main concerns with the paper are the assumptions. 
  - For example, what is a croncrete nontrivial scenario where all those assumptions hold simultaneously ? This is in contrast to previous works, wherein the assumptions made on the model and data are quite transparent to the reader. For example, what do the results of the current paper say about a single layer neural network with random hidden weights, and output weights learnt with MSE loss (this was analyzed in Adlam and Pennington 2020 "The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization")?  

- It's not clear what is ultimately being assumed in Corollary 5. 

After authors' response
---
I'm changing my score from 6 to 8. I was convinced by the answers given to my concerns.

summary_of_the_review: This paper presents a completely new approach to understand the phenomenon of double-descent, for very general models / loss functions (including finite-width neural networks). I have a few concerns about the assumptions being used in the paper though (as explained further above).
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper provides a new analysis of the phenomena of double-descent in maximum likelihood type of estimators, with a focus on neural networks. This analysis is built on: 
* expressing the population loss based on a "add-one-in" procedure (a symmetric procedure to the more classical "leave-one-out", which allows in a second stage to use influence functions to provide a lower bound of this loss,
* proving that the lower bound on the population loss diverges at a certain threshold, by analysing the spectrum of the Hessian at the optimum.

The paper also studies the influence of different loss functions on this behavior. In particular, the authors provide an analysis for the case of cross-entropy. Finally, as a by product of their analysis, they apply the influence function analysis to the ``leave-one-out'' loss, and show that, from a practical point of view, second order influence functions can be interesting to analyse along side the currently considered first order ones to provide a better understanding of deep learning. 
main_review: Novelty: While the impact of the Hessian on the learning dynamics is expected, analysing it using the influence functions is novel to the best of my knowledge, and provides valuable  insights,  as  it  allows  to  express  the  population  loss  differently,  and therefore explicit a lower bound showing the double descent behavior.

Clarity:The  paper  is  generally  well  structured  and  clearly  written.  The  argument  is outlined  from  the  beginning  and  detailed  afterwards,  which  makes  it  easy  to follow.

Significance of the theory: The  overall  argument  is  well  constructed,  and  to  the  best  of  my  knowledge,the  provided  proofs  seem  correct.   In  particular,  the  analysis  in  terms  of  the Hessian  spectrum  and  rank  and  the  approach  taken  by  the  authors  to  do  so provide explanations to many of the latest observations in the double descent phenomena (e.g. the effect of regularization [Nakkiran et al., 2020]).  A major strength of the paper is the focus on finite-width models,  and the analysis of the cross entropy loss, which are of particular interest to practitioners.There are however a few weaknesses, in my opinion, of this analysis:
* The  authors  claim  that  the  only  interesting  term  to  analyze  when  the model grows is the Hessian’s smallest non-zero eigenvalue.  There are however  in  the  bounds  other  quantities  that  can  hide  a  dependence  on the size of the model, and on which the authors do not provide sufficient comments - in particular the constants $A_{θ_0}$ and $B_{θ_0}$.  While the role of these constants is conceptually clear (i.e. the spectrum of the covariance of the gradients at the optimum is close to the one at initialization), it is not obvious that these constants are independent of the size of the model.Can the authors provide a more precise comment on these constants?
* The provided analysis considers the size of the model,  independently of its architecture.  However, growing a model by increasing its depth or its width results in different training dynamics.  Can the authors comment on  this  point?   Can  their  analysis  be  adapted  to  take  into  account  the network’s architecture?  What happens if, for example, the difference in width between the hidden layers is larger than 20?
* Recent works suggest the presence of a triple rather than a double descent in  neural  networks  [d’Ascoli  et  al.,  2020].   The  study  of  the  eigenvalues of the Hessian can only provide an explanation for a single descent (by the nature of the random matrix theory it is built on).  Can the authors comment on this line of works and its link to their analysis?

Significance of the experiments: The  experiments  provided  in  the  paper  are  in  line  with  the  theory  and  provide an interesting support for it.  There are however a few weaknesses in the experimental section:
* In figure 1, the authors use a different size of subset for the 2 and 3 layer networks.  While the results show a drop of the eigenvalue and a peak of the test loss in the expected threshold in both cases, it would probably be better to use similar training subsets for a matter of comparability.
* Both the initialization of the network and the randomly chosen training subset can influence the results.  I think that it would be better to show averaged results across different seeds (10 seeds would be great, but given how complicated and time consuming to sweep over the model size, 5 can already be enough to give an indication on the consistency and variance of the results).
* The authors mention results on MNIST and CIFAR 10 in the main text,but they are not available in the appendix. It would be interesting to show the consistency of the results across different datasets.

Minor comment: The authors cite a recent work in the discussion section that suggests that thespectrum of the features of the penultimate layer of the network can explain the double descent phenomena [Kuzborskij et al., 2021], and claim that the currentwork  contradicts  this  conjecture.   There  is  however  no  inherent  contradiction between the two approaches, they study two different quantities.  These workscan in the contrary be complementary, e.g. by indicating two different thresholds(which goes in the direction of a triple descent).
summary_of_the_review: The paper provides a novel analysis tool for the double descent phenomena, that is particularly useful in the case of finite width neural networks.  While the work can be of high interest to the community, it has some weaknesses, in some of the theoretical results and in the empirical validation that can limit its impact.This is why a recommend acceptance, but I think the paper can be improved.

Post rebuttal: The authors addressed most of my concerns, as well as most if the other reviewers' comments and questions. The resulting paper is substantially improved, and I therefore recommend accepting it.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The current work deals with the generalization properties of finite-width DNNs from the Hessian perspective combined with the influence functional approach. Based on several assumptions, they derive a lower bound, bounding the loss by a quantity proportional to the inverse of the minimal non-zero Hessian eigenvalue. In addition, by assuming the Hessian is close to a random matrix, they estimate its lowest (non-zero) eigenvalue and show that their bound can reflect double descent behaviour at the anticipated interpolation threshold. They do so both in the context of MSE loss and cross-entropy loss. Their theoretical results are compared with small scale experiments on downsized (n=500) MNIST datasets. 
main_review: This work derives an interesting and to the best of my knowledge new, lower bound on DNN generalization and draws connections with a timely topic - the behaviour of finite width DNNs. The assumptions, proofs, and references to the relevant works are laid out in an accessible manner. A simple picture of the double descent behaviour arises from their work, creating a direct link with the spectrum of Wishart matrices.

Notwithstanding I found the work lacking in the following aspects - 

** Assumptions: To derive their bound, the authors make 6 assumptions (A1-A6). Some of which seem quite reasonable however for some I didn't find sufficient support. 

Concerning the A2 assumption, arguing a certain term in the Hessian is zero, the authors provide two empirical references supporting this (one being very recent). However, looking at these Refs. I could not find where this is shown or implied. In addition, the authors argue that the loss term ($l_i$) would be close to zero near the interpolation threshold - but on what scale? Notably, the A2 assumption is crucial for one of the main novel features of their bound -- being robust to zero Hessian eigenvalues --- however, as far as I could tell the crux of it is the fact that $C$ always accompanies $[H+\lambda I]^{1}$ and if $C=H$ zero eigenvalues do not contribute. Thus any small deviation of $C$ from being aligned with $H$ may affect this result. 

Concerning the A5 assumption, here the authors relate the low and high eigenvalue of the spectrum of the Hessian after training to that before training by some non-universal constants. For this to be of any quantitative use, these constants should be of order $1$ (otherwise the assumption is null). The authors justify this using experiments, however, due to the hardness of computing the low Hessian eigenvalues - these experiments are quite limited in scope. This again is a very crucial assumption - it allows them to glance over the difference between trained DNNs and DNNs at initialization. As such I think it needs more extensive support. 

** Tightness of lower bound - in their experiments the authors compare the lower bound with the actual population risk. The aim is to show they exhibit the same trend however if I understood correctly, a noticeable difference appears in their scale, with the bound being orders of magnitude lower than the actual risk slightly away from the interpolation threshold and a factor of $10$, or $e$ smaller at the interpolation threshold. This, along with the assumptions and low amount of experiments, raises concern in how intimately does their bound really affects and reflects performance. 

** Other real-world effects - The bound does not depend much on the high eigenvalues of the Hessian, which according to several works also affect generalization quite strongly. It also misses out on the fact that infinite width DNNs often under-perform their finite width counterparts thereby showing evidence of a second over-parameterization scale, not tied with the interpolation threshold (see for instance https://arxiv.org/pdf/2106.06529.pdf). It's true that this happens less for fully connected DNNs considered in the current work, but that's maybe a testimony against taking conclusions on finite width fully connected and applying it to real-world CNNs. In addition, while it may or may not be that the minimal Hessian eigenvalues of the true Hessian will provide a second change of trend - I find it hard to see how the analytical approach, modelling the latter as a random matrix, will provide such a second scale. 

** Experiments - Since this work relies on various assumptions, its potential impact is tied with verifying these assumptions. In this aspect I found the work lacking - experiments we're only done on fully-connected DNNs trained on MNIST1D reduced to 500 points. The main text promised some results on CIFAR10 but I couldn't find those in the supplementary material. In addition, I didn't find the little bump in Figure 3 (left) convincing as evidence for an interpolation peak.  

summary_of_the_review: An interesting exploration into the low eigenvalues of the Hessian and their links with generalization in finite DNNs. Some underlying assumptions need more support, the bound seems non-tight and not clearly reflective of the actual test loss, and the relevance to real-world settings, where other effects come into play, is unclear. 

Following discussions with the authors I currently raise my score to 8
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper derives an expression of the population risk with influence function, and then use that to derive a lower bound on the population risk, which provides an explanation for double descent phenomena in the finite-width regime at the optimum point. The paper provides experiments to support the theoretical arguments. Moreover, the authors investigate how the choice of loss functions affect the double descent phenomena.
main_review: The topic and the goal are both very important. However, the theorems are crucially limited and incremental. Theorem 3 simply rewrites the population risk by putting the difficult term into the expectation or population covariance of the gradient. The right-hand of (1) cannot be evaluated because of the population covariance. In the most cases, if we can evaluate it, then we can evaluate the population risk too. Moreover, the second term includes the trance of the matrix of size of the number of parameters. Thus, this can grow linearly as we increase the number of parameters in the worst case, which is not good for over-parametrized regime that this paper focuses on; otherwise, the first term is no longer negligible.  

The proof of Theorem 3 is very unclear regarding the O(n^2) term. It reads “when |S| = n is large enough to ignore O(n^2) terms, the (infinitesimal) definition of influence function is equivalent to using the finite-difference form”. However, the O(n^2) term can also grow in practice as we increase n. Thus, the authors must include the exact expression of the O(n^2) term and a more precise argument on why we can ignore this term. 

In Theorem 4, Assumption 5 is problematic in many ways. First of all, the main goal of paper, as stated, is to avoid the neural tangent kernel regime, which is known to be not practical, and to analyze the practical finite-width regime of neural networks. However, Assumption 5 almost results in the neural tangent kernel regime, because the covariance contains neural tangent kernel by the chain rule, and the Assumption 5 restricts the practical change of the neural tangent kernel during the training, which is exactly the main issue of the neural tangent kernel regime. In the neural tangent kernel regime, the neural tangent kernel is not allowed to change a lot, which means that neural networks in the neural tangent kernel regime is equivalent to linear models with a random feature (or the initial kernel). The proof of this paper is not addressing this main limitation.

Minor comments: why equation (10) in Theorem 10 does not contain O(n^2) term? There is a typo on page 3 with undesired space before `let us consider who the parameter estimator’. 

Update after author response: the authors' responses do not address my concerns. Assumption 5 (and the minimum eigenvalue in the revised version) is problematic. The modes studied in this paper are essentially still in the lazy/kernel regime. Based on these, I keep my original score.
summary_of_the_review: The topic and the goal are both very important. However, the theorems are crucially limited and incremental as explained above. Moreover, the main claim to analyze the finite-width neural networks outside of the neural tangent kernel regime is not well supported because of the Assumption 5.
review_title: null

Meta-review: This paper studies the important statistical phenomenon of double descent, a very timely topic, using influence functions, and thereby derives lower bounds for the population loss. The reviewers generally appreciated the conceptual as well as the technical contributions in the work, but argued that the set of assumptions taken by authors can potentially diminish the significance of the analysis. This, as well as additional issues regarding the empirical and the analytical support for the modeling assumptions (and the implied scope of applicability, i.e. lazy\kernel vs. rich regime) have generated considerable discussion between the reviewers and the authors. Along the process, major and minor concerns were addressed to the satisfaction of the reviewers, resulting in a substantial improvement of the overall evaluation. Thus, this AC recommends acceptance.
Decision: Accept (Poster)