Sample compression and PAC-Bayes bounds — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: Literature-sourcedVerification: AI-adaptedjudge pass (gpt-6-luna)Open item page →

A posterior concentrated on one hypothesis

Example

Let the hypothesis space be the two-point measurable space $Θ = {h_{0}, h_{1}}$ with its full sigma-algebra, and let the prior be uniform on the two hypotheses. Let $Z$ be any measurable observation space, let $D$ be a probability measure on $Z$ , and let $ℓ : Θ \times Z \to [0, C]$ be product-measurable for a finite $C \geq 0$ . Define $R (h) = \int_{Z} ℓ (h, z) D (d z)$ and ${\hat{R}}_{S} (h) = m^{- 1} \sum_{i = 1}^{m} ℓ (h, Z_{i})$ . For an IID sample $S = (Z_{1}, \dots, Z_{m})$ of size $m \geq 1$ with common law $D$ , take the posterior $ρ = δ_{h_{0}}$ . Then $K L (ρ ∥ π) = \log 2$ , and for every fixed $λ > 0$ and $δ \in (0, 1)$ , with probability at least $1 - δ$ , $R (h_{0}) \leq {\hat{R}}_{S} (h_{0}) + \frac{λ C^{2}}{8 m} + \frac{\log 2 + \log (1 / δ)}{λ}$

Example references

PAC-Bayes priors, posteriors, and relative entropy: defines the sample-independent prior, absolutely continuous posterior, and finite-partition relative entropy used here.

The PAC-Bayes KL generalization bound: gives the simultaneous posterior-average risk bound under the stated product-measurability and IID hypotheses.

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

Alquier, User-friendly Introduction to PAC-Bayes Bounds, Chapter 2, §2.1.1: discusses the PAC-Bayes bound with a posterior concentrated on an individual predictor.

Facts & Assumptions

Given: The finite measurable hypothesis space, its uniform prior, the bounded jointly measurable loss, an IID sample with common law $D$ , and the point-mass posterior $δ_{h_{0}}$ .

[F1]

A prior and posterior are probability measures, and relative entropy is the supremum of finite-partition divergences using the natural logarithm. PAC-Bayes priors, posteriors, and relative entropy, Probability measures and probability spaces, The natural logarithm as the inverse of the exponential function

[F2]

For the fixed prior and bounded product-measurable loss, with probability at least $1 - δ$ the PAC-Bayes inequality holds simultaneously for every posterior absolutely continuous with respect to the prior. The PAC-Bayes KL generalization bound

Verification

Given: The finite measurable hypothesis space, uniform sample-independent prior, bounded product-measurable loss, IID sample with common law $D$ , and posterior $δ_{h_{0}}$ in the Example.

1.1givenF1casesalgebra

The posterior $δ_{h_{0}}$ is absolutely continuous with respect to the uniform prior because every prior-null subset of $Θ$ is empty. For a finite measurable partition, if its cells keep $h_{0}, h_{1}$ together, its divergence is $0$ ; if it separates them, the cell containing $h_{0}$ contributes $1 \cdot \log (1 / (1 / 2)) = \log 2$ and the other cell contributes $0$ . Hence every partition divergence is at most $\log 2$ , and the partition into singletons attains it, so [F1] gives $K L (δ_{h_{0}} ∥ π) = \log 2$ .

2.1givenF2step 1.1algebra∎

Since $ρ$ is concentrated at $h_{0}$ , its population and empirical risk averages are respectively $R (h_{0})$ and ${\hat{R}}_{S} (h_{0})$ . Applying [F2] to this posterior gives the displayed inequality with probability at least $1 - δ$ .

CounterexampleConstruction: AI-generatedVerification: AI-adaptedjudge pass (gpt-6-luna)Open item page →

A data-dependent prior can invalidate the PAC-Bayes bound

Statement refuted

