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.

Agnostic sample complexity for finite-VC ERM

Statement

Let $(X, Σ)$ be a nonempty measurable space, let $H$ be a nonempty class of measurable binary classifiers with finite VC dimension $d$ , and put $Z : = X \times {0, 1}$ with sigma-algebra $Σ_{Z} : = Σ \otimes P ({0, 1})$ . Let $P$ be any law on $Z$ and let $S = (Z_{1}, \dots, Z_{m}) \sim P^{m}$ be an IID sample with $m \geq 1$ . For $h \in H$ , put $g_{h} (x, y) : = 1 {h (x) \neq y}$ , $G_{H} : = {g_{h} : h \in H}$ , and ${\overline{G}}_{H} : = {1 - g : g \in G_{H}}$ . Define $R_{P} (h) : = P {h (X) \neq Y}$ and ${\hat{R}}_{S} (h) : = m^{- 1} \sum_{i = 1}^{m} g_{h} (Z_{i})$ . Let $A$ be a risk-measurable $η$ -approximate ERM for finite $η \geq 0$ , in the sense that ${\hat{R}}_{S} (A (S)) \leq \inf_{h \in H} {\hat{R}}_{S} (h) + η$ .

For measurable $g : Z \to [0, 1]$ , write $P g : = \int g d P$ and $P_{m} g (S) : = m^{- 1} \sum_{i = 1}^{m} g (Z_{i})$ . Let $S^{'} = (Z_{1}^{'}, \dots, Z_{m}^{'})$ be an independent sample with law $P^{m}$ , and write $P_{m}^{'} g : = P_{m} g (S^{'})$ . Assume the following maps are measurable:

$S \mapsto \sup_{g \in G_{H}} (P g - P_{m} g (S))$ and $S \mapsto \sup_{\overset{ˉ}{g} \in {\overline{G}}_{H}} (P \overset{ˉ}{g} - P_{m} \overset{ˉ}{g} (S))$ on $(Z^{m}, Σ_{Z}^{\otimes m})$ ;
$(S, S^{'}) \mapsto \sup_{g \in G_{H}} (P_{m}^{'} g - P_{m} g (S))$ and $(S, S^{'}) \mapsto \sup_{\overset{ˉ}{g} \in {\overline{G}}_{H}} (P_{m}^{'} \overset{ˉ}{g} - P_{m} \overset{ˉ}{g} (S))$ on $(Z^{m} \times Z^{m}, Σ_{Z}^{\otimes m} \otimes Σ_{Z}^{\otimes m})$ ;
for every fixed $σ \in {- 1, + 1}^{m}$ , the maps $(S, S^{'}) \mapsto \sup_{g \in G_{H}} m^{- 1} \sum_{i = 1}^{m} σ_{i} (g (Z_{i}^{'}) - g (Z_{i}))$ and $(S, S^{'}) \mapsto \sup_{\overset{ˉ}{g} \in {\overline{G}}_{H}} m^{- 1} \sum_{i = 1}^{m} σ_{i} (\overset{ˉ}{g} (Z_{i}^{'}) - \overset{ˉ}{g} (Z_{i}))$ on $(Z^{m} \times Z^{m}, Σ_{Z}^{\otimes m} \otimes Σ_{Z}^{\otimes m})$ ;
for every fixed $σ \in {- 1, + 1}^{m}$ , the maps $S \mapsto \sup_{g \in G_{H}} m^{- 1} \sum_{i = 1}^{m} σ_{i} g (Z_{i})$ and $S \mapsto \sup_{\overset{ˉ}{g} \in {\overline{G}}_{H}} m^{- 1} \sum_{i = 1}^{m} σ_{i} \overset{ˉ}{g} (Z_{i})$ on $(Z^{m}, Σ_{Z}^{\otimes m})$ .

The first pair of maps gives the two one-sided deviation suprema and makes the absolute-deviation supremum measurable. Put $K_{0} : = 3 e^{2} / (e - 1)$ , $K : = 4 K_{0}$ , $A_{0} : = 12 e K + 2$ , and $C_{V C} : = 3 \sqrt{8 A_{0}} (\sqrt{\log A_{0}} + 2 \sqrt{\log 2})$ , where $e : = \exp (1)$ and $\log$ is natural. If these measurability conditions hold and the Axiom of Choice is assumed, then for every $0 < δ < 1$ , with probability at least $1 - δ$ ,

$R_{P} (A (S)) - \inf_{h \in H} R_{P} (h) \leq 4 C_{V C} \sqrt{\frac{d + 1}{m}} + 2 \sqrt{\frac{\log (2 / δ)}{2 m}} + η .$

Consequently, assume additionally that the same rule $A$ is risk-measurable under every law $P$ on $Z$ and that conditions 1–4 hold for every such law. For $0 < ϵ < 1$ and $0 \leq η \leq ϵ / 2$ , if

