Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper investigates the phenomenon of double descent, also referred to as "more data hurts", in high dimensional linear regression using the least square estimator.  In the same setup, previous sharp results were already established in the asymptotic regime. Non-asymptotic results are also known but are less precise. The authors of this paper try to provide a new type of results that fill the gap between the two regimes (asymptotic vs non-asymptotic). To do so they have managed to derive second order (CLT type) asymptotic results for different risks based on more refined random matrix theory results.

#######################################################################
pros:

Asymptotic confidence intervals for different prediction risks  are derived. These results seem new. One of the main applications of the main results is a better explanation of the more data hurts phenomenon. Indeed, using just first order asymptotic results we had to take both n and p to infinity and compare the ratios p/n. Using the finite-sample results in this paper we can now fix p (large enough) and see that, in the overparameterized regime, a larger n leads to a larger prediction risk. 

#######################################################################
cons:

While the statistical decomposition of the risk was already known, the novelty of the results in the present paper are only based on known results from random matrix theory which limits its theoretical contribution. Also, Section 4 needs more discussion. As a reader, I was felt abandoned at the end of Section 4, where the it just ended after stating the results. I think at this stage the authors should take the time to explain more their results and how they are different from previous ones. In particular by saying "explicitly" what happens when the sample size grows. Although that was clear from your introduction, but it is always good to draw conclusions for the reader after you state your results and remind your contributions.

#######################################################################
Score:

This paper is well written and the proofs seem sound to me. Overall, I think the present paper is marginally above the acceptance threshold because it seems like an incremental work over previous asymptotic results by using well established CLT results from random matrix theory.

Typos:

* In assumption (B1), did you mean $\lambda_{\min}$ instead of $\lambda$?



review_title: Review of Provable More Data Hurt in High Dimensional Least Squares Estimator

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper provides the central limit theorem type of results for generalization error of high-dimensional least squares estimator. 

Strength: It is nice to know that the finite sample prediction error converges to its asymptotic limits in the CLT style. Previous results have shown that the prediction error converges to the asymptotic limit, but it is unclear how fast the convergence speed. This CLT type of results provides the answer and this explains why empirical simulations have shown good accuracy for a sample size of just 300-500. I think it is a nice piece of result to be added to the current double descent literature.   

Weakness: One major concern is although CLT type of results is interesting, whether the overall level of contribution of the paper meets the standard of acceptance or in other words whether the story of CLT is complete. This paper seems to be on the borderline and the story looks to be only half-written. First, this paper only focused on the cases when features are isotropic or signals are isotropic. Recent double descent works have extended this setting to both anisotropic features and anisotropic signals (e.g. https://arxiv.org/abs/2006.05800) and those settings are more realistic and more interesting. Secondly, although $\sqrt{n}$ convergence is probably the optimal speed, it is good to have a lower bound result to rigorously show it. The story of this paper will be more complete if the authors can also show results on these two points.  

In summary, I like the CLT type of result, but I recommend a weak accept because of the simple setting. I will give an 8 if the authors can extend their results to the most updated settings in this linear regression model and complete the lower bound results. Further, I think the authors can simplify their theorems and assumption quite a lot once they study the general anisotropic settings. It gives better clarity.   
review_title: A good addition to double descent literature. Weak Accept because of the setting of isotropic features or signals. 

final_score: rating: 7: Good paper, accept
review_content: **Summary**: In this article, the authors characterized the second-order fluctuation of the prediction risk of the (min-norm) least square estimator, by assuming an underlying noisy teacher model $y_i = \beta^T x_i + \epsilon_i$, in the regime where the data dimension $p$ and the number of training samples $n$ grow large at the same pace. Results in both the under-parameterized (Theorem 4.1 and 4.2) and over-parameterized regimes (Theorem 4.3-4.5) were provided, under the statistical model where the data $x_i$ are zero-mean random vectors with **generic** i.i.d. entries and then "rotated" to have some possible covariance structures. Numerical experiments for relatively small values of $n,p$ were conducted to support the theoretical assessment.

**Strong points**: The authors provided a solid contribution to the theoretical understanding of high-dimensional (over-parameterized) machine learning systems that are of growing interest today. The technical tool of the CLT for linear spectral statistics introduced here is popular in RMT literature and may be of independent interest to the machine learning community. To the best of my knowledge, there are very few results on the second-order fluctuations of the prediction, one possibly relevant paper is "Asymptotic normality and confidence intervals for derivatives of 2-layers neural network in the random features model" at NeurIPS 2020.

**Weak points**: This article could be strengthened by summarizing more explicitly the lessons to be learned for practitioners.

**Recommendation**: This is a good paper that made solid contributions to the theoretical understanding of high-dimensional least squares estimators and consequently, shed interesting light on the future design of more elaborate machine learning systems. I thus recommend it for publication at ICLR.

**Detailed comments**: 

* Sec 1 introduction: "However, the existing asymptotic results, which focus on the first order limit of the prediction risk, cannot exactly guarantee the more data hurt phenomenon": it would be helpful to provide a more concrete illustrating example for the insufficiency of the first-order analysis, or perhaps simply refer to the discussion above Figure 1 below.
* The x- and y-axes are hardly visible in Figure 1, and the same applies to other figures in this article as well.
* below (1): is the independence between the entries of $\mathbf{x}_i$ necessary, should this be stated here?
* Theorem 4.3, 4.4 and 4.5: it would be helpful to comment here that only the case of **identity data covariance** is considered here, is the general covariance case easily follows, with just more complicated expressions, or there may be some technical challenge to master?
* Since the theoretical results in the paper are "universal" with respect to the distribution of the entries of $\mathbf{x}$, it would be good to provide numerical experiments on non-normal data to better illustrate the contribution of this work, or at least, to mention explicitly that experiments **on more general data distribution** are available in the Appendix.
* In Figure 3, we observe that the statistic $T_{n,0}$ fits less well the theoretical prediction (at least compared to $T_n$ in Figure 2 or $T_{n,1}$ in Figure 3), could the authors provide any theoretical justification or intuition on this?


**After rebuttal**:  I've read the authors' feedback and my score remains the same.
review_title: Solid contribution in characterizing the second-order fluctuation of high-dimensional least squares estimators

Meta-review: This paper derives CLT type results for the minimum $\ell_2$ norm least squares estimator allowing both n and p to grow.

Pros:
As one reviewer puts it: Asymptotic confidence intervals for different prediction risks are derived. These results seem new. 

Cons:
It's not clear what has been gained by having these results, other than having them.

Reasoning:
Staring at Figure 1 for a while, what jumps out is how little the CI matters. Unless $p\approx n$, the band is essentially uniform around the first-order result derived elsewhere. The claim the authors seem to make at the bottom of page 1 is that, "supposing I have 90 observations and 100 predictors, it may not be so bad to collect 8 more observations. Even though on average I'm worse off, perhaps not for my data?" The flip side of this argument is "why am I using min-norm OLS"? I think that the authors are making the wrong argument in this paper. The point of analyzing this problem is not to understand what happens when $p\approx n$ but to understand why $p \gg n$ is good, and thereby try to justify parameter explosion in deep learning. I should be looking at the left side of Figure 1, not the center. Even the language "more data hurt" is the wrong statement. The point isn't to show that collecting data is bad but to justify adding parameters. We should say "more parameters help". If the authors' proof technique added to the understanding in that case, then this paper would be more convincing. As is, I find it hard to overrule with the reviewers who appear to be mainly on the fence with little enthusiasm.

Decision: Reject