TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Cross-validation estimates risk at its training sizes

Statement

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 $\hat{R}$ be its cross-validation estimate. Then

$E [\hat{R}] = \sum_{r = 1}^{B} w_{r} R_{∣ T_{r} ∣} .$

In particular, a holdout split trained on $k$ observations has expected score $R_{k}$ . For a fixed $K$ -fold partition, this gives $E [{\hat{R}}_{C V}] = \sum_{j = 1}^{K} (∣ I_{j} ∣ / n) R_{n - ∣ I_{j} ∣}$ , 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_{∣ T_{r} ∣} - 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.

Facts & Assumptions

Given: The IID sample, measurable learning rules and integrable losses in the statement, and a finite split schedule. Prove the displayed expectation formula.

[F1]

Identical distribution and IID families: IID means the variables have one common law and the whole family is mutually independent.

[F2]

Independent random elements have product joint law: a finite independent family has joint law equal to the product of its marginal laws.

[F3]

Cross-validation splits and training-size risk targets: $R_{k}$ is the expected loss from training on $k$ IID observations and evaluating on an independent test observation; the fixed-partition score averages held-out losses with weight $1 / n$ per observation.

[F4]

Holdout, leave-out, V-fold, and repeated cross-validation: each finite schedule consists of nonempty disjoint training and validation sets, nonnegative weights summing to one, and the score is the weighted average of within-validation-set loss averages.

[F5]

Holdout, leave-out, V-fold, and repeated cross-validation: a randomized split schedule is admissible when its law is declared and independent of the observations.

[A1]

Cross-validation splits and training-size risk targets: in addition to schedule training sizes, assume the full-sample loss $L (A_{n} (Z_{1}, \dots, Z_{n}), Z_{n + 1})$ is integrable, so $R_{n}$ is finite.

[F6]

Holdout, leave-out, V-fold, and repeated cross-validation: in $K$ -fold validation, $T_{j} = I_{j}^{c}$ , $V_{j} = I_{j}$ , and $w_{j} = ∣ I_{j} ∣ / n$ .

Proof

1.1F1F2F3F4

Fix a split $r$ and an index $i \in V_{r}$ . Since $T_{r}$ and $V_{r}$ are disjoint by [F4], $i \notin T_{r}$ . By [F1], the $∣ T_{r} ∣$ training observations $(Z_{ℓ})_{ℓ \in T_{r}}$ and the test observation $Z_{i}$ are independent, each with law $P$ . By [F2], their joint law is $P^{\otimes (∣ T_{r} ∣ + 1)}$ . Hence [F3] gives $E [L (A_{∣ T_{r} ∣} (Z_{T_{r}}), Z_{i})] = R_{∣ T_{r} ∣}$ .

2.1F4step 1.1algebra

For a fixed schedule, its score is a finite sum of the integrable terms from step 1.1, so linearity of expectation and [F4] give $E [\hat{R}] = \sum_{r = 1}^{B} (w_{r} / ∣ V_{r} ∣) \sum_{i \in V_{r}} R_{∣ T_{r} ∣} = \sum_{r = 1}^{B} w_{r} R_{∣ T_{r} ∣}$ .

3.1A1step 2.1algebra

By [A1], the full-sample target $R_{n}$ is finite. Subtracting it from step 2.1 yields $E [\hat{R}] - R_{n} = \sum_{r} w_{r} (R_{∣ T_{r} ∣} - R_{n})$ . This expression has no fixed sign in general; if $k \mapsto R_{k}$ is nonincreasing, then each difference is nonnegative because $∣ T_{r} ∣ < n$ .

3.2F5givenstep 2.1algebra

Let the schedule be independently randomized with finite range. Conditional on any realized schedule $s$ , the sample remains IID with law $P$ by [F5], so step 2.1 applies and gives $E [\hat{R} ∣ S = s] = \sum_{r} w_{r} (s) R_{∣ T_{r} (s) ∣}$ . Averaging this identity over the finite schedule law gives the stated unconditional expectation.

4.1F6step 2.1algebra∎

In a fixed $K$ -fold partition, [F6] gives $T_{j} = I_{j}^{c}$ , $V_{j} = I_{j}$ , and $w_{j} = ∣ I_{j} ∣ / n$ . Substituting these values in step 2.1 gives the displayed fold-size formula; equal folds of size $m$ give $R_{n - m}$ . The holdout claim is the one-split case $B = 1$ , $w_{1} = 1$ .

Remarks

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.

Depends on

Used by

A holdout estimate targets a smaller training sample Example

Dependency tree · two levels

13 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Sylvain Arlot and Alain Celisse, A survey of cross-validation procedures for model selection, §5.1.1, author version arXiv:0907.4728 (standard reference, not scraped)
Gareth James, Daniela Witten, Trevor Hastie, and Robert Tibshirani, An Introduction to Statistical Learning, 7th printing, Chapter 5 §§5.1.1–5.1.3 (standard reference, not scraped)