Ureidoglycolate hydrolase

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

Given a training sample $S=(z_1,z_2,\dots ,z_m)\in Z^m$, and a hypotheses set $\mathcal{\mathscr{H}}$ (where $\mathcal{\mathscr{H}}$ is a class of real-valued functions defined on a domain space $Z$), the empirical Rademacher complexity of $\mathcal{\mathscr{H}}$ is defined as:

${\widehat{\mathcal{ℛ}}}_S(\mathcal{\mathscr{H}})=\frac{2}{m}\mathbb{𝔼}\left[{\sup }_{h\in \mathcal{\mathscr{H}}}|\sum _{i=1}^m{\sigma }_{i}h(z_i)|\right|S]$

where ${\sigma }_1,{\sigma }_2,\dots ,{\sigma }_m$ are independent random variables such that $\mathrm{Pr}({\sigma }_i=+1)=\mathrm{Pr}({\sigma }_i=-1)=1/2$ for $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{\mathscr{H}}$ with respect to $P$ for sample size $m$ is:

${\mathcal{ℛ}}_m(\mathcal{\mathscr{H}})=\mathbb{𝔼}[{\widehat{\mathcal{ℛ}}}_S(\mathcal{\mathscr{H}})]$

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}}$.

Gaussian complexity

Gaussian complexity is a similar complexity with similar physical meanings, and can be obtained from the previous complexity using the random variables $g_i$ instead of ${\sigma }_i$, where $g_i$ are Gaussian i.i.d. random variables with zero-mean and variance 1, i.e. $g_i\sim \mathcal{𝒩}(0,1)$.

References

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

• Giorgio Gnecco (2008) Approximation Error Bounds via Rademacher's Complexity. Applied Mathematical Sciences, Vol. 2, 2008, no. 4, 153 - 176