Risk and cross validation in ridge regression with correlated samples
Authors: Alexander Atanasov
Jacob A Zavatone-Veth
Cengiz Pehlevan
Venue: ICML 2025 poster (2025)
Keywords: Linear regression
random matrix theory
Primary area: deep_learning->theory

Abstract: Recent years have seen substantial advances in our understanding of high-dimensional ridge regression, but existing theories assume that training examples are independent. By leveraging techniques from random matrix theory and free probability, we provide sharp asymptotics for the in- and out-of-sample risks of ridge regression when the data points have arbitrary correlations. We demonstrate that in this setting, the generalized cross validation estimator (GCV) fails to correctly predict the out-of-sample risk. However, in the case where the noise residuals have the same correlations as the data points, one can modify the GCV to yield an efficiently-computable unbiased estimator that concentrates in the high-dimensional limit, which we dub CorrGCV. We further extend our asymptotic analysis to the case where the test point has nontrivial correlations with the training set, a setting often encountered in time series forecasting. Assuming knowledge of the correlation structure of the time series, this again yields an extension of the GCV estimator, and sharply characterizes the degree to which such test points yield an overly optimistic prediction of long-time risk. We validate the predictions of our theory across a variety of high dimensional data.

Risk and cross validation in ridge regression with correlated samples
Alexander Atanasov 12
Jacob A. Vavatone-Veth 23 Cengiz Pehlevan 245
Abstract
& Potters, 2003; Mudelsee, 2014; Williams & Linderman, 2021) reederinn results obtained under the i.i.d assump- tion inapplicable. In particular, estimators of the out-of- sample prediction risk based on cross-validation assume independence (Golub et al., 1979; Craven & Wahba, 1978; Bates et al., 2024; Xu & Huang, 2012; Gu & Ma, 2005; Xu et al., 2018; 2019). To enable accurate prediction of risk for regression from timeseries data, it imperative that correlations be taken into account.
Recent years have seen substantial advances in our understanding of high-dimensional ridge regression, but existing theories assume that training examples are independent. By leveraging techniques from random matrix theory and free probability, we provide sharp asymptotics for the in- and out-of-sample risks of ridge regression when the data points have arbitrary correlations. We demonstrate that in this setting, the generalized cross validation estimator (GCV) fails to correctly predict the out-of-sample risk. However, the case where the noise residuals have the same correlations as the data points, one can modify the GCV yield cofipualtyy-oompuaall unbiased estimator that concentrates in the high-dimensional limit, which we dub CorGGCV, We further extend our asymptotic analysis to the case where the test point has nontrivial correlations with the training set, a setting often encountered time series forecasting. Assuming knowledge of the correlation structure of the time series, this again yields an extension of the GCV estimator, and sharply characterizes the degree to which such test points yield an overly optimistic prediction of long-time time risk. We validate the predictions of our theory across variety of high dimensional data.
In the paradigmatic setting of ridge regression, a signifi- cant body of recent research has aimed to provide sharp asymptotic characterizations of the out-of-sample risk when the in-sample risk is estimated using i.i.d. samples (Hastie et al., 2022: Dobriban Wager, 2018: Advani Ganguli, 2016; Canatar al., 2021b; Loureiro et al., 2021: Atanasov et al., 2024; Mel & Pennington, 2021; Mel & Ganguli, 2021; Bordelon et al., 2020; Jacot et al., 2020; Gerace et al., 2020). The crucial feature of these nigh-dimensional asymptotics is that they allow both the dimensionality of the covariates and the number of examples to be large.' This body of work reveals two broad principles: First, ridge regression has a spectral bias towards learning functions aligned with eigen- functions of the feature covariance (Canatar et al., 2021b; Bordelon et al., 2020; Mel & Pennington, 2021; Mel & Gan- guli, 2021). Second, ridge regression displays Gaussian universality in high dimension, i.e., the out-of-sample risk for a given dataset will under general conditions be asymp- totically identical that for a Gaussian dataset with matched first and second moments (Hastie al., 2022; Montanari & Saeed, 2022; Hu & Lu, 2022). Importantly, nearly all of these works assume the training examples are i.i.d.. A rare exception is recent paper by Bigot et al. (2024), who allow for independent but non-identically distributed Gaussian data with per-example modulation of total variance.
Statistics classically assumes that one has access to inde- pendent and identically distributed (i.i.d.) samples. How- ever, this fundamental assumption is often violated when one considers data sampled from a time series-e.ge in the case of financial, climate, neuroscience data (Bouchaud
These sharp asymptoties are omniscient risk estimates: they assume one has access to the true joint distribution of co- variates and labels from which the training set is sampled. If one wants perform hyperparameter tuning in practice- for ridge regression this of course means tuning the ridge parameter-a non-omniscient estimate is required. A stan- dard approach to this problem is the method of generalized
"qqual contribution 'Department of Physics, Harvard Uni- versity 'Center for Brain Science, Harvard University 'Society of Fellows, Harvard University "The John A. Paulson School of Engineering and Applied Sciences, Harvard University 'The Kempner Institute for the Study of Natural and Artificial Intelli- gence, Harvard University. Correspondence to: JAZ-V <jzavaton- eveth @ fas. harvard.edu>, CP <epchlevan@ seas hdd
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
In contrast, classical asymptotics assume that the dimension is small relative to the number of examples (Hastic al., 2009).

---

Risk and cross validation in ridge regression with correlated samples
cross-validation, which dates back least the 1970s (Golub et al., 1979; Craven & Wahha, 1978; Bates al., 2024). The GCV estimates the out-of-sample risk by apply- ing a multiplicative correction to the in-sample risk, which itself can be estimated from the data. Recent works have shown that the GCV is asymptotically exact in high di- mensions: the limiting GCV estimate coincides with the omniscient asymptotic (Jacot et al., 2020; Hastic et al., 2022: Atanasov et al., 2024). Though classical cross-va voss-vaaldationn and the GCV estimator assume i.i.d. training data points, several works have aimed to extend these methods to cases in which there are correlations (Altman, 1990; Opsomer et al., 2001; Carmack et al., 2012; Rabinowicz & Rosset, 2022; Lukas, 2010; Wang, 1998). However, most of these works focus on correlations only in the label noise, and none of them show that their estimators are asymptotically exact in high dimensions. Indeed, we will show that none of the previously- ppopposed corrections to the GCV are asymptoti- cally exact in high dimensions, and require further modifi- cation to accurately predict -ut-of-sample risk.
1. Setup and notation
We begin by briefly introducing the setup of our work, and fixing notation. We consider ridge regression on a dataset D (æe, yt ) of T data points, with N N-dimensional covariates 2; E RN and scalar labels yt- We minimize the mean-squared error over this dataset, with ridge penalty:
1 L(w) = T Σ U3 - o w) + A/|w|1?
We write tü = argmin ( As long as À 0 the solution is unique. We will consider both the underparam- eterized case of classical statistics where T' > N as well as the modern overparameterized setting where N > T (Hastie et al., 2022). We define the overparameterization ratio q = N/TT. All of our results will hold exactly in the limit of N, T
with g fixed.
We now state our statistical assumptions on the data. Defin- ing the design matrix X E RT'NN such that Xs; = [ and collecting the labels into a vector E IR", we assume the labels are generated from a deterministic linear "teacher" v E S plus noise c E R." as:
Here, we fill this gap understanding by providing a de- tailed asymptotic characterization of ridge regression with correlated samples. We first show that even under rela- tively mild sample-samplc correlations previously-obtained omniscient risk asymptotics assuming i.i.d. data are not predictive. Correspondingly, the ordinary GCV estimator fails to accurately estimate the out-of- sft-ol-sample risk. We then compute sharp high-dimensional asymptotics for the out-of- sample risk when the training examples are drawn from a general matrix Gaussian with anisotropic correlations across both features and samples. When the test point is uncorre- lated with the training data and the label noise has the same correlation structure as the covariates, we show that there exists a corrected GCV estimator. We term this estimator the CorrGCV. Unlike previous attempts to correct the original GCV, ConGCV is asymptotically exact (Figure 1).2
y= X +
We assume that X is Gaussian, with zero mean and
B(m1,123,]== KigKis
(1)
for a feature-feature covariance E E RR and a sample- sample correlation K E RTx We have the representation
X = K1/2 12/2 for Z E R.TN a matrix with i.i.d. standard Gaussian elements Zes NN 1), where / denotes the principal square root of the positive-definite symmetric matrix Σ. We assume that the noise is indepen- dent of X, and is Gaussian with mean zero and covariance Eleees] = = K's-
Without loss of generality, we will always assume the nor- malization 1. Tr (K) = 1, as the overall scale can be ab- sorbed into Σ. We will often assume that the data are statis- tically stationary, in which case K2: = 1 for all t; we will explicitly highlight when we impose this condition. Simi- larly, we normalize 1 Tr(K') 1, as the scale here can be absorbed into de.
In deriving the CorrGVV, we uncover interesting duality between train-test covariate shift and mismatch in the covariate and noise correlations. Finally, we extend all of these results to the case when the test point is correlated with the training points. Focusing on the setting of time series regression, this gives us a sharp characterization of how accuracy depends on prediction horizon, and makes precise the notion that testing on near-horizon data gives an overly optimistic picture of long-tern forecast accuracy. In all, our results both advance the theoretical understanding of ridge regression in high dimensions and provide application to time series data.
We contrast this with prior treatments of linear regression in the proportional limit where K, K' were chosen to be the identity matrix (Hastie et al., 2022; Dobriban & Wa- ger, 2018; Advani & Ganguli, 2016; Canatar et al., 2021b; Loureiro et al., 2021; Atanasov et al., 2024; Mel & Pen- nington, 2021; Mel & Ganguli, 2021; Bordelon et al., 2020; Jacot et al., 2020; Gerace et al., 2020), and where the origi- nal GCV estimator (Golub et al., 1979) applies. In Section 3.2 we consider the case where K- = K'. There, we show that the GCV estimator (Golub et al., 1979) has a natural analogue. In Section 3.3 we consider the more general case and show that there is an obstruction to a GCV estimator.
*Code compute the ConGCV and reproduce all of our experiments is publicly available on GitHub at http://github..om/PPhheeee wtw.oo/eeeeeeaearrorssss.... Group/SS.ransffom
2

---

Risk and cross validation in ridge regression with correlated samples
Exponential Correlations N 100 a=1.8/ 0.3 {= 1e-02, == 1e04,, 0.05
Correlated Regression N 100 0-1.8, 0.3 1e+02. lee-04, 6,
10F
10a4
10a
10
Error
10-3
Vary
10
Nalve GCV,
Nalve GCVs
CorrCCV
10"4
10:
10
10
10a
10a
10>
T
Figure 1. Empirical risk R. out-of-sample risk R. and fine-grained bias-variance decompositions for ridge regression with structured features and correlated examples. Theory is plotted in solid lines. Experiments with error bars over 10 dataset repetitions are plotted as markers. The data points are exponentially correlated as E( æs] xx e --tt-1// Left: Weak correlations, & = 10 10-? Here, the generalized cross validation method (orchid) as well as its other proposed corrections in the presence of correlations (pink, purple) all agree and are overlaid. Right: Strong correlations, Ç 102. Here, we see that naive estimates of the GCV proposed in prior works in this setting. They either underestimate (purple) overestimate (pink) the out-of-sample risk. We define the naive GCVs in the text, and connect them with prior proposals in Appendix G. By contrast, our proposed estimator, ConGCVV correctly predicts the out-of-sample risk in all settings.
We define the empirical covariance Σ = X X and kernel Gram matrix K = + X Writing y E RRT as the vector of training labels and E E R²" as the vector of label noises, we have:
for some positive-definite matrix M (Bouchaud & Potters, 2003; Hastie al., 2009). Indeed, the Bayesian minimum squared error estimator is equivalent minimizing this loss with M (K'))² (Appendix H). However, under our assumptions on the data this is equivalent to considering an isotropic loss under the mapping K + 1 K 1/2 and K' + 1/ 1/2 As result, our asymptotics for Rg apply immediately to general choices M.
X T We also let 9 Xw be the vector of predictions on the training set. We are interested analytically characterizing the in-sample and out-of-sample risks. The in-sample risk is defined as:
き - (É- X -
T
2. Deterministic equivalences
Ren (10)
71
1 1y 9.13
We now introduce the key tools of our analysis: determinis- tic equivalents for the sample covariance. We first review standard aspects of the free probability approach to random matrices, and then state the required deterministic equiva- lents. Our presentation of free probability follows Potters Bouchaud (2020).
For the out of sample risk, we we consider a held-out test point x and label noise drawn from the same marginal distribution as single example æz, ct, discarding the time- dependent scale factor Ket in the marginal:
Rout (i) = Ex, (x:
1 + x )
iw
Σ
w)) T toa.
2.1. Weak deterministic equivalents
Here have identified the generalization error Rg as the excess risk, i.e., Rows minus the Bayes error o². We study the case where the test point and label noise are drawn independently from the test set in Section 3. We study the more general case where x, have nontrivial correlations with the training set in Section 5.
We define the first and second degrees of freedom of matrix E I N as
df
(F)(A) (A) = Tr + A)
N
d (A) N
When it is clear from context, we will write these as df,, dfg- The S-transform S(df) is a formal function of a variable df defined as
One could instead consider an estimator based on a weighted loss, Le.. ÜM arg min,, LM (w) for
Lm (w) (Xw v) M M(xw y) 2/we2
1 df
(d(f df df (df)
(2)
3

---

Risk and cross validation in ridge regression with correlated samples
Here 7 is the functional inverse of the equation df df (A), df A (af (A)) x. We will use the symbol df to highlight its role as a formal variable in the S-transform, whereas we will call df1 the actual value of the degrees of freedom for a given matrix A at ridge X. Our definition of SA differs by a sign from the common definition of the S transform in terms of the /-function L (A)) = -df'
2.2. One-point strong deterministic equivalents
The equivalence (3) extends to class of 'equalities' of matrices known strong deterministic equivalents:
Definition 2.1 (Strong deterministic equivalence). For two sequences of (possibly random) matrices A and B in- dexed by their common size N, we say that A and B are deterministically equivalent and write A = B if (T(AM)/((MM))) - 1 in probability as N + oo for any sequence of test matrices M of bounded spectral norm.
(2) implies that:
1
dr's (A) 1+ A (df (A))
The S-transform plays a crucial role in high-dimensional random matrix theory and free probability because for two symmetric matrices A, that are free of one another, tak- ing the symmetrized product A B 1/2 BA with 1/22 the principal matrix square root yields:
For the Wishart matrices Σ and K, we have:
Lemma 2.2. Let and R be as in (3). Then,
Σ + +1 > + k)
(6)
K(K 2) K (K +R)
(df) = SA (ddd)))(((f))
This implies the following subordination relation:
Proof. We derive (6) using a diagrammatic argument in Appendix C.I; see Potters & Bouchaud (2020); Bun et al. (2016a); Atanasov et al. (2024) for alternative proofs.
df A.B(A)
+ ASA. (d) (A))
(3)
1+ AS AB (A)) (A))
Using the one- mee-point deterministic equivalents, we see that A and R are related by the identity gdf; 2d = gdf (A) dr k (A) = dfx(R) dr, In addition, we show in Appendix C that k and R satisfy the duality relation:
= df (AS (df)
We define what it means for two random variables to be free, and give a longer discussion on subordination relations and R and S transforms in Appendix B. Often, one views B as a source of multiplicative noise, and A as deterministic. Then A * B random matrix. The above equation thus relates the degrees of freedom of random matrix to the degrees of freedom of a deterministic one. For this reason it is known as (weak) deterministic equivalence.
dr
In physical terms, we can interpret (6) as renormaliza- tion effect: the effect of the random fluctuations in B can be absorbed into a renormalized ridge x (Atanasov et al., 2024). This renormalization generates implicit regulariza- tion. Even in the limit of zero regularization, one can have limx-o (Appendix F).
We now specialize to the Wishart matrices Σ = } x
and k = 1 X we consider here, though subset of the subsequent results extend to more general ensembles (see Appendix B and (Potters & Bouchaud, 2020; Atanasov et al., 2024)). Define the shorthand df, = (xx) df, = d (R), df,2 = (1t), and dfz = df (R). Then, we define x and R via:
2.3. Two-point strong deterministic equivalents
As (6) involves a trace against a single test matrix, we refer to it as a 'one-point' equivalent. We will also require 'two- point' equivalents involving pairs of resolvents:
(ddff) R= ( As the multiplicative noise a structured Wishart matrix, the S-transforms appearing in (4) are
(4)
Lemma 2.3. Let E' be N N test matrix. Then, E'
[ + K)
s(df,) = 5 z Sd
N df,
+ 5 Σ + x) " EΣ,''
T
1-
(5)
T
where we define
š((n) = S zz (dri)
dr,
N
dfa dit
dfg df df
イ = df, df,
and wx. =
For uncorrelated data (K = 1), SK 1. Weak determinis- tic equivalents for Wishart matrices with general correlation structure have long been subject of study in random matrix theory due to their applications to covariance matrix estima- tion (Burda et al., 2005b;a; Burda & Jarosz, 2022; Potters & Bouchaud, 2020).
for
a N
1/2
Tr EE
Proof. See Appendix C.2.
"Our convention here follows Bach (2024).

---

Risk and cross validation in ridge regression with correlated samples
When K I, this recovers two-point equivalents proved in previous works (Bach, 2024; Patil & LeJeune, 2024). The
GCV (Golub et al., 1979; Craven & Wahba, 1978):
1²² Rout X² Rin = 52
first term is "disconnected" component coming from sepa- rately averaging the two resolvents, while the second term is a ''comnected' component coming from averaging them together. These two contributions correspond to the bias- variance decomposition of the estimator over the training data. An analogous deterministic equivalent holds for K': state this explicitly in Appendix C.
Since S depends only df1, which can be estimated solely from the data, the right hand side of this equation yields way to estimate the out of sample error from the training error alone. The GCV estimator has also appeared in recent literature as the kernel alignment risk estimator or KARE (Jacot et al., 2020). The fact that the GCV estimator is directly related to the S-transform in the free probability regime N + oo was first pointed out in our previous work (Atanasov et al., 2024).
We also derive a final required two-point equivalent:
Lemma 2.4. Let K' be a T x T test matrix. Then,
Σ + X T K' [ + A)=
~ 5 + A) " dl K.
3.2. Correlated data with identically correlated noise
1-7 Tr KK (K + 1..
We now state the results for general correlated data with matched correlations between the covariates and noise
where we let di K
1 T
(K K'). Using the deterministic equivalents introduced in Section 2, we obtain:
Proof. See Appendix C.2.
Theorem 3.2. Assume K ==a K-K'. Then, we have
3. Predicting an uncorrelated test set
x²
Rg = 1-7
EE + 1;)
2w +
1 - 0e
3.1. Warm-up: Linear regression without correlations
where
We begin by reviewing the known results in the case where the data points are assumed to be drawn i.idd from distri- bution with covariance Σ. This is case of K = I introduced above. In this case, we require only x and not R, which satisfies the simplified equation
df2 dfz dr dr,
7
Similarly, we obtain:
Run df, dip x²
Σ(Σ + x) -'o
1 1 w
A
Sdf,
K = == ( I- -dr
(7)
df, - df2 1
?..
where d (1)) ~ ar (A). Here we have used that the S-transform of Wishart matrix is 5 2 - (1 --ddd)f)=
sdr, 1 7
At this point, we note that depending on whether one picks df, (k)) or df, df= (A), this either gives a self- consistent equation given omniscient knowledge of Σ or a way to estimate x from the data alone, namely by com- puting (A). Then, one has the following deterministic equivalents:
Proof. See Appendix C.4.
This yields an extension of the GCV estimator to correlated data. We call this the CorrGCV for correlated generalized cross-validation:
Theorem 3.1. For uncorrelated data (K- = I), one has n²
df,
Bont S(di)
Rin-
Rg 1-7
w
E>{{++ +
? 22
df, df,
1 1-9
This estimator is unbiased and asymptotically exact in the proportional limit T, .N + co. Moreover, it concentrates over draws of the dataset for T sufficiently large.
where 7 = gdfz. and
X²
X2
Rin ~ 1- in =))++))+
2
w
+
7 0
R21
Like the ordinary GCV, the ConrGVV can be estimated from the training data alone. We give the explicit algorithm in Appendix A. In Figures 1, 2, 3, 4, and 6 and Appendices G and J we compare this estimator with other previously proposed estimators of out-of sample risk in correlated data. In partieular, we compare against the ordinary GCV
Proof. This result is well-known (Hastie et al., 2022:
Atanasov et al., 2024; Bordelon et al., 2020; Canatar et al., 2021b; Dobriban & Wager, 2018: Loureiro et al., 2021). It follows as a special case of the proof in Appendix C.4. n
Naive GCV, - (1-qdf,)
This yields the generalizeddccoos--vviiaaaaaiidd estimator or
5

