Pipeline-generated

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.

Minimax learning lower bounds and optimal rates — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

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

One-sample Bernoulli two-point testing

Example

Take $u = 1 / 2$ and one observation, so $P_{-} = Bern (1 / 4)$ and $P_{+} = Bern (3 / 4)$ . The deterministic test $ψ (y) = y$ has equal-prior error $1 / 4$ , and this error is minimal among all randomized tests.

Example references

Mohri et al., Foundations of Machine Learning, 2nd ed., Lemma 3.21

Shalev-Shwartz and Ben-David, Understanding Machine Learning, §28.2.1

Facts & Assumptions

Given: The two laws $P_{-}$ and $P_{+}$ on ${0, 1}$ , equal prior probabilities, and the test convention that $ψ (y)$ is the probability of deciding $+$ .

[F1]

The equal-prior average error $e_{k} (ψ)$ is the half-sum of the two conditional error probabilities A Bernoulli two-point testing lower bound.

Verification

1.1givenalgebra

Here $P_{-} (0) = 3 / 4$ , $P_{-} (1) = 1 / 4$ , $P_{+} (0) = 1 / 4$ , and $P_{+} (1) = 3 / 4$ . The test $ψ (y) = y$ has error $\frac{1}{2} (P_{-} (1) + P_{+} (0)) = \frac{1}{4}$ .

2.1givenF1algebra∎

For any randomized test $ψ$ , direct expansion gives $e_{1} (ψ) = \frac{1}{2} + \frac{1}{4} (ψ (0) - ψ (1)) \geq \frac{1}{4}$ , since $ψ (0) \geq 0$ and $ψ (1) \leq 1$ . The deterministic test attains this lower bound.

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

A finite class shattering three points

Example

Let $X = {x_{1}, x_{2}, x_{3}}$ have the discrete sigma-algebra, and let $H$ be the class of all eight functions from $X$ to ${0, 1}$ . Then $VCdim (H) = 3$ .

Example references

Mohri et al., Foundations of Machine Learning, 2nd ed., Chapter 3

Statistical Learning Theory course notes, University of British Columbia, §7.2.2

Facts & Assumptions

Given: The finite measurable space $X$ and the class $H = {0, 1}^{X}$ .

[F1]

A class shatters an indexed finite set exactly when its trace family contains every subset of the index set; its VC dimension is the supremum of shattered cardinalities (Binary learning minimax excess risk, Shattering and the Vapnik–Chervonenkis dimension of a set family).

Verification

1.1givenF1construct

For each $A \subseteq [3]$ , the function $h_{A}$ defined by $h_{A} (x_{i}) = 1$ exactly when $i \in A$ belongs to $H$ ; hence the indexed trace family on ${x_{1}, x_{2}, x_{3}}$ is $P ([3])$ , so this set is shattered by [F1].

2.1givenF1algebra∎

The whole domain has only three points, so no subset of four distinct domain points exists. Thus no four-point set can be shattered, and the VC dimension is exactly three.

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

Fixed-confidence lower bounds at dimension four

Example

Let $H$ be any nonempty measurable binary class of VC dimension $4$ and let $m = 64$ . For every learner, there is a realizable law and target with probability at least $1 / 100$ that target risk exceeds $3 / 2048$ , and there is an agnostic law with probability at least $1 / 64$ that class excess risk exceeds $1 / \sqrt{5120}$ . The two laws may differ.

Example references

Mohri et al., Foundations of Machine Learning, 2nd ed., Theorems 3.20 and 3.23

Statistical Learning Theory course notes, University of British Columbia, Theorem 7.13 and proof (supports the realizable assertion here)

Facts & Assumptions

Given: A binary class $H$ with $VCdim (H) = 4$ , an integer sample size $m = 64$ , and a learner $A$ .

[F1]

For $d \geq 2$ and $m \geq ⌈ (d - 1) / 4 ⌉$ , the realizable lower-bound error threshold is $(d - 1) / (32 m)$ with failure probability at least $1 / 100$ (A realizable VC minimax lower bound).

[F2]

For $d \geq 2$ and $m \geq ⌈ 64 d / 5 ⌉$ , the agnostic lower-bound threshold is $\sqrt{d / (320 m)}$ with failure probability at least $1 / 64$ (An agnostic VC minimax lower bound).

[F3]

The VC dimension is the supremum of the cardinalities of finite shattered point sets (Binary learning minimax excess risk).

Verification

1.1givenF1F3algebra

By [F3] the given class has $d = 4$ . Hence $⌈ (4 - 1) / 4 ⌉ = 1 \leq 64$ and $(4 - 1) / (32 \cdot 64) = 3 / 2048$ , so [F1] gives the realizable assertion.

2.1givenF2algebra∎

Also $⌈ 64 \cdot 4 / 5 ⌉ = 52 \leq 64$ and $\sqrt{4 / (320 \cdot 64)} = 1 / \sqrt{5120}$ , so [F2] gives the agnostic assertion. The theorems allow different hard laws, as stated.

Minimax learning lower bounds and optimal rates — Examples

2 · Logical flowchart

3 · Definitions, theorems and proofs

4 · Examples, counterexamples and false statements

One-sample Bernoulli two-point testing

Example

Example references

Facts & Assumptions

Verification

A finite class shattering three points

Example

Example references

Facts & Assumptions

Verification

Fixed-confidence lower bounds at dimension four

Example

Example references

Facts & Assumptions

Verification

Sources