Sample compression and PAC-Bayes bounds

Let $(\mathrm{\Theta },\mathcal{A})$ be a measurable space. A prior is a probability measure $\pi$ on $(\mathrm{\Theta },\mathcal{A})$ fixed independently of the training sample. A posterior relative to $\pi$ is a probability measure $\rho$ on $(\mathrm{\Theta },\mathcal{A})$ that is absolutely continuous with respect to $\pi$, meaning that $\pi (A)=0$ implies $\rho (A)=0$ for every $A\in \mathcal{A}$.

For such $\rho$ and $\pi$, define their Kullback–Leibler relative entropy by $\mathrm{K}\mathrm{L}(\rho \mathrm{\parallel }\pi ):={\sup }_{\mathcal{P}}{\sum }_{A\in \mathcal{P}}\rho (A)\log \frac{\rho (A)}{\pi (A)},$ where the supremum is over all finite measurable partitions $\mathcal{P}$ of $\mathrm{\Theta }$. A term with $\rho (A)=0$ is $0$; a term with $\rho (A)>0=\pi (A)$ is $+\mathrm{\infty }$. The value may be $+\mathrm{\infty }$.

Measurable spaces and measurable sets: a measurable space is a set equipped with a specified sigma-algebra.

Probability measures and probability spaces: a probability measure is a measure of total mass one.

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

Alquier, User-friendly Introduction to PAC-Bayes Bounds, Chapter 2: uses a sample-independent prior and relative entropy between posterior and prior.

For natural numbers $m,d$ with $1\le d\le m$, ${\sum }_{i=0}^d\left(\genfrac{}{}{0px}{}{m}{i}\right)\le {\left(\frac{em}{d}\right)}^d,$ where $\left(\genfrac{}{}{0px}{}{m}{i}\right)$ is the number of $i$-element subsets of an $m$-element set, natural numbers and binomial counts in real expressions denote their canonical real images, and $e=\exp (1)$.

Finite sums and finite products, by recursion: defines the real finite sums in the displayed inequality.

Laws of finite sums and finite products: real finite sums preserve inequalities between corresponding terms.

The set $[A{]}^k$ of $k$-element subsets and the binomial coefficient $\left(\genfrac{}{}{0px}{}{n}{k}\right):=\mid [n{]}^k\mid$: $\left(\genfrac{}{}{0px}{}{m}{i}\right)$ counts the $i$-element subsets of an $m$-element set.

The canonical natural $\iota (n)=n\cdot 1_F$ of a field: $n$ is the canonical real associated with the natural number $n$.

Canonical naturals are positive and strictly increasing: $n>0$ whenever $n\ge 1$.

Integer powers $a^m$: the exponent $d$ denotes a natural power in the real field.

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

Floyd and Warmuth, Sample Compression, Learnability, and the Vapnik–Chervonenkis Dimension, §5 and Appendix: their compression sample-size derivation uses the same binomial sum; this item proves the estimate below directly.

Let $(\mathrm{\Theta },\mathcal{A})$ be a measurable space, let $\pi$ be a probability measure, and let $\rho$ be a probability measure absolutely continuous with respect to $\pi$, meaning that $\pi (A)=0$ implies $\rho (A)=0$ for all $A\in \mathcal{A}$. Define $\mathrm{K}\mathrm{L}(\rho \mathrm{\parallel }\pi ):={\sup }_{\mathcal{P}}{\sum }_{A\in \mathcal{P}}\rho (A)\log \frac{\rho (A)}{\pi (A)},$ where $\mathcal{P}$ ranges over finite measurable partitions of $\mathrm{\Theta }$, a zero-numerator term is $0$, and a positive numerator over a zero denominator is $+\mathrm{\infty }$. For every bounded measurable $f:\mathrm{\Theta }\to \mathbb{R}$, ${\mathbb{E}}_{\theta \sim \rho }f(\theta )\le \mathrm{K}\mathrm{L}(\rho \mathrm{\parallel }\pi )+\log {\mathbb{E}}_{\theta \sim \pi }\exp (f(\theta )),$ with the inequality interpreted as vacuous when $\mathrm{K}\mathrm{L}(\rho \mathrm{\parallel }\pi )=+\mathrm{\infty }$.

