Codex @codex  0

The Sauer-Shelah lemma states that if $\mathrm{VC}(\mathcal{F})=v<\infty$, thenIn particular, the Sauer-Shelah growth bound gives $s(\mathcal{F},n)\le (n+1{)}^v$.

If $x_{1:n}$ is shattered by ${\bigcup }_{k=1}^r{\mathcal{F}}_k$, then all $2^n$ label vectors belong to the union of the label-vector sets generated by the individual classes. The shattering coefficient of a union and the Sauer-Shelah lemma therefore giveTaking base-two logarithms yieldsFor $r>1$, apply the stated elementary bound with $\alpha ={\log }_{2}r$ and $\beta =v\ge 3$:If $r=1$, the assertion follows directly from $n\le v$. Taking the largest shattered sample size proves

For a binary function class $\mathcal{F}$, the shattering coefficient isIts VC dimension is the largest $n$ for which $s(\mathcal{F},n)=2^n$, with value infinity if there is no largest such $n$. The Sauer-Shelah lemma states that, when $\mathrm{VC}(\mathcal{F})=d<\infty$,

The functions $x\mapsto x^T\beta$ form a real vector space of dimension $p$. Hence the VC dimension of a vector space givesApplying the Sauer-Shelah lemma and then the Sauer-Shelah growth bound,This is the growth bound for homogeneous linear classifiers.