Prediction Risk and Estimation Risk of the Ridgeless Least Squares Estimator under General Assumptions on Regression Errors
Authors: Sungyoon Lee
Sokbae Lee
Venue: ICLR 2025 Poster (2025)
Keywords: minimum norm solution
ridgeless estimator
benign overfitting
double descent
overparameterization
Primary area: learning theory

Abstract: In recent years, there has been a significant growth in research focusing on minimum $\ell_2$ norm (ridgeless) interpolation least squares estimators. However, the majority of these analyses have been limited to an unrealistic regression error structure, assuming independent and identically distributed errors with zero mean and common variance. In this paper, we explore prediction risk as well as estimation risk under more general regression error assumptions, highlighting the benefits of overparameterization in a more realistic setting that allows for clustered or serial dependence. Notably, we establish that the estimation difficulties associated with the variance components of both risks can be summarized through the trace of the variance-covariance matrix of the regression errors. Our findings suggest that the benefits of overparameterization can extend to time series, panel and grouped data.

Published as a conference paper at ICLR 2025
PREDICTION RISK AND ESTIMATION RISK OF THE RIDGELESS LEAST SQUARES ESTIMATOR UNDER GENERAL ASSUMPTIONS ON REGRESSION ERRORS
Sungyoon Lee
Sokbae Lee
Department of Computer Science Hanyang University sungyoonleethhanyage ac. kr
Department of Economics Columbia University
s138416 111841@columbe wew.oummia.....mmm...mm........e edu
ABSTRACT
In recent years, there has been significant growth in research focusing min- imum le norm (ridgeless) interpolation least squares estimators. However, the majority of these analyses have been limited structure, assuming independent and identically distributed errors with zero mean and common variance. In this paper, we explore prediction risk as well es- timation risk under more general regression error assumptions, highlighting the benefits of overparameterization tered or serial dependence. Notably, we establish that the estimation difficulties associated with the variance components of both risks can be summarized through the trace of the variance-covariang matrix of the regression errors. Our findings suggest that the benefits of overparameterization can be extended to time series, panel and grouped data.
unrealistic regression
more realistic setting that allows for clus-
INTRODUCTION
Recent years have witnessed a fast growing body work that analyzes minimum l norm (ridgeless) interpolation least squares estimators (see, e.g.. Bartlett al. 2020 Hastie al. 2022 Tsigler & Bartleu 2023, and references therein). Researchers in this field were inspired by the ability of deep neural networks accurately predict noisy training data with perfect fits, a phenomenon known as "double descent" or "benign overfitting" (e.g.. Belkin et al. 2018 2019 2020 Zou et al. 2021 Mei & Montanari, 2022, among many others). They discovered that achieve this phenomenon, overparameterization is critical.
In the setting of linear regression, we have the training data {(I,, v1) E R2 x :i= 1, where the outcome variable y; is generated from
Y/ _1. B +
1,...,n,
I; is a vector features (or regressors), 3 a vector of unknown parameters, and 6 is a regression error. Here, is the sample size of the training data and p is the dimension of the parameter vector 3.
In the literature, the main object for the theoretical analyses has been mainly on the out-of-sample prediction risk. That is, for the ridge interpolation estimator 3, the literature has focused on
E (1n
3 2o 3)2
,1.-.., F
where Zo is test observation that is identically distributed as x; but independent of the training data. For example, Dobriban & Wager 2018); Wu & Xul (2020); Richards et al. (02T)); Hastic et al. (2022) analyzed the predictive risk of ridge(less) regression and obtained exact asymptotic expressions under the assumption that p/n converges to some constant as both p and n go to infinity. Overall, they found the double descent behavior of the ridgeless least squares estimator in terms of the prediction risk. [Bartlett et al. (2020):[Kor Kobak et (2020): Tsiglerr & Bartlett (2023) characterized the phenomenon of benign overfitting in different setting.

---

Published as a conference paper at ICLR 2025
To the best of our knowledge, vast majority of the theoretical analyses have been confined to simple data generating process, namely, the observations are independent and identically distributed (i..d.), and the regression enrors have mean zero, have the common variance, and are independent of the feature vectors. That is,
(I) This assumption, although convenient, is likely to be unrealistic in various real-world examples. For instance, [iao al. (023) adopted high-dimensional linear models examine the double descent phenomenon in economic forecasts. In their applications, the outcome variables include S&P firms' earnings, U.S. equity premium, U.S. unemployment rate, and countries' GDP growth rate. As in their applications, economic forecasts are associated with time series or panel data. As a result, it is improbable that (T) holds in these applications. As another example, [Spiess al. (2023) examined the performance of high-ding -igh-dimensional synthetic control estimators with many control units. The outcome variable their application the state-level smoking rates in the Abadie et al. (2010)
x))) T ~ i.idd with Elei] = 0, B[e]] = o² < oc and & is independent of x3-
dataset. Considering the geographical aspects of the U.S. states, it is unlikely that the regression
errors underlying the synthetic control estimators adhere to (.. In short, it desirable to go beyond the simple but unrealistic regression error assumption given in
0.9
0.7
0.6
0.5
0.4
orror Ic-
bait entor 1c 144)
Irah 204)
0.2
lest eroor (c
oroor (2- 1(4)
error dr 144
0.0
500
1000
1500
2000
Figure 1:
Comparison of in-sample and out-of-sample mean squared error (MSE) across various degrees of clustered noise. The vertical line indicates (= 1, 115).
To further motivate, we start with our own real-data example from American Community Survey (ACS) 2018, extracted from IPUMS USA (Ruggles et al., 2024). The ACS is an ongoing annual survey by the US Census Bureau that provides key information about the US population. To have relatively homogeneous population, the sample extract is restricted to white males residing in Cali- fornia with at least bachelor's 's degree. We consider demographic group defined by their age, the type of degree, and the field of degree. Then, we compute the average of log hourly wages for each ege-degree-fie field group, treat each group average the outcome variable, and predict group wages by various group-level regression models where the regressors are constructed using the indicator variables of age, degree, and field well their interactions. We consider specifications ranging from 209 to 2, 182 regressors. To understand the role of non-i.i.d. regressor errors, we add the artifi- cial noise the training sample. See Appendix [A for details regarding how to generate the artificial noise. In the experiment, the constant varies such that e = ( corresponds to no clustered depen- dence across observations but as a positive gets larger, the noise has a larger share of clustered errors but the variance of the overall regression errors remains the same regardless of the value of c. shows the in-sample (train) vs. out-of-sample (test) mean squared error (MSE) for various values of e E {0, 0.25, 0.5, 0.75). It can be seen that the experimental results are almost identical across different values especially when p > n, suggesting that the double descent phenomenon might be universal for various degrees of clustered dependence, provided that the overall variance of the regression errors remains the same. It is our main goal to provide a firm foundation for this empirical phenomenon. To do so, articulate the following research questions:
How to analyze the outple prediction risk of the ridgeless least squares estimator under general assumptions on the regression errors?
2

---

Published as a conference paper at ICLR 2025
Why does not the prediction risk seem to be affected by the degrees of dependence across observations?
To delve into the prediction risk, suppose that Σ == E[ is finite and positive definite. Then,
E (1 zō B)² 21............................ Fn E (B 3) E 3) 21.....,
E = (i.e., the case of isotropic features), where / is the identity matrix, the mean squared error of the estimator defined by E|| 311²), where || - || is the usual Euclidean norm, is the same as the expectation of the prediction risk defined above. However, if 2 * I, the link between the two quantities is less intimate. One may regard the prediction risk as the E-weighted mean squared error of the estimator; whereas F|[] []]²]] can be viewed as "unweighted" version, even if Σ + J. In other words, regardless of the variance-covariance structure of the feature vector, E[|l - 31] treats each component of /3 "equally." The mean squared error of the estimator is arguably one of the most standard criteria to evaluate the quality of the estimator in statisties. For instance, in the celebrated work by James & Stein] (1961). the mean squared error criterion is used to show that the sample mean vector is not necessarily optimal even for standard normal vectors (so-called "Stein's paradox"). Many follow-up papers used the same criterion; e.g., [Hansen] (2016) compared the mean-squared error of ordinary least squares, James-Stein, and Lasso estimators in an underparameterized regime. Both E-weighted and unweighted versions of the mean squared error are interesting objects to study. For example, [Dobriban & Wager (2018) called the former "predictive risk" and the latter "estimation risk" in high-dimensional linear models; |erttherr et al.) 2020) called the former "generalization error" and the latter "reconstruction error" in the context of stochastic gradient descent for the least squares problem using the noiseless linear model. In this paper, we analyze both weighted and unweighted mean squared errors of the ridgeless estimator under general assumptions on the data tatt-gennrating processes, not to mention anisotropic features. Furthermore, our focus is on the sanite-sample analysis, that is, both p and n are fixed but > n.
Although most of the existing papers consider the simple setting in D. our work is not the first paper to consider more general regression errors in the overparameterized regime. [Chnot et al. (2022) Chinot & Lerasle (2023) analyzed minimum norm interpolation estimators well regu- larized empirical risk minimizers in linear models without any conditions on the regression errors. Specifically, Chinot & Lerasle (2023) showed that, with high probability, without assumption on the regression errors, for the minimum norm interpolation estimator, (ß - T - B) is bounded from above by (118113 Sigl? {₂ Σー=ee /n, where is an absolute constant and {x(E) is
the eigenvalues of Σ in descending order. Chinot & Lerasle (202)) also obtained the bounds on the estimation error (â B) TB B). Our work is distinct and complements these papers in the sense that we allow for a general pariance-covariang
matrix of the regression errors. The main motivation of not making any assumptions on e; in Chinot et al. (2022) and [hinot & Lerasle (2023) to allow for potentially adversarial errors. We aim to allow for a general variance-covariance ma- trix of the regression errors to accommodate time series and clustered data, which are common in applications. See, e.g., [ansen (2022) for a textbook treatment (see Chapter 14 for time series and Section 4.21 for clustered data).
The main contribution of this paper is that we provide exact finite-smpple characterization of the variance component of the prediction and estimation risks under the assumption that X [21, 372,...,23. _n]] is left-spherical (e.g., x;'s can be i.i.d. normal with mean zero but more gen- eral); ey's can be correlated and have non-identical variances; and e, 's are independent of x; 's. Specifically, the variance term can be factorized into a product between two terms: one term de- pends only on the trace of the variance-covarriance matrix, say Q. of e e,'s; the other term solely determined by the distribution of x; 's. Interestingly. we find that although Q may contain non-zero off-diagonal elements, only the trace of Ω2 matters, as hinted by Figure [ and further demonstrate our finding via numerical experiments. In addition, we obtain exact finite-sample expression for the bias terms when the regression coefficients follow the random-effeet hypothesis (Dobriban & Wager 2018). Our finite-sample findings offer distinct viewpoint on the prediction and estimation risks, contrasting with the asymptotic inverse relationship (for optimally chosen ridge estimators) between the predietive and estimation risks uncovered by Dobriban & Wager (2018). Finally, connect our findings to the existing results on the prediction risk (c.g., Hastic et al. 2022) by consid- ering the asymptotic behavior of estimation risk. Remarkably, our findings stand in sharp contrast
3

---

Published as a conference paper at ICLR 2025
to the well-established results in econometries. In the latter, unlike in our framework, of the key objectives is to estimate the variance-covariance matrix, denoted by VLs, of the asymptotic distribu- tion of the least squares estimators. In this context, the off-diagonal elements of f do affect Vi.s. implying that any consistent estimator of Vis must account for these off-diagonal components.
One of the limitations of theoretical analysis is that the design matrix X is assumed to be left- spherical, although it more general than i.i.d. normal with mean zero. We not only view this as a convenient assumption but also expect that our findings will hold least approximately even if X does not follow the left-spherical distribution. It is topic for future research to formally investigate this conjecture.
THE FRAMEWORK UNDER GENERAL ASSUMPTIONS ON REGRESSION ERRORS
We first describe the minimum & norm (ridgeless) interpolation least squares estimator in the over- parameterized case (p > n2). Our goal is to understand the generalization ability of overparam- eterized models trained with gradient-based optimization (c.g., gradient descent) Gunasekar et al. (017)) Define
y [V1, V2,
Vn _ R"
E = [11, 6 Enl E R",
X : [1] T2 ... nnl E Rexa
so that y = X33 + c. The estimator we consider is
i = arg [1b] Xb = -) =x y= y
bER"
where At denotes the Moore Penrose inverse of matrix A.
The main object of interest in this paper is the prediction and estimation risks of 3 under the data scenario such that the regression error e; may not be i.i.d. Formally, make the following assump- tions.
Assumption 2.1. (i y = X + E, where e is independent of X, and B[s] (ii) Ω Bsss is finite and positive definite (but not necessarily spherical).
We emphasize that Assumption 2.1 is more general than the standard assumption in the literature on benign overfitting that typically assumes that Ω I²I. Assumption 2.11 allows for non-identical variances across the elements of because the diagonal elements of Q2 can be different among each other. Furthermore, allows for non-zero off-diagonal elements in Ω. It difficult to assume that the regression emrors are independent among each other with time series or clustered data; thus, in these settings, it is important to allow for general Ω * o²1. Below we present a couple of such examples.
Example 2.1 (Time Series AR(1) Errors). Suppose that the regressor error follows an autoregres- sive process:
pE;-1 7/s
where p E (-1,1) is an autoregressive parameter, is independent and identically distributed with mean zero and variance o²(0 < o² < oo) and independent of X. Then, the (i. element of f2
a²
Py = 1--1
Note that Diy U 0 long as p # 0.
Example 2.2 (Panel and Grouped Data Clustered Errors). Suppose that regression errors mu- tually independent across clusters but they can be arbitrarily correlated within the same cluster. For instance, students in the same school may affect each other and also have the same teachers: thus it would be difficult to assume independence across student test scores within the same school. How- ever, it might be reasonable that student test scores independent across different schools. For
4

---

Published as a conference paper at ICLR 2025
example, assume that (i) if the regression enror E; belongs to cluster 9. where ...... G and G is the number of clusters, B[E = og for some constant og > 0 that can vary over g; (ii) the regression errors E, and εj (i * j) belong to the same cluster g. B|s,e,] = Pg for some constant Py + 0 that can be different across g; and (iii) if the regression errors ε; and Ej (i # j) do not belong to the same cluster, E[e,ey] = 0. Then, f2 is block diagonal with possibly non-identical blocks.
For vector and square matrix A, let ||a]] = a T Aa. Conditional on X and given A, we define Bias (3 x)= and we write Var Vary and Bias Bias, for the sake of brevity in notation.
||a|| X] B and A X) == Tr(Cov( X))),
The mean squared prediction error for an unseen test observation Zog with the positive definite co- variance matrix Σ B( (assuming that zi is independent of the training data X) and the mean squared estimation error of 3 conditional on X can be written as:
Rp(31 X) = E. [(x 3 2i 3)² x] = [Biass (3 x))² + Vars( x);
(5( X) == [11 B11 x [Bias( 3 X)]² + Var( X).
In what follows, we obtain exact sample expressions for prediction and estimation risks:
Rp(0) Ex ( X)] and (B( Ex (R X)].
We first analyze the variance terms for both risks and then study the bias terms.
3 THE VARIANCE COMPONENTS OF PREDICTION AND ESTIMATION RISKS
3.1 THE VARIANCE COMPONENT OF PREDICTION RISK
We rewrite the variance component of prediction risk as follows:
Varg( X)= Tr(Cov(3 ( x)z) Tr ||Sxt||
where positive definite symmetric matrices S == 1// and := /2 the square root matrices of the positive definite matrices Σ and Ω, respectively. To compute the above Frobenius norm of the matrix SX we need to compute the alignment of the right-singular vectors of B = SXt E Rxxx with the left-cigenvectors of T' e "=""" Here, B is a random matrix while T' is fixed. Therefore, we need the distribution of the right-singular vectors of the random matrix B.
Perhaps surprisingly, to compute the expected variance Ex [Varg X)). it turns out that we do not need the distribution of the singular vectors if we make a minimal assumption (the left-spherical symmetry of X) which weaker than the assumption that {xx; } is i.i.d. normal with B[x]] 0.
Definition 3.1 LLeft-Spherical Symmetry (Dawid 1977 1978 1981 Gupta & Nagar 1999)). A ran- dom matrix 7 or its distribution is called to be left-spherical it OZ and 2 have the same distribution
(oz Z) for any fixed orthogonal matrix E ((n) == (A E R=*" AAT ATA=1}.
Assumption 3.2. The design matrix X is left-spherical.
For the isotropic error case (Ω = I) we have Ex (Vars:(3 X)] Ex(TT((XTx)) directly from (3) since XtT = xx).. Moreover, for the arbitrary error, the left-spherical symmetry of X plays critical role to factor out the same Ex [TT((X X) x)12)] and the trace of the variance- covariance matrix of the regression errors, Tr(S2), from the variance after the expectation over X.
Lemma 3.3. For subset S C TRmxm satisfying C-1 E for all C E S, if matrix-valued random variables Z and AZ have the same distribution measure pz for any A E S. then we have
Ez(s(Z)] = Ezlf(AZ)) Ez [f
for any function f E L' (pz) and any probability density function v on S. Theorem 3.4. Let Assumptions 2.1 and 3.2 hold. Then, we have
Ex ( X)] = Tr(2) (TT() (X
5

---

Published as a conference paper at ICLR 2025
Sketch of Proof. With B / and T = 2 rewrite the variance follows:
Vary (3 X): = |B 9- = |UDV UrDrV, VIT I|D'T Ur
from the singular value decompositions B UDV and T VV.VV with orthogonal matrices U, U2, Vr, and diagonal matrices D, Dr. Then, need to compute the alignment V U of the right-singular vectors of B with the left-eigenvectors of 'T' because
I UT Dr 12 A ((x ((xT))/=) T T(X)A()) = a(x) T(X)6,
where (X) == A ((XT))())
X(22), v60 = V.s, uld) == (UT).j Yoj == (olO, ub)i²2 0, r(X) = (7t))ss 12xx and X(A) E R" is a vector where its elements are the eigenvalues A.
Now, we want to compute the expected variance. To do so, from Lemma 3.3 with 8 ( and the left-spherical symmetry of X, we can obtain
Exxx())TT(X) Ex (aoo)/l(OO)))) [[OX)b] = Ex [a(x) (o-
where is the unique uniform distribution (the Haar measure) over the orthogonal matrices (n).
Here, we can show that (TxO))( = J, where J is the all-ones matrix with Jiy = 1 = 1,2, 1,). Therefore, we have the expectéd variance follows:
Ex [arrs(3 [x]] = Ex [(x) T - Jb
1 Σ
- -Ex[IT((XXXX)) x) Tr()). 7
Ex [x]
This recovers the previous results (e.g.. Hastie et al. (2022) when Ω 0²1, i.e., es's are i.i.d. with
Var[e:] = o². The proofs of Lemma 3.3 and Theorem are in the supplementary appendix.
3.2 THE VARIANCE COMPONENT OF ESTIMATION RISK
For the expected variance Ex [Var( [)] of the estimation risk, a similar argument still holds plugging-in in B Xt instead of B xt. Theorem 3.5. Let Assumptions
2.1 and 3.2 hold. Then, we have
Ex [ar
X)]
(T(AA))(TT((A))
mp
where XX /pD /p= T for some orthogonal matrix U E O(n).
3.3 NUMERICAL EXPERIMENTS
In this section, we validate our theory with some numerical experiments of Examples 2.1 and 2.2 especially how the expected variance is related to the general covariance Ω of the regressor error the both examples, we sample {a; } from A/ Σ) with general feature covariance DUU for an orthogonal matrix Us E O(p) and diagonal matrix Dy 0. In this setting, we have rank(XX )) and At A almost everywhere.
See Fig in Appendix C for the experiments with large and p (e.g., = 10k, p = 150k).
AR(1) Errors As shown in Example 2.1 when the regressor error follows autoregressive pro- cess in equation 2 we have P4y 0² /(1 p²) and Tr(Ω)/n o²/ p p²). Therefore, for pairs of (a², n²) with the same Tr(S)/n, /n. they are expected to yield the same variances of the pre- diction and estimation risk from Theorem 3.4 and (33) [355 even though they have different off-diagonal elements in Ω. To be specific, the pairs (o=,p²)
line ((o2. : o² /R² + p² 1} have the same Tr(2)) n and the same expected variance which gets larger for the line with respect to larger R
Figure (left) shows the contour plots of Ex [x different pairs of (a², p²) in Example 2.1 They have different slopes -x according to the value of n Tr(Ω)/n. The right panel shows equivalent contour plots for estimation risk.
X)] and Tr(2))x (Tr((" (T((XX)( for

---

Published as a conference paper at ICLR 2025
Prediction Risk AR(1) Erros
Estimation Risk AR(1) Errors
0.6
0.6
0.4
0.4
0.3
0.3
0.2
0.2
0.1
0.0
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
o²
Figure 2: Our theory (dashed lines) matches the expected variances (solid lines) of the prediction
(left) and estimation risks (right) in Example 2.1 (AR(1) Errors). Each point (o² p²) represents different noise covariance matrix S2, but with the same Tr(S2) along each line (0²2," ,²) p² 1} for some x² > 0, they have the same expected variance. We set 500, p 1000, and
: o //² +
evaluate on 100 samples of X and 100 samples of E (for each realization of X) to approximate the expectations.
Prediction Risk Clustered Errors
Estimation Risk Clustered Errors
0.5
0.5
0.4
0.2
0.2
0.1
9.36
0.1
0.1
0.2
0.3
0.4
0.5
0.1
0.2
0.3
0.4
0.5
of
of
Figure 3: Our theory (dashed lines) matches the expected variances (solid lines) of the prediction
(left) and estimation risks (right) in Example 2.2 (Clustered Errors), Each point (a oz) represents
a different noise covariance matrix Ω, but with the same Tr(s?) along each line { 02) " "o +
1x0 = x² } for some x² > O, they have the same expected variance. We set G = 2, (nj = 50, ny = 150), n 200, p 400, Pr P2 = 0.05, and evaluate on 100 samples of X and 100 samples of (for each realization of X) to approximate the expectations.
Clustered Errors Now consider the block diagonal covariance matrix
diag(S4, 02,--. Qg) in Example 2.2 where Gy is ng ny matrix with (Ng) o and (My)is = Pg (i + j) for each j = 1,2, ... ng and g = 1,2, G. Let = E ng. We then have Tr(Ω)/n = ES Tr(22))/n = (ng
Therefore, given partition {n₂
of the observations, the covariance matrices Ω with different {0)) have the same Tr(lt)/n if
(of, off.oz ... .g)) E TRG are on the same hyperplane ato =2 + usag R² for some x² 0.
Figure 3 (left) shows the contour plots of Ex (V X)] and 1 Tr(2) xX X)
for different pairs of (z) for simple two-clusters example (G 2) of Example 2.2 with (N1,72) 722) = (3, 15). Here, we use a fixed value of P1 P2 = 0.05, but the results are the same regardless of their values, as shown in the Appendix. Unlike Example 2.1 the hyperplanes
thogonal to v = [ng n2] regardless of the value of x² Tr(22)/, /n. Again, the right panel shows equivalent contour plots for estimation risk.