Let $X = {1, \dots, 20}$ with its full sigma-algebra, let $D$ be uniform on $X$ , let $c (x) = 0$ , and let $H = {h_{A} : A \subseteq X, ∣ A ∣ = 10}$ with its full sigma-algebra, where $h_{A} (x) = 1_{A} (x)$ . Use the zero-one loss $ℓ (h, x) = 1 {h (x) \neq c (x)}$ , the sample size $m = 10$ , confidence $δ = 1 / 4$ , and tuning parameter $λ = 20$ . Draw independent observations $X_{1}, \dots, X_{10}$ with common law $D$ . For each sample $S = (X_{1}, \dots, X_{10})$ , let $A (S)$ be the lexicographically first ten-element subset disjoint from ${X_{1}, \dots, X_{10}}$ and put $π_{S} = ρ_{S} = δ_{h_{A (S)}}$ . Even if one drops the requirement that the prior be fixed independently of the sample, the same PAC-Bayes formula holds with probability at least $3 / 4$ over this sample: $E_{h \sim ρ_{S}} R_{D} (h) \leq E_{h \sim ρ_{S}} {\hat{R}}_{S} (h) + \frac{λ}{8 m} + \frac{K L (ρ_{S} ∥ π_{S}) + \log (1 / δ)}{λ},$ where $R_{D} (h) = D {x : h (x) \neq c (x)}$ , ${\hat{R}}_{S} (h) = m^{- 1} \sum_{i = 1}^{m} ℓ (h, X_{i})$ , and $K L$ is the supremum of the finite-partition divergences with zero-numerator terms equal to $0$ and positive-numerator/zero-denominator terms equal to $+ \infty$ .

Statement references

The PAC-Bayes KL generalization bound: gives this form of bound when the prior is fixed independently of the sample.

PAC-Bayes priors, posteriors, and relative entropy: defines the prior's sample-independence requirement and the finite-partition relative entropy.

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

Alquier, User-friendly Introduction to PAC-Bayes Bounds, Chapter 2, §2.1.1: states the PAC-Bayes result with a prior fixed before observing the sample.

Facts & Assumptions

Given: The finite instance space and hypothesis class with their full sigma-algebras, the uniform distribution $D$ , the target $c (x) = 0$ , the indicator hypotheses $h_{A}$ , and an IID sample $S = (X_{1}, \dots, X_{10})$ .

[F1]

A probability measure has total mass one; population risk is the integral of the loss, empirical risk is its sample average, and fixed-predictor risks are measurable under the stated assumptions. Probability measures and probability spaces, Population and empirical risk, Population and empirical risks are measurable

[F2]

For each sample, relative entropy is the supremum over finite measurable partitions of the partition divergence, using the natural logarithm. PAC-Bayes priors, posteriors, and relative entropy, The natural logarithm as the inverse of the exponential function

[F3]

The proved PAC-Bayes inequality assumes that its prior is fixed independently of the sample. The PAC-Bayes KL generalization bound

[F4]

The natural logarithm is increasing and for $x \geq 1$ satisfies $0 \leq \log x \leq x - 1 \leq x$ . Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The natural logarithm is bounded above by its positive argument minus one

Counterexample

technique · direct

Given: The finite learning problem and the sample-dependent measures in the Statement.

1.1givenconstruct

For each sample $s = (x_{1}, \dots, x_{10})$ , its observed support has at most ten points, so its complement in $X$ has at least ten points. Let $A (s)$ be the lexicographically first ten-element subset of that complement. This defines a measurable function of the sample because the sample space is finite. Put $π_{s} = ρ_{s} = δ_{h_{A (s)}}$ .

2.1givenF1step 1.1algebra

Every $A (s)$ has ten points, so [F1] gives $R_{D} (h_{A (s)}) = 10 / 20 = 1 / 2$ . Since $A (s)$ is disjoint from the sample support, every sampled label is predicted as zero and ${\hat{R}}_{s} (h_{A (s)}) = 0$ .

3.1F2F4step 1.1step 2.1algebra

The measures $π_{s}$ and $ρ_{s}$ are equal, so every finite-partition divergence is zero and [F2] gives $K L (ρ_{s} ∥ π_{s}) = 0$ . By [F4], $\log 4 \leq 3$ , and therefore the proposed right side is at most $20 / (8 \cdot 10) + 3 / 20 = 2 / 5 < 1 / 2$ . Thus the displayed inequality fails for every sample.

4.1F3step 3.1given∎

The failure probability is one, contradicting the claimed success probability $3 / 4$ . The choice $π_{s}$ violates the fixed-prior hypothesis [F3], which is why this construction does not contradict the stated PAC-Bayes theorem.

ExampleConstruction: AI-generatedVerification: AI-adaptedOpen item page →

A finite-support sample-compressed classifier

Example

