Why the Training-Sample Size Matters
A cross-validation score is often described as an estimate of “prediction error.” That description is incomplete unless it specifies which fitted procedure is being assessed. A model evaluated on observations held out from its own training set was trained on fewer than all the available observations. Consequently, the natural risk target depends on the size of each fold’s training set, as well as on the randomness in the data used to train the procedure.
This tutorial makes that target precise. The central calculation is an expectation identity: under independent and identically distributed sampling, and when fold assignment does not depend on the observed data, the expected cross-validation score equals the prediction risk of the learning procedure trained on the corresponding fold-complement sample size. This is an identity about the target of the average; it does not assert that one realized score equals that risk, or that the score estimates the risk of the final model trained on all \(n\) observations.
Definition and Risk Target
Let \(Z_1,\ldots,Z_n\) be independent observations from a distribution \(P\). An observation \(Z_i\) may include both predictors and a response. Let \(\ell(g,z)\) be a prediction loss for predictor \(g\) evaluated at observation \(z\). Assume the expected losses under discussion are finite.
A learning procedure \(\mathcal A_m\) takes \(m\) training observations and returns a predictor. It may also use randomization, such as a random initialization; if so, that randomization is part of the procedure and is independent of the data. Define its unconditional prediction risk at sample size \(m\) by
where \(Z_1,\ldots,Z_m,Z_{m+1}\) are iid from \(P\), and the expectation also averages over any randomness used by \(\mathcal A_m\). Thus \(\mathcal R_m\) averages over both the training sample and a fresh test observation. It is not the risk conditional on one particular realized training sample.
For a fixed partition, let \(\hat g_{-k}=\mathcal A_{m_k}((Z_i)_{i\in I_{-k}})\). The pooled K-fold cross-validation estimate is
Each observation is scored once, using a predictor trained without the fold containing that observation. If folds have equal sizes, this pooled average is also the simple average of the \(K\) fold-specific mean losses. With unequal sizes, those two ways of averaging need not agree.
Worked Example: Reading the Training Size From the Fold Design
Suppose \(n=12\) observations are divided into \(K=4\) equal folds. Each fold has \(n_k=12/4=3\) observations, so the training set for every fold has
\(m_k=n-n_k=12-3=9\) observations.
The four fold fits therefore each use nine observations, not twelve. The pooled score contains \(12\) losses, three from each fitted predictor. Under the assumptions used below, its expectation is \(\mathcal R_9\): the unconditional risk of this procedure trained on nine iid observations and evaluated on one fresh observation. It is not, solely by virtue of using all twelve observations for validation, an estimate with target \(\mathcal R_{12}\).
The Exact Expectation Identity
The proof needs only the marginal distribution of each validation loss. For \(i\in I_k\), the training observations indexed by \(I_{-k}\) are independent of \(Z_i\). They have the same joint distribution as \(m_k\) iid training observations, and \(Z_i\) has the distribution of an independent test observation. Therefore
This remains true if the fold-specific procedure uses independent randomization with the same law as \(\mathcal A_{m_k}\): averaging over that randomization gives the risk in the definition of \(\mathcal R_{m_k}\). By linearity of expectation,
The losses in this sum are generally dependent: different folds’ training sets overlap, and their fitted predictors can share many observations. Dependence does not invalidate this expectation calculation, which uses linearity rather than independence among the losses. It does matter for variability and other properties of the realized score; the identity above makes no claim about those.
Worked Example: Unequal Folds Produce a Weighted Risk Target
Let \(n=11\) and \(K=3\), with fold sizes \(4,4,3\). The corresponding training sizes are \(7,7,8\). The pooled cross-validation score weights each observation equally, so the theorem gives
\(E[\widehat R_{\mathrm{CV}}]=(4/11)\mathcal R_7+(4/11)\mathcal R_7+(3/11)\mathcal R_8=(8/11)\mathcal R_7+(3/11)\mathcal R_8.\)
For illustration, suppose \(\mathcal R_7=0.20\) and \(\mathcal R_8=0.16\). Then
\(E[\widehat R_{\mathrm{CV}}]=(8/11)(0.20)+(3/11)(0.16)=1.60/11+0.48/11=2.08/11\approx0.1891.\)
The unweighted average of the three fold means would instead have expectation \((2\mathcal R_7+\mathcal R_8)/3=(0.20+0.20+0.16)/3\approx0.1867\). It gives each fold equal weight, rather than each observation equal weight. The two targets differ because the fold sizes differ.
What Randomness Is Being Averaged?
The risk \(\mathcal R_m\) is unconditional: it averages over a new training sample of size \(m\), any procedure randomization, and an independent test observation. The cross-validation score itself is computed from one observed data set and one fold assignment. Its expectation identity says that, under the stated conditions, averaging over repeated iid data sets (and over any independent fold randomization) gives the stated risk target.
There is also a conditional risk for a fitted predictor. If \(D_m\) is a particular training sample and \(g=\mathcal A_m(D_m)\), its conditional prediction risk is
where \(Z\) is a fresh observation independent of the training data. Averaging this conditional risk over the training sample and procedure randomization recovers \(\mathcal R_m\). These are different quantities: a conditional risk refers to a particular fitted predictor, while an unconditional risk averages across the possible fits produced from samples of the specified size.
For a fixed fold \(k\), conditional on its training data and fitted predictor, the validation observations are independent draws from \(P\). Hence the expected fold mean, conditional on that fit, is \(R(\hat g_{-k})\). This statement concerns the fold’s own fitted predictor. It does not make the fold scores independent, nor does it turn them into conditional estimates of the risk of a separately refitted model.
Worked Example: A Bernoulli Mean Predictor
Let each response \(Y\) be Bernoulli with success probability \(1/2\), and use squared-error loss. The procedure trained on \(m\) responses predicts their sample mean \(\bar Y_m\). For an independent test response \(Y_{\mathrm{new}}\),
\(\mathcal R_m=E[(\bar Y_m-Y_{\mathrm{new}})^2].\)
Since \(E[\bar Y_m]=E[Y_{\mathrm{new}}]=1/2\), \(\operatorname{Var}(\bar Y_m)=\operatorname{Var}(Y)/m=1/(4m)\), and \(\operatorname{Var}(Y_{\mathrm{new}})=1/4\), independence gives
\(\mathcal R_m=\operatorname{Var}(\bar Y_m)+\operatorname{Var}(Y_{\mathrm{new}})=1/(4m)+1/4.\)
With \(n=10\) and \(K=5\) equal folds, each predictor uses \(m=8\) responses. Thus the expected cross-validation score is \(\mathcal R_8=1/32+1/4=9/32=0.28125\). The risk of this same procedure trained on all \(10\) responses is \(\mathcal R_{10}=1/40+1/4=11/40=0.275\). The difference is not a failure of the expectation identity: the two quantities refer to different training-sample sizes.
Assumptions and Common Pitfall
The simple identity depends on the held-out observation having the same distribution as a fresh test observation and being independent of the data used to fit its fold’s predictor. A fixed partition of iid observations satisfies this requirement. A random partition also satisfies it when the partition is chosen independently of the observed values, conditional on its fold sizes. If fold assignment uses observed outcomes or predictors, that independence argument need not apply; the resulting design requires its own analysis.
Common mistake: “Every observation is used for validation, so K-fold cross-validation estimates the risk of the final predictor trained on all \(n\) observations.” This reasoning confuses the number of observations scored with the number used to train each predictor. In each fold, the predictor excludes that fold’s \(n_k\) observations and is trained on \(m_k=n-n_k\). For equal folds, the exact unconditional target is \(\mathcal R_{n-n/K}\), not automatically \(\mathcal R_n\). The two risks may be close in a particular application, but that requires justification beyond the fold bookkeeping.
When fold sizes are unequal, another mistake is to call the pooled score the simple average of the \(K\) fold means. The pooled score weights a fold in proportion to its size; the simple average weights each fold equally. Check which quantity was computed before identifying its expectation target.
Check Your Understanding
For each question, identify the risk target or the condition needed for the standard calculation.
- With \(n=20\) and \(K=5\) equal folds, how many observations train each fold predictor, and what is the pooled score’s unconditional expectation?
- For fold sizes \(3,3,4\) when \(n=10\), write the expectation of the pooled cross-validation score in terms of \(\mathcal R_m\).
- Why does the expectation identity not require losses from different folds to be independent?
- In the Bernoulli example, calculate the risk for a predictor trained on \(m=5\) responses.
- What assumption about fold assignment is needed for a held-out observation to have the fresh-test-observation distribution independently of its fold’s fitted predictor?