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.

The sample-compression generalization bound

Statement

Let $(X, Σ)$ be a measurable space, let $H$ be a nonempty class of measurable maps $c : X \to {0, 1}$ , fix a target $c \in H$ , and let $D$ be a probability measure on $X$ . Put $Z = X \times {0, 1}$ with the product sigma-algebra. Let $m, d \in N$ satisfy $m > d$ , set $[m] = {1, \dots, m}$ , and draw $(X_{1}, \dots, X_{m})$ under $D^{m}$ , labeling $X_{j}$ by $c (X_{j})$ . Write $S = ((X_{1}, c (X_{1})), \dots, (X_{m}, c (X_{m})))$ . For each $0 \leq i \leq d$ , let $G_{i} : Z^{i} \times X \to {0, 1}$ be a fixed jointly measurable reconstruction map (for $i = 0$ , $G_{0}$ is measurable on $X$ ). For $I = {i_{1} < \dots < i_{k}} \subseteq [m]$ , define $S_{I} = ((X_{i_{1}}, c (X_{i_{1}})), \dots, (X_{i_{k}}, c (X_{i_{k}})))$ and $g (S_{I}) (x) : = G_{k} (S_{I}, x)$ ; for $I = \emptyset$ , let $S_{I}$ be the empty sequence and use $G_{0}$ . Define $R_{D} (g (S_{I})) : = D {x : g (S_{I}) (x) \neq c (x)}$ . For every $ϵ \in (0, 1)$ , $\Pr_{D^{m}} {\begin{cases} there is an index subset I \subseteq [m], ∣ I ∣ \leq d, such that R_{D} (g (S_{I})) > ϵ \\ and g (S_{I}) (X_{j}) = c (X_{j}) for every j \in [m] \end{cases}} \leq \sum_{i = 0}^{d} (\binom{m}{i}) (1 - ϵ)^{m - i} .$ The event displayed above is measurable. Thus any measurable consistent compression learner of size at most $d$ using these reconstructors has failure probability no larger than this bound.

Statement references

Deterministic sample-compression schemes: the reconstruction map uses only the ordered selected labeled entries and is jointly measurable; consistency means reproducing every label in the full sample.

Population and empirical risk: population risk is expected loss and empirical risk is the average loss on the sample; here the loss is binary zero-one loss against the fixed target.

For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique: $D^{m}$ assigns a product rectangle the product of its coordinate probabilities.

Basic identities for a probability measure: the probability of a finite union is at most the sum of its probabilities.

The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ : $(\binom{m}{i})$ counts the $i$ -element index subsets of $[m]$ .

Floyd and Warmuth, Sample Compression, Learnability, and the Vapnik–Chervonenkis Dimension, Theorem 5 and Appendix proof: fixes an indexed compression set, bounds consistency on the remaining independent sample, and sums over all subset sizes.

Facts & Assumptions

Given: A fixed measurable target $c \in H$ , a probability measure $D$ , a size-at-most- $d$ compression scheme, integers $m > d \geq 0$ , and $ϵ \in (0, 1)$ .

[F1]

For each $0 \leq i \leq d$ , the reconstruction map $G_{i}$ is jointly measurable, and a consistent scheme reproduces each of the $m$ target labels from its selected entries. Deterministic sample-compression schemes

[F2]

Under zero-one loss, population risk is the probability of disagreement with the target and empirical risk is the average of the corresponding indicators; fixed-predictor risks are defined and the empirical-risk function of the sample is measurable. Population and empirical risk, Population and empirical risks are measurable

[F3]

$D$ is a probability measure, $D^{m}$ is the finite product measure on the finite product sigma-algebra, and it has the rectangle formula and uniqueness property. A coordinate permutation preserves it because both pushforward measures agree on all rectangles. Probability measures and probability spaces, The product sigma-algebra and its finite iterates, For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique

[F4]

Tonelli makes the section risk measurable and permits integration first over selected coordinates and then over the remaining product coordinates. Tonelli's theorem for nonnegative measurable functions on a sigma-finite product

