Risk and cross validation in ridge regression with correlated samples

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.

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

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

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.

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

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

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:

• We will change the color used for the CorrGCV to to distinguish it from the NaiveGCV_1.

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

• We have fixed the typo on Line 436, thank you for catching this.

Thank you for your careful assessment of our manuscript. First, with regards to your questions and concerns:

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

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

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

4. 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. One 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.

In addition to the changes reflected above, we will make the following additions to our manuscript:

• We will add a figure showing a sweep over values of $\lambda$ to show that the CorrGCV is broadly effective.

• We will add citations to the five references you suggested; we regret that we missed these relevant works in preparing our manuscript.