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

ERM excess risk from Rademacher uniform deviation

Statement

Assume AC. Let $(X, Σ_{X})$ , $(Y, Σ_{Y})$ , and $(A, Σ_{A})$ be nonempty measurable spaces, let $P$ be a probability measure on $X \times Y$ , let $H$ be a nonempty class of measurable predictors $h : X \to A$ , and let $ℓ : A \times Y \to [0, 1]$ be measurable. For $h \in H$ , define $g_{h} (x, y) : = ℓ (h (x), y)$ , $G : = {g_{h} : h \in H}$ , and $\overline{G} : = {1 - g : g \in G}$ . Assume the sample, independent-copy, and sign suprema over $G$ and $\overline{G}$ required by the uniform generalization theorem are measurable in their respective product sigma algebras. Let $Z_{i} = (X_{i}, Y_{i})$ be mutually independent with common law $P$ , with $m \geq 1$ , and write

$R_{P} (h) : = P g_{h}, {\hat{R}}_{S} (h) : = P_{m} g_{h} .$

Suppose a measurable prediction rule ${\hat{h}}_{η}$ exists such that ${\hat{h}}_{η} (S) \in H$ for every sample $S$ and each samplewise output is an $η$ -approximate empirical risk minimizer, meaning ${\hat{R}}_{S} ({\hat{h}}_{η} (S)) \leq \inf_{h \in H} {\hat{R}}_{S} (h) + η$ for a fixed finite $η \geq 0$ . Assume $S \mapsto R_{P} ({\hat{h}}_{η} (S))$ is measurable. For $δ \in (0, 1)$ , with independent uniform signs $σ_{i}$ , ${\hat{R}}_{S} (G) = E_{σ} \sup_{g \in G} m^{- 1} \sum_{i} σ_{i} g (Z_{i})$ and $R_{m} (G) = E_{S} {\hat{R}}_{S} (G)$ , each of the following excess-risk bounds holds with probability at least $1 - δ$ :

$R_{P} ({\hat{h}}_{η} (S)) - \inf_{h \in H} R_{P} (h) \leq 4 R_{m} (G) + 2 \sqrt{\frac{\log (2 / δ)}{2 m}} + η,$

$R_{P} ({\hat{h}}_{η} (S)) - \inf_{h \in H} R_{P} (h) \leq 4 {\hat{R}}_{S} (G) + 6 \sqrt{\frac{\log (4 / δ)}{2 m}} + η .$

The two displayed bounds are separate probability guarantees. This corollary asserts no existence of an empirical-risk-minimizing measurable rule for a general class.

Statement references

Supervised prediction problems: supplies measurable observation, prediction, and loss spaces with a joint law.

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

Population and empirical risk: defines population risk as expected loss and empirical risk as its sample average.

Empirical risk minimizers: defines exact and $η$ -approximate ERM rules and does not assert a selector exists for every class.

Population and empirical risks are measurable: proves measurability of induced losses and fixed-predictor risks.

Rademacher uniform generalization bounds: supplies the two separate two-sided uniform deviation bounds under AC.

One-sided Rademacher complexity: defines the one-sided empirical and expected complexities used in the conclusion.

The Axiom of Choice: AC is carried because the concentration-based supplier assumes it.

The natural logarithm as the inverse of the exponential function: defines the logarithm appearing in the confidence terms.

Mohri et al., Theorem 3.3 and complete proof, Chapter 3 §3.1: supplies the uniform Rademacher deviations; the two-deviation ERM comparison is proved locally.

Bartlett and Mendelson, Theorem 8 and complete proof, printed pp. 466–467: gives an independent uniform risk-bound argument in a different normalization.

Facts & Assumptions

Given: A supervised prediction problem with bounded measurable loss, IID sample, AC, and an existing measurable $η$ -approximate ERM rule with ${\hat{h}}_{η} (S) \in H$ for every sample $S$ and measurable selected population risk.

[A1]

Assume AC. It is used by the concentration theorem in the uniform-deviation supplier. The Axiom of Choice

[F1]

A supervised problem has nonempty measurable instance, label, and action spaces; a joint law; measurable predictors; and a measurable loss. Supervised prediction problems

[F2]

