= Solution
Let $\varepsilon_1,\ldots,\varepsilon_n$ be <independent random variables>[independent] <Rademacher random variable>[Rademacher signs], also independent of the <independent and identically distributed random variables>[i.i.d. sample] $Z_{1:n}$. With the $1/n$ normalization, the <Rademacher complexity> is
$$
\mathcal R_n(\mathcal F)
=\mathbb E_{Z,\varepsilon}\left[
\sup_{f\in\mathcal F}\frac1n\sum_{i=1}^n
\varepsilon_i f(Z_i)
\right].
$$
The <Rademacher symmetrization inequality> is
$$
\boxed{
\mathbb E\left[
\sup_{f\in\mathcal F}\frac1n\sum_{i=1}^n
\bigl(f(Z_i)-\mathbb Ef(Z_i)\bigr)
\right]
\leq2\mathcal R_n(\mathcal F).
}
$$
The <Bounded differences inequality> states that if $W=g(U_1,\ldots,U_n)$ for <independent random variables> $U_i$, and replacing only $U_i$ can change $g$ by at most $c_i$, then for every $t>0$,
$$
\boxed{
\mathbb P(W-\mathbb EW\geq t)
\leq\exp\left(-\frac{2t^2}{\sum_{i=1}^nc_i^2}\right).
}
$$
The same estimate holds for the lower tail $\mathbb P(W-\mathbb EW\leq-t)$.
Back to article page
