Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the generalization risk of ridge and ridgeless linear regression under Gaussian data and Gaussian noise settings. The limiting bias and variance are described in closed-form. The analysis leverages random matrix theory and CGMT. The authors show that sample-wise multiple descent phenomenon can take place or be avoided if optimal regularization is applied.
main_review: The paper is well-written and technically sound as far as I can tell. I enjoy reading Theorem 1, which uses two different approaches to derive the same limits in a way that can mutually corroborate each other, and believe this closed-form result will have future impact on other topics. The theoretical result is further supported by clean experiments up to high precision. I believe it is a mathematically strong paper that is among top quality in this venue.

However, I have reservations regarding the motivation, at least it is not nicely explained.
1. As the title suggests, the authors are working on sample-wise multiple descents. They made this clear in the INTRODUCTION by citing (Nakkiran et al.,2021;Chen et al., 2020b; Min et al., 2021). However, I believe the authors are working on something else by their setup in section 1.1 'Asymptotic Regime' as $n,d\to\infty$. In words, not only the sample size goes to infinity but also the feature size goes to infinity in proportion. First of all, this is not sample-wise descents in prior works, where $d$ is fixed! A better description of this work is on sample-feature-wise multiple descents. Second, this seems to limit the application as in most tasks the number of features is fixed. Whether the theoretical results in this work shed any light on real cases needs at least empirical evidence.
2. Can the authors give some motivation on why to assume $\|\Pi_i\theta^*\|_2→\eta_i$. I understand its use in theory but what does this assumption mean in words?

Other minor points: the paper seems very sloppy, e.g. Page 4 'Bias-Variance Decomposition of Expected Excess Risk', the first line of equations misses a square; in CONCLUSION section, the first sentence should have ridge regression besides ridgeless; in the same section, "risk curve.Moreover"->"risk curve. Moreover"; there are multiple places where the lines are out of margin, e.g. Equation (8); the appendices are not well-referenced, e.g. after reading Theorem 1, I tried to look for the proofs but there is no hyperlink that should link to Appendix C. Same thing happens to other results wherever appendices should be clearly referenced.
summary_of_the_review: This paper is technically very strong and well-supported by experiments. I believe it is among top 20% of accepted ICLR papers. However, the motivation of the problem is less clear which requires non-trivial improvement.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Authors study the generalization risk of ridge and ridgeless linear regression. It is assumed that the data follows a multivariate normal distribution and there is also an assumption on the spectrum of the covariance matrix. Among the contributions, the authors show a formula for the limiting bias and variance, show that sample-wise multiple descent happens when the covariance matrix is highly ill-conditioned, and study optimal regularization.
main_review: Strengths
* The paper is well written
* Technical contributions are sound and somewhat interesting

Weaknesses
* Some assumptions are unclear if they are mild or why they are assumed in the first place. For instance, assuming fixed eigenvalues looks like a rather strange assumption at first glance, and authors do not provide any intuition why this is assumed and how restrictive it is. To me, that assumption is an artifact for the proof techniques, which undermines the contributions of the paper.

summary_of_the_review: After my first read of the paper, I am recommending a weak accept. My concerns are more about the assumptions and the lack of discussions about them. I would appreciate it if the authors can comment on this matter.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper builds on a very recent line of work studying the “multiple descent” phenomenon. 
Multiple descent is known to occur along many axes: (i) number of parameters, (ii) train time, (iii) amount of train data. The current paper focuses on studying the theoretical rates for (iii) in the asymptotic regime where the number of samples and the dimensionality of data tend to infinity at similar rates.  This covers both under and over-parameterized settings.
In this limiting regime, the main results of the paper are:
1.	Computing formulae for the excess risk of the least squares estimator and the ridge regression estimator in a specific setting.
2.	Using 1, they show that if the covariance matrix of data is ill-conditioned, then multiple descent can happen.
3.	They also show that under an assumption on the scaling of the projections of the true parameter to the eigen-spaces of the eigenvalues of the covariance matrix, an optimal amount of regularization ridge regression estimator avoids multiple descent even in anisotropic settings which is novel.


main_review: Strengths of the paper:
1.	The paper tackles an important problem very relevant to the ICLR community.
2.	It provides a deep theoretical analysis of a specific setting and the proofs appear non-trivial. The main contributions of the paper are novel.


Weaknesses of the paper:
Overall the paper is reasonably well-written but the writing can improve in certain aspects. Some comments and questions below.
1.	It is not apparent to the reader why the authors choose an asymptotic regime to focus on. My understanding is that the primary reason is easier theoretical tractability. It would help the reader to know why the paper focuses on the asymptotic setting.
2.	It is unclear in the write-up if sample-wise descent occurs only in the over-parameterized regime or not. Pointing this explicitly in the place where you list your contributions would help. More broadly, it is important to have a discussion around these regimes in the main body and also a discussion around how they are defined in the asymptotic regime would help.
3.	The paper is written in a very technical manner with very little proof intuition provided in the main body. It would benefit from having more intuition on the tools used and the reasons the main theorems hold.
4.	Given that prior work already theoretically shows that sample-wise multiple descent can occur in linear regression, the main contribution of the paper appears to be the result that optimal regularization can remove double descent even in certain anisotropic settings. If this is not the case, the paper should do a better job of highlighting the novelty of their result in relation to prior results.

