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 realizable PAC bound

Statement

Let $H$ be a finite nonempty class of measurable classifiers $h : X \to {0, 1}$ on a measurable instance space, and let $P$ be a law on $X \times {0, 1}$ for which some $h^{*} \in H$ has zero population zero-one risk. Let $Z_{i} = (X_{i}, Y_{i})$ , $1 \leq i \leq m$ , be IID with law $P$ , and let ${\hat{h}}_{0} (S)$ be the measurable exact ERM returned by the finite-list selector on an ordered enumeration of $H$ . For $0 < ϵ, δ < 1$ and integer $m \geq 1$ , if

$m \geq \frac{\log ∣ H ∣ + \log (1 / δ)}{ϵ},$

then $P_{S} {R_{P} ({\hat{h}}_{0} (S)) \leq ϵ} \geq 1 - δ$ . This is a realizable guarantee; it makes no claim for distributions without a zero-risk member of $H$ . The proof is choice-free.

Statement references

Realizable and agnostic PAC learning: defines realizability by existence of a zero-risk classifier and the realizable PAC criterion.

Finite-list empirical risk minimization: supplies an exact finite-list ERM selector.

The finite-list ERM selector is measurable: establishes the selector’s measurability and exact-minimizer property.

The natural logarithm as the inverse of the exponential function: defines the natural logarithm as the inverse of the exponential on positive reals.

Facts & Assumptions

Given: A finite nonempty class of measurable binary classifiers, an IID sample of size $m \geq 1$ with law $P$ , a classifier $h^{*}$ with $R_{P} (h^{*}) = 0$ , and $0 < ϵ, δ < 1$ .

[A1]

No form of the Axiom of Choice is assumed or used; the learner selects from a given finite ordered list.

[F1]

IID means the sample coordinates are mutually independent and have the same law. Identical distribution and IID families

[F2]

Measurable coordinatewise functions of an independent family remain independent. Measurable coordinatewise functions preserve independence

[F3]

For any finite list of events, the probability of their union is at most the sum of their probabilities. Basic identities for a probability measure

[F4]

If $0 \leq p \leq 1$ and $m$ is natural, then $(1 - p)^{m} \leq e^{- m p}$ . $1 + x \leq \exp (x)$ for every real $x$ , hence $(1 - p)^{m} \leq \exp (- m p)$

[F5]

For finite empirical risks, the finite-list procedure at tolerance zero returns a first exact minimizer. Finite-list empirical risk minimization

[F6]

The finite-list selector is measurable and an exact ERM when its tolerance is zero. The finite-list ERM selector is measurable

[F7]

Population zero-one risk is the probability of classification error, and empirical zero-one risk is the average of the sample error indicators. Population and empirical risk

[F8]

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

[F9]

The exponential is positive for every real input and $\exp (- x) = 1 / \exp (x)$ . The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$

Proof

Given: The hypotheses in the Statement.

1.1givenF1F2F4F7A1

Fix $h \in H$ with $R_{P} (h) > ϵ$ and put $I_{i} = 1 {h (X_{i}) \neq Y_{i}}$ . The error indicator is a measurable function of $Z_{i}$ , so [F1]–[F2] make $I_{1}, \dots, I_{m}$ independent with $P (I_{i} = 1) = R_{P} (h)$ . Therefore the probability that $h$ is consistent on the full sample is $P (I_{1} = \dots = I_{m} = 0) = (1 - R_{P} (h))^{m} \leq (1 - ϵ)^{m} \leq e^{- m ϵ}$ by [F4].

2.1F3step 1.1

The bad-consistent event is the union over $h \in H$ with $R_{P} (h) > ϵ$ of the event that $h$ is consistent. By [F3] and step 1.1 its probability is at most $∣ H ∣ e^{- m ϵ}$ .

3.1givenF3F5F6F7step 2.1A1

Since $R_{P} (h^{*}) = 0$ , each observation disagrees with $h^{*}$ on a null event; the finite union of these null events has probability zero. Thus $h^{*}$ is sample-consistent almost surely, the empirical minimum is zero, and [F5]–[F6] make ${\hat{h}}_{0}$ a measurable consistent classifier almost surely. If its risk exceeded $ϵ$ , it would be a bad consistent classifier, so the failure event is contained in the event bounded in step 2.1.

4.1givenF8F9step 2.1step 3.1algebra∎

The assumed sample-size inequality gives $m ϵ \geq \log ∣ H ∣ + \log (1 / δ) = \log (∣ H ∣ / δ)$ by [F8]. The argument $∣ H ∣ e^{- m ϵ}$ is positive by [F9], and [F8] yields $\log (∣ H ∣ e^{- m ϵ}) = \log ∣ H ∣ - m ϵ \leq - \log (1 / δ) = \log δ$ . Since $\log$ is increasing, $∣ H ∣ e^{- m ϵ} \leq δ$ . Steps 2.1–3.1 therefore bound the failure probability by $δ$ , proving the claim.

Depends on

Used by

Finite-class realizable and agnostic sample complexity Theorem

Dependency tree · two levels

44 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.5 and proof (standard reference, not scraped)
Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Chapter 2 §2.3.1 and Corollary 2.3 (standard reference, not scraped)