What is Rademacher Complexity?
Rademacher complexity measures how well a function class can correlate with random noise:
R̂(F) = Eσ[supf∈F (1/n)Σi σif(xi)]
Breaking down the formula:
- RÌ‚(F): The empirical Rademacher complexity of function class F
- F: A set of functions (e.g., all linear functions, all degree-3 polynomials)
- Eσ: Expected value over random σ variables
- σi: Random ±1 labels (Rademacher random variables)
- supf∈F: Supremum (maximum) over all functions in class F
- n: Number of data points
- f(xi): Function f evaluated at data point xi
- Σi: Sum over all data points i = 1 to n
In plain English: For each random labeling, find the function in F that best correlates
with those random labels. Average this over many random labelings. The result tells you how well
the function class can "memorize" pure noise.
Key Insights:
- High complexity (close to 1) → can fit random patterns → risk of overfitting
- Low complexity (close to 0) → can't fit noise → better generalization
- Complexity depends on both the function class F and the data distribution
Why It Matters
Rademacher complexity provides a data-dependent measure of model capacity. Unlike VC dimension, it considers the actual data distribution, making it more practical for understanding generalization bounds.
Simple Example:
Imagine you have 10 data points and you randomly assign each one a label of +1 or -1 by flipping a coin.
- A
constant function (always outputs same value) will correlate poorly with random labels
- A
degree-10 polynomial can perfectly fit any 10 points, even random ones!
- The polynomial has higher Rademacher complexity = more prone to overfitting