Capacity is not a fixed number of a class — it is measured on your data: how well the class can fit pure coin-flips. Line up your sample, throw random signs σ ∈ {±1} at it, and ask the class to correlate with the noise as hard as it can. The average best correlation is the complexity. Down the center, data flows: the sample and its 2m sign patterns go in, the engine takes the sup then the mean, and R comes out — exact, by enumeration. The blue team builds and defends it; the red team tries to break it.
source Bartlett & Mendelson, Rademacher and Gaussian Complexities: Risk Bounds and Structural Results, JMLR 3 (2002) 463–482 — jmlr.org/papers/v3/bartlett02a.html. Rendered, not quoted.
Fix a sample of m points. A random sign vector σ labels them by coin-flip. The class earns its capacity by correlating with that noise:
R(H) = Eσ [ suph∈H (1/m) Σi σi h(xi) ]
Two operators, in order: the sup is worst-case — the single best-aligned hypothesis for THIS sign pattern. The mean over all 2m equally-likely σ is exact, no sampling. The current class H, as label vectors on the m points:
The VC dimension counts the largest sample a class can shatter — a coarse, combinatorial, worst-case-over-all-distributions integer.
Rademacher complexity is that same idea made data-dependent and real-valued: not "can it shatter some m points" but "how much does it correlate with noise on these points". A class that shatters the sample scores R = 1; VC is recovered as the loose ceiling. Each sphere is the next one's premise: VC in, a tighter, distribution-aware capacity out.
The blue team's live check: recompute R for the two exactly-known classes (a shattering class must give 1, a constant hypothesis 0), confirm Massart's bound holds, and confirm the generalization gap stays covered over fixed-seed samples. If red tampers, this badge is where it shows.
Two things feed the engine: a sample of m points (here abstract indices x1…xm) and the full set of 2m random-sign labelings σ ∈ {−1,+1}m. Every σ is one throw of m fair coins; enumerating all of them makes the expectation exact, not sampled.
A hypothesis h is a labeling of the same m points into {−1,+1}. The class H is a set of such labelings — that is the whole input to the panel below.
Aggregation over h: SUP — worst-case, the definition.
All 2m sign patterns for the current class — the winning hypothesis and its per-pattern correlation (1/m)·sup⟨σ,h⟩:
| σ (signs) | best h | (1/m)·⟨σ,h⟩ |
|---|
Change the class or m — R is enumerated on the spot from every σ, never looked up.
What the machine proves, by exact counting: R for the current class (left), and the two anchors that pin the scale — a class that realizes every sign pattern (shatters the sample) hits the maximum R = 1; a single constant hypothesis hits R = 0. From R fall two guarantees:
| quantity | value (current) |
|---|
Massart's finite-class bound and the Rademacher generalization bound; the blue witness (left) confirms them live, the red team (right) tries to make them wrong.
The empirical R here differs from the expected R over the distribution; the generalization theorem's tight constant is subtle (for 0–1 loss the loss-class Rademacher is half the classifier-class R, so the bound below is a valid but loose 2R). "Data-dependent" cuts both ways: sharper when you can compute it, useless when you cannot.
"Rademacher complexity is just VC dimension in disguise." Cut. VC is a distribution-free integer; Rademacher is a real number on your actual sample — strictly finer, and it can be small where VC is large.
"Take the average correlation over the whole class." Cut. The definition is the sup, worst-case over h. Averaging (the planted tamper) under-estimates capacity and erodes the bound's safety margin.
"Estimate R by sampling a few sign vectors." Kept, corrected. Legitimate for large m — but then it is an estimate. Here m is small, so all 2m are enumerated and R is exact.
The red team's move: swap the inner suph for a meanh — an average-case correlation instead of worst-case. R is under-estimated, so 2R shrinks and the generalization bound's safety margin erodes. The blue witness (window 7) is watching the exact anchor.
Replace the worst-case sup with the average over h and a shattering class drops from R=1 to R=0 — the witness recomputes, the anchor breaks, the badge turns red. Nothing is faked; the attack is real and it is caught.