Deterministic sample-compression schemes

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.