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.

Finite-class agnostic ERM bound

Statement

Let $(X, Σ_{X})$ be a measurable space, let $P$ be a probability law on $X \times {0, 1}$ , and let $H$ be a finite nonempty class of measurable classifiers $h : X \to {0, 1}$ . Let $Z_{i} = (X_{i}, Y_{i})$ , $1 \leq i \leq m$ , be IID with law $P$ , where $m \geq 1$ , and define $R_{P} (h) = P {h (X) \neq Y}$ and ${\hat{R}}_{S} (h) = m^{- 1} \sum_{i = 1}^{m} 1 {h (X_{i}) \neq Y_{i}}$ . With natural logarithms, for $0 < δ < 1$ put

$a_{m, H, δ} : = \sqrt{\frac{\log ∣ H ∣ + \log (2 / δ)}{2 m}} .$

Then, with probability at least $1 - δ$ , both $∣ R_{P} (h) - {\hat{R}}_{S} (h) ∣ \leq a_{m, H, δ}$ for every $h \in H$ and

$R_{P} ({\hat{h}}_{η} (S)) - \inf_{h \in H} R_{P} (h) \leq 2 a_{m, H, δ} + η,$

for each fixed finite tolerance $η \geq 0$ , where ${\hat{h}}_{η}$ is the measurable finite-list empirical-risk selector applied with tolerance $η$ to an ordered list containing every member of $H$ exactly once. In particular, exact ERM ( $η = 0$ ) has excess risk at most $2 a_{m, H, δ}$ . The conclusion is agnostic: it assumes no zero-risk classifier. No form of the Axiom of Choice is assumed.

Statement references

Realizable and agnostic PAC learning: defines realizable and agnostic PAC learning for finite measurable binary classes.

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

Uniform deviation bound for a finite unit-range class: gives the choice-free two-sided tail bound for finite classes of measurable functions in $[0, 1]$ .

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

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: establishes that $\log$ is increasing and obeys the product, quotient, and reciprocal laws.

Finite-list empirical risk minimization: specifies the deterministic finite-list ERM selector.

The finite-list ERM selector is measurable: proves that selector measurable and exact or approximate ERM.

Facts & Assumptions

Given: A measurable binary classification problem, a finite nonempty measurable classifier class $H$ , IID observations $Z_{1}, \dots, Z_{m}$ with law $P$ , $m \geq 1$ , $0 < δ < 1$ , and a finite tolerance $η \geq 0$ .

[A1]

No form of the Axiom of Choice is assumed; the finite-list selector uses the given finite ordering, and the uniform-deviation supplier states that its proof is choice-free.

[F1]

For a finite nonempty class $G$ of measurable functions $g : Z \to [0, 1]$ and IID observations with law $P$ , $P {\sup_{g \in G} ∣ P_{m} g - P g ∣ \geq t} \leq 2 ∣ G ∣ e^{- 2 m t^{2}}$ for every $t > 0$ ; its proof uses scalar exponential moments and finite independence and does not assume choice. Uniform deviation bound for a finite unit-range class

[F2]

A supervised prediction problem has measurable instance and label spaces, a joint law on their product, a class of measurable predictors, and a measurable loss. Supervised prediction problems

[F3]

Population risk is the integral of the loss under the joint law, and empirical risk is the average loss on the ordered sample. With binary zero-one loss these are $P {h (X) \neq Y}$ and $m^{- 1} \sum_{i} 1 {h (X_{i}) \neq Y_{i}}$ . Population and empirical risk

[F4]

An $η$ -approximate ERM has empirical risk at most the empirical infimum plus $η$ when that infimum is finite; an exact ERM attains the infimum. Empirical risk minimizers

[F5]

On a finite ordered list with finite empirical risks, the finite-list procedure returns the first list entry whose empirical risk is at most the minimum plus $η$ ; at $η = 0$ it returns a first exact minimizer. Finite-list empirical risk minimization

[F6]

For a finite ordered list of measurable predictors and finite $η \geq 0$ , the finite-list selector is measurable and is an $η$ -approximate ERM; when $η = 0$ it is an exact ERM. The finite-list ERM selector is measurable

[F7]

IID means the observations are mutually independent and identically distributed. Identical distribution and IID families

[F8]

The natural logarithm is increasing, $\log 1 = 0$ , and obeys the product, quotient, and reciprocal laws; it is the inverse of 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

Proof

Given: The hypotheses in the Statement.

1.1givenF2F3F7A1construct

For each $h \in H$ , define $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})$ , a measurable union of rectangles because $h$ is measurable and ${0, 1}$ is discrete. Thus $g_{h}$ is measurable and $[0, 1]$ -valued; $G : = {g_{h} : h \in H}$ is finite and nonempty with $∣ G ∣ \leq ∣ H ∣$ . By [F3], $P g_{h} = R_{P} (h)$ and $P_{m} g_{h} = {\hat{R}}_{S} (h)$ .

2.1F1F7F8step 1.1A1algebra

By [F7], the observations meet the IID hypothesis of [F1]. Put $a = a_{m, H, δ}$ . Since $∣ H ∣ \geq 1$ and $2 / δ > 1$ , [F8] makes the numerator positive, so $a > 0$ . Apply [F1] to $G$ at $t = a$ . By [F8], $\log ∣ H ∣ + \log (2 / δ) = \log (2 ∣ H ∣ / δ)$ and $e^{- \log (2 ∣ H ∣ / δ)} = δ / (2 ∣ H ∣)$ . Hence $2 ∣ G ∣ e^{- 2 m a^{2}} \leq 2 ∣ H ∣ e^{- 2 m a^{2}} = δ$ . With probability at least $1 - δ$ every $h \in H$ satisfies $∣ R_{P} (h) - {\hat{R}}_{S} (h) ∣ < a$ , hence also the asserted non-strict bound.

3.1F3F4F5F6step 2.1algebra

On that event, [F6] gives ${\hat{R}}_{S} ({\hat{h}}_{η}) \leq \inf_{h \in H} {\hat{R}}_{S} (h) + η$ . The deviation bound gives $R_{P} ({\hat{h}}_{η}) \leq {\hat{R}}_{S} ({\hat{h}}_{η}) + a$ and ${\hat{R}}_{S} (h) \leq R_{P} (h) + a$ for every $h$ . Hence $\inf_{g \in H} {\hat{R}}_{S} (g) \leq R_{P} (h) + a$ for every $h \in H$ , and taking the infimum over $h$ gives $\inf_{g \in H} {\hat{R}}_{S} (g) \leq \inf_{h \in H} R_{P} (h) + a$ . Combining these inequalities gives $R_{P} ({\hat{h}}_{η}) - \inf_{h \in H} R_{P} (h) \leq 2 a + η$ .

4.1step 2.1step 3.1∎

The event from step 2.1 has probability at least $1 - δ$ , and step 3.1 establishes both stated inequalities on that event. This proves the claim for arbitrary $P$ , whether or not the class is realizable.

Depends on

Used by

Finite-class realizable and agnostic sample complexity Theorem
Private finite-class ERM excess-risk bound Theorem

Dependency tree · two levels

39 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., Chapter 2 Theorem 2.13 and proof (standard reference, not scraped)
Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Chapter 4 §4.2 and Corollary 4.6 (standard reference, not scraped)