Abstract
We examine generalized and leave-one-out cross-validation for ridge regression in a proportional asymptotic framework where the dimension of the feature space grows proportionally with the number of observations. Given i.i.d. samples from a linear model with an arbitrary feature covariance and a signal vector that is bounded in $\ell_2$ norm, we show that generalized cross-validation for ridge regression converges almost surely to the expected out-of-sample prediction error, uniformly over a range of ridge regularization parameters that includes zero (and even negative values). We prove the analogous result for leave-one-out cross-validation. As a consequence, we show that ridge tuning via minimization of generalized or leave-one-out cross-validation asymptotically almost surely delivers the optimal level of regularization for predictive accuracy, whether it be positive, negative, or zero.
Introduction
In modern machine learning, high-dimensional datasets—where the number of features ($p$) is comparable to or exceeds the number of observations ($n$)—are commonplace. To manage noise and prevent overfitting in these regimes, regularization techniques like Ridge regression are essential. These techniques rely on a tuning parameter, $\lambda$, typically selected via cross-validation (CV).
While CV is a standard tool, its theoretical reliability in high-dimensional settings has historically been less clear. Previous proofs of its effectiveness often relied on restrictive assumptions, such as feature independence or specific random distributions for the signal. This paper addresses a fundamental question: Does the cross-validation error curve converge to the true out-of-sample error curve as $n$ and $p$ grow? If so, minimizing the CV curve will asymptotically yield the "oracle" optimal model.
Theoretical Framework
The authors analyze Ridge Regression within a proportional asymptotic framework, where $n, p \to \infty$ such that $p/n \to \gamma \in (0, \infty)$. To handle the overparametrized regime, they employ an Extended Ridge Estimator based on the Moore-Penrose pseudoinverse, allowing for $\lambda$ values that are zero or even negative. They also utilize "shortcut" formulas that allow CV to be computed using only a single model fit on the full dataset, rather than naively re-fitting the model $n$ times.
A key technical contribution is the use of Bias-Variance Decomposition. Both the true prediction error and the Generalized Cross-Validation (GCV) estimate are broken down into their respective bias and variance components. By applying tools from random matrix theory and the Arzela-Ascoli theorem, the authors prove that the difference between the CV estimate and the true error vanishes uniformly across a range of $\lambda$ values. This uniform convergence ensures that the overall shape of the CV curve matches the true error curve, guaranteeing that the global minimum of the CV curve is a reliable proxy for the optimal regularization level.
Key Insights: The Power of Cross-Validation
The study reveals several critical properties of CV in high dimensions:
- Consistency for Interpolators: GCV remains a valid estimator even at $\lambda = 0$, where the model perfectly fits the training data. Although the standard GCV formula appears indeterminate ($0/0$) at this point, its limit correctly captures out-of-sample performance.
- Optimal Negative Regularization: In overparametrized settings, the optimal $\lambda$ is not always positive. If the signal is aligned with the "small" directions (eigenvectors with small eigenvalues) of the data covariance, a slightly negative $\lambda$ can actually improve predictive accuracy. The authors prove that CV is robust enough to identify these negative optima.
- Minimal Assumptions: Unlike prior work, this analysis does not require a random signal or independent features. It only assumes that the covariance matrix has bounded eigenvalues and the signal has a bounded $\ell_2$ norm.
Key Results and Empirical Validation
The primary theoretical result is the Uniform Consistency of GCV and Leave-One-Out Cross-Validation (LOOCV). Specifically, $|gcv(\lambda) - err(\lambda)| \to 0$ and $|loo(\lambda) - err(\lambda)| \to 0$ almost surely and uniformly over compact intervals of $\lambda$. This implies Asymptotic Optimality: the $\lambda$ chosen by minimizing CV results in a prediction error identical to that of an "oracle" with perfect knowledge of the data distribution.
Numerical simulations with synthetic data ($n=6000, p=12000$) illustrate these findings. Using an autoregressive covariance structure, the simulations show that the GCV and LOOCV curves track the true error curve with remarkable precision, even when the optimal regularization is negative.
Conclusion and Future Directions
This work provides a rigorous foundation for using CV to tune high-dimensional ridge models. However, some open questions remain. The current proofs assume covariance eigenvalues are strictly bounded; future research could explore "decaying" spectra. Additionally, while the results are asymptotically strong, determining finite-sample convergence rates would provide more practical guidance on the required sample sizes for reliable tuning. Finally, extending these uniform consistency results to non-linear models or other penalties like the Lasso remains a significant challenge for the field.
Summary updated