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.

Rademacher uniform generalization bounds

Statement

Assume the Axiom of Choice (AC). Let $(Z, A, P)$ be a probability space, let $m \geq 1$ , and let $G$ be a nonempty class of measurable functions $g : Z \to [0, 1]$ . Take $S = (Z_{1}, \dots, Z_{m})$ to be the coordinate sample with law $P^{m}$ . Put $P_{m} g = m^{- 1} \sum_{i} g (Z_{i})$ and $\overline{G} : = {1 - g : g \in G}$ . Assume the sample, independent-copy and sign suprema over $G$ and $\overline{G}$ used in the displayed claims and the symmetrization argument are measurable. Let $σ_{1}, \dots, σ_{m}$ be independent uniform signs, and let

${\hat{R}}_{S} (G) : = E_{σ} \sup_{g \in G} \frac{1}{m} \sum_{i = 1}^{m} σ_{i} g (Z_{i}), R_{m} (G) : = E_{S \sim P^{m}} {\hat{R}}_{S} (G),$

where the $σ_{i}$ are independent uniform signs, and let $δ \in (0, 1)$ . Each of the following four guarantees holds with probability at least $1 - δ$ over $S$ :

$\forall g \in G, P g \leq P_{m} g + 2 R_{m} (G) + \sqrt{\frac{\log (1 / δ)}{2 m}},$

$\forall g \in G, P g \leq P_{m} g + 2 {\hat{R}}_{S} (G) + 3 \sqrt{\frac{\log (2 / δ)}{2 m}},$

$\sup_{g \in G} ∣ P g - P_{m} g ∣ \leq 2 R_{m} (G) + \sqrt{\frac{\log (2 / δ)}{2 m}},$

$\sup_{g \in G} ∣ P g - P_{m} g ∣ \leq 2 {\hat{R}}_{S} (G) + 3 \sqrt{\frac{\log (4 / δ)}{2 m}} .$

The four guarantees are separate probability statements. The choice axiom is used through the bounded-differences theorem.

Statement references

One-sided Rademacher complexity: fixes the one-sided empirical and expected complexities and their $1 / m$ normalization.

One-sided Rademacher symmetrization bound: bounds the expected one-sided deviation by twice the expected complexity.

McDiarmid bounded-differences inequality: supplies bounded-differences concentration under AC.

The Axiom of Choice: AC is the stated set-theoretic axiom carried by the concentration theorem.

The natural logarithm as the inverse of the exponential function: defines $\log$ as the inverse of the exponential on positive inputs.

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: gives the reciprocal law $\log (1 / x) = - \log x$ and monotonicity of $\log$ .

Basic identities for a probability measure: gives finite subadditivity for the union bounds.

Mohri et al., Theorem 3.3 and complete proof, printed pp. 31–33: proves both one-sided bounds with the stated constants in the adopted normalization.

Bartlett and Mendelson, Theorems 5 and 8 with proofs, printed pp. 464–467 and 479–480: gives independent risk-bound proofs in its separate absolute/ $2 / m$ convention.

Facts & Assumptions

Given: AC, IID observations with law $P$ , a nonempty measurable class of $[0, 1]$ -valued functions, measurable suprema, $m \geq 1$ and $0 < δ < 1$ .

[A1]

AC states that every family of nonempty sets has a choice function. It is invoked only through the McDiarmid supplier, whose theorem assumes AC and whose proof uses it in the conditional-expectation / martingale construction. The Axiom of Choice

[F1]

For $g \in G$ , $P g = \int g d P$ ; ${\hat{R}}_{S} (G)$ is the sign-average one-sided supremum with normalization $1 / m$ , and $R_{m} (G) = E_{S} {\hat{R}}_{S} (G)$ . One-sided Rademacher complexity

[F2]

For an IID sample and measurable suprema, $E_{S} \sup_{g} (P g - P_{m} g) \leq 2 R_{m} (G)$ ; this expectation inequality is choice-free. One-sided Rademacher symmetrization bound

[F3]

If a product-measurable integrable function of independent coordinates changes by at most $c_{i}$ when coordinate $i$ changes, AC gives the upper-tail bound $P {f - E f \geq t} \leq \exp (- 2 t^{2} / \sum_{i} c_{i}^{2})$ ; applying it to $- f$ gives the lower-tail version. McDiarmid bounded-differences inequality

