Generalized Sauer's Lemma

In words...

Sauer's Lemma provides a polynomial bound on the growth function of a class of binary classifiers based on its VC-dimension.

This result can be generalized to apply to classes of functions taking values in a finite set. By a quantization argument, this can also be used for real-valued function classes, as in proving margin-based error bounds.

In pictures...

In maths...

Given a function class $\F$ of functions from $\X \rightarrow \{1,\dots,m\}$ with fat-shattering dimension at unit scale no greater than $d$, $\fat_{1}(\F) \leq d$, the uniform packing number at scale $\epsilon=2$ of $\F$ with respect to the $\ell_{\infty}$ pseudo-metric is bounded by $$ \mathcal{M}_{\infty}(2,\F,n) < 2(n m^2)^{\lceil \log_2 p \rceil} $$ with $$ p = \sum_{k=0}^{d} \begin{pmatrix}n\\k\end{pmatrix} m^k $$ or $$ \mathcal{M}_{\infty}(2,\F,n) \leq 2(n m^2)^{d \log_2 \left(\frac{e nm}{d} \right) } $$

Proof:

Pigeonhole principle

The pigeonhole principle states that when dividing a set of $n$ objects into $m$ subsets with $n> k m$, at least one subset must contain more than $k$ objects.

Notes

The original proof of this lemma can be found in .