Cross-validation risk, model selection, and comparison uncertainty: Examples

1 · Prerequisites

2 · Summary

Examples

A holdout estimate targets a smaller training sample calculates a nonzero holdout bias for a sample-mean predictor.
Paired K-fold comparison retains correlated fold errors computes the covariance terms in a paired two-fold comparison and checks them on all 16 binary samples.
Random row splits leak repeated-group information shows why repeated observations must be split by group when the target is a new group.
Equal predictive risks do not identify a model label gives two observationally equivalent labels with equal predictive risks.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

A holdout estimate targets a smaller training sample

Example

Take $n = 4$ IID observations $Z_{i} \sim Bernoulli (1 / 2)$ , squared loss $L (a, z) = (a - z)^{2}$ , and the learning rule $A_{k} (z_{1}, \dots, z_{k}) = k^{- 1} \sum_{q = 1}^{k} z_{q}$ . Hold out $Z_{4}$ and train on $Z_{1}, Z_{2}, Z_{3}$ . The expected holdout score estimates $R_{3}$ , while training on all four observations has risk $R_{4}$ .

Facts & Assumptions

Given: The four IID Bernoulli observations, the sample-mean rule, squared loss, and holdout split above. Compute the training-size risks and their difference.

[F1]

Cross-validation estimates risk at its training sizes: the expected holdout score with $k$ training observations is $R_{k}$ .

[F2]

Cross-validation splits and training-size risk targets: $R_{k} = E [L (A_{k} (Z_{1}, \dots, Z_{k}), Z_{k + 1})]$ for an independent test observation.

[F3]

Identical distribution and IID families: the observations are mutually independent and have one common law.

[F4]

Moments, variance, and covariance on a probability space: variance is $E [(X - E X)^{2}]$ for square-integrable $X$ .

[F5]

Expectations factor over finite products of independent random variables: expectations of products of integrable functions of independent variables factor.

[F6]

Holdout, leave-out, V-fold, and repeated cross-validation: a holdout score averages losses on the validation indices after training on their complement.

[F7]

Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials: For $p \in [0, 1]$ , a Bernoulli $(p)$ random variable takes the value $1$ with probability $p$ and $0$ with probability $1 - p$ .

Verification

1.1givenF3F4F5F7algebra

For $Z \sim Bernoulli (p)$ , [F7] gives $E Z = p$ and the two-point expectation gives $Var (Z) = p (1 - p)$ . Expanding the variance of ${\overset{ˉ}{Z}}_{k} = k^{- 1} \sum_{q = 1}^{k} Z_{q}$ , the diagonal terms sum to $k p (1 - p)$ and each cross covariance vanishes by [F3] and [F5]; hence $Var ({\overset{ˉ}{Z}}_{k}) = p (1 - p) / k$ .

2.1F2F3F4F5step 1.1algebra

The independent test variable $Z_{k + 1}$ has mean $p$ and variance $p (1 - p)$ . Expanding $E [({\overset{ˉ}{Z}}_{k} - Z_{k + 1})^{2}]$ around the common mean $p$ , the centered cross term is zero by independence, so [F2] gives $R_{k} = Var ({\overset{ˉ}{Z}}_{k}) + Var (Z_{k + 1}) = p (1 - p) (1 + 1 / k)$ .

3.1F1F2F6step 2.1algebra∎

At $p = 1 / 2$ , $R_{3} = \frac{1}{4} (1 + \frac{1}{3}) = \frac{1}{3}$ and $R_{4} = \frac{1}{4} (1 + \frac{1}{4}) = \frac{5}{16}$ . The split in [F6] holds out one observation, so [F1] gives expected holdout score $R_{3}$ ; its bias for full-sample risk is $R_{3} - R_{4} = \frac{1}{48} > 0$ .

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Paired K-fold comparison retains correlated fold errors

Example

Let $n = 4$ , $K = 2$ , $I_{1} = {1, 2}$ , $I_{2} = {3, 4}$ , and $Z_{i} \overset{I I D}{\sim} Bernoulli (1 / 2)$ . Compare $A_{k} (z_{1}, \dots, z_{k}) = \prod_{q} z_{q}$ with the zero predictor $B_{k} = 0$ under loss $L (h, z) = h z$ , using the same folds for both procedures. Write $\hat{Δ}$ for the paired difference of their cross-validation scores.

Facts & Assumptions

