TheoremStatement: 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.

An agnostic VC minimax lower bound

Statement

Let $H$ be a nonempty measurable binary class with finite VC dimension $d \geq 2$ , and let $m \geq ⌈ 64 d / 5 ⌉$ be an integer. Set $r = \sqrt{d / (320 m)}$ . For every possibly randomized learner $A$ , there is a probability law $D$ on $X \times {0, 1}$ such that $\Pr_{S \sim D^{m}, A} {R_{D} (A (S)) - \inf_{h \in H} R_{D} (h) > r} \geq \frac{1}{64} .$ The probability includes both the iid sample and the learner's internal randomness.

Statement references

Mohri et al., Foundations of Machine Learning, 2nd ed., Theorem 3.23 and proof

Shalev-Shwartz and Ben-David, Chapter 28 §28.2.2 (independent product-prior proof; the printed final substitution is not used)

Facts & Assumptions

Given: A measurable binary class $H$ with $VCdim (H) = d \geq 2$ , an integer $m \geq ⌈ 64 d / 5 ⌉$ , and a possibly randomized learner $A$ .

[F1]

A finite set of $d$ distinct points is shattered when its indexed trace family contains every subset of $[d]$ (Binary learning minimax excess risk, Shattering and the Vapnik–Chervonenkis dimension of a set family).

[F2]

For the two Bernoulli laws with success probabilities $(1 - u) / 2$ and $(1 + u) / 2$ , every equal-prior test based on $k \geq 1$ samples has error at least $2 Φ (2 ⌈ k / 2 ⌉, u)$ ; with $k = 0$ its error is $1 / 2$ (A Bernoulli two-point testing lower bound).

[F3]

If $Z \in [0, 1]$ almost surely and $0 \leq t < 1$ , then $\Pr {Z > t} \geq (E Z - t) / (1 - t)$ (A lower-tail bound from a bounded mean).

[A1]

For a point $z$ of a measurable space, the point-mass law $δ_{z}$ assigns a measurable set $B$ mass $1_{{z \in B}}$ ; a finite convex combination of point-mass laws is a probability law.

Proof

1.1givenA1F1choosealgebra

Put $r = \sqrt{d / (320 m)}$ and $a = 64 r / 7$ . The sample range gives $r \leq 1 / 64$ and $0 < a \leq 1 / 7$ . Choose distinct $x_{1}, \dots, x_{d}$ shattered by $H$ . For each $σ \in {- 1, + 1}^{d}$ , define $D_{σ} : = \frac{1}{d} \sum_{i = 1}^{d} [(\frac{1}{2} + \frac{σ_{i} a}{2}) δ_{(x_{i}, 1)} + (\frac{1}{2} - \frac{σ_{i} a}{2}) δ_{(x_{i}, 0)}]$ . The weights are nonnegative and sum to one, so [A1] makes this a probability law. The Bayes label $b_{i} = 1_{{σ_{i} = + 1}}$ is realized on these points by some $h \in H$ by [F1]. At atom $x_{i}$ , predicting $b_{i}$ has error $(1 - a) / 2$ , while predicting $1 - b_{i}$ has error $(1 + a) / 2$ , by the two point masses in $D_{σ}$ . Since each atom has marginal weight $1 / d$ , the class benchmark is $(1 - a) / 2$ and every binary predictor $g$ has excess risk $R_{D_{σ}} (g) - \inf_{h \in H} R_{D_{σ}} (h) = \frac{a}{d} \sum_{i = 1}^{d} 1_{{g (x_{i}) \neq b_{i}}}$ . This identity holds for every binary output $g$ .

1.2givenF2algebra