---

Published as a conference paper at ICLR 2025
4 THE BIAS COMPONENTS OF PREDICTION AND ESTIMATION RISKS
Our main contribution is to allow for general assumptions on the regression errors, and thus the bias parts remain the same they do not change with respect to the regression errors. For completeness, in this section, we briefly summarize the results on the bias components. First, we make the fol- lowing assumption for constant rank deficiency of X X which holds, for example, each 2; has positive definite covariance matrix and is independent of each other.
Assumption 4.1. rank(X) = almost everywhere.
4.1
THE BIAS COMPONENT OF PREDICTION RISK
The bias term of prediction risk can expressed as follows:
[Bias:(3 x)]² (533 lim 22 + +T)
(4)
A A
where Σ = X
1TXXx. X/n. Now, in order to obtain an exact closed form solution, we make the following
assumption:
Assumption 4.2. Eg[SB(53) = =////p. where r == E < oc and / is independent of X.
similar assumption (see Assumption 4.4) has been shown to be useful to obtain closed-fone form expressions in the literature (e.g.. Dobriban & Wager 2018 Richards al. 2021 Li et al. 2021
Chen et al.) 2023).
Under this assumption, since (B X)]² (r(33(S3) lim 22 ES + AI)
from
4), we have the expected bias (conditional on X) follows:
Eg Biasy (8) x)²
X
E ((E 03} = r p-
where 5; are the eigenvalues of S- E F2xp and rank(S-1$ss) rank(X) everywhere under Assumption 4.1 This bias is independent of the distribution of X or the spectral density of S-I but only depending on the rank deficiency of the realization of X.
almost
Finally, the prediction risk Rp(ß) can be summarized as follows:
Corollary 4.3. Let Assumptions 2.7
3.2
4.1
and 4.2 hold. Then, we have
R
2
n
Tr(?2)
Ex [T(((XXXX))]
p
4.2 THE BIAS COMPONENT OF ESTIMATION RISK
For the bias component of estimation risk, we can obtain a similar result with as follows:
[Bias(3 x))² = TT ΣイΣ) = lim 3 A + AB3 x
Assumption 4.4. Eg[33T] = T/p, where y = [ < oc and 3 independent of X.
Under Assumption
we have the expected bias (conditional on X) as follows:
E, [iiass 3 x X]
2
y2
{i [p] s; 0} p ppp-
(S)
p
where are the eigenvalues of R and rank ( rank(X) under Assumption 4.1
Thanks to Theorem 3.5 and
we obtain the following corollary for estimation risk.
Corollary 4.5. Let Assumptions 2.1
3.2
4.1 and 4.4 hold. Then, we have
+ Tr(
Ex / d In (n(8)
RE(3) = ,
n
where (s) = - (()((A)
S 8) is the empirical spectral distribution of a matrix and (A)),)2(A) (A) are the eigenvalues of A.
8

---

Published as a conference paper at ICLR 2025
The proof of Corollary 4.5 is in the Appendix.
4.2.1 ASYMPTOTIC ANALYSIS OF ESTIMATION RISK
To study the asymptotic behavior of estimation risk, we follow the previous approaches (Dobriban) & Wager, 2018; Hastie et al., 2022). First, we define the Stieltjes transform as follows: Definition 4.6. The Stieltjes transform sp(2) of df F is defined as:
8p(2):- = dF (x), for E C (upp(F).
Estimation Risk
19
10'
valiance
x verience
varfance Rhheor)
variance Rhherss
varizioe Kheory,
variance Rheory, so.)
181
[theary]
(thetry)
10
10a
10-1
10a
10'
Figure 4:
The "descent curve" in the overparamettrizztion regime for prediction risk (left) and estimation risk (right). We test Q's with Tr(12/n = 1,2, black, blue, red, respectively. For the anisotropic feature, the expected variance (x) and its theoretical expression (+) are [T(Q)/ 7-1
and larger than that in the high- nigh-dimensional asymptotics for the isotropic Σ I. For the isotropic = J, the variance terms (dotted) and the bias terms (dashed) in the high-dimensional asymptotics respectively.
are lim
Tr(2) and 2
We now ready to investigate the asymptotic behavior of the mean squared estimation error with the following theorem:
Theorem 4.7. Silverstein & Bai 1995 Theorem I.I) Suppose that the rows (x: (x:)i_ in are i...d.
centered random vectors with E و Σ and that the empirical spectral distribution F² = >E= 1(T, < s} of E converges almost surely to probability distribution function H -
When p/n y 0 n.p oc, then a.s., FXX converges vaguely to a df F and the limit s* l F (z) 2) of its Stieltjes transform 85 is the unique solution to the equation:
-- / 1+ dH()).
(6)
This theorem is a direct consequence of Theorem 1.1 in Silverstein & Bai (1995). Then, from Corollary 4.5 we can write the limit of estimation risk as follows:
Corollary 4.8. Let Assumptions 2.7
3.2
4. and 4.4 hold. Then, under the same assumption as
Theorem as n.p + no and p/
7,
where < 50 is constant, we have
lim Tr(Ω))
RE( = E 311
,
-
10-000
Here, the limit s* of the Stieltjes transform sr is highly connected with the shape of the spectral distribution Σ. For example, the case of isotropic features ( T), i.e., dH = ö(T 1)dr, have s (r 1) from squared error is exactly the same as the expression for > in equation (10) Hastie et al. 2202 Theorem 1). This is because prediction risk is the same estimation risk when Σ =
- In addition, if S2 o²1, then the limit of the mean

