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 Rademacher symmetrization bound

Statement

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]$ . Let $S = (Z_{1}, \dots, Z_{m})$ be IID with law $P$ , let $S^{'} = (Z_{1}^{'}, \dots, Z_{m}^{'})$ be an independent IID copy on a finite product probability extension, and let $σ_{1}, \dots, σ_{m}$ be independent uniform signs independent of both samples. Write $P_{m} g = m^{- 1} \sum_{i} g (Z_{i})$ and $P_{m}^{'} g = m^{- 1} \sum_{i} g (Z_{i}^{'})$ . Assume the random suprema $\sup_{g} (P g - P_{m} g)$ , $\sup_{g} (P_{m}^{'} g - P_{m} g)$ , $\sup_{g} \sum_{i} σ_{i} (g (Z_{i}^{'}) - g (Z_{i}))$ , and $\sup_{g} \sum_{i} σ_{i} g (Z_{i})$ are measurable on their respective product sigma algebras. Then, with $R_{m} (G)$ the expected one-sided Rademacher complexity,

$E_{S} \sup_{g \in G} (P g - P_{m} g) \leq 2 R_{m} (G) .$

This is a one-sided expectation inequality; it does not assert a tail bound or an absolute-value deviation bound. No choice axiom is assumed.

Statement references

One-sided Rademacher complexity: $R_{m} (G)$ is the expected empirical one-sided sign supremum with normalization $1 / m$ .

Mohri et al., Theorem 3.3 proof, printed pp. 31–33: the complete ghost-sample and sign-symmetrization argument for the one-sided bound.

Bartlett and Mendelson, Theorem 8 proof, printed pp. 466–467: an independent ghost-sample proof in their different $2 / m$ absolute-value convention.

Facts & Assumptions

Given: A probability law $P$ , a nonempty measurable $[0, 1]$ -valued class, an IID sample, an independent copy, independent uniform signs and the stated measurability of the suprema.

[A1]

The random suprema over the sample, independent copy and signs named in the Statement are measurable.

[F1]

For each $g \in G$ , $P g = \int g d P$ , $P_{m} g = m^{- 1} \sum_{i} g (Z_{i})$ , and $R_{m} (G) = E_{S} E_{σ} \sup_{g \in G} m^{- 1} \sum_{i} σ_{i} g (Z_{i})$ . One-sided Rademacher complexity

[F2]

IID means mutual independence with common law; a finite family of independent random elements has product joint law. Identical distribution and IID families, Independent random elements have product joint law

[F3]

For a measurable bounded $g$ and a random element with law $P$ , its expectation is $\int g d P$ . Change of variables for expectation

[F4]

A finite product measure is determined by its rectangle values. Consequently, permuting coordinates of a finite product of the same probability law preserves that product law. For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique

[F5]

Fubini gives equality of product and iterated integrals for an integrable product-measurable function on sigma-finite factors. Here each factor carries a probability measure and is sigma-finite, while the product-measurable sample-copy supremum is bounded on a probability product and hence integrable. Fubini's theorem for L^1 functions on a sigma-finite product

Proof

Given: The objects and hypotheses in the Statement.

1.1A1F1F2F3F5givenalgebra

For each fixed sample $S$ and each $g \in G$ , [F2]–[F3] give $E_{S^{'}} P_{m}^{'} g = P g$ , so $P g - P_{m} g = E_{S^{'}} (P_{m}^{'} g - P_{m} g)$ . For any bounded family $X_{g}$ , $\sup_{g} E X_{g} \leq E \sup_{g} X_{g}$ , since each $E X_{g}$ is at most $E \sup_{h} X_{h}$ . Applying this conditionally on $S$ and integrating, with [F5] to identify the iterated and joint product expectations, gives $E_{S} \sup_{g} (P g - P_{m} g) \leq E_{S, S^{'}} \sup_{g} (P_{m}^{'} g - P_{m} g)$ .

2.1A1F2F4step 1.1

By [F2], the $2 m$ coordinates of $(S, S^{'})$ have product law $P^{2 m}$ . For each fixed sign vector, swap $Z_{i}$ and $Z_{i}^{'}$ exactly when $σ_{i} = - 1$ . This coordinate permutation preserves the product law by [F4] and sends each difference $g (Z_{i}^{'}) - g (Z_{i})$ to $σ_{i} (g (Z_{i}^{'}) - g (Z_{i}))$ . Averaging over the finite sign space gives $E_{S, S^{'}} \sup_{g} (P_{m}^{'} g - P_{m} g) = E_{S, S^{'}, σ} \sup_{g} m^{- 1} \sum_{i} σ_{i} (g (Z_{i}^{'}) - g (Z_{i}))$ .

3.1F1F2step 1.1step 2.1algebra∎

For every pair of samples and sign vector, subadditivity gives $\sup_{g} m^{- 1} \sum_{i} σ_{i} (g (Z_{i}^{'}) - g (Z_{i})) \leq \sup_{g} m^{- 1} \sum_{i} σ_{i} g (Z_{i}^{'}) + \sup_{g} m^{- 1} \sum_{i} (- σ_{i}) g (Z_{i})$ . The first term has expectation $R_{m} (G)$ by [F1] and the law of $S^{'}$ ; the second has the same expectation because $- σ$ is uniform on the sign cube and $S$ has law $P^{m}$ by [F2]. Combining with steps 1.1–2.1 proves the result.

Depends on

Used by

Rademacher uniform generalization bounds Theorem

Dependency tree · two levels

33 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), Theorem 8 and proof (standard reference, not scraped)