Rademacher Complexity

Counting hypotheses works when there are finitely many of them. Count the members of your class, take a logarithm, and the union bound tells you how much data you need. But a linear model has uncountably many settings, and counting stops working.

VC dimension patches this by asking a combinatorial question — how many points can the class label in every possible way? It is a genuine advance, but it has two irritating properties. It ignores your data entirely, so a class that is wildly flexible in regions where your data never goes is charged full price. And it is a single integer you have to derive with a proof, not something you can measure on a Tuesday afternoon.

Rademacher complexity replaces both problems with one experiment you can actually run: take your inputs, throw away the labels, replace them with coin flips, and see how well the class can fit the noise. A class that can match random labels closely is a class that will match spurious patterns in real labels closely. The number that comes out is a complexity measure, it depends on your actual data, and it plugs straight into a generalization bound.

The analogy: the shuffled-returns test

Every quant research group eventually runs this experiment. Take the strategy pipeline, feed it a target that has been randomly shuffled so that by construction there is nothing to find, and see what backtest Sharpe the search produces anyway.

If the pipeline returns a Sharpe of 0.1 on shuffled data, it is a disciplined pipeline; whatever it finds on real data is probably real. If it returns 1.8 on shuffled data, then a real-data Sharpe of 1.8 means precisely nothing — the machinery manufactures that number from noise alone.

Rademacher complexity is that experiment written as a definition. The "shuffle" is a fresh coin flip per observation, and the "Sharpe on noise" is how strongly the best model in the class can correlate with those flips.

Writing it down

Let $x_1, \dots, x_n$ be your inputs. Draw independent Rademacher variables $\sigma_1, \dots, \sigma_n$, each equal to $+1$ or $-1$ with probability one-half — pure fair-coin labels, carrying no information whatsoever.

The empirical Rademacher complexity of a class $\mathcal{F}$ on this sample is

$$\hat{\mathfrak{R}}_S(\mathcal{F}) = \mathbb{E}_{\sigma}\left[\; \sup_{f \in \mathcal{F}} \; \frac{1}{n}\sum_{i=1}^{n} \sigma_i\, f(x_i) \right]$$

Take it apart. The inner sum $\frac{1}{n}\sum_i \sigma_i f(x_i)$ is the correlation between one model's outputs and the coin flips — near $+1$ if the model happens to agree with the noise, near $0$ if it is unrelated. The $\sup$ picks the single best-agreeing model in the class, which is what a fitting procedure would find. The $\mathbb{E}_\sigma$ averages over many independent redraws of the coins, so no single lucky shuffle dominates.

In words: on average over random label assignments, how well can the best member of this class fit them? The answer sits between 0 and 1 for models that output $\pm 1$.

Two anchors make the scale concrete. If $\mathcal{F}$ contains exactly one fixed function, the $\sup$ does nothing and $\mathbb{E}_\sigma[\frac{1}{n}\sum \sigma_i f(x_i)] = 0$, because each $\sigma_i$ averages to zero. If $\mathcal{F}$ contains every function from the sample to $\pm 1$, the $\sup$ can always choose $f(x_i) = \sigma_i$, giving $\frac{1}{n}\sum \sigma_i^2 = 1$. Zero means no capacity to chase noise; one means total capacity.

Worked example 1: computing it exactly, by hand

Take three points on a line, $x_1 < x_2 < x_3$, and let $\mathcal{H}$ be one-sided threshold rules: pick a cut, label $+1$ above it and $-1$ below. Only four label patterns are achievable — $(-,-,-)$, $(-,-,+)$, $(-,+,+)$, $(+,+,+)$ — because a threshold cannot produce a $+$ below a $-$.

Now enumerate all $2^3 = 8$ coin-flip vectors and, for each, find the achievable pattern that agrees best. The score is $\sum_i \sigma_i h(x_i)$, which is (number of agreements) minus (number of disagreements).

coin flips $\sigma$	best achievable pattern	$\sum_i \sigma_i h(x_i)$
$(+,+,+)$	$(+,+,+)$	3
$(+,+,-)$	$(+,+,+)$	1
$(+,-,+)$	$(-,-,+)$	1
$(+,-,-)$	$(-,-,-)$	1
$(-,+,+)$	$(-,+,+)$	3
$(-,+,-)$	$(-,-,-)$	1
$(-,-,+)$	$(-,-,+)$	3
$(-,-,-)$	$(-,-,-)$	3

The eight scores sum to $3+1+1+1+3+1+3+3 = 16$, so the average is $16/8 = 2$. Divide by $n = 3$:

$$\hat{\mathfrak{R}}_S(\mathcal{H}) = \frac{2}{3} = 0.667$$

