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

${\hat{R}}_{\varphi }(h)=n^{-1}{\sum }_{i=1}^n\varphi (Y_{i}h(X_i))$.

${\mathcal{R}}_n(\mathcal{H})=E{\sup }_{h\in \mathcal{H}}|n^{-1}{\sum }_i{\epsilon }_{i}h(X_i)|$, with the expectation over data and independent Rademacher signs.

Because $\hat{R}(\hat{h})\le \hat{R}(h^{\ast })$, adding and subtracting empirical risks and taking expectations leaves at most $E{\sup }_h(R(h)-\hat{R}(h))$. Symmetrization and the unit-Lipschitz contraction lemma for hinge loss bound this by $2{\mathcal{R}}_n(\mathcal{H})$.

Each $Z_j=n^{-1}{\sum }_i{\epsilon }_i{X}_{ij}$ is $1/\sqrt{n}$-sub-Gaussian. Applying the exponential-moment bound to the $2p$ variables $\pm Z_j$ and optimizing the parameter gives $E{\max }_j|Z_j|\le \sqrt{2\log (2p)/n}$.

For fixed hidden units, the supremum over $\Vert \alpha {\Vert }_1\le \lambda$ is $\lambda$ times the largest absolute unit correlation. Taking the further supremum over admissible ${\beta }_k$ gives exactly the displayed bound.

The Rademacher contraction lemma for ReLU (which is 1-Lipschitz and vanishes at zero), duality between ${\ell }_1$ and ${\ell }_{\infty }$, and part (d) give ${\mathcal{R}}_n(\mathcal{H})\le 2\lambda \sqrt{2\log (2p)/n}$. Combining with part (c) gives the claimed $4\lambda \sqrt{2\log (2p)}/\sqrt{n}$.