Rademacher complexity

In statistics and machine learning, Rademacher complexity measures richness of a class of real-valued functions with respect to a probability distribution.

Let ${\mathcal {F}}$ be a class of real-valued functions defined on a domain space $Z$. The empirical Rademacher complexity of ${\mathcal {F}}$ on a sample $S=(z_{1},z_{2},\dots ,z_{m})\in Z^{m}$ is defined as

${\widehat {\mathcal {R}}}_{S}({\mathcal {F}})={\frac {2}{m}}\ \operatorname {E} \left(\sup _{f\in {\mathcal {F}}}\left|\sum _{i=1}^{m}\sigma _{i}f(z_{i})\right|\right)$

where $\sigma _{1},\sigma _{2},\dots ,\sigma _{m}$ are independent random variables such that $\Pr(\sigma _{i}=+1)=\Pr(\sigma _{i}=-1)=1/2$ for any $i=1,2,\dots ,m$. The random variables $\sigma _{1},\sigma _{2},\dots ,\sigma _{m}$ are referred to as Rademacher variables.

Let $P$ be a probability distribution over $Z$. The Rademacher complexity of the function class ${\mathcal {F}}$ with respect to $P$ for sample size $m$ is

${\mathcal {R}}_{m}({\mathcal {F}})=\operatorname {E} \left({\widehat {\mathcal {R}}}_{S}({\mathcal {F}})\right)$

where the above expectation is taken over an identically independently distributed (i.i.d.) sample $S=(z_{1},z_{2},\dots ,z_{m})$ generated according to $P$.

One can show, for example, that there exists a constant $C$, such that any class of $\{0,1\}$-indicator functions with Vapnik-Chervonenkis dimension $d$ has Rademacher complexity upper-bounded by $C{\sqrt {\frac {d}{m}}}$.