---

Risk and cross validation in ridge regression with correlated samples
Correlated Regression N= 100 u=111 0.8 {= 1=+020 q=0,91, 0.05
3.3. Mismatched correlations and OOD generalization
We generalize the above result a setting where does not have the same correlation structure K. That is, B[c,c,] of o2Ky, In fact, we consider an even more general case: namely when the covariance of the test point E' is also different from the covariance of the training set Σ. This is the case of ditoo--distribution generalization under covariate shift. These two different mismatches exhibit a surprising duality. In general, we have
R
10a4
Blas'
Var,
10:4
Vats
Naive GCV,
Natve GEV, CorrCV
10
10-2
Theorem 3.3. Consider covariate-shifted setting with test covariance E' not necessarily equal to E, and noise covariance K' that may not match K. Then, we have Rg ~ R ww + +n) 1 + x
A
Figure 2. Estimating the optimal ridge parameter for exponential correlations using the ConGGVV. The setup here is as in Figure 1. We that only the ConGCV accurately predicts the out- of-sample risk, and thus is the only estimator that allows one to correctly pinpoint the optimal ridge parameter X.
Blas
+ x²2 E.,'' w M
20
EE, K,K'
1-9
Varx
Varxe
(8)
Here, have highlighted how the risk naturally splits into three terms given by respective bias and variance compo- nents resulting from the covariates X and the noise as
outlined in Appendix D (Atanasov et al., 2024). We have also defined:
which does not take into account the sample-sample correla- tions, and the estimator proposed by Altman (1990),
df
dr df K. df
YE. =
KKK''
df
Naïve GCV, S (x/A)²
which was designed to account for sample-sample correla- tions in the label noise but not in the covariates. Further comparisons to the estimator Carmack et al. (2012) are given in Appendix G. When the samples are correlated, only the CorrGCV accurately predicts the out-of-sample risk. As result, it is the only correction to the GCV that allows accurate tuming of the ridge parameter À (Figure 2).
drz = Tr E +)
N
di K
Tr
[KK
K + -
T
Similarly, for the training error, we have Rmn df, dfz
x²
1-7 w T "EE +x)+
Sdr,
An important contribution from the theory of high- dimensional regression with uncorrelated samples is a characterization of how plwer-law decays covariance cigenspectra-as occur for variety of real Late-give rise to pawer-law decays in out-of- oamsll risk Rg as a func- tion of sample size T (Caponnetto & De Vito, 2007: Spigler al., 2020; Bordelon al., 2020; Cui et al., 2021; Atanasov et al., 2024). Thus, it is natural to ask whether correlations between samples can alter these scaling laws. We show in Appendix E that the correlation structure of the stationary processes we consider cannot change the decay rates. Con- cretely, assume that Σ has eigenvalues A k- for an exponent known the capacity. Further, the signal has that A (2or+)+) for exponent r known as the source. For correlated data, the scaling is unchanged from prior predictions of optimal rates in (Caponnetto & De Vito, 2007; Spigler et al., 2020; Bordelon et al., 2020; Cui et al., 2021),, namely that Rg ~ T 20min((;1), We illustrate this phenomenon in Figure
+ +
T
Tr + +R)-1
dr,
df2 df
K.K'
1-7 df,
Proof. See Appendix C.4.
We validate these formulae across several experiments (Fig- ure Appendix J). As a special case, setting K Ir recovers previously-obtanned asymptotics for the risk of ridge regression under covariate shift (Patil et al., 2024; Canatar et al., 2021a: Tripuraneni et al., 2021). In general, the training error is proportional to the generalization error only in the setting where Σ = Σ' and K K'. Thus, it is only in this setting that a GCV exists.
3.4. Effect on double descent
It is interesting to consider how correlation structure affects double descent. From Equations (4), (5) one has in the
6

---

Risk and cross validation in ridge regression with correlated samples
Exponential Correlations f| 5000 == {= 1=+02;A==100
Thus, correlations mollify the double descent phenomenon. We do not say that they regularize the effect, because the risk still explodes in the ridgeless + 1 limit.
A11000 1e06 0,
Noise correlations affect the generalization error only if the covariates are also correlated. If the covariates are un- correlated, namely K = IT then K' enters the risk (8) only through + Tr K', which is 1 by definition. Conversely, we can consider the case where the covariates are corre- lated but the noise is uncorrelated, i.e., K' Lr. In the overparameterized regime, in the ridgeless limit this yields an eπror equal to that with uncorrelated data multiplied by 1 Tr(K-1), which is greater than one so long as K + I7 (Appendix F). This implies that having uncorrelated noise is generally worse than having noise with matched correla- tions. We illustrate this behavior in Figure 4(c), where this effect is visible strong magnification of double-descent.
10-
Eror
10-1
10-1
(a) Exponential Correlations
T
Power Law Correlations = 5000 gm1.2. rm 0.3, 0e-000
10-1
16-1
4. A Algorithmic implementation
Ras?
Error
Nakee
In this section, we give an algorithm to compute the Cor- rGCV given knowledge of the function Sx (gdfj). We dis- cuss how to estimate SK from data in Appendix A.2. The diagram for this calculation is given in Figure 5. In what follows, we will use the notation b + to indicate variable assignment of b given that a has been computed. We also use a = b to highlight that the variable a is shorthand for b. This allows one to easily track the causal chain of how the relevant variables are estimated.
10-1
16--
20-1
15a
10 T
12a
(b) Power Law Correlations
Figure 3. Power law scalings for data with a) exponential correla- tions with E 102 and b) power law correlations Rx," a ox -- with = 0.3. In both cases, the correlations of the data do not affect the scaling of the generalization error as a function of T, which generally goes as 222 min(r.1), as derived in prior works. Although other estimators correctly predict the rate of decay, only the CorGCV correctly recovers the exact risk.
First, given Σ alone, we can calculate x as long as the functional form of SK is known. We obtain:
(x(gff))
dfi + (d) IS K x qdqdf
At this point, the ordinary GCV is directly given by S Rin- Given functional form of Sk. this gives x. as a differen- tiable program of A. Derivatives can be efficiently evaluated with autograd, for example using the JAX library (Bradbury et al., 2018). This will be important for the next steps.
structured case that:
K A
gdr, Sk (gdff));
Second, by applying the duality relation (see Appendix CC), we obtain estimates for df, = dd*x(A) and R:
compare with (7) in the uncorrelated setting. In the ridge- less limit in the overparameterized regime q > 1, k will be such that gdf (x) = 1, which is unchanged from the uncorrelated setting (Appendix F). The double descent be- havior in that case is unchanged by correlations. At finite ridge, we see that training on correlated data similar to replacing À= + AS (gdfz) with uncorrelated data. Near the double descent peak, this expands to leading order in q 1 as (1). In Appendix F, we show that Sx 2 pointwise. Thus, correlations will enhance the ridge near the interpolation threshold, meaning that the double-descent peak should be mollified. For strong exponential correla- tions K₁, = e It-al/E, (1k(1) is approximately Xg. This leads to the less sharp double descent peak in Figure 4(b).
df, + gdf,,
kqdfi
Third, we leverage autograd to estimate dfa = dr by applying another duality relationship:
0xdf1
dfa df + 0g log
Fourth, by using this and applying autograd again, we obtain an estimate for df, = dr
ax log
df² + df, q 0g log
(df, dfz).
7

---

Risk and cross validation in ridge regression with correlated samples
Correntes Regrendin ii 100 nemori Data (- 20-02, 10.4, 0000 (uncormbree
Carriitedd Regraaioon vobroki Data
uted tegrosatinn betest: Data Je-00
0.5
33-
Wry
10-
33-1
Nike OOV
10a0
16-
(a)
(b)
(c)
Figure Precise asymptoties for double-descent linear regression with unstructured data across various correlations. We choose an exponential correlation with correlation length & and vary Ç. a) Weakly correlated data and noise, giving rise to the traditional double descent curve as analyzed (Advani et al., 2020; Hastic et al., 2022). All GCV-related estimators agrec and correctly estimate the out-of-sample risk. b) Strongly correlated data with matched noise correlations. The double descent peak is mollified. c) Strongly correlated data but uncorrelated noise. The double descent peak is exacerbuted. This mismatch in correlations violates the assumptions of the CorGGVV and thus GCV asymptotically match it without knowledge of the noise level o, Across all settings the theory curves (solid lines) find excellent agreement with the experiments (solid markers with error bars over 10 different datasets).
GCV
GCV2 = 52 X
(I-qdr,)
df
df
df
K X
Sx(gdf,) I-ddf
df, df
X
gdp
= df,
CorGGV
K di, -x
dii
dr, dr K
drk
R
df, = dr K
Figure 5. graphical representation of the program needed to ohtain the ConGGV empirically from given dataset. The asymmetry of the diagram arises from the fact that we estimate x first rather than A. This is because it is more reasonable to assume a good estimate of the correlations K, which often have properties such as stationarity that improve the estimation process, compared to estimating Σ. As result, it is casier to use either an exact form or a differentiable interpolation of Sx (df) rather than Sz.
Finally, from this obtain the ConGCV estimator:
correction to the asymptotic risk:
df,
Theorem 5.1. Denote by R the the test point has correlation [k), with data point x4- In this case, the test point is conditionally Gaussian with
risk when
Ecorrcev SinSS
df, df2
5. Testing on correlated data
B|x X a, Var x X] = (1 (1-p)) -)
where = K k and p kT K k. Assume that e; has the same correlation
Finally, we consider the setting where the data point æ which we test on has a nontrivial correlation k with each That is, E[x, xx] x k. For simplicity, we assume that the covariates and noise are identically correlated. Such a setting arises naturally in the case of forecasting time series, where one trains model on a window of data and then aims predict at future time within the correlation time of the process. This correlation introduces multiplicative
namely K. Then,
R ~ R-k [1 - p R² K K(K + +R) 2a
Proof. See Appendix C.5.
We note that because è > 0, the spectrum of 2 + +))- is strictly bounded between zero and one. Thus, the last term in brackets is strictly bounded from above by p. meaning that
8

---

Risk and cross validation in ridge regression with correlated samples
Correlated Unstructurdd Regression r= 0e+00 1e-04 0, 0.5
6. Conclusion
102
In this paper, we have provided a comprehensive charac- terization of the asymptotic risk of high-dimensional ridge regression with correlated Gaussian datapoints. We expect our asymptotics to extend to non- non-Gaussian data thanks to the universality of ridge regression (Hu & Lu, 2022; Montanari & Saeed, 2022; Misiakiewiez & Saeed, 2024). Our results show that greviously-propose timator to non-i.id. data are asymptotically biased, and immediately give the formula for the corrected GCV. This correction factor requires one estimate more fine-grained spectral statisties of the cample--ample covariance than the usual GCV. However, as we have shown in the figures and discussed in Appendix A, obtaining an excellent estimate appears relatively straightforward.
101
100
Error
10-1
10
extensions of the GCV es-
DCV Na
12a1
Consty
O-wi ComGcy
10"
(a) Isotropic, Correlated Test
Correlated Unstructured Regression
Oc+ 00 1e 2404,
10
Though our results are quite general, they are not without limitations, and there are several opportunities for further theoretical inquiry. First, our matrix-Gaussian model for the training data (1) could be relaxed to allow for sample- dependent covariance between features. On the technical side, to our knowledge Gaussian universality of ridge re- gression for non-independent data has not been rigorously established, though we expect it to hold (Hu & Lu, 2022: Montanari & Saeed, 2022: Misiakiewicz & Saeed, 2024). One might also want to establish dimension- tic equivalents with relative error bounds, in Misiakiewicz & Saeed (2024). However, these are largely technical, rather than conceptual, limitations.
10-
Comooc
giCorGCV
100
300 10a 10²
determinis-
(b) Isotropic, Correlated Test
Figure 6. Strongly exponentially correlated data as in Figure 1 b), with Ex, e-r/E, { = 10². a) Comparison of the out-of- sample risk for testing points the future from the training data. We emphasize that the CorrGVV here is the ConGCV for testing on uncorrelated test point, which is pessimistic relative to the risk for the correlated point at r 5. b) Plot of the out-of-sample risk as function of the horizon time that we test out. We see that testing on closer times is predictably more optimistic. We see that (1 p) times the CorrGVV provides good approximation of the optimism of lesting on a correlated point. Given a knowledge of the correlation structure of K, this can be efficiently computed for stationary time series data.
After the completion of this work, we became aware of the contemporaneous work Luo et al. (2024), who derived an asymptotically unbiased non-omniscient risk estimator un- der the assumption of right rotation-invariance. Concretely, they assume that the design matrix X satisfies XO d X for any orthogonal matrix O. Their results thus allow for non-Gaussian data, but do not allow for correlations between features, and are therefore complementary to our own.
correlated point that is r = 5 time
We conclude by commenting briefly on applications of our results. First and foremost, we anticipate that our asymp- totically exact correction to the GCV should be of some utility in timeseries regression settings, whether in finance (Bouchaud & Potters, 2003), neuroscience (Williams & Lin- derman, 2021), or elsewhere. Moreover, our results might be of use in the study of in-context learning in language mod- els, where most theoretical investigations neglect for the sake of analytical convenience the rich correlations present in language (Lu et al., 2024).
R& is always less than Rk=0 This precisely quantifies the over-optimism of cross-validation when the held-out samples are nearby in time.
The train error is not affected by the correlated test point. Consequently, this yields an extension of the CorrGCV:
sdi
Author contributions
Roat dr - df2
[1 11-++Ro
a K(K + R) -2x] Rim-
A.A. and J.A.Z.-V. conceived the project, performed re- search, and wrote the manuscript. C.P. supervised the project and edited the manuscript.
In practice, we find that the simple approximation Rl R
(1 - pp) Rk=0 works very well (Figure 6).

