Least Squares Regression Can Exhibit Under-Parameterized Double Descent

We thank the reviewer for recognizing the paper's good contextualization, its original viewpoint, and its significant result.

We now address the reviewer's concerns.

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:

We thank the reviewer for pointing out these concerns. We shall address them in the revised version of the paper.

Table 1: What does 1/Low mean? The superscript 3 leads to nowhere.

Subscript 3 points to Appendices A and F, which present a conjectured formula for the low-rank case with experimental evidence. We shall update the table only to say 1, the rank considered in the main text.

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.

We apologize there was a typo in the equation, it should read $\sum_{i=1}^r \frac{(y^T V)_I^2}{\sigma_i^2}$.

This quantity depends on two things: the product $y^TV$, which we call the alignment, and $\sigma_i^2$, which is the spectrum.

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.

We thank the reviewer for the feedback and shall reduce the number of italicized phrases.

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.

We shall add a definition for the spiked model in section 4.1

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).

We shall add the following small proof sketch to the paper.

Sketch: The main steps for the proof are as follows. First, we use the results from [49], which is like a Sherman Morrison formula but for pseudoinverses. Following this, we rewrite the error as a sum and product of various dependent quadratic forms. We then use ideas from random matrix theory and concentration of measure to show that each quadratic form concentrates on a deterministic number that depends on the Stieljtes transform of the limiting empirical spectral distribution. We then show that the product/sums of dependent forms also concentrate. This gives us the error rate as well.

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?

Theorem 1 provides the complete error curve as a function of $c$, not just where the maximum is. Prior works such as [24,48] have shown that noise on the independent variable acts as a regularizer. Hence, we have two regularizers for the problem - the noise and the ridge regularization. It is interesting to explore their tradeoffs. We do this in Appendix D. We shall expand on this in the main text.

Is Theorem 2 just a corollary of Theorem 1?

Theorem 2 can be viewed as a corollary of Theorem 1. It follows by taking the leading terms in Theorem 1 and doing calculus (compute the first derivative to find the critical point and the second to check that it is a maximum).

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.

We thank the reviewer for pointing out this concern and shall change the phrasing to make it clearer.

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.

The reviewer is correct that there is no initial descent. This is actually quite common for linear models. See Hastie et al (2020) for many such examples.

Whether the error is minimum at $c = 0$ vs $c = \infty$ is quite interesting and related to benign overfitting. $c~0$ is the case when $n >> d$. Hence, we have a lot of data points. Hence, classically, we hope for consistent estimators. Hence, we can expect to do well.

The $c ~\infty$ case is when $d >> n$. This is the largely overparameterized case. If the global minimum is here, this suggests that the model exhibits benign overfitting.

For our examples, benign overfitting seems absent, and hence, the minimum is at $c = 0$.

We hope this has addressed the reviewers' concerns and improved their opinion about our work. If the reviewer has further concerns, please let us know,

We thank the reviewer for finding that the paper tackles a very important research topic, is rigorous with relevant contributions, and is well written. We now address the reviewer's concerns.

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).

We agree that the conclusions are short. In the final version of the paper, we shall increase the length of the conclusions to make it more substantive while balancing the two examples. In particular, we will add the stronger version of Theorem 4 mentioned in the response to reviewer 4cXR.

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?

Thank you for the feedback. We shall do so.

The ablation experiment is described on lines 212 to 218, where we break the misalignment in two ways.

First, we consider the unregularized problem and artificially shift the spectrum of the noise matrix. This results in the shifted noise matrix having the same spectrum as the effective spectrum in the regularized problem. However, the alignment wasn't broken, so we see the peak at 1. Figure 3 (left).

Second, for the regularized problem, we artificially fixed the alignment and noticed that the peak is now in the over-parameterized regime.

Hence, the experiment validates the theory that the location of the peak was due to the misalignment.

What do the authors exactly mean by input and output noise?

Consider a linear function $y = \beta^T x$. This is a function that we are trying to fit. However, if we had access to exactly the correct inputs $x$ and outputs $y$, then solving the problem would be easy, and we would never see a double descent. To see double descent, we need to introduce noise into the problem. This can be done in two ways.

1. Output noise. That is, we do not receive the responses $y$, but noisy versions, so $y = \beta^T x + noise$.
2. Input noise. Now, instead of getting noisy $y$ measurements. We get the true measurements $y$ but receive noisy inputs $x$.

