Fit polynomials in age of degree 0 to 8 to the systolic blood pressure of the 5,176 adults examined in NHANES 2017–2018 (National Center for Health Statistics, 2020), and estimate each one's prediction error by leave-one-out cross-validation. Degree 5 wins, with 301.95 mm Hg$^2$, against 302.76 for the straight line. Ten-fold cross-validation, repeated with 30 different random fold assignments, picks degree 5 twenty-six times, degree 8 three times and degree 6 once, and its usual standard error at degree 5 (the standard deviation of the ten fold errors over $\sqrt{10}$) is 8.50, ten times the quintic's advantage of 0.81. What does the number 301.95 estimate: the error of this fitted quintic on new adults, or the error of quintics fitted to samples like this one? And how far can its standard error be trusted? It estimates the error of quintics fitted to 5,176 adults like these, not that of this quintic, and its usual standard error is too small; the sections below prove both, and show that the 8.50 measures the uncertainty of the error level, not of the comparison between degrees.
Cross-Validation defines the method, derives the leave-one-out shortcut for least squares, and shows in simulation that the estimate tracks the average error over training sets better than the error of the fitted model, and that its usual standard error is too small. This article proves those statements and goes beyond them. It establishes which fitting methods admit the shortcut and why, what generalized cross-validation estimates, exactly what K-fold cross-validation estimates in expectation, why its estimate carries no information about the fitted model's own error in the normal linear model, and how large its variance is.
First we prove an exact condition for the leave-one-out shortcut and show that every linear smoother defined by penalized least squares (a quadratic penalty) meets it, while nearest neighbors does not. Then we prove that generalized cross-validation estimates the expected in-sample error with a relative error bounded in terms of the smoother's trace (Golub, Heath and Wahba, 1979). Next we prove that the expectation of K-fold cross-validation is the expected error of a model fitted to $n(1 - 1/K)$ observations, and that in the normal linear model the estimate is independent of the fitted model's error given the inputs (Bates, Hastie and Tibshirani, 2024). Then we derive the variance of the estimate and the bias of its naive standard error, and measure everything on the NHANES adults and the diabetes data. A last section places cross-validation among the model-selection criteria of The Bayesian Information Criterion and the Laplace Approximation. The article assumes The Geometry of Least Squares and the deletion identities of Leverage, Influence and Residual Diagnostics.
Notation and the running data
Two settings are used, and each result says which.
Fixed inputs. The notation of Optimism and Effective Degrees of Freedom: $\mathbf{y} = \boldsymbol\mu + \boldsymbol\varepsilon$ with errors of mean 0, variance $\sigma^2$, uncorrelated. A linear smoother produces fitted values $\hat{\mathbf{y}} = S\mathbf{y}$ with an $n \times n$ matrix $S$ that depends on the inputs but not on $\mathbf{y}$; its entries are $S_{ij}$. Least squares has $S = H$, the hat matrix, whose diagonal entries $h_{ii}$ are the leverages. The training error is $\overline{\mathrm{err}} = \lVert\mathbf{y} - \hat{\mathbf{y}}\rVert^2/n$, and the in-sample error $\mathrm{Err}_{\mathrm{in}}$ is the average squared error of $\hat{\mathbf{y}}$ on a fresh copy of $\mathbf{y}$ at the same inputs. That article proves that $\operatorname{tr}S$ is the smoother's degrees of freedom.
Random inputs. The data $\mathcal{T} = \{(\mathbf{x}_i, y_i)\}_{i=1}^n$ are independent draws from a population, and $(\mathbf{x}_0, y_0)$ is one more, independent of them. A fitting rule applied to $\mathcal{T}$ gives a prediction function $\hat f$. Following Bates, Hastie and Tibshirani (2024), with squared-error loss:
- the conditional error $\mathrm{Err}_{\mathcal{T}} = E[(y_0 - \hat f(\mathbf{x}_0))^2 \mid \mathcal{T}]$, the error of the model actually fitted (they write $\mathrm{Err}_{XY}$);
- the error given the inputs, $\mathrm{Err}_X = E[\mathrm{Err}_{\mathcal{T}} \mid \mathbf{x}_1, \ldots, \mathbf{x}_n]$, averaging over the outcomes only;
- the expected error $\mathrm{Err}(n) = E[\mathrm{Err}_{\mathcal{T}}]$, the average over training sets of size $n$; plotted against $n$ it is the learning curve.
K-fold cross-validation divides the $n$ observations at random into $K$ folds, fits the rule without each fold in turn, and averages the squared errors of the held-out predictions: $\mathrm{CV}_K = \frac1n\sum_i e_i$, with $e_i = (y_i - \hat f^{-\kappa(i)}(\mathbf{x}_i))^2$ and $\kappa(i)$ the fold of observation $i$. Leave-one-out is $K = n$.
Data. The NHANES adults are the unit's population, the 5,176 adults of the unit's file with a systolic reading and a body mass index, aged 18 to 80, treated as a finite population (no survey weights). Age is rescaled to $t = (\text{age} - 49)/31$ and polynomials are fitted in the Legendre basis, as in the BIC article. The diabetes data are the 442 patients and ten baseline inputs of Efron, Hastie, Johnstone and Tibshirani (2004), as in Model Selection. Every number is computed by tools/experiments/statistics/cross-validation-theory.py.
Leave-one-out for linear smoothers
For least squares, leaving out observation $i$ changes the prediction at $\mathbf{x}_i$ by an amount that can be read off the full fit: the deleted residual is $e_i/(1 - h_{ii})$ (Leverage, Influence and Residual Diagnostics, Theorem 1, proves it through the Sherman–Morrison formula). Hastie, Tibshirani and Friedman (2009, eq. 7.51) state that the same shortcut, with $S_{ii}$ in place of $h_{ii}$, holds "for many linear fitting methods", and their Exercise 7.3 asks for "general conditions on any smoother" that make it hold. Here is the answer. The shortcut holds exactly when leaving a point out simply removes its weight and rescales the rest; and every linear smoother defined by minimizing a sum of squares plus a penalty (in practice, a quadratic penalty) has that property.
Write $\hat y_{(-i)}$ for the prediction at $\mathbf{x}_i$ of the same rule fitted without observation $i$.
Lemma 1 (when the shortcut holds). Let $S_{ii} < 1$. The identity $$y_i - \hat y_{(-i)} = \frac{y_i - \hat y_i}{1 - S_{ii}}$$ holds for every $\mathbf{y}$ if and only if, for every $\mathbf{y}$, $$\hat y_{(-i)} = \sum_{j \ne i}\frac{S_{ij}}{1 - S_{ii}}\,y_j.$$
Proof. Since $\hat y_i = S_{ii}y_i + \sum_{j \ne i}S_{ij}y_j$, $$y_i - \frac{y_i - \hat y_i}{1 - S_{ii}} = \frac{y_i(1 - S_{ii}) - y_i + \hat y_i}{1 - S_{ii}} = \frac{\hat y_i - S_{ii}y_i}{1 - S_{ii}} = \sum_{j \ne i}\frac{S_{ij}}{1 - S_{ii}}y_j.$$ So the identity says $\hat y_{(-i)}$ equals the right side, which is the condition. $\square$
In words: the leave-one-out prediction must use the full fit's weights on the other points, divided by their total $1 - S_{ii}$ when the weights in each row of $S$ sum to 1. A rule with this property we call self-renormalizing. The next property is easier to check.
A rule is self-stable at $i$ if, after fitting without observation $i$ to get $\hat f^{(-i)}$, refitting on all $n$ points with $y_i$ replaced by the value $\hat f^{(-i)}(\mathbf{x}_i)$ returns a fit whose value at $\mathbf{x}_i$ is still $\hat f^{(-i)}(\mathbf{x}_i)$. Adding a point that lies exactly on the curve does not move the curve.
Theorem 1 (self-stable linear smoothers). If a linear smoother is self-stable at $i$ and $S_{ii} < 1$, the leave-one-out identity of Lemma 1 holds at $i$.
Proof. Let $v = \hat y_{(-i)}$ and let $\mathbf{z}$ be $\mathbf{y}$ with $z_i = v$. The full-data fit is linear in the responses, so its value at $\mathbf{x}_i$ on $\mathbf{z}$ is $\sum_{j \ne i}S_{ij}y_j + S_{ii}v$. Self-stability says this equals $v$. Solving, $v(1 - S_{ii}) = \sum_{j \ne i}S_{ij}y_j$, which is the condition of Lemma 1. $\square$
Lemma 2 (penalized least squares is self-stable). Suppose the rule chooses $f$ from a class $\mathcal{F}$ of functions to minimize $$\sum_{j \in D}\big(y_j - f(\mathbf{x}_j)\big)^2 + J(f)$$ over the data set $D$ in use, where the penalty $J \ge 0$ does not depend on the data, and suppose the minimizer exists and is unique both for all $n$ points and for the $n - 1$ points without $i$. Then the rule is self-stable at $i$.
Proof. Let $g$ be the minimizer without observation $i$, and replace $y_i$ by $g(\mathbf{x}_i)$. For any $f \in \mathcal{F}$, the full criterion on the modified data is $$\sum_{j \ne i}\big(y_j - f(\mathbf{x}_j)\big)^2 + \big(g(\mathbf{x}_i) - f(\mathbf{x}_i)\big)^2 + J(f) \ge \sum_{j \ne i}\big(y_j - f(\mathbf{x}_j)\big)^2 + J(f) \ge \sum_{j \ne i}\big(y_j - g(\mathbf{x}_j)\big)^2 + J(g),$$ the last step because $g$ minimizes the criterion without $i$. The right side is the full criterion of $g$ on the modified data, whose $i$th term is zero. So $g$ minimizes the full criterion on the modified data, and by uniqueness it is the full-data fit. Its value at $\mathbf{x}_i$ is $g(\mathbf{x}_i)$. $\square$
Lemma 2 holds for any penalty, the lasso's included, but self-stability turns into the shortcut only through Theorem 1, which needs the fit to be linear in $\mathbf{y}$. The lasso, when its solution is unique (as Lemma 2 requires, with and without point $i$), is self-stable and not linear, so it has no matrix $S$ and no shortcut of this form. A quadratic penalty gives a linear fit, as the next result shows.
Corollary 1. The leave-one-out identity holds for:
- least squares on any design of full column rank whose deleted design still has full rank, with $S = H$, $J = 0$; the sum of squared deleted residuals is Allen's (1974) PRESS statistic, so leave-one-out cross-validation equals $\mathrm{PRESS}/n$;
- ridge regression and any quadratic penalty $J(\boldsymbol\beta) = \boldsymbol\beta^{\mathsf T}\Omega\boldsymbol\beta$ with $\Omega$ positive semidefinite on a basis expansion $f(\mathbf{x}) = \mathbf{b}(\mathbf{x})^{\mathsf T}\boldsymbol\beta$, whenever $B^{\mathsf T}B + \Omega$ and its leave-one-out version are positive definite ($B$ the matrix of basis functions at the data), with $S = B(B^{\mathsf T}B + \Omega)^{-1}B^{\mathsf T}$; penalized regression splines and the smoothing splines of Hastie et al.'s exercise are of this form.
In both cases $0 \le S_{ii} \le 1$, so the deleted residual is never smaller in absolute value than the ordinary one.
Proof. With a quadratic penalty and a positive definite $B^{\mathsf T}B + \Omega$, the criterion is a strictly convex quadratic in $\boldsymbol\beta$ with the unique minimizer $(B^{\mathsf T}B + \Omega)^{-1}B^{\mathsf T}\mathbf{y}$, linear in $\mathbf{y}$, and the same holds without row $i$; fitted values are then unique. Lemma 2 and Theorem 1 apply once $S_{ii} < 1$. That inequality follows from the matrix determinant lemma exactly as in Ridge and Lasso Regression (proof of Theorem 4): $\det(M - \mathbf{b}_i\mathbf{b}_i^{\mathsf T}) = \det M\,(1 - S_{ii})$ with $M = B^{\mathsf T}B + \Omega$, and both determinants are positive. Least squares is the case $\Omega = 0$, where $M$ and the deleted $M$ are positive definite by the rank assumptions. For the bounds, $S$ is symmetric, and $S - S^2 = B M^{-1}\Omega M^{-1}B^{\mathsf T}$ is positive semidefinite (expand $S^2 = BM^{-1}(M - \Omega)M^{-1}B^{\mathsf T}$), so $S_{ii} \ge (S^2)_{ii} = \sum_jS_{ij}^2 \ge S_{ii}^2$, which gives $0 \le S_{ii} \le 1$. $\square$
Part 1 recovers the deletion identity of Leverage, Influence and Residual Diagnostics without matrix inversion, and part 2 recovers ridge's (Theorem 4 of Ridge and Lasso Regression). Golub, Heath and Wahba (1979, §2) give the ridge case through the Sherman–Morrison–Woodbury formula, and they call the leave-one-out criterion Allen's PRESS; Hastie et al. list Allen (1974) among the key references for cross-validation.
Example (a kernel smoother is self-renormalizing). The Nadaraya–Watson smoother predicts at $\mathbf{x}_i$ by a weighted average with weights $K_{ij} = K(\mathbf{x}_i, \mathbf{x}_j) \ge 0$: $S_{ij} = K_{ij}/\sum_lK_{il}$. Without observation $i$ the weights become $K_{ij}/\sum_{l \ne i}K_{il}$ for $j \ne i$, and $\sum_{l \ne i}K_{il}/\sum_lK_{il} = 1 - S_{ii}$, so the leave-one-out weights are $S_{ij}/(1 - S_{ii})$, the condition of Lemma 1. It is not a penalized least-squares fit, so Lemma 1 is the more general route.
Example (nearest neighbors is not). The $k$-nearest-neighbor rule averages the outcomes of the $k$ training points closest to $\mathbf{x}$; at a training point, the point itself is one of them, so $S_{ii} = 1/k$ and $S_{ij} = 1/k$ for its $k - 1$ nearest other points. Lemma 1's right side averages those $k - 1$ points. But the rule refitted without $i$ averages the $k$ nearest other points, bringing in a new one. So the shortcut computes the leave-one-out error of the $(k - 1)$-nearest-neighbor rule. On the diabetes data, with progression predicted from standardized BMI, blood pressure and S5 and $k = 10$ (these three inputs have no ties among any patient's eleven nearest distances), the true leave-one-out error is 3,279.4 and the shortcut gives 3,364.2, which the script confirms is exactly the leave-one-out error of 9 nearest neighbors.
Check. On 200 NHANES adults drawn at random (seed 20261119), the shortcut was compared with 200 explicit refits for four smoothers of pressure on age: least squares with a cubic; ridge with degree 8 and penalty 1 on the non-constant Legendre coefficients (trace of $S$ 8.639); a cubic B-spline basis of 20 functions with penalty 10 on the squared second differences of the coefficients (trace 7.340); and the Nadaraya–Watson smoother with a Gaussian kernel of bandwidth 5 years. The shortcut and the refits agreed to within $10^{-8}$ for every adult and every smoother.
Generalized cross-validation
Leave-one-out needs each $S_{ii}$. Generalized cross-validation replaces each by the average $\mu_1 = \operatorname{tr}S/n$: $$\mathrm{GCV} = \frac{\frac1n\lVert(I - S)\mathbf{y}\rVert^2}{(1 - \mu_1)^2}$$ (Craven and Wahba, 1979; Golub, Heath and Wahba, 1979, eq. 1.4; Hastie et al., 2009, eq. 7.52). Two identities explain what this does to leave-one-out.
Proposition 1. (i) GCV is a weighted PRESS: with $r_i = (y_i - \hat y_i)/(1 - S_{ii})$ the leave-one-out residuals of Lemma 1, $$\mathrm{GCV} = \frac1n\sum_{i=1}^n w_ir_i^2, \qquad w_i = \Big(\frac{1 - S_{ii}}{1 - \mu_1}\Big)^2.$$ (ii) GCV is unchanged if the data are rotated, $\mathbf{y} \mapsto Q\mathbf{y}$ and $S \mapsto QSQ^{\mathsf T}$ for an orthogonal $Q$; leave-one-out in general is not.
Proof. (i) $w_ir_i^2 = (y_i - \hat y_i)^2/(1 - \mu_1)^2$; average over $i$. (ii) $\lVert(I - QSQ^{\mathsf T})Q\mathbf{y}\rVert = \lVert Q(I - S)\mathbf{y}\rVert = \lVert(I - S)\mathbf{y}\rVert$ and $\operatorname{tr}(QSQ^{\mathsf T}) = \operatorname{tr}S$. Leave-one-out depends on the individual diagonal entries, which a rotation changes. $\square$
So GCV down-weights the leave-one-out residuals of high-leverage points and up-weights the others, and it equals leave-one-out when all $S_{ii}$ are equal. Golub, Heath and Wahba (1979, §2) derive GCV as leave-one-out applied after a rotation that makes the diagonal constant, and they argue that, when the coefficients and errors have spherical normal priors, a good choice of a ridge parameter should be invariant under rotations; they also note that in the extreme case of a diagonal design, leave-one-out does not depend on the ridge parameter at all and so cannot choose it. What does GCV estimate? Since it needs no estimate of $\sigma^2$, the natural target is the in-sample error, and the next theorem bounds the gap.
Theorem 2 (Golub, Heath and Wahba, 1979, Theorem 1, there for symmetric $S$). Let $S$ be fixed, $0 \le \mu_1 = \operatorname{tr}S/n < 1$ ($\mu_1 \ge 0$ when every $S_{ii} \ge 0$; both bounds hold for the smoothers of Corollary 1 and the kernel smoother, whose $S_{ii}$ lie in $[0, 1)$), $\mu_2 = \operatorname{tr}(S^{\mathsf T}S)/n > 0$, $b^2 = \lVert(I - S)\boldsymbol\mu\rVert^2/n$, and let $R = E\lVert S\mathbf{y} - \boldsymbol\mu\rVert^2/n = b^2 + \sigma^2\mu_2$ be the risk of the fitted means. Then $$\frac{E[\mathrm{GCV}] - \sigma^2 - R}{R} = \frac{\mu_1(2 - \mu_1)}{(1 - \mu_1)^2} - \frac{\sigma^2\mu_1^2}{R(1 - \mu_1)^2}, \quad\text{so}\quad \frac{\lvert E[\mathrm{GCV}] - (\sigma^2 + R)\rvert}{R} \le \Big(2\mu_1 + \frac{\mu_1^2}{\mu_2}\Big)\frac{1}{(1 - \mu_1)^2}.$$ Since $E[\mathrm{Err}_{\mathrm{in}}] = \sigma^2 + R$, GCV is nearly unbiased for the expected in-sample error, with a relative error controlled by $\mu_1$ and $\mu_1^2/\mu_2$.
Here is the idea. The numerator of GCV is the training error, whose expectation falls short of $\sigma^2 + R$ by the optimism; dividing by $(1 - \mu_1)^2 \approx 1 - 2\mu_1$ adds back about $2\mu_1$ times the training error, which is about the optimism $2\sigma^2\mu_1$ of Optimism and Effective Degrees of Freedom. The theorem measures what "about" costs.
Proof. For a fixed matrix $A$, $E\lVert A\mathbf{y}\rVert^2 = \lVert A\boldsymbol\mu\rVert^2 + \sigma^2\operatorname{tr}(A^{\mathsf T}A)$, the mean of a quadratic form (Covariance Matrices and Quadratic Forms, Theorem 5). With $A = I - S$, $\operatorname{tr}((I - S)^{\mathsf T}(I - S)) = n - 2\operatorname{tr}S + \operatorname{tr}(S^{\mathsf T}S)$, so $$E\Big[\tfrac1n\lVert(I - S)\mathbf{y}\rVert^2\Big] = b^2 + \sigma^2(1 - 2\mu_1 + \mu_2).$$ With $A = S$ and mean $\boldsymbol\mu$ subtracted, the same formula gives $R = b^2 + \sigma^2\mu_2$. The denominator of GCV is not random. Write $q = (1 - \mu_1)^2$, so $1 - q = \mu_1(2 - \mu_1)$. Then $$q\big(E[\mathrm{GCV}] - \sigma^2 - R\big) = b^2 + \sigma^2(1 - 2\mu_1 + \mu_2) - q(\sigma^2 + b^2 + \sigma^2\mu_2) = (b^2 + \sigma^2\mu_2)(1 - q) + \sigma^2(1 - 2\mu_1 - q) = R\,\mu_1(2 - \mu_1) - \sigma^2\mu_1^2,$$ using $1 - 2\mu_1 - q = -\mu_1^2$. Divide by $qR$ for the identity. Both terms on its right are nonnegative, because $0 \le \mu_1 < 1$, so the absolute value of their difference is at most the larger, hence at most their sum; and $\sigma^2/R \le 1/\mu_2$ because $R \ge \sigma^2\mu_2$, while $\mu_1(2 - \mu_1) \le 2\mu_1$. $\square$
For a projection ($S$ symmetric and idempotent of rank $p$), $\mu_1 = \mu_2 = p/n$ and the bound is $3(p/n)/(1 - p/n)^2$, the expression Golub, Heath and Wahba's Example 1 obtains as a bound for ridge regression with $p$ columns. Leave-one-out and GCV agree when $p/n$ is small and the leverages are even. Golub, Heath and Wahba also show that the expected GCV has a (possibly local) minimizer whose expected risk is within a factor $(1 + h)/(1 - h)$ of the smallest possible, with $h$ the bound of Theorem 2, a result not reproduced here.
Blood pressure by age
For the 5,176 adults, with polynomials of degree $d$ ($p = d + 1$ coefficients) and ten-fold cross-validation repeated over fold seeds 1 to 30:
| Degree | Training error | Leave-one-out (PRESS/$n$) | GCV | Ten-fold, median over seeds |
|---|---|---|---|---|
| 0 | 396.07 | 396.22 | 396.22 | 396.20 |
| 1 | 302.53 | 302.76 | 302.77 | 302.77 |
| 2 | 302.32 | 302.67 | 302.67 | 302.69 |
| 3 | 302.05 | 302.51 | 302.51 | 302.54 |
| 4 | 301.93 | 302.51 | 302.52 | 302.53 |
| 5 | 301.27 | 301.95 | 301.97 | 302.02 |
| 6 | 301.20 | 302.00 | 302.02 | 302.07 |
| 7 | 301.20 | 302.11 | 302.14 | 302.19 |
| 8 | 301.05 | 302.06 | 302.09 | 302.13 |
Leave-one-out and GCV both choose degree 5. At degree 5 Theorem 2's bound is $3\mu_1/(1 - \mu_1)^2 = 0.00349$ with $\mu_1 = 6/5{,}176$: GCV's expectation is within 0.349% of the expected in-sample error, for any true mean function. The ten-fold estimate at degree 5 ranged over the fold seeds from 301.90 to 302.17 (interquartile range), wider than the differences among degrees 5, 6 and 8 in the table, and the minimum fell on degree 5 for 26 of the 30 fold seeds, degree 8 for 3 and degree 6 for 1. The quintic improves on the line by 0.81 in leave-one-out error. That is 1.6 times the naive standard error of the paired difference, 0.51 (the standard deviation of the 5,176 differences between the two models' leave-one-out squared errors, over $\sqrt{5{,}176}$), whereas the error level of either model is uncertain by about 8.50 (the fold-level standard error of the ten-fold estimate at degree 5, median over seeds) or 8.52 (the same idea computed from the 5,176 leave-one-out losses). Two estimates made on the same adults move together, so their difference is far less noisy than either. The last section returns to what such a choice means; first, what is being estimated.
What K-fold cross-validation estimates
Here is the idea in one sentence: each held-out observation is a fresh draw from the population, scored by a model fitted to $n - n/K$ other fresh draws, so on average the estimate is the error of a model fitted to that many points.
Theorem 3 (the expectation of K-fold cross-validation). Let the data be independent draws from a population, let $K$ divide $n$, let the folds have $n/K$ observations each and be assigned independently of the data, and let the expected squared error of the rule fitted to $n - n/K$ points be finite. Then $$E[\mathrm{CV}_K] = \mathrm{Err}\big(n - n/K\big).$$ In particular $E[\mathrm{CV}_n] = \mathrm{Err}(n - 1)$ for leave-one-out.
Proof. Fix the fold assignment (it is independent of the data). Take $i$ in fold $k$. The fit $\hat f^{-k}$ uses only the $n - n/K$ observations outside fold $k$, which are independent draws from the population, and $(\mathbf{x}_i, y_i)$ is a draw independent of them. Conditioning on those observations, $$E\big[(y_i - \hat f^{-k}(\mathbf{x}_i))^2 \mid \text{data outside fold } k\big] = \mathrm{Err}_{\mathcal{T}_{-k}},$$ the conditional error of the model fitted to them, because $(\mathbf{x}_i, y_i)$ has the population's distribution and is independent of them. Taking expectations, $E[e_i] = E[\mathrm{Err}_{\mathcal{T}_{-k}}] = \mathrm{Err}(n - n/K)$. Average over $i$. $\square$
So the bias of K-fold cross-validation as an estimate of $\mathrm{Err}(n)$ is exactly $\mathrm{Err}(n - n/K) - \mathrm{Err}(n)$, the rise of the learning curve over the data held out, which Cross-Validation observed. Nothing in the theorem refers to the model actually fitted to all $n$ points.
Check on the NHANES adults. Training sets of $n = 100$ adults were drawn with replacement from the 5,176 (independent draws from the population, as the theorem needs), and a cubic in age was fitted by least squares. The conditional error $\mathrm{Err}_{\mathcal{T}}$ of each fit was computed exactly, as its mean squared error over all 5,176 adults. For 30 seeds, 400 training sets each, the pooled means were:
| Estimate | Pooled mean | Learning curve at the matching size | Pooled mean | Monte Carlo SE of the difference |
|---|---|---|---|---|
| 2-fold | 328.63 | $\mathrm{Err}(50)$ | 328.90 | 0.71 |
| 5-fold | 318.07 | $\mathrm{Err}(80)$ | 318.16 | 0.62 |
| 10-fold | 316.11 | $\mathrm{Err}(90)$ | 316.07 | 0.61 |
| Leave-one-out | 314.74 | $\mathrm{Err}(99)$ | 314.87 | 0.60 |
Every difference is within half a Monte Carlo standard error of 0 (the script asserts it), as Theorem 3 predicts; the learning-curve values were estimated from separate training sets of the matching size. The expected error at $n = 100$ itself was 314.71. Two-fold cross-validation overstates it by about 14, the rise of the learning curve from 100 points to 50.
The diabetes design with normal errors
Theorem 3 is about expectations. Does a single cross-validation estimate say anything about the model fitted to the data at hand? In the normal linear model fitted by least squares, nothing at all, given the inputs.
Lemma 3 (linear invariance). For least squares with every training part of full column rank, $\mathrm{CV}_K$ computed from $(X, \mathbf{y} + X\boldsymbol\gamma)$ equals $\mathrm{CV}_K$ computed from $(X, \mathbf{y})$, for every vector $\boldsymbol\gamma$ and every fold assignment. Consequently $\mathrm{CV}_K$ is a function of $X$, the fold assignment and the residual vector $\mathbf{e} = (I - H)\mathbf{y}$ only.
Proof. Let $X_{-k}$ be the rows outside fold $k$. Least squares on $(X_{-k}, \mathbf{y}_{-k} + X_{-k}\boldsymbol\gamma)$ gives $(X_{-k}^{\mathsf T}X_{-k})^{-1}X_{-k}^{\mathsf T}\mathbf{y}_{-k} + \boldsymbol\gamma$, so each held-out prediction rises by $\mathbf{x}_i^{\mathsf T}\boldsymbol\gamma$, exactly as $y_i$ does, and every held-out error is unchanged. Taking $\boldsymbol\gamma = -\hat{\boldsymbol\beta}$ replaces $\mathbf{y}$ by $\mathbf{y} - X\hat{\boldsymbol\beta} = \mathbf{e}$. $\square$
Theorem 4 (Bates, Hastie and Tibshirani, 2024, Theorem 1). Let $y_i = \mathbf{x}_i^{\mathsf T}\boldsymbol\beta + \varepsilon_i$ with the $\varepsilon_i$ independent $N(0, \sigma^2)$ (normal with mean 0 and variance $\sigma^2$) and independent of the inputs, which are independent draws with second-moment matrix $\Sigma = E[\mathbf{x}_0\mathbf{x}_0^{\mathsf T}]$. Fit by least squares. Then, given $X$, the cross-validation estimate (for any $K$ and fold assignment) is independent of the conditional error $$\mathrm{Err}_{\mathcal{T}} = \sigma^2 + (\hat{\boldsymbol\beta} - \boldsymbol\beta)^{\mathsf T}\Sigma(\hat{\boldsymbol\beta} - \boldsymbol\beta).$$ Consequently $E[(\mathrm{CV}_K - \mathrm{Err}_{\mathcal{T}})^2] = E[(\mathrm{CV}_K - \mathrm{Err}_X)^2] + E[\operatorname{Var}(\mathrm{Err}_{\mathcal{T}} \mid X)]$: cross-validation estimates $\mathrm{Err}_X$ more accurately than it estimates the error of the model at hand.
Proof. First the formula: $y_0 - \mathbf{x}_0^{\mathsf T}\hat{\boldsymbol\beta} = \varepsilon_0 - \mathbf{x}_0^{\mathsf T}(\hat{\boldsymbol\beta} - \boldsymbol\beta)$, with $\varepsilon_0$ independent of everything else and of mean 0; squaring and averaging over $(\mathbf{x}_0, \varepsilon_0)$ gives $\sigma^2 + (\hat{\boldsymbol\beta} - \boldsymbol\beta)^{\mathsf T}\Sigma(\hat{\boldsymbol\beta} - \boldsymbol\beta)$. So $\mathrm{Err}_{\mathcal{T}}$ is a function of $\hat{\boldsymbol\beta} - \boldsymbol\beta = M^{-1}X^{\mathsf T}\boldsymbol\varepsilon$, with $M = X^{\mathsf T}X$, and by Lemma 3 the estimate is a function of $\mathbf{e} = (I - H)\boldsymbol\varepsilon$ and the independent fold assignment. Given $X$, the pair $(M^{-1}X^{\mathsf T}\boldsymbol\varepsilon, (I - H)\boldsymbol\varepsilon)$ is jointly normal with cross-covariance $\sigma^2M^{-1}X^{\mathsf T}(I - H) = \sigma^2M^{-1}(X^{\mathsf T} - X^{\mathsf T}H) = 0$, since $X^{\mathsf T}H = X^{\mathsf T}$; uncorrelated jointly normal vectors are independent (The Multivariate Normal Distribution). Functions of independent vectors are independent. For the decomposition, write $\mathrm{CV}_K - \mathrm{Err}_{\mathcal{T}} = (\mathrm{CV}_K - \mathrm{Err}_X) - (\mathrm{Err}_{\mathcal{T}} - \mathrm{Err}_X)$ and expand the square. The cross term has expectation $E\big[E[\mathrm{CV}_K - \mathrm{Err}_X \mid X]\;E[\mathrm{Err}_{\mathcal{T}} - \mathrm{Err}_X \mid X]\big]$ by the conditional independence, and the second factor is 0 by the definition of $\mathrm{Err}_X$. $\square$
The proof is Bates et al.'s, who give it in a few lines; they state it for every "linearly invariant" estimator, which includes Mallows' $C_p$, data splitting and bootstrap estimates. Their Theorem 2 adds that when $n$ and the number of inputs grow together, $\mathrm{Err}_X$ varies much less than $\mathrm{Err}_{\mathcal{T}}$ (variance of order $1/n^2$ against $1/n$ for normal inputs), so the estimate is asymptotically uncorrelated with $\mathrm{Err}_{\mathcal{T}}$ and is best read as an estimate of $\mathrm{Err}$.
Example (the diabetes design). Keep the 442 patients' ten inputs fixed, and simulate outcomes from the fitted ten-input model, $\boldsymbol\beta = \hat{\boldsymbol\beta}$ and $\sigma^2 = 2{,}932.7$ (the residual mean square), with normal errors. Let the population of inputs be the 442 rows themselves, so $\Sigma = X^{\mathsf T}X/442$ and $\mathrm{Err}_X = \sigma^2(1 + \operatorname{tr}(\Sigma M^{-1})) = \sigma^2(1 + p/n)$ with $1 + p/n = 1.0249$, so $\mathrm{Err}_X = 3{,}005.7$, the same for every simulated data set. For 30 seeds of 1,000 data sets each, the correlation between the ten-fold estimate and $\mathrm{Err}_{\mathcal{T}}$ had median −0.004 (interquartile range −0.026 to 0.015), and that between leave-one-out and $\mathrm{Err}_{\mathcal{T}}$ −0.005 (−0.030 to 0.014), as Theorem 4 requires. The conditional error varied little: its standard deviation was 30.9 in the simulation, against an exact value of 31.1 ($\mathrm{Err}_{\mathcal{T}} - \sigma^2$ is a quadratic form in normal variables). Leave-one-out varied much more, with a standard deviation of 205.4 around a mean of 3,005.6, close to $\mathrm{Err}_X$. The estimate is noisy, and its noise has nothing to do with how good the fitted model is.
Simulation: what the estimates track
Theorem 4 needs normal errors and fixed inputs. The NHANES experiment of Theorem 3 has neither: the inputs vary from set to set and the pressures are skewed. The table summarizes, as medians over the 30 seeds of quantities computed over each seed's 400 training sets: the mean and standard deviation of the estimate, its correlation with the conditional error, the mean of the naive standard error (the standard deviation of the $n$ held-out squared errors divided by $\sqrt n$, Bates et al.'s $\widehat{\mathrm{se}}$; Cross-Validation uses the fold-level version, the standard deviation of the $K$ fold errors divided by $\sqrt K$, which the next section shows is too small by exactly the covariance between folds), and how often the naive 95% interval $\mathrm{CV}_K \pm 1.96\,\widehat{\mathrm{se}}$ covered $\mathrm{Err}_{\mathcal{T}}$ and $\mathrm{Err} = 314.71$.
| Estimate | Mean | SD | Correlation with $\mathrm{Err}_{\mathcal{T}}$ | Naive SE | Covers $\mathrm{Err}_{\mathcal{T}}$ | Covers $\mathrm{Err}$ |
|---|---|---|---|---|---|---|
| 2-fold | 328.34 | 73.91 | 0.063 | 61.29 | 0.884 | 0.888 |
| 5-fold | 317.89 | 66.60 | 0.078 | 60.12 | 0.885 | 0.890 |
| 10-fold | 316.07 | 65.44 | 0.067 | 59.87 | 0.889 | 0.890 |
| Leave-one-out | 314.78 | 64.71 | 0.070 | 59.62 | 0.889 | 0.889 |
Three observations, each about this experiment:
- Bias followed the learning curve, and variance fell with K. The means match Theorem 3. The standard deviation fell from 2 to 5 folds and only slightly after; leave-one-out was the least variable, as in the cubic simulation of Cross-Validation. With a stable fit such as a cubic, there was no sign of the high variance often attributed to leave-one-out.
- The estimates barely tracked the fitted model. The correlation with $\mathrm{Err}_{\mathcal{T}}$ was below 0.08 for every $K$. The conditional error itself varied with a standard deviation of only 10.44 across training sets, against about 65 for the estimates: most of what moves a cross-validation estimate is which adults happened to be held out and how far their pressures lay from any curve.
- The naive intervals undercovered. They covered $\mathrm{Err}_{\mathcal{T}}$ and $\mathrm{Err}$ about 89% of the time instead of 95%.
Why the naive standard error is too small
The naive standard error treats the $n$ held-out errors as independent. They are not: two observations in the same fold are predicted by the same fitted model, and an observation in one fold helped fit the models that predict every other fold. The theorem below gives the exact consequence under the natural symmetry (Bengio and Grandvalet, 2004, as Bates et al., 2024, §4.1, report it).
Theorem 5 (variance of K-fold cross-validation and the naive estimate). Let the folds have $m = n/K$ observations, and let the held-out errors have a common mean, common variance $a_1$, covariance $a_2$ for two observations in the same fold and $a_3$ for two in different folds (which holds, by symmetry, for independent draws, any fixed assignment to folds of equal size, and a fitting rule that does not depend on the order of its training data). Then $$V = \operatorname{Var}(\mathrm{CV}_K) = \frac{a_1}{n} + \frac{m - 1}{n}a_2 + \frac{n - m}{n}a_3,$$ and the observation-level naive variance estimate $\widehat{\mathrm{se}}^2 = \frac{1}{n(n - 1)}\sum_i(e_i - \bar e)^2$ (the one in the simulation table; the theorem says nothing directly about the fold-level version) has expectation $$E\big[\widehat{\mathrm{se}}^2\big] = \frac{a_1 - V}{n - 1}.$$ In particular $E[\widehat{\mathrm{se}}^2] < V$ exactly when $(m - 1)a_2 + (n - m)a_3 > 0$, that is, whenever the errors are positively correlated on balance.
Proof. $\operatorname{Var}(\bar e) = n^{-2}\sum_{i,j}\operatorname{Cov}(e_i, e_j)$. Each $i$ contributes $a_1$ once, $a_2$ for the $m - 1$ others in its fold and $a_3$ for the $n - m$ outside it; summing over $i$ and dividing by $n^2$ gives $V$. For the naive estimate, the means are equal, so $E(e_i - \bar e)^2 = \operatorname{Var}(e_i - \bar e) = a_1 - 2\operatorname{Cov}(e_i, \bar e) + V$, and $\sum_i\operatorname{Cov}(e_i, \bar e) = \operatorname{Cov}(n\bar e, \bar e) = nV$. Hence $E\sum_i(e_i - \bar e)^2 = na_1 - 2nV + nV = n(a_1 - V)$, and dividing by $n(n - 1)$ gives the formula. Finally $(a_1 - V)/(n - 1) < V$ iff $a_1 < nV$ iff $(m - 1)a_2 + (n - m)a_3 > 0$. $\square$
The fold-level version. Let $F_k$ be the mean held-out error of fold $k$, so that $\mathrm{CV}_K$ is the average of the $F_k$. By the same covariance model, $\operatorname{Var}F_k = a_1/m + (m - 1)a_2/m$ and $\operatorname{Cov}(F_k, F_l) = a_3$ for $k \ne l$, so $V = \operatorname{Var}F_k/K + (K - 1)a_3/K$, which agrees with the formula above. The sample variance $s_F^2$ of the $K$ fold means has expectation $\operatorname{Var}F_k - a_3$, by the argument of the proof applied to $K$ equally correlated variables, so the fold-level estimate $s_F^2/K$ has $E[s_F^2/K] = V - a_3$: it is too small by exactly the covariance between folds, whenever $a_3 > 0$.
The naive estimate does not even estimate $a_1/n$, the variance it would have under independence; it is pulled below that by the same covariances that push $V$ above it. Bengio and Grandvalet (2004) prove that no estimator of $V$ from a single run of K-fold cross-validation is unbiased for all distributions (as Bates et al. report), so the covariances cannot be repaired from one run; Bates et al. propose a nested cross-validation estimate of the mean squared error instead.
Example (the NHANES cubics). For ten-fold cross-validation with $n = 100$, the covariances were estimated from each seed's 400 training sets. The median over seeds of $a_1$ was 405,113 (in mm Hg$^4$; squared errors of pressures are heavy-tailed). The split of the covariance between $a_2$ and $a_3$ is not well determined: their medians over seeds were 11 and 261, with interquartile ranges from −873 to 1,527 and from 72 to 494, and pooling all 12,000 training sets gives 221 and 236. The data do not distinguish the two. What they do determine is the total. Plugged into Theorem 5, the medians give $\sqrt V = 65.47$ against an observed standard deviation of 65.44; that agreement holds by construction (the components are a decomposition of the same sample covariance matrix), so it is a decomposition of the observed variance, not a test of the theorem. The theorem's content is the second formula: $\sqrt{E[\widehat{\mathrm{se}}^2]} = 63.63$, against $\sqrt{a_1/n} = 63.65$, and the ratio $V/E[\widehat{\mathrm{se}}^2]$ is 1.06. In this experiment the covariances made the naive variance about 6% too small, not enough by themselves to explain coverage of 89%.
The rest came from the variability of $\widehat{\mathrm{se}}$ itself. Its coefficient of variation across training sets was 0.37 (median over seeds, ten folds). An interval with a random half-width $W$ covers less often than one with the fixed half-width $E[W]$ when $W$ is independent of an estimate $X$ that is symmetric and unimodal about the target: the coverage $g(w) = P(\lvert X - \text{target}\rvert \le w)$ is then concave in $w > 0$, because the density falls away from the centre, so Jensen's inequality (Probability Inequalities) gives $E[g(W)] \le g(E[W])$. The estimate here is skewed and its standard error is not independent of it, so this is a guide, not a proof; but in the experiment an interval of fixed half-width $1.96$ times the root mean square of $\widehat{\mathrm{se}}$ covered 0.946 (median over seeds, ten folds), against 0.890 with the random $\widehat{\mathrm{se}}$. Here the 2.5% and 97.5% points of $(\mathrm{CV}_{10} - \mathrm{Err})/\widehat{\mathrm{se}}$, over all 12,000 training sets, were −3.38 and 1.58, not ±1.96. Three checks in the script isolate this:
- Skewness alone does not explain it. The estimates were skewed (median skewness 0.57 for ten folds), yet an interval using the true standard deviation of the estimate in place of $\widehat{\mathrm{se}}$ covered $\mathrm{Err}$ in 0.951 of the training sets for ten folds and 0.954 for leave-one-out.
- The misses were one-sided. The naive standard error rose and fell with the estimate (correlation 0.816 across training sets for ten folds): a training set with a few adults of very high pressure produced both a large estimate and a large standard error, and one without them produced both small. The truth lay above the interval in 0.105 of training sets and below it in 0.005 (medians over seeds).
- The coupling did not cause the misses. Pairing each estimate with a standard error randomly reassigned among the training sets, which breaks the coupling and keeps the noise, gave coverage 0.883, no better than the actual 0.890. The coupling decided on which side the misses fell, not how many there were.
So in this experiment the covariances that Bates et al. emphasize cost a little (with the fixed half-width at the naive root mean square, coverage was 0.946 rather than the 0.951 of the true standard deviation), and the noise of the standard error cost more (from 0.946 to 0.890). Their relative sizes in other settings are not something one experiment can establish.
Cross-validation as a model selector
Back to the opening: leave-one-out chose the quintic, as AIC did, and BIC chose the line (The Bayesian Information Criterion and the Laplace Approximation). That agreement with AIC is a theorem. Stone (1977) proved, for a logarithmic assessment of predictive densities and maximum likelihood fitting within each model, an asymptotic equivalence between choosing a model by cross-validation and by Akaike's criterion. For linear models, Shao (1997) places leave-one-out, GCV, AIC and $C_p$ in one class (his Class 1): asymptotically efficient when no correct model of fixed dimension exists, and not consistent when more than one candidate of fixed dimension is correct (under his conditions, which for leave-one-out include leverages tending to 0). Shao (1993), as Shao (1997) reports, showed for a fixed set of candidate regressions (his Example 1) that leave-one-out is inconsistent and that leave-$d$-out is consistent provided $d/n \to 1$. Shao's leave-$d$-out averages over many subsets of size $d$ rather than over $K$ disjoint folds, and he shows (1997, eq. 4.5) that it behaves like the criterion $\mathrm{RSS} + \lambda_n\hat\sigma^2p$ with $\lambda_n = n/(n - d) + 1$. For his scheme, holding out a fixed fraction $d/n = 1/K$ gives $\lambda = K/(K - 1) + 1$, a fixed penalty between 2 and BIC's growing $\ln n$: about 2.11 for $K = 10$ and 3 for $K = 2$, his Class 3. So the fraction held out is a choice of penalty. The cross-validations of the opening table, with small $d/n$, behave like AIC.
The table also says how much the choice matters. The quintic beats the line by 0.81 in leave-one-out error, about a quarter of a percent, and the naive standard error is ten times that. Choosing among nearly equal models is not the same as estimating their error, and the error of the chosen one is estimated honestly only by nested cross-validation or a separate test set.
What is proved here, what is cited, and what the experiment shows
Proved on this page: the exact condition for the leave-one-out shortcut (Lemma 1); that self-stable linear smoothers satisfy it (Theorem 1) and that penalized least squares is self-stable (Lemma 2), giving least squares (PRESS), ridge and penalized splines with $0 \le S_{ii} \le 1$ (Corollary 1); that kernel smoothers satisfy the condition and nearest neighbors does not; GCV as a rotation-invariant weighted PRESS (Proposition 1); the Golub–Heath–Wahba identity and bound for $E[\mathrm{GCV}]$ (Theorem 2); the expectation of K-fold cross-validation (Theorem 3); linear invariance and the conditional independence of cross-validation and $\mathrm{Err}_{\mathcal{T}}$ in the normal linear model, with the mean squared error decomposition (Lemma 3, Theorem 4); the variance of K-fold cross-validation and the expectation of the naive variance estimate (Theorem 5).
Taken from other pages: the deletion identities and the matrix determinant argument (Leverage, Influence and Residual Diagnostics, Ridge and Lasso Regression); the mean of a quadratic form (Covariance Matrices and Quadratic Forms); independence of uncorrelated jointly normal vectors (The Multivariate Normal Distribution); degrees of freedom and optimism (Optimism and Effective Degrees of Freedom).
Cited: Bates, Hastie and Tibshirani's Theorem 2 and their nested cross-validation; Bengio and Grandvalet's impossibility result, as Bates et al. report it; Golub, Heath and Wahba's derivation of GCV by rotation and their results on its minimizer; Stone's (1977) equivalence, at the strength of its abstract; Shao's (1997) classification and his report of Shao (1993).
Computed: every number on the page, by tools/experiments/statistics/cross-validation-theory.py, with seeds stated. The simulations describe these experiments only; the size of the undercoverage and its causes in particular depend on the data and the method.
Worked problems
These problems are posed for this article, on small exact cases and on its simulation. Every number is recomputed by the article's script, the first two in exact rational arithmetic.
Problem 1 (PRESS and GCV by hand). Fit a line by least squares to the four points $(0, 1)$, $(1, 3)$, $(2, 2)$, $(3, 6)$. Compute the leverages, the leave-one-out residuals, PRESS, leave-one-out cross-validation and GCV.
Solution. With $\bar x = 1.5$, $\sum(x_i - \bar x)^2 = 5$ and $\bar y = 3$, the slope is $\sum(x_i - \bar x)(y_i - \bar y)/5 = 7/5 = 1.40$ and the intercept $3 - 1.4 \times 1.5 = 0.90$. The leverages of a line are $h_{ii} = 1/n + (x_i - \bar x)^2/\sum(x_j - \bar x)^2$: 0.70, 0.30, 0.30, 0.70, summing to 2. The fitted values are 0.9, 2.3, 3.7, 5.1, so the residuals are 0.10, 0.70, −1.70, 0.90 and $\mathrm{RSS} = 4.20$. Dividing each residual by $1 - h_{ii}$ (Corollary 1) gives the leave-one-out residuals $0.1/0.3 = 0.3333$, $0.7/0.7 = 1.0000$, $-1.7/0.7 = -2.4286$ and $0.9/0.3 = 3.0000$; the script confirms each against a line fitted to the other three points. PRESS is the sum of their squares, $7{,}060/441 = 16.0091$, and leave-one-out cross-validation is $16.0091/4 = 4.0023$. For GCV, $\mu_1 = 2/4$, so $\mathrm{GCV} = (4.20/4)/(1 - 1/2)^2 = 4.20$. GCV exceeds leave-one-out here because the largest ordinary residual, −1.7, sits at a middle point of low leverage. Proposition 1 up-weights the middle points' squared leave-one-out residuals by $(0.7/0.5)^2 = 1.96$ and down-weights the end points' by $w = (0.3/0.5)^2 = 0.36$; the middle point at $x = 2$ alone contributes $1.96 \times (17/7)^2 = 11.56$ of the weighted sum 16.80, which divided by 4 is GCV.
Problem 2 (a kernel smoother left one out). Three points have outcomes 2, 4, 9, and the kernel weights from the middle point to the three points are $\tfrac12, 1, \tfrac12$. Find the Nadaraya–Watson fit at the middle point, its leave-one-out prediction directly, and check the shortcut.
Solution. The weights sum to 2, so $S_{22} = 1/2 = 0.50$ and the fit is $(\tfrac12 \cdot 2 + 1 \cdot 4 + \tfrac12 \cdot 9)/2 = 9.5/2 = 4.75$. Left out, the middle point is predicted by the other two with weights $\tfrac12, \tfrac12$: $(1 + 4.5)/1 = 5.50$, so the leave-one-out residual is $4 - 5.5 = -1.50$. The shortcut gives $(4 - 4.75)/(1 - 0.5) = -1.50$, as the Example after Corollary 1 guarantees.
Problem 3 (how short is the naive standard error?). In the NHANES experiment with $n = 100$ and $K = 10$, the held-out squared errors had variance $a_1 = 405{,}113$ and ten-fold cross-validation had variance $V = 4{,}282.7$ (standard deviation 65.44). Using Theorem 5, find the total covariance $(m - 1)a_2 + (n - m)a_3$, the root of the naive variance estimate's expectation, and the ratio $V/E[\widehat{\mathrm{se}}^2]$.
Solution. By the first formula of Theorem 5, $nV = a_1 + (m - 1)a_2 + (n - m)a_3$, so the total covariance is $428{,}270 - 405{,}113 = 23{,}157$, compared with $a_1/n = 4{,}051.1$ for the independent part of $V$. The naive estimate has expectation $(a_1 - V)/(n - 1) = (405{,}113 - 4{,}282.7)/99$, whose square root is 63.63, and the ratio $V/E[\widehat{\mathrm{se}}^2]$ is 1.06. The total covariance is positive, as Theorem 5's condition for underestimation requires. How it splits between the 9 within-fold partners and the 90 others of each observation is not determined by this experiment (see the Example after Theorem 5).
Summary
| Result | Statement |
|---|---|
| Shortcut condition (Lemma 1) | $y_i - \hat y_{(-i)} = (y_i - \hat y_i)/(1 - S_{ii})$ iff $\hat y_{(-i)} = \sum_{j \ne i}S_{ij}y_j/(1 - S_{ii})$ |
| Where it holds | quadratically penalized least squares (least squares, PRESS; ridge; penalized splines), kernel smoothers; not $k$-nearest neighbors |
| GCV | $\frac1n\lVert(I - S)\mathbf{y}\rVert^2/(1 - \operatorname{tr}S/n)^2$; $\lvert E\,\mathrm{GCV} - (\sigma^2 + R)\rvert/R \le (2\mu_1 + \mu_1^2/\mu_2)/(1 - \mu_1)^2$ |
| What K-fold estimates | $E[\mathrm{CV}_K] = \mathrm{Err}(n - n/K)$ |
| Normal linear model | $\mathrm{CV}_K$ independent of $\mathrm{Err}_{\mathcal{T}}$ given $X$ |
| Variance | $V = a_1/n + (m - 1)a_2/n + (n - m)a_3/n$; $E[\widehat{\mathrm{se}}^2] = (a_1 - V)/(n - 1)$ |
| As a selector | leave-one-out and GCV in AIC's class; leave-$d$-out with $d/n \to 1$ consistent (Shao, 1997) |
What we have learned
Cross-validation estimates a property of a fitting procedure, not of a fitted model. Its expectation is exactly the expected error of the procedure applied to $n(1 - 1/K)$ points; in the normal linear model it is independent of the error of the model actually fitted; and in the NHANES experiment its correlation with that error was below 0.08. For linear smoothers that minimize a penalized sum of squares, leave-one-out costs one fit, because adding a point that lies on the curve does not move the curve, and GCV replaces the leverages by their average to estimate the expected in-sample error within a relative error set by the trace. The estimate's variance includes covariances that its naive standard error ignores. In the experiment the naive intervals undercovered, a little because of those covariances and mostly because the standard error is itself noisy, and the misses fell almost all on one side because the estimate and its standard error moved together.
As a model selector, leave-one-out behaves like AIC, efficient but not consistent, and the fraction held out acts as a penalty. The topic page, Prediction Error and Model Choice, sets these results beside optimism, AIC and BIC.
References
- Allen, D. M. (1974). The relationship between variable selection and data agumentation [sic] and a method for prediction. Technometrics, 16(1), 125–127. https://doi.org/10.1080/00401706.1974.10489157 record
- Bates, S., Hastie, T., and Tibshirani, R. (2024). Cross-validation: what does it estimate and how well does it do it? Journal of the American Statistical Association, 119(546), 1434–1445. https://doi.org/10.1080/01621459.2023.2197686 (published online 2023; preprint arXiv:2104.00673). record · 2 pages
- Bengio, Y., and Grandvalet, Y. (2004). No unbiased estimator of the variance of K-fold cross-validation. Journal of Machine Learning Research, 5, 1089–1105. Cited as Bates et al. (2024) report it. record · 2 pages
- Craven, P., and Wahba, G. (1979). Smoothing noisy data with spline functions: estimating the correct degree of smoothing by the method of generalized cross-validation. Numerische Mathematik, 31(4), 377–403 (issue dated December 1978; commonly cited as 1979). https://doi.org/10.1007/BF01404567 record
- Efron, B., Hastie, T., Johnstone, I., and Tibshirani, R. (2004). Least angle regression. The Annals of Statistics, 32(2), 407–499. https://doi.org/10.1214/009053604000000067 record · 18 pages
- Golub, G. H., Heath, M., and Wahba, G. (1979). Generalized cross-validation as a method for choosing a good ridge parameter. Technometrics, 21(2), 215–223. https://doi.org/10.1080/00401706.1979.10489751 record · 2 pages
- Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. §7.10 and Exercise 7.3. record · 31 pages
- National Center for Health Statistics (2020). National Health and Nutrition Examination Survey 2017–2018: Demographic Variables and Sample Weights (DEMO_J), Blood Pressure (BPX_J) and Body Measures (BMX_J) data files. Centers for Disease Control and Prevention. https://wwwn.cdc.gov/nchs/nhanes/continuousnhanes/default.aspx?BeginYear=2017 record · 95 pages
- Shao, J. (1993). Linear model selection by cross-validation. Journal of the American Statistical Association, 88(422), 486–494. https://doi.org/10.1080/01621459.1993.10476299 Cited as Shao (1997) reports it. record
- Shao, J. (1997). An asymptotic theory for linear model selection. Statistica Sinica, 7(2), 221–264. record · 2 pages
- Stone, M. (1977). An asymptotic equivalence of choice of model by cross-validation and Akaike's criterion. Journal of the Royal Statistical Society, Series B, 39(1), 44–47. https://doi.org/10.1111/j.2517-6161.1977.tb01603.x record