$m \geq \frac{256 C_{V C}^{2} (d + 1) + 32 \log (4 / δ)}{ϵ^{2}},$

then $A$ is agnostic $(ϵ, δ)$ -PAC on $H$ . If $d = 0$ , then $H$ contains one function and every $H$ -valued rule has excess risk zero without a sample-size condition. These are conditional guarantees for risk-measurable selectors; no exact or approximate ERM existence is asserted.

Statement references

Measurable PAC learning criteria for a possibly infinite VC class: defines an $η$ -approximate ERM and the agnostic PAC criterion for a possibly infinite class.

VC entropy uniform deviation without a logarithmic sample-size factor: supplies the two-sided finite-VC deviation bound used in the comparison.

Mohri et al., Theorems 3.3, 3.5, 3.7, and Corollary 3.19: Rademacher generalization and the exact logarithmic VC display.

Bartlett and Mendelson, Theorem 5 and Appendix B: independent classification-risk comparison in their Rademacher normalization.

Facts & Assumptions

Given: A finite-VC binary class, an IID sample with law $P$ , a risk-measurable $η$ -approximate ERM $A$ , $m \geq 1$ , and $0 < δ < 1$ .

[F1]

The agnostic PAC event is ${R_{P} (A (S)) - \inf_{h \in H} R_{P} (h) \leq ϵ}$ , and an $η$ -approximate ERM obeys ${\hat{R}}_{S} (A (S)) \leq \inf_{h \in H} {\hat{R}}_{S} (h) + η$ . Measurable PAC learning criteria for a possibly infinite VC class

[A1]

Assume the Axiom of Choice for the concentration result imported through [F2]; the finite entropy estimate itself is choice-free. The Axiom of Choice

[F2]

Under the Axiom of Choice and all measurability conditions stated in the entropy uniform-convergence theorem, the two-sided deviation is at most $2 C_{V C} \sqrt{(d + 1) / m} + \sqrt{\log (2 / δ) / (2 m)}$ with probability at least $1 - δ$ . VC entropy uniform deviation without a logarithmic sample-size factor

[F3]

Population and empirical risk are the population error probability and empirical error fraction; all risks lie in $[0, 1]$ . Population and empirical risk

[F4]

The natural logarithm is the inverse of the exponential, is strictly increasing, and has $\log 1 = 0$ ; the exponential is strictly increasing and has $\exp (0) = 1$ . Thus $e = \exp (1) > 1$ , $K_{0} > 0$ , $K > 0$ , $A_{0} > 1$ , and $C_{V C} > 0$ ; also $0 < δ < 1$ gives $\log (4 / δ) > 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 real exponential function and the number $e$ by a power series, The exponential function is strictly increasing

Proof

Given: The hypotheses in the Statement.

1.1F1F3givenalgebra

If $d = 0$ , then any two classifiers in $H$ agree at every point, so $H$ contains a single function. Its population risk is the infimum risk, hence every $H$ -valued rule has excess risk zero.

1.2A1F1F2F3algebra

Suppose $d \geq 1$ and write $a_{m} : = 2 C_{V C} \sqrt{(d + 1) / m} + \sqrt{\log (2 / δ) / (2 m)}$ . On the event in [F2], [F1] gives $R_{P} (A (S)) \leq {\hat{R}}_{S} (A (S)) + a_{m} \leq \inf_{h \in H} {\hat{R}}_{S} (h) + η + a_{m}$ . For every $h \in H$ , the same event gives ${\hat{R}}_{S} (h) \leq R_{P} (h) + a_{m}$ , so $\inf_{h \in H} {\hat{R}}_{S} (h) \leq R_{P} (h) + a_{m}$ for every $h$ and therefore $\inf_{h \in H} {\hat{R}}_{S} (h) \leq \inf_{h \in H} R_{P} (h) + a_{m}$ . Combining proves excess risk at most $2 a_{m} + η$ .

2.1F1F2F4step 1.2givenalgebra∎

The event in [F2] has probability at least $1 - δ$ , so step 1.2 proves the first inequality. Under the sample-size premise, $2 C_{V C} \sqrt{(d + 1) / m} \leq ϵ / 8$ and $\sqrt{\log (2 / δ) / (2 m)} \leq ϵ / 8$ : the first follows from $m \geq 256 C_{V C}^{2} (d + 1) / ϵ^{2}$ , and the second from $m \geq 32 \log (4 / δ) / ϵ^{2}$ . Hence $a_{m} \leq ϵ / 4$ , and $2 a_{m} + η \leq ϵ$ when $η \leq ϵ / 2$ . Under the additional hypotheses for the PAC conclusion, this argument applies to every law $P$ with the same $A, m, ϵ, δ$ and $η$ , so [F1] gives the agnostic PAC criterion.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

45 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., Theorems 3.3, 3.5, 3.7, and Corollary 3.19 (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)