PAC-Bayes priors, posteriors, and relative entropy: a posterior is absolutely continuous with respect to the prior, and $\mathrm{K}\mathrm{L}$ is the supremum over finite measurable partitions.

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

Finite log-sum inequality with support and equality cases: for finite nonnegative vectors, the sum of coordinatewise relative-entropy terms is at least the corresponding aggregate term.

Alquier, User-friendly Introduction to PAC-Bayes Bounds, Chapter 2, Lemma 2.2: states the Donsker–Varadhan variational formula for bounded measurable functions.

Let $(\mathcal{X},\mathrm{\Sigma })$ be a measurable instance space, let $\{0,1\}$ have its full discrete sigma-algebra, and give $\mathcal{Z}:=\mathcal{X}\times \{0,1\}$ the product sigma-algebra. For each $k\in \mathbb{N}$, give ${\mathcal{Z}}^k$ its finite product sigma-algebra, with ${\mathcal{Z}}^0=\{()\}$. Let $\mathcal{H}$ be a nonempty class of measurable functions $c:\mathcal{X}\to \{0,1\}$. For $m,d\in \mathbb{N}$, write $[m]:=\{j\in \mathbb{N}:1\le j\le m\}$, so $[0]=\mathrm{\varnothing }$, and give ${\mathcal{I}}_{m,d}:=\{I\subseteq [m]:\mathrm{\mid }I\mathrm{\mid }\le d\}$ its discrete sigma-algebra. For $d\in \mathbb{N}$, a deterministic sample-compression scheme of size at most $d$ consists of a measurable compression map ${\kappa }_m:{\mathcal{Z}}^m\to {\mathcal{I}}_{m,d}$ for every $m\in \mathbb{N}$, and fixed reconstruction maps $G_k:{\mathcal{Z}}^k\times \mathcal{X}\to \{0,1\}$ for $1\le k\le d$ and $G_0:\mathcal{X}\to \{0,1\}$, all measurable for the stated product and discrete sigma-algebras. If $S=(z_1,\dots ,z_m)$ and $I={\kappa }_m(S)=\{i_1<\cdots <i_k\}$, write $S_I=(z_{i_1},\dots ,z_{i_k})$ and define $g(S_I)(x):=G_k(S_I,x)$; for $I=\mathrm{\varnothing }$, use $G_0$. The scheme is consistent if, for every $c\in \mathcal{H}$, every $m\in \mathbb{N}$, and every $S=((x_1,c(x_1)),\dots ,(x_m,c(x_m)))$, this reconstruction satisfies $g(S_I)(x_j)=c(x_j)$ for every $j\in [m]$. The reconstruction map uses only the ordered selected labeled entries and no other side information; the reconstructed classifier need not belong to $\mathcal{H}$.

Supervised prediction problems: fixes measurable instance, label, and prediction spaces and uses measurable predictors.

Measurable spaces and measurable sets: a measurable space is a set equipped with a specified sigma-algebra.

The product sigma-algebra and its finite iterates: the product sigma-algebra is generated by measurable rectangles.

A measurable function between measurable spaces: a map is measurable when preimages of measurable sets are measurable.

The cardinality $\mid A\mid$ of a finite set: $\mathrm{\mid }I\mathrm{\mid }$ denotes the finite cardinality of the selected index set.

The natural numbers $\mathbb{N}$ (von Neumann): sample lengths and compression sizes are natural numbers, including $0$.

Floyd and Warmuth, Sample Compression, Learnability, and the Vapnik–Chervonenkis Dimension, §3: defines compression and reconstruction maps, permits reconstructed hypotheses outside the concept class, and requires consistency on the original sample.