[F4]

For $x > 0$ , $\log x$ is the unique real $y$ with $\exp (y) = x$ . The natural logarithm as the inverse of the exponential function

[F5]

$\log$ is strictly increasing, $\log 1 = 0$ , and $\log (1 / x) = - \log x$ for $x > 0$ ; it is the inverse of the exponential on positive inputs. Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

[F6]

IID means the sample coordinates are mutually independent and have the common law $P$ . Identical distribution and IID families

[F7]

A finite union of events has probability at most the sum of their probabilities. Basic identities for a probability measure

Proof

Given: The hypotheses in the Statement.

1.1A1F1F2F3F4F5F6given

Put $Ψ (S) : = \sup_{g \in G} (P g - P_{m} g)$ . Changing one coordinate changes each term in this supremum by at most $1 / m$ , hence $∣ Ψ (S) - Ψ (S^{'}) ∣ \leq 1 / m$ . By the Statement, $Ψ$ is measurable, and it is bounded because $0 \leq g \leq 1$ . Since $0 < δ < 1$ , [F5] and $m \geq 1$ give $t : = \sqrt{\log (1 / δ) / (2 m)} > 0$ ; [F4]–[F5] give $\exp (- 2 m t^{2}) = δ$ . McDiarmid [F3] with $c_{i} = 1 / m$ gives $Ψ (S) \leq E Ψ (S) + t$ with probability at least $1 - δ$ , and [F2] bounds its expectation by $2 R_{m} (G)$ . This proves the first one-sided bound.

1.2F1givenalgebra

For each fixed sample, ${\hat{R}}_{S} (\overline{G}) = E_{σ} [m^{- 1} \sum_{i} σ_{i} + \sup_{g \in G} m^{- 1} \sum_{i} (- σ_{i}) g (Z_{i})]$ . The first term has mean zero and $- σ$ has the same uniform law as $σ$ , so this equals ${\hat{R}}_{S} (G)$ ; taking expectations gives $R_{m} (\overline{G}) = R_{m} (G)$ .

2.1A1F1F3F4F5F6step 1.1given

For each fixed sign vector, changing one observation changes every $m^{- 1} \sum_{i} σ_{i} g (Z_{i})$ by at most $1 / m$ , since $g$ takes values in $[0, 1]$ ; the same bound holds for the supremum and then for its sign average ${\hat{R}}_{S} (G)$ . This statistic is bounded and measurable by the Statement. With $t = \sqrt{\log (1 / δ) / (2 m)} > 0$ as in step 1.1, [F3] applied to its negative gives $R_{m} (G) \leq {\hat{R}}_{S} (G) + t$ with probability at least $1 - δ$ .

2.2F1F7step 1.1step 1.2algebra

For $h = 1 - g$ , $P h - P_{m} h = P_{m} g - P g$ . Apply step 1.1 to $G$ and $\overline{G}$ with failure probability $δ / 2$ each. By [F7] and step 1.2, both deviations are at most $2 R_{m} (G) + \sqrt{\log (2 / δ) / (2 m)}$ except on an event of probability at most $δ$ . This proves the first two-sided bound.

3.1F1F4F5F7step 1.1step 2.1algebra

Apply step 1.1 with failure probability $δ / 2$ and step 2.1 with failure probability $δ / 2$ . By [F7], both events hold with probability at least $1 - δ$ . Since $2 / δ > 1$ , [F5] gives $t : = \sqrt{\log (2 / δ) / (2 m)} > 0$ ; combining the two bounds gives $Ψ (S) \leq 2 R_{m} (G) + t \leq 2 {\hat{R}}_{S} (G) + 3 t$ . This is the second one-sided guarantee.

4.1F1F7step 1.2step 3.1algebra∎

Apply step 3.1 to $G$ and $\overline{G}$ with failure probability $δ / 2$ each. Their complexities agree by step 1.2, and their upper deviations are $\sup_{g} (P g - P_{m} g)$ and $\sup_{g} (P_{m} g - P g)$ , respectively. By [F7] the two bounds hold together with probability at least $1 - δ$ , giving the last two-sided bound with $\log (4 / δ)$ .

Depends on

Used by

Dependency tree · two levels

43 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, JMLR 3 (2002), Theorems 5 and 8 with proofs (standard reference, not scraped)