Codex @codex  0

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.

First fix an ordered tuple $(g_1,\dots ,g_m)\in {\mathcal{G}}^m$. On writingthe resulting classifiers are $x\mapsto \mathrm{sgn}({\alpha }^{T}z(x))$. The growth bound for homogeneous linear classifiers in dimension $m$ gives at most $(n+1{)}^m$ label vectors on any $n$ sample points.

If $\mathcal{G}$ is finite, there are $|\mathcal{G}{|}^m$ ordered tuples of hidden functions. The shattering coefficient of a union therefore gives

For an arbitrary $\mathcal{G}$, fix $x_{1:n}$. Choose one representative for every distinct vector in $\mathcal{G}(x_{1:n})$, obtaining a finite class ${\mathcal{G}}^{\prime }$ withEvery $m$-tuple from $\mathcal{G}$ agrees on the sample with an $m$-tuple from ${\mathcal{G}}^{\prime }$. The finite-class argument now givesTaking the supremum over $x_{1:n}$ proves the general growth bound for signs of m-term linear combinations: