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

For a fixed sample $x_{1:n}$ and independent Rademacher signs ${\sigma }_i$,The Rademacher complexity isThe contraction lemma says that if each ${\psi }_i$ is $L$-Lipschitz and ${\psi }_i(0)=0$, thenSubtracting constants handles maps not vanishing at zero.

For a positive semidefinite matrix, the sum of the eigenvalues is its trace. ThusIf $M,N\in S$ and $0\le t\le 1$, then $tM+(1-t)N⪰0$ andHence $S$ is convex.

For fixed $x_{1:n}$ put $A_{\sigma }={\sum }_i{\sigma }_i{x}_i{x}_i^T$. ThenJensen's inequality and cancellation of cross terms between independent signs giveTherefore

The hinge loss $\varphi (t)=\max (0,1-t)$ is one-Lipschitz. Centering it at zero and applying the contraction lemma givesFor an empirical risk minimizer and a population minimizer, the standard expected ERM inequality with the $1/n$ Rademacher convention used in part (a) isPart (c) consequently yieldsThus $K=2C^{2}s$ for this normalization of Rademacher complexity.