The Leave-One-Out Generalization Identity

Why an Expected Generalization Gap Has a Leave-One-Out Representation

A model is evaluated on the same observations used to fit it when we calculate empirical training loss. Its population risk instead averages loss on a new observation, independent of the training data. The difference between these quantities is the generalization gap. Independence allows its expectation to be represented using held-out observations, but the precise identity depends on whether a held-out point is deleted or replaced.

This distinction matters. Replacing one training observation keeps the training sample size fixed; deleting one observation reduces it by one. The corresponding identities are both exact, but they concern algorithms trained on different sample sizes. Neither identity, by itself, says that a model's training loss estimates its risk accurately for a particular realized data set.

Setup and Definitions

Let \(Z_1,\ldots,Z_n\) be independent observations with common distribution \(P\), and write \(S=(Z_1,\ldots,Z_n)\). A deterministic learning algorithm \(A_n\) maps a sample of size \(n\) to a predictor or model. Let \(\ell(a,z)\) be the loss of model \(a\) on observation \(z\). For a fixed model \(a\), define its population risk as \(R(a)=E_{Z\sim P}[\ell(a,Z)]\), when this expectation exists. Its empirical training risk on \(S\) is \(\hat R_S(a)=n^{-1}\sum_{i=1}^n\ell(a,Z_i)\).

For the identities below, assume the data space and model space are measurable, the algorithm and loss are measurable, and the displayed losses have finite absolute expectations. In particular, these conditions permit writing population risk as an expectation over an independent observation and taking the expectations and finite sums below. We use a deterministic algorithm to keep the notation focused; an algorithm with independent randomization can be handled by including that randomization in the expectations.

The Fixed-Size Replacement Identity

Let \(Z_1',\ldots,Z_n'\) be independent observations from \(P\), also independent of \(S\). For each \(i\), define the replacement sample \(S^{(i)}=(Z_1,\ldots,Z_{i-1},Z_i',Z_{i+1},\ldots,Z_n)\). The point \(Z_i\) is held out for evaluation, while \(Z_i'\) takes its place in the training sample. Thus \(A_n(S^{(i)})\) is still trained on \(n\) observations.

Proof. Take an independent \(Z'\sim P\). By the definition of risk and independence of \(Z'\) and \(S\), \(E[R(A_n(S))]=E[\ell(A_n(S),Z')]\). For a fixed index \(i\), hold all coordinates of \(S\) other than \(Z_i\) fixed, but do not condition on the replacement observation \(Z_i'\). The pair \((Z_i,Z')\) has distribution \(P\otimes P\), as does \((Z_i',Z_i)\). The first coordinate of the first pair supplies the \(i\)th training entry and the second supplies the evaluation point. In the second pair, those roles are supplied by \(Z_i'\) and \(Z_i\). Consequently,

This equality is unconditional over the two independent draws and the other sample coordinates. It holds for every \(i\). Averaging these equalities over \(i\), and subtracting \(E[\hat R_S(A_n(S))]=n^{-1}\sum_i E[\ell(A_n(S),Z_i)]\), gives the identity. \(\square\)

The proof uses exchangeability of the relevant independent pairs, not a pointwise equality of losses. In general, the two losses inside a summand are dependent, and neither one must have the same value as the other on any particular data set.

The Conventional Delete-One Identity

In conventional leave-one-out cross-validation, observation \(Z_i\) is removed, rather than replaced. Write \(S_{-i}\) for the ordered sample of the other \(n-1\) observations, and let \(A_{n-1}\) be an algorithm trained on \(n-1\) observations. Define the leave-one-out prediction loss and the corresponding training loss by

The second quantity averages the training risk of each of the \(n\) models, each fitted after deleting one observation. It is not the empirical risk of one model trained on all \(n\) observations.

Proof. For each \(i\), \(Z_i\) is independent of \(S_{-i}\) and has distribution \(P\). Conditioning on \(S_{-i}\), then integrating over \(Z_i\), gives \(E[\ell(A_{n-1}(S_{-i}),Z_i)]=E[R(A_{n-1}(S_{-i}))]\). The sample \(S_{-i}\) has the distribution of \(T\), so each term has expectation \(E[R(A_{n-1}(T))]\).

For the training part, \(S_{-i}\) also has the distribution of \(T\), and its inner average is precisely the empirical risk of \(A_{n-1}(S_{-i})\) on that sample. Hence \(E[(n-1)^{-1}\sum_{j\ne i}\ell(A_{n-1}(S_{-i}),Z_j)]=E[\hat R_T(A_{n-1}(T))]\). Averaging the two equalities over \(i\) and subtracting proves the result. \(\square\)

This identity concerns the expected generalization gap at training size \(n-1\), not \(n\). The fixed-size replacement identity instead concerns \(A_n\), with a replacement observation still included in its training set. Comparing the two expected gaps requires additional information about how the algorithm behaves as its training size changes.

A Common Pitfall: Conditioning on the Replacement

A tempting but invalid proof conditions on the replacement value \(Z_i'\), treats it as fixed, and then tries to exchange \(Z_i\) with an independent test point. Once \(Z_i'\) is fixed, the replacement sample still contains that fixed value; exchanging \(Z_i\) with the test point does not turn the replacement sample into the original sample in the required way. The valid proof compares the joint distributions of \((Z_i,Z')\) and \((Z_i',Z_i)\) without fixing \(Z_i'\).

How to Use the Identities

These identities express an expected gap as a difference between two evaluation schemes. They do not require the algorithm to be an empirical risk minimizer, nor do they assume stability. Their role is to make the comparison exact; further assumptions are needed to bound the size of the difference. In particular, if changing one observation has little effect on the fitted model's loss, the replacement expression can help control the expected gap.

Keep the sample size and evaluation design explicit when applying the result:

• Fixed-size replacement: train on \(n\) observations, replacing \(Z_i\) by an independent draw, and evaluate on the omitted \(Z_i\). This gives the expected gap for \(A_n\).
• Delete-one cross-validation: train on the \(n-1\) observations excluding \(Z_i\), then evaluate on \(Z_i\). Comparing its prediction loss with the training loss of those deleted samples gives the expected gap for \(A_{n-1}\).

A frequent mistake is to call these two procedures interchangeable because each involves holding out one observation. They use different training sets and, generally, different fitted models. Another is to interpret an identity in expectation as a statement about each realized sample. The equalities proved here concern expectations under independent sampling; they do not assert equality of the corresponding random quantities for every data set.