Let $X = {0, 1}$ with its full sigma-algebra, let $D$ be uniform on $X$ , and let $H = {c}$ for the target $c (x) = x$ . Define $G_{0}$ to be the constant-zero map. For each positive sample length $n$ , the compressor selects the index of the first occurrence of each distinct input in the labeled sample; for length zero it selects the empty index set. For each selected ordered sequence of length $1 \leq k \leq 2$ , the fixed reconstruction map returns the selected label at the first selected entry whose input equals its argument, if such an entry exists, and returns $0$ otherwise; the empty sequence is reconstructed by $G_{0}$ . This is a deterministic consistent compression scheme of size at most $d = 2$ . Draw $m \geq 3$ independent observations with law $D$ and define $R_{D} (h) = D {x : h (x) \neq c (x)}$ . The reconstructed classifier has risk $1 / 2$ exactly when all $m$ observations are $0$ , and otherwise has risk $0$ . Consequently, at threshold $ϵ = 1 / 4$ its failure probability is $2^{- m}$ , bounded by the compression theorem's value $\sum_{i = 0}^{2} (\binom{m}{i}) (3 / 4)^{m - i}$ .

Example references

Deterministic sample-compression schemes: defines deterministic index selection, reconstruction from selected labeled entries alone, and consistency.

The sample-compression generalization bound: bounds the bad consistent reconstruction probability by the finite sum over index subsets.

Population and empirical risk: population risk is disagreement probability and empirical risk is the sample average for zero-one loss.

Floyd and Warmuth, Sample Compression, Learnability, and the Vapnik–Chervonenkis Dimension, §3 and Theorem 5: gives the sample-compression setup and its generalization bound.

Facts & Assumptions

Given: The two-point measurable instance space, uniform distribution, identity target, the first-occurrence compressor, and the reconstruction rule in the Example.

[F1]

A size-at-most-two compression scheme measurably selects at most two indices and reconstructs using only the selected labeled entries in sample order through fixed measurable maps. It is consistent if the reconstruction reproduces every label of every target-labeled sample. Deterministic sample-compression schemes

[F2]

For the fixed target, population risk is disagreement probability and empirical risk is the average sample disagreement; both are well-defined for measurable predictors. Population and empirical risk, Population and empirical risks are measurable

[F3]

For a size-at-most- $d$ consistent scheme with $m > d$ , the probability of any consistent reconstructed hypothesis of risk greater than $ϵ$ is at most $\sum_{i = 0}^{d} (\binom{m}{i}) (1 - ϵ)^{m - i}$ . The sample-compression generalization bound

Verification

Given: The two-point measurable instance space, uniform distribution, identity target, first-occurrence compressor, and reconstruction rule in the Example.

1.1givenF1construct

For the empty sample, the selected index set is empty and consistency is vacuous. For a positive-length sequence, the set of first-occurrence indices has at most two members, and the reconstruction maps are fixed functions of the selected entries. On a sample labeled by $c$ , if an input $x$ occurs in the full sample, its first occurrence is selected and its selected label is $c (x) = x$ ; if it does not occur, no sample-consistency condition applies at $x$ . Thus the reconstructed function agrees with every observed label, so the scheme is consistent in the sense of [F1]. All spaces are finite with their full sigma-algebras, so the compressor, reconstructor, risk, and output-risk event are measurable.

2.1F2givenstep 1.1algebra

If at least one observation equals $1$ , then the reconstruction returns $1$ at input $1$ and returns $0$ at input $0$ , either from a selected entry or by the default rule, so its risk is $0$ . If every observation is $0$ , it returns $0$ at both inputs and errs only at $1$ , so [F2] gives risk $D ({1}) = 1 / 2$ . Independence and $D ({0}) = 1 / 2$ make the latter event have probability $(1 / 2)^{m} = 2^{- m}$ .

3.1F3step 2.1algebra∎

For $m \geq 3$ , the size parameter satisfies $m > d = 2$ . At $ϵ = 1 / 4$ , step 2.1 shows that the event $R_{D} > ϵ$ is exactly the all-zero sample event, hence has probability $2^{- m}$ . Its value is at most $(3 / 4)^{m}$ , which is the $i = 0$ term in the sum in [F3]; all other terms are nonnegative. Thus the exact example probability is bounded by $\sum_{i = 0}^{2} (\binom{m}{i}) (3 / 4)^{m - i}$ as stated.

Sample compression and PAC-Bayes bounds — Examples

2 · Logical flowchart

3 · Definitions, theorems and proofs

4 · Examples, counterexamples and false statements

A posterior concentrated on one hypothesis

Example

Example references

Facts & Assumptions

Verification

A data-dependent prior can invalidate the PAC-Bayes bound

Statement refuted

Statement references

Facts & Assumptions

Counterexample

A finite-support sample-compressed classifier

Example

Example references

Facts & Assumptions

Verification

Sources