Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 2 / 31L / d

Use the empirical Rademacher conventionBecause $H_3$ is symmetric under $h\mapsto -h$, optimizing a linear functional over the positive ${\ell }^1$ hull defining $\mathcal{F}$ gives

By part (c), $VC(H_3)\le D=d(d+1)/2$. Sauer--Shelah therefore bounds the number $N$ of distinct label vectors on the sample byMassart's finite-class lemma states that for $A\subseteq \{-1,1{\}}^n$,Applying it to the distinct label vectors of $H_3$ gives