TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generated

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.

Realizable sample complexity for finite-VC classes

Statement

Let $(X, Σ)$ be a nonempty measurable space, let $H$ be a nonempty class of measurable binary functions with finite VC dimension $d$ , put $Z = X \times {0, 1}$ , and let $P$ be a probability law on $Z$ . Fix an integer $m \geq 1$ and a map $A : Z^{m} \to H$ for which $S \mapsto R_{P} (A (S))$ and $S \mapsto {\hat{R}}_{S} (A (S))$ are measurable, where $R_{P} (h) : = P {(x, y) : h (x) \neq y}, {\hat{R}}_{S} (h) : = \frac{1}{m} \sum_{i = 1}^{m} 1 {h (X_{i}) \neq Y_{i}} .$ Suppose $P$ is realizable by $H$ and $A$ is consistent $P^{m}$ -almost surely. For $0 < ϵ < 1$ , assume the events $E_{m, ϵ} : = {S \in Z^{m} : \exists h \in H, R_{P} (h) > ϵ, {\hat{R}}_{S} (h) = 0}$ and $B_{m, ϵ} : = {(S, S^{'}) \in Z^{m} \times Z^{m} : \exists h \in H, R_{P} (h) > ϵ, {\hat{R}}_{S} (h) = 0, {\hat{R}}_{S^{'}} (h) \geq ϵ / 2}$ are measurable in their respective product sigma-algebras; this holds when $H$ is countable. For $0 < ϵ, δ < 1$ and $S \sim P^{m}$ , if $d = 0$ then $R_{P} (A (S)) = 0$ almost surely for every such rule. If $d \geq 1$ and $m \geq \frac{64}{ϵ} [d \log ⁣ (\frac{64 e}{ϵ}) + \log ⁣ (\frac{4}{δ})],$ where $\log$ is natural and $e = \exp (1)$ , then $P {R_{P} (A (S)) \leq ϵ} \geq 1 - δ$ . This is a conditional upper bound for consistent risk-measurable learners; it asserts no existence or computational-efficiency result.

Statement references

Measurable PAC learning criteria for a possibly infinite VC class: defines a realizable distribution and the realizable PAC event for possibly infinite classes, with the required risk measurability.

Mohri et al., Chapter 3, Exercise 3.30: identifies the realizable VC upper-rate problem; the argument here supplies the complete finite-trace proof and explicit sample-size constants.

Bartlett and Mendelson, Theorem 5 and Appendix B: independent classification-risk generalization context; that theorem is not used as a realizable sample-size proof.

Facts & Assumptions

Given: A measurable binary class $H$ with finite VC dimension $d$ , a law $P$ realized by some $h^{*} \in H$ , a consistent risk-measurable rule $A$ , $m \geq 1$ , and $0 < ϵ, δ < 1$ .

[F1]

Realizable PAC learning means that every law with a zero-risk member satisfies the stated high-probability risk event; consistency means ${\hat{R}}_{S} (A (S)) = 0$ . The definition makes no learner-existence claim. Measurable PAC learning criteria for a possibly infinite VC class

[F2]

A finite indexed tuple is shattered when all binary label vectors occur, and $d = VCdim (H)$ . Indexed shattering and VC dimension of a binary class

[F3]

$Π_{H} (n)$ counts the largest number of traces on indexed $n$ -tuples. Growth function of a binary hypothesis class

[F4]

If $1 \leq d \leq n$ , then $Π_{H} (n) \leq (e n / d)^{d}$ . Sauer–Shelah growth bound for indexed samples

[F5]

Population risk is the zero-one error probability and empirical risk is the average error indicator; for each fixed $h$ these are well-defined measurable quantities. Population and empirical risk, Population and empirical risks are measurable

[F6]

IID coordinates have the finite product joint law; finite product probability measures exist, and Tonelli permits integration of the nonnegative event indicators over the two samples. Identical distribution and IID families, For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique, Independent random elements have product joint law, Tonelli's theorem for nonnegative measurable functions on a sigma-finite product

[F7]

