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.

One-sided VC uniform convergence and the finite-class branch

Statement

Let $(X, Σ)$ be a nonempty measurable space, let $H$ be a nonempty class of measurable binary functions on $X$ with finite VC dimension $d$ , put $Z = X \times {0, 1}$ with its product sigma-algebra, and let $P$ be a probability law on $Z$ . For $h \in H$ , define $R_{P} (h) : = P {(x, y) : h (x) \neq y}$ and ${\hat{R}}_{S} (h) : = m^{- 1} \sum_{i = 1}^{m} 1 {h (X_{i}) \neq Y_{i}}$ for an IID sample $S = ((X_{i}, Y_{i}))_{i = 1}^{m}$ of size $m \geq 1$ with law $P$ . Assume every displayed supremum over $H$ and its binary loss class that appears below is measurable. For $0 < δ < 1$ , the following separate branches hold.

If $H$ is finite, then without an Axiom of Choice premise, with probability at least $1 - δ$ , $\sup_{h \in H} ∣ R_{P} (h) - {\hat{R}}_{S} (h) ∣ \leq \sqrt{\frac{\log ∣ H ∣ + \log (2 / δ)}{2 m}} .$ In particular, if $d = 0$ , then $H$ is a singleton and this gives $\sup_{h \in H} ∣ R_{P} (h) - {\hat{R}}_{S} (h) ∣ \leq \sqrt{\log (2 / δ) / (2 m)}$ .
If $1 \leq d \leq m$ and the Axiom of Choice (AC) is assumed, then with probability at least $1 - δ$ , simultaneously for every $h \in H$ , $R_{P} (h) \leq {\hat{R}}_{S} (h) + \sqrt{\frac{2 d \log (e m / d)}{m}} + \sqrt{\frac{\log (1 / δ)}{2 m}} .$

Here $\log$ is the natural logarithm and $e = \exp (1)$ .

Statement references

Mohri et al., Theorem 3.3, Theorem 3.5, Theorem 3.7, Corollary 3.8, and Corollary 3.19: one-sided Rademacher generalization, the finite-sample maximum bound, and the stated VC display.

Bartlett and Mendelson, Theorem 5 and Appendix B: an independent classification-risk bound in their $2 / m$ absolute-supremum normalization.

Facts & Assumptions

Given: A measurable binary class $H$ with finite $d = VCdim (H)$ , an IID sample of size $m \geq 1$ with law $P$ , measurable deviation suprema, and $0 < δ < 1$ .

[F1]

Shattering is defined on indexed tuples; repeated points remain distinct coordinates and $d$ is the supremum of shattered lengths. Indexed shattering and VC dimension of a binary class

[F2]

$Π_{H} (m)$ is the supremum of trace cardinalities on indexed $m$ -tuples. Growth function of a binary hypothesis class

[F3]

For every integer $m \geq 0$ , $Π_{H} (m) \leq \sum_{j = 0}^{d} (\binom{m}{j})$ , and for $1 \leq d \leq m$ it is at most $(e m / d)^{d}$ . Sauer–Shelah growth bound for indexed samples

[F4]

Population risk is the integral of the nonnegative loss and empirical risk is its sample average; for zero-one loss they are the error probability and the sample error fraction. Population and empirical risk

[F5]

For each fixed measurable classifier, its population and empirical risks are measurable functions of the sample. Population and empirical risks are measurable

[F6]

IID observations are independent and have the same law; their finite product law exists and has the rectangle formula; bounded measurable functions on a product probability space may be integrated in either order. Identical distribution and IID families, For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique, Independent random elements have product joint law, Fubini's theorem for L^1 functions on a sigma-finite product

[A1]

Assume the Axiom of Choice for the VC branch. The supplied McDiarmid inequality assumes AC through its conditional-expectation proof. The Axiom of Choice

[F7]

Under AC, if a measurable integrable function on a finite product probability space changes by at most $c_{i}$ when coordinate $i$ alone changes, then its upper tail is at most $\exp (- 2 t^{2} / \sum_{i} c_{i}^{2})$ . McDiarmid bounded-differences inequality

[F8]

For a finite nonempty class $G$ of measurable $[0, 1]$ functions, $\Pr {\sup_{g \in G} ∣ P_{m} g - P g ∣ \geq t} \leq 2 ∣ G ∣ e^{- 2 m t^{2}}$ , and this finite-class proof is choice-free. Uniform deviation bound for a finite unit-range class

[F9]

If $0 \leq Y \leq 1$ almost surely, then $E e^{λ (Y - E Y)} \leq e^{λ^{2} / 8}$ for every real $λ$ . The Hoeffding MGF bound for a variable in a unit interval

[F10]

The natural logarithm is increasing and obeys the product law. The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

[F11]

Expectation is linear and monotone for integrable real random variables. Linearity, monotonicity, and the modulus bound for expectation

[F12]

For all $x, y \in R$ and $0 \leq t \leq 1$ , $\exp ((1 - t) x + t y) \leq (1 - t) \exp (x) + t \exp (y)$ . The two-point convexity inequality for the exponential function

Proof

Given: The objects and assumptions of the Statement.

1.1F4F5givenconstruct

Put $g_{h} (x, y) : = 1 {h (x) \neq y}$ . Its unit-level set is $(h^{- 1} {0} \times {1}) \cup (h^{- 1} {1} \times {0})$ , so each $g_{h}$ is measurable and takes values in $[0, 1]$ . By [F4]–[F5], $P g_{h} = R_{P} (h)$ and $P_{m} g_{h} = {\hat{R}}_{S} (h)$ are well-defined, measurable risk functions; the assumed supremum measurability applies to their deviations.

