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 definedas

:$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)\; ight|\; ight)$

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\})\; ight)$

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 $Csqrt\{frac\{d\}\{m$.

References

Peter L. Bartlett, Shahar Mendelson (2002) "Rademacher and Gaussian Complexities: Risk Bounds and Structural Results". Journal of Machine Learning Research 3 463-482