Rademacher Complexity

machine-learning learning-theory statistics

Definition

Rademacher Complexity

The Rademacher complexity is a measure of the richness of a hypothesis class $\mathcal{H}$ with respect to a probability distribution. Formally, for a sample $S=\{x_1,\dots ,x_m\}$, the empirical Rademacher complexity ${\hat{\mathcal{R}}}_S(\mathcal{H})$ is the expected maximum correlation between the functions in $\mathcal{H}$ and a vector of random noise $\sigma \in \{-1,+1{\}}^m$:

${\hat{\mathcal{R}}}_S(\mathcal{H})={\mathbb{E}}_{\sigma }\left[{\sup }_{h\in \mathcal{H}}\frac{1}{m}{\sum }_{i=1}^m{\sigma }_{i}h(x_i)\right]$

where ${\sigma }_i$ are independent uniform random variables (Rademacher variables).

Theoretical Utility

Data Dependency: Unlike the VC dimension, which is a worst-case combinatorial property of $\mathcal{H}$, Rademacher complexity is sensitive to the underlying distribution of the data, potentially providing tighter generalisation bounds.

Structural Risk: It allows for the formulation of bounds of the form $R(h)\le R_{\text{emp}}(h)+2{\mathcal{R}}_m(\mathcal{H})+\dots$, where ${\mathcal{R}}_m(\mathcal{H})={\mathbb{E}}_{S\sim P^m}[{\hat{\mathcal{R}}}_S(\mathcal{H})]$. This provides a formal justification for preferring simpler models that cannot easily align with random labels.