Cross-validation risk, model selection, and comparison uncertainty

Let $(\mathcal{Z},\mathcal{F})$ be a measurable sample space with probability law $P$. For each training size $k\ge 1$, a learning rule is a measurable map $A_k:{\mathcal{Z}}^k\to (\mathcal{H},\mathcal{G})$, where $(\mathcal{H},\mathcal{G})$ is a measurable predictor space. This is a statistic in the sense of Statistics and estimators. Let $L:\mathcal{H}\times \mathcal{Z}\to \mathbb{R}$ be jointly measurable and assume $L(A_k(Z_1,\dots ,Z_k),Z_{k+1})$ is integrable under $P^{\otimes (k+1)}$ for every size used. The convention that risk is expected loss agrees with Loss functions and risk for nonnegative losses; the integrable real-valued case is used here as well. The product law is the joint law of independent observations by Independent random elements have product joint law.

The risk at training size $k$ is

$R_k:={\mathbb{E}}_{P^{\otimes (k+1)}}\text{\hspace{0.17em}⁣}\left[L\right(A_k(Z_1,\dots ,Z_k),Z_{k+1}\left)\right],$

where $Z_{k+1}$ is independent of the training sample. A split of $[n]:=\{1,\dots ,n\}$ is a pair $(T,V)$ of disjoint nonempty sets with $T\cup V=[n]$; $T$ is the training index set and $V$ is the validation index set. For a fixed partition $I_1,\dots ,I_K$ of $[n]$ into nonempty folds with $K\ge 2$, the equal-observation-weight cross-validation score is

${\widehat{R}}_{CV}:=\frac{1}{n}{\sum }_{j=1}^K{\sum }_{i\in I_j}L(A_{n-\mathrm{\mid }{I}_j\mathrm{\mid }}(Z_{I_j^c}),Z_i),$

where each training tuple $Z_{I_j^c}$ is ordered by increasing index and $I_j^c=[n]\setminus I_j$. The risk corresponding to this design is the weighted training-size target ${\sum }_{j=1}^K(\mathrm{\mid }{I}_j\mathrm{\mid }\mathrm{/}n)R_{n-\mathrm{\mid }{I}_j\mathrm{\mid }}$. For equal folds of size $m$, this target is $R_{n-m}$; it is not automatically $R_n$, the risk after training on all $n$ observations.

Let $(\mathcal{Z},\mathcal{F})$ be an observation space, let $M$ be a nonempty finite set of candidate labels, and for each $m\in M$ let $P_m$ be a probability law on $(\mathcal{Z},\mathcal{F})$. For each $m\in M$ and training size $k\ge 1$, let $A_{m,k}:{\mathcal{Z}}^k\to (\mathcal{H},\mathcal{G})$ be a measurable learning rule into a common measurable predictor space. For a data law $P$ and loss $L$ satisfying the measurability and integrability hypotheses of Cross-validation splits and training-size risk targets, write

$R_{m,k}(P):={\mathbb{E}}_{P^{\otimes (k+1)}}\text{\hspace{0.17em}⁣}\left[L\right(A_{m,k}(Z_1,\dots ,Z_k),Z_{k+1}\left)\right]$

for its risk at training size $k$; when $P$ is fixed, write $R_{m,k}$. A risk-minimizing selector chooses a label minimizing the specified risk criterion, such as $R_{m,k}$ or its cross-validation estimate; a fixed ordering of $M$ may be used to resolve ties. This objective compares expected predictive loss.

For each $n\ge 1$, a data-based selector is a measurable map ${\widehat{m}}_n:{\mathcal{Z}}^n\to M$, where $M$ has its discrete sigma-algebra. A true model label at sample size $n$ is a specified $m_0\in M$ when the observations are IID with law $P_{m_0}$. The selector sequence $({\widehat{m}}_n)$ is model-consistent at $m_0$ when $P_{m_0}^{\otimes n}({\widehat{m}}_n=m_0)\to 1$ as $n\to \mathrm{\infty }$. This identification objective is distinct from minimizing predictive risk: risk minimization alone does not assert that the family is identifiable, that one candidate is true, or that the minimum-risk label is the true label. The distinction between risk estimation/model selection for prediction and model identification follows Cross-validation splits and training-size risk targets's risk target and the source treatments cited below.

Input: observations $z_1,\dots ,z_n$, learning rules $A_k$, a loss $L$, and a finite split schedule $((T_r,V_r,w_r){)}_{r=1}^B$. Each $(T_r,V_r)$ is a split as in Cross-validation splits and training-size risk targets, $w_r\ge 0$, and ${\sum }_{r=1}^B{w}_r=1$. A randomized schedule is admissible only when its law is specified and is independent of the observations.

Output: the cross-validation estimate

$\widehat{R}:={\sum }_{r=1}^B{w}_r\frac{1}{\mathrm{\mid }{V}_r\mathrm{\mid }}{\sum }_{i\in V_r}L(A_{\mathrm{\mid }{T}_r\mathrm{\mid }}(z_{T_r}),z_i),$

with each training tuple ordered by increasing index.

Instructions: fit the rule on each training set, evaluate its loss on every observation in that split's validation set, average within that validation set, then combine the split averages using the declared weights. To compare two or more candidate rules, apply the same schedule and subtract their validation losses within each split before averaging; this is the paired comparison.

The following choices give standard procedures:

