Consistency of K-Fold Cross-Validation for Finite Procedures

Why Consistency Needs More Than Unbiasedness

K-fold cross-validation reuses observations: each observation is assessed once and belongs to the training set for the other folds. Consequently, fold scores are generally dependent. Their dependence does not by itself rule out consistency, but it does mean that a law of large numbers for independent fold scores cannot simply be invoked.

A second issue is the target. A fold trains on fewer observations than the full data set, and each fold has its own fitted model. We first define the risk target that matches those fitted models. We then give sufficient conditions under which cross-validation estimates this target consistently for a finite collection of procedures.

The training-set size in this definition is \(m=n(K-1)/K\). Thus \(T_{j,n}\) concerns the procedure trained on \(m\) observations, averaged over the \(K\) training sets. It is not automatically the risk of the same procedure trained on all \(n\) observations. If fold sizes differ by at most one, the definitions use weights \(|I_k|/n\) and the corresponding training sizes instead.

Unbiasedness for the Random Fold-Risk Target

Assume the folds are fixed in advance or are assigned independently of the observations. Conditional on \(D_{-k}\), each \(Z_i\) with \(i\in I_k\) remains an independent draw from \(F\). Therefore each held-out loss has conditional expectation equal to the risk of the rule fitted without that fold.

Proof. For any \(k\) and \(i\in I_k\), condition on the fold assignment and on \(D_{-k}\). The fitted rule \(A_j(D_{-k})\) is then fixed, while \(Z_i\) is independent of \(D_{-k}\) and has distribution \(F\). Hence

Summing over the \(n/K\) observations in each fold and dividing by \(n\) gives a conditional expectation of \(K^{-1}\sum_k R(A_j(D_{-k}))=T_{j,n}\). Taking expectations proves the proposition. The equality is an equality of expectations; it is not a sample-by-sample identity. \(\square\)

A Consistency Result for Finitely Many Procedures

Unbiasedness alone says nothing about whether the random difference between score and target becomes small. A convenient sufficient condition is that, in prediction loss, each fold-fitted rule approaches a fixed limiting rule. The condition below is deliberately explicit: it measures discrepancy on a fresh observation, averaged over the randomness in that fold’s training data.

Proof. For each \(j\), let \(P_n\ell(a_j)=n^{-1}\sum_{i=1}^n\ell(a_j,Z_i)\), the empirical average for the fixed rule. Define

The triangle inequality gives

For an observation \(Z_i\in I_k\), its fold-trained rule uses data outside \(I_k\), so \(Z_i\) is independent of that training data. Thus the expectation of each absolute difference in \(W_{j,n}\) is the discrepancy in the theorem’s assumption for fold \(k\). Because the folds have equal size,

Also, by the triangle inequality for integration,

Taking expectations shows \(E|T_{j,n}-R(a_j)|\to0\). Markov’s inequality therefore implies both \(W_{j,n}\xrightarrow{p}0\) and \(|T_{j,n}-R(a_j)|\xrightarrow{p}0\). Finally, the terms \(\ell(a_j,Z_i)\) are independent and bounded, so

Chebyshev’s inequality gives \(P_n\ell(a_j)\xrightarrow{p}R(a_j)\). The displayed triangle inequality now proves convergence for each \(j\). Since \(J\) is finite, the union bound gives convergence of the maximum: for every \(\varepsilon>0\), the probability that any procedure’s error exceeds \(\varepsilon\) is at most the sum of the finitely many corresponding probabilities, each of which tends to zero. \(\square\)

The proof handles overlapping training sets without pretending that fold scores are independent. It compares the fold-specific losses with losses from fixed rules, for which the ordinary independent-observation law of large numbers applies. The assumption is sufficient, not necessary; it may fail for procedures whose predictions continue to vary substantially with their training samples.

Consequences for Choosing Among a Finite Set

Uniform consistency matters when the same cross-validation scores are used to select a procedure. Let \(\widehat j\) minimize \(\widehat R_{j,\mathrm{CV}}\) over \(j\in J\), and let \(j_n^*\) minimize the fold-risk targets \(T_{j,n}\). If there is a unique minimizer it is unambiguous; otherwise choose any minimizer. For each realized data set,

The first and last inequalities follow from the definition of \(\Delta_n\); the middle one follows because \(\widehat j\) minimizes the cross-validation score. The theorem implies \(\Delta_n\xrightarrow{p}0\), so the selected procedure’s target risk approaches the smallest target risk in the finite set, in the sense of this excess-risk bound. This statement concerns the fold-size targets, not automatically the risks of procedures refitted on all \(n\) observations.

What Overlap Does—and Does Not—Permit

The training sets \(D_{-k}\) overlap heavily, so the random fold risks \(R(A_j(D_{-k}))\) can be dependent. Likewise, losses in different folds can be dependent because the fitted rules share training observations. The proof above does not require these fold quantities to be independent: it uses an expected discrepancy bound and an empirical average of fixed-rule losses.

A common mistake is to apply a concentration inequality for \(K\) independent fold scores, or to treat all \(n\) fitted losses as independent just because they are evaluated on \(n\) different observations. The correction is to identify which observations a fitted rule depends on and justify concentration for the actual dependence structure. Here, the theorem supplies a different route: compare with fixed limiting rules, then use independence only for their empirical losses.

Finally, the fact that \(E[\widehat R_{j,\mathrm{CV}}-T_{j,n}]=0\) does not mean the two quantities are close for a particular data set. Unbiasedness is an expectation statement; consistency is a probability statement about the absolute error shrinking. The prediction-convergence assumption is one transparent sufficient condition connecting the latter to the former.