Measurable functions of independent observations remain independent, and expectations of products of independent nonnegative variables factor. Measurable coordinatewise functions preserve independence, Expectations factor over finite products of independent random variables

[F8]

The expectation of a finite sum of integrable indicators is the sum of their expectations. Linearity, monotonicity, and the modulus bound for expectation

[F9]

For a nonnegative random variable $W$ and $a > 0$ , $P (W \geq a) \leq E [W] / a$ . Markov's inequality for random variables

[F10]

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

[F11]

The natural logarithm is increasing, satisfies the product law, and $\log x = \int_{1}^{x} d t / t$ for $x > 0$ . The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t

[F12]

The nonnegative integral is monotone; on $[1, 2]$ , $1 / t \geq 1 / 2$ , and on $[1, 5 / 4]$ , $[5 / 4, 3 / 2]$ , and $[3 / 2, 2]$ it is respectively at most $1$ , $4 / 5$ , and $2 / 3$ . Consequently $1 / 2 \leq \log 2 \leq 47 / 60 < 4 / 5$ . Monotonicity and nonnegative homogeneity of the nonnegative integral

[F13]

$e = \exp (1) > 0$ , $\exp (a + b) = \exp (a) \exp (b)$ , and $1 + x \leq \exp (x)$ for every real $x$ . The real exponential function and the number $e$ by a power series, The exponential addition formula $\exp (x + y) = \exp (x) \exp (y)$ , The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ , $1 + x \leq \exp (x)$ for every real $x$ , hence $(1 - p)^{m} \leq \exp (- m p)$

[A1]

No Axiom of Choice is used: the sample partitions, trace patterns, and event unions in the proof are finite, and existential witnesses are used pointwise rather than selected as a sample-dependent function.

Proof

Given: The hypotheses in the Statement.

1.1F1F2givenA1

If $d = 0$ , any two members of $H$ agree at every $x \in X$ , since otherwise the one-point tuple $(x)$ would be shattered. Thus $H$ has one function. Realizability makes that function have zero risk, and every $H$ -valued rule outputs it, proving the $d = 0$ clause.

1.2F5F6F7F8F9F11F12F13givenA1

Suppose $d \geq 1$ and put $L = \log (64 e / ϵ) > 1$ and $D = \log (4 / δ) > 0$ ; the sample-size premise gives $m ϵ \geq 64 (d L + D) > 8$ . Let $E_{S} : = {\exists h \in H : R_{P} (h) > ϵ, {\hat{R}}_{S} (h) = 0}$ and let $B_{S, S^{'}}$ be the event that some such $h$ also has ${\hat{R}}_{S^{'}} (h) \geq ϵ / 2$ , where $S^{'}$ is an independent IID sample. For each fixed $S \in E_{S}$ , fix one witness $h$ for this $S$ only, with no sample-dependent selection function, and let $K_{h} = \sum_{i = 1}^{m} 1 {h (X_{i}^{'}) \neq Y_{i}^{'}}$ . By [F5]–[F8], $K_{h}$ is a sum of independent Bernoulli indicators with mean $m p$ , where $p = R_{P} (h) > ϵ$ . Factorization [F7] gives $E [2^{- K_{h}}] = (1 - p / 2)^{m} \leq e^{- m p / 2}$ by [F13]. On $K_{h} < m p / 2$ , $2^{- K_{h}} > 2^{- m p / 2}$ , so [F9] gives $P (K_{h} < m p / 2) \leq \exp [- m p (1 - \log 2) / 2]$ . From [F11]–[F12], $1 / 2 \leq \log 2 < 4 / 5$ , so this probability is at most $e^{- m p / 10} \leq e^{- m ϵ / 10} \leq e^{- 4 / 5} \leq e^{- \log 2} = 1 / 2$ . Since $m p / 2 > m ϵ / 2$ , this proves $P_{S^{'}} (B_{S, S^{'}} ∣ S) \geq 1 / 2$ for each $S \in E_{S}$ . Integrating the measurable sections by [F6] yields $P (E_{S}) \leq 2 P (B_{S, S^{'}})$ .

2.1F2F3F6F10step 1.2A1