Given: The two-fold partition, IID Bernoulli observations, product and zero rules, and loss above. Compute the covariance terms and the variance of the paired difference.

[F1]

Cross-validation splits and training-size risk targets: the equal-fold score is the average of the four held-out losses.

[F2]

Holdout, leave-out, V-fold, and repeated cross-validation: paired comparison applies the same split schedule and averages within-fold loss differences.

[F3]

Identical distribution and IID families: the four observations are mutually independent with a common Bernoulli law.

[F4]

Expectations factor over finite products of independent random variables: expectations of products of functions of distinct observations factor.

[F5]

Moments, variance, and covariance on a probability space: variance and covariance are the centered second moments.

[F6]

The covariance decomposition of a fixed K-fold score: for $K$ equal folds, the average-error variance is $σ^{2} / n + (m - 1) ω / n + (n - m) γ / n$ .

[F7]

Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials: For $p \in [0, 1]$ , a Bernoulli $(p)$ random variable takes the value $1$ with probability $p$ and $0$ with probability $1 - p$ .

Verification

1.1givenF1F2

Since the zero rule has zero loss, the four paired errors are $e_{1} = Z_{1} Z_{3} Z_{4}$ , $e_{2} = Z_{2} Z_{3} Z_{4}$ , $e_{3} = Z_{3} Z_{1} Z_{2}$ , and $e_{4} = Z_{4} Z_{1} Z_{2}$ , and $\hat{Δ} = \frac{1}{4} \sum_{i = 1}^{4} e_{i}$ .

2.1F3F4F5F7step 1.1algebra

Each $e_{i}$ is a product of three independent Bernoulli $(1 / 2)$ variables, so [F3]–[F5] and [F7] give $E e_{i} = 1 / 8$ and $Var (e_{i}) = 1 / 8 - (1 / 8)^{2} = 7 / 64$ . For any distinct $i, j$ , the product $e_{i} e_{j}$ equals $Z_{1} Z_{2} Z_{3} Z_{4}$ because $Z_{q}^{2} = Z_{q}$ ; hence $E [e_{i} e_{j}] = 1 / 16$ and $Cov (e_{i}, e_{j}) = 1 / 16 - (1 / 8)^{2} = 3 / 64$ . Thus $ω = γ = 3 / 64$ .

3.1F5F6step 2.1algebra

Substituting $n = 4, m = 2, σ^{2} = 7 / 64, ω = γ = 3 / 64$ into [F6] gives $Var (\hat{Δ}) = \frac{7}{256} + \frac{3}{256} + \frac{6}{256} = \frac{1}{16}$ . Treating the four errors as independent would keep only $7 / 256$ , omitting the two positive covariance contributions.

4.1F3F4F5F7step 3.1algebra∎

Directly, if all four observations are one then $\hat{Δ} = 1$ ; if exactly three are one then $\hat{Δ} = 1 / 4$ ; with at most two ones it is zero. By [F7] these events have probabilities $1 / 16$ , $4 / 16$ , and $11 / 16$ , respectively, so $E \hat{Δ} = 1 / 8$ , $E {\hat{Δ}}^{2} = 5 / 64$ , and the direct variance is $5 / 64 - (1 / 8)^{2} = 1 / 16$ , confirming step 3.1.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Random row splits leak repeated-group information

Example

There are $G \geq 2$ groups, each with two repeated rows $(g, Y_{g})$ , where $Y_{1}, \dots, Y_{G}$ are IID Bernoulli $(1 / 2)$ . Choose uniformly a balanced two-fold partition of the $2 G$ rows, independently of the labels. The learner memorizes the majority label for any group ID present in training (ties are resolved as zero) and predicts zero for a previously unseen ID. Use zero-one loss. This grouped design is not an IID row sample: the two rows in a group share a label and fixed group IDs.

Facts & Assumptions

Given: The repeated-group data, balanced random row partition, memorizing rule, and zero-one loss above. Compare the expected row-split score with prediction risk for a new group.

[F1]

Holdout, leave-out, V-fold, and repeated cross-validation: a K-fold schedule trains on each fold's complement and weights held-out rows equally when folds have equal size.

[F2]

Identical distribution and IID families: IID requires mutual independence; repeated rows sharing $Y_{g}$ violate this row-level condition.

[F3]

Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials: For $p \in [0, 1]$ , a Bernoulli $(p)$ random variable takes the value $1$ with probability $p$ and $0$ with probability $1 - p$ .

Verification

1.1givenF1

