Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 1 / 31J (Mathematics of Machine Learning)

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

Choose $2m$ ordered points. Every subset of them has at most $m$ maximal consecutive runs, and those runs can be covered by at most $m$ closed intervals. Thus the points are shattered. On $2m+1$ ordered points, however, the alternating labelinghas $m+1$ separated positive runs and cannot be realized by a union of $m$ intervals. Therefore

These are indicators of affine half-spaces in ${\mathbb{R}}^p$. Adjoining a constant coordinate embeds their defining functions in the $(p+1)$-dimensional vector spaceThe VC dimension of a vector space bound therefore givesIn fact equality holds, but only the upper bound is required.

Fix sample points $(x_i,z_i)$, $1\le i\le n$. A labeling by $h(x,z)=f(x)g(z)$ is the coordinatewise product of one labeling that $\mathcal{F}$ realizes on $x_1,\dots ,x_n$ and one that $\mathcal{G}$ realizes on $z_1,\dots ,z_n$. There are at most the product of the two numbers of choices, so

For fixed $x_1,\dots ,x_n$, the vectoris again the coordinatewise product of a labeling realized by $\mathcal{F}$ and one realized by $\mathcal{G}$, now on the same sample. Hence there are at mostpossible products. Maximizing over samples proves the claimed inequality.

For one real coordinate, a union of $m$ intervals labels a fixed $n$-point sample by choosing at most $2m$ endpoints among the $n+1$ gaps, so the number of labelings is at most $(n+1{)}^{2m}$. Membership in a Cartesian product is the product of the $p$ coordinate-membership indicators. Applying part (c) repeatedly gives

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