---

Risk and cross validation in ridge regression with correlated samples
Acknowledgements
Atanasov, A. B., Zavatone- Veth, J. A., and Pehlevan, C. Scaling and renormalization in high-dimensional regres- sion. arXiv preprint arXiv:2405.00 405.00592 2024.
AA is grateful to Holden Leslie-Bole and Jacob Prince for useful conversations. We also thank Benjamin Ruben for helpful comments on a previous version of this manuscript. JAZV supported by the Office of the Director of the National Institutes of Health under Award Number DP50D037354. The content is solely the responsibility of the authors and does not necessarily represent the official views of the National Institutes of Health. JAZV is further supported by Junior Fellowship from the Harvard Society of Fellows. C.P. is supported by NSF grant DMS-2134157, NSF CAREER Award IIS-2239788 DARPA grant DIAL- FP-038, Sloan Research Fellowship, and The William F. Milton Fund from Harvard University. This work has been made possible in part by a gift from the Chan Zuckerberg Initiative Foundation to establish the Kempner Institute for the Study of Natural and Artificial Intelligence.
Bach, F. High-dimensional analysis of double descent for
linear regression with random projections, SIAM Journal on Mathematics of Data Science, 6(1):26-50, 2024.
Bahri, Y., Dyer, E., Kaplan, J., Lee, J., and Sharma, U. Explaining neural scaling laws. Pro- ceedings of the National Academy of Sciences, 121(27))e231187112, 2024. doi: 10.1073/pnas.
2311878121. URL https: : /wwww www.wppp.........w.......w..w... pnas.org/dol. abs
Basak, A., Bose, A., and Sen, S. Limiting spectral distri- bution of sample autocovariance matrices. Bernoulli, 20
(3):1234 - 1259, 2014. doi: 10.3150/13-BEI522 URL https: / /tt.i wrw.orog///./o 50 1 BEJ520.
Bates, S., Hastie, T., and Tibshirani. R. vooss-valiottion:
Impact statement
What does it estimate and how well does it do it?
Journal of the American Statistical Association, 119 (546): (44)::43441445, 2024. doi: 10. 10.1080001221459.222 2197686. URL https: org/ 1080/
This paper presents work whose goal is 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.
01621459. 2023 .11123.219760 2197686.
Bigot, J., Dabo, I.-M., and Male, C. High-dimensions analysis of ridge regression for non-identically distributed data with variance profile. arXiv, 2024. URL https:
References
Adlam, B. and Pennington, J. Understanding double de- scent requires fine-grained bias- variance decomposition. Advances in neural information processing systems, 33: 11022-11032, 2020.
//arxiv. org/ httg//b//////// 22..22233222222 20200.
Bordelon, B., Canatar, A., and Pehlevan, C. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pp. 1024-1034. PMLR, 2020.
Advani, M. and Ganguli, S. Statistical mechanics of opti- mal convex inference in high dimensions. Phys. Rew. X, 6:03,034, Aug 2016. doi: 10. R0.11.6/PhyseewX.6. 031034. URL https:ttppo.omcc..ttt / 1ink wiiikaaps.c.. aps. opp..org//oi/1 11 1103/PhysRevx. 6. 031.
Bordelon, B., Atanasov, A., and Pehlevan, C. A dy- namical model of neural scaling laws. arXiv preprint WwXhv:2402.01099 2024.
Böttcher, A., Grudsky, S., Maksimenko, E. A., and Un- terberger, J. The first order asymptotics of the ex- treme eigenvectors of certain Hermitian Toeplitz matri- ces. Integral Equations and Operator Theory, 63(2): 165-180, Feb 2009. ISSN 1420-8989, doi: 10.1007/ 500020-008-160 1646-x. URL https: /ttp///oi.... org/10.
Advani, M. S., Saxe, A. M., and Sompolinsky, H. High- dimensional dynamics of generalization eтror in neural networks. Neural Networks, 132:428-4466 2020.
Altman, N. S. Kernel smoothing of data with cor- related errors. Journal of the American Sta- tistical Association, 85(411):749-759, doi: 1011880016224599..999.1177882829
1007/s00020- 008-00080000 6466x
1990.
Bouchaud, J.-P. and Potters, M. Theory of Financial Risk and Derivative Pricing: From Statistical Physics to Risk Management. Cambridge University Press, 2 edition, 1753389
URL
htttp::/www..aanfffot hwwp:/tiiiiiccccaoooooommaaeeo www/ wwtoo///o/aaee doi/dbo//////////// /bss/
10. 1011000000011000 1990. 10479993...44466...
2003. doi:
Atanasov, A., Bordelon, B., Vavatooeee-ee,h J. A., Paquette, C., and Pehlevan, C. Two-point deterministic equiva- lence for stochastic gradient dynamics in linear mod- els. arXiv, 2025. URL https:/ //tr//araa /arxivv.... org/ abs/ 2502. 05074.
Bradbury, J., Frostig, R., Hawkins, P., Johnson, M. J., Leary, C., Maclaurin, D., Necula, G., Paszke, A., VanderPlas, J., W'anderman-Mile S.,, and Zhang, Q. JAX: composable transformations of Python+NumPy programs, 2018. URL http://g http://gitttt thub. com goog/ aoooolle// jax.
10

---

Risk and cross validation in ridge regression with correlated samples
Bun, J., Allez, R., Bouchaud, J.-P., and Potters, M. Ro- tational invariant estimator for general noisy matrices. IEEE Transactions on Information Theory, 62(12):7445- 7490, 2016a. doi: 10.1009/TT.200166666113
Carmack, P. S., Spence, S., and Schucany, W. R. Gener- alised correlated cross-validation. Journal of Nonpara- metric Statistics, 24(2)269-282, 2012. doi: 10.1080/ 10485255.20112.655755. URL https: //tp:///oi...//ooo http//oi.oogggooo org/ 10. 10.108001148880
2012 2. 655733.
Bun, J. Allez, R., Bouchaud, J.-P., and Potters, M. Ro- tational invariant estimator for general noisy matrices. IEEE Transactions on Information Theory, 62(12):7475- 7490, 201
Chizat, L.., Oyallon, E., and Bach, F. On lazy training in differentiable programming. Advances in neural informa- tion processing systems, 32, 2019.
Craven, and Wahba, Smoothing noisy data with spline functions: estimating the correct degree of smoothing by the method of generalized cross-validation. Numerische mathematik, 31(4):377-40) 1978.
Burda, Z. and Jarosz, A. Cleaning large-dimensional co- variance matrices for correlated samples. Phys. Rev. E, 105:034136, Mar 2022. doi: 10. 10.1103/PhysRev...M 105. 034136. URL https:://///// 1inkk. aps wwt//oi/l1 1103/PhysRevE. 105. 034136.
Cui, H., Loureiro, B., Krzakala, F., and Zdeborová, L. Gen- eralization error rates in kernel regression: The crossover from the noiseless to noisy regime. Advances in Neural Information Processing Systems, 34:10131-10144 2021.
Burda, Z., Jurkiewicz, J., and Waclaw, B. Eigenvalue density of empirical covariance matrix for correlated samples. Acta Physica Polonica B, 36(9), 2005a.
URL https:/ http:///www.attthss....u wdu.uupeeupppppp.. fulltextt?seiees [ualleek22serisssfeervoo-----ppp
Defilipiis I.., Loureiro, B., and Misiakiewicz, Dimension-fre deterministic equivalents for random fea- ture regression. arXiv preprint arXiv:2405.15699 2024.
Burda, Z., Jurkiewicz, J., and Wactaw, Spectral mo- ments of correlated wishart matrices. Phys. Rev. E, 71:
Dobriban, E. and Wager, S. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247 279, 2018. doi: 10.1214/ 17-AOS1549, URL https: /tt.:/ooooooooooooooooo/ooo 1214/ 17 AOS1549.
026111, February 2005b. doi: 10.1103/hhysRevE.71.
026111. URL https:://////.. wtt. 11 1103/PhysReval 71 026111.
Burda, Z., Janik, R., and Nowak, M. Multiplication law and S transform for non-Hermitian random matrices. Physi- cal Review E, 84(6):061122 125, 2011.
Gerace, F., Loureiro, B., Krzakala, F., Mézard, M., and Zdeborová, L. Generalisation error in learning with ran- dom features and the hidden manifold model. In Interna- tional Conference Machine Learming, pp. 3452-3462. PMLR, 2020.
Canatar, A., Bordelon, B., and Pehlevan, C. Out- of-distribution generalization in kernel regression. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang. P. and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, vol- ume 34, pp. 12600-12612. Curran Associates, Inc., neurips. 2021a. URL [iaaer__fiees//pper///2////e ce cttppppr_filles/eeeeeeeeeeeeeeee 1911cb..6$1331177777744883388883 pdf.
Golub, G. H., Heath, M., and Wahba, G. Generalized cross- validation method for choosing good ridge parame- ter. Technometrics, 21(2):215-22 1979.
Gu, C. and Ma. P. Optimal smoothing in nonpara- metric mixed-effect models. The Annals of Statis- tics, 33(3):1357 1379, 2005. doi: 10.1214/ 0090536050000000000 1214 0114/009050 009053605000000100
Canatar, A., Bordelon, B., and Pehlevan, C. Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature communications, 12(1 12(1):2914, 2021b.
Hastie, T., Tibshirani, R., Friedman, H., and Friedman, J. The elements of statistical learning: data mining. inference, and prediction, volume Springer, 2009.
Caponnetto, A. and De Vito, E. Optimal rates for the regu- larized least-squares algorithm. Foundations of Computa- tional Mathematics, 7:331-366 2007.
Hastie, T., Montanari, A., Rosset, S., and Tibshirani, R. J. Surprises in high-dimensional ridgeless least squares in- terpolation. The Annals of Statistics, 50(2):949 986, 2022.
Caponnetto, A. and Vito, E. D. Fast rates for regularized sqastesquares algorithm. Technical report, Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory, 2005.
Hu, H. and Lu, Y. M. Universality laws for high- high-dimensional learning with random features. IEEE Transactions on Information Theory, 69(3):1932-19644 2022.

---

Risk and cross validation in ridge regression with correlated samples
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent ker- nel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
hBRphhtpss:/prrcceedings ml presss/ v v139/met ht/mmml21ll... att.1laahtttnn htmml.
2021. URL wtttttsp::////
Mel, G. and Pennington, Anisotropic random feature re- gression in high dimensions. In International Conference on Learning Representations, 2021.
Jacot, A., Simsek, B., Spadaro, F., Hongler, C.,, and Gabriel, F. Kernel alignment risk estimator: Risk prediction from training data. Advances in neural information processing systems, 33:15568-15578 2020.
Mingo, J. A. and Speicher, R. Free probability and random matrices, volume 35. Springer, 2017.
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. Scaling laws for neural language models. arXiv preprint 20iv:2001.08366 2020.
Misiakiewicz, T. and Saeed, B. A non-asymptotic the- ory of kernel ridge regression: deterministic equiva- lents, test error, and GCV estimator. arXiv preprint arXiv:2403.0880 089388 2024.
Kühn, R. and Sollich, P. Spectra of empirical auto- covariance matrices. Europhysics Letters, 99(2)200008 2012.
Montanari, A. and Saeed, B. N. Universality of empir- ical risk minimization. In Loh, P.-L. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 4310-4312. PMLR, 02-05 Jul 2022. URL http:: http:s:://oocccdeeeeeeeee / v178 htt////onnnniiiiii html.
Lin, L. and Dobriban, E.
What causes the test error? going beyond bias-variance via anova. Journal of Machine Learning Research, 22(155):1-82, 2021. URL http: html.
mll press/
//jmlr.orge http:/paapss////////p
Loureiro, B., Gerbelot, C., Cui, H., Goldt, S., Krzakala, F., Mezard, M., and Zdeborová, L. Learning curves of generic features maps for realistic datasets with a teacher- student model. Advances in Neural Information Process- ing Systems, 34:18137-18151 2021.
Mudelsce, M. Climate time series analysis: Classical statis- tical and bootstrap methods. Ammosphriic and Oceano- graphic Sciences Library, 51:1 2014.
Nica, A. and Speicher, R. Lectures on the combinatorics of free probability, volume 13. Cambridge University Press, 2006.
Lu, Y. M., Letey, M. I., Zavatone- J. A., Maiti, A., and Pehlevan, C. Asymptotic theory of in-context learning by linear attention. arXiv, 2024. URL https::////// /taps:://axiv.. org/ abs 2405/ 11751.
Noschese, S., Pasquini, L., and Reichel, L. Tridiago- nal Toeplitz matrices: properties and novel applica- tions. Numerical Linear Algebra with Applications, 20(2):302-326 2013. doi: https://doi.org/10.100 nla. 1811. URL htRps:::: wonoonnnnenarrrrrr wiley. com/
Lukas, M. A. Robust GCV choice of the regulariza- tion parameter for correlated data. Journal of Inte- gral Equations and Applications, 22(3):519- 547, 2010. doi: 10. (0.12166/1E-221--22---1111 URL httpt:///d//o org/10 11..:..211//1E-1110 21tp://00EE001------0020--2----- -2---11.
1002 ml..00////...11....
Opsomer, J., Wang, Y., and Yang. Nonparametric Re- gression with Correlated Errors. Statistical Science, 16 (2):134 153, 2001. doi: 10. 10.12144ss/1009211299, URL https: http:///ooo.oogo...11///////////
Luo, K., Li, Y., and Sur, P. Roti-gev: Generalized cross-validation for right-rotationally invariant data. arXiv, 2024. URL https://arxxt wow.//rg//a.o /abs/ 11666.
Patil, P. and Leleune, D. Asymptotically free sketched ridge ensembles: Risks, cross-validation. and tuning. In The Twelfth International Conference on Learning Represen- tations, 2024. URL https: //tpr/////e/eeeeeeeeeemee .nt// forum? 1 11d 5VG5ND
Maloney, A., Roberts, A., and Sully, A solvable model of neural scaling laws. arXiv preprint arXiv:2210. 168599 2022.
Mel. G. and Ganguli, S. A theory of high dimen- sional regression with arbitrary correlations between input features and target functions: sample complex- ity, multiple descent curves and a hierarchy of phase transitions. In Meila, M. and Zhang, T. (eds.), Pro- ceedings of the 38th International Conference on Ma- chine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 7578-7587, PMLR, 18-24 Jul
Patil, P., Du, J.-H., and Tibshirani, J. Optimal ridge regu- larization for out-of-distribution prediction. arXiv, 2024. URL https: /arxiv.. org/ ht///bba//0000 01233.
Potters, M. and Bouchaud, J.-P. A first course in random ma- trix theory: for physicists, engineers and data scientists. Cambridge University Press, 2020.
12

---

Risk and cross validation in ridge regression with correlated samples
Rabinowicz, A. and Rosset, S. Cross-validation for corre- lated data. Journal of the American Statistical Associa- tion, 117(538)718-7311 2022.
regression and its asymptotic optimality. Journal of Com- putational and Graphical Statistics,, 28(4):891 2019. doi: 10.1080/1061 000000000006000000111111.1.00000 14. URL https: / doi. org/ /ttp://///..11000001111100110000
2019. 1586714.
Spigler, S., Geiger, M., and Wyart, M. Asymptotic learning curves of kernel methods: empirical data versus teacher- student paradigm. Journal Statistical Mechanics: The- ory and Experiment, 2020(12):124001) 2020.
Zavatone-Vethh J. A. and Pehlevan, C. Learning curves for deep structured Gaussian feature models. In Advances in Neural Information Processing Systems, 2023.
Hooft, planar diagram theory for strong interactions. Nucl. Phys. B, 72(CERN-TH SELEER--TH-178888 (1---186):4611444 473, 1973.
Tripuraneni, N., Adlam, B., and Pennington, J. Covari- ate shift in high-dimensional random feature regression. arXiv preprint arXiv:21 11.22111..022 1.08244, 2021.
Voiculescu, D. V. Free probability theory, volume 12, Amer- ican Mathematical Soc.. 1997.
Voiculescu, D. V., Dykema, J., and Nica, Free random variables. American Mathematical Society, 1992.
Wang, Y. Smoothing spline models with corre- lated random errors. Journal of the American Statistical Association, 93(441):341-34, 1998.
doi: 10.1080001624559.19999 1998..444119...1
URL
http:/://wwwwwwwt.fotttee. com/ toi//bs//
10. 1tt.:/00...21411199...1441111111
Weingarten, D. Asymptotic behavior of group integrals in the limit of infinite rank. Journal of Mathematical Physics, 1900, 1978.
Williams, A. H. and Linderman, W. Statistical neu- roscience in the single trial limit. Current Opinion in Neurobiology. 70:193-205, 2021. ISSN 0959- 4388. doi: http:://ho...gg///..oo...o.m.... URL http:://www.scclennedeeeec com/
/iiince/arrcclee//////5552222221 Computational Neuroscience.
Xu, G. and Huang. J. Z. Asymptotic optimality and efficient
computation of the leave-subject-out cross validation. The Annals of Statistics, 40(6):3003 3030, 2012. doi: 10.1214/2-A0S10663 URL https: : /oii/oiooo//////oo//// http//ii..ooo..////////o 1214/12-
Xu, G., Shang, Z.. and Cheng, G. Optimal tuning for divide-and-conquu kernel ridge regression with mas- sive data. In Dy, J. and Krause, A. (eds.), Proceed- ings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learn- ing Research, pp. 5483-5491, PMLR, 10-15 Jul 2018. URL hetphttttt... http:tt//ppoccedggggeet/ http///oceedngg....o mlr press/v80/ cul8f.Ie html.
Xu, G., Shang, Z., and and, G. C. Distributed general- ized cross-validation for divide-and-conquer kernel ridge
13

---

Risk and cross validation in ridge regression with correlated samples
R In-sample risk, AKA training Error
lamb: Value the ridge
# Ratio N/T
eigs_Sh: Eigenvalues of empirical covariance Sigma hat (Sh)
S.K: Function of df given by the S-transform S_K
from jax import grad
import jax. numpy as inp
fn_hhh lambda 1: mew. (1teigs_Sh))
10 d_dfi_fn_sh grad
11
12 dfl Sh_est dfl_fmm fn ________________________________ (1amb)
dfl Kh
q _e1__h__stt
15 R_GVV R (1-q=df1_sst)
16
17 est = 1/ [f1--tdfllestt + s_K(qrdfl_est)
18 GCV2 R_in 8_est++2
19
20 kappal_ff
1ambda 1: 1/ 1f(1=qxofl_fn_hhh)
s_K(q-dfi__f__hhh) (1))
(1))
21 kappa2 in = Lambda 1: 1/ (q dfl in Sh(l) k1 kl]
22 log kappal in = grad (lamoda 1: jap. (kappal fn)1))
log kappa2 in grad 1: jnp. (kappa2 (1]))
24
df2_fn Sh lambda 1: df1_fr_sh (1) kappa_aapa
fd (1)
25
26
dfs_Kh_est qedfl_est
(df1 fafi_fn_sh (lamb) af2_fn_8h (lamb)) k_log_ki_fn (lamb)
d __log_k2_00 k2 fn (1amb)
28
R_CorrGCv Rn * ees df1 Kh est/ (dEl Kh Kh_ est dff2Kh_estt
Code Block 1: Python code for computing ConrGCV estimator given relevant parameters.
A. Algorithmic implementation of the CorrGCV
A.1. Code for implementation
In Code Block we give the code for implementing the ConGGVV estimator in JAX given ridge X, training error Rin. overaparameterization ratio g, empirical covariance matrix Σ, and function Sx(df) given by the S-transform of the correlation structure.
A.2. Estimating the S-transform from data
If the functional form of the correlations is not exactly known, there are several options.
1. From empirical data, one can fit K to a parametric form for which the S-transform Sx can be calculated exactly. We give some examples of this in Appendix I; practically-relevan example is exponential e -it-t'l// (Potters Bouchaud, 2020).
2. For a time series with the assumption of stationarity, one can estimate the autocorrelation A, K,,++ as a function of lag much more reliably than the full matrix Ke,e, as it depends on only O(T)) parameters rather than O
3. From K, one calculate df &e (A) function of X. By making of solver (such as bisection method), can evaluate df K (df) and then get
1 df
Sx(df) df = (x( = (g di) -1-11))) di)
Sk (d)) df df K
(9)
(dF)
df df
k (df)
We can then evaluate K2 follows:
First, sample fine grid of X.
From the data, we estimate df, =df (1) for each lambda, leading to fine grid of df, and df, = gdf,
14