In Table 1 (page 3), where are the footnotes related with numbers 3 and 4?

We apologize for this.

Footnote 3 points to Appendix A and F, which discuss the low-rank version of Theorem 1. Appendix A provides numerical experiments to verify the formula, and Appendix F has a statistical physics-type derivatization for the error.

Footnote 4 states that [41] only considers optimal regularization.

In Figure 3, what ablation experiments do the authors refer to?

The ablation experiment is described on lines 212 to 218, where we break the misalignment in two ways.

First, we consider the unregularized problem and artificially shift the spectrum of the noise matrix. This results in the shifted noise matrix having the same spectrum as the effective spectrum in the regularized problem. However, the alignment wasn't broken, so we see the peak at 1. Figure 3 (left).

We hope that this has addressed the concerns of the reviewers and improved their opinion about our work. If the reviewer has further concerns, please let us know,

We thank the reviewer for finding that the problem we study is significant and that the findings are interesting. We now address the reviewer's concerns.

Another issue is the contribution: while Theorem 1 is rather general ... It is thus difficult for me to evaluate the significance of this work.

The paper's main purpose is to attempt to understand the reasons peaks occur in the excess risk curve and their locations. Prior work has phrased this as occurring due to overparameterization and the location being on the boundary of the under and overparameterized regimes. Additionally, some prior work [32] has criticized parameter counts as a measure of complexity, saying that parameter counts might overestimate the true complexity. Hence, shifting the boundary between under and over-parameterized to the right, not the left.

We question this narrative. In particular, we show that the location of the peak is determined by technical reasons in random matrix theory and not because it is the boundary between over and under-parameterized. To show this, we present the two conditions in Section 3 and, in particular, lines 145 to 148 highlight them again. The rest of the paper then presents two examples where each example violates exactly one of the conditions, and we show that the peak moves to the left.

In particular, our examples let us move the peak to the left and control its location.

Scaling of $d$, $n$, and $n_{tst}$

This is a great question. Our results are valid for any $n$, $d$, and $n_{tst}$. However, they are only meaningful when $n$ and $d$ are large, and $d$ and $n$ are proportional. Note that we assume that $\sigma^2_{tst} = O(n_{tst})$. The last error is mostly independent of the scaling of $n_{tst}$.

This can be seen as follows. The primary proof technique is concentration of measure. In particular, we want to show that the risk concentrates. Theorem 1 can be interpreted as saying when $c = d/n$ that (grouping the first and second term together)

$\left|\mathcal{R}(c, \mu) - \frac{\sigma\_{trn}^2(\sigma\_{trn}^2 + 1)}{2d\tau^2} \left( \frac{c(1+c+\mu^2 c)}{\sqrt{(1-c+\mu^2 c)^2+4\mu^2 c^2}} - 1\right) - \frac{\sigma\_{tst}^2}{\tau^2 n\_{tst}} \right| = o\left(\frac{1}{d}\right) = o\left(\frac{1}{n}\right)$

Hence, we show that the error concentrates around the above expression with an error of order $o\left(\frac{1}{d}\right)$. Hence if $d,n$ are small, the error might be large, however, if $d,n$ are large then the error will be small.

To make sure this is meaningful, suppose $\sigma_{trn}^2 = \Theta(n) = \Theta(d)$ (we are assuming $n$ and $d$ are proportional) and $\sigma_{tst}^2 = \Theta(n_{tst})$. Then we see that $\tau^2 = \Theta(n^2) = \Theta(d^2)$. Then we see that the first term $\frac{\sigma_{trn}^2(\sigma_{trn}^2 + 1)}{2d\tau^2} \left( \frac{c(1+c+\mu^2 c)}{\sqrt{(1-c+\mu^2c)^2+4\mu^2c^2}} - 1\right)$ is $\Theta(1/d) = \Theta(1/n)$. The final term $\frac{\sigma_{tst}^2}{\tau^2 n_{tst}}$ of order $\Theta(1/d^2)$. Thus, the whole expression is of order $\Theta(1/d)$, while the error goes to zero faster.

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).

Thank you for this suggestion. We had forward pointers to the Theorems; however, we shall do this for the definitions as well.

Footnote links

We apologize for this.

Footnote 3 points to Appendix A and F, which discuss the low-rank version of Theorem 1. Appendix A provides numerical experiments to verify the formula, and Appendix F has a statistical physics-type derivatization for the error.

Footnote 4 states that [41] only considers optimal regularization.

Line 123

