Leave-One-Out Cross-Validation and Stability

Why Leave-One-Out Error Has a Different Risk Target

Leave-one-out cross-validation (LOOCV) fits a procedure repeatedly: each fit omits one observation, and that fit is evaluated on the omitted observation. The resulting average is often used to assess a procedure trained on all $n$ observations. That interpretation needs care. Each prediction in LOOCV comes from a fit trained on only $n-1$ observations, so its expected risk target is generally the risk of the procedure at sample size $n-1$, not $n$.

Stability makes this distinction quantifiable. If deleting one observation changes the prediction loss only slightly, then the risks at sample sizes $n-1$ and $n$ are close. We will also separate this expected-risk comparison from a stronger-looking claim that is not generally true: a realized LOOCV score need not be close to the conditional population risk of the full-sample fit.

Definition of Leave-One-Out Cross-Validation

Let $Z_i=(X_i,Y_i)$, $i=1,\ldots,n$, be independent and identically distributed observations from a distribution $P$. A learning rule $A_m$ takes a training sample of size $m$ and returns a predictor. Write $S_n=(Z_1,\ldots,Z_n)$, and let $S_n^{-i}$ denote the sample with observation $i$ deleted. Let $L(f,z)$ be the loss when predictor $f$ is evaluated at observation $z$. Assume the learning rules and loss are measurable, so the expectations below are defined. For simplicity, assume $0\leq L(f,z)\leq 1$; the risk comparisons also hold for integrable losses when the stability bound is finite.

Definition: The leave-one-out cross-validation error is $$ \widehat R_{\mathrm{LOO}}(S_n) = \frac{1}{n}\sum_{i=1}^n L\bigl(A_{n-1}(S_n^{-i}),Z_i\bigr). $$ For a fixed fitted predictor $f$, its population risk is $R(f)=E_{Z\sim P}[L(f,Z)]$, where the test observation $Z$ is independent of the training data. The conditional risk of the full-sample fit is the random quantity $R(A_n(S_n))$.

These are different quantities. The LOOCV score is a random average of losses on the observed sample. The conditional risk $R(A_n(S_n))$ averages over a fresh test observation while holding the observed training sample fixed. The unconditional expected risk at sample size $m$ is

\mathcal R_m = E_{S_m}\bigl[R(A_m(S_m))\bigr].

This tutorial compares expected risks across sample sizes. It does not identify a realized LOOCV score with a conditional risk for a particular observed sample.

The Expected-Risk Identity

Theorem: Under the independent, identically distributed sampling assumption and the measurability and integrability conditions above, $$ E\bigl[\widehat R_{\mathrm{LOO}}(S_n)\bigr]=\mathcal R_{n-1}. $$ Thus LOOCV is unbiased, in expectation, for the risk of the learning rule trained on $n-1$ observations.

Proof. By linearity of expectation, it is enough to compute the expectation of one term. For each $i$, the deleted sample $S_n^{-i}$ contains $n-1$ observations and is independent of $Z_i$. Its distribution is the same as that of $S_{n-1}$. Therefore, averaging first over the independent test observation $Z_i$, and then over the deleted training sample, gives

E\bigl[L(A_{n-1}(S_n^{-i}),Z_i)\bigr] = E_{S_{n-1}}\left[ E_{Z\sim P}\bigl[L(A_{n-1}(S_{n-1}),Z)\mid S_{n-1}\bigr] \right] = \mathcal R_{n-1}.

Every term in the average has this same expectation. Taking their average proves the identity. $\square$

Worked Example: The Sample Mean with Bernoulli Responses

Suppose $Y_i\sim\operatorname{Bernoulli}(p)$, predictors are constant, the fitted constant is the training-sample mean, and the loss is squared error. Compute the expected risk of the fit trained on $m$ observations.

Write $\bar Y_m$ for that sample mean, and let $Y\sim\operatorname{Bernoulli}(p)$ be an independent test response. The test risk conditional on the training data is

E[(Y-\bar Y_m)^2\mid S_m] = \operatorname{Var}(Y)+(E[Y]-\bar Y_m)^2 = p(1-p)+(\bar Y_m-p)^2.

Since $E[\bar Y_m]=p$ and $\operatorname{Var}(\bar Y_m)=p(1-p)/m$, taking expectation over the training sample yields

\mathcal R_m = p(1-p)+E[(\bar Y_m-p)^2] = p(1-p)\left(1+\frac{1}{m}\right).