Let $(\mathrm{\Theta },\mathcal{A})$ and $(\mathcal{Z},\mathcal{B})$ be measurable spaces. Let $\pi$ and $D$ be probability measures on them, respectively. Let $C\ge 0$ and let $\mathrm{\ell }:\mathrm{\Theta }\times \mathcal{Z}\to [0,C]$ be measurable with respect to $\mathcal{A}\otimes \mathcal{B}$. Let $m\ge 1$ and let $S=(Z_1,\dots ,Z_m)$ consist of independent observations with common law $D$, equivalently having product law $D^m$. Define $R(\theta ):={\int }_{\mathcal{Z}}\mathrm{\ell }(\theta ,z)D(dz),{\widehat{R}}_S(\theta ):=\frac{1}{m}{\sum }_{i=1}^m\mathrm{\ell }(\theta ,Z_i)\mathrm{.}$ Fix the prior $\pi$ independently of $S$, and fix $\lambda >0$ and $\delta \in (0,1)$. For a probability measure $\rho$ with $\rho \ll \pi$ (that is, $\pi (A)=0$ implies $\rho (A)=0$ for all measurable $A$), define $\mathrm{K}\mathrm{L}(\rho \mathrm{\parallel }\pi ):={\sup }_{\mathcal{P}}{\sum }_{A\in \mathcal{P}}\rho (A)\log \frac{\rho (A)}{\pi (A)},$ where $\mathcal{P}$ ranges over finite measurable partitions of $\mathrm{\Theta }$, terms with zero numerator are $0$, and a positive numerator over zero denominator is $+\mathrm{\infty }$. With probability at least $1-\delta$ over $S$, simultaneously for every such posterior $\rho$, ${\mathbb{E}}_{\theta \sim \rho }R(\theta )\le {\mathbb{E}}_{\theta \sim \rho }{\widehat{R}}_S(\theta )+\frac{\lambda C^2}{8m}+\frac{\mathrm{K}\mathrm{L}(\rho \mathrm{\parallel }\pi )+\log (1\mathrm{/}\delta )}{\lambda }\mathrm{.}$ An infinite relative entropy makes the bound vacuous. The conclusion bounds posterior-average risk, not the risk of every posterior draw.

PAC-Bayes priors, posteriors, and relative entropy: defines a sample-independent prior, an absolutely continuous posterior, and relative entropy.

Population and empirical risk: population risk is the expected loss and empirical risk is the sample-average loss.

Identical distribution and IID families: IID observations are independent and have a common law.

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

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

The Hoeffding MGF bound for a variable in a unit interval: a unit-range random variable has centered exponential moment at most $\exp (t^2\mathrm{/}8)$ for every real $t$.

Alquier, User-friendly Introduction to PAC-Bayes Bounds, Chapter 2, Theorem 2.1 and proof: proves the bounded-loss PAC-Bayes KL bound by integrating the fixed-parameter Hoeffding MGF, applying the Donsker–Varadhan formula, and using Markov's inequality.

This is a posterior-average risk bound. It does not assert that $R(\theta )$ obeys the same inequality for every individual $\theta$ sampled from $\rho$.

