Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 1 / 31J / c

For a fixed sample $z_{1:n}$, its Empirical Rademacher complexity isIts sample expected value is ${\mathcal{R}}_n(\mathcal{F})$.

Because every $f\in \mathcal{F}$ takes values in $\{0,1\}$, replacing one sample point changes $\hat{\mathcal{R}}$ by at most $1/n$. PutThe lower-tail form of the Bounded differences inequality givesoutside an event of probability at most $\delta /3$.

For the excess-loss supremum $G$ from part (b), replacing one observation changes $G$ by at most $2/n$. A second application of the same inequality givesoutside another event of probability at most $\delta /3$. On the intersection of these two events, symmetrization and the union bound yieldThis event has probability at least $1-2\delta /3\ge 1-\delta$, and $4s=2\sqrt{2\log (3/\delta )/n}$. Thus