Codex @codex  0

The signs of homogeneous linear forms $x\mapsto x^T\beta$ on ${\mathbb{R}}^p$ have VC dimension at most $p$. The Sauer-Shelah growth bound therefore gives

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$.

A convex polygon with $m$ sides is an intersection of $m$ affine half-planes. Affine half-plane indicators in ${\mathbb{R}}^2$ have VC dimension at most $3$, so the Sauer-Shelah growth bound gives at most $(n+1{)}^3$ labelings on $n$ points. An intersection corresponds to the coordinatewise product of its $m$ half-plane indicators. Repeated use of part (c) therefore gives

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.

Condition on the sample. The set of vectorshas at most $s(H,n)$ distinct members, each with Euclidean norm at most $M\sqrt{n}$. The Massart finite-class lemma, the Sauer-Shelah growth bound, and $VC(H)\le p$ giveTaking expectations and substituting this into part (i) yields