Prediction Risk and Estimation Risk of the Ridgeless Least Squares Estimator under General Assumptions on Regression Errors

We thank the reviewers for their time and valuable feedback. During the discussion period, we hope to hear more questions or comments from the reviewers for further discussion to strengthen the paper.

the technical difficulty of dealing with the non-i.i.d. noise assumption and the role of the left-spherical symmetry assumption

We would like to emphasize our contributions that the non-i.i.d. noise assumption itself cannot explain the double descent phenomenon and the left-spherical symmetry (LSS) plays an important role for factoring out $\mathrm{Tr}((X^\top X)^\dagger\Sigma)$ term from the expected variance in the non-i.i.d. noise setting. This trace term explains the double descent phenomenon.

• To further elaborate this, we rewrite the expected variance as $\mathbb{E}\_X[\mathrm{Var}_\Sigma(\hat\beta\mid X)]=c^\top b$, where $a=\lambda((X^\top X)^\dagger \Sigma), b=\lambda(\Omega)$, and $c=\mathbb{E}_X[\Gamma^\top a]$.
• For the i.i.d. noise with $\Omega=\sigma^2 I$ (i.e., $\mathbb{E}[\varepsilon_i\varepsilon_j]=\sigma^21_{i=j}$), the vector $b=\sigma^2 \mathbf{1}$ is parallel to $\mathbf{1}$; and thus we have $c^\top b= (c^\top \mathbf{1})\sigma^2$. Here, we have $c^\top \mathbf{1}=\mathbb{E}\_X[a^\top \Gamma \mathbf{1}]=\mathbb{E}\_X[a^\top \mathbf{1}]=\mathbb{E}\_X[\mathrm{Tr}((X^\top X)^\dagger \Sigma)]$ since $\Gamma \mathbf{1}=\mathbf{1}$ ($\Gamma$ is a doubly stochastic matrix).
• For the non-i.i.d. noise setting (with a general $\Omega$), the vector $b$ is not (necessarily) parallel to $\mathbf{1}$, but with the LSS assumption, $c$ is now parallel to $\mathbf{1}$; and thus we can similarly factorize the expected variance as $c^\top b=\bar c (1^\top b)=\frac1n\mathbb{E}\_X[\mathrm{Tr}((X^\top X)^\dagger \Sigma)] \mathrm{Tr}(\Omega)$ for any positive definite $\Omega$ where $c=\bar c\mathbf{1}$ and $\bar c=\mathbb{E}\_X[\frac1n \sum\_i a\_i]=\frac1n \mathbb{E}\_X[\mathrm{Tr}((X^\top X)^\dagger \Sigma)]$.
• To achieve the factorization $c^\top b=\frac1n\mathbb{E}\_X[\mathrm{Tr}((X^\top X)^\dagger \Sigma)] \mathrm{Tr}(\Omega)$ for any positive definite $\Omega$ (for any $b$ with $b_i>0$), it is necessary for $c$ to be parallel to $\mathbf{1}$. And this may not be achieved without the LSS assumption in the non-i.i.d. noise setting.

the left-spherical symmetry and the double descent phenomenon

The left-spherical symmetry makes each eigenvalue of $(X^\top X)^\dagger\Sigma$ have an equal influence on the risk.

• The double descent phenomenon can be explained by the trace term $\mathrm{Tr}((X^\top X)^\dagger\Sigma)$ (especially by large eigenvalues) from the expected variance under the left-spherical symmetry (LSS) assumption.
• This is because when $p\approx n$ there are many small eigenvalues of $X^\top X$ near 0 and they highly increase $\mathrm{Tr}((X^\top X)^\dagger\Sigma)$ and the expected variance, but in the overparameterized regime $p\gg n$, the eigenvalues of $X^\top X$ are distant from 0, and thus the variance becomes much smaller.
• Under the LSS assumption, the expected variance is factorized as $\frac1n\mathbb{E}\_X[\mathrm{Tr}((X^\top X)^\dagger \Sigma)] \mathrm{Tr}(\Omega)$ where each eigenvalue of $(X^\top X)^\dagger \Sigma$ is weighted with the same $\mathrm{Tr}(\Omega)$.
• However, this is not the case without the LSS assumption. In other words, without the LSS assumption, the small eigenvalues of $X^\top X$ near 0 may not play the similar role as they do under the LSS assumption.

Thank you for the detailed description of theoretical contributions. However, I'm not yet convinced about the setting of numerical studies. So, I will keep my original rating.

First of all, thank you for pointing out a typo in "we can obtain a similar result with 4.1". We will replace the problematic first sentence in Section 4.2 with the following: "For the bias component of prediction risk, we can attain a result comparable to those presented in Section 4.1 as follows:''

We now move to your main concern, namely lack of comprehensive elucidation. In Theorem 3.1, we factorize the variance component of $\mathbb{E}\_X[\mathrm{Var}\_\Sigma(\hat\beta\mid X)]$ into the product of the two terms: specifically,

$

    \mathbb{E}\_X[\mathrm{Var}_\Sigma(\hat\beta\mid X)]
    &=\frac{1}{n} \mathrm{Tr}(\Omega)\mathbb{E}\_X[\mathrm{Tr}((X^\top X)^{\dagger}\Sigma)],

$

where on the one hand, the first term $\frac{1}{n} \mathrm{Tr}(\Omega)$ remains bounded even if both $n$ and $p$ are very large and on the other hand, the second term $\mathbb{E}\_X[\mathrm{Tr}((X^\top X)^{\dagger}\Sigma)]$ tends to be smaller if $p/n$ gets larger. In other words, we isolate the effect of non-spherical $\Omega$ via $\mathrm{Tr}(\Omega)$. We obtain an even cleaner result for estimation risk in Theorem 3.2, where we have that