---

Published as a conference paper at ICLR 2025
Remark 4.9. Generally, if the support of H is bounded within [cH, Cиl I for some positive constants 0 < си I Cи < oc, then we can observe the double descent phenomenon the over-
parameterization regime with lim oo and Iim following inequalities:
with θ 7-1
from the
1
8 S CH 7
H
7
In fact, a tighter lower bound is available:
2 H (7-
(8)
where μn := Er~H [7], i.e., the mean of distribution H. The proofs of and 8 are given in the supplementary appendix.
We conclude this paper by plotting the "descent curve" in the overparameeterization regime in Figure On one hand, the expected variance (x) perfectly matches its theoretical counterpart (+) and goes
gets large. On the other hand, the bias term is bounded even if y + The Appendix contains the experimental details for all the figures.
CONCLUSION
We present analysis of the prediction and estimation risks of the minimum & norm (ridgeless) interpolation least squares estimator under more general regression error assumptions, highlighting the benefits of overparameterrizatoo in more realistic setting. This allows for clustered serial dependence, which enables us to extend our results to time series, panel and grouped data. Notably, provide important understanding that the estimation difficulties associated with the variance components both risks can be factorized into a product between two terms: one term depends only the trace of the variance-covariance matrix of e; 's; the other term is solely determined by the distribution of x; ss. Although Ω may contain non-zero off-diagonal elements, the off-diagonal correlation Elayey] do not play any role but only the trace of matters. would be promising orthogonal research direction to explore the risks under a general feature setting such as kernel regression or random feature models, along with general error assumptions.
ACKNOWLEDGMENTS
This work was partly supported by Institute of Information & communications Technology Planning Evaluation (ITPP) grants 1332013,- Artificial Intelligence Graduate School Program (Hanyang University): RS RSS-2023-002206284, Artificial intelligence for prediction of structure-based protein interaction reflecting physicochemical principles) and the National Research Foundation of Korea (NRF) grants (RS-2023-0024489) Implicit bias of optimization algorithms for robust generalization of deep learning; the BK21 FOUR (Fostering Outstanding Universities for Research) Solutions for Bridging the AI Divide: Blockchain and Federated Learning- Based AI Training Data Platform) funded by the Korean government (MSIT).
project; NRF-2024S NRF-22224IASC3AAAA IASC3A000436533
ETHICS STATEMENT
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
REPRODUCIBILITY STATEMENT
Detailed explanations to draw Fig 4 are included in Appendix and We also attach our code to facilitate the reproduction of our experiments.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Alberto Abadie, Alexis Diamond, and Jens Hainmueller. Synthetic control methods for compara- tive case studies: Estimating the effeet of california's tobacco control program. Journal of the American Statistical Association, 105(490):493505, 2010.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(44))33063-30077 2020.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to under- stand kernel learning. In International Conference Machine Learning, pp. 541-549. PMLR, 2018.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849 15854, 2019.
Mikhail Belkin, Daniel Hsu, and Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4):1 2020.
Raphaël Berthier, Francis Bach, and Piere Gaillard. Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model. Advances in Neural Information Processing Systems, 33:2576-2586, 2020.
Xin Chen, Yicheng Zeng. Siyue Yang, and Qiang Sun. Sketched ridgeless linear regression: The role of downsampling, In International Conference on Machine Learning, pp. 3296-5326. PMLR, 2023.
Geoffrey Chinot and Matthieu Lerasle. On the robustness of the minimum & interpolator. Bernoulli, 2023. forthcoming, available at https:: www. www.bbrrnolll... iosiiityyyyyy.ooo org/
publ iontiict/o/bbrbouuu
//bernouulllleeeeeeeeoeee li -aaurral--ppprss
Geoffrey Chinot, Matthias Löffler, and Sara van de Geer. On the robustness of minimum norm inter- polators and regularized empirical risk minimizers. The Annals of Statistics, 50(4):2306 2333, 2022. doi: 10.1214/2-AOS22190 URL BtRtsttss:/ sattps://dol: //doi. org/ ot./10.121111.11111111.......... AA2220
AP Dawid. Spherical matrix distributions and a multivariate model. Journal of the Royal Statistical Sociery: Series B (Methodological), 39())254 261, 1977.
AP Dawid. Extendibility of spherical matrix distributions. Journal of Multivariate Analysis, 8(4): 559-566, 1978.
AP Dawid. Some matrix-variate distribution theory: Notational considerations and a Bayesian ap- plication. Biometrika, pp. 265-274, 1981.
Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247 279, 2018. doi: 10.121417-A0S15499 10. 10t.0/o000/...111/7---00003
URL
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Sre- bro. Implicit regularization in matrix factorization. Advances in Neural Information Processing Systems, 30, 2017.
Arjun K Gupta and Daya K Nagar. Matrix variate distributions, volume 104. CRC Press, 1999.
Bruce Hansen. Econometrics. Princeton University Press, 2022.
Bruce E Hansen. The risk of James-Stein and Lasso shrinkage. Econometric Reviews, 35(8-10): 1456-1470, 2016.
Trevor Hastic, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949-986 2022.
W. James and Charles Stein. Estimation with quadratic loss. In Proc. 4th Berkeley Sympos. Math. Statist. and Prob., Vol. pp. 361-379. Univ. California Press, Berkeley, Calif,, 1961.
11