Apologies, it should be $\hat{\beta}$ on line 123 and the equation should be $\frac{(y^TV)_i^2}{\sigma_i^2}$

Definition 1

Thank you, we shall add the phrase.

Theorem 1: perhaps say somewhere in the theorem that this result holds ...

and

Honestly, I do not understand this result...

Please see our response on the scaling on $d$ and $n$. It is imperative that we clarify any concerns about the theoretical results. Please let us know if something is still unclear.

Theorem 2 looks interesting...

Setting $\mu = 0$ exactly recovers the result from [24], so it is an extension of that result. It is not a direct extension of the results in, say, Dobriban and Wager, Hastie et al., or Bartlett et al. Those settings are different.

In our setting we have low dimensional signal, the response depends on the signal and have noise on the inputs. In the setting of Dobriban and Wager, Hastie et al., or Bartlett et al., we have full dimensional signal and noise on the outputs. The regularized extension for these works can be seen in [11,23]. Here, we see double descent for certain $\mu$, and for the optimal $\mu$, we do not. However, the peak does not move!. This and more prior work are summarized in Table 1.

In our work, the peak moves $\mu$, which is quite surprising. Classical wisdom would states that increasing $\mu$ would increase the regularization, hence would decrease the complexity of the model. Hence, we would need a larger number of parameters to overfit. Hence, the peak would move to the right in the overparameterized regime.

However, we show that the peak moves to left!

Line 207-208

Apologies, that is a typo. It should read $\hat{\Sigma}^T \hat{\Sigma} = \Sigma^T \Sigma + \mu^2 I$.

We thank the reviewer again for their detailed comments. We hope that our response addressed all of the concerns. We would be eager to continue the conversation if there are any more concerns.

We hope that the response has improved the reviewer's opinion on our work.

We thank the reviewer for finding our analysis thorough, especially the reasoning for the trends. We now address the reviewer's concerns.

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?

We believe that much prior work assumes Assumptions A1 (alignment between $y$ and $V$) and A2 (Stieljtes Transform Peak). In our paper, we want to construct examples that violate these two assumptions. Hence, the example in Section 4 makes assumptions A3 and A4 (not A1 and A2), while the example in Section 5 is a mixture of a high-dimensional Gaussian and a one-dimensional Gaussian.

Assumptions A3 and A4 exist in prior work such as [24,37]. These works do have a peak at $c=1$. In our paper, setting $\mu = 0$ recovers [24]. Appendix A, F has the corresponding result for which setting $\mu = 0$ recovers [37].

The mixture example can be viewed as an extension of prior theory presented in papers such as Dobriban and Wager, and Hastie et al., by taking data distributions that satisfy their assumptions and creating a mixture with a distribution supported on a lower dimensional set. Setting $\pi_1 = 1$ (i.e., removing the low dimensional component) recovers an example that satisfies their assumptions

Finally, we would like to highlight some prominent examples that explicitly assume A1 and A2 or their assumptions imply A1 and A2 are satisfied.

Dobriban and Wager, 2015

A1

Assume that $\beta$ (and hence $y$) has an isotropic distribution (Assumption B in the arxiv version). Hence, $y^T V$ has an isotropic distribution. Hence, they assume A1.

A2

The paper assumes assumption A and that the operator norm of the expected sample covariance is uniformly bounded. These assumptions then satisfy the assumptions of Theorem 1.1 in [BZ08], which implies that the Stieljtes transform of the limiting distribution satisfies

$m(z) = \int \frac{1}{t(1-c-czm) - z} dH(t),$

where $H$ is the limiting distribution of the population covariance matrix, our assumption A2 is concerned about the function $c \mapsto m(0)$. Here, we see that

$m(0) = \int \frac{1}{t(1-c)} dH(t)$

This function is clearly maximum when $c = 1$. Hence, it satisfies assumption A2.

Hastie, Montanari, Rosset, Tibshirani, 2020

A1

They assume that data $x_i \sim \mathcal{N}(0,\Sigma)$. If the $x_i$ are the columns of $X = U\Sigma V$ (as is the notation in our paper). Then $XX^T/n = U\Sigma\Sigma^T U^T / n$ is the sample covariance. Hence, it is not dependent on $V$. Hence, this implies that the distribution of $V$ doesn't impact the sample covariance matrix. Hence, we believe this is similar to assuming that $V$ is uniform. Hence, assuming $y^T V$ is istropic.

A2