• Holdout: one split, with $T$ the chosen training set, $V=T^c$, and weight $1$.
• Leave-one-out: for $n\ge 2$, use $n$ splits $T_i=[n]\setminus \{i\}$, $V_i=\{i\}$, with weights $1\mathrm{/}n$.
• Leave-$p$-out: for $n\ge 2$ and $1\le p<n$, use one split for every $p$-element subset $J\subseteq [n]$, with $T_J=J^c$, $V_J=J$, and weight $1\mathrm{/}\left(\genfrac{}{}{0px}{}{n}{p}\right)$.
• $K$-fold: for $2\le K\le n$ and a partition $I_1,\dots ,I_K$ into nonempty folds, use $T_j=I_j^c$, $V_j=I_j$, and $w_j=\mathrm{\mid }{I}_j\mathrm{\mid }\mathrm{/}n$; for equal folds this is $1\mathrm{/}K$.
• Repeated $K$-fold: for $n\ge 2$, $2\le K\le n$ and $R\ge 1$, apply the $K$-fold schedule to each of $R$ declared partitions and give fold $I_{rj}$ weight $\mathrm{\mid }{I}_{rj}\mathrm{\mid }\mathrm{/}(Rn)$. If partitions are randomized, record their independent randomization law and average under that law or over the declared finite repetitions.

These instructions define estimates only. Their validity as estimates of a deployment target depends on matching the split, sampling unit, training size, and averaging law to that target.

Let $Z_1,\dots ,Z_n$ be IID with law $P$. Let $A_k$ and $L$ satisfy the measurability and integrability hypotheses of Cross-validation splits and training-size risk targets at every schedule training size and also at size $n$. For a fixed finite schedule $((T_r,V_r,w_r){)}_{r=1}^B$ as in Holdout, leave-out, V-fold, and repeated cross-validation, let $\widehat{R}$ be its cross-validation estimate. Then

$\mathbb{E}[\widehat{R}]={\sum }_{r=1}^B{w}_r{R}_{\mathrm{\mid }{T}_r\mathrm{\mid }}\mathrm{.}$

In particular, a holdout split trained on $k$ observations has expected score $R_k$. For a fixed $K$-fold partition, this gives $\mathbb{E}[{\widehat{R}}_{CV}]={\sum }_{j=1}^K(\mathrm{\mid }{I}_j\mathrm{\mid }\mathrm{/}n)R_{n-\mathrm{\mid }{I}_j\mathrm{\mid }}$, and for equal folds of size $m$ it gives $R_{n-m}$. For every fixed schedule, the bias for the full-sample risk $R_n$ is exactly ${\sum }_r{w}_r(R_{\mathrm{\mid }{T}_r\mathrm{\mid }}-R_n)$; it need not have a fixed sign without an additional monotonicity hypothesis on $k\mapsto R_k$.

If a schedule $S$ is randomized independently of the observations and takes values in a finite set of such schedules, then, conditional on each realized schedule, the same formula holds; the unconditional expectation is the corresponding average of these training-size risks.

The calculation uses linearity of expectation only; the fold losses may be dependent because their training sets overlap. It does not assert that a smaller training sample always has higher risk.

Let $n=Km$ with integers $K\ge 2$ and $m\ge 1$. Let $Z_1,\dots ,Z_n$ be IID, let $I_1,\dots ,I_K$ be a fixed partition into folds of size $m$, and let $A_k$ be a permutation-symmetric measurable learning rule with a measurable loss. For $i\in I_j$, write $e_i=L(A_{n-m}(Z_{I_j^c}),Z_i)$ and assume $\mathbb{E}[e_i^2]<\mathrm{\infty }$. For a paired comparison, $e_i$ may instead be the difference of the two rules' losses evaluated using the same fold; assume both rules are symmetric and the differences are square-integrable. Define ${\sigma }^2:=\mathrm{Var}(e_i)$, $\omega :=\mathrm{Cov}(e_i,e_{i^{\mathrm{\prime }}})$ for distinct indices in one fold, and $\gamma :=\mathrm{Cov}(e_i,e_{i^{\mathrm{\prime }}})$ for indices in different folds. When $m=1$, set $\omega =0$ because there is no within-fold pair. These values are well-defined, and

$\mathrm{Var}\text{\hspace{0.17em}⁣}\left(\frac{1}{n}{\sum }_{i=1}^n{e}_i\right)=\frac{{\sigma }^2}{n}+\frac{m-1}{n}\omega +\frac{n-m}{n}\gamma \mathrm{.}$

The formula includes the within-fold dependence from a common training set and the between-fold dependence from overlapping training sets. It applies to foldwise paired differences under the same symmetry and moment hypotheses.

Fix $K\ge 2$, $m\ge 1$, $n=Km$, and a fixed equal-fold partition of $[n]$. A universal variance estimator is a measurable procedure based on the observed sample and the known rule, loss, and split, but not the unknown law $P$; any auxiliary random seed must be independent of both $P$ and the sample. No such procedure is unbiased for the K-fold score variance on every IID law and every symmetric learning rule with measurable loss whenever that variance is finite. More strongly, even if an estimator is tailored to one fixed symmetric rule, no such estimator is unbiased for all $P=\mathrm{Bernoulli}(p)$, $0<p<1$, for the explicit rule and loss in the proof.

This finite-support argument does not assume that a candidate variance estimator is analytic and applies even when it may use the full observed sample. The theorem does not rule out biased, asymptotic, or law-specific procedures, and it does not apply to an estimator supplied with fresh independent data.