Sanity-check it against the anchors. A single fixed rule scores $0$. All eight patterns available would score $1$ (the $\sup$ always matches the coins exactly). Thresholds reach four of the eight patterns and land at $0.667$ — flexible, but not able to fit everything. The number behaves exactly as a capacity measure should, and nothing about it required a theorem.

Worked example 2: from a shuffle test to a real bound

For binary classification with 0–1 loss, the standard result says that with probability at least $1-\delta$, every $h$ in the class satisfies

$$R(h) \;\le\; \hat{R}_S(h) \;+\; \hat{\mathfrak{R}}_S(\mathcal{H}) \;+\; 3\sqrt{\frac{\ln(2/\delta)}{2n}}$$

In words: true error is at most training error, plus how well the class fits noise, plus a small term for the luck of the draw. (The textbook version has a factor of 2 on a complexity computed over the loss class; for 0–1 loss that quantity is exactly half the complexity of the hypothesis class, so the two cancel and the form above is what you use.)

Take $n = 2{,}000$ and $\delta = 0.05$. The last term is

$$3\sqrt{\frac{\ln 40}{4000}} = 3\sqrt{\frac{3.6889}{4000}} = 3\sqrt{0.00092222} = 3 \times 0.03037 = 0.0911$$

Now measure $\hat{\mathfrak{R}}_S$ the practical way. Replace all 2,000 labels with coin flips, refit, record the best training accuracy $a$; repeat twenty times and average. For a $\pm 1$ classifier the correlation with the coins is exactly $2a - 1$, because agreements minus disagreements over $n$ is $a - (1-a)$.

Model A — an unrestricted gradient-boosted tree. Average accuracy on shuffled labels: $a = 0.71$. So $\hat{\mathfrak{R}}_S = 2(0.71) - 1 = 0.42$. Its real training error is a flattering $0.05$, giving

$$R \le 0.05 + 0.42 + 0.0911 = 0.561$$

Worse than a coin flip. The bound is vacuous — and it should be, because a model that can reach 71% on pure noise has told you its 95% on real data proves nothing.

Model B — a regularised linear model. Shuffled accuracy $a = 0.53$, so $\hat{\mathfrak{R}}_S = 0.06$. Its real training error is a less impressive $0.14$:

$$R \le 0.14 + 0.06 + 0.0911 = 0.291$$

A usable guarantee. Model A looked three times better on the training set and is the one you cannot trust, and one shuffle experiment on your own data — no theorems, no derivations — is what revealed it.

The explorer below is the same story interactively: increase classifier flexibility and watch the boundary start tracking individual points rather than the underlying structure. A class that can do that to real data can do it to coin flips.

What this means in practice

The shuffle test is the cheapest model-risk check you own. Any research pipeline — feature selection, hyperparameter search, the lot — can be pointed at a shuffled target. Whatever performance survives is your complexity, and every real result must clear it before you believe anything.

It is data-dependent, which is the whole point. VC dimension charges a linear classifier in 500 dimensions for 500 dimensions' worth of flexibility even if your data lies on a two-dimensional surface. Rademacher complexity looks at the points you actually have and prices the flexibility you actually used, which is why margin-based and norm-based bounds derived from it are far tighter for large-margin classifiers.

It gives the right scaling law. For a linear class with weight norm at most $B$ and inputs of norm at most $X$, $\hat{\mathfrak{R}}_S \le BX/\sqrt{n}$. With $B = 2$, $X = 3$ and $n = 2{,}000$ that is $6/44.72 = 0.134$; at $n = 20{,}000$ it falls to $6/141.4 = 0.042$. Ten times the data, roughly a third of the complexity penalty — the familiar $1/\sqrt{n}$ again.

Shrinking $B$ shrinks the bound directly. That is the theoretical justification for weight decay stated in one line: constraining the norm of the weights literally reduces the measured capacity to fit noise.

Practise it

1. Two points, threshold rules on a line. Enumerate the four coin-flip vectors and compute $\hat{\mathfrak{R}}_S$. (Answer: achievable patterns are $(-,-)$, $(-,+)$, $(+,+)$; best scores are $2, 0, 2, 2$; average $1.5$, divided by $n=2$ gives $0.75$.)
2. A model reaches 62% accuracy on shuffled labels. What is $\hat{\mathfrak{R}}_S$? (Answer: $2(0.62) - 1 = 0.24$.)
3. With that model, $n = 5{,}000$, $\delta = 0.05$ and a real training error of $0.19$, what does the bound give? (Answer: $3\sqrt{3.6889/10{,}000} = 0.0576$, so $R \le 0.19 + 0.24 + 0.058 = 0.488$ — barely better than guessing.)
4. How much data would Model A in example 2 need before its bound drops below 0.30, holding its shuffled accuracy fixed? (Answer: none — the $0.42$ complexity term does not shrink with $n$ unless the class is constrained. Only reducing capacity helps.)