---

Published as a conference paper at ICLR 2025
Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez. The optimal ridge penalty for real- world high-dimensional data can zero or negative due to the implicit ridge regularization. The Journal of Machine Learning Research, (((1)6683368875 2020.
Zeng Li, Chuanlong Xie, and Qinwen Wang. Asymptotic normality and confidence intervals for prediction risk of the min-norm least squares estimator. In International Conference on Machine Learning. pp. 6533-6542. PMLR, 2021.
Yuan Liao, Xinjie Ma, Andreas Neuhierl, and Zhentao Shi. Economic forecasts using many noises. arXiv preprint arXiv:2312.05593 2023. URL
05593
Song Mei and Andrea Montanari. The generalization enror of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766, 2022.
Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge (less) regres- sion under general source condition. In International Conference on Artificial Intelligence and Statistics, pp. 3889-3897. PMLR, 2021.
Steven Ruggles, Sarah Flood, Matthew Sobek, Daniel Backman, Annie Chen, Grace Cooper, Stephanie Richards, Renae Rodgers, and Megan Schouweiler. IPUMS USA: Version 15.0 [dataset],
V15.0 2024. Minncapolis, MN: IPUMS.
Jack W Silverstein and ZD Bai. On the empirical distribution of eigenvalues of a class of large dimensional random matrices. Journal of Multivariate analysis, 54(2):175-192, 1995.
Jann Spiess, Guido Imbens, and Amar Venugopal. Double and single descent in causal inference with an application to high-dimensional synthetic control. In Thirty-sevnnth Conference on Neu- ral Information Processing Systems, 2023. URI. http:httt////petttt /ttttp:://operrevieew www.:nntttoummmoooo
dL.GGM9wttqq
Alexander Tsigler and Peter L. Bartlett. Benign overfitting in ridge regression. Journal of Ma- chine Learning Research, 24(123):1-76, 2023. URL http: http://mmr...oo wttpp.opp/ppppr///22/
22-1398 html
Denny Wu and Ji Xu. On the optimal weighted & regularization in overparameterized linear regres- sion. Advances in Neural Information Processing Systems, 13:10112-1011 2020.
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Benign overfitting of constant-stepsize SGD for linear regression. Conference on Learning Theory, pp. 4633- 4635. PMLR, 2021.
12

---

Published as a conference paper at ICLR 2025
A DETAILS FOR DRAWING FIGURE
To draw Figure ! we use a sample extract from American Community Survey (ACS) 2018. To have a relatively homogeneous population, the sample extract is restricted white males residing in California with at least bachelor's degree, We consider a demographic group defined by their age in years (between 25 and 70), the type of degree (bachelor's. s, master's, professional, and doctoral), and the field of degree (172 unique values). Then, we compute the average of log hourly wages for each age-degree-Fie field group (all together 7,073 unique groups in the sample). We treat each group average as the outcome variable (say, Va.d,f) and predict group wages by various group-level regression models where the regressors are constructed using the indicator variables of age, degree, and field as well their interactions: that is,
ya.d, = Fo.df $ Ea.d,f.
For the regressors Fa,d,f. we consider specifications ranging from 209 to 2,183 regressors:
Spec. 1 (p 209): dummy variables for age (say, Ta) + dummy variables for the type of degree (say, z.) + dummy variables for the field of degree (say, .yy),
Spec. 2 (p 391): Spec. + all interactions between and Ea.
Spec. 3 (p 598): Spec. + all interactions between zd and zf.
Spec. 4 (p = 778): Spec. + interactions between za and va + all interactions between and ft
Spec. 5 (p 1640): Spec. + all interactions between Ty and Ta + all interactions between va and zf.
Spec. 6 (p 1754): Spec. all interactions between za and x all interactions
between Fa and fy.
Spec. 7 (p 2182): Spec. + all three-way interactions among za Fd ayd.
Here, the dummy variable are constructed using one-hot encoding. We randomly split the sample into the train and test samples with a ratio of 1 4. The resulting sample sizes are 1,415 and 5,658, respectively. To understand the role of non-i.i.d. regressor errors, add the artificial noise the training sample: that is, we compute the ridgeless least squares estimator using the training sample of (Wa.d.f. a. ",, where Va.d.f Ya,d. + Ma,d,f- Here, the artificial noise tu has the form
Ua,d. (1- cc.es
/1--)2+6
where fa.d, o2), independently across age (a), degree (d) and field (/); ey is the average of another independent N(0, d²) variable within f (hence, ey is identical for each value of f) and thus the source of clustered errors; and E (0, 0.25, 0.5, 0.75) is constant that will be varied across the experiment. As gets larger, the noise has a larger share of clustered errors but the variance of the overall regression errors (u,, remains the same: other words, va. o² for each value of c. Figure | was generated with o 0.5 by generating the artificial noise only once.
13

---

Published as a conference paper at ICLR 2025
B DETAILS FOR DRAWING FIGURES 2 3 AND 4
2 and we sample (z; ) from NV N(, Σ) with E = UU-DUU where Us is an orthogonal matrix random variable, drawn from the uniform (Haar) distribution on O(p), and Dy is a diagonal matrix with its elements d; |=il/ 2x.1 |zi| being sampled with z; ~ (0, 1) for each i= 1,2, ... Pp. With this general anisotropic Σ, the term Ex (TT((A)>))// is somewhat larger than
To draw Figures
H Siso = = -7-11) 17-1] 1--1 which is in Figures2anne and since μM = and = 2. For example, in Figure 2 when o² = 11, p² O, we have Tr(22)/m = 1 but x [Tr(A ()] >
In Figure we fix n 50 and use p p- for E 100].
To compute the expectations of Ex [Var X)] and Ex Ex(TrAA-)) over X, sample Nx sam- ples of X's, X2, .Nx. Moreover, to compute the expectation over Var(3|X,)
Tr [ec[BTT] Ee Be] we sample N₂ samples of s's, $1,62,". E,, for each realization X,. To be specific,
Nx
Nx
N Ne
N₂
N
1
Ex (ar((
Var(
~
Tr
B
Bid
Big
Nx
Nx
N2
Ne
1=1
3=1
j=1
j=
Nx
Nx
1 Ex
Tr((X,X;)
Nx
Nx
Ax(x)X))))
X;b - yi. 0}. Wis = X, + Ej. and (x,X,)) is the k-th eigenvalue of X,X,J. We can do similarly for the variance part of the prediction risk. Figure shows an additional experimental result.
where Big = arg {
Prediction Risk Clustered Errors
Estimation Risk Clustered Errors
0.5
1.72
0.5
0.4
0.4
1
0.2
0.2
0.1 4M
0.1
55.0
0.1
0.2
0.3
0.4
0.5
0.1
0.2
0.3
0.4
0.5
of
of
We use a similar setting as Figure 3 for each experiment with the pairs (af.of). of). As expected, the off-diagonal elements pt of Q do not affect the expected variances.
Figure 5:
except uniformly sample each P from [0, 0.05]
14

