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

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