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.

VC entropy uniform deviation without a logarithmic sample-size factor

Statement

Let $(X, Σ)$ be a nonempty measurable space, let $H$ be a nonempty class of measurable binary classifiers with finite VC dimension $d$ , and put $Z : = X \times {0, 1}$ with sigma-algebra $Σ_{Z} : = Σ \otimes P ({0, 1})$ . Let $P$ be a probability law on $Z$ , and let $S = (Z_{1}, \dots, Z_{m})$ consist of $m \geq 1$ IID observations with law $P$ . For $h \in H$ , put $g_{h} (x, y) : = 1 {h (x) \neq y}$ , $G_{H} : = {g_{h} : h \in H}$ , and ${\overline{G}}_{H} : = {1 - g : g \in G_{H}}$ . Define $R_{P} (h) : = P {h (X) \neq Y}$ and ${\hat{R}}_{S} (h) : = m^{- 1} \sum_{i = 1}^{m} g_{h} (Z_{i})$ . For measurable $g : Z \to [0, 1]$ , write $P g : = \int g d P$ and $P_{m} g (S) : = m^{- 1} \sum_{i = 1}^{m} g (Z_{i})$ . Let $S^{'} = (Z_{1}^{'}, \dots, Z_{m}^{'})$ be an independent sample with law $P^{m}$ , and write $P_{m}^{'} g : = P_{m} g (S^{'})$ .

Assume the following maps are measurable:

$S \mapsto \sup_{g \in G_{H}} (P g - P_{m} g (S))$ and $S \mapsto \sup_{\overset{ˉ}{g} \in {\overline{G}}_{H}} (P \overset{ˉ}{g} - P_{m} \overset{ˉ}{g} (S))$ on $(Z^{m}, Σ_{Z}^{\otimes m})$ ;
$(S, S^{'}) \mapsto \sup_{g \in G_{H}} (P_{m}^{'} g - P_{m} g (S))$ and $(S, S^{'}) \mapsto \sup_{\overset{ˉ}{g} \in {\overline{G}}_{H}} (P_{m}^{'} \overset{ˉ}{g} - P_{m} \overset{ˉ}{g} (S))$ on $(Z^{m} \times Z^{m}, Σ_{Z}^{\otimes m} \otimes Σ_{Z}^{\otimes m})$ ;
for every fixed $σ \in {- 1, + 1}^{m}$ , the maps $(S, S^{'}) \mapsto \sup_{g \in G_{H}} m^{- 1} \sum_{i = 1}^{m} σ_{i} (g (Z_{i}^{'}) - g (Z_{i}))$ and $(S, S^{'}) \mapsto \sup_{\overset{ˉ}{g} \in {\overline{G}}_{H}} m^{- 1} \sum_{i = 1}^{m} σ_{i} (\overset{ˉ}{g} (Z_{i}^{'}) - \overset{ˉ}{g} (Z_{i}))$ on $(Z^{m} \times Z^{m}, Σ_{Z}^{\otimes m} \otimes Σ_{Z}^{\otimes m})$ ;
for every fixed $σ \in {- 1, + 1}^{m}$ , the maps $S \mapsto \sup_{g \in G_{H}} m^{- 1} \sum_{i = 1}^{m} σ_{i} g (Z_{i})$ and $S \mapsto \sup_{\overset{ˉ}{g} \in {\overline{G}}_{H}} m^{- 1} \sum_{i = 1}^{m} σ_{i} \overset{ˉ}{g} (Z_{i})$ on $(Z^{m}, Σ_{Z}^{\otimes m})$ .

The first pair of maps gives the two one-sided deviation suprema and makes the absolute-deviation supremum in the conclusion measurable. Set $K_{0} : = 3 e^{2} / (e - 1)$ , $K : = 4 K_{0}$ , $A : = 12 e K + 2$ , and $C_{V C} : = 3 \sqrt{8 A} (\sqrt{\log A} + 2 \sqrt{\log 2})$ , where $e : = \exp (1)$ and $\log$ is the natural logarithm. If the Axiom of Choice (AC) is assumed, then for every $0 < δ < 1$ , with probability at least $1 - δ$ ,

$\sup_{h \in H} ∣ R_{P} (h) - {\hat{R}}_{S} (h) ∣ \leq 2 C_{V C} \sqrt{\frac{d + 1}{m}} + \sqrt{\frac{\log (2 / δ)}{2 m}} .$