Similar to the Dobriban paper, their data satisfies the assumption of Theorem 1.1 in [BZ08].

[BZ08] Zhidong Bai and Wang Zhou. Large sample covariance matrices without independence structures in columns.

Line 190: Is the assumption " is sufficiently large" used only to assume $o(1/d) = 0$ in the Equation between Lines 177 & 178? If so, clarifying it in the main text would be better.

The reviewer is right. We shall clarify this.

Does $\|W_{opt}\|$ in Line 240 indicate its expectation?

Yes, thank for yo pointing this out, we shall correct this.

I recommend the authors to double check the overall text and equations. Here is a list of errata & typos.

We thank the reviewer for the typos found. We shall correct them.

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.

Some prior work assumes A3 and A4 (such as [24,37], setting $\mu = 0$ in our result recovers those results); however, other prior work does not. The key fact is that A1 and A2 are true in prior work in these prior works.

We hope that we have addressed all of the reviewers' concerns and questions and improved their opinion of our work. If the reviewer has further concerns, please let us know.

We thank the reviewer for finding our paper well-written and our perspective interesting. We now address the reviewer's concerns.

Notation

We shall fix $\beta^T X$ to $X^T\beta$ to align the paper better with the prior convention. We shall change the font for the $u$ to clarify the difference.

Strong Assumptions

We agree with the reviewer that some of our assumptions are strong. However, we believe that this helps us highlight the dependence of the location on the peak on 1) the alignment between $y$ and $V$ and 2) The peak in the Stieljtes transforms curve at 0.

However, here we discuss some relaxations of the assumptions.

For rank 1 assumptions, we refer the reviewer to Appendix A and Appendix F, where we provide a conjectured formula for general rank $r$ data as well as numerical verification of the conjecture.

For the orthogonality assumption, this is primarily to simplify the proof. Please note that in the numerical simulations displayed on the left of Figure 7, $\beta$ is not orthogonal to $z$. This version of the result can be proved.

We will update the paper with the result without assuming orthogonality. Here are the proof changes sketched out.

If we do not make this assumption, Then at the bottom of page 19, we would have an additional term:

$\frac{\|v\|^2}{1+\|v\|^2 z^T(AA^T)^{-1}z} \beta^T z z^T(AA^T)^{-1}$

Thus, on line 565, when we compute the excess risk, instead of

$\mathbb{E}\left[\left\|\left\|\xi^T \begin{bmatrix} A^T \\ vz^T \end{bmatrix} \left(AA^T + \|v\|zz^T\right)^{-1} \right\|\right\|^2 | X \right],$

we would have

$\mathbb{E}\left[\left\|\left\|\xi^T \begin{bmatrix} A^T \\ vz^T \end{bmatrix} \left(AA^T + \|v\|zz^T\right)^{-1} + \frac{\|v\|^2}{1+\|v\|^2 x^T(AA^T)^{-1}z} \beta^T z z^T(AA^T)^{-1}\right\|\right\|^2 | X \right]$

Then, we can expand the term norm into parts and see that the cross terms are zero due to $\xi$ being independent from $z, A$ and having mean zero. The first term would be

$\mathbb{E}\left[\left\|\left\|\xi^T \begin{bmatrix} A^T \\ vz^T \end{bmatrix} \left(AA^T + \|v\|zz^T\right)^{-1} \right\|\right\|^2 | X \right],$

which have already shown how to compute the expectation. For the second term, to understand the contribution of the norm of this term, we would need to compute

$\left(\frac{\|v\|^2}{1+\|v\|^2 z^T(AA^T)^{-1}z}\right)^2 \text{Tr}(z^T(AA^T)^{-2} z)$

Using the estimates from lines 568-570 and the same concentration results from [24], we see that this concentrates around

$\left(\frac{\|v\|^2}{1+\|v\|^2\mathbb{E}\_{\lambda \sim \nu}\left[\frac{1}{\lambda}\right]}\right)^2 \mathbb{E}\_{\lambda \sim \nu}\left[\frac{1}{\lambda^2}\right]$

Then, since the covariance for the Gaussian part is $\frac{\pi_1}{d} I$. Multiplying, we get that this term goes to zero as $d \to \infty$. Hence, the error formula is unchanged.

We hope that this has addressed the concerns of the reviewers and improved their opinion about our work. If the reviewer has further concerns, please let us know.

Dear authors, thank you for your reply. It has nicely addressed my concerns. I have thus increased my score by 1.