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.

No universal unbiased estimator of K-fold cross-validation variance

Statement

Fix $K \geq 2$ , $m \geq 1$ , $n = K m$ , 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 = Bernoulli (p)$ , $0 < p < 1$ , for the explicit rule and loss in the proof.

Facts & Assumptions

Given: The fixed equal-fold design and the universal-estimator meaning above. Prove the nonexistence claim.

[F1]

Identical distribution and IID families: IID means a common marginal law and mutual independence.

[F2]

Independent random elements have product joint law: the joint law of a finite independent sample is its finite product law.

[F3]

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

[F4]

Cross-validation splits and training-size risk targets: for a fixed equal-fold partition, ${\hat{R}}_{C V}$ is the average of the held-out losses, with training sample size $n - m$ .

[F5]

Holdout, leave-out, V-fold, and repeated cross-validation: K-fold evaluation uses the declared common partition and averages its held-out losses.

[F6]

The covariance decomposition of a fixed K-fold score: when the fold errors have common variance $σ^{2}$ , common within-fold covariance $ω$ , and common between-fold covariance $γ$ , the variance of their average 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$ .

Proof

1.1F6

By [F6], the K-fold score variance separates diagonal, within-fold, and between-fold covariance terms.

1.2F1F2F3F4F5F7construct

To test universality, take $Z = {0, 1}$ , $Z_{i} \overset{I I D}{\sim} Bernoulli (p)$ , predictor class $H = {0, 1}$ , and loss $L (h, z) = h z$ . By [F7], each $Z_{i}$ is one with probability $p$ and zero otherwise. For every training size $k$ , let the symmetric rule $A_{k} (z_{1}, \dots, z_{k}) = \prod_{q = 1}^{k} z_{q}$ . If $i \in I_{j}$ , its fold error is $e_{i} = Z_{i} \prod_{ℓ \in I_{j}^{c}} Z_{ℓ}$ , a product of $r : = n - m + 1$ distinct Bernoulli variables. By [F1]–[F3], $E [e_{i}] = p^{r}$ , so $E [{\hat{R}}_{C V}] = p^{r}$ .

2.1F1F2F7step 1.2algebra

For each fixed data vector $x \in {0, 1}^{n}$ , ${\hat{R}}_{C V} (x)$ is a finite real number. Hence $g (p) : = E_{p} [{\hat{R}}_{C V}^{2}] = \sum_{x \in {0, 1}^{n}} {\hat{R}}_{C V} (x)^{2} p^{s (x)} (1 - p)^{n - s (x)}$ , where $s (x)$ is the number of ones in $x$ , is a polynomial of degree at most $n$ . It follows that ${Var}_{p} ({\hat{R}}_{C V}) = g (p) - p^{2 r}$ . Since $2 r - n = m (K - 2) + 2 > 0$ , the term $- p^{2 r}$ has degree higher than $g$ , so the variance polynomial has degree $2 r > n$ .

3.1F7givenstep 2.1algebra∎

Any proposed estimator $T$ based on this sample, with no dependence on $p$ , has conditional mean $t (x) : = E [T ∣ Z = x]$ for each $x \in {0, 1}^{n}$ ; this is finite if $T$ is unbiased with finite expectation for every $0 < p < 1$ , since [F7] gives every such $x$ positive probability. The auxiliary random seed has a fixed law independent of $p$ , so $t (x)$ is fixed. Therefore $E_{p} [T] = \sum_{x} t (x) p^{s (x)} (1 - p)^{n - s (x)}$ is a polynomial of degree at most $n$ . It cannot equal the degree- $2 r$ variance polynomial on the whole interval $(0, 1)$ , because two polynomials equal on an interval must be identical. This contradiction proves the claim.

Remarks

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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

28 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

Yoshua Bengio and Yves Grandvalet, No Unbiased Estimator of the Variance of K-Fold Cross-Validation, JMLR 5 (2004), §§2–4 and Theorem 6, pp. 1090–1098 (standard reference, not scraped)
Sylvain Arlot and Alain Celisse, A survey of cross-validation procedures for model selection, §§5.2–5.2.3 (standard reference, not scraped)