= Solution
For a fixed sample $x_{1:n}$ and independent Rademacher signs $\sigma_i$,
$$
\widehat{\mathcal R}(H(x_{1:n}))
=\mathbb E_\sigma\sup_{h\in H}\frac1n\sum_{i=1}^n\sigma_i h(x_i).
$$
The <Rademacher complexity> is
$$
\mathcal R_n(H)=\mathbb E_{X_{1:n}}\widehat{\mathcal R}(H(X_{1:n})).
$$
The contraction lemma says that if each $\psi_i$ is $L$-Lipschitz and $\psi_i(0)=0$, then
$$
\mathbb E_\sigma\sup_{h\in H}\frac1n\sum_i\sigma_i\psi_i(h(x_i))
\leq L\widehat{\mathcal R}(H(x_{1:n})).
$$
Subtracting constants handles maps not vanishing at zero.
Back to article page
