Rademacher Complexity

machine-learning learning-theory statistics

Definition

Rademacher Complexity

The Rademacher complexity is a measure of the richness of a hypothesis class with respect to a probability distribution. Formally, for a sample , the empirical Rademacher complexity is the expected maximum correlation between the functions in and a vector of random noise :

where are independent uniform random variables (Rademacher variables).

Theoretical Utility

Data Dependency: Unlike the VC dimension, which is a worst-case combinatorial property of , 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 , where . This provides a formal justification for preferring simpler models that cannot easily align with random labels.