Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the double descent (DD) phenomena for least squares and proves upper bounds for excess risk of gradient descent. For both cases with and without label noise, the upper bound involves a term $E[(1-\alpha \hat{\lambda}\_{\min}^+)^{2T}]$, where $T$ is the training time, $\alpha$ is the learning rate, $\hat{\lambda}\_{\min}^+$ is the smallest positive eigenvalue of the covariance matrix of training inputs.

The most important observation in this paper is that the peak of the double descent curve around $d \approx n$ can be related to $\hat{\lambda}\_{\min}^+$. By a non-asymptotic version of Bai-Yin limit, $\hat{\lambda}\_{\min}^+$ could be very small when  $d \approx n$, and thus $E[(1-\alpha \hat{\lambda}\_{\min}^+)^{2T}]$ can be very close to $1$ when $T$ is finite.

Experiments show that $\hat{\lambda}\_{\min}^+$ for intermediate features correlates with the double descent curve of test error.
main_review: I like the idea of relating DD to the smallest positive eigenvalue $\hat{\lambda}\_{\min}^+$ of the covariance matrix, which seems to give a fairly new perspective on the DD curves. But I'm not an expert in DD as I only read a few related papers. Thus I think a detailed comparison with previous papers is important for me to have a proper evaluation for this paper. However, the related work section is in the appendix, not in the main body of the paper. Also, comparisons with some closely related papers are not detailed enough. The authors mentioned that [Derezinski et al., 2020], [Rangamani et al., 2020], [Hastie et al., 2019] also noted that $\hat{\lambda}_{\min}^+$ is important in explaining double descent, but the key difference to the current paper is not very clear to me if I only read the related work section. I would suggest the authors add more details:

1. What are the assumptions on the data distribution in previous works? How do they compare with those in the current paper?
2. How do those papers find the connection between DD and $\hat{\lambda}_{\min}^+$ without studying GD optimization?
3. If they prove double descent without considering GD optimization, does it mean optimization is not a crucial factor to make double descent occur? The authors claim that the current paper is superior as it considers GD optimization, but it should be justified that GD optimization is crucial in the first place.

Unlike some previous papers, this paper does not assume an explicit formula for the data distribution. This is an advantage of this paper as it can hold for broader settings. However, this also makes it impossible to derive an exact formula for excess risk. Alternatively, the authors study the upper bounds, but no lower bound is given. Lower bounds are especially important for explaining the peak because having an upper bound $\approx 1$ can be either because there is a peak or the upper bound is not tight enough. I would like to see the authors' argument about the tightness of the upper bounds. Empirical evaluations for those upper bounds may also help.
limitations_and_societal_impact: The major limitation of this paper is that it only provides the upper bounds, as discussed above.

Besides this, the theoretical analysis of this paper only holds for least squares and cannot be extended easily to deep neural nets. But the authors did MLP experiments on MNIST to show that similar phenomena can happen for intermediate features, and I understand that studying deep neural nets is hard.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper studies the double descent phenomenon of linear least squares problems from an optimization point of view. Specifically,  the contributions of the paper lie in two parts: (1) for a linear least squares problem, an upper bound for the excess risk after T gradient descent iterations is derived by a contraction property of GD. The upper bound depends on the smallest non-zero singular value of the feature matrix, which is also related to the smallest nonzero eigenvalue of the Gram matrix. (2) The concentration of the smallest nonzero eigenvalue around its population counterpart is studied, and the discrepancy of the two is controlled. The control is provided separately for under-parameterized and over-parameterized cases, using existing random matrix theories. 

Combining the two components above, an upper bound of the excess risk is provided that shows a peak at the interpolation threshold. The bound depends on the number of parameters d, the number of data n, as well as the number of iterations T, hence it is optimization related. This bound only characterizes the peak at d=n, but does not characterize the first descent in the under parameterized regime. 

