Least Squares Regression Can Exhibit Under-Parameterized Double Descent

Summary

The paper aims to understand the phenomenon of double descent in regression, and helps complement existing knowledge about the phenomenon by proving that double descent can occur even in the under-parametrized regime, going against previous intuition. They also prove that the peak in the norm of the estimator does not imply a peak in the risk.

Strengths

Quality and Clarity: Contextualization relative to prior work is good, Table 1, for example, provides a very concise and insightful summary of existing results. Originality: The paper considers an original viewpoint on the problem of double-descent, namely they realize that violating either Assumptions 1 or 2 can cause the peak to move into the under-parametrized region. To the best of my knowledge, this had not been noticed before. Significance: This result is significant, as it addresses the prominent double-descent phenomenon in machine learning, which is an important primitive for understanding generalization and other properties of estimators operating on high-dimensional data. They also prove that a peak in the norm of the estimator does not imply a peak in risk, and this is important as it goes against some of the intuition provided in earlier works.

Weaknesses

Clarity: Although the contextualization relative to prior work is good, I find that the paper lacks in clarity. In particular, it is not exceptionally well written, and leaves some sections with much to be desired in terms of exposition. Specific examples are: - Table 1: What does 1/Low mean? The superscript 3 leads to nowhere. - Middle of page four: “Hence, this is controlled by 1. The alignment…, 2. The spectrum”. What exactly is being controlled here? And why exactly is it controlled by 1. and 2. ? This is not immediate to me, and I think this needs to be made more precise. - Over-use of italics in the introduction makes it hard to know what to focus on. I would recommend maximum one italicized sentence per paragraph. - Section 4.1: be more precise about the model, I don’t know what it is at this point. I later identify that $X + A$ represents the spiked data, but this must be made clear earlier on. I find“Let A be the noise matrix” to not be clear enough. - Theorem 1: a comment on the proof technique for this theorem would be helpful, even if you have already mentioned it previously (or given the intuition). Also, the interpretation of Theorem 1 is not clear until we read Theorem 2, could you interpret Theorem 1 a bit more and specifically identify what it says that is not said in Theorem 2? Is Theorem 2 just a corollary of Theorem 1? - The first sentence of the abstract is not clear. Overall, the abstract may need to be rewritted in a more professional manner, not referring to previous works as "believing" in something, but something more precise.

Questions

Figure 2: I see a clear peak, but I do not see an initial “descent”. Is there something I am missing here? Why does the model have best generalization at $c = 0$? I am guessing that the focus of the study is on the peak, although that is not the full picture of double descent as I am not seeing the initial descent. That is okay, but just make clear why there is no initial descent.

Rating

7

Confidence

3

Soundness

4

Presentation

2

Contribution

3

Limitations

Yes

Summary

The authors explore the double descent phenomenon, postulating that the location of the peak (that separates the "classical" and the "modern" interpolating regime) depends on the properties of the spectrum and the eigenvectors of the sample covariance. In particular, the authors show that the violation of one of two assumptions (assumption 1: Alignment of y and right singular vectors of X; assumption 2: Stieljtes Transform Peak Assumption) can move the peak from the interpolation point into the under-parameterized regime. They also present two simple examples that exhibit double descent in the under-parameterized regime and do not seem to occur for reasons provided in prior work.

Strengths

- The paper tackles a very important research topic, and tries to understand the reasons behind the location of the peak in double descent. - The work seems rigorous and the contributions relevant. - Overall, the paper is well-written and reasonably clear.

Weaknesses

- The conclusions of the paper are very brief and, from my point of view, not very informative (see section 6 in the paper). In relation to this, I also perceive a certain imbalance in the weight of the two examples provided: while the first (the one related to "Alignment Mismatch") occupies 3 pages of the work, the second example ("Shifting Local Maximum for Stieljtes Transform as a Function of c") is addressed more hastily (one page). - The volume of information provided by the paper is very high. From this point of view, I think it would be positive to recapitulate and indicate clearly, and in a simple and intuitive way, the way in which the risk curves shown throughout the paper are created (Figures 2, 4 and 6). The same applies to Figure 3: what ablation experiments do the authors refer to?

Questions

- What do the authors exactly mean by input and output noise? - In Table 1 (page 3), where are the footnotes related with numbers 3 and 4? - In Figure 3, what ablation experiments do the authors refer to?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

- In my opinion, the authors do not sufficiently discuss the limitations of the work performed. In fact, in the NeurIPS Paper Checklist, they only state that "We believe the main purpose of the paper is to show that a certain phenomenon exists and are very careful with our assumptions."

Summary

In this paper, the authors focus on the generalization performance of linear least squares regression and show the existence of double descent generalization curve in the under-parameterization regime. In particular, the authors argue, in the linear model in (1) under study (which is slightly different from standard linear models in the literature, but well motivated), that the generalization risk can have a peak in the under-paramererized regime that is due to the alignment between singular space of data and the target, and spectrum of data covariance, instead of the raw dimension ratio or the explosion of the estimator norm. Some numerical results are provided to support the theoretical analysis.

Strengths

The problem under study is of significance. The message of this paper looks interesting. But I find it a bit hard to really understand the results and contribution, see my comments below.

Weaknesses

While this paper looks interesting, it is a bit hard for me to really understand the results and contribution. I think making precise the dimension settings (relation between $n, d, n_{tst})$ will address this issue, see some of my detailed comments below. Another issue is the contribution: while Theorem 1 is rather general, the discussion thereafter seems all special cases: For example Theorem 2 is a special case, and the results in Sec 4.3 and 4.5 are essentially numerical. The discussions in Sec 5 is interesting but again a very special setting (mixture model of multivariate Gaussian and a fixed direction) without any motivation. It is thus difficult for me to evaluate the significance of this work.