$

    \mathbb{E}\_X[\mathrm{Var}(\hat\beta\mid X)]
    &=\frac{1}{np}\mathrm{Tr}(\Omega)\mathbb{E}\_X[\mathrm{Tr}(\Lambda^{\dagger})],

$

where $XX^\top/p= U\Lambda U^\top$ for some orthogonal matrix $U\in O(n)$.
It can be easily seen that $\mathbb{E}\_X[\mathrm{Tr}(\Lambda^{\dagger})]$ is of order $n$, thus implying that the variance component of estimation risk will become smaller as $p/n$ gets larger. We would like to emphasize that both results are non-trivial and Assumption 2 (that is, left-spherical design matrix $X$) plays a key role in proving them. In summary, Theorems 3.2 and 3.3 imply that the variance components of both risks will be smaller if $p/n$ is larger, thereby preserving the essential feature of benign overfitting. Furthermore, we need to analyze the bias components to fully characterize benign overfitting. This task is done in Corollaries 4.1 and 4.2. Notice that Assumptions 4.3 and 4.4 restrict that both weighted and unweighted $L_2$ norms of $\beta$ are bounded. As we focus on the case that $p$ is large, the $L_2$ boundedness of $\beta$ requires that a large number of elements of $\beta$ be ``close to zero'' in some sense (unimportant parameters as we describe in the abstract). We hope that our explanations clarify the contributions of our main theoretical results and intend to implement appropriate revisions in the paper to enhance its overall exposition.

We thank the reviewers for their time and valuable feedback. During the discussion period, we hope to hear more questions or comments from the reviewers for further discussion to strengthen the paper.

It seems that the main theorems do not give direct access to the relations between the deterministic parameters underlying the data generating process and the learning risks, except in the asymptotic regime of $n,p\rightarrow \infty$. If that is the case, the nature of the contributions should be made clearer to stress that point.

Your comment that ``the main theorems do not give direct access to the relations between the deterministic parameters underlying the data generating process and the learning risks'' seems to indicate that the $\beta$ parameter is random in our setting. Please correct us if there are any misunderstandings. The assumption of the $\beta$ parameter is widely adopted in the literature. For example, see Dobriban and Wager (2018, Annals of Statistics); Richards, Mourtada, and Rosasco (2021, AISTATS); Li, Xie, and Wang (2021, ICML); Chen, Zeng, Yang, and Sun (2023, ICML) among others.

The random $\beta$ parameter assumption facilitates a clear and concise exposition of the bias components of prediction and estimation risks. Importantly, our main results are concerned with the variance components, which do not require the random $\beta$ assumption at all. We will mention in the revised version of the paper that it is a topic for future research to consider the fixed $\beta$ parameter. This would require more careful analysis because where the intricate interplay among $\beta, \Sigma$ and $\Omega$ has to be dealt with.

Thank you for the comment. We will revise our manuscript with the following discussions.

Our Focus on Overparameterized model and More Discussions on the Ridge Regularization

• One of our main goal is to understand the ability of deep neural networks and how overparameterization plays a role in the "double descent'' or "benign overfitting'' phenomena. This is why we focus on the overparameterized regime. There is not so much difficulties to extend our analysis to the underparameterized regime. The expected variance result is symmetric with respect to the line $\gamma=1$ (Fig 3, "logarithmic" horizontal axis), i.e., the curve for $\gamma'=n/p>1$ is the same as the curve for $\gamma=p/n>1$. Anyway, the underparameterized regime is just not our focus.

• On the other hand, it is not trivial to extend our analysis to the ridge regularization, but we can obtain a similar result with a little modification of the proof (Theorem 3.2). We summarize the modifications as follows:

  • For the ridge regression, we have $\hat\beta_\mu =(X^\top X+\mu I)^{-1}X^\top y = A_\mu y$ where $A_\mu = (X^\top X+\mu I)^{-1}X^\top$.
  • Thus, we have the expected variance $\mathrm{Var}\_\Sigma(\hat\beta\_\mu\mid X)=\mathrm{Tr}(A_\mu\Omega A_\mu^\top \Sigma)=||SA_\mu T||\_F^2$ and $a_\mu(X)=\lambda(A_\mu A_\mu^\top \Sigma)$.
  • Here, $a_\mu(OX)=a_\mu(X)$ still holds since $A_\mu A_\mu^\top = (X^\top X+\mu I)^{-1}X^\top X(X^\top X+\mu I)^{-1}$ is the same for $X$ and $OX$.
  • Using the notation $A_\mu(X)=(X^\top X+\mu I)^{-1} X^\top$, we have $SA_\mu(OX)=SA_\mu(X)O^\top$, and thus $\Gamma(OX)_{ij}=\langle Ov^{(i)}, u^{(j)}\rangle^2$.
  • We can conclude that $\mathbb{E}\_X[\mathrm{Var}\_\Sigma(\hat\beta_\mu\mid X)]=\mathbb{E}\_X[a_\mu(X)^\top \frac1n Jb]=\frac1n \sum_{i,j}\mathbb{E}\_X[(a\_\mu(X))_i]b_j=\frac1n \mathbb{E}\_X[\mathrm{Tr}(A\_\mu A\_\mu^\top \Sigma)]\mathrm{Tr}(\Omega)$