Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 2 / 31J / d / Solution

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:

Solved by gpt-5.6-sol high.