Finally, numerical experiments on nonlinear models such as neural networks are provided to show the similar double descent phenomenon and the behavior of the smallest singular value of the feature matrix. Here, the feature is taken to be the output of the second last layer. 
main_review: This paper tries to study and explain the double descent phenomenon from a new perspective. However, it does not provide much new insight for the phenomenon. The reasons are as follows:
1. The object lying in the center of the analysis---the smallest nonzero eigenvalue of the Gram matrix---is the well known cause of the double descent phenomenon in linear least squares problems (including the random feature models), and is also extensively studied. In the works focusing on minimal norm solutions or ridge regression solutions, the same quantity is also studied and identified to be the factor that leads to the DD phenomenon. 
2. The upper bound for the excess risk only considers the smallest nonzero eigenvalue of the Gram matrix, which means it only controls the slowest component in the dynamics. Hence, the bound becomes tight only when the number of iterations, T, becomes large. Before this, the components corresponding to big eigenvalues dominate the dynamics and the DD phenomenon does not appear. This is showed by the empirical results in the paper. However, once T is sufficiently big such that the component of the smallest eigenvalue dominates the dynamics, the GD solution is already close to the minimal norm solution or the l2 regularized solutions studied in previous works. Therefore, the so-called "the roll of optimization" does not make much sense. Especially considering that the loss function is actually convex and any reasonable optimization algorithm will converge to a global minimum. 
3. For a linear least squares problem, the GD solutions and the corresponding population risk can be written down in close form. Hence, the reviewer does not see the necessity to derive the excess risk bounds via indirect approach such as (\Delta, M)-admissible. Also, the (\Delta, M)-admissible condition does not help extend the analysis to non-linear cases. 

Some other comments:
1. Shown by numerical experiments on neural networks, it seems the peak of the generalization error happens when the width approximately equals the number of data. This is different that shown in Belkin et.al, in which the the generalization error peaks when the number of parameters = number of data * number of classes. Hence, this is like a different kind of "double descent". It is possible to provide more explanation on this phenomenon using the techniques employed in the paper?
2. Some notations are confusing. For example, (a) the excess risk is denoted by E(w^*) while w^* is actually a fixed point. It is better to use E(A_S(W_0)) to highlight the dependence of the excess risk with the GD solution.  (b) the data us denoted by a capital X, which it is mentioned that vectors are denoted by boldface lower case letters. This causes confusion. 
limitations_and_societal_impact: The authors have addressed the limitations and societal impact of the work.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper studies the phenomenon of double descent (DD), and how different parameters of the problem affect this phenomenon. First, the authors show several theoretical results on linear predictors in the over-parameterized regime, with and without label noise. These results indicate that a certain eigenvalue of the data matrix affects the generalization error. Next, several experiments are shown on the MNIST and FashionMNIST datasets, that there is a correlation between this eigenvalue and the DD phenomenon.
main_review: I think that DD is still not well understood, and studying it is important and interesting. Also, the connection between DD and certain parameters of the data or optimization is an interesting observation. On the other hand, I think this paper makes a weak case for why these parameters actually affect DD, especially on the experimental part, and vaguely connects the theory presented in the paper with the experiments. In more details:

For the theoretical part:
1) I think the main idea is nice, studying linear regression in the case where d>n (more parameters than data examples), which is a less studied case in the literature. 

2) Viewing section 2 as a whole, it is hard to grasp a single conclusion on how the excess risk behaves. It would have been much clearer if there was a single theorem that shows a bound on the excess risk when d goes to infinity. In both theorems 2 & 3, there are terms where it is not clear how they behave (e.g. E[||w^*||^2]_{I-M}).

3) To emphasize the previous point, two parameters are considered (n and d), and throughout the section it is unclear which one is considered to be larger. I assume the authors meant that d>n (since this is the over-parameterized case), but in line 163 (and Appendix F) it seems the E[||w^*||^2]_{I-M} term only goes to zero with large n, as well as the noise in Theorem 3. What happens in the over-parameterized regime when n is fixed and d goes to infinity? I think this is the interesting case when studying DD.

4) Section 3 is very unclear. What are the assumptions made in the equation after line 216? What are the main conclusions of this section? There are very long paragraphs, where the bottom line isn’t clear.

For the empirical part
1) I think this is the main weak point of the paper. The connection between the experiments and the theory is not well grounded. Also, the experiments are very lacking and not convincing enough.

2) To emphasize, the theoretical part focuses on a certain eigenvalue of the data matrix. This eigenvalue has no connection at all to the optimization process and is fixed. On the other hand, in the theoretical part the authors consider the eigenvalue of the output of some intermediary layer, which changes through the optimization process. Why not take the eigenvalue of the data itself? And if the authors already decide to take the eigenvalue of an intermediary layer, I suggest taking the eigenvalue of all layers and comparing them. 

