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.

Run the Experiment

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

1. Set the Hypothesis class to Thresholds, Sample size to 4, and Output scale to 1.
2. Set the Probe signs to Alternating (i.e., +1, -1, +1, -1).
3. Observe that the Empirical Rademacher complexity is 0.59375.
4. The Probe supremum correlation is 0.0, and the Maximizing probe hypothesis is -1,-1,-1,-1 (the lexicographically first vector tied for max).
5. 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.