[F5]

For events $E_{1}, \dots, E_{N}$ , $\Pr (⋃_{j = 1}^{N} E_{j}) \leq \sum_{j = 1}^{N} \Pr (E_{j})$ . Basic identities for a probability measure

[F6]

$(\binom{m}{i})$ is the number of $i$ -element subsets of $[m]$ . The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$

[F7]

The reconstruction maps are measurable maps on finite product measurable spaces; real finite sums and comparisons of measurable functions remain measurable, and natural powers preserve inequalities between nonnegative bases for a fixed positive exponent. The product sigma-algebra and its finite iterates, A measurable function between measurable spaces, Arithmetic and lattice operations preserve measurability whenever they are defined, Finite sums and finite products, by recursion, Integer powers $a^{m}$ , Monotonicity of $x \mapsto x^{n}$ and of $n \mapsto a^{n}$

Proof

Given: The hypotheses in the Statement.

1.1F1F2F4F7given

Fix $0 \leq i \leq d$ and $I \subseteq [m]$ with $∣ I ∣ = i$ . For an ordered selected tuple $s$ , define $L_{s} (x) : = 1 {G_{i} (s, x) \neq c (x)}$ and $r_{i} (s) : = \int L_{s} d D$ . By [F1], [F2], [F7], and [F4], the mismatch indicator and its section integral are measurable; the event that the selected hypothesis agrees with each selected example is also measurable. Thus the event $E_{I}$ that this subset reconstructs a hypothesis of risk greater than $ϵ$ consistent on the full sample is measurable.

2.1F1F2F3F4F7step 1.1algebra

Reorder the coordinates so the indices in $I$ come first. [F3] identifies the resulting law as $D^{i} \times D^{m - i}$ . For fixed selected tuple $s$ , let $A_{s} : = {x : G_{i} (s, x) = c (x)}$ ; then $D (A_{s}) = 1 - r_{i} (s)$ by [F2]. The remaining coordinates are all consistent exactly on the rectangle $A_{s}^{m - i}$ , whose product probability is $(1 - r_{i} (s))^{m - i}$ by [F3]. On $r_{i} (s) > ϵ$ , we have $0 \leq 1 - r_{i} (s) < 1 - ϵ$ and $m - i \geq 1$ , so [F7] gives $(1 - r_{i} (s))^{m - i} \leq (1 - ϵ)^{m - i}$ . Integrating over $s$ by [F4] and discarding the additional requirement that selected entries themselves be consistent gives $\Pr_{D^{m}} (E_{I}) \leq (1 - ϵ)^{m - i}$ .

3.1F5F6step 2.1givenalgebra∎

There are exactly $(\binom{m}{i})$ subsets of $[m]$ of size $i$ by [F6]. Applying [F5] over all such subsets and then over $i = 0, \dots, d$ yields $\Pr_{D^{m}} (⋃_{I \subseteq [m], ∣ I ∣ \leq d} E_{I}) \leq \sum_{i = 0}^{d} (\binom{m}{i}) (1 - ϵ)^{m - i}$ , which is the stated bound. The output of any consistent compression learner is one of these reconstructed candidates, so its measurable failure event is contained in this union.

Remarks

The theorem assumes a size- $d$ compression scheme; it does not prove that every class of VC dimension $d$ has a compression scheme of size $O (d)$ . Floyd and Warmuth identified that question in 1995, so the cited source is not used as a current-status claim.

Remarks references

Floyd and Warmuth, Sample Compression, Learnability, and the Vapnik–Chervonenkis Dimension, §9.1: records the 1995 open question about size- $O (d)$ compression for arbitrary VC-dimension- $d$ classes.

Depends on

Used by

A sample-size consequence for compression schemes Corollary
A finite-support sample-compressed classifier Example

Dependency tree · two levels

79 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

Sally Floyd and Manfred Warmuth, Sample Compression, Learnability, and the Vapnik–Chervonenkis Dimension, Theorem 5 and Appendix proof (standard reference, not scraped)