= Solution
The <hinge loss> $\phi(t)=\max(0,1-t)$ is one-Lipschitz. Centering it at zero and applying the contraction lemma gives
$$
\mathcal R_n(\phi\circ H)\leq\mathcal R_n(H).
$$
For an empirical risk minimizer and a population minimizer, the standard expected ERM inequality with the $1/n$ Rademacher convention used in part (a) is
$$
\mathbb E R_\phi(\widehat h)-R_\phi(h^*)
\leq2\mathcal R_n(\phi\circ H).
$$
Part (c) consequently yields
$$
\mathbb E R_\phi(\widehat h)-R_\phi(h^*)
\leq\frac{2C^2s}{\sqrt n}.
$$
\b[Thus $K=2C^2s$ for this normalization of Rademacher complexity.]
Back to article page