This is a uniform absolute-deviation bound; it claims neither ERM existence nor a distribution-free lower bound.

Statement references

Mohri et al., Theorem 3.3 and proof: one-sided generalization through ghost-sample symmetrization and bounded differences.

Bartlett and Mendelson, Theorem 5 and Appendix B: an independent Rademacher generalization proof in a different normalization.

Facts & Assumptions

Given: A nonempty finite-VC binary class, an IID sample, measurable deviation suprema, and $0 < δ < 1$ .

[F1]

For every fixed sample, the zero-one loss class $G_{H}$ has one-sided empirical Rademacher complexity at most $C_{V C} \sqrt{(d + 1) / m}$ , with explicit $C_{V C}$ . VC entropy bound for empirical Rademacher complexity

[F2]

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

[F3]

The fixed-class risks are measurable functions of the sample. Population and empirical risks are measurable

[F4]

IID observations have the finite product joint law, and the bounded measurable integrands used in ghost-sample symmetrization satisfy Fubini. 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; the concentration supplier below requires it. The Axiom of Choice

[F5]

Under AC, a measurable integrable function with coordinate oscillations at most $c_{i}$ has upper tail $\Pr {f - E f \geq t} \leq \exp (- 2 t^{2} / \sum_{i} c_{i}^{2})$ . McDiarmid bounded-differences inequality

[F6]

Probability is subadditive on a finite union. Basic identities for a probability measure

[F7]

The natural logarithm is increasing and inverse to the exponential on positive reals. The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The real exponential function and the number $e$ by a power series, The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$

[F8]

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

Proof

Given: The hypotheses in the Statement.

1.1F2F3F4F8givenconstructalgebra

For $h \in H$ , put $g_{h} (x, y) = 1 {h (x) \neq y}$ and define $Φ (S) = \sup_{h \in H} (R_{P} (h) - {\hat{R}}_{S} (h))$ . On a product probability space take an independent IID copy $S^{'}$ . Each coordinate of $S^{'}$ has law $P$ , so product-law marginals and Fubini [F4], together with expectation linearity [F8], give $R_{P} (h) = E_{S^{'}} {\hat{R}}_{S^{'}} (h)$ for every $h$ . Monotonicity of expectation then gives $Φ (S) \leq E_{S^{'}} \sup_{h} ({\hat{R}}_{S^{'}} (h) - {\hat{R}}_{S} (h))$ . The integrand is bounded and measurable by assumption, hence [F4] allows integration in either sample order. For each fixed sign vector, swapping $Z_{i}$ with $Z_{i}^{'}$ at exactly its negative coordinates preserves the joint product law, so the expected supremum is unchanged when each difference is multiplied by $σ_{i}$ . Subadditivity of the supremum and expectation linearity [F8] bound it by the sum of the two expected one-sided empirical Rademacher suprema, which are equal because $σ$ and $- σ$ have the same law. Thus $E Φ (S) \leq 2 E_{S, σ} {\hat{R}}_{S} (G_{H})$ .

2.1A1F1F5F7step 1.1algebra

By [F1], $E Φ (S) \leq 2 C_{V C} \sqrt{(d + 1) / m}$ . Replacing one observation in $S$ changes each ${\hat{R}}_{S} (h)$ by at most $1 / m$ , so the supremum $Φ (S)$ changes by at most $1 / m$ as well. Applying [F5] with $c_{i} = 1 / m$ and $t = \sqrt{\log (2 / δ) / (2 m)}$ gives $\Pr {Φ (S) > E Φ (S) + t} \leq δ / 2$ .

3.1A1F1F4F6F7step 1.1step 2.1algebra∎

The complemented class $\overset{ˉ}{H} = {1 - h : h \in H}$ has the same trace counts and VC dimension as $H$ , and its loss satisfies $g_{1 - h} (x, y) = 1 - g_{h} (x, y)$ . Applying steps 1.1–2.1 to $\overset{ˉ}{H}$ with the same $δ$ and $t$ therefore gives, except on an event of probability at most $δ / 2$ , ${\hat{R}}_{S} (h) - R_{P} (h) \leq 2 C_{V C} \sqrt{(d + 1) / m} + t$ for every $h \in H$ . The finite union bound [F6] combines this lower-deviation event with step 2.1, giving the asserted absolute-deviation bound with probability at least $1 - δ$ .

Depends on

Used by

Agnostic sample complexity for finite-VC ERM Theorem

Dependency tree · two levels

80 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., Theorem 3.3 and proof (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)