From Cross-Validation to SURE: Asymptotic Risk of Tuned Regularized Estimators
Authors: Karun Adusumilli, Maximilian Kasy, Ashia Wilson
Organizations: Department of Economics, University of Pennsylvania. · Department of Economics, University of Oxford. · Department of Electrical Engineering and Computer Science, MIT.
We derive the asymptotic risk function of regularized empirical risk minimization (ERM) estimators tuned by n-fold cross-validation (CV). The out-of-sample prediction loss of such estimators converges in distribution to the squared-error loss (risk function) of shrinkage estimators in the normal means model, tuned by Stein's unbiased risk estimate (SURE). This risk function provides a more fine-grained picture of predictive performance than uniform bounds on worst-case regret, which are common in learning theory: it quantifies how risk varies with the true parameter. As key intermediate steps, we show that (i) n-fold CV converges uniformly to SURE, and (ii) while SURE typically has multiple local minima, its global minimum is generically well separated. Well-separation ensures that uniform convergence of CV to SURE translates into convergence of the tuning parameter chosen by CV to that chosen by SURE.
Figures & tables
Figure 1: Risk function for JS-shrinkage, dimension 10
Figure 2: Examples of multi-modality of SURE
Result
Assumptions invoked
Builds on
Lemma 1 (Lipschitz gλ )
convexity of π
—
Lemma 2 (Influence-function approx.)
1, 2, 4.1, 4.2, 5.2
Lemma 1
Lemma 3 (Limiting squared-error loss)
1, 2, 5.3
—
Corollary 2 (Asymptotic distribution)
1, 4.1
Lemmas 1 , 2
Lemma 4 (CV → SURE)
1, 2, 3, 5.1–5.4
Lemmas 1 , 2 , Cor. 2
Lemma 5 (Tuning-parameter convergence)
1, 3
Lemmas 2 , 4 , Cor. 2
Table 1: Assumptions invoked by each result.
Loss
Penalty
p
θ0
A
D1
Linear
Ridge
10
(1,…,1)
I
D2
Linear
Lasso
10
(3,−3,2,0,…,0)
I
D3
Logit
Ridge
10
(1,…,1)
I
D4
Logit
Lasso
10
(3,−3,2,0,…,0)
I
D5
Linear
Ridge
10
1.5⋅(1,…,1)
diag(40(j−1)/9)
Table 2: Simulation designs.
Design
ΔIF
ΔCV
Δtune
Rn
R
ΔR
(Lem. 2)
(Lem. 4)
(Lem. 5)
(Thm. 1)
(limit)
∣Rn−R∣
D1 Linear / Ridge
0.028
0.208
0.052
3.110
3.084
0.026
D2 Linear / Lasso (sparse)
0.028
0.226
0.111
3.885
3.789
0.096
D3 Logit / Ridge
0.032
0.309
0.055
3.062
3.075
0.013
D4 Logit / Lasso (sparse)
0.038
0.297
0.127
3.731
3.776
0.046
D5 Linear / Ridge (anisotropic)
0.028
0.152
0.036
4.827
4.733
0.094
Table 3: Approximation diagnostics at n=400 .
Figure 3: Convergence of the approximations as n grows (designs identified in the legend panel, lower right). Top left: the influence-function error ΔIF (Lemma 2 ), ∝n−1 . Top right: the cross-validation gap ΔCV (Lemma 4 ), ∝n−1/2 . Bottom left: the finite-sample risk Rn converging to the limit R (dotted lines; Theorem 1 ).
Figure 4: Convergence of the risk function (linear–Ridge design). Along the slice θ0=t⋅v (with v a fixed unit vector, so ∥θ0∥=t ), the finite-sample risk Rn(θ0) of the CV-tuned estimator approaches the SURE-tuned limit R(θ0) ; by n=200 the curves are nearly indistinguishable from the limit.
This guide provides a reference for high-probability regret bounds in empirical risk minimization (ERM). The presentation is modular: we begin with intuition and general proof strategies, then state broadly applicable guarantees under high-level conditions and provide tools for verifying them for specific losses and function classes. We emphasize that many ERM rate derivations can be organized around a three-step recipe -- a basic inequality, a uniform local concentration bound, and a fixed-point argument -- which yields regret bounds in terms of a critical radius, defined via localized Rademacher complexity, under a mild Bernstein-type variance-risk condition. To make these bounds concrete, we upper bound the critical radius using local maximal inequalities and metric-entropy integrals, thereby recovering familiar rates for VC-subgraph, Sobolev/Hölder, and bounded-variation classes. We also study ERM with nuisance components -- including weighted ERM and Neyman-orthogonal losses -- as they arise in causal inference, missing data, and domain adaptation. Following the orthogonal statistical learning framework, we highlight that these problems often admit regret-transfer bounds linking regret under an estimated loss to population regret under the target loss. These bounds typically decompose the regret into (i) statistical error under the estimated loss and (ii) approximation error due to nuisance estimation. Under sample splitting or cross-fitting, the first term can be controlled using standard fixed-loss ERM regret bounds, while the second depends only on nuisance-estimation accuracy. As a novel contribution, we also treat the in-sample regime, in which the nuisances and the ERM are fit on the same data, deriving regret bounds and showing that fast oracle rates remain attainable under suitable smoothness and Donsker-type conditions.
Lars van der Laan
Department of Statistics, University of Washington
We present a simple Gaussian approximation to the finite-sample distribution of the classical ridge regression estimator. Our approximation captures the fact that, in finite samples, the ridge regression estimator trades off bias and variance to reduce estimation and prediction error. Our approximation is based on nonstandard asymptotics where i) we let the estimator's regularization parameter grow proportionally to the sample size; and ii) we treat the population regression coefficients as local to the reference vector that defines the estimator's direction of shrinkage. In contrast to other asymptotic approximations in the literature, we allow for general forms of heteroskedasticity and autocorrelation in the data generating process (at the cost of considering a low-dimensional model where the number of covariates is not allowed to grow with the sample size). We use our simple Gaussian approximation to propose two new strategies to select the regularization parameter for the ridge regression estimator. The suggested strategies select the regularization parameter to minimize either average or worst-case excess prediction risk, where risk is computed using our suggested Gaussian approximation.
José Luis Montiel Olea, Ryan Strong, Amilcar Velez +2
Cross-validation is one of the most widely used tools for risk estimation and model selection in statistics and machine learning, yet its theoretical properties when embedded in a learning procedure remain insufficiently understood. This paper develops a general, distribution-free framework for learning via model selection with cross-validation risk estimation within classical statistical learning theory. We establish VC dimension-based deviation bounds for the entire learning pipeline, providing detailed proofs for both bounded and unbounded loss functions, the latter requiring a novel extension of existing results. A central focus of the analysis is how the structure of the collection of candidate models influences generalization. To this end, we introduce Learning Spaces as collections of candidate models equipped with a partial order whose inclusion structure reflects increasing model complexity. We show how Learning Spaces can be constructed from domain knowledge and analyze how such structural information increases generalization. The framework is illustrated through case studies and a simulation study in high-dimensional linear regression, comparing learning via model selection in two distinct Learning Spaces against ordinary least squares, LASSO, and ridge regression across scenarios of varying alignment between prior knowledge and the true target. The results demonstrate that, when the Learning Space is well-adapted to the target and an efficient search algorithm is employed, learning via model selection can outperform standard methods by orders of magnitude. Through theoretical insights and concrete examples, we provide guidance on selecting the family of candidate models based on domain knowledge to enhance the performance of model selection with cross-validation.