Questions

* line 35: when summarizing the contribution of this work, it would be helpful to forward point to the corresponding theoretical result and/or definition, for the sake of a precise statement of the technical result or the definition (for example, the spiked covariate model). * it seems that the footnotes 3 and 4 are missing? * Equation after line 123: I am a bit confused here. What is the purpose here? Is $\hat \beta$ still the min norm solution, then what is $\beta$? * To make Definition 1 more rigorous, perhaps say here that the convergence of ESD holds in a weak sense as $k \to \infty$, or something like that? * Theorem 1: perhaps say somewhere in the theorem that this result holds in the asymptotic setting as $n,d,n_{tst}$ going to infinity at the same pace? * Honestly, I do not understand this result. It seems to me that my previous comment is wrong, and that the result in Theorem 1 does NOT hold in the limit of $n,d,n_{tst} \to \infty$ together, or at least, $n_{tst}$ and $n$ can be much larger than $d$. Some specifications and discussions are needed here. * Theorem 2 looks interesting. Could the authors comment more on this? For example, note that taking $\mu = 0$ is (more or less) similar to the ridgeless case in the literature. There, according to Theorem 2, we should have a at $c = 1$, as in accordance with "classical" double descent. So, should we understand Theorem 2 as an extension of "classical" double descent to the regularized setting? Or is this due to the model in (1) and (2)? * line 207 -208: $\hat \Sigma^T \hat \Sigma = \Sigma^T \Sigma + \mu^2$ a typo here? --- I thank the authors for their detailed reply, which helps me better understand their theoretical results and their contribution I increase my score accordingly. I, nonetheless, feel that there are a few typos that need be fixed and clarifications needed, in the current version of the paper.

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

I do not see any potential negative social impact of this work.

Summary

The paper considers the problem of linear least squares. Its main contribution is presenting two examples of double descent in the under-parameterized regime.

Strengths

- The paper is well written: Related works are sufficiently discussed (to my knowledge); the introduction is well-motivated and easy to follow; theorems are often followed by examples, figures, and illustrations helping the reader understand the results. - The problem the paper investigates and the perspective the paper takes is quite interesting. While the mainstream research in the field focuses on double descent in the case of over-parameterization, the paper analyzes under-parametrization in-depth and presents several results that improve one's understanding of double descent.

Weaknesses

- The paper takes unconventional notations that make the paper more challenging to penetrate. For example, it uses row vector notations and writes vector-matrix multiplication $\beta^\top X$ rather than the more common matrix-vector multiplication $X^\top \beta$. Sometimes I also found that the notations of singular vector $u$ and regularization parameter $\mu$ can be confusing as they look similar. - The two examples the paper offered are indeed examples. The reason is that the paper's assumptions are quite strong. For example, Assumption 3 assumes the test and training data matrices are both of rank $1$, and Theorem 4 has the orthogonality assumption $\beta^\top z=0$ which greatly simplifies the model and analysis.

Questions

I have no questions. It should be noted that I am not an expert in the exact area of double descent. I am not very familiar with the proof techniques used in the literature and am unable to make comments on technical depth.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

See above.

Summary

The authors show several facts about the double descent phenomena for the linear regression model with L2 loss and Frobenius norm regularization. They show taking different assumption from previous work moves the peak of the risk of the problem from the interpolation point into the under-parameterized regime. Provided theorems concretely describe the position of peak risk, including separating the risk into several terms: bias and the norm of the estimator. The authors also provide derivations (appendix) and experiments.

Strengths

Their analysis is thorough. Especially, reasoning change of trends of risks in Figure 4 through the term of the norm of the estimator supports the reliability of the results. They clarify proof steps in the appendix. Experiments provided to support each theorem also look thorough.

Weaknesses

The authors results which do not coincide with prior theory are based on different assumptions. Can the authors discuss how wider cases covered by their assumption?

Questions

Line 190: Is the assumption "$d$ is sufficiently large" used only to assume $o\left(1/d\right)=0$ in the Equation between Lines 177 & 178? If so, clarifying it in the main text would be better. Does $\left\|W_{opt}\right\|_F$ in Line 240 indicate its expectation? I recommend the authors to double check the overall text and equations. Here is a list of errata & typos. Note that from the equation between Line 119 and Line 120, $\hat \beta\in\\mathbb{R}^{d\times k}$. * Line 120: $\hat\beta = y X^\dagger$ -> $\hat \beta = \left(X^\dagger\right)^Ty^T$ * Displayed Equation between Lines 123-124: The denominator seems wrong. The following should be correct: $$ \left\|\hat\beta\right\|^2 = \sum_{i=1}^{\mathrm{rank}\left(X\right)}\frac{\left(y V\right)_i^2}{\sigma_i^2} $$ * Line 129: It would be better to add a couple of words emphasizing $\Sigma_n^{1/2}$ indicates the diagonal matrix $\Sigma$ in $X=U\Sigma V^T$ for readability. $\Sigma_n^{1/2}z_i$ looks like a summation symbol. I first thought it is a typo of $\sum_{i=1}^{1/2}z_i$. * Displayed equation between Lines 137-138: $z\in \mathbb{C}\setminus J$ -> $\zeta\in \mathbb{C}\setminus J$ * Lines 239-240: Is "for $n$ large enough and $d=cn$" a typo of "for $n$ and large enough $d=cn$"?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

Does the previous work (peak at interpolation point, using Assumptions 1 and 2) also rely on Assumptions 3 and 4? Or are you using just a different set (A 2 & 3 & 4) of assumptions which is a neither necessary nor sufficient condition of one of the previous work (A 1 & 2)? It should be stated more clearly.