Why count patterns rather than parameters?
A parameter grid controls an infinite family by comparing nearby parameters. That strategy needs a metric and a uniform Lipschitz condition. Sometimes two very different parameter values make the same predictions on all observed points. Conversely, a class with an innocent-looking description can fit every observed label. We need a way to measure the functions on a sample, rather than count their names.
Random signs provide a test. Give each observation an independent fair sign and ask how well a function in the class can align its values with those signs. A rich class can follow much of this artificial noise; a restricted class cannot. The calculation is made on the loss functions themselves. A bound for a prediction class does not automatically become one for its losses without another argument.
Setup and the random-sign measure
Let be independent identically distributed observations with law , where . Let be a nonempty countable class of measurable functions taking values in . Write
Definition 10.3.1
(Empirical and expected Rademacher complexity)
Let be independent fair signs, independent of the sample. The empirical Rademacher complexity is the conditional expectation
The supremum chooses after seeing the signs; otherwise the expectation of each fixed signed sum is zero. Countability ensures that the suprema used below are measurable. The quantity is nonnegative even when the zero function is absent: its supremum dominates the signed sum for any one fixed , whose expectation is zero.
Theorem 10.3.2
(A one-sided uniform generalization bound)
For , with probability at least over the sample,
Consequently, on this same event, every measurable data-dependent choice satisfies plus the right-hand side. The complexity here is an expectation over samples, not the observed empirical complexity alone.
Proof: a ghost sample and concentration
Proof
(Symmetrization, then bounded differences)
Introduce an independent ghost sample with the same law. For each fixed original sample, . Moving expectation outside a supremum can only increase the expression, so
Each pair is exchangeable, independently of the other pairs. Therefore independently swapping the two members according to fair signs preserves their joint law. Inserting signs and then using the inequality yields
The two suprema may use different functions; this is the source of an inequality, not an equality. The final equality uses the symmetry of the signs.
Set . Replacing one observation changes every by at most , and hence changes by at most . The bounded-differences inequality gives . For completeness, its proof exposes the assumptions: reveal observations one at a time in the Doob martingale for ; conditional on the past, each martingale increment has mean zero and lies in an interval of length at most . Hoeffding's lemma bounds its conditional exponential moment by . Multiplication and Markov's inequality give ; optimizing at gives the stated tail. Choosing and using the ghost-sample estimate proves the theorem.
Proof X-ray
Three moves, each removing one obstacle
The ghost sample replaces the unknown by the empirical average of an independent copy. The only inequality in this step is moving an expectation outside a supremum.
Signs can then be inserted without changing anything, because each pair is exchangeable and the pairs are independent; this is where the i.i.d. assumption is used. Splitting the supremum produces two Rademacher complexities, and the factor two comes from this split, which loses because the two suprema may choose different functions.
Concentration of around its mean uses only the range , through differences of size ; this is where boundedness enters. Countability is used only to make the suprema measurable. The bound is stated with the expected complexity because symmetrization controls , not itself.
This is a one-sided bound. Applying it also to and taking a union bound gives a two-sided discrepancy bound with in the square root. The complexities agree because the extra signed constant has expectation zero and sign reversal preserves the signs' law. A uniform two-sided event further gives an approximate empirical minimizer the comparison if ; compare with an arbitrary before taking its infimum.
Turning sample patterns into a bound
Lemma 10.3.3
(Pattern-count bound)
Suppose that, on a fixed sample, the set of value vectors has at most distinct elements. Then
Proof
(An exponential moment over finitely many patterns)
To see this, enumerate the distinct vectors as . For any , Jensen's inequality, the exponential maximum bound, and imply
Optimize in and divide by when . If , the expected signed sum is exactly zero. A deterministic bound on for every sample also bounds after averaging. This simple estimate can exceed one and need not be tight; it is useful when is small compared with .
Proof X-ray
Why only the number of patterns matters
The class enters only through its value vectors, so the supremum becomes a maximum over finitely many sums; that is what allows the soft-maximum bound . Jensen's inequality then moves the sign expectation inside the logarithm. Independence of the signs factors each exponential moment into , and the range bounds it by . The choice balances the two terms. Using instead of gives the sharper .
Worked example 10.3.4
(Threshold losses have few sample patterns)
Let be real-valued and take for rational . This countable class has infinitely many functions, yet sorting any observations shows at most distinct value vectors: moving the threshold only adds observations in sorted order. Ties may reduce this number. Hence
with probability at least . At and the right side is approximately . It is a distribution-free sufficient guarantee, not the observed error or a sharp threshold-process inequality.
Worked example 10.3.5
(Two functions on two points, computed exactly)
Let and let have value vectors and on the sample. Then and , so the signed supremum is . Over the four equally likely sign pairs it equals , with average . Dividing by gives . The pattern-count bound with gives , more than three times larger. The bound is valid, but for small an exact average over sign vectors can be far sharper.
Worked example 10.3.6
(Edge case: a single observation)
For the threshold class and , every observation admits both patterns and , by placing a rational below or above it. With the supremum is ; with it is , attained by the pattern . Hence for every sample and . The theorem then bounds by , which exceeds for every . Since the gap can never exceed for -valued losses, the bound is true but vacuous; the pattern estimate is vacuous too. Useful guarantees need small compared with .
A class that memorizes
Bounded values and countability do not by themselves make the complexity small.
Counterexample mode
A countable bounded class whose gap does not shrink
Claim: for a countable class of -valued functions, the uniform gap tends to zero as grows. Let be uniform on and let consist of indicators of finite unions of open intervals with rational endpoints. It is countable. For any finite sample and every , cover the sample points by finitely many such intervals whose total length is less than . The corresponding function has and , so . In fact it realizes every binary labeling of any sample with distinct points, by choosing sufficiently small intervals around the points labeled one. Thus a bounded loss and even countability alone do not ensure a useful uniform bound: the complexity of this class does not vanish. The fixed-class assumption also matters; choosing a family using the same sample requires separate analysis.
Common mistakes
Common mistake
(Choosing the function before the signs)
If the supremum is replaced by one fixed , the expectation of is zero and the complexity of every class would vanish. The definition lets depend on the sign vector; that is precisely how it measures the ability to fit noise.
Common mistake
(Using the observed complexity in place of the expected one)
The theorem is stated with . Replacing it by the value computed on the observed sample needs a further concentration argument for and changes the constants; that step is not proved here. A deterministic pattern count valid for every sample avoids the issue, as in the threshold example.
Common mistake
(Transferring a prediction-class bound to the loss class)
The calculation is made on the loss functions themselves. A complexity bound for a class of predictors does not automatically become one for the composed losses; that transfer needs its own argument about how the loss depends on the prediction.
Exercises
Quick check
(For the class consisting of the single function , compute its empirical Rademacher complexity. Why is it not one?)
Solution · Answer
It is . The supremum has only one candidate, and the fair signs cancel in expectation. The loss value one is not itself a signed correlation.
Quick check
(A binary-valued class produces at most 16 distinct patterns on every sample of size . Give a numerical upper bound on its expected Rademacher complexity using the pattern estimate.)
Solution · Answer
The estimate is . Since the estimate holds for every sample, taking the expectation preserves it.
Quick check
(For the threshold class above, suppose an empirical threshold is chosen after observing the sample. Explain why the simultaneous theorem applies to this choice and identify a condition that still needs checking.)
Solution · Answer
The event controls every rational threshold at once, so it controls a threshold selected using the data. The selection must be measurable and lie in the fixed countable family; an arbitrary data-dependent enlargement of that family is not justified by the same theorem.
Quick check
(For the interval-union memorization class, calculate the empirical complexity on a sample of distinct points. Explain why it does not approach zero.)
Solution · Answer
For each sign vector the class realizes the indicator of precisely the positive-sign points. Its maximum signed sum is therefore the number of positive signs. The empirical complexity is for every distinct-point sample, independent of . The countable interval family is rich enough to memorize the random signs.