ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedjudge 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.

Zero training error can coexist with positive population risk

Example

Let $X = {a, b}$ have the discrete sigma-algebra, and let $P$ assign probability $1 / 2$ to each of $(a, 0)$ and $(b, 0)$ . Let $h_{0} (a) = h_{0} (b) = 0$ and $h_{1} (a) = 0$ , $h_{1} (b) = 1$ , so $H = {h_{1}, h_{0}}$ is realizable by $h_{0}$ . Run exact finite-list ERM on the ordered list $(h_{1}, h_{0})$ . For every integer $m \geq 1$ , if $S = ((X_{1}, Y_{1}), \dots, (X_{m}, Y_{m}))$ is an IID sample from $P$ , the event $S = ((a, 0), \dots, (a, 0))$ has probability $2^{- m}$ ; on this event $h_{1}$ has empirical risk zero and population risk $1 / 2$ , and the tie-breaking rule returns $h_{1}$ . Thus zero training error does not imply zero population risk on every sample, even for a realizable finite class; PAC guarantees bound a failure probability over samples.

Example references

Realizable and agnostic PAC learning: defines realizability and the probability-over-samples form of a PAC guarantee.

Finite-list empirical risk minimization: returns the first exact minimizer in the given order when tolerance is zero.

Facts & Assumptions

Given: The finite instance space, joint law, two classifiers, and ordered list in the Example, with IID samples of size $m \geq 1$ .

[F1]

At tolerance zero, the finite-list algorithm returns the first empirical-risk minimizer. Finite-list empirical risk minimization

[F2]

IID means sample observations are mutually independent and identically distributed. Identical distribution and IID families

[F3]

Realizable PAC requires the risk threshold with probability at least $1 - δ$ over the IID sample; it is a probability guarantee, not a pointwise assertion for every sample. Realizable and agnostic PAC learning

Verification

Given: The model and ordered finite-list ERM in the Example.

1.1givenalgebra

The classifier $h_{1}$ errs exactly when $X = b$ , so $R_{P} (h_{1}) = 1 / 2$ , while $h_{0}$ has zero risk. On the specified all- $a$ sample, each observed pair is $(a, 0)$ and both classifiers have empirical risk zero.

2.1F1F2F3step 1.1algebra∎

By [F2], the probability that all $m$ independent inputs equal $a$ is $(1 / 2)^{m} = 2^{- m} > 0$ . On that event, [F1] selects $h_{1}$ first, so the learner returns zero empirical risk with population risk $1 / 2$ . This is a positive-probability sample event and does not contradict the probabilistic form of [F3].

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

9 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.