View $2 m$ IID observations as a combined sample $T$ . By [F6], permuting its coordinates preserves its product law, so the joint law of the first and second halves equals the average over all uniform choices of an $m$ -index training subset $I \subseteq [2 m]$ and its complement. For fixed $T$ , each $h$ determines an error-index set $J_{h} = {i : h (X_{i}) \neq Y_{i}}$ , and the number of distinct such sets is at most $Π_{H} (2 m)$ because the labels $Y_{i}$ only flip coordinates of the trace. If $∣ J_{h} ∣ = k > m$ , no training subset can be disjoint from all errors. If $k \leq m$ , the fraction of training subsets disjoint from $J_{h}$ is $\prod_{j = 0}^{k - 1} (m - j) / (2 m - j) \leq 2^{- k}$ : after $j$ specified errors have been assigned to the ghost half, the next specified index lies there with probability $(m - j) / (2 m - j) \leq 1 / 2$ . Therefore only error patterns with $k \geq m ϵ / 2$ can witness $B$ , and the finite union bound [F10] gives $P (B_{S, S^{'}}) \leq Π_{H} (2 m) 2^{- m ϵ / 2}$ .

3.1F1F4step 1.2step 2.1givenalgebra

Combining steps 1.2 and 2.1, $P (E_{S}) \leq 2 Π_{H} (2 m) 2^{- m ϵ / 2}$ . The sample-size hypothesis implies $m \geq d$ , so [F4] at $n = 2 m$ gives $P (E_{S}) \leq 2 (2 e m / d)^{d} 2^{- m ϵ / 2}$ . Put $N_{A} : = {S : {\hat{R}}_{S} (A (S)) > 0}$ . This event is measurable because $S \mapsto {\hat{R}}_{S} (A (S))$ is measurable, and it is $P^{m}$ -null by the almost-sure consistency assumption. For $S \notin N_{A}$ with $R_{P} (A (S)) > ϵ$ , $A (S)$ witnesses $E_{S}$ , so the failure event ${S : R_{P} (A (S)) > ϵ}$ is contained in $E_{S} \cup N_{A}$ .

4.1F11F12F13step 3.1givenalgebra

Put $L = \log (64 e / ϵ)$ , $D = \log (4 / δ)$ , and $M = 64 (d L + D) / ϵ$ . Then $L > 1$ , $D > 0$ , and the hypothesis gives $m \geq M$ . For real $t \geq M$ , define $q (t) = \log 2 + d \log (2 e t / d) - (\log 2) ϵ t / 2$ . Its derivative is $d / t - (\log 2) ϵ / 2 \leq ϵ / (64 L) - ϵ / 4 < 0$ , using $\log 2 \geq 1 / 2$ from [F11]–[F12]; hence $q (m) \leq q (M)$ . The identity $\log (2 e M / d) = L + \log 2 + \log (L + D / d)$ , together with $\log (L + D / d) \leq \log L + D / (d L)$ (from [F11], [F13]), $\log L \leq L$ , $\log 2 \leq L$ , and $\log 2 \geq 1 / 2$ , gives $q (M) \leq L - 13 d L + D / L - 16 D$ . Consequently $q (M) - \log δ \leq L - 13 d L + D / L - 15 D - \log 4 < 0$ , because $d \geq 1$ , $L > 1$ , and $D > 0$ . Exponentiating shows $2 (2 e m / d)^{d} 2^{- m ϵ / 2} \leq δ$ .

5.1step 3.1step 4.1givenA1∎

By step 3.1 the failure event is contained in $E_{S} \cup N_{A}$ , with $P (N_{A}) = 0$ , and step 4.1 bounds $P (E_{S})$ by $δ$ . Hence $P_{S \sim P^{m}} {R_{P} (A (S)) \leq ϵ} \geq 1 - δ$ . The argument used no arbitrary-index choice axiom.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

91 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 3, Exercise 3.30 (standard reference, not scraped)
Peter L. Bartlett and Shahar Mendelson, Rademacher and Gaussian Complexities: Risk Bounds and Structural Results, Theorem 5 and Appendix B (standard reference, not scraped)