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.

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.

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.

Sources

Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning, 2nd ed., Chapter 3 §3.4 (standard reference, not scraped)
Statistical Learning Theory course notes, University of British Columbia, Chapter 7 §7.3 (standard reference, not scraped)