The theorem therefore gives $E[\widehat R_{\mathrm{LOO}}]=p(1-p)(1+1/(n-1))$. This is the expected risk of a fit trained on $n-1$ observations. The full-sample fit has expected risk $p(1-p)(1+1/n)$, which is generally smaller. Their difference is

\mathcal R_{n-1}-\mathcal R_n = p(1-p)\left(\frac{1}{n-1}-\frac{1}{n}\right) = \frac{p(1-p)}{n(n-1)}.

For example, with $p=1/4$ and $n=4$, $p(1-p)=3/16$. Thus $\mathcal R_3=(3/16)(4/3)=1/4$, while $\mathcal R_4=(3/16)(5/4)=15/64$. The expected LOOCV error is $1/4$, exceeding the expected full-sample risk by $1/64$.

Deletion Stability and a Risk Bound

To control the difference between the two sample-size targets, use a stability condition that directly compares a fit before and after one observation is deleted. The condition is uniform over both the training sample and the point at which loss is evaluated. It is a cross-size condition: the two fitted predictors come from learning rules with different training sample sizes.

Definition: The learning rules have uniform deletion stability $\delta_n$ if, for every sample $s=(z_1,\ldots,z_n)$ and every $i$, $$ \sup_z \left| L(A_n(s),z)-L(A_{n-1}(s^{-i}),z) \right| \leq \delta_n. $$

Theorem: Under the assumptions of the expected-risk identity, if the learning rules have uniform deletion stability $\delta_n$, then $$ \left|\mathcal R_n-\mathcal R_{n-1}\right|\leq\delta_n, \qquad \left|E[\widehat R_{\mathrm{LOO}}]-\mathcal R_n\right|\leq\delta_n. $$

Proof. Take a sample $S_n$ and an independent test observation $Z\sim P$. For each $i$, deletion stability holds at every test point, and hence at this $Z$:

\left| L(A_n(S_n),Z)-L(A_{n-1}(S_n^{-i}),Z) \right| \leq \delta_n.

Take expectations over $S_n$ and $Z$. The expectation of the first loss is $\mathcal R_n$. The deleted sample has the distribution of an independent size-$(n-1)$ training sample, independent of $Z$, so the expectation of the second loss is $\mathcal R_{n-1}$. Applying $|E[W]|\leq E[|W|]$ gives $|\mathcal R_n-\mathcal R_{n-1}|\leq\delta_n$. The expected-risk identity then gives $E[\widehat R_{\mathrm{LOO}}]=\mathcal R_{n-1}$, proving the second inequality as well. $\square$

The same stability condition also provides a sample-wise comparison with the full fit’s empirical training error. Define that error as $n^{-1}\sum_{i=1}^n L(A_n(S_n),Z_i)$. Applying deletion stability at $z=Z_i$ to each summand and using the triangle inequality gives

\left| \widehat R_{\mathrm{LOO}}(S_n) - \frac{1}{n}\sum_{i=1}^n L(A_n(S_n),Z_i) \right| \leq \frac{1}{n}\sum_{i=1}^n\delta_n = \delta_n.

This comparison is between two empirical quantities evaluated on the observed data. It does not, by itself, bound the realized difference between LOOCV and the conditional population risk $R(A_n(S_n))$.

Worked Example: Verifying the Stability Bound for the Sample Mean

Let the responses lie in $[0,1]$, let $A_m$ predict the sample mean, and use squared-error loss $L(a,y)=(a-y)^2$. This loss lies in $[0,1]$. For a sample of size $n$, write $a$ for its full-sample mean and $b$ for the mean after deleting observation $i$. If the deleted response is $y_i$, then

a=\frac{(n-1)b+y_i}{n}, \qquad |a-b|=\frac{|y_i-b|}{n}\leq\frac{1}{n},

because both $y_i$ and $b$ lie in $[0,1]$. For any test response $y\in[0,1]$, factor the difference of squared losses:

\left|(a-y)^2-(b-y)^2\right| = |a-b|\,|a+b-2y|.

Here $a,b,y\in[0,1]$, so $a+b\in[0,2]$ and $2y\in[0,2]$. Consequently $|a+b-2y|\leq 2$, and therefore

\left|(a-y)^2-(b-y)^2\right| \leq \frac{1}{n}\cdot 2 = \frac{2}{n}.

Thus $\delta_n=2/n$ is a valid uniform deletion-stability bound, and the discrepancy between expected LOOCV error and expected full-sample risk is at most $2/n$.

