Compression generalization for trained networks

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.

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.