I am not too familiar with the particular techniques and tools used in the paper and could not verify the claims but they seem correct.
summary_of_the_review: The problem of multiple descent is an important scientific question which is relevant to the ICLR community. The contributions of the current paper are novel. The techniques used appear novel as well. However the degree of significance of the results is not fully clear. The paper would benefit from a deeper discussion around this.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: Derived the asymptotic generalization error (squared loss) of the minimum $\ell_2$-norm interpolator under general Gaussian design. The precise asymptotic formulas reveal that the risk curve can be non-monotonic and exhibit multiple peaks (in the variance term), depending on the spectral properties of the feature covariance matrix $\Sigma$. 
main_review: This authors devoted a lot of effort to rigorously prove the generalization error formulas in the proportional limit.  
Unfortunately, my impression is that most of the theorems in this submission are essentially re-derivation of existing results from the following papers (some of these prior results actually allow for weaker assumptions):   
* Dobriban and Wager, Annals of Statistics 2017. https://arxiv.org/pdf/1507.03003.pdf. 
* Wu and Xu, NeurIPS 2020. https://arxiv.org/pdf/2006.05800.pdf. 
* Richards et al., AISTATS 2021. https://arxiv.org/pdf/2006.06386.pdf.
* Amari et al., ICLR 2021. https://arxiv.org/pdf/2006.10732.pdf.  

Note that all of these papers have been publicly available for more than one year, so I think it is no longer the case that this new submission can be considered as concurrent work. 

Specifically,   
1. in terms of the risk formula, [Wu and Xu] and [Richards et al.] derived the limiting risk under the same problem setup for general regularization parameter $\lambda$, whereas [Amari et al.] focused on the bias-variance decomposition in the ridgeless limit. All these works built upon a generalized Marchenko-Pastur theorem, as well as [Dobriban and Wager], which showed that the limiting variance can be related to the Stieltjes transform and its derivative (sometimes referred to as the "derivative trick"). 
These results cover Theorem 1 and 2 in the current submission. 
2.  The two block ($m=2$) case was already studied in Section 3 of [Richards et al.], Appendix A.4 of [Amari et al.], and Section 5 of [Wu and Xu]. In particular, the closed-form expression of the Stieltjes transform (and therefore the limiting variance) has been derived in Appendix A.6 of [Richards et al.] and Appendix D.10 of [Amari et al.], and the resulting "multiple descent" has also been reported. These results cover Theorem 3 and Corollary 2 in the current submission. 
3. Theorem 4 in this submission is analogous to Proposition 7 in [Wu and Xu], which states that under an isotropic prior on the true parameters $\theta^*$, the optimally-tuned ridge regression estimator has monotonically decreasing generalization error with respect to $\gamma=n/d$, and thus avoids multiple descent; this is basically equivalent to the projection formulation in Theorem 4 (the bias term in the generalization error only depends on the projection of $\theta^*$ onto the eigenspace of $\Sigma$).  


**Additional Comments** 

- At a high level, I personally do not find counting the number of peaks in the risk curve to be that interesting of a research problem, as least in the case of minimum $\ell_2$-norm interpolation. It is rather intuitive that one can engineer the features such that the sample covariance matrix becomes ill-conditioned once in a while, and it is not clear if this specific phenomenon has wider implications in practical machine learning problems. 

- (minor) Note that the Gaussian assumption has already been relaxed to bounded moments in the Stieltjes transform-based analysis, e.g., [Dobriban and Wager] and [Wu and Xu]. Hence I'm not sure if there's any benefit of introducing CGMT to this problem (which limits the analysis to Gaussian features). 

- (minor) In Corollary 2, why is $\varrho\to\infty$ a well-defined limit? Intuitively, wouldn't this violate the condition that the eigenvalues do not depend on $d$ which goes to infinity?
summary_of_the_review: Due to the significant overlap with prior results, I cannot recommend acceptance. I'm happy to adjust my score if the authors can clarify how the current submission differs from (and improves upon) all the aforementioned papers.
review_title: null

Meta-review: The authors analyze linear regression with gaussian covariates in an
asymptoptic setting, where the number of examples and the number of
covariates go to infinity together.  They identify conditions
on the covariance under which "multiple descent" occurs, and
conditions under which a regularization removes this effect.

Concerns were raised that the overlap between this paper and previous
research was too substantial for it to be published in ICLR.  These
persisted after the authors' response and the discussion period.
Decision: Reject