For $c = a^{2} / (1 - a^{2}) > 0$ and $q = e^{- c t}$ , direct differentiation of $Φ (t, a) = \frac{1}{4} (1 - \sqrt{1 - q})$ gives $Φ^{'} (t, a) = - \frac{c q}{8 \sqrt{1 - q}} < 0$ and $Φ^{''} (t, a) = \frac{c^{2} q (2 - q)}{16 (1 - q)^{3 / 2}} > 0$ for $t > 0$ . Also $Φ (0, a) = 1 / 4$ and $Φ$ is continuous there. Approximating any zero endpoint in the monotonicity and convexity inequalities by positive arguments and taking limits extends both properties to $[0, \infty)$ .

2.1givenF2step 1.1step 1.2

Fix coordinate $i$ and condition on all other signs and all sample data outside $x_{i}$ . Given $N_{i} = k \geq 1$ observations at $x_{i}$ , the learner's prediction there is a randomized test of $σ_{i}$ based on $k$ iid labels with the two laws in [F2]. Its conditional average mistake probability is at least $2 Φ (2 ⌈ k / 2 ⌉, a)$ . Since $2 ⌈ k / 2 ⌉ \leq k + 1$ and $Φ$ is decreasing by step 1.2, this is at least $2 Φ (k + 1, a) > Φ (k + 1, a)$ . For $k = 0$ the prediction is independent of $σ_{i}$ , so its average mistake probability is $1 / 2 > Φ (1, a)$ because $0 < Φ (1, a) < 1 / 4$ .

2.2givenstep 1.1algebrastep 1.2

Put $s = d / m \leq 5 / 64$ . Since $a^{2} = 64 s / 245$ and $m / d = 1 / s$ , $c (m / d + 1) = \frac{64}{245} \frac{1 + s}{1 - (64 / 245) s} \leq \frac{23}{80}$ . The derivative of $h (s) = \frac{64}{245} \frac{1 + s}{1 - (64 / 245) s}$ is $\frac{(64 / 245) (1 + 64 / 245)}{(1 - (64 / 245) s)^{2}} > 0$ , and direct substitution gives $h (5 / 64) = 23 / 80$ . Moreover, $\ln (4 / 3) = \int_{0}^{1 / 3} \frac{d x}{1 + x} > \frac{1}{3} - \frac{1}{18} + \frac{1}{81} - \frac{1}{324} + \frac{1}{1215} - \frac{1}{4374} = \frac{12581}{43740} > \frac{23}{80}$ . The strict lower bound follows from $1 / (1 + x) = 1 - x + x^{2} - x^{3} + x^{4} - x^{5} + x^{6} / (1 + x)$ , whose remainder is positive on $(0, 1 / 3]$ ; the final rational comparison follows from $80 \cdot 12581 = 1006480 > 1006020 = 23 \cdot 43740$ . Hence $c (m / d + 1) < \ln (4 / 3)$ , so $e^{- c (m / d + 1)} > 3 / 4$ and therefore $Φ (m / d + 1, a) > 1 / 8$ .

3.1givenstep 1.1step 1.2step 2.1algebra

Let $N_{i}$ count occurrences of $x_{i}$ ; $N_{i} \sim Bin (m, 1 / d)$ , so $E (N_{i} + 1) = m / d + 1 = : t_{0} > 0$ . With $Z$ equal to the excess risk in step 1.1 divided by $a$ , we have $Z \in [0, 1]$ . Averaging the strict coordinate bounds of step 2.1 over the finitely many coordinates, sample counts, signs, and learner randomization gives $E Z > E Φ (N_{i} + 1, a)$ . By step 1.2, $Φ^{'}$ is increasing on $(0, \infty)$ . For each possible value $x = N_{i} + 1 > 0$ , if $x > t_{0}$ the mean value theorem gives $Φ (x, a) - Φ (t_{0}, a) = Φ^{'} (ξ, a) (x - t_{0}) \geq Φ^{'} (t_{0}, a) (x - t_{0})$ for some $ξ \in (t_{0}, x)$ ; if $x < t_{0}$ , it gives the same inequality because $Φ^{'} (ξ, a) \leq Φ^{'} (t_{0}, a)$ for some $ξ \in (x, t_{0})$ and $x - t_{0} < 0$ ; equality holds when $x = t_{0}$ . Summing this finite inequality over the distribution of $N_{i}$ cancels the linear term because $E (N_{i} + 1) = t_{0}$ , so $E Φ (N_{i} + 1, a) \geq Φ (t_{0}, a) = : v$ . Therefore $E Z > v$ .

4.1step 3.1step 2.2choose

The prior on $σ$ is finite. Since the joint average in step 3.1 is greater than $v > 1 / 8$ , some $σ$ has $E_{S \sim D_{σ}^{m}, A} Z > 1 / 8$ .

5.1givenF3step 1.1step 4.1algebra∎

For this $σ$ , $r / a = 7 / 64$ . Apply [F3] to $Z$ at $t = 7 / 64$ : $\Pr {Z > 7 / 64} \geq \frac{E Z - 7 / 64}{57 / 64} > \frac{1 / 8 - 7 / 64}{57 / 64} = \frac{1}{57} > \frac{1}{64}$ . Since $a (7 / 64) = r$ , the event is exactly that the class excess risk exceeds $r$ .

Depends on

Used by

The realizable and agnostic VC lower rates Corollary
Fixed-confidence lower bounds at dimension four Example

Dependency tree · two levels

12 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, Theorem 3.23 and proof (standard reference, not scraped)
Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, 2014, Chapter 28 §28.2.2 (standard reference, not scraped)