Let $(\mathcal{X},\mathrm{\Sigma })$ be a measurable space, let $\mathcal{H}$ be a nonempty class of measurable maps $c:\mathcal{X}\to \{0,1\}$, fix a target $c\in \mathcal{H}$, and let $D$ be a probability measure on $\mathcal{X}$. Put $\mathcal{Z}=\mathcal{X}\times \{0,1\}$ with the product sigma-algebra. Let $m,d\in \mathbb{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\le i\le d$, let $G_i:{\mathcal{Z}}^i\times \mathcal{X}\to \{0,1\}$ be a fixed jointly measurable reconstruction map (for $i=0$, $G_0$ is measurable on $\mathcal{X}$). For $I=\{i_1<\cdots <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=\mathrm{\varnothing }$, let $S_I$ be the empty sequence and use $G_0$. Define $R_D(g(S_I)):=D\{x:g(S_I)(x)\mathrm{\ne }c(x)\}$. For every $ϵ\in (0,1)$, ${\mathrm{Pr}}_{D^m}\left\{\begin{array}{l}\text{there is an index subset }I\subseteq [m],\mathrm{\mid }I\mathrm{\mid }\le d,\text{ such that }{R}_D(g(S_I))>ϵ\\ \text{and }g(S_I)(X_j)=c(X_j)\text{ for every }j\in [m]\end{array}\right\}\le {\sum }_{i=0}^d\left(\genfrac{}{}{0px}{}{m}{i}\right)(1-ϵ{)}^{m-i}\mathrm{.}$ 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.

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 $\left(\genfrac{}{}{0px}{}{n}{k}\right):=\mid [n{]}^k\mid$: $\left(\genfrac{}{}{0px}{}{m}{i}\right)$ 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.

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.

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.

Let $(\mathrm{\Theta },\mathcal{A},\pi )$ and $(\mathcal{Z},\mathcal{B},D)$ be probability spaces. Let $C\ge 0$, and let $\mathrm{\ell }:\mathrm{\Theta }\times \mathcal{Z}\to [0,C]$ be $\mathcal{A}\otimes \mathcal{B}$-measurable. Draw $S=(Z_1,\dots ,Z_m)$ from the product law $D^m$, where $m\ge 1$, and define $R(\theta )=\int \mathrm{\ell }(\theta ,z)D(dz)$ and ${\widehat{R}}_S(\theta )=m^{-1}{\sum }_{i=1}^m\mathrm{\ell }(\theta ,Z_i)$. Fix $\pi$ independently of $S$ and define $\mathrm{K}\mathrm{L}(\rho \mathrm{\parallel }\pi )$ as the supremum of ${\sum }_{A\in \mathcal{P}}\rho (A)\log (\rho (A)\mathrm{/}\pi (A))$ over finite measurable partitions $\mathcal{P}$ of $\mathrm{\Theta }$, with zero-numerator terms equal to $0$ and positive-numerator/zero-denominator terms equal to $+\mathrm{\infty }$. Let $\mathrm{\Lambda }=\{{\lambda }_1,\dots ,{\lambda }_N\}\subset (0,\mathrm{\infty })$ be a nonempty finite set fixed independently of the sample. For every $\delta \in (0,1)$, with probability at least $1-\delta$ over the sample, simultaneously for every probability measure $\rho$ satisfying $\pi (A)=0\Rightarrow \rho (A)=0$ for each $A\in \mathcal{A}$ and every $\lambda \in \mathrm{\Lambda }$, ${\mathbb{E}}_{\theta \sim \rho }R(\theta )\le {\mathbb{E}}_{\theta \sim \rho }{\widehat{R}}_S(\theta )+\frac{\lambda C^2}{8m}+\frac{\mathrm{K}\mathrm{L}(\rho \mathrm{\parallel }\pi )+\log (N\mathrm{/}\delta )}{\lambda }\mathrm{.}$

The PAC-Bayes KL generalization bound: for each fixed $\lambda$ and confidence value, one event controls every posterior average.

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

PAC-Bayes priors, posteriors, and relative entropy: a posterior is a probability measure absolutely continuous with respect to the sample-independent prior; relative entropy is the supremum over finite measurable partitions.

Alquier, User-friendly Introduction to PAC-Bayes Bounds, Chapter 2, Theorem 2.4 and proof: applies a union bound over a finite, sample-independent tuning grid.

Let $m,d\in \mathbb{N}$ with $m>d$. Let $(\mathcal{X},\mathrm{\Sigma })$ be a measurable space, let $c:\mathcal{X}\to \{0,1\}$ be measurable, and let $D$ be a probability measure on $\mathcal{X}$. Put $\mathcal{Z}=\mathcal{X}\times \{0,1\}$ with its product sigma-algebra. For each $0\le i\le d$, let $G_i:{\mathcal{Z}}^i\times \mathcal{X}\to \{0,1\}$ be a fixed jointly measurable reconstruction map, with $G_0$ measurable on $\mathcal{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<\cdots <i_k\}\subseteq [m]$ with $k\le 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)=\mathrm{\varnothing }$, 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)\mathrm{\ne }c(x)\}$. Fix $ϵ,\delta \in (0,1)$. If $d=0$ and $mϵ\ge \log (1\mathrm{/}\delta )$, or if $1\le d<m$ and $ϵ(m-d)\ge d\log \left(\frac{em}{d}\right)+\log (1\mathrm{/}\delta ),$ where $e$ is the base of the real exponential function, then $R_D(h_S)\le ϵ$ with probability at least $1-\delta$ over the independent observations.

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\le d\le m$, ${\sum }_{i=0}^d\left(\genfrac{}{}{0px}{}{m}{i}\right)\le (em\mathrm{/}d{)}^d$.

$1+x\le \exp (x)$ for every real $x$, hence $(1-p{)}^m\le \exp (-mp)$: $(1-p{)}^n\le \exp (-np)$ 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\mathrm{/}\exp (x)$: the real exponential is positive and $\exp (-x)=1\mathrm{/}\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.