Population risk is the integral of the loss under $P$ and empirical risk is its sample average. For $g_{h} (x, y) = ℓ (h (x), y)$ these equal $P g_{h}$ and $P_{m} g_{h}$ . Population and empirical risk

[F3]

An $η$ -approximate ERM relative to $H$ belongs to $H$ and has empirical risk at most the empirical infimum plus $η$ when the infimum is finite; the supplied measurable prediction rule has ${\hat{h}}_{η} (S) \in H$ for every sample $S$ , is jointly measurable in sample and new instance, and the definition asserts no selector exists for every class. Empirical risk minimizers

[F4]

The induced loss $g_{h}$ is measurable, and fixed-predictor population and empirical risks are well-defined. Population and empirical risks are measurable

[F5]

With probability at least $1 - δ$ , $\sup_{g \in G} ∣ P g - P_{m} g ∣ \leq 2 R_{m} (G) + \sqrt{\log (2 / δ) / (2 m)}$ . Rademacher uniform generalization bounds

[F6]

With probability at least $1 - δ$ , $\sup_{g \in G} ∣ P g - P_{m} g ∣ \leq 2 {\hat{R}}_{S} (G) + 3 \sqrt{\log (4 / δ) / (2 m)}$ . Rademacher uniform generalization bounds

[F7]

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

Proof

Given: The hypotheses in the Statement.

1.1F1F2F4F5F6F7givenconstruct

For each $h \in H$ , the supervised loss function $g_{h}$ is measurable by [F1] and [F4]. By [F2], $R_{P} (h) = P g_{h}$ and ${\hat{R}}_{S} (h) = P_{m} g_{h}$ , so the uniform bounds in [F5]–[F6] control all predictors in $H$ under the IID hypothesis [F7].

2.1F2F3F5step 1.1algebra

On the event in [F5], put $d : = 2 R_{m} (G) + \sqrt{\log (2 / δ) / (2 m)}$ . Then every $h$ satisfies $R_{P} (h) \leq {\hat{R}}_{S} (h) + d$ and ${\hat{R}}_{S} (h) \leq R_{P} (h) + d$ . By [F3], ${\hat{R}}_{S} ({\hat{h}}_{η}) \leq \inf_{h} {\hat{R}}_{S} (h) + η$ . Since ${\hat{h}}_{η} (S) \in H$ by [F3], applying the first inequality to ${\hat{h}}_{η}$ and taking the infimum in the second gives $R_{P} ({\hat{h}}_{η}) - \inf_{h} R_{P} (h) \leq d + \inf_{h} {\hat{R}}_{S} (h) + η - \inf_{h} R_{P} (h) \leq 2 d + η$ , where $\inf_{h} {\hat{R}}_{S} (h) \leq \inf_{h} R_{P} (h) + d$ .

2.2F2F3F6step 1.1algebra

On the event in [F6], put $d : = 2 {\hat{R}}_{S} (G) + 3 \sqrt{\log (4 / δ) / (2 m)}$ . The two inequalities $R_{P} (h) \leq {\hat{R}}_{S} (h) + d$ and ${\hat{R}}_{S} (h) \leq R_{P} (h) + d$ hold for every $h$ . Since ${\hat{h}}_{η} (S) \in H$ , [F3] permits applying the first inequality to the selected predictor and gives $R_{P} ({\hat{h}}_{η}) - \inf_{h} R_{P} (h) \leq d + \inf_{h} {\hat{R}}_{S} (h) + η - \inf_{h} R_{P} (h) \leq 2 d + η$ , using $\inf_{h} {\hat{R}}_{S} (h) \leq \inf_{h} R_{P} (h) + d$ .

3.1A1F5F6step 2.1step 2.2algebra∎

The events in [F5] and [F6] are the AC-dependent concentration branch [A1]. Each has probability at least $1 - δ$ ; step 2.1 proves the first displayed excess bound on the [F5] event, and step 2.2 proves the second on the [F6] event. Substituting each value of $d$ from those steps gives respectively $4 R_{m} (G) + 2 \sqrt{\log (2 / δ) / (2 m)} + η$ and $4 {\hat{R}}_{S} (G) + 6 \sqrt{\log (4 / δ) / (2 m)} + η$ . The guarantees are separate.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

30 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)