Finite-description compression bound for trained classifiers

The following corrected finite-description form of Arora, Ge, Neyshabur, and Zhang's compression bound applies to a measurable sample-dependent score classifier. Let $(\mathcal{X},{\mathrm{\Sigma }}_X)$ be a nonempty measurable space, let $\mathcal{Y}=\{1,\dots ,K\}$ have the discrete sigma-algebra with $K\ge 2$, put ${\mathrm{\Sigma }}_Z={\mathrm{\Sigma }}_X\otimes 2^{\mathcal{Y}}$ on $Z=\mathcal{X}\times \mathcal{Y}$, and let $P$ be a probability law on $(Z,{\mathrm{\Sigma }}_Z)$. Let $m\ge 1$ and draw $S=((X_1,Y_1),\dots ,(X_m,Y_m))$ independently and identically distributed (IID) with law $P$, with sample space $Z^m$ carrying ${\mathrm{\Sigma }}_Z^{\otimes m}$. Fix integers $q\ge 0$, $r\ge 1$, a helper string $s$ independent of $S$, finite nonempty parameter 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$ (with the empty product a singleton when $q=0$), a distortion tolerance $ϵ>0$, and a confidence level $0<\delta <1$. For any score map $u$ with measurable coordinates, write $h_u(x)$ for the classifier that chooses the least index attaining the largest coordinate of $u(x)$. For each $a\in \mathcal{A}$, let $g_{s,a}:\mathcal{X}\to {\mathbb{R}}^K$ have measurable coordinates and put $h_{s,a}:=h_{g_{s,a}}$. Equip ${\mathbb{R}}^K$ with its Borel sigma-algebra. Let $F:Z^m\times \mathcal{X}\to {\mathbb{R}}^K$ be measurable for ${\mathrm{\Sigma }}_Z^{\otimes m}\otimes {\mathrm{\Sigma }}_X$, write $f_S(x)=F(S,x)$, and let $\alpha :Z^m\to \mathcal{A}$ be measurable for the discrete sigma-algebra on $\mathcal{A}$. Suppose that, for $P^m$-almost every $S$, ${\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)$ With natural logarithms, define $R_P(h):=P\{(x,y):h(x)\mathrm{\ne }y\},{\widehat{R}}_S(h):=\frac{1}{m}{\sum }_{i=1}^m\mathbf{1}\{h(X_i)\mathrm{\ne }{Y}_i\},$ $M_{f_S}(x,y):=f_S(x{)}_y-{\max }_{j\mathrm{\ne }y}{f}_S(x{)}_j,{\widehat{L}}_{\gamma }(f_S;S):=\frac{1}{m}{\sum }_{i=1}^m\mathbf{1}\{M_{f_S}(X_i,Y_i)\le \gamma \},\gamma \ge 0.$ Then, with probability at least $1-\delta$ over $S$, $R_P\left(h_{s,\alpha (S)}\right)\le {\widehat{L}}_{2ϵ}(f_S;S)+\sqrt{\frac{q\log r+\log (1\mathrm{/}\delta )}{2m}}\mathrm{.}$ In particular, the coordinatewise distortion $ϵ$ only guarantees preservation of an observed label when its original score margin is strictly greater than $2ϵ$. The conclusion bounds the selected compressed classifier $h_{s,\alpha (S)}$; it does not bound the original classifier $h_{f_S}$ unless a separate all-domain loss-preservation argument is supplied. The theorem assumes a suitable fixed-helper compressor and makes no claim that a network compression construction exists or that layer-stability or cushion hypotheses hold.

Margin-preserving compression of score classifiers: defines the finite codebook, fixed helper string, score distortion, least-index tie rule, margin, and empirical margin loss.

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

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

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

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

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

Basic identities for a probability measure: finite unions of events have probability at most the sum of their probabilities.

The Hoeffding MGF bound for a variable in a unit interval: for $0\le Y\le 1$, $\mathbb{E}\exp (\lambda (Y-\mathbb{E}Y))\le \exp ({\lambda }^2\mathrm{/}8)$ for every real $\lambda$; its proof is choice-free.

Measurable coordinatewise functions preserve independence: applying measurable coordinate maps to independent random elements preserves independence.

Expectations factor over finite products of independent random variables: expectations of finite products of nonnegative Borel functions of independent real variables factor.

Markov's inequality for random variables: for a nonnegative random variable $X$ and $a>0$, $\mathbb{P}(X\ge a)\le \mathbb{E}[X]\mathrm{/}a$.

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 exponential is continuous and strictly increasing.

Sums, scalar multiples, products, absolute values, maxima, minima and quotients with nonvanishing denominator of continuous functions are continuous, as are constants, the identity and every polynomial function: sums, scalar multiples, constants, and the identity function are continuous.

A composite of continuous functions is continuous, with no side hypothesis of the kind the composition of limits needs: a composite of continuous real functions is continuous.

The Borel sigma-algebra of a topological space: the Borel sigma-algebra is generated by open sets.

Law or distribution of a random element: the law of a random element is its pushforward probability measure.

Change of variables for expectation: $\mathbb{E}[g(X)]=\int gd{P}_X$ for a nonnegative measurable $g$ and a random element $X$ with law $P_X$.

The real exponential function and the number $e$ by a power series: defines the real exponential function used in the MGF and Markov argument.

The expectation of an indicator is the probability of the event: the expectation of the indicator of an event equals its probability.

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

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: supplies the product, quotient, reciprocal, and monotonicity laws for $\log$.

The exponential is positive and satisfies $\exp (-x)=1\mathrm{/}\exp (x)$: $\exp (-x)=1\mathrm{/}\exp (x)>0$ for every real $x$.

Arora et al., §2, Theorem 2.1 and Remarks 1–4: fixes the finite code family and helper-string model, and explicitly states that its conclusion concerns the compressed classifier.

Arora et al., supplementary material, Appendix A.1: gives the finite-code Hoeffding/union-bound route; the local proof corrects its margin step.

Shalev-Shwartz and Ben-David, Chapter 4 §4.2: independently proves finite-class bounded-loss uniform convergence by Hoeffding's inequality and a union bound.