DefinitionDefinition: AI-adaptedProof: Not applicablePipeline-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.

Measurable PAC learning criteria for a possibly infinite VC class

Definition

Let $(X, Σ)$ be a nonempty measurable space, let $H$ be a nonempty class of measurable functions $h : X \to {0, 1}$ , put $Z = X \times {0, 1}$ with its product sigma-algebra, and let $P$ be a probability law on $Z$ . For a fixed sample size $m \geq 1$ , a risk-measurable learning rule under $P$ is a map $A : Z^{m} \to H$ for which the real-valued maps $S \mapsto R_{P} (A (S))$ and $S \mapsto {\hat{R}}_{S} (A (S))$ are measurable; if the class infimum is used, also require $S \mapsto \inf_{h \in H} {\hat{R}}_{S} (h)$ to be measurable. The realizable condition is that some $h^{*} \in H$ has $R_{P} (h^{*}) = 0$ . The rule is consistent on a sample when ${\hat{R}}_{S} (A (S)) = 0$ , an exact ERM when it attains $\inf_{h \in H} {\hat{R}}_{S} (h)$ , and an $η$ -approximate ERM for finite $η \geq 0$ when ${\hat{R}}_{S} (A (S)) \leq \inf_{h \in H} {\hat{R}}_{S} (h) + η$ .

In each PAC criterion below, require $A$ to be risk-measurable under every law $P$ quantified over in that criterion. For $0 < ϵ, δ < 1$ , $A$ is realizable $(ϵ, δ)$ -PAC on $H$ if for every law $P$ satisfying the realizable condition, $P_{S \sim P^{m}} {R_{P} (A (S)) \leq ϵ} \geq 1 - δ$ . It is agnostic $(ϵ, δ)$ -PAC if for every law $P$ on $Z$ , $P_{S \sim P^{m}} {R_{P} (A (S)) - \inf_{h \in H} R_{P} (h) \leq ϵ} \geq 1 - δ$ . These are probability criteria only; no existence, attainment, measurability of a selector beyond the stated risk maps, or computational-efficiency claim is implicit. When $H$ is finite and $A$ is measurable into the discrete space $H$ , these probability formulas are the criteria in the finite-class definition.

Definition references

Realizable and agnostic PAC learning: gives the same realizable and agnostic probability criteria when $H$ is finite and the learner takes values in that finite class.

Population and empirical risk: population risk is the expected nonnegative loss and empirical risk is its sample average; here the loss is binary zero-one loss.

Mohri et al., Chapter 2: finite-class PAC criteria and risk notation.

Shalev-Shwartz and Ben-David, Chapters 2–4: PAC learning and VC-dimension framework.

Depends on

Used by

Agnostic sample complexity for finite-VC ERM Theorem
Realizable sample complexity for finite-VC classes Theorem

Dependency tree · two levels

5 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 (standard reference, not scraped)
Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Chapters 2–4 (standard reference, not scraped)