= Solution
Let $\varepsilon_1,\ldots,\varepsilon_n$ be independent Rademacher signs. For the set of evaluation <vectors>
$$
\mathcal F(z_{1:n})=\left\{(f(z_1),\ldots,f(z_n)):f\in\mathcal F\right\},
$$
the empirical <Rademacher complexity> is
$$
\widehat R(\mathcal F(z_{1:n}))
=\mathbb E_\varepsilon\left[
\sup_{f\in\mathcal F}\frac1n\sum_{i=1}^n\varepsilon_i f(z_i)
\right].
$$
For an independent sample $Z_1,\ldots,Z_n$,
$$
R_n(\mathcal F)=\mathbb E_{Z_{1:n}}
\widehat R(\mathcal F(Z_{1:n})).
$$
Back to article page