The factor $2$ matters. For $n=2$, let the deleted response be $0$, the remaining response be $1$, and the test response be $0$. Then $a=1/2$, $b=1$, and the absolute loss difference is $|(1/2)^2-1^2|=3/4$. A bound of $1/n=1/2$ would fail, while $2/n=1$ is valid.

What Stability Does—and Does Not—Guarantee

A small deletion-stability bound guarantees that the expected LOOCV target and the expected risk of the full-sample fit are close. It also controls, sample by sample, the difference between LOOCV and the full fit’s empirical training error. Neither statement says that every realized LOOCV score is close to the full fit’s conditional population risk. Such a conclusion would require control of the random variation in the validation score as well as the stability comparison.

Worked Example: A Realized LOOCV Score Can Differ Sharply

Let $n=2$, let $Y_1,Y_2$ be Bernoulli with $p=1/2$, and consider the sample realization $(Y_1,Y_2)=(0,1)$. Fit the sample mean and use squared error. Deleting the first observation leaves the prediction $1$, which incurs loss $(1-0)^2=1$ on the omitted response. Deleting the second leaves the prediction $0$, which incurs loss $(0-1)^2=1$. Hence

\widehat R_{\mathrm{LOO}}=\frac{1+1}{2}=1.

The full-sample prediction is $1/2$. Its conditional population risk, given this observed sample, is

R(A_2(S_2)) = E[(Y-1/2)^2] = \frac{1}{2}(0-1/2)^2+\frac{1}{2}(1-1/2)^2 = \frac{1}{4}.

The realized difference is $3/4$. The bound $2/n=1$ from the preceding example is not contradicted: it compares each delete-one loss with the full predictor’s loss at the same observed response, and its risk conclusion concerns expectations. This example shows why an expected-risk guarantee should not be read as a deterministic guarantee about a particular sample.

Worked Example: A Learner with No Deletion Stability

Consider a rule for binary responses that predicts the constant $1$ if the training-sample mean is at least $1/2$, and predicts $0$ otherwise. Use zero-one loss. With the sample $(0,1)$, the full-sample mean is $1/2$, so the full fit predicts $1$. Deleting the observation $1$ leaves a sample mean of $0$, so that deleted fit predicts $0$. At test response $y=0$, the full fit incurs loss $1$ and the deleted fit incurs loss $0$. Their loss difference is $1$.

Since zero-one loss is bounded between $0$ and $1$, no uniform deletion-stability bound smaller than $1$ can hold for this rule. The example does not imply that LOOCV is always inaccurate for this learner; it shows that the stability argument gives no nontrivial guarantee in this case. A small stability bound is a sufficient way to control the risk discrepancy, not a condition required for LOOCV to be useful in every particular problem.

Common Mistake

A frequent error is to conclude that LOOCV directly estimates the risk of the full-sample fit because every observation is used once for evaluation. Each evaluation is indeed made on an observation excluded from its own fit. But that fit was trained on $n-1$ observations, and the expected-risk identity therefore targets $\mathcal R_{n-1}$. The conclusion that it also targets $\mathcal R_n$ needs a further argument, such as a bound on deletion stability.

Another tempting shortcut is to bound the squared-loss difference for two predictors in $[0,1]$ by $1/n$ solely because their predictions differ by at most $1/n$. The factorization $(a-y)^2-(b-y)^2=(a-b)(a+b-2y)$ shows why that shortcut is incomplete: the second factor can have absolute value $2$, not $1$. For the sample mean with responses in $[0,1]$, the valid bound is $2/n$.

Key takeaway: LOOCV has expected risk target $\mathcal R_{n-1}$. Uniform deletion stability $\delta_n$ bounds its expected discrepancy from $\mathcal R_n$ by $\delta_n$. Keep that expectation-level conclusion distinct from claims about a particular realized score or conditional risk.

Check Your Understanding

Use the definitions and results above to answer the following questions.

Why is the expected risk target of LOOCV $\mathcal R_{n-1}$, rather than $\mathcal R_n$? State the independence fact used in the argument.
If a learning rule has uniform deletion stability $\delta_n=0.03$, what bound follows for the absolute difference between expected LOOCV error and expected full-sample risk?
For the sample-mean predictor with squared loss on responses in $[0,1]$, explain why the factor $|a+b-2y|$ is bounded by $2$, and not necessarily by $1$.
What two quantities are compared by the sample-wise stability inequality, and why does that inequality not directly compare LOOCV with conditional population risk?
In the Bernoulli sample-mean example, compute the expected risk difference between sample sizes $n-1$ and $n$ in terms of $p$ and $n$.