2.1F6F11givenstep 1.1

For an independent IID copy $S^{'}$ of $S$ , every coordinate of $S^{'}$ has law $P$ ; the product-law and Fubini facts in [F6], together with finite expectation linearity [F11], give $R_{P} (h) = E_{S^{'}} P_{m}^{'} g_{h}$ for every $h$ . Thus $Φ (S) : = \sup_{h \in H} (R_{P} (h) - P_{m} g_{h}) \leq E_{S^{'}} \sup_{h \in H} (P_{m}^{'} g_{h} - P_{m} g_{h})$ . The integrand is bounded and measurable, so product-law invariance and Fubini [F6] allow integration over $S, S^{'}$ . For each fixed sign vector $σ$ , swapping $Z_{i}$ with $Z_{i}^{'}$ whenever $σ_{i} = - 1$ preserves their joint product law; averaging over the finite sign space therefore leaves this expectation unchanged after inserting $σ_{i}$ into each difference.

3.1F6F11step 2.1algebra

Subadditivity of the supremum and expectation linearity [F11] give $E Φ (S) \leq 2 E_{S, σ} {\hat{R}}_{S} (G_{H})$ , where ${\hat{R}}_{S} (G_{H}) = E_{σ} \sup_{h} m^{- 1} \sum_{i} σ_{i} g_{h} (Z_{i})$ . Writing $\tilde{h} = 2 h - 1$ and ${\tilde{Y}}_{i} = 2 Y_{i} - 1$ gives $g_{h} (Z_{i}) = (1 - \tilde{h} (X_{i}) {\tilde{Y}}_{i}) / 2$ ; the sign-only term has mean zero and $- σ_{i} {\tilde{Y}}_{i}$ are again independent uniform signs, so ${\hat{R}}_{S} (G_{H}) = \frac{1}{2} E_{σ} \sup_{h} m^{- 1} \sum_{i} σ_{i} \tilde{h} (X_{i})$ .

4.1F2F9F10F12step 2.1step 3.1algebra

For a fixed sample, the set $V_{S} = {(\tilde{h} (X_{1}), \dots, \tilde{h} (X_{m})) : h \in H}$ has $∣ V_{S} ∣ \leq Π_{H} (m)$ and each vector has Euclidean norm $\sqrt{m}$ . For a fixed $v \in {- 1, + 1}^{m}$ , $Y_{i} = (1 + σ_{i} v_{i}) / 2$ is in $[0, 1]$ with mean $1 / 2$ ; applying [F9] at parameter $2 λ$ gives $E e^{λ σ_{i} v_{i}} \leq e^{λ^{2} / 2}$ . Expanding the finite uniform sign sum factors over coordinates, so $E_{σ} e^{λ \sum_{i} σ_{i} v_{i}} \leq e^{m λ^{2} / 2}$ . For a finite $V$ of size $N$ , $e^{λ \max_{v} \sum_{i} σ_{i} v_{i}} \leq \sum_{v} e^{λ \sum_{i} σ_{i} v_{i}}$ . On the finite sign space, the two-point convexity inequality [F12] gives $e^{λ E_{σ} \max_{v} \sum_{i} σ_{i} v_{i}} \leq E_{σ} e^{λ \max_{v} \sum_{i} σ_{i} v_{i}}$ ; its equal-weight finite form follows by induction over its $q = 2^{m}$ outcomes, applying [F12] to the mean of the first $q - 1$ outcomes and the last outcome with weights $(q - 1) / q$ and $1 / q$ . Taking logarithms using [F10] yields $E_{σ} \max_{v \in V} m^{- 1} \sum_{i} σ_{i} v_{i} \leq \log N / (m λ) + λ / 2$ . Optimizing $λ > 0$ gives $\sqrt{2 \log N / m}$ (and the bound is $0$ if $N = 1$ ). By steps 2.1–3.1, $E Φ (S) \leq \sqrt{2 \log Π_{H} (m) / m}$ .

5.1A1F3F7step 4.1algebra

By [F3], when $1 \leq d \leq m$ the preceding expectation is at most $\sqrt{2 d \log (e m / d) / m}$ . Changing one sample coordinate changes $Φ (S)$ by at most $1 / m$ , because every $g_{h}$ is $[0, 1]$ -valued. Apply [F7] with $c_{i} = 1 / m$ and $t = \sqrt{\log (1 / δ) / (2 m)}$ ; since $\sum_{i} c_{i}^{2} = 1 / m$ , with probability at least $1 - δ$ we have $Φ (S) \leq E Φ (S) + t$ , which is the stated VC branch.

6.1F1F4F8F10givenalgebra∎

If $d = 0$ , no two distinct functions in $H$ can differ at any point, since that point would be shattered; hence $H$ contains one function. If $H$ is finite, the loss class ${g_{h} : h \in H}$ is finite with size at most $∣ H ∣$ . Put $t = \sqrt{(\log ∣ H ∣ + \log (2 / δ)) / (2 m)}$ ; then $2 ∣ H ∣ e^{- 2 m t^{2}} = δ$ by [F10]. Applying [F8] at this $t$ proves the choice-free branch, including the $d = 0$ case.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

89 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., Theorems 3.3, 3.5, 3.7, Corollary 3.8, and Corollary 3.19 (standard reference, not scraped)
Peter L. Bartlett and Shahar Mendelson, Rademacher and Gaussian Complexities: Risk Bounds and Structural Results, Theorem 5 and Appendix B (standard reference, not scraped)