Empirical Rademacher Finite Classes

Empirical Rademacher complexity measures a hypothesis class's ability to correlate with random noise on a specific fixed sample. By taking a fixed sample of size n, we can compute all distinct prediction vectors generated by the class on these points. We then evaluate how well these vectors can match completely random target labels (Rademacher variables, which are independent and take values -1 or +1 equiprobably). The complexity is the expected value, over all 2^n possible random sign assignments, of the maximum correlation achieved by any hypothesis in the class.

Worked Example: Constants Class

Consider a sample of size n = 4 and the "Constants" hypothesis class with an output scale of 1. This class has only two distinct hypothesis vectors regardless of the sample size: h_0 = (-1, -1, -1, -1) and h_1 = (1, 1, 1, 1).

There are 2^4 = 16 possible random sign vectors σ ∈ {-1, +1}^4. For each sign vector σ, we find the maximum correlation with our hypotheses. The correlation of hypothesis h with signs σ is (1/4) ∑ σ_i h_i.

Number of +1s in σ	Count (Combinations)	Corr(h_0, σ)	Corr(h_1, σ)	Supremum
0 (all -1)	1	1.0	-1.0	1.0
1	4	0.5	-0.5	0.5
2	6	0.0	0.0	0.0
3	4	-0.5	0.5	0.5
4 (all +1)	1	-1.0	1.0	1.0

The Empirical Rademacher complexity is the expectation of these suprema over all 16 sign vectors:

E[sup] = (1×1.0 + 4×0.5 + 6×0.0 + 4×0.5 + 1×1.0) / 16 = (1.0 + 2.0 + 0.0 + 2.0 + 1.0) / 16 = 6.0 / 16 = 0.375

This matches the independent calculation: with n=4, the Constants class has an Empirical Rademacher complexity of exactly 0.375.

Run the Experiment

You can interact with the Empirical Rademacher Finite Classes module to test different classes and parameters:

Set the Hypothesis class to Thresholds, Sample size to 4, and Output scale to 1.
Set the Probe signs to Alternating (i.e., +1, -1, +1, -1).
Observe that the Empirical Rademacher complexity is 0.59375.
The Probe supremum correlation is 0.0, and the Maximizing probe hypothesis is -1,-1,-1,-1 (the lexicographically first vector tied for max).
Change the Hypothesis class to All labelings. The Empirical Rademacher complexity becomes exactly 1.0 because the class can perfectly match any random noise vector.

Limitations

The Empirical Rademacher complexity only measures the capacity of a class on a specific, fixed set of sample points. It is not a direct generalization guarantee without additional probabilistic assumptions (such as the points being drawn i.i.d. from a distribution) and concentration inequalities. Furthermore, calculating the exact expectation by enumerating all 2^n sign vectors scales exponentially, meaning this exact calculation method is only computationally feasible for very small sample sizes.

References

The concepts of Rademacher complexity and its use in bounding the generalization error of learning algorithms are fundamentally detailed in statistical learning theory texts.

Percy Liang's CS229T Statistical Learning Theory notes discuss Rademacher complexity extensively. See: Statistical Learning Theory (Stanford CS229T).

Empirical Rademacher Finite Classes