Margin-preserving compression of score classifiers

Let $(\mathcal{X},{\mathrm{\Sigma }}_X)$ be a nonempty measurable instance space, let $\mathcal{Y}=\{1,\dots ,K\}$ have its discrete sigma-algebra with $K\ge 2$, and equip $\mathcal{X}\times \mathcal{Y}$ and its finite powers with their product sigma-algebras. Let $P$ be a probability law on $\mathcal{X}\times \mathcal{Y}$. For an integer $m\ge 1$, write a sample as $S=((X_1,Y_1),\dots ,(X_m,Y_m))$. A score map $u=(u_1,\dots ,u_K):\mathcal{X}\to {\mathbb{R}}^K$ is coordinatewise measurable when each $u_k:(\mathcal{X},{\mathrm{\Sigma }}_X)\to (\mathbb{R},\mathcal{B}(\mathbb{R}))$ is measurable. Define its classifier by the least-index tie rule

$h_u(x):=\min \{k\in \mathcal{Y}:u_k(x)={\max }_{j\in \mathcal{Y}}{u}_j(x)\}$

and its margin on label $y$ by

$M_u(x,y):=u_y(x)-{\max }_{j\in \mathcal{Y},j\mathrm{\ne }y}{u}_j(x)\mathrm{.}$

For each $k\in \mathcal{Y}$, $\{x:h_u(x)=k\}={\bigcap }_{j<k}\{x:u_k(x)>u_j(x)\}\cap {\bigcap }_{j>k}\{x:u_k(x)\ge u_j(x)\},$ and each comparison set is measurable; an intersection over no indices means $\mathcal{X}$. Since $\mathcal{Y}$ is finite, $M_u$ is measurable on $\mathcal{X}\times \mathcal{Y}$ as well. The population zero-one risk is $R_P(h_u):=P\{(x,y):h_u(x)\mathrm{\ne }y\}\mathrm{.}$ For a sample $S$ of length $m$ and $\gamma \ge 0$, the empirical margin loss is ${\widehat{L}}_{\gamma }(u;S):=\frac{1}{m}{\sum }_{i=1}^m\mathbf{1}\{M_u(X_i,Y_i)\le \gamma \}\mathrm{.}$ The event defining $R_P(h_u)$ is measurable by measurability of $h_u$.

Fix integers $q\ge 0$ and $r\ge 1$. A fixed-helper finite parameter codebook consists of a helper string $s$ fixed independently of the sample, finite nonempty sets $D_1,\dots ,D_q$ with $\mathrm{\mid }{D}_j\mathrm{\mid }\le r$, a nonempty code set $\mathcal{A}\subseteq {\prod }_{j=1}^q{D}_j$, and one coordinatewise measurable decoder score map $g_{s,a}:\mathcal{X}\to {\mathbb{R}}^K$ for each $a\in \mathcal{A}$. For $q=0$, the empty product is the singleton containing the empty tuple. The codebook and all its decoders are fixed independently of the sample, so $\mathrm{\mid }\mathcal{A}\mathrm{\mid }\le r^q$.

Let $F:(\mathcal{X}\times \mathcal{Y}{)}^m\times \mathcal{X}\to {\mathbb{R}}^K$ be measurable for the product sigma-algebra on its domain and the Borel sigma-algebra on ${\mathbb{R}}^K$. Let $\alpha :(\mathcal{X}\times \mathcal{Y}{)}^m\to \mathcal{A}$ be measurable, where $\mathcal{A}$ has its discrete sigma-algebra, and write $f_S(x):=F(S,x)$. For $ϵ>0$, the sample-dependent trained score map $f_S$ is $ϵ$-compressible by this codebook on a sample $S$ if ${\max }_{k\in \mathcal{Y}}\mathrm{\mid }{f}_S(X_i{)}_k-g_{s,\alpha (S)}(X_i{)}_k\mathrm{\mid }\le ϵ(1\le i\le m)\mathrm{.}$ The code $\alpha (S)$ may depend on $S$; the helper string, codebook, and decoders remain fixed independently of the sample.

Measurable spaces and measurable sets: a measurable space consists of a set equipped with a sigma-algebra.

Supervised prediction problems: supplies measurable instance and label spaces, a joint probability law, measurable predictors, and a measurable loss.

Population and empirical risk: population risk is the nonnegative integral of the loss, and empirical risk is its finite sample average.

A measurable function between measurable spaces: measurability is the preimage condition.

The product sigma-algebra and its finite iterates: finite product sigma-algebras are generated recursively by measurable rectangles.

Arithmetic and lattice operations preserve measurability whenever they are defined: finite maxima and arithmetic combinations of measurable real-valued functions are measurable.

Arora et al., §2, Definitions 1–2: score closeness on training inputs with a finite code family and a helper fixed before sampling.

Shalev-Shwartz and Ben-David, Chapter 4 §4.2: finite measurable hypothesis classes and empirical/population zero-one risk conventions.