CorollaryStatement: AI-adaptedProof: 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.

A sample-size consequence for compression schemes

Statement

Let $m, d \in N$ with $m > d$ . Let $(X, Σ)$ be a measurable space, let $c : X \to {0, 1}$ be measurable, and let $D$ be a probability measure on $X$ . Put $Z = X \times {0, 1}$ with its product sigma-algebra. For each $0 \leq i \leq d$ , let $G_{i} : Z^{i} \times X \to {0, 1}$ be a fixed jointly measurable reconstruction map, with $G_{0}$ measurable on $X$ . Draw independent observations $X_{1}, \dots, X_{m}$ , each with law $D$ , and form $S = ((X_{1}, c (X_{1})), \dots, (X_{m}, c (X_{m})))$ . A deterministic compressor selects an index subset $I (S) = {i_{1} < \dots < i_{k}} \subseteq [m]$ with $k \leq d$ and outputs $h_{S} (x) = G_{k} (S_{I (S)}, x)$ , where $S_{I (S)}$ is the ordered tuple of selected labeled entries; for $I (S) = \emptyset$ , use $G_{0}$ . Assume the reconstruction is consistent on every such sample, meaning $h_{S} (X_{j}) = c (X_{j})$ for each $j$ , and assume the learner's output-risk event is measurable. Define $R_{D} (h) : = D {x : h (x) \neq c (x)}$ . Fix $ϵ, δ \in (0, 1)$ . If $d = 0$ and $m ϵ \geq \log (1 / δ)$ , or if $1 \leq d < m$ and $ϵ (m - d) \geq d \log (\frac{e m}{d}) + \log (1 / δ),$ where $e$ is the base of the real exponential function, then $R_{D} (h_{S}) \leq ϵ$ with probability at least $1 - δ$ over the independent observations.

Statement references

The sample-compression generalization bound: the probability of any consistent bad reconstruction among all index subsets is bounded by the exact binomial sum.

Deterministic sample-compression schemes: a deterministic scheme selects at most $d$ labeled entries and reconstructs a binary classifier from those entries alone, consistently on the full sample.

A binomial-sum bound for compression sample sizes: for $1 \leq d \leq m$ , $\sum_{i = 0}^{d} (\binom{m}{i}) \leq (e m / d)^{d}$ .

$1 + x \leq \exp (x)$ for every real $x$ , hence $(1 - p)^{m} \leq \exp (- m p)$ : $(1 - p)^{n} \leq \exp (- n p)$ for $p \in [0, 1]$ and natural $n$ .

The natural logarithm as the inverse of the exponential function: $\log$ is the inverse of the real exponential on the positive reals.

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: the natural logarithm is increasing and obeys the product and reciprocal laws.

The real exponential function and the number $e$ by a power series: $e = \exp (1)$ .

The exponential addition formula $\exp (x + y) = \exp (x) \exp (y)$ : $\exp (x + y) = \exp (x) \exp (y)$ .

The exponential function is strictly increasing: the real exponential is increasing.

The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ : the real exponential is positive and $\exp (- x) = 1 / \exp (x)$ .

Floyd and Warmuth, Sample Compression, Learnability, and the Vapnik–Chervonenkis Dimension, Theorem 5 and §5: sample-size consequences are derived from the compression probability bound.

Facts & Assumptions

Given: The hypotheses in the Statement.

[F1]

The exact bad-subset probability is at most $\sum_{i = 0}^{d} (\binom{m}{i}) (1 - ϵ)^{m - i}$ . The sample-compression generalization bound

[F2]

If $1 \leq d \leq m$ , then $\sum_{i = 0}^{d} (\binom{m}{i}) \leq (e m / d)^{d}$ . A binomial-sum bound for compression sample sizes

[F3]

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

[F4]

The natural logarithm and real exponential are defined on their stated domains; the logarithm is increasing, inverse to the exponential, and satisfies the product and reciprocal laws, while the exponential is increasing and positive and obeys the addition law. 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 addition formula $\exp (x + y) = \exp (x) \exp (y)$ , The exponential function is strictly increasing, The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$

Proof

Given: The hypotheses in the Statement.

1.1F1F3F4givenalgebra

If $d = 0$ , [F1] reduces the bad-subset probability to $(1 - ϵ)^{m}$ . By [F3] this is at most $\exp (- m ϵ)$ , which is at most $δ$ when $m ϵ \geq \log (1 / δ)$ by [F4].

1.2F1F2F3F4givenalgebra

If $1 \leq d < m$ , then for every $i \leq d$ , [F3] with $n = m - i$ gives $(1 - ϵ)^{m - i} \leq \exp (- ϵ (m - i))$ . Since $m - i \geq m - d$ and $ϵ > 0$ , monotonicity of the exponential [F4] gives $\exp (- ϵ (m - i)) \leq \exp (- ϵ (m - d))$ . Thus [F1] and [F2] bound the bad-subset probability by ${(\frac{e m}{d})}^{d} \exp (- ϵ (m - d)) = \exp (d \log (\frac{e m}{d}) - ϵ (m - d))$ . The displayed sample-size condition makes the exponent at most $- \log (1 / δ) = \log δ$ , so monotonicity of the exponential gives a bound at most $δ$ .

2.1F1step 1.1step 1.2given∎

A consistent learner's output is one of the reconstructions counted by the bad-subset event in [F1]. Therefore its measurable failure event has probability at most $δ$ in either case, proving the conclusion.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

40 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 §5 (standard reference, not scraped)