---

Published as a conference paper at ICLR 2025
C
EXPERIMENTS WITH LARGE AND p
conduct the extra experiments with larger n and p (e.g., 10k and p = 150k).
n= 100, p 200, 2=
n= 500, p 1000, ==
0.5
0.5
0.4
0.4
0.1
0,1
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
p
500.p 2000,
0.4
0.4
0.3
0.3
0.1
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
o²
100,
1000, 10.0
500,
5000, 10.0
0.6
0.6
0.5
0.3
0.3
0.2
0.2
0.50
o²
o²
500, p 50k
500,
100k
15k, 150k
10a2
EXITIIX (111)-
10
EXITrIX 1
extTrixx T 100
our thwory:
our theory:
10-3
10~3
10
10
10-2
10
10-3
10
10
10
10-2
10-3
10-2
10
expected
Ediaart XIl
variance: ExiVart
EviVarté [X]]
Figure 6: [Top Three Rows] Estimation Risk in Example 2.1 (AR(1) Errors) with a wide range of (n. p) pairs. See caption of Fig 2 (Right) for more details. Panels in each row have the same y = 2, 4, 10 (Top, Middle, Bottom). With the same y, it shows almost identical results for each row [Last Row] Large scale validation with 50000 = 50k (Left), p = 100k (Middle), and p = 150k (Rigth). cf. æ; IRP (CIFAR-10 & 3.1k and ImageNet ~ 150k).
15