For a fixed group $g$ , if its two rows fall in different folds, then each validation row's group ID appears in training and its memorized prediction is $Y_{g}$ , so both losses are zero. If both rows fall in one fold, neither is in the training set for that fold; both losses are $Y_{g}$ . Therefore the full row-split score is ${\hat{R}}_{r o w} = G^{- 1} \sum_{g = 1}^{G} Y_{g} 1 {the two rows of g share a fold}$ .

1.2givenalgebra

In a uniformly chosen balanced partition, the probability both rows of a fixed group lie in fold 1 is $(\binom{2 G - 2}{G - 2}) / (\binom{2 G}{G}) = (G - 1) / (2 (2 G - 1))$ ; the same probability holds for fold 2. Thus the probability they share a fold is $(G - 1) / (2 G - 1)$ .

2.1F2F3step 1.1step 1.2algebra

The split is independent of $Y_{g}$ , and [F3] gives $E Y_{g} = 1 / 2$ , so step 1.1 and the probability in step 1.2 give $E {\hat{R}}_{r o w} = (G - 1) / (2 (2 G - 1)) < 1 / 2$ . For a new group ID no training row has that ID, so the learner predicts zero and its error probability is $P (Y_{n e w} = 1) = 1 / 2$ . Row-split CV is therefore estimating an easier within-group prediction target than new-group prediction.

3.1F2F3step 2.1∎

The example violates the independent-row premise in [F2], so it is a warning about choosing the resampling unit to match deployment; it is not a counterexample to the IID risk identity.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Equal predictive risks do not identify a model label

Example

Let the candidate model labels be $M = {0, 1}$ with identical observation laws $P_{0} = P_{1} = Bernoulli (1 / 2)$ . Associate with each label the constant learning rule $A_{m, k} (z_{1}, \dots, z_{k}) = h_{m}$ for every $k$ , where $h_{0} = 0$ and $h_{1} = 1$ , and use squared loss. The labels describe distinct candidate specifications but make the same observable data law.

Facts & Assumptions

Given: The two candidate labels, their common data law, and the two constant predictors. Compare their risks and show that observations cannot recover the label.

[F1]

Risk estimation versus model identification: risk minimization chooses a label by predictive loss, whereas identification asks to recover the true data-generating label.

[F2]

Cross-validation splits and training-size risk targets: risk is expected loss on an independent test observation after training.

[F3]

Identical distribution and IID families: an IID sample has mutually independent coordinates with the common law.

[F4]

Independent random elements have product joint law: the joint law of an IID finite sample is the product of its common marginal law.

[F5]

Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials: For $p \in [0, 1]$ , a Bernoulli $(p)$ random variable takes the value $1$ with probability $p$ and $0$ with probability $1 - p$ .

Verification

1.1F1F2F5algebra

Under either label, $Y \sim Bernoulli (1 / 2)$ . By [F5], the two prediction risks are $E [(0 - Y)^{2}] = 1 / 2$ and $E [(1 - Y)^{2}] = 1 / 2$ , since $Y^{2} = Y$ and $(1 - Y)^{2} = 1 - Y$ . Thus the predictive-risk objective ties the labels and any fixed tie rule selects one without separating them.

1.2F3F4algebra

For every sample size $n$ , [F3]–[F4] give the same data law $P_{0}^{\otimes n} = P_{1}^{\otimes n}$ . Therefore every measurable data-based selector has the same output distribution under labels 0 and 1. If it were model-consistent at label 0, then $P_{0} ({\hat{m}}_{n} = 0) \to 1$ , and equality of the sample laws would give $P_{1} ({\hat{m}}_{n} = 0) \to 1$ . Consistency at label 1 would also give $P_{1} ({\hat{m}}_{n} = 1) \to 1$ , impossible because these disjoint events have probabilities summing to at most one.

2.1F1step 1.1step 1.2∎

The example has equal predictive risk but no observable information that distinguishes the two labels, so risk minimization alone does not identify a true model.

Cross-validation risk, model selection, and comparison uncertainty — Examples

1 · Prerequisites

2 · Summary

Examples

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

A holdout estimate targets a smaller training sample

Example

Facts & Assumptions

Verification

Paired K-fold comparison retains correlated fold errors

Example

Facts & Assumptions

Verification

Random row splits leak repeated-group information

Example

Facts & Assumptions

Verification

Equal predictive risks do not identify a model label

Example

Facts & Assumptions

Verification

Sources