3) The only datasets used are MNIST and FashionMNIST which I think are very small and not very hard to learn, even with simple models. To give a more convincing argument I suggest using larger and harder datasets (e.g. CIFAR 10/100, ImageNet).

4) The models considered are very small, e.g. one hidden layer and three hidden layers. I suggest experimenting on more realistic models and see if this eigenvalue has the same effect. Also, to experiment on other architectures such as ConvNets.

5) There are no experiments on regularization (e.g. L1/L2, Dropout, BatchNorm). Regularization techniques might mitigate the effect of this eigenvalue on the DD phenomenon. Without these experiments, it is hard to evaluate whether this phenomenon is due to the effects of this eigenvalue, or some other property that can be mitigated using regularization techniques.

6) In line 308 it says that ablation studies are in Appendix H. The only experiment in Appendix H is a three-layer network with or without skip connections. I suggest adding significantly more ablation studies to give a more convincing case.

Some more issues:

1) Why do the authors show the experiments for a different number of iterations? The reason is not explained in the paper, this is very confusing and takes three times as much space. I think the point of DD is looking at a trained model, if the authors want to emphasize some idea for an untrained model (e.g. after T=1000 iterations) then they should explain it.

2) There are confusing notational issues throughout the paper: the parameters alpha and T are shown in the introduction, but are defined only in section 2. Some notations are used in the main part of the paper, but are only defined in the appendix (e.g. ||A||_M norm). It is OK to define some notations in the appendix, but if something appears in the main part of the paper, then I think it should be defined there.

3) Line 131, what does it mean that \Delta and W_0 are independent? Each coordinate of W_0 is i.i.d Gaussian, so how can it be dependent on \Delta. Is it meant to be that \Delta is independent of d?

4) In all the theorems, why is W_0 upper case? This is a vector, and the notations state that vectors are lower case, also w and w^* are lower case.

5) The figures are extremely small and hard to read. I suggest the authors to remove the different number of iterations experiments and just show how the trained model behaves, this will save much space and will allow to give much bigger and clearer figures.

6) In lines 699-700 it states that “the deeper the network the harder it is to train them”, while Figure 6 shows the opposite, that deeper networks achieve smaller test error. 

7) The title is “On the Role of Optimization in Double Descent..”, while the paper studies how a certain eigenvalue of the data matrix affects DD. 

8) The "related work" section is in the appendix. Although this is allowed, in my opinion, this is bad practice. This section is a crucial part of the paper and helps the reader to evaluate its contribution and novelty, based on previous works that were done in the same area.

Some typos and other minor issues:

1) Sometimes “optimization” is used and other times “optimisation”. Both are OK, but the authors should be consistent and choose one form.

2) Title of Section 3: parammeterization → parameterization

3) In figure 1, “The first row demonstrates behavior of (1)...” what is (1)? The hyperlink points to the introduction section.

4) First sentence of appendix F, should it be the over-parameterized case?


To improve the paper I suggest making a more thorough experimental study. This includes more realistic datasets, different architectures, Verify whether the conclusions hold with different regularization schemes, and conduct more ablation studies. Also, to connect the empirical results to the theoretical study I suggest looking at different architectures and network depths, and calculate the eigenvalue for more intermediary layers (including for the data itself). It will also help if the theoretical part will have a single corollary or theorem on how the excess risk behaves when d->\infty, without any unclear terms such as E[||w^*||^2]_{I-M}.

-------------Update after rebuttal---------------

After reading the author's response my concerns remain, and I retain my score.
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work
review_title: null

Meta-review: Reviewers reached a consensus by which the paper is not ready for publication.  Several concerns were raised, most notably:

* Only an upper bound on the excess risk is derived, which is insufficient for establishing a double descent phenomenon (for that, a matching lower bound is required).

* While experiments indicate that the upper bound may be tight after many iterations, it seems that in the early phases of a run it is not.  This is particularly problematic since in late stages of a run the model may in fact be close to convergence, and at convergence optimization reaches the Moore-Penrose solution, which was heavily analyzed in prior work (hinting that the regime in which the analysis is valid is one that is already well understood).

* The experiments on deep neural networks are somewhat disconnected from the theory, and this warrants a more thorough empirical investigation.

I encourage the authors to make use of the above feedback in revising their paper towards future submission.
Decision: Accept (Poster)