---

Published as a conference paper at ICLR 2025
D PROOFS OMITTED IN THE MAIN TEXT
Proof of Lemma 3.3
For given A S, since A-1 S, we have Z _ A- := Z and
Ez]f(Z)] = =z]((Z] = E2If(AZ)) [z[](AZ)).
This naturally leads to
BglBas= = E = [ =
where the first equality comes from Fubini's theorem and the integrability of f.
Proof of Theorem 3.4 Since = Xty, we have Cov (X) = XtCov(y X) X)X = XiΩxiT, which leads to the following expression for the variance component of prediction risk:
Varg X) Tr(Cov(B x)E) Tr(xixxt Σ) = |Sx ||BT|
where 1y/2 T 12'/2, and B Sxi. Using the singular value decomposition (SVD) B rewrite this as follows:
and 7', respectively,
|BT =
where B = UDVT and T DVD with orthogonal matrices U, V. UT, VT, and diagonal matrices D. Dr. Now we need to compute the alignment V UT of the right-singulat vectors of B with the left-eigenvectors T.
DT
Σ
Di Σ
Vi (UT)
=
k=1
h== X= X3
(T) (
sggil A ((x X) (9)m
A(2)
1xn
where Tyy = (V., (UT):))² 2 0, r(X) = (Tu))a E Ruxa and A(A) E R" is a vector with its element (A) as the i-th largest eigenvalue of A.
Therefore, we can rewrite the variance as Vars(3 [ [x) = ((x))TTXXXX with with
a(X) = ((XT X) E R", b = X(2) RR".
T(X); My = (v, n 0))
where (1() : Vi, and (1)) = (Ur).j. Note that the alignment matrix T(X) is a doubly stochastic matrix since E, Y/s Σ. ?t and S 7/o S 1.
Now, we want to compute the expected variance. To do so, from Lemma 3.3 with S (n)), we can obtain
Ex (x ((X))] = Ex [oox)
Ex (ox))"o=.(((OO)))
where is the unique uniform distribution (the Haar measure) over the orthogonal matrices O(n). For an orthogonal matrix O E On), we have
r(OX); (O)(0) 000)2= = (T o.
since S(OX)! T TOT UD(OV)T. Here, (OX)t = X follows from the
orthogonality of E O(n). Since the Haar measure invariant under the matrix multiplication in (n)). if we take the expectation over the Haar measure, then have
T T(X); Eo.,, ((0X) = Eo-. (0) OT (1))) oTuti
Eo- Eo-w((u (u OTTTTTOTT o0TTT
16

---

Published as a conference paper at ICLR 2025
Here, for given we can choose matrix O6) E O(n) such that its first column is xt) and OG) u()) e1, then r(X); is independent of (say [(X);) aạ). Since r(X) is doubly stochastic, so is ((X) and we have Σj=1 [(X); = no; = I which yields [(X);; = a; = 1/n, regardless of the distribution V: thus, T(X) J. where Jıj [(i.j 1.2. n).
32
Therefore, we have the expected variance as follows:
Ex [arr::B X)] = Ex Ex(a [a(x] - Jb] Σ
Ex (X]]b ( TYO).
m
Proof of Corollary
4.3 Note that
Tr(2) E [[r((()))
Ex
p
A
Tr(2))
Ex
d (p(s)
Tr(?)
[dpxx(/m(s)) (m(s)
Ex
Then, the desired result follows directly from (5)
Proof of 4 The bias term of the prediction risk can he expressed as follows:
[Biasz(3 X)]²
||ا| x] - B1
-|(S// 1)
(I -I ビンンز
-T lim A05: + +1) ' lim 2(5 1
2
=SS) lim - + AT) 253,
A
where Σ = XTX/n. Here, the fourth equality comes from the equation
I -ーン lim (
A
lim (8) + A1) 1 " A N
A
lim A( A
Proof of 7 The RHS of (6) is bounded above by f T+ogs- dd(()) = Ttege and thus
s which yields s* S CH -- We can similarly prove the other inequality in 7 with a lower
bound I+Chs* on the RHS of 66
Proof of 8 To further explore the inequalities 77.. rewrite (6) from Theorem 4.7 follows:
Er~H [g[T;s")], where g(:;s) = + is
for f, 0.
Here, since g(t;s) s) is convex with respect to for a given 5 > by Jensen's inequality, we then have
stmn) 2 g (pH: s = g(1 s = 1 1
where ba Er.H(T]. Therefore, the limit Stieltjes transform s* in the anisotropic case should be larger than HH Sh of the isotropic case satisfy Er~H [g(T; s*]] =
Y since g(t; s) is a decreasing function with respect to s 2 0 when t This leads to a tighter lower bound
-1
s* 1H 0/000 2H 1 -1)-1 than 7 because pm S Cn.
-1
17

---

Published as a conference paper at ICLR 2025
E RIDGE REGRESSION
We can easily extend Theorem 3.4 to the ridge regression case with the ridge estimator Bx = arg minseRs {||Xb yll2 + |||la 2, i.e., 3x = -
Theorem E.1. Let Assumptions
2.7 and 3.2 hold. Then, we have
Ex (x(rsss388 x)] (T())xx(TT(() x XX x
Sketch of Proof. The ridge estimator is 32 = Pay, where Pa = (X X + AT)- With Bx 1// PA and T = 12 we can rewrite the variance as follows:
Var x) [BTI |UDAV SOAVVUTDrAA 11 |D UT Un
from the singular value decompositions Bx UT and T DTVVV with orthogonal ma- trices U, V, Ur, Vr, and diagonal matrices Dx, Dr. Note that U. do not depend on X. Then, we need to compute the alignment V UT of the right-singular vectors of B, with the left-eigenvectors of I' because
IDAVTU = (PAPPT T(X)((1) T(X)o,
where a(X;A) = ((P.PT R = X(2) E R", v = Vi, u() == (UT),,, Yi == (u((), w()0)² 2 0, [(X) = (1t)aa RR and X(4) R" is vector where its elements the cigenvalues of A.
Now, we want compute the expected variance. To do so, from Lemma 3.3 with S O(n) and the left-spherical symmetry of X, we can obtain
Ex A) T(()6]] = Ex [Bo-= A) [[OX)o]] = Ex [a(X:A) [oxx/
where y is the unique uniform distribution (the Haar measure) over the orthogonal matrices O
Here, we can show that (TxO) JJ where is the all-ones matrix with Jis 1(i,j 1. .n) Therefore, we have the expected variance as follows:
Ex (a Xx] = Ex a( x( 1
Ex (X;
+ XX - Tr())
Similarly, Theorem 3.5 can be extended as follows:
Theorem E.2. Let Assumptions
2.1 and 3.2 hold. Then, we have
Ex Var B
X)]
((00)E([TT(AA (
np
where XXT /pppppuee U for some orthogonal matrix U E O(n).
18


Reviews:
[{"review_id": "982fWHlmHb", "reviewer": "Reviewer_4djy", "summary": "In this paper, the authors investigate prediction risk and  estimation risk under more general regression error assumptions beyond i.i.d. errors. In particlar, they explore the benefits of overparameterization in a more realistic setting, which allows for clustered or serial dependence. This paper  demonstrated   that the estimation difficulties associated with the variance components  can be summarized through the trace of the variance-covariance matrix of the regression errors.", "questions": "I have several comments and suggestions for the authors to address.\n\n\n1. The paper is not complete. Please add the conclusion section in the revision. \n\n2. It is worthwhile to extend the proposed approach from the case  p>n   to the ultra-high dimensional case with p=exp(n). \n\n3. It is of interest for the authors to  compare   proposed method with existing ones  (including  Chinot et al. (2022) and Chinot & Lerasle (2023), etc.)  in the experiments.\n\n4. The new idea about benefits of over-parameterization could be extended to time series, panel and grouped data.  It is helpful  for the authors to  elaborate it by proving more details.\n\n5. There are some  typos, grammatical errors,  etc. in the paper. Please check it in the revision carefully. \n\nin page 1, line 022, \"can extend\" -> \"can be extended\". \n\nin page 5, line 312, \"appendix\" -> \"Appendix\".\n\nin page 9, line 432, \"appendix\" -> \"Appendix\".\n\nin page 10, line 500, \"appendix\" -> \"Appendix\".\n\nin page 14, line 704, \"Figure\" -> \"Figures\".\n\nin page 17, line 905, \"6\" -> \"(6)\".", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is written clearly.  I appreciate the significant contribution to high-dimensial data analysis.  The new approach is  promising for \n more  broad framework. This paper attacked the very challenging problem involved in least-squares estimators beyond the  assumiption with  i.i.d.  errors. The new idea about  benefits of  over-parameterization could be extended  to time series, panel and grouped data, etc.  with the broad impact.", "weaknesses": "The paper proved several  good theoretical results and properties. The experiemts of data set may not be comprehensive, Since there is no comparison of  the  proposed method with existing methods.   In addition,  the proposed approach only works for  the case  p>n. In practice,    the ultra-high dimensional case with p=exp(n) is very  common.  This is a more realistic setting in the big data era.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yNPNVwkd06", "reviewer": "Reviewer_Wss5", "summary": "The paper extends the analysis of ridgeless least squares estimators to more\nrealistic error structures beyond the traditional i.i.d. assumptions. It\naddresses both prediction and estimation risks in settings where regression\nerrors may be correlated or exhibit heteroscedasticity.\n\nThe authors provide exact finite-sample expressions for both types of risk,\nwhich are decomposed into bias and variance components. The variance in\nprediction risk is shown to be the product of two distinct terms: one related to\nthe error covariance matrix and the other dependent on the feature distribution.\n\nThe paper also conducts a systematic asymptotic analysis of prediction and\nestimation risks. Numerical experiments with autoregressive and clustered\nregression errors illustrate the theoretical findings.", "questions": "1. Include discussions on relevant regularized least squares estimators, and\n   provide scenarios where the ridgeless least squares estimator excels or\n   underperforms.\n2. Provide comparative experiments with other regularization techniques to\n   demonstrate where ridgeless least squares excels or underperforms.\n3. Add discussions on the limitations of the current investigation, particularly\n   in terms of the assumptions.\n4. Provide discussions connecting the results in the high-dimensional setting to\n   those in the low-dimensional setting.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Originality:\n\nThis paper extends the analysis of ridgeless least squares estimators by\nrelaxing the i.i.d. assumption on the regression errors. Correlated and\nheteroscedastic errors are frequently encountered in practice but are not\ninvestigated in prior works in the high-dimensional setting. This work fills a\ngap in understanding the performance of least squares estimators, extending the\nobservation of double descent to more general settings.\n\nQuality:\n\nThe paper is technically sound and comprehensive in its treatment of both\nprediction and estimation risks. The finite-sample and asymptotic behaviors\nfinite-sample results are rigorously presented. The numerical result in Section\n1 demonstrates the motivation of the generalized assumptions and the results in\nSection 3.3 help validate the theoretical findings.\n\nClarity:\n\nThe paper is overall well written with clear presentation.\n\nSignificance\n\nThe paper extends the theory of least squares estimators to include the\nsituation with non i.i.d. errors in the context of overparameterization. It fill\na gap in the literature, so the results deserve to be documented.", "weaknesses": "For the high-dimensional setting considered in the paper, ridgeless least\nsquares estimators are seldom applied in practice. Regularization is almost\nalways helpful, and there is a large body of literature demonstrating the\nadvantages of regularized least squares. The paper should at least discuss this\nline of research. In particular, it has been shown that optimized ridge\nregression avoids bias inflation. Why, then, would practitioners care about\nridgeless least squares estimators in this scenario?\n\nWhile the assumptions are more general than the i.i.d. case, the scenario\nconsidered is still much simpler than what is encountered with real, practical\ndata. For example, the assumption of left-spherical symmetry for the design\nmatrix is limiting in practical scenarios. Most real-world datasets feature\nasymmetrical or skewed distributions, and many variables in real data are\nactually categorical, rather than numerical. It would help to add discussions on\nthe limitations of the current investigation in these contexts.\n\nMost of the theoretical results, especially the finite-sample results, appear\nsimilar to the low-dimensional or fixed-$p$ case. It would be helpful to include\ndiscussions on this point. If the results are not the same, do they reduce to\nthe low-dimensional results? Even if they have the same expression, it would be\ninsightful to explain why it is nontrivial to derive these results in the\nhigh-dimensional setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "B3BzPLjIH9", "reviewer": "Reviewer_CYv5", "summary": "This paper studies the prediction and estimation risks of the ridgeless least square regression under a more general assumption on the noise. Specifically, consider the data\n$$\ny_i = x_i^\\top\\beta + \\epsilon_i,\\ i=1,...,n\n$$\nwith target $\\beta\\in\\mathbb{R}^p$ and $ \\epsilon_i$ is the noise independent of $x$ with $\\mathbb{E}[\\epsilon]=0$ and $\\mathbb{E}[\\epsilon\\epsilon^\\top]=\\Omega$ finite and positive definite. This includes the case of i.i.d. Gaussian noise, autoregressive noise and cluster noise.\n\nThis paper applies the classical bias-variance decomposition onto the risks and finds a closed form expression for the variance term for both risks.", "questions": "I believe this paper could improve its significance if it can answer the following questions:\n\n1. What new insights could one gain from Theorem 3.4, 3.5?\n\n2. Related to Q1, the true noise covariance $\\Omega$ is not observable in reality. Could the authors provide any examples or algorithms to approximate such noise covariance in real-world datasets? If it is impractical to approximate it, how could we still analyse the risk with your risk expression in $\\Omega$? \n\n3. Could the authors extend their results to more general settings like kernel ridge regression or kernel gradient flow? Or at least explain what are the technical difficulties that might hinder the extension?\n\n4. One Central idea of regularization is to balance out the effect of the noise in the labels. With the ridgeless linear regression setting, this paper unfortunately misses the opportunity to discuss the important interplay between the non-i.i.d. noise and regularization, which I find quite disappointing.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper provides rigorous proof and experiments to validate their claim. The assumption on the noise and the input is more general than previous works.", "weaknesses": "However, my biggest concern is the significance of the contribution provided by this paper. \n\nAs mentioned in line 132-133, this paper is not the first to consider non-i.i.d. Gaussian noise. Although this paper requires less assumptions on the noise than [1], it does not contain enough illustrations or interpretations on their main results (Theorem 3.4, 3.5) for \"allowing potentially adversarial errors\" as promised in line 142-143. Indeed, this paper does not explain how their main results could recover previous result with i.i.d. Gaussian noise or gain new insights with more general noise.\n\nAlso, it seems that the techniques used in the main results are rather standard and can be extended easily to more general settings like kernel ridge regression or kernel gradient flow, which could potentially increase the significance of this work.\n\n\nReference:\n[1] Geoffrey Chinot and Matthieu Lerasle. On the robustness of the minimum ℓ2 interpolator.\nBernoulli, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)