A class that can match many arbitrary label patterns may fit noise as well as signal. Rademacher complexity asks a quantitative version of that question on the observed inputs: how strongly can a function from a class correlate with independent random signs? Unlike a simple count of hypotheses, its value can depend on where the sample lies.
Random signs on a fixed sample
Let be i.i.d. from a fixed distribution , with , and let be a nonempty class of measurable functions fixed before the sample. Write and . Assume the suprema used below are measurable, including those involving independent ghost samples and signs; finite or countable classes suffice, as do the continuous compact-parameter examples below.
All logarithms below are natural.
Definition 2.5.1
(Empirical and expected Rademacher complexity)
Given a sample , let be independent uniform signs in , independent of the sample. Define
The same must be used at all sample points. The signs are an analytical probe, not labels supplied to a training algorithm. The expectation over signs is outside the supremum: for each sign vector the supremum may choose a different function. For any fixed member, its signed sum has expectation zero, so .
Worked example 2.5.2
(Two constant functions)
Let consist of the constant-zero and constant-one functions. For , the supremum is . Its expectation is : only the two-positive-sign case contributes. This is a complexity of the class on the sample, not its training error or a probability of misclassification.
A uniform bound from symmetrization
Theorem 2.5.3
(Empirical Rademacher generalization bound)
For , with probability at least over the i.i.d. sample, simultaneously for every ,
For a fixed class of loss functions this controls population loss by empirical loss; the complexity must be computed for that loss class, not automatically for the underlying predictors. It remains valid for a function selected from the class after seeing the sample, because the event is simultaneous.
Proof
(Ghost sample, symmetrization and bounded differences)
Let and introduce an independent ghost sample with the same distribution. Since , moving the expectation outside the supremum gives
Each pair is exchangeable. Independently swapping pairs according to random signs leaves their joint distribution unchanged, so
For the inequality, split the supremum of the difference into two suprema; the sign vector has the same distribution as its negative. This is the symmetrization step.
We use the bounded-differences inequality: if changing the th independent input changes a function by at most , its deviation above its mean by has probability at most ; the same bound holds below its mean. It follows, for example, by applying Hoeffding's lemma to the successive conditional-expectation martingale differences. Changing one sample point changes either or by at most , because every function value is in . With , the upper deviation of and lower deviation of each fail with probability at most . On their common event,
Since for every member, the theorem follows.
Proof X-ray
Why the ghost sample and signs appear
The ghost sample is used only in the proof. Pairwise swaps turn a difference between two empirical means into a signed difference. Separating the resulting supremum produces two copies of the complexity. Only after that expectation argument do bounded differences replace the unknown expected complexity by its empirical version.
The inequality is one-sided. It is not a guarantee that the right side is small for every sample: the empirical complexity itself can be large, and a probability- exceptional event remains. If is built after inspecting the same sample, this fixed-class theorem cannot be applied without an additional argument.
Finite classes and a norm-bounded infinite class
Lemma 2.5.4
(Finite classes have small complexity)
For a fixed finite class of size , every sample satisfies
Proof
(A moment generating function argument)
To see this for , let . For any , Jensen's inequality and for nonnegative give
Here , because and . Minimize at . For the signed sum has mean zero, so the same bound holds. It may exceed the trivial range bound and need not be tight.
A cardinality bound cannot be used directly for an infinite class. Yet take the domain and distribution to be supported on the ball , and consider , with and , and let . These functions lie in . On any sample,
The constant term has zero sign expectation; the supremum of over the Euclidean ball is . Jensen's inequality and cancellation of cross terms establish the middle bound. The class is infinite but its complexity is controlled by the norm constraints. Dimension can still matter indirectly through how , and the data scale.
Worked example 2.5.5
(A finite class, and when the bound is vacuous)
Let and , and suppose the empirical mean of the selected function is . For the finite-class bound gives , and the confidence term is . The theorem's right side is therefore at most , which exceeds the trivial value : at this sample size it says nothing. For the same quantities are and , so the right side is at most . In the degenerate case the bound reads , in agreement with the fact that a single function has zero Rademacher complexity.
Worked example 2.5.6
(The norm-bounded linear class at two sample sizes)
Take , , so and the functions lie in . The complexity bound is , which is for and for . With the complexity contribution to the theorem is at most and respectively, against confidence terms of and . At the confidence term, not the complexity of this infinite class, dominates. The class has infinitely many functions, yet its contribution is smaller than the finite eight-function bound above.
Counterexample mode
A sample-dependent class can invalidate the theorem
Let the domain have equally likely points and label each point implicitly by the value of a function. After observing , choose the singleton class containing that is zero on observed points and one elsewhere. Its empirical complexity is zero, since there is only one function, and , but . For and , the theorem’s displayed right side would be about , so applying it here would fail on every sample. The function class was chosen using the sample, so the fixed-class theorem does not apply to it. The missing complexity lies in the adaptive choice among many possible functions.
Common mistake
(Putting the supremum outside the expectation over signs)
For each fixed the signed sum has mean zero, so for every class. The complexity is , in which the supremum may adapt to the signs. For the two constants with the correct value is , not . Exchanging the two operations would make every class appear to have no capacity to fit noise.
Common mistake
(Using the complexity of the predictors instead of the loss class)
The theorem controls , the class of loss functions with values in . For labels and the zero-one loss, . The term contributes zero mean, and is again a uniform sign, so the complexity of the loss class is exactly half that of the predictor class on the same inputs. Substituting the complexity of directly doubles the complexity term; the correct class must be named.
Practice with solutions
Quick check
(For the class containing only the constant function , compute empirical Rademacher complexity for any .)
How many functions does the supremum range over?
Solution · Answer
It is zero: the signed sum has mean zero.
Quick check
(For and , state the finite-class upper bound.)
Substitute into .
Solution · Answer
.
Quick check
(If , and , bound the complexity of the displayed linear class.)
Use .
Solution · Answer
At most .
Quick check
(Why does the theorem permit a data-selected but not an unaccounted data-selected class?)
Which object is fixed before the sample is drawn?
Solution · Answer
One simultaneous event covers every member of a class fixed before sampling; changing the class itself after seeing the sample is outside that event's quantifiers.