CorollaryStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

The realizable and agnostic VC lower rates

Statement

Let $H$ be a nonempty measurable binary class with finite VC dimension $d \geq 2$ . In the ranges $m \geq ⌈ (d - 1) / 4 ⌉$ and $m \geq ⌈ 64 d / 5 ⌉$ , respectively, the realizable and agnostic theorems imply $M_{r e a l} (m, H) \geq \frac{d - 1}{3200 m} \geq \frac{d}{6400 m}, M_{a g n} (m, H) \geq \frac{1}{64} \sqrt{\frac{d}{320 m}} .$ For $0 < δ < 1 / 100$ , $0 < η \leq 1 / 8$ , and any integer $m$ in the realizable theorem's range with $m < (d - 1) / (32 η)$ , no learner satisfies $\sup_{D \in D_{r e a l} (H)} \Pr_{S \sim D^{m}, A} {R_{D} (A (S)) > η} \leq δ$ . For $0 < δ < 1 / 64$ , $η > 0$ , and any integer $m$ in the agnostic theorem's range with $m < d / (320 η^{2})$ , no learner satisfies $\sup_{D \in D} \Pr_{S \sim D^{m}, A} {R_{D} (A (S)) - R_{D}^{*} (H) > η} \leq δ$ . Thus, within the stated sample ranges and at fixed confidence levels, necessary sample sizes scale at least proportionally to $d / η$ in the realizable case and $d / η^{2}$ in the agnostic case. These are information-theoretic lower bounds and make no claim about computational efficiency.

Statement references

Mohri et al., Foundations of Machine Learning, 2nd ed., §3.4

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

Facts & Assumptions

Given: A finite-VC binary class $H$ with $d \geq 2$ .

[F1]

In the realizable range, every learner has a realizable law with probability at least $1 / 100$ of target risk greater than $(d - 1) / (32 m)$ (A realizable VC minimax lower bound).

[F2]

In the agnostic range, every learner has a law with probability at least $1 / 64$ of class excess risk greater than $\sqrt{d / (320 m)}$ (An agnostic VC minimax lower bound).

[F3]

The realizable expected minimax value is the infimum over learners of the supremum realizable expected target risk ( $M_{r e a l}$ ) (Binary learning minimax excess risk).

[F4]

The agnostic expected minimax value is the infimum over learners of the supremum expected class excess risk ( $M_{a g n}$ ) (Binary learning minimax excess risk).

[F5]

Class excess risk is nonnegative and at most one for every hypothesis in $H$ (Binary learning minimax excess risk).

Proof

1.1givenF1F2F3F4F5algebra

For a nonnegative random variable $X$ and $t \geq 0$ , $X \geq t 1_{{X > t}}$ pointwise, so $E X \geq t \Pr {X > t}$ . For each learner, [F1] supplies a realizable law with target risk exceeding $(d - 1) / (32 m)$ with probability at least $1 / 100$ ; since the supremum over realizable laws is at least this expectation, [F3] gives $M_{r e a l} \geq \frac{1}{100} \frac{d - 1}{32 m} = \frac{d - 1}{3200 m} \geq \frac{d}{6400 m}$ because $d - 1 \geq d / 2$ . Likewise [F2], nonnegativity in [F5], and the supremum over all laws in [F4] give $M_{a g n} \geq \frac{1}{64} \sqrt{d / (320 m)}$ .

2.1givenF1F2algebra∎

If $m < (d - 1) / (32 η)$ then $(d - 1) / (32 m) > η$ , so the event in [F1] is contained in the event of error exceeding $η$ . Its probability is at least $1 / 100 > δ$ . If $m < d / (320 η^{2})$ then $\sqrt{d / (320 m)} > η$ , so [F2] similarly gives failure probability at least $1 / 64 > δ$ . Thus any successful sample size in the respective theorem range must be at least $(d - 1) / (32 η)$ or $d / (320 η^{2})$ , respectively. Since $d - 1 \geq d / 2$ for $d \geq 2$ , the first is at least $d / (64 η)$ ; the second is already a constant multiple of $d / η^{2}$ .

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)
Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, 2014, Chapter 28 §28.2 (standard reference, not scraped)
Statistical Learning Theory course notes, University of British Columbia, Chapter 7 §7.3 (standard reference, not scraped)