---

Risk and cross validation in ridge regression with correlated samples
Given the bisection-based algorithm evaluate d We then evaluate Sx(df) using (9). This leads an K'
exact formula for SK the corresponding fine grid of df; gdf1-
Using the definition
(odf,) we obtain fine grid of differentiate through and guarantee that the grid Ax -
function of X.
We now apply appropriate interpolation method that gets finer, both the function and its derivatives converge to the true and 0
The last bullet point requires further discussion. In practice, because k can vary over several orders of magnitude, and because estimating the CorrGCV requires logarithmic derivatives, it is often best to interpolate log ii against log X. A good interpolator compatible with autograd can be a Gaussian process with appropriately chosen covariance, piece-wise smooth spline function, polynomial interpolator, or wavelet based method that converges in the appropriate Sobolev norm. We used simple degree 5 polynomial interpolation of Sx to generate the power law correlation learning curves in Figure 2(b).
B. Review of free probability
B.1. Definition of Freedom
We now define what means for set of random matrices {A:]_= to be jointly (asymptotically) free. All of these matrices are N x N and consider the limit of N co. This is the limit in which free probability theory applies for random matrices. There are several texts on this rich subject. See, for example (Mingo & Speicher, 2017; Voiculescu, 1997; Nica & Speicher, 2006).
We say that a polynomial p(A,) has the mean zero property if
Tr(p(A,)) ~ O. N
Above, 0 means that this converges to zero in probability as N + xc.
Take set of m polynomials {px [ each with the mean zero property. Further, take a labeling {in)e- with each d E .1....,m} so that is + is+1 for all k. The {Ar)"= are jointly asymptotically free and only if
1 Tr (pI .. Pm = N for any m, any labeling {is). and any set of polynomials {px) satisfying the properties above.
For our purposes we only require that the $ =z Z and 1 = matrices are free of any fixed deterministic matrix, specifically Σ and K.
B.2. The R and S transforms
We review here basic properties of the R and S transforms of free probability (Voiculescu et al., 1992; Voiculescu, 1997). The recent book by Potters and Bouchaud (Potters & Bouchaud, 2020) provides an accessible introduction to these techniques in the context of random matrix theory.
Given a N x symmetric random matrix A, one considers the resolvent, also known as the Stiltjes Transform: 1
(A =
N (A
The eigenvalue density of A, PA can be obtained from the inverse Stiltjes transform:
1
PA (A) = lim c-0
Im gAngg(A>aia
Similarly, one defines the degrees of freedom dr3 (A)
1 Tr[A(4 + 1)-'} dA)
1
dA)(
Tr TA
N
N
One has the relationship:
(A(A) 1 1- 1 d
We let 9 1 1 denote the respective functional inverses. The and S transforms are respectively functions of formal
15

---

Risk and cross validation in ridge regression with correlated samples
variables g, df given by:
Ra(2)= 9 1 Sa(df) = df df (df)
1 df
(10)
They have the property that for any two matrices A, B that are free of one another:
RA+B(9) Ra(9) + RB(g). (df S (d(d))SB((ff)
From these two respective properties, together with the definitions (10) we obtain the subordination relations, also known as (weak) deterministic equivalence:
9A+B (A) = _a(A + RB), df df dAA(A
(11)
Here, the additive and multiplicative renormalizations of A, given by Rg and SB respectively, can each be evaluated in two different ways. The first way from the original noisy matrices A B and A s B. This is the analogue the empirical estimate of S, discussed in the text.
RB = RB(gA+B(A)), =B SB(ff D. (A)).
The second way from the clean matrix A itself. This what gives the omniscient estimate of the renormalized ridges. Writing K4,, K, for À + RB, AS respectively, we obtain the self-consistent equations:
K_ x+ (B
AS (K.))
B.3. Strong deterministic equivalence
The deterministic equivalences in (11) extend to the matrices themselves. Taking A deterministic and B random and free of
A, we have:
(A+ A
A B(A A(A+R.)
Here, for two matrices, we use the relation = to denote that the traces of these quantities against any test matrix of bounded spectral norm will converge in probability to the same quantity as N -> oc.
The above two formulas can be derived using replica theory (Bun et al., 2016b; Potters & Bouchaud, 2020), from diagrammatics (Burda et al., 2011; Atanasov et al., 2024), or from cavity arguments (Bach, 2024).
In this paper, only require the properties of the S-transform. The above deterministic equivalences called "one point" equivalences, as they only involve single matrix inverse. We will derive two-point equivalents in the sequel.
C. Deferred proofs of main results
C.1. Warm-up: 1-point deterministic equivalents
In this section, we prove Lemma 2.2 using a diagrammatic argument based on Atanasov et al. (2024), specialized to the specific case of Wishart noise matrices B. The argument diagrammatic, appealing the fact that large N, free random matrices obey non-crossing properties in their diagrammatics ('t Hooft, 1973). The argument holds rigorously only in the N + oo limit. However, it can rigorously be shown to be the leading term in asymptotic series in 1/N by leveraging known properties of the higher-order corrections (Weingarten, 1978).
In what follows, for the sake of notational levity we absorb a factor of 1/VT into each insertion of Z or ZT Because each pair of Z, Z insertions will necessarily be averaged over via Wick contraction, this is the same as associating an factor of T/ with each Wick contraction.
16

---

Risk and cross validation in ridge regression with correlated samples
Eg E3Σ(E + = (-2)-1
1 Z K
y1/2
+ (-X)-
1/2 T
K
Z
E
7 T
K
Z
1/2
+ (-x)-2
V K
Z Σ
7
K
1/2
Such a suppression of crossing diagrams is a defining characteristic of free probability. Because each loop contributes a trace, while each insertion of Z Z contributes factor of /T,, in order for diagram to give an order contribution we will need have as many loops there are pairs of Z Z. Consequently, crossing diagrams such as the following suppressed as N, T +
11 Z
K Z
3
2
K Z 11/2
Because crossing diagrams do not contribute, one can observe the following pattern. Any diagram that appears will be link of averages from one Z' to some later Z that creates an arc. Beneath that arc, all averages can only be between the matrices within the arc, by non-crossing. As such, we can expand:
1/S
EΣSΣ + + --X)-
1//2
1/2
1/S
1/S
(-X)-
1//
Σ
Σ 1/2 1/2
The terms in the dashed lines are pre-emptively denoted by 1/S. We make observations.
Because the isotropic matrix Z is right-invariant to rotations in N 1/S must be deterministic matrix that is invariant under rotation. The only such matrices constants times the identity.
Because the isotropic matrix Z also left-invariant rotations in RT, 1/S is rotationally invariant scalar functional of the product of matrices beneath the arc. The only such rotationally invariant scalar functional is any constant multiple of the trace.
The fact that the shaded parts are scalars immediately implies we can resum this as:
Ez +
Σ E
E(E + AS
(-XS)²
n=l
17

---

Risk and cross validation in ridge regression with correlated samples
An immediate consequence is:
1 11-EZE(E+ATT Ez (z -
- - - +
(12)
now remains to evaluate S. We have
Z +
+
$
K
K Z Σ 2
K
Z
We immediately recognize this the trace of AK K
A)- Because Z has entries going 1/ T/V this implies:
Ez Tr K(K 1)-1
(13)
Here, because the trace is self-averaging, we could drop the Ez and still keep this as an equality in probability as T, + co.
By slight adjustment of the above diagrammatic argument, swapping the role of and K, we have an analogue of (12):
(z(K A) 5(K + AS)
S =E
1
Ez X
(14)
We now define
AS, x == AS,
dJ,
= =
n + dr, - |KK + R)-
Note that at this stage we have shown the equivalence:
df, (AS) df (A) gdf (A) qd qdf
Putting (14) back into (13) yields:
X
dr,
KR
We recognize the duality relation. We can also get explicit expression for S in terms of Sn and df by defining the formal function of df
dr
Sd( = dr dr (df)
(dr)
and plugging in A K, df ddfx(() dd, into this:
Rdf df,
(df,)
Using dr, qdf, this yields the desired relationship:
Sx (gdf) qdf
Thus, given knowledge of X, df, and Sk, one can calculate x exactly. For discussion of how obtain Sx from given correlated dataset, see A.2.
C.2. 2-point deterministic equivalents
In this section, we extend this diagrammatic technique to calculate the necessary 2-point deterministic equivalents stated in Lemmas 2.3 and 2.4. Some of these were derived using leave-one-out (cavity) arguments in recent papers of Bach (Bach, 2024) and (Patil & Leleune, 2024) in the case of K I. The remaining results that we derive are to our knowledge novel. As we discuss in Atanasov et al. (2025), they have useful applications to high-dimensional regression problems beyond just those studied in the context of this paper.
As in the prior section, we absorb a factor of 1/VT into each or insertion, or equivalently associate a factor of 1/T with each Wick contraction.
18

---

Risk and cross validation in ridge regression with correlated samples
We first prove Lemma 2.3, which concerns the evaluation of
- +) A)-
for arbitrary matrix E' between the resolvents. In performing this average, we note that the types diagrams that appear split into two classes. The first those with no ares over Σ':
1/2 Z
K
Z
1 E' 1 Z
K Z /
Because no ares connect the resolvent on the left with the resolvent on the right, we can take the averages of the left and right resolvent separately, and obtain:
-) - -
The second class of term has ares connecting the two resolvents on both sides. An example of such diagram is:
1/2 K Z 11/2 E' 11/2 Z K Z 1
Any term in the second class will have some number of ares over E'. Note that this will necessarily be number 2n, as they will alternate between averaging Z on the left with Z on the right and vice versa. This will give 2n loops that are traced over. There will be loops involving K matrices, which we will call K loops, and n loops involving Σ matrices which we will call Σ loops. The above term has n 1. An example of a Σ loop is:
Z T Σ +...
Z
Σ +...
Here, on each side we denote by Σ the series:
Σ+ (- 2Σ + (-x)- ZΣZ =
xM -)
We recognize this resolvent. Because have explicitly accounted for ares connecting terms in the left resolvent with the terms the right resolvent, within each loop we can treat the left and right resolvent average separately. This average is given in (12), and similarly for K. This yields
Eoooo = X2 T
1/
S + 1)
Σ
E + 2)-1 1//2 = qd2
K-loop 2 T 1/2
EZ
(K + 2) 1
KEz (K + 1//2 2
The innermost loop will have insertion of Σ' in between the two resolvents, each of which is separately averaged, yielding:
52
'1 S² (EE
T
19

---

Risk and cross validation in ridge regression with correlated samples
We adopt the shorthand
1 Tr EE E k) -] N
df E
dr K,K' T Tr [K K + x)
to denote this term by E This must necessarily be followed by K loop. By making use of the duality relationship, we can write this joint contribution as:
dl d.
x gd M. dfz
YE."'
d df,
Between this innermost E' and K loop and the outside, there can be an arbitrary number of pairs of closed K and loops in between. Again applying the duality relation, we see each pair contributes:
1 X2 qk df x dr
df2df2 df =
Here we divide by X because each zz pair introduces a factor of (-X)-1, This gives an interpretation of y as the
contribution of a pair of E and K loops. It remains to sum over to get the final contribution from all of the loops:
E.
EE
n=0
Finally, outside of the loops, can perform the average of the left resolvent and the right resolvent separately. This gives the desired relation:
(x)+==++++++++0 5 + +k) 2 'E,'' E S (
(15)
1-
When = I, this recovers the earlier result (Bach, 2024). By applying the same argument with minimal modifications, one obtains the deterministic equivalence for kernel resolvents, namely:
(K +
x) 5 K + +R - 5 - -)- KK
(16)
1-7
df3.df2 K'K'
Here YKK
dfidf,
We next prove Lemma 2.4, which gives equivalent for
K' + A) A) K1/2 22 K' k1/2211/2 (=2"
+
This time, because there odd number of Zs on both the left and the right side of K' in all diagrams, the disconnected terms which average each side separately will vanish. We are left with just the connected term
Again, we sum over the K and E loops. The first term (which involves no Σ loops) is:
11/2 Z
K2 Z 1/2
The innermost loop will be K loop involving an insertion of K' in the middle. As in the caleualtion of the Σ' loop the prior case, this contributes
52 1 Tr K + R) -) 52 K
T
Between this innermost loop and the outer resolvents, there must be an even number 2n of alternating Σ, K loops. The contributions of such loops are unchanged. Each pair gives factor of y. We thus get:
di2 K.
(17)
Contracting this with an arbitrary matrix Σ' and multiplying by 4 gives the more symmetric form:
X²
df
Th
(18)
T
dr
1 1-
20

---

Risk and cross validation in ridge regression with correlated samples
We can further simplify this by adopting the shorthand K',''KKK' d di
K.K.
df
This result can alternatively be derived using a straightforward but tedious and significantly less conceptually illuminating argument based on a one-point deterministic equivalent for a 'sourced' resolvent. Concretely, this argument starts by writing
0 (É + A) = a. | z (K + (2K ZE + x|
Σ +
J=0
and then proceeds by using one-point deterministic equivalent before implicitly differentiating the resulting S-transforms. Then, various applications of the duality relation allow the result to be simplified into the form obtained using diagrammatics above.
C.3. Duality relations and derivatives
Here, we explicitly state all duality relationships that one can derive. In the section on 1-point deterministic equivalents, we have proven that:
gdf, = (d) = gdr's (A) = df k (A) = df (R) = df,
(19)
We have also seen the first duality relation, namely that:
1
ASS
(20)
gdf dr,
Logarithmic differentiation of this yields second duality relation:
doog K. + dlog X = + df (A) d dlog X
dlog R.
df,
Here we have used that
ddr, df 3 - (A) d\
(21)
A
We stress that unlike with 1f,, df # df
df2. Since the right hand side can be estimated from the data, this gives
us a way to turn an estimate
dlogg dllg
into an estimate for dlog or vice-versa. d'log X
Next, we relate df, dfz. We will be explicit and write all dfs with subscripts to avoid confusion. We have, by differentiating (19):
K dd (A)
x dd Ad
Ad (A) = K dr
df = d Evaluating the left and right sides using (21) we get:
de
kD df
K (R)
K
K dR
dlog ñi dlog n
((dfs(n)) (1))
(dr kc (R) df (N))
This yields:
df, = dfx (R) gdf (k)) + dlog R
ddlog (df (K) dff
(22)
Similarly one can write an estimate of df from just the data alone:
d log > d log k
log x dx > (A).
df = (f (A) +
(A)
(dF (A) df di's (A) + d log k
Plugging this back into (22) gives an istimate of df, from the data alone. This is crucial in allowing the ConGGCV to be efficiently computed.
We now calculate the derivative of K, R on A. We have
SA dlog A dlog k
d log 1/S dlog
dlog 1/S d log df, dlog dr, d dlog k d dog 1/S df, dfa dlog df, df,
Using dr, qdf, write
S
SK Sk(dij (dii)
1 df, k (df1)
1 - df,
21

---

Risk and cross validation in ridge regression with correlated samples
Differentiating this gives:
d doog 1/5
df Rdf (R)
dri
dí2
1 +
d log dff
dfi
df2
df
df2
All together this is:
d dlog A
df2
dfi df2
1+ dr df,
d dlog
dfi
df df2dí2
di dr df, df
dr 1
df,
This finally yields:
df2
Ok
1
S
df1
(23)
01
1-7
1
An analogous argument yields:
OK
1
deg
di
(24)
1
Note also that when K = I, dí2 = (df,)²= = dff, yielding
7 = df2dfz
gdf2.
df,
This recovers the uncorrelated ridge regression setting.
C.4. Correlated samples and noise, uncorrelated test point
By applying the deterministic equivalences proved in the prior section, we can directly obtain exact formula for the asymptotic form of the training and generalization error for a linear model trained on a correlated dataset and evaluated on an uncorrelated test point. In fact, we can do better. The deterministic equivalence (15) allows us to easily consider the case where the test point has a different covariance E' from the covariance Σ of the training set. This allows us to state the formula for generalization under covariate shift as well. In one fell swoop. we thus prove Theorems 3.1, 3.2, and 3.3 by directly proving Theorem 3.3, from which the other two results follow as special cases.
We recall that
X T
い = ビン (E +) (
Eelee =elee"]=o22 o²K'.
We have that the generalization error (for a test point whose distribution has covariance E') is: w
Rg
Σ' (t0
w
1 2 ( A) I 1 w +o² THE +) IE
X K X X A)
T
Signal
Noise
The Signal term is immediately obtained by applying the deterministic equivalence in (15).
Signal x=2 E + 2 Ew k2w "E
A)
Ew EE.
1-7
Bins2
Varx
Here we have explicitly delineated which parts of the signal term are due to the bias of the estimator, and which terms are Varx- The latter can be removed by bagging the estimator over different datasets. Note that in diagrammatic language the bias term corresponds exactly the to the disconnected averages the left and right resolvents separately, which makes sense, as it the generalization obtained by first averaging the predictor over different training sets before calculating the test risk.
Similarly, by applying the deterministic equivalence (18), obtain:
Noise o² '', K.
1 1-7
Varxe X
22

---

Risk and cross validation in ridge regression with correlated samples
This yields
Rg = 10 + - x))
w
E' in
K.
(25)
Bias?
Varx
Varx+
Specializing to the case of = E', K K' yields the in-distribution matched-nooss--corelatin setting.
We next treat the training error. We have
Rin 71y y -11 T
Xw
X
7 xx{ + A) w0 2 X(E+ + A) x
T
X2
x Σ + 1 2 +
K' ('
Signal
Noise
One can evaluate the signal term by recognizing it as a derivative and applying the chain rule:
Signal = -2 d
w "I +
+A)
dl
xa dic
w Σ(Σ + 2
X2S dli
dl2
1
w
TEE - 2mn.
df1
1-7
In the last line, have inserted the form of de from (23).
ax
The noise term for generic K' is slightly more involved. We can write it as:
Noise;n 0. X2
TA
Tr
K' ('K + +
X2
0²¹ 0x
Tr [K'K + R) -
T
[K'( + - - -² X dā
T. Tr
Tr
K
K'K
+ -
T dd
Now applying the derivative relationship (24) we get:
df,
df,
1
Noise,, = o T
Tr [K RR)
df
df K'
dfi
1-7
In the case K K' this simplifies to:
df
dfa
df
df2 1
Noise;n oRdd 1
dfg
(26)
d df,
df
S
df 1 1-7
C.5. Correlated test point
Here, we prove Theorem 5.1. Specifically, our setting is one where we allow the test point æ to have non-vanishing correlation with the training set. Similarly, assume that the label noise the test point, has nontrivial correlation with the label noise the test set. We assume general matrix- Gaussian model for the covariates:
a
.
0. K
Σ
x
K
where the vector IR gives the correlation between the training points and the test point, i.e.,
Elargragl Eigke.
Similarly for e, we write:
(:) ()~x(0.0 (0.0² (1.
k. K
))
We further assume that these are independent of the x covariates. That is, E[ = E[I,es] = 0.
23

---

Risk and cross validation in ridge regression with correlated samples
By the usual formulas for Gaussian conditioning, this generative model implies that
x x ~ N(X a, (1 - p}Σ) (1-p)E)
and
< c N(a (1 - ()-))
where we write
= k K k, a= K- k.
Then, the out-of-sample risk is
Rout = E, T (t0 w) +elp.
We have the well-known closed-form expression for w::
② X(Σ 1) x(E
_
-xx e.
1
T
Given that E [ = O, we have:
12
Rout
A2E T (E (1+ w
+
c
x
T (1+
x
T
Signal
Noise
Here, we have again identified the two terms that appear as signal and noise terms. Taking an expectation over æ X, we have for the signal term
Signal (1 (1--)) p1= ( + A)-
+ ( + -)= aa X( + 1)
Leveraging the deterministic equivalences (15), (17), obtain
22 w E + x)) [1 ---p-ia K(K + 2a)
Signal 1
(27)
Similarly, taking an expectation first over e é and then over a: X, we have
Noise = (1 - p)o? E α T T (É+ 1
= (1- - p)
Ee T X + (1)+)))-I(E+ x) xc -
T
+ a T - a T K(K + + 12
Noting that
4 4-K + 11 A(K + 11-
this simplifies to
1 T
-X o? + + A)- to]²
Noise (1 p1
RE
Finally, taking the remaining expectation over E, we have
Noise = -2
E T2
Tr
+ + (K [K+
KKK +
K
Now again leveraging deterministic equivalence (17) as well as (16) we obtain:
0²
Noise = =0 - p)
Ra K(K + -)-
(28)
0² [1 p+ Ra T K(K + -2))
?
All together Equations (27) and (28) together give the desired result:
Rbe
Rk=0 [1 p + a K(K + R) 2a]
One could straightforwardly extend this to the where the label noise correlations different from those of the
24

---

Risk and cross validation in ridge regression with correlated samples
covariates with relative ease. As doing adds complexity the formulas without much conceptual gain, will not do so here.
D. Bias- decompositions
Often in prior work, has been convention to call the proportional to the signal to the Bias and the term proportional to the noise of the variance component of the total risk. Strictly speaking from the perspective of fine- seee-graindd analysis of variance, this is not true. This was pointed out detail by (Adlam & Pennington, 2020; Lin & Dobriban, 2021), where fine-grained bias variance decompositions performed for random feature models.
The estimator to is given by:
र = ( X T
We that the estimator is sensitive both the draw of and the choice of X. Even in the case of noise, of 0. the estimator would still have variance over different draws of X. This variance can be removed if one had access to multiple datasets by bagging over the data. In the limit of infinite bagging, this amounts to a data average. This yields, by deterministic equivalence:
Ex = B
+
Consequently the risk of this estimator would be just the bias:
Bias R(Exx =² T E(Σ + x
Similarly, if one fixed the dataset X but averaged over different draws of the noise e, the risk of this averaged predictor would be the same as the risk of a predictor trained on a noiseless dataset o² Note that this predictor still has variance over the draw of X. We thus get that:
Varx = R(E,.t) uh) Bias = R² ETE + x)
30 Y
The remaining term is Varx,e, since removable either by bagging over datasets or by averaging over noise e. given by:
Y02 1-7
Varx e R(wb) -Bis Varx
We stress this is true under both correlated and uncorrelated data, given that vi, y appropriately define. This decomposition was computed for linear models in (Canatar et al., 2021b; Atanasov al., 2024). These equations also hold for out of distribution risk, as given in (25).
E. Scaling analysis
E.1. Review of optimal rates
The analysis of the scaling properties of linear regression under power-law decay in the covariance Σ and target to along the principal components of was studied in detail in (Caponnetto & Vito, 2005; Caponnetto De Vito, 2007). has received renewed attention given that it can sharply characterize the scaling properties of kernel methods, especially the neural tangent kernel (Jacot al., 2018) variety of realistic datasets (Spigler al., 2020; Bordelon al., 2020; Cui et al., 2021). This has implications for neural scaling laws (Kaplan et al., 2020; Bahri et al., 2024) in the lazy regime of neural network training identified in (Chizat et al., 2019).
One defines the source and capacity exponents ar, r respectively by looking at the decay of the eigenvalues A of Σ and components Vyg of t along those cigendirections. Then, for many real datasets one observes the power laws:
d k We k
is advantageous to write 3 2ar + 1, as the exponent r appears naturally in the final rates. Then, in the ridgeless limit one has qdf; = From this one can easily obtain that
T~
At finite ridge, more generally one has
max(A, (A, T-a).
(29)
25

---

Risk and cross validation in ridge regression with correlated samples
Minimum eigenvalue of power law Toeplitz
10
X
4 10
x
n
x
2048
10
Amin
10-3
10
10
10
10-3
10-2
10
100
10º
102
X
Figure 7. Verification of the minimum eigenvalue for a Toeplitz matrix with power law decay Kts = (1+ =|)= We see a great match between (31) (solid black line) and empirics shapes) matrix sizes ranging between this guarantees that the matrix will never be singular even at very small positive corresponding to strong power law correlations. It is interesting note that the minimum eigenvalue 2 2 Toeplitz matrix this form, which simply Amin 2 x, is relatively close to the minimum eigenvalue of the infinite operator: their ratio decreases from
1024 1024. particular,
log(2) 1.534... at 4 towards I [2g(2/7]
For this reason, & is often called the resolution or the signal capture threshold. It determines which eigencomponents are learned and which are not. Further, taking a, O, one gets the scaling:
Rout Rg K 2min(r;1))
one takes the ridge to scale with the data as T as in (Cui et al., 2021), the full equation in the noiseless setting becomes
Rout T 2min(a, 1))
These are the rates predicted in (Capomnetto & De Vito, 2007).
one passes data through linear random features hefore performing, one can change the resolution scaling by adding a further bottleneck:
max N-
(30)
This plays important role in current models of neural scaling laws (Bahri al., 2024: Maloney et al., 2022; Bordelon et al., 2024; Atanasov et al., 2024; Defilippis et al., 2024). It is therefore interesting ask whether the presence of strong correlations could also affect the scaling laws by adding a further bottleneck to (30). We answer this in the negative.
E.2. Strong correlations do not affect scaling exponents
Here, we ask whether strongly correlated data could change the scaling in (29). First, we note that for correlated data, as long as each new sample is linearly independent of the prior ones in RR, we have that K does not have any zero eigenvalues. In general, the invertible as long as each new datapoint not a linear combination of the prior ones. could however be that the smallest eigenvalue goes to zero as T + oo. This would lead Sk to blow up and could lead worse scaling law. We show that this will not happen for exponential, nearest neighbor, and power law correlations. In the latter case, require some assumptions the power law exponent.
correlation matrix K will have Toeplitz structure when the correlations are stationary and will be
Proposition E.1. Under exponential, nearest neighbor, and power law correlations, the T correlation matrix K remains nonsingular as oc.
Proof. We can study the invertibility of the limiting T - oo matrix by applying standard results on the asymptotic behavior of Hermitian Toeplitz matrices (Böttcher et al., 2009). Let the autocorrelation be Ket+r 0r. The three cases of interest
26

---

Risk and cross validation in ridge regression with correlated samples
exponential correlations
ar = --
with correlation length ę > nearest-neighbor correlations
1
T= 0
b/2
T
=1
hewwes
with b [0, 1) (see Appendix 1), and power-law correlations
1
0r
(1
+ |T))x
with exponent X > O. The key object then the symbol of the Toeplitz operator corresponding to the finite matrices, which the Fourier transform of the autocorrelation:
w (
Σ
agetko
20
where 0 [0, 2T). For the three cases of interest, we can easily work out that
sinh(1/g)
w(O) = cosh(11E) cos(O)
(exponential)
w(f) = 1 + cos(()
(nearest-neighbor)
(0) - (ix e0 Lix (e -0--
10
(power-law)
where (x) is the polyogarithm order X. It is easy to verify that all three of these are real, positive continuously- differentiable functions that are symmetrie about 0 = n and minimized at that point, where they take the values
w(Tr) tanh 1
(exponential)
25
w(T) 1-
(nearest-neighbor)
w(T)) = 2(1 - 2 x(xx
(power-law),
(31)
where for power-law correlations the result for X = 1 understood in a limiting sense. By standard results on the minimum eigenvalue of Hermitian Toeplitz matrices, as these symbols are well-behaved w(T) both gives the T - oo limit of the minimum cigenvalue and lower bound on the minimum cigenvalue at any finite T. A stronger bound is given in (Böttcher et al., 2009), but we require only the weakest statement. Thurm,, as for each case of interest w(r) > 0 within the valid range of parameters, all of the matrices of interest remain invertible. For illustrative purposes, we compare (31) to numerical computation of the minimum eigenvalue for power-law correlations in Figure 7.
Under the assumption that K remains invertible in the large T limit, we have that limx-so df K (A)) = at any value of T. More generally & is a continuous monotonically decreasing function of À that goes from 1 when À = 0 to 0 as X - cc.
As + do we can expand and get at linear order that df K = X TrK = 4- Writing:
SK (df (A)) A SK (df (A))
df (A)
implies that at small X, SK is bounded from above by a T-independent constant at any T. SK is also bounded from below by (see F.1). Then, writing
A
Sx (gdfi);
gdf,
we see that Sg will not contribute any pole or zero that would effect the scaling properties of k as À 0. Consequently, correlated data does not affect the scaling law.
F. Double descent analysis
In this appendix, we study how double descent is effected by correlations. We also more generally study how correlations affect the key quantities of interest relative the uncorrelated setting.
In particular, we have lim ((x)) log 0.386
27

---

Risk and cross validation in ridge regression with correlated samples
F.1. Bounds on renormalized ridges Lemma F.l. For positive-definte K such that + Tr(K) 1 have that Sk (df) 2 1 for all values of df (0, 1].
Proof. We adapt an argument from Zavatone-Veth Pehlevan (2023). We recognize that for fixed x > 0 the function:
concave. Consquently, Jensen's inequality yields:
Ep R +
df (R) E K
df)(k)
pP
R
pointwise in R. Here Ep is the expectation over the spectrum of K. We have also used that Eplp] = T Tr(K) = 1. The above inequality strict unless K IT or =.
We next observe that both df k (A) and df, (A) are monotonically decreasing function in that are equal to 1 only when 0. This means that the solutions the equations df = df x and df = dfi (A) are unique for all df e (0, and is also monotonically decreasing. Consequently we have:
df (df) S df (df) 1- df
dr
Upon dividing both sides by d we get the desired equality = Sk(df) 2 This an equality when K Lr. When and thus df = 1, Sk (df) may still be greater than one.
Proposition F2. Let Fi be the renormalized ridge XS when the data has correlation structure K and let Ku be the corresponding value of K when there is no correlation between data points. We have Ke 2 Kw. Moreover, in the ridgeless limit Ric Feg-
Proof. In the correlated setting, we recall that the renormalized ridge Re solves
AS (
Kg 1 - --d (Kie)
Call the numerator A. From the preceding lemma we have that À 2 A. Thus, we have that K is equivalent to the self-consistent solution for the equation
Ā
Ke
qdf (Re)
But this is the same as the self-consistent equation for a linear regression problem with an explicit ridge À A. The proposition then follows from the fact that monotonic in À in the uncorrelated ridge regression setting.
As À + 0, is entirely determined by the pole structure of gdf 1. This is independent of any structure K and so in the ridgeless limit, Ke Ku.
Corollary F.3. Fix q. The presence correlations either decreases or keeps constant df, dig. In the ridgeless limit, they unchanged.
Proof. Evaluating df, as df, (x we have since Ke 2 Kr and df, monotone decreasing k that df; decreases. Since df, qdf,, this also decreases. Because is unchanged in the ridgeless limit, the last part of the corollary follows.
Corollary F.4. Fix q. The presence of correlations either decreases or keeps constant dfz, the ridgeless limit, unchanged.
Proof. The proof is as in the prior corollary, noting that df, dff is monotone decreasing in and K, 2 Kg,
Proposition F.S. Let Ra be the renormalized ridge X5 when the data has correlation structure K and let R. be the corresponding value of R when there is no correlation between data points. We have Feg S Ry. Moreover, in the ridgeless limit Ri Ri still.
28

---

Risk and cross validation in ridge regression with correlated samples
50
32
30
6 cof
cofr K
free
di corr
df, carr
10-
di free
d/3 free
30
dis free
d/g free
10
102 101
101
(a)
(b)
(c)
Figure 8. Theory curves comparing K, R, df,, df,, df2, df, for conrelated data K uncorrelated data K at 10 for N = 100 on isotropic data. For the correlations, we choose exponential correlations with length ç = 102 a) We see that when T < N, k; strongly agree, whereas when T .,, becomes of order the ridge while & becomes order The effects of correlations therefore noticcable in this limit. b) We see that the 1f dfi are unchanged between correlated (solid) and uncorrelated (dashed) data when the ridge is small. c) We see similar behavior for df, but for df, when T > N. Still, first order near N, we see agreement of df2 between the correlated and uncorrelated settings, as predicted by our theory.
Proof. When o we can rewrite the duality relation (20) as
q xdf (k)
R
This separately holds true for the pairs Kus Ki and Kir Re. We note that on the left hand side (x)) is sum of xytr over the eigenspectrum X; Σ. Each term is monotone increasing in K, and thus increases as we go from the uncorrelated Ki to the correlated Ke- Consequently, Re S Ra.
In the ridgeless limit, by the prior corollary, df is unchanged between correlated and uncorrelated data. Consequently, have:
1 = dft (15x) = (ne) S 1 Rc
1
1 + Ry
Thus, again have Re S Ra with equality only if K IT No =0
E2. Ridgeless limit
The limiting behavior of the renormalized ridges i and & depends whether is in the underparameterized regime T > N (q < 1) or the overparameterized regime T < N (q 1). In the underparameterizee regime, we have that J. 0 as A 4 O, while generically & remains non-zero and solves the self-consistent equation g = dr, (R). Conversely, in the overparameterized regime R i 0 as À J 0 while к remains non-zero and solves 1/4 = df, (k). We numerically illustrate these complementary limiting behaviors in Appendix J.
Our task now to determine the corresponding limits of the out-of-sample risk. First, we consider the case of matched correlations. There, the underparameterrzze regime we have y df2/g, /gg, while in the overparameterized regime we have y + gdf2. As result, find that
df
o²
< 1,
lim Ri X1O
q
df2
x²
gdf2
+1)+xx)22
I- gdf, d²
q 1,
gdf,
In the overparameterized ridgeless setting, since neither k. df, or df, is modified, the generalization error is exactly identical as that for linear regression. In the underparameterrized limit, study how dfz behaves. We write
) df (Rz)² dff (k..) (ff
dr (Rc) Ep
E,
p
Re
p+ 1D+R. Ri
where the expectation taken over the eigenspectrum of K. Moreover, near q = 1 when is small we have that at linear
29

---

Risk and cross validation in ridge regression with correlated samples
50
12
107
KL coF
10-1
free
dG cor
df, carr
di free
d/3 free
dis free
10a d/s free
30a
105
100 101
101
(a)
(b)
(c)
Figure 9. Theory curves comparing K, R, df,, df,, df2, df, for conrelated data K uncorrelated data K at A 10 for N = 100 on isotropic data. For the correlations, we choose exponential correlations with length ç 102 a) We see across the hoard that in the presence of explicit ridge, grows while & shrinks under correlations h) We that the df df1 always decreased by the presence of correlations when the ridge is present. c) We see similar behavior for df2. For df2, we also see a decrease in the neighborhood the double descent peak T N. Still, at first order near N, see agreement df,, between the correlated and uncorrelated settings, as predicted by our theory.
order:
1
df (R.) = 2R
= df (Ro)² O((3) = dff( 0KK))
Thus, at first order the double descent peak is unaffected by correlations in the underparametterized regime well. We illustrate these observations in Figure 8.
E3. Effective ridge enhancement
If À is finite, we have by Proposition F.2 that by F.5 that Kic > Ku and R. < k. Specifically, let Σx be the empirical covariance of the data when the data points have correlations K. We can write the following equivalence:
EK (Ex + +A)-1= EE + A.S((gdf)) (gdf;))
Thus adding correlations amounts to increasing the ridge. Because ΣK is bounded from above from Proposition E. I, in the ridgeless limit the A will remain zero.
When there is explicit ridge, we have that df,, df, will shrink from their uncorrelated values. Because to linear order in K, R. have df, (df,)² )2 at q and because correlations cause df decrease first order in at this point, we get that correlations cause dfş decrease in neighborhood of q 1.
As result of this, at first order in K, R, we can write y = (d)) Near 1, this will also shrink in the correlated case relative to the uncorrelated case. Thus, the double descent effect will be further reduced. We illustrate these observations in Figure 9.
E4. Mismatched correlations
Now we consider the case of mismatched correlations. We consider the fully general setting in which E' + E and K' + K. In the underparameterized regime, we have d + N Tr(E 'E') so TEV' + - 1 Tr(E E'). Similarly, KK''KK' - - ddr K Tr(E-1E)) In the overparameterized regime, we similarly have dr2 d + Tr(K-1K)), which leads >ΣΣ/ + qdl D
N
'E' and YEEKK KK + qdl + -KKK" Combining these results, we find that
dr KK Tr(E-1E) o²
q 1,
q -dds
-1 2 x² gdl g Σ 3E
lim Rg
2 Σ x) - E''
1 1-qdfz
2 EΣ' Pt(K-1K'
?
9>1
- gdl2
30

---

Risk and cross validation in ridge regression with correlated samples
The effect of mismatch is easiest understand in the overparameterized regime, where the factor + Tr(K (O(K-1 multiplies the same expression for the noise term that appears for uncorrelated datapoints. In the special case K' Ir, Jensen's 's inequality to bound
T TT(K-)
Tr(K)/T
with equality iff K Ir, hence in this special case mismatch generically increases the error.
F.5. Further comments on the effect of mismatched correlations
Here, we briefly comment further on the case in which the noise uncorrelated (K' Ir). In greatest generality, we seek to bound
di K. (R) TrK +
in terms of
1 TriK2(K + 7]
dk)(R) T
We prove a simple upper bound, which follows from negative association argument: Proposition F.6. For any & 2 0 and K invertible, we have
(T((K-)) (
df K KI (R) s
df2(R),
with equality when 0.
Proof. If & 0, the claim obviously holds with equality long K is invertible. Then, for any fixed R >> define Ø²
f()) = (p ++R Rj²
and
s(p) p'
such that
dr K. - k (R)
E[f(p))(p)
and
df)(R) = E[g(p)]
where expectation is taken with respect to the distribution of eigenvalues of K. Observe that f(p) is for any A > 0 monotone increasing function on (0, oc), while g(p) is monotone decreasing function (0, oo). Then, for any Pl, E (0, oc), we have
[f(p)) ((=))((o(p) s(p2)l S
so upon taking expectations for Pl, P2 independently drawn from the eigenvalue distribution of K we have
0 z B
( (p2))lo(()) - -9(02]] -2E((())((o) (E[(())B)((())
hence
([(())((P)) & ([(()))((()))
Using the definitions and g, this concludes the proof.
G. Asymptotics of previously-proposed extensions of the GCV
Here, we compute the high-dimensional asymptotics of prroposse extensions to the GCV in the presence of correlations. We write each estimator in the form
Epredicted GR
Moreover, we introduce the notation
H - (K + -
31

---

Risk and cross validation in ridge regression with correlated samples
for the smoothing matrix, in terms of which the predictions on the training set given
Hy:
these estimators make use of this matrix. For comparison, we recall from the main text that the asymptotically precise ConGCV estimator is
dr,
GConGEV S(dfi) dr dl2
G.1. The GCV
The standard GCV can be written
Geev = 1 1 Tr(H))2
T
hence have immediately that
1
GGoV [1 - dr, (R)]²
We denote this estimator by GCV, in Figure 5 and in all plots.
G.2. The Altman estimator
Starting from the GCV, Altman (1990) and later Opsomer et al. (2001) consider regression with correlated errors cov(c) o² K.
and and consider the estimator
GAltman
[1 T Tr(HK.))
Asymptotically, we have immediately that
G Alteman
TT/K + =)-
Putting K. K, we can write
+ [ 1 Tr- R(K + "1 - Tr(K) Rdf
hence, as Tr(K) by normalization, have
GARmman
R2d1
Using the duality relation
KW
X
df
this reduces to
x²
GAltman
~
S2
X2
We denote this estimator GCV, in Figure 5 and in all plots.
G.3. The GCCV estimator of Carmack al.
In our notation, Carmack et al. (2012) again assume that the label noise has COV(E) o² K.
and consider the estimator
GCarmack
[1- 1 Tr(2HK, HK,HT)
The first term is identical to Altman (1990)'s estimator, while the second is additional correction. We have (()
1
T Tr(HK.)
32

---

Risk and cross validation in ridge regression with correlated samples
Nearest-Wleighbor Correlation,
Nearest-Neighhor Correlations {- Eo1o A 1e:04, 00.05
1o-04, o,
10'
107
10
10a
Varz
Vars.
Navve GCV,
10tH
10-
Carmak GCV
ferve GCV,
CorsCV
207
107
201 101
107
101
(a) Unstructured Covariates
(b) Structured Covariates
Figure 10. Plot of the Carmack et al. (2012) estimator relative to other GCV estimators defined earlier. We note that similar to the naive GCVs and 2, the Carmack estimator fails to correctly predict R. a) Unstrucutred Covariates. Structured Covariates with source and capacity exponents labelled.
and
TTHKK,H 1
Tr - KIK
Ar 1)
T
Tr K.K,K(KHH (K))) A0
Tr K + 1)
T
1
0K
T Tr [
Tr|K
K K + R)
OAT
80
dR
+
Tr K,
K(K + -1
T
Setting K. = K, we have
OR 0x
Tr(2HK HKH Rdf,
df
T
$ Tr(K) 1. Now, using (24) and the defining equation X5 k, we have
dfg ब
1
Tr22K HKH = Rdî 1-
di
with
dfz df, df, dr
Then, have
- dfa
G GCarmack
Rdf;
h
df
1
We now write
df2 df
7
dr, df,
and use the duality relation expand ädf; A/R 1/S, which upon combining terms gives
1 df dfg
GCarmack
S df
33

---

Risk and cross validation in ridge regression with correlated samples
We recognize the term in brackets as the noise term when K
K' in (26). In general this implies that
drp
2
1
dfadr2 df dfs
2
Garmaack (1 -)) g2
S²
df dfg
1
df1 aF2
ConúCV2
When K = Ir, df, /(df - dfz) - 1/11-1/(R++1)
We plot an example of this estimator for correlated data in Figure 10; note the substantial deviation. This is to be expected, as there was no claim in Carmack et al. (2012) that this estimator should work for X correlations.
H. Weighted risks and the MMSE estimator
In this Appendix, we briefly comment on related risks and the MMSE estimator. As discussed in the main text, one might consider a weighted loss
LM = X MX y) + A||w>?; T for M& general positive-definite symmetric weighting matrix. Under our Gaussian statistical assumptions, this is equivalent to using unweighted loss with M +- IT, K 2 ///2K'//' and K' + 1/ M''MK'M
We now observe that the Bayesian MMSE estimator is equivalent to minimizing a weighted loss with the particular choice M = (K')-1. Under our statistical assumptions, the MMSE estimator is simply given by the posterior mean:
MMMSE = f dw p(w X, y).
Using our Gaussian assumptions on the data and Gaussian prior corresponding to the ridge penalty, the posterior is p(w x,y) x p( X, y w w)w)
pyy X, w w)p ()p(x))((((())) (p))
- X T())) (K')-
Xw) -T-K-'X---
|3]
exp
Discarding wo-independent terms and completing the square, this means that the posterior over w Gaussian with mean (X (x') + +1)-1 (K')-yy x
and covariance
(X (K') X X)-1
Therefore, the MMSE estimator corresponds to minimizing weighted loss with
M = (KK)-
If K' K, this then corresponds to minimizing an unweighted loss for uncorrelated datapoints.
However, we now observe that this procedure is only possible if one has omniscient knowledge of K', as reliably estimating (K') from samples is challenging.
I. S-transforms for certain Toeplitz covariance matrices
In this Appendix, we record formulas for the spectral statistics of a few tractable and practically-relevant classes of Toeplitz covariance matrices. We direct the interested reader to work by Küihn & Sollich (2012) or Basak al. (2014) for studies of the limiting spectral properties of empirical autocovariance matrices.
I.I. Neirest-neighhor correlations
We begin with the simplest non-trivial example: nearest-neighhor correlations. In this case we give a self-contained analysis, which hints at some of the approaches that can be used for more general classes of Toeplitz matrices. Suppose that
Kis
b/2 t= 1=
0
otherwise
34

---

Risk and cross validation in ridge regression with correlated samples
a symmetric tridiagonal Toeplitz matrix with diagonal elements and off-diagonal elements 6/2. We have the diagonal elements equal to 1 without loss of generality this is equivalent to choosing overall scale. Tridiagonal Toeplitz matrices are exactly diagonalized by Fourier modes (Noschese et al., 2013), and their eigenvalues are known to be
at
A = 1 + b cos
T+1 where = 1,.... T. Clearly, for the matrix to be positive-defintt we must have bb < 1; we will assume > without loss of generality as the cosine term symmetric. For a test function Φi we therefore have
Σ ((x) - Σ
1 [ cos T+I)
TI.
T
t=1
Recognizing this as a Riemann sum for an integral with respect to x = 1/(T + 1), it easy to see that
1 Σ ((xe) / dx Φ1 11 b m.:)
lim T T
Putting À = + b (T2). we have = 1 + b when x = 0 and = 1 when x = т. In this range, we can invert the relationship to find that r = arccos((A 1)/bl/T n. Differentiating, we have dx * =((-L+0)(==--)) dλ. Thus, the integral becomes
dA
v - b)(1 +b ((1).
1-6
This shows that for any b >>0 the limiting density of eigenvalues
x b,
v (A- 1 (A-1+b)
which is arcsine distribution centered at of width b. In other words, the limiting distribution is simply the pushforward of the uniform measure on [0. L] by 1 + b cos(Tz)), much the distribution at finite size is the pushforward of the uniform measure on {1/(T + 1)..,,) + 1)} by the same function.
Applying the result of this digression, the limit of the traced resolvent is
/ dA
1
gk (3)
TV(A - 1+ b)
-
1)² 62
From this, we can obtain with bit of algebra the corresponding S-transform
Sx(t) (1 + t) / + d2t(1
(1 b2)
We observe that the limit as 4 of these results gives
lim gK (x())
640
2
lim Sx())= 1, 610
which recover the expected results for the identity matrix.
1.2. Exponential correlations
Now we consider the case of exponential correlations
Kes - -t-ss/E
for some correlation length S, which is treated in the textbook Potters Bouchaud (2020). Though the eigenvectors of this matrix are not precisely Fourier modes finite size, one can argue that the approximation error the resolvent resulting from treating K circulant becomes negligible, and from that determine the limit. In the end, one finds that
t+1
(x(()= bt + V + (b2 - 1)
b coth 1/C.
35

---

Risk and cross validation in ridge regression with correlated samples
J. Further experiments
J.1. Exponential correlations
Resolutions, N 100, Isotropic Data
Resolutions, N - 100, Isotropic Data 1c: 04, 1c+02 Expanential
A= 13-03, 1e:02 Exponential
167
107
10
10-
10"4
Rocv
10ah
16
Kicy
Rocy
10
107
107
10t
Resalutions N = 100, a= 1.8 = 1e-06, 1e:02 Exponential
Resalutions N 100, a= 1.8 A= 1e-06, f 1e+02 Exponential
107
10F
10
10
10a
10-2
T-2
10-9
10-1
KoCv
KGcy
Recv
Rocy
10'4
10-4
10
10a
10
10a
13
Figure 11. Plots of the resolutions K, R under exponential correlations. Top: Isotropic Data. Bottom: Anisotropic power law data with the eigenvalues of Σ having power law decay k 1.8. Overlaid in dashed is the expected scaling in the overparameterized regime. Left: { 10-2, essentially uncorrelated. Right: & 10?, strongly correlated. We fix N = 100 and vary T. Overlaid in dashed is the scaling expected the overparameterized regime when
In this section we study the predictions of the theory for various relevant quantities in the case of both strong and weak exponential correlations. Plots of the eтrоr curves in this setting are numerous in the main text. We test this across both isotropic and structured data.
In Figure 11, we plot several different curves for K, R as T varies from small to large across differently structured datasets. We then plot the corresponding degrees of freedom in Figure 12. Finally, we verify the duality relation holds empirically in Figure 13.
36

---

Risk and cross validation in ridge regression with correlated samples
Degrees 100, Isatropic
Degrees 100, Isatrapic
A 1e-03, { 1e-02 Exponential
A 1e-04, {= 1e+02 Exponential
1.
100
0.8
dif
dif
dff
dff
dg
0.0
36
12
307
16
10
107
Degrees Freedom,
Degrees of Freedom,
A 1e-06, { 1e-02 Exponential
A 1c-06, {= 1e+02 Exponential
1.0
1.0
0.5
0.8
dff
dif
0.6
dif
dfg
dfg
dg
18P
103
16a
107
Figure 12. Plots of the the degrees of freedom df,, df,, df2, dfz under exponential correlations as in Figure 11. Solid lines theory, dots with error bars are empirics. The lack of substantial error bars stems from the fact that all quantities concentrate. We find that although día can be numerically sensitive, día remains numerically precise in the presence of strong correlations.
37

---

Risk and cross validation in ridge regression with correlated samples
Checking Duality Relation, N 100, Isotropic Data - 1e-03, {- 1e-02 Exponential
Checking Duality Relation, N 100, Isotropic Data A= 1e-04, E= 1e4402 Exponential
theory
theery
KRIA
KRIA 1/ar
1/dr
12P
100
10
10
10"1
12a
10
Duality Relation, 06, ş Exponential
Checking
Exponential
theory
101
theory
1/drk
1/0rk
10P
Figure 13. Plots verifying the duality relation " af hold for the settings in Figures 11 and 12 under exponential correlations. Dashed black lines lines are theory, dots with error bars are empiries. The lack of substantial error bars stems from the fact that all quantities concentrate.
38

---

Risk and cross validation in ridge regression with correlated samples
J.2. Nearest-neighhor correlations
Nearost-Naighhen hor Corne lations, N 100, Isotropiic Data 0.800, A 1e-04, o, 0.5
Nearast-Neigghor Correlations N- 100 a-1 a, a-1., 0.95, ==1e-04 a, 0.05
D.3
101
10-
Å.
Error
100
Verx VOC GCV) GCV,
Error
10-2
Vary
Vary
Natve GCV,
10-1
10a
207
10
10a
10
10
Figure 14. Risks, Sources of Variance, and Risk Estimators, similar Figure but with nearest neighbor correlations. a) Isotropic covariates. b) Structured covariates under source and capacity conditions.
The S-transform for correlation matrix K where only nearest neighbor data points correlated can be straightforwardly obtained. We do in Section 1.1. In general, the effect of correlations is quite weak unless the off-diagonal correlation element b/2 has 6 close to 1. In Figure 14, plot the risk curves and sources of variance in both the setting of isotropic and anisotropic data. In general, all estimators tend to agree better for the choices of b listed compared to the strongly exponentially correlated data. However, only the CorrGCV consistently correctly estimates the out-of-sample risk across T, X, and o.. Especially at small value T, we see that only the CorGGVV estimator is the most reliable.
We further plot the resolutions in Figure and degrees of freedom in Figure across two different values of 0.5, 0.95 both the isotropic and anisotropic case.
J.3. Power-law correlations
For power correlations, we do have an explicit analytic formula for SK- We instead estimate it by interpolating df к function of À and esimating the functional inverse df k as discussed in Section A.2 We ensure our interpolator compatible with autograd so that we can run Algorithm to get estimators for df2, df, and thus for the CorrGCV.
We show two examples with power-law correlations in Figure 17. We further plot the resolutions in Figure 18 and degrees of freedom in Figure 19 across two different values of x 1.5, 0.1 in both the isotropic and anisotropic case.
39

---

Risk and cross validation in ridge regression with correlated samples
Resolutions, N 100, Isotropic Data À 1e-03, b 0.50 NeareettNNiighor
Resolutions, N = 100, Isotropic Data À 1e-03, b - 0.95 Nearest-Neighhor
16
100
10
13-4
R
Kecv
Kicy
10--
Rocv
16-
Razv
10-
10
10
Resalutions == 100, a= 1.2 A 1e-05, b 0.50 Nearest -eiightt
Resolutions = 100, a= 12 A 1e-05, b 0.95 Nearest Nearest-Neighhor
10
10-1
10-9
Recv
10-9
Rocy
10-4
10
104
10
10
10
10'
Figure Plots the resolution K, under nearest neighbor correlations. Top: Isotropic Data. Bottom: Anisotropic power law data with the eigenvalues of Σ having power law decay --a, a = 1.2. Left: b = 0.5, weakly correlated. Right: & = 0.95, strongly correlated. We N 100 and vary T'. Solid lines are theory dots with error are empirics. Overlaid in dashed the expected scaling in the overparameterized regime when >> 1.
40

---

Risk and cross validation in ridge regression with correlated samples
Degrees Isotropic
Degrees
Isotropic
A 1e-03,, b= 0.50 Nearest-Neighber
A 11-03, D= 0.95 hearret-NNeighbr
1.0
100
2.8
3.6
2.6
9.4
92
111
dff
417
dff
dfg
-22
df5
-22
19
10'
107
15
10' 7
10'
7
Degrees Freedom, À 1e-05, b= 0.50 Searrel--Neighoor
Degrees Freedom, A 1e-05, b= 0.95 hearest-NNeihhoo.
1.0
df
dig
dff
off
dfg
0.4
d
dig
0.0
30'
101
18'
101
Figure 16. Plots of the the degrees of freedom df,, di, df2, dfa under nearest-neighhor correlations in Figure 15 Solid lines theory. dots with error bars are empirics. The lack of substantial error bars stems from the fact that all quantities concentrate. We find that although dfz can be numerically sensitive, dfa remains numerically precise in the presence of strong correlations.
Correlations, f= 1e-022.y0 y 0.7, a,
Correlations g=1., à. 0.3 5 1=1022 y 0.7, a,
10
109
30
Blas'
Bias?
Error
10-1
Error
30
Vary
Nalve GCV
Nalve GCV, Naive GCV, ComdCVV
10.2
Nave GCV,
CorrCCV
10-9
10-3
Figure 17. Risks. Sources of Variance, and Risk Estimators, similar to Figure 1, but with power law correlations E[ x (1+[t-8)) with exponent 0.7. a) Isotropic covariates. b) Structured covariates under source and capacity conditions.

---

Risk and cross validation in ridge regression with correlated samples
Resolutions, N 100, Isotropic Data
Resolutions, N = 100, Isotropic Data
A 1e-03, x= 1.5 Power Law
A 1e-03, x 0.1 Power Law
107
100
10-3
Rocv
10a
Racv
10
16-1
T
T
Resolutions N- 100, a 1.2 A 1e-05, 1.5 Power Law
Resolutions N - 100, a 12 A 1e-05, 0,1 Power Law
10
100
10-1
10--
10-
Kocv
KiCV
10
Figure 18. Plots of the resolution K, & under power law correlations. Top: Isotropic Data. Bottom: Anisotropic power law data with the eigenvalues of Σ having power law decay = 1.2. Overlaid in dashed is the expected scaling in the overparameterizeed regime. Left: x = 1.5, weakly correlated. Right: = 0.1, strongly correlated. We fix N = 100 and vary T'. For strongly correlated data, we slight deviation between x in theory and empirics. This due the low-degree polynomial interpolation estimator of Sy (gdfi) performing more poorly near gdf; = 1. This can be resolved with more flexible interpolant.
42

---

Risk and cross validation in ridge regression with correlated samples
Degrees 100, Isatrapic A 1e-03, x= 1.5 Power Law
Degrees =00, Isatrapic Dala
À 1e-03, x D.1 Power Law
dif
0.5
dif
0.8
dff
dff
0.4
0.4
db
d
36
19
107
16
10
10t
Degrees Freedom,
Degrees of
A 1e-05, y= 1.5 Power Law
A 1e:05, x D.1 Power Law
dff
dif
dfg
0.4
0.4
dg
18P
103
16a
107
103
Figure 19, Plots of the the degrees of freedom df,, df,, df2, dfz under power law correlations in Figure 18. Solid lines theory, dots with error bars are empirics. The lack of substantial error bars stems from the fact that all quantities concentrate. We find that although df, be numerically sensitive, dfa remains numerically precise in the presence of strong correlations.
43

---

Risk and cross validation in ridge regression with correlated samples
K. Experimental details
Error bars are always reported over ten runs of the same regression over different datasets. We ensembled over these datasets calculate the Varx term empirically. We also held out target free of label noise calculate the Varxe component of the variance empirically.
We used JAX (Bradbury et al., 2018) to perform all the linear algebraic manipulations. All experiments were done primarily on CPU with very little compute required. We also tested speedup of running our code on GPU, amounting to less than 1 GPU-day of compute usage. As mentioned in the main text, all code is available at http://githbb.com/Phllaaaa Group/S.transform.. transform.
44


Reviews:
[{"review_id": "VgfXhNyZwQ", "reviewer": "Reviewer_E8tJ", "summary": "This paper employs novel techniques from random matrix theory and free probability to analyze the asymptotic properties of the generalized cross-validation (GCV) as an empirical risk estimator for high-dimensional ridge regression, particularly in settings with cross-sectional and temporal correlations in both the covariates and the label errors. By leveraging insights from the in-sample and out-of-sample risks, the authors develop a new consistent estimator, CorrGCV, for the out-of-sample risk when the label noise exhibits the same correlation structure as the covariates. The performance of CorrGCV is further examined through a series of numerical experiments. Overall, the paper is well-written and was a pleasure to read.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful assessment of our manuscript. First, with regards to your questions and concerns: \n\n1. You are correct in stating that with the introduction of a weighting $M$ the definition of the effective vector of measured responses changes. Our observation here is simply that under our Gaussian statistical assumption on the matrix of observed covariates $X \\overset{d}{=} K^{1/2} Z \\Sigma^{1/2}$ and noise $\\epsilon \\overset{d}{=} (K')^{1/2} \\eta$ (for $Z$ and $\\eta$ having i.i.d. Gaussian elements), the minimizer of the weighted risk is equal in distribution to the minimizer of an unweighted risk with $K$ and $K'$ replaced by $M^{1/2} K M^{1/2}$ and $M^{1/2} K' M^{1/2}$, respectively. Therefore, one can apply the same results to obtain the asymptotics of the out-of-sample risk as defined in Line 147-148, which does not depend on the choice of weighting. We will revise the discussion starting on Line 157, and Appendix H, to clarify this issue. \n\n2. For a discussion of the derivation of (5), please see our response to Reviewer GGLG, who voiced similar concerns about the accessibility of the proof. In brief, the multiplicative property of the $S$-transform is one of the fundamental results of free probability. In this case it follows from studying the asymptotics of the resolvent of a Wishart matrix, but this multiplicative property extends to more general products of ``free'' random matrices (see Appendix B or the textbook of Potters and Bouchaud for a definition). \n\n3. The basic assumption we need to make on $K$ and $\\Sigma$ is that their empirical eigenvalue distributions tend to well-defined limiting measures as $T$ and $N$ tend to infinity, respectively. The support of these measures should be bounded strictly away from zero, and spectral moments of all orders (e.g., $\\frac{1}{T} \\mathrm{Tr}(K^{n})$) should be bounded. In our revised manuscript, we will make this clearer by stating these conditions as an explicit Assumption (as part of re-organization into Theorem-Proof style, as requested by Reviewer GGLG). \n\n4. Our focus on the case $K=K'$ is fundamentally motivated by our theoretical result that in that case the asymptotic risks are proportional. This is the same proportionality property that enables the definition of the (easily-computable) classic GCV as an asymptotically unbiased estimator of the out-of-sample risk for independent training samples. Our analysis shows that if $K \\neq K'$ then the training and test risks are not in general directly proportional, which means that an asymptotically un-biased estimator should not have the simple form of the GCV. This does not, however, mean that no estimator of the out-of-sample risk exists; it just must be something more than a multiplicative correction to the training risk.\nOne practically-relevant setting in which one would expect to have $K=K'$ is if the noise arises through components of the target function that cannot be learned through linear regression. Namely, nonlinear components will act as effective noise, as is discussed in the literature on Gaussian universality cited in our response to Reviewer XMHo. As mentioned there, we believe that a comprehensive examination of practical applications of the CorrGCV estimator is beyond the scope of this paper, as it is primarily theoretical in its aims. We will expand our discussion of Gaussian universality in our revised manuscript. \n\n\nIn addition to the changes reflected above, we will make the following additions to our manuscript: \n\n- We will add a figure showing a sweep over values of $\\lambda$ to show that the CorrGCV is broadly effective. \n\n- We will add citations to the five references you suggested; we regret that we missed these relevant works in preparing our manuscript.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "For the most part, the experimental designs make sense; however, I would like to see a bit more. For example, the purpose of cross-validation is essentially to choose the optimal tuning parameter $\\lambda$ that minimizes the out-of-sample risk. For this approach to be effective, CorrGCV must accurately approximate the risk over a wide range of $\\lambda$ values. Therefore, it would be beneficial to verify this behavior, rather than relying solely on the current setting with a fixed $\\lambda = 0.001$.", "relation_to_broader_scientific_literature": "I believe that the results of the paper enhance our understanding of the behavior of the out-of-sample risk when correlations are present in the data.", "essential_references_not_discussed": "1. Line 63-66, the authors state that \"However, most of these works focus on correlations only in the label noise, and none of them show\nthat their estimators are asymptotically exact in high dimensions. \" This is not entire accurate. There has been some work in the smoothing spline literature (which is essentially a high-dimensional Kernel ridge regression) on how to approximate the out-of-sample risk consistently when there are correlations. For example, [1]-[3].\n\n2. The asymptotic properties of the GCV for independent data have also been investigated in depth in \\cite{ref5} and \\cite{ref6} for kernel ridge regression, which I believe are also relevant.\n\nReferences:\n\n[1]. Wang, Y. (1998). Smoothing spline models with correlated random errors. Journal of the American Statistical Association, 93(441), 341-348.\n\n[2]. Xu, G., & Huang, J. Z. (2012). Asymptotic optimality and efficient computation of the leave-subject-out cross-validation.\n\n[3]. Gu, C., & Ma, P. (2005). Optimal smoothing in nonparametric mixed-effect models.\n\n[5]. Xu, G., Shang, Z., & Cheng, G. (2018). Optimal tuning for divide-and-conquer kernel ridge regression with massive data. In International Conference on Machine Learning (pp. 5483-5491). PMLR.\n\n[6]. Xu, G., Shang, Z., & Cheng, G. (2019). Distributed generalized cross-validation for divide-and-conquer kernel ridge regression and its asymptotic optimality. Journal of computational and graphical statistics, 28(4), 891-908.", "other_strengths_and_weaknesses": "Strength: The analysis is thorough and informative, and the paper is quite well written.\n\nWeakness: I am not sure how widely applicable the proposed CorrGCV criterion is in practice, since it requires that the label noise has the same correlation structure as the covariates ($K=K'$). Such a requirement does not seem to be very common in practical applications.", "other_comments_or_suggestions": "I believe that the motivation for the model considered in (1) needs to be significantly strengthened. A practical approach would be to provide concrete examples that demonstrate the usefulness of model (1) in real-world applications. In particular, since the proposed CorrGCV is specifically designed for the case where $K=K'$, it would be beneficial to include examples that illustrate why this assumption is both common and useful in practice.", "questions_for_authors": "1. In the last paragraph of Section 1, the authors discuss the weighted least squares loss with a weight matrix $M$. It is stated that \"this is equivalent to considering an isotropic loss under the mapping ... and as a result, our asymptotics apply immediately to general choices of $M$.\" I am afraid that this is not so simple. Under such a mapping, one would have to change the definition of the response vector $\\mathbf{y}$, and consequently, the definition of the risk would become dependent on $M$. Therefore, the theory would be applied to a different in-sample and out-of-sample risk than that originally defined for $\\mathbf{y}$. Could you please clarify this point?\n\n2. Can you provide more details on the derivation of the equations in (5)? As someone who is not familiar with free probability theory, I find it difficult to understand why these equations hold. Is this due to some special properties of Wishart matrices?\n\n3. What are the conditions on $K$ and $\\Sigma$ for equation (6) to hold? There is no requirement on the eigenvalues of $K$ and $\\Sigma$？\n\n4. In my opinion, the most interesting case is discussed in Section 3.3, as I believe it is very common in practice. However, the conclusion from this section appears to be that \"there is nothing we can do to approximate the out-of-sample risk.\" Is my understanding correct? If so, this outcome is quite disappointing and significantly limits the practical value of this work, as assuming $K=K'$ is rather restrictive. Could you explore the possibility of developing an alternative cross-validation method to approximate the out-of-sample risk based on the relationship between $R_g$ and $\\hat{R}$?", "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": "1SPLMYdgFd", "reviewer": "Reviewer_BdGx", "summary": "This paper investigates the problem of high-dimensional ridge regression with correlated data, which is a common feature in time series. Using methods from RMT and free probability, the authors derive sharp asymptotics for the in- and out-of-sample risk, showing that the standard cross-validation estimator fails for non-iid data, as it is asymptotically biased. They introduce a corrected GCV estimator that is unbiased and accurately predicts the out-of-sample risk, extending their results to the setting where test points are correlated with training points. Finally, they show that correlations can smooth the double-descent peak.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading of our manuscript, and are gratified by their strongly positive assessment. We will update the paper to address all three of their comments: \n\n- We will change the color used for the CorrGCV to to distinguish it from the NaiveGCV\\_1. \n\n- We will adopt the notation $\\mathrm{df}^{2}\\_{\\Sigma, \\Sigma'}$ to distinguish it from $\\mathrm{df}^{2}\\_{A=\\Sigma\\Sigma'}$. We would appreciate the reviewer's feedback on whether this notation is sufficiently distinct, or if further changes would be helpful. \n\n- We have fixed the typo on Line 436, thank you for catching this.", "claims_and_evidence": "All claims are supported by convincing evidence and limitations are clearly stated.", "methods_and_evaluation_criteria": "The methods used are well suited to the problem considered, as they are frequently employed in the study of ridge regression problems.", "theoretical_claims": "I have no issues to discuss.", "experimental_designs_or_analyses": "I have no issues to discuss.", "relation_to_broader_scientific_literature": "This work is related to several studies in the literature on ridge regression, extending for the first time previous findings to anisotropic data that exhibit correlations between samples (and additionally to correlations between test and training data). Most previous works have considered iid data or correlations in the label noise. Besides providing a corrected GCV estimator, the authors analyze the standard estimator as well as other estimators proposed in the literature, deriving sharp asymptotics and demonstrating their failure in high dimensions.", "essential_references_not_discussed": "I am not aware of any essential references that have been omitted.", "other_strengths_and_weaknesses": "I have not identified any major weaknesses. The presentation is clear, and the authors provide detailed explanations on algorithmic implementations, experiments, and the background knowledge necessary to understand their derivations. Even with its limitations, which are appropriately discussed, this paper provides original and interesting theoretical results closely related to time series applications.", "other_comments_or_suggestions": "-In several plots, the colors for CorrGCV and NaiveGCV_1 are very similar. I suggest changing one of them to improve clarity.\n\n-Even if clearly distinguishable from the context, I believe that the notations ${\\rm df}^2_{A}$ and ${\\rm df}^2_{\\Sigma\\Sigma'}$ (etc.) may be misleading, since ${\\rm df}^2_{\\Sigma\\Sigma'} \\neq {\\rm df}^2_{A = \\Sigma\\Sigma'}$.\n\n-Typo on line 436: the reference authors are repeated twice.", "questions_for_authors": "I do not have additional important questions.", "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": "dwtDUCepZD", "reviewer": "Reviewer_XMHo", "summary": "The paper proposes CorrGCV, a modified version of the more well known generalized cross validation estimator (GCV) to estimate out-of-sample risk from in-sample data.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad that the referee found our theoretical results \"sound'', and our experiments \"convincing.'' We appreciate the referee's concerns regarding demonstration of real-world applications, but given that our paper is theoretical in nature we are surprised by the strongly negative assessment. In particular, it is the first theoretical analysis of high-dimensional ridge regression with correlated samples, and thus contributes to the extensive theoretical literature on this simple and fundamental learning algorithm. \n\nWe would like to elaborate on why we believe the assumption of Gaussian covariates (under which our theoretical results were derived) is not highly restrictive. This assumption is motivated by the extensive literature on Gaussian universality in ridge regression: in the high-dimensional regime of interest, the risk obtained for some non-Gaussian dataset is asymptotically equal to that for Gaussian data of matched covariance (see, for instance, Hu and Lu https://arxiv.org/abs/2009.07669, Dubova et al https://arxiv.org/abs/2009.07669, or Misiakiewicz and Saeed https://arxiv.org/abs/2403.08938, or the many references cited within these works). Indeed, contemporaneous work from Luo et al (https://arxiv.org/abs/2406.11666) shows universality for data where features are uncorrelated but samples are correlated. And, since the submission of our manuscript, work by Moniri and Hassani (https://arxiv.org/abs/2412.03702) has shown universality for covariates of the form $X \\overset{d}{=} K^{1/2} Z \\Sigma^{1/2}$ where $Z$ has general sub-Gaussian i.i.d. entries; this generalizes our model in which we assumed the entries of $Z$ to be Gaussian. Therefore, we do not believe the assumptions under which are theoretical results are derived to be overly restrictive. We mentioned this motivation in our submitted manuscript, and will endeavor to make it more explicit in the revised version of our work. \n\nIn light of this, we respectfully request the referee to reconsider their assessment. While a comprehensive experimental validation of the CorrGCV estimator with real data will be important to establish its broad applicability, to do this justice would require a manuscript-length study in its own right. Therefore, we believe that the theoretical contributions of this work can stand alone.", "claims_and_evidence": "The theoretical derivations are sound.", "methods_and_evaluation_criteria": "The theoretical derivations are sound, the experiments are convincing.", "theoretical_claims": "The theoretical derivations are sound.", "experimental_designs_or_analyses": "Simulations are sound, however the paper lacks real world application analyses.", "relation_to_broader_scientific_literature": "The paper proposes CorrGCV, a modified version of the more well known generalized cross validation estimator (GCV) to estimate out-of-sample risk from in-sample data.", "essential_references_not_discussed": "Essential references have been mentioned.", "other_strengths_and_weaknesses": "* Modified CorrGCV is very interesting, and an improvement\n* However, it is unclear how sensitive the results will breakdown if assumptions are violated\n* Simulations are sound, however the paper lacks real world application analyses.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "* However, it is unclear how sensitive the results will breakdown if assumptions are violated: assumptions on correlation structure are too strcit \n* Simulations are sound, however the paper lacks real world application analyses.", "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": "mDd7l9VfIE", "reviewer": "Reviewer_GGLG", "summary": "This is a theoretical paper that studies cross-validation in ridge regularized linear regression. The authors study an understudied regime in the literature on cross-validation: when the samples are *not* i.i.d. In this case, they show that the traditional generalized cross-validation (GCV) estimator does not correctly estimate the out-of-sample error. By theoretically analyzing the exact out of sample error, the authors derive a cross-validation estimator that *does* correctly estimate the out-of-sample error. The authors extend the results to the case of distribution shift (the test point at which one wishes to assess the out-of-sample error comes from a different distribution than the training data), and when the test point is correlated with the training data.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and forthright assessment of our paper. We appreciate your concerns regarding the clarity of our manuscript, and will revise it to make its impact clearer. \n\n- Following your suggestion, we will re-organize the main text and Appendices into Theorem-Proof style. This will make the paper easier to navigate for the reader, and as you noted will break the lengthy Appendix C into more manageable chunks. \n\n- Your concerns regarding the accessibility of the proof methods to the ICML audience are well-taken. Our terminology, and the particular diagrammatic approach to the proof, is taken from physics. The core idea is to compute $\\mathbb{E} \\hat{\\Sigma} (\\hat{\\Sigma} + \\lambda I)^{-1}$ by expanding order-by-order in $1/\\lambda$ and then re-summing the resulting series of moments. Here, \"Wick contractions'' are pairings of indices corresponding to non-vanishing joint moments of elements of the Gaussian random matrix. This terminology comes from the fact that Isserlis' theorem for Gaussian moments is known in physics as \"Wick's theorem'' (Wick's theorem in physics is in fact far more general, but the terminology is applied also in the case of a Gaussian random vector). This approach is closely related to the diagrammatic formulation of the moment method in random matrix theory, where one builds a diagrammatic notation to represent the combinatorics of which elements in the expansion of an expression like $\\mathbb{E}_{M} \\mathrm{Tr}(M^n)$ give non-negligible contributions. \"Crossing diagrams'' refer to a subset of these pairings of indices that give rise to non-zero moments but do not contribute at leading order to the final result. \"Inserting'' a matrix corresponds to adding it to an ordered product of matrices at a particular location. We apologize for this rather heavy use of jargon; we will clarify each term in the updated version of our manuscript.", "claims_and_evidence": "I want to be up front that I really struggled to understand the detailed results of the paper, as I don't have a background in random matrix theory / free probability.\n\nMy one suggestion along these lines is that the paper could do a much better job of highlighting what the important results are, breaking them out into theorem/lemma/proposition environments, and then discussing the importance of these results. As-is, the paper reads a bit like a stream of formulae, without much connection back to results that matter to the broader machine learning community. I say this because I think there's some good potential impact to the ML community in this paper, but it's a little hard to dig out as-is. The only significant discussion is the final paragraph of the conclusion which comments on the applications of the theory. I think significantly adding to that discussion and moving more of the technical results to the appendix would strengthen the paper and better connect it to the ML community.", "methods_and_evaluation_criteria": "Yes, this is a theoretical paper, and the authors use synthetic data to demonstrate their results. This seems appropriate to me.", "theoretical_claims": "I attempted to check the proofs of some of the claims, but I don't have the required mathematical background to do so.\n\nI am a little worried whether much of the broader machine learning community has the needed background, and so whether ICML is an appropriate venue for this paper. An example of this is in Appendix C.1, which is a \"warm-up\" proof of preliminary results.The proof uses terms like \"insertions\", \"Wick contractions\", \"crossing diagrams\" that I've never heard of and struggled to find definitions of online. And the proof proceeds by drawing pictures, rather than using algebra, in a way that I'm also not familiar with.", "experimental_designs_or_analyses": "The paper is light on experiments because it's a theoretical paper. The use of synthetic data to back up the theoretical results is a nice addition.", "relation_to_broader_scientific_literature": "Cross-validation (CV) has a long history in statistics and machine learning. Despite its long history, its theoretical properties are complicated. In the last ~10 years, a growing body of work has started to understand the theory of CV. However, this body of work has primarily focused on models fit to i.i.d. samples, which is not realistic in practice. So, while the model studied by the authors is relatively simple (ridge regression), it starts to fill in an important gap in our understanding of a widely used procedure (CV).\n\n... all of this is assuming I've correctly understood the results of the paper!", "essential_references_not_discussed": "I don't believe there is anything major missing.", "other_strengths_and_weaknesses": "1. I think the theoretical development could be better organized to help readers. First, as mentioned above, I think the major results should be broken out into Proposition / Lemma / Theorem environments. This would help not only highlight the major results but also collect all of the necessary assumptions. E.g., which results require the independence of the noise $\\epsilon$ from the covariates $x$? This is stated in one sentence in Appendix C.5 (~line 1202), but I'm not sure which results it applies to.\n2. It wasn't always clear where to find the proof of various results in the paper. E.g., the first main result is derived in Section 3.2, which just states that some of the results are derived \"in Appendix C.\" But Appendix C contains many of the proofs.", "other_comments_or_suggestions": "Nothing else", "questions_for_authors": "No questions.", "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:

Meta-review: The submission has as main goal the study of a suitable cross validation estimator in the case of correlated samples. It has collected an overall positive feedback because of the novelty of the approach, based on random matrix theory and free probability tools, and of the results. The text clarity has also been remarked. The work has a theoretical nature and by consequence some concerns on the actual real-world application of the proposed estimator and analysis have been raised (due to a number of assumptions required for a full theoretical investigation). Nevertheless, the paper presents an interesting analysis on its own that might serve as starting point for the study of cross validation in presence of correlation. I thererefore suggests *Weak Accept*.
Decision: Accept (poster)