Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1 / 31K / a

Let ${\epsilon }_1,\dots ,{\epsilon }_n$ be independent Rademacher signs. For the set of evaluation vectorsthe empirical Rademacher complexity isFor an independent sample $Z_1,\dots ,Z_n$,

For points $z_1,ldots,z_n$, letThe shattering coefficient and VC dimension areThus a set of $n$ points is shattered when every binary labeling occurs on it.

Take any $p+1$ points $z_1,ldots,z_{p+1}\in {\mathbb{R}}^p$. For each coordinate $j$, choose a point attaining the largest $j$th coordinate. At most $p$ points are chosen, so some point $z_k$ is not among them.

Consider the labeling that assigns $1$ to every chosen coordinate maximizer and $0$ to $z_k$. Any lower orthantcontaining all the chosen points must have $a_j\ge {\max }_i(z_i{)}_j$ for every $j$, and hence contains $z_k$ as well. This labeling is impossible. No $p+1$ points are shattered, soThis is the VC dimension bound for lower orthants.