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

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.

Put $D=y^{(1)}-y^{(0)}$ and define the loss classSince $\hat{h}$ minimizes $\hat{Q}$,The expectation of the second term is zero. Symmetrization of the first givesTherefore the expected excess-risk bound for empirical risk minimization gives

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