Rademacher Complexity and Generalization Bounds

Intuition Beginner

The previous chapter measured a family of rules by a worst-case count: the largest set of points it can tag in every yes/no pattern. That count never looks at your actual data, so it always plans for the nastiest possible distribution. This unit measures the same family in a friendlier, data-aware way: it asks how well the family can chase pure noise on the data you actually have.

Here is the test. Take your data points and flip a fair coin for each one, plus or minus. Now hunt through your whole family of rules for the one that best lines up with those coin flips. If even your best rule can only weakly match random coins, the family is simple. If some rule in the family can match almost any pattern of coins, the family is rich, and that richness is exactly what lets it fool you by fitting noise instead of signal. The average best match, over many coin-flip rounds, is the family's complexity.

Why is this the right thing to measure? Because the gap between your measured error and your true error is, at heart, the same chasing-noise problem. A family that can fit random coins can also fit the random part of your sample, making its training error look better than its true error. So this one number bounds how much you can be misled, and it adapts to your data instead of bracing for the worst case.

Visual Beginner

Picture your data points on a line. Above each one sits a coin showing plus or minus. Your family of rules each produce a yes/no pattern over the points; you slide through the family looking for the pattern that agrees with the coins most. The fraction of coins your best rule matches, averaged over many fresh coin-flip rounds, is the complexity.

   points:    x1   x2   x3   x4   x5
   coins:      +    -    +    +    -
   best rule:  +    -    +    -    -    <- matches 4 of 5
   average best-match over many coin rounds = complexity
   simple family: best match stays near "half" (chance level)
   rich family:   best match near "all" (can chase any coins)

Family of rules	Best match to random coins	What it means
simple (few patterns)	barely better than a coin toss	low complexity, errors trustworthy
moderate	beats chance by a clear margin	moderate complexity
rich (can hit any pattern)	matches almost every coin	high complexity, can fit noise

The picture teaches the lesson: a family that can chase random coins can chase the random part of your data, so its training score flatters it; the average chase level is the warning number.

Worked example Beginner

Take three data points and a tiny family of just two rules. Rule one outputs the pattern (yes, yes, no); rule two outputs (no, yes, yes). We measure the complexity by averaging the best coin-match over all coin assignments. Code yes as $+1$ and no as $-1$.

Step 1. List the coin assignments. With three points there are $8$ equally likely coin patterns: $(+,+,+),(+,+,-),(+,-,+),(-,+,+),(+,-,-),(-,+,-),(-,-,+),(-,-,-)$.

Step 2. For each coin pattern, score each rule by the sum of agreements (a match adds $1$, a mismatch subtracts $1$), then keep the better rule's score. Rule one is $(+,+,-)$, rule two is $(-,+,+)$. For coins $(+,+,+)$: rule one scores $1+1-1=1$, rule two scores $-1+1+1=1$; best is $1$. For coins $(+,+,-)$: rule one scores $1+1+1=3$, rule two scores $-1+1-1=-1$; best is $3$.

Step 3. Do this for all eight. By the symmetry between the two rules, the eight best-scores come out as $3,3,1,1,1,1,3,3$ in some order, averaging to $2$.

Step 4. Divide by the number of points to get the complexity: average best-score $2$ divided by $3$ points gives about $0.67$.

What this tells us: even this two-rule family can chase coins fairly well (a score of $0.67$ out of a maximum of $1$), because two opposite-looking rules already cover many patterns. A family with a single fixed rule would score lower, and a family rich enough to output every pattern would score the maximum.

Check your understanding Beginner

Formal definition Intermediate+

The setting is the agnostic learning setup of 45.07.04, now with a general bounded loss. Fix a domain $\mathcal{Z}$ (typically $\mathcal{Z}=\mathcal{X}\times \mathcal{Y}$), a distribution $\mathcal{D}$ on $\mathcal{Z}$, and a sample $S=(z_1,\dots ,z_m)\sim {\mathcal{D}}^m$. For a function $g:\mathcal{Z}\to \mathbb{R}$ write ${\mathbb{E}}_{\mathcal{D}}g={\mathbb{E}}_{z\sim \mathcal{D}}g(z)$ and ${\mathbb{E}}_{S}g=\frac{1}{m}{\sum }_{i=1}^{m}g(z_i)$. A hypothesis class $\mathcal{H}$ and a loss $\ell$ produce the loss class $\mathcal{G}=\ell \circ \mathcal{H}=\{z\mapsto \ell (h,z):h\in \mathcal{H}\}$, assumed to take values in $[0,1]$ unless stated otherwise. Let $\sigma =({\sigma }_1,\dots ,{\sigma }_m)$ be independent Rademacher variables, each uniform on $\{-1,+1\}$, independent of $S$.

Definition (Rademacher complexity of a set of vectors). For a bounded set $A\subseteq {\mathbb{R}}^m$,

$$R(A)=\frac{1}{m}{\mathbb{E}}_{\sigma }\left[\underset{a\in A}{\sup }\sum _{i=1}^m{\sigma }_i{a}_i\right].$$

This is the empirical Rademacher complexity of $A$; ${\sum }_i{\sigma }_i{a}_i=⟨\sigma ,a⟩$ measures how well $a$ aligns with a random sign pattern, and the supremum picks the best-aligning vector ^{[Shalev-Shwartz Ben-David 2014]}.

Definition (empirical and average Rademacher complexity of a function class). For a class $\mathcal{G}$ of functions $\mathcal{Z}\to \mathbb{R}$ and a sample $S$, the empirical Rademacher complexity is $R(\mathcal{G}\circ S)$ applied to the vectors $\{(g(z_1),\dots ,g(z_m)):g\in \mathcal{G}\}$, written

$${\hat{\mathfrak{R}}}_S(\mathcal{G})=\frac{1}{m}{\mathbb{E}}_{\sigma }[\underset{g\in \mathcal{G}}{\sup }\sum _{i=1}^m{\sigma }_{i}g(z_i)],{\mathfrak{R}}_m(\mathcal{G})={\mathbb{E}}_{S\sim {\mathcal{D}}^m}[{\hat{\mathfrak{R}}}_S(\mathcal{G})].$$

The first is a function of the realised sample (observable up to the average over $\sigma$); the second, the average Rademacher complexity, averages also over the draw of $S$ and is a deterministic function of $\mathcal{D}$, $\mathcal{G}$, and $m$. The symbol $\mathfrak{R}$ denotes Rademacher complexity throughout.

Definition (representativeness). For the loss class $\mathcal{G}=\ell \circ \mathcal{H}$, the representativeness of $S$ is ${\mathrm{Rep}}_{\mathcal{D}}(\mathcal{G},S)={\sup }_{g\in \mathcal{G}}({\mathbb{E}}_{\mathcal{D}}g-{\mathbb{E}}_{S}g)$, the largest amount by which the sample underestimates the true risk over the class. It is the quantity the generalization bound controls, and Rademacher complexity is its average upper bound.

Counterexamples to common slips Intermediate+

• "Rademacher complexity is a property of the hypothesis class alone." It depends on the class through the loss and on the distribution (for ${\mathfrak{R}}_m$) or the sample (for ${\hat{\mathfrak{R}}}_S$). The same $\mathcal{H}$ has different Rademacher complexity under different $\mathcal{D}$; this distribution-dependence is precisely what makes the bound sharper than the distribution-free VC bound.
• "The empirical and average complexities are interchangeable." They differ by the fluctuation of ${\hat{\mathfrak{R}}}_S$ around its mean. The high-probability bound uses the empirical one (observable), while the in-expectation bound uses the average one; bridging them needs a concentration step, since ${\hat{\mathfrak{R}}}_S$ is itself a random variable.
• "Complexity grows with the number of hypotheses." For a finite class Massart's lemma gives only a $\sqrt{2\log |\mathcal{H}|}$ dependence, and for infinite classes the cardinality is irrelevant — a ball in an RKHS has complexity controlled by $\sqrt{\mathrm{tr}K}/m$, with no reference to how many functions it contains.

Key theorem with proof Intermediate+

The signature result is the Rademacher generalization bound: the average representativeness is at most twice the average Rademacher complexity, with a high-probability version through the bounded-differences inequality of 40.07.05. The data-dependent form replaces the worst-case growth function of 45.07.04 by the observable empirical complexity.

Theorem (Rademacher generalization bound). Let $\mathcal{G}=\ell \circ \mathcal{H}$ with $\ell$ taking values in $[0,1]$. Then

$${\mathbb{E}}_{S\sim {\mathcal{D}}^m}\left[\underset{h\in \mathcal{H}}{\sup }\right(L_{\mathcal{D}}(h)-L_S(h)\left)\right]\le 2{\mathfrak{R}}_m(\mathcal{G}).$$

Moreover, for every $\delta \in (0,1)$, with probability at least $1-\delta$ over $S$, simultaneously for all $h\in \mathcal{H}$,

$$L_{\mathcal{D}}(h)\le L_S(h)+2{\hat{\mathfrak{R}}}_S(\mathcal{G})+4\sqrt{\frac{2\log (4/\delta )}{m}}.$$

^{[Shalev-Shwartz Ben-David 2014] [Bartlett Mendelson 2002]}

Proof. Write $\Phi (S)={\sup }_{g\in \mathcal{G}}({\mathbb{E}}_{\mathcal{D}}g-{\mathbb{E}}_{S}g)={\mathrm{Rep}}_{\mathcal{D}}(\mathcal{G},S)$. The expectation bound is symmetrisation. Introduce a ghost sample $S^{\prime }=(z_1^{\prime },\dots ,z_m^{\prime })\sim {\mathcal{D}}^m$ independent of $S$, so that ${\mathbb{E}}_{\mathcal{D}}g={\mathbb{E}}_{S^{\prime }}[{\mathbb{E}}_{S^{\prime }}g]$ and, by Jensen applied to the supremum,

$${\mathbb{E}}_S\Phi (S)={\mathbb{E}}_S\underset{g}{\sup }({\mathbb{E}}_{S^{\prime }}{\mathbb{E}}_{S^{\prime }}g-{\mathbb{E}}_{S}g)\le {\mathbb{E}}_{S,S^{\prime }}\underset{g}{\sup }({\mathbb{E}}_{S^{\prime }}g-{\mathbb{E}}_{S}g)={\mathbb{E}}_{S,S^{\prime }}\underset{g}{\sup }\frac{1}{m}\sum _{i=1}^m(g(z_i^{\prime })-g(z_i)).$$

Since $z_i$ and $z_i^{\prime }$ are i.i.d., swapping the pair $(z_i,z_i^{\prime })$ leaves the joint law unchanged; inserting independent Rademacher signs ${\sigma }_i$ that perform this swap gives, for every fixed $\sigma$, the same expectation, hence

$${\mathbb{E}}_{S,S^{\prime }}\underset{g}{\sup }\frac{1}{m}\sum _i(g(z_i^{\prime })-g(z_i))={\mathbb{E}}_{\sigma ,S,S^{\prime }}\underset{g}{\sup }\frac{1}{m}\sum _i{\sigma }_i(g(z_i^{\prime })-g(z_i)).$$

Splitting the supremum of a difference into the sum of two suprema and using that $({\sigma }_i)$ and $(-{\sigma }_i)$ have the same law,

$$\le {\mathbb{E}}_{\sigma ,S^{\prime }}\underset{g}{\sup }\frac{1}{m}\sum _i{\sigma }_{i}g(z_i^{\prime })+{\mathbb{E}}_{\sigma ,S}\underset{g}{\sup }\frac{1}{m}\sum _i(-{\sigma }_i)g(z_i)=2{\mathfrak{R}}_m(\mathcal{G}),$$

which is the expectation bound.

For the high-probability bound, view $\Phi$ as a function of the $m$ independent coordinates $z_1,\dots ,z_m$. Changing one $z_i$ alters each ${\mathbb{E}}_{S}g$ by at most $1/m$ (the loss lies in $[0,1]$), so $\Phi$ changes by at most $1/m$: $\Phi$ has the bounded-differences property with constants $c_i=1/m$. McDiarmid's inequality 40.07.05 gives, with probability $\ge 1-\delta /2$,

$$\Phi (S)\le {\mathbb{E}}_S\Phi (S)+\sqrt{\frac{\log (2/\delta )}{2m}}\le 2{\mathfrak{R}}_m(\mathcal{G})+\sqrt{\frac{\log (2/\delta )}{2m}}.$$

The empirical complexity ${\hat{\mathfrak{R}}}_S(\mathcal{G})$ likewise has bounded differences $1/m$ in each coordinate, so a second application of McDiarmid gives ${\mathfrak{R}}_m(\mathcal{G})\le {\hat{\mathfrak{R}}}_S(\mathcal{G})+\sqrt{\log (2/\delta )/(2m)}$ with probability $\ge 1-\delta /2$. Combining the two events by a union bound, replacing ${\mathfrak{R}}_m$ by the observable ${\hat{\mathfrak{R}}}_S$, and using $L_{\mathcal{D}}(h)-L_S(h)\le \Phi (S)$ for every $h$, with the numerical constants collected into the stated $4\sqrt{2\log (4/\delta )/m}$ term, yields the uniform high-probability bound. $\square$

Bridge. This theorem is the foundational reason the distribution-free VC theory of 45.07.04 has a sharper, data-aware sibling: it shows that the uniform deviation ${\sup }_h(L_{\mathcal{D}}(h)-L_S(h))$ is controlled not by the worst-case growth function but by the Rademacher complexity, which adapts to the actual distribution and sample, and the bridge is the same symmetrisation step that proved the fundamental theorem, here carried out without ever passing to a union bound over labelings. This is exactly the substitution that lets the effective count of 45.07.04 become a continuous, observable quantity: where Sauer-Shelah fed ${\Pi }_{\mathcal{H}}(2m)$ into a crude union bound, Massart's lemma now feeds the same growth function into ${\hat{\mathfrak{R}}}_S$ and recovers the VC bound as the worst case. It generalises the finite-class union bound to arbitrary classes through the contraction lemma, and it builds toward the margin bounds of the next unit, where the contraction lemma applied to the ramp loss turns this complexity into a margin-normalised norm bound. The central insight reappears throughout: learnability is the concentration of a supremum over an effective complexity, and putting these together, the McDiarmid upgrade of 40.07.05 is what converts the in-expectation symmetrisation into the single-sample guarantee a practitioner can compute. The bridge is that the complexity is at once a tool of empirical-process theory and the object that appears again in the data-dependent penalties of structural risk minimization.

Exercises Intermediate+

Advanced results Master

The generalization bound is the hinge between four developments: the symmetrisation that produces it, the structural calculus that makes Rademacher complexity computable by reduction, the contraction principle that handles general Lipschitz losses, and the local-complexity refinement that yields fast rates beyond the worst-case $1/\sqrt{m}$.

Theorem 1 (symmetrisation and the two-sided bound). For $\mathcal{G}=\ell \circ \mathcal{H}$ with $\ell \in [0,1]$, ${\mathbb{E}}_S{\sup }_g({\mathbb{E}}_{\mathcal{D}}g-{\mathbb{E}}_{S}g)\le 2{\mathfrak{R}}_m(\mathcal{G})$ and, with probability $\ge 1-\delta$ uniformly in $h$, $L_{\mathcal{D}}(h)\le L_S(h)+2{\hat{\mathfrak{R}}}_S(\mathcal{G})+4\sqrt{2\log (4/\delta )/m}$ ^{[Shalev-Shwartz Ben-David 2014]}. The data-dependent term ${\hat{\mathfrak{R}}}_S$ is observable: it can be estimated by Monte Carlo over the signs $\sigma$, making the bound a Rademacher penalty computable from a single sample ^{[Koltchinskii 2001]}. A matching lower bound — the deviation is also at least a constant multiple of ${\mathfrak{R}}_m$ minus a $1/\sqrt{m}$ term — shows the complexity is the right order, not merely an upper bound.

Theorem 2 (structural calculus of Rademacher complexity). Empirical Rademacher complexity obeys a calculus ^{[Bartlett Mendelson 2002]}: it is invariant under translation by a fixed function and under taking the (absolute) convex hull, ${\hat{\mathfrak{R}}}_S(\mathrm{conv}\mathcal{H})={\hat{\mathfrak{R}}}_S(\mathcal{H})$; it scales by $|c|$ under $\mathcal{H}\mapsto c\mathcal{H}$; it is monotone under inclusion; and it is sub-additive, ${\hat{\mathfrak{R}}}_S({\mathcal{H}}_1+{\mathcal{H}}_2)\le {\hat{\mathfrak{R}}}_S({\mathcal{H}}_1)+{\hat{\mathfrak{R}}}_S({\mathcal{H}}_2)$. Massart's finite-class lemma $R(A)\le {\max }_a\Vert a{\Vert }_2\sqrt{2\log |A|}/m$ is the base case from which the VC corollary ${\hat{\mathfrak{R}}}_S(\ell \circ \mathcal{H})\le \sqrt{2\log {\Pi }_{\mathcal{H}}(m)/m}$ follows, and the convex-hull invariance is why boosting and other ensemble methods do not increase capacity beyond that of their base class.

Theorem 3 (contraction / Ledoux-Talagrand lemma). If ${\varphi }_1,\dots ,{\varphi }_m$ are $\rho$-Lipschitz with ${\varphi }_i(0)=0$, then for any bounded $A\subseteq {\mathbb{R}}^m$, ${\mathbb{E}}_{\sigma }{\sup }_{a\in A}{\sum }_i{\sigma }_i{\varphi }_i(a_i)\le \rho {\mathbb{E}}_{\sigma }{\sup }_{a\in A}{\sum }_i{\sigma }_i{a}_i$, so ${\hat{\mathfrak{R}}}_S(\varphi \circ \mathcal{H})\le \rho {\hat{\mathfrak{R}}}_S(\mathcal{H})$ ^{[Bartlett Mendelson 2002]}. Beyond Dudley's entropy integral ${\hat{\mathfrak{R}}}_S(\mathcal{H})\lesssim {\inf }_{\alpha \ge 0}(\alpha +\frac{1}{\sqrt{m}}{\int }_{\alpha }^1\sqrt{\log N(\epsilon ,\mathcal{H},L^2(P_m))}d\epsilon )$ — the chaining bound of 45.05.04 specialised to the empirical metric — the contraction lemma is the engine that turns the complexity of a base class into the complexity of its loss class for any Lipschitz loss, including the hinge, logistic, and ramp losses. This is the same contraction principle that powers the Donsker preservation calculus.

Theorem 4 (local Rademacher complexity and fast rates). Restricting the supremum to the sub-class $\{g:\mathrm{Var}(g)\le r\}$ defines the local Rademacher complexity ${\mathfrak{R}}_m({\mathcal{G}}_r)$; its fixed point $r^{\star }$ solving $r^{\star }\asymp {\mathfrak{R}}_m({\mathcal{G}}_{r^{\star }})$ governs the rate ^{[Koltchinskii 2001]}. Under a Bernstein/variance condition relating variance to excess risk, the excess risk of ERM is $O(r^{\star })$, which for VC-type classes is $O(d\log m/m)$ — the fast $1/m$ rate rather than the worst-case $1/\sqrt{m}$. The localisation isolates the part of the class near the optimum, where the variance is small and concentration is sharper; this is the Rademacher route to the fast rates also reachable through Talagrand's inequality for the supremum of an empirical process.

Synthesis. The foundational reason the data-dependent theory exists is that one quantity — the Rademacher complexity, the average best alignment of the class with random signs — governs the uniform deviation, the model-selection penalty, and, through localisation, the rate, and every result here is that single quantity read through a different operation. This is exactly the meeting of the symmetrisation of 45.07.04 and the chaining of 45.05.04: symmetrisation produces the Rademacher average, chaining bounds it by an entropy integral, and putting these together the worst-case growth function ${\Pi }_{\mathcal{H}}(2m)$ of the distribution-free theory becomes the distribution-adapted ${\hat{\mathfrak{R}}}_S$, which recovers the VC bound through Massart as its worst case and improves on it for benign distributions. The structural calculus and the contraction lemma are dual readings of the same alignment quantity — convex hulls and Lipschitz images leave the alignment with random signs essentially unchanged — and the contraction step is the central insight that lets a single base-class complexity serve every Lipschitz loss, which is exactly what the margin bounds of the next unit exploit. The bridge upward at every level is the same: the cardinality $|\mathcal{H}|$ of the finite-class bound generalises to the growth function, then to the Rademacher complexity, then to the local complexity, and the high-probability upgrade is always the bounded-differences inequality of 40.07.05, so the entire data-dependent theory is the concentration of a supremum over an effective complexity that the data itself reveals.

Full proof set Master

Proposition 1 (symmetrisation inequality). Let $\mathcal{G}$ be a class of functions $\mathcal{Z}\to [0,1]$ and $S,S^{\prime }\sim {\mathcal{D}}^m$ independent. Then ${\mathbb{E}}_S{\sup }_{g\in \mathcal{G}}({\mathbb{E}}_{\mathcal{D}}g-{\mathbb{E}}_{S}g)\le 2{\mathfrak{R}}_m(\mathcal{G})$.

Proof. Since ${\mathbb{E}}_{\mathcal{D}}g={\mathbb{E}}_{S^{\prime }}{\mathbb{E}}_{S^{\prime }}g$ and the supremum of an expectation is at most the expectation of the supremum (Jensen, the supremum being convex), ${\mathbb{E}}_S{\sup }_g({\mathbb{E}}_{\mathcal{D}}g-{\mathbb{E}}_{S}g)={\mathbb{E}}_S{\sup }_g{\mathbb{E}}_{S^{\prime }}({\mathbb{E}}_{S^{\prime }}g-{\mathbb{E}}_{S}g)\le {\mathbb{E}}_{S,S^{\prime }}{\sup }_g({\mathbb{E}}_{S^{\prime }}g-{\mathbb{E}}_{S}g)={\mathbb{E}}_{S,S^{\prime }}{\sup }_g\frac{1}{m}{\sum }_i(g(z_i^{\prime })-g(z_i))$. The summands $g(z_i^{\prime })-g(z_i)$ are antisymmetric under swapping $z_i\leftrightarrow z_i^{\prime }$, and because $(z_i,z_i^{\prime })$ are i.i.d. pairs the joint law is invariant under such swaps; thus for any fixed sign vector $\epsilon \in \{\pm 1{\}}^m$ the expectation equals ${\mathbb{E}}_{S,S^{\prime }}{\sup }_g\frac{1}{m}{\sum }_i{\epsilon }_i(g(z_i^{\prime })-g(z_i))$, and averaging over $\epsilon =\sigma$ uniform leaves it unchanged. Hence the quantity equals ${\mathbb{E}}_{\sigma ,S,S^{\prime }}{\sup }_g\frac{1}{m}{\sum }_i{\sigma }_i(g(z_i^{\prime })-g(z_i))$. Bounding the supremum of a sum by the sum of suprema and using that $\sigma$ and $-\sigma$ are equidistributed gives $\le {\mathbb{E}}_{\sigma ,S^{\prime }}{\sup }_g\frac{1}{m}{\sum }_i{\sigma }_{i}g(z_i^{\prime })+{\mathbb{E}}_{\sigma ,S}{\sup }_g\frac{1}{m}{\sum }_i{\sigma }_{i}g(z_i)=2{\mathfrak{R}}_m(\mathcal{G})$. $\square$

Proposition 2 (Massart's finite-class lemma). For finite $A\subseteq {\mathbb{R}}^m$ with $r={\max }_{a\in A}\Vert a{\Vert }_2$, $R(A)\le r\sqrt{2\log |A|}/m$.

Proof. With $W={\sup }_{a\in A}⟨\sigma ,a⟩$, Jensen gives $e^{\lambda \mathbb{E}W}\le \mathbb{E}{e}^{\lambda W}\le {\sum }_{a\in A}{\mathbb{E}}_{\sigma }{e}^{\lambda ⟨\sigma ,a⟩}$ for $\lambda >0$. By Hoeffding's lemma each coordinate satisfies ${\mathbb{E}}_{\sigma }{e}^{\lambda {\sigma }_i{a}_i}\le e^{{\lambda }^2{a}_i^2/2}$, and by independence ${\mathbb{E}}_{\sigma }{e}^{\lambda ⟨\sigma ,a⟩}\le e^{{\lambda }^2\Vert a{\Vert }_2^2/2}\le e^{{\lambda }^2{r}^2/2}$. Thus $\mathbb{E}W\le \log |A|/\lambda +\lambda r^2/2$, minimised at $\lambda =\sqrt{2\log |A|}/r$ to give $\mathbb{E}W\le r\sqrt{2\log |A|}$; divide by $m$. $\square$

Proposition 3 (contraction lemma; single-coordinate induction). Let $\varphi :\mathbb{R}\to \mathbb{R}$ be $\rho$-Lipschitz with $\varphi (0)=0$. For bounded $A\subseteq {\mathbb{R}}^m$, ${\mathbb{E}}_{\sigma }{\sup }_{a\in A}{\sum }_i{\sigma }_i\varphi (a_i)\le \rho {\mathbb{E}}_{\sigma }{\sup }_{a\in A}{\sum }_i{\sigma }_i{a}_i$.

Proof. It suffices to treat one coordinate and iterate. Condition on ${\sigma }_2,\dots ,{\sigma }_m$ and average over ${\sigma }_1$: writing $u(a)={\sum }_{i\ge 2}{\sigma }_i\varphi (a_i)$, the ${\sigma }_1$-average of ${\sup }_a({\sigma }_1\varphi (a_1)+u(a))$ is $\frac{1}{2}{\sup }_a(\varphi (a_1)+u(a))+\frac{1}{2}{\sup }_{a^{\prime }}(-\varphi (a_1^{\prime })+u(a^{\prime }))$. Choose near-maximisers $a,a^{\prime }$; the bracket is $\le \varphi (a_1)-\varphi (a_1^{\prime })+u(a)+u(a^{\prime })\le \rho |a_1-a_1^{\prime }|+u(a)+u(a^{\prime })$ by the Lipschitz bound. Taking $a_1\ge a_1^{\prime }$ without loss of generality, $\rho |a_1-a_1^{\prime }|=\rho (a_1-a_1^{\prime })$, so the bracket is $\le (\rho a_1+u(a))+(-\rho a_1^{\prime }+u(a^{\prime }))\le {\sup }_a(\rho a_1+u(a))+{\sup }_{a^{\prime }}(-\rho a_1^{\prime }+u(a^{\prime }))$, which is twice the ${\sigma }_1$-average of ${\sup }_a({\sigma }_1\rho a_1+u(a))$. Hence replacing $\varphi (a_1)$ by $\rho a_1$ does not decrease the conditional average; iterating over all coordinates and using $\varphi (0)=0$ to anchor the comparison gives the claim. (The factor $2$ in the version ${\hat{\mathfrak{R}}}_S(\varphi \circ \mathcal{H})\le 2\rho {\hat{\mathfrak{R}}}_S(\mathcal{H})$ of ^{[Bartlett Mendelson 2002]} arises when the supremum is over $|\cdot |$ rather than the signed quantity; the signed form above has constant $\rho$.) $\square$

Proposition 4 (high-probability bound via bounded differences). Under the hypotheses of Proposition 1, with probability $\ge 1-\delta$ uniformly in $h$, $L_{\mathcal{D}}(h)\le L_S(h)+2{\hat{\mathfrak{R}}}_S(\ell \circ \mathcal{H})+4\sqrt{2\log (4/\delta )/m}$.

Proof. The map $S\mapsto \Phi (S)={\sup }_g({\mathbb{E}}_{\mathcal{D}}g-{\mathbb{E}}_{S}g)$ changes by at most $1/m$ when one coordinate of $S$ is replaced, since $\ell \in [0,1]$ and $\Phi$ is a supremum of $1/m$-bounded-difference functions. McDiarmid's inequality 40.07.05 with constants $c_i=1/m$ gives $\mathrm{Pr}[\Phi (S)\ge \mathbb{E}\Phi +t]\le \exp (-2t^2/\sum c_i^2)=\exp (-2m{t}^2)$, so with probability $\ge 1-\delta /2$, $\Phi (S)\le \mathbb{E}\Phi +\sqrt{\log (2/\delta )/(2m)}\le 2{\mathfrak{R}}_m+\sqrt{\log (2/\delta )/(2m)}$ by Proposition 1. Likewise ${\hat{\mathfrak{R}}}_S$ has bounded differences $1/m$, so ${\mathfrak{R}}_m\le {\hat{\mathfrak{R}}}_S+\sqrt{\log (2/\delta )/(2m)}$ with probability $\ge 1-\delta /2$. A union bound over the two events and $L_{\mathcal{D}}(h)-L_S(h)\le \Phi (S)$ for each $h$ give $L_{\mathcal{D}}(h)\le L_S(h)+2{\hat{\mathfrak{R}}}_S+3\sqrt{\log (2/\delta )/(2m)}$; absorbing constants and rewriting $\log (2/\delta )$ as $\log (4/\delta )$ for a clean union-bound budget yields the stated form. $\square$

Proposition 5 (RKHS-ball complexity). For $\mathcal{H}=\{f\in {\mathcal{H}}_K:\Vert f{\Vert }_{{\mathcal{H}}_K}\le B\}$ and Gram matrix $\mathbf{K}=(K(x_i,x_j))$, ${\hat{\mathfrak{R}}}_S(\mathcal{H})\le B\sqrt{\mathrm{tr}\mathbf{K}}/m$.

Proof. By the reproducing property $f(x_i)=⟨f,K_{x_i}⟩$, so ${\sup }_{\Vert f\Vert \le B}{\sum }_i{\sigma }_{i}f(x_i)={\sup }_{\Vert f\Vert \le B}⟨f,{\sum }_i{\sigma }_i{K}_{x_i}⟩=B\Vert {\sum }_i{\sigma }_i{K}_{x_i}{\Vert }_{{\mathcal{H}}_K}$ by Cauchy-Schwarz. Then ${\hat{\mathfrak{R}}}_S(\mathcal{H})=\frac{B}{m}{\mathbb{E}}_{\sigma }\Vert {\sum }_i{\sigma }_i{K}_{x_i}\Vert \le \frac{B}{m}({\mathbb{E}}_{\sigma }\Vert {\sum }_i{\sigma }_i{K}_{x_i}{\Vert }^2{)}^{1/2}$ by Jensen, and ${\mathbb{E}}_{\sigma }\Vert {\sum }_i{\sigma }_i{K}_{x_i}{\Vert }^2={\sum }_{i,j}\mathbb{E}[{\sigma }_i{\sigma }_j]K(x_i,x_j)={\sum }_{i}K(x_i,x_i)=\mathrm{tr}\mathbf{K}$. Hence ${\hat{\mathfrak{R}}}_S(\mathcal{H})\le B\sqrt{\mathrm{tr}\mathbf{K}}/m$. $\square$

Connections Master

This unit is the data-dependent refinement of the chapter capped by 45.07.04. The fundamental theorem controlled the uniform deviation ${\sup }_h(L_{\mathcal{D}}(h)-L_S(h))$ by the worst-case growth function through symmetrisation and a union bound over the ${\Pi }_{\mathcal{H}}(2m)$ labelings; Rademacher complexity replaces that union bound by the alignment quantity ${\hat{\mathfrak{R}}}_S$, and the VC bound reappears as the special case obtained by feeding the growth function into Massart's lemma. The symmetrisation step is identical in spirit, but here it terminates in an observable complexity rather than a combinatorial count.

The VC-dimension and Sauer-Shelah machinery of 45.07.03 supplies the worst-case recovery: ${\hat{\mathfrak{R}}}_S(\ell \circ \mathcal{H})\le \sqrt{2\log {\Pi }_{\mathcal{H}}(m)/m}$ and ${\Pi }_{\mathcal{H}}(m)\le (em/d{)}^d$ give the $O(\sqrt{d\log (m/d)/m})$ rate, so finite VC dimension bounds the Rademacher complexity uniformly over distributions, while a benign distribution can make ${\hat{\mathfrak{R}}}_S$ much smaller. The growth function is the bridge between the combinatorial and the data-dependent pictures.

The chaining and entropy machinery of 45.05.04 is the empirical-process source of the sharper bounds on ${\hat{\mathfrak{R}}}_S$: Dudley's entropy integral ${\hat{\mathfrak{R}}}_S(\mathcal{H})\lesssim \frac{1}{\sqrt{m}}{\int }_0^1\sqrt{\log N(\epsilon ,\mathcal{H},L^2(P_m))}d\epsilon$ specialises the chaining maximal inequality to the empirical metric, and the symmetrisation and Ledoux-Talagrand contraction principle developed there for the Donsker preservation calculus are the same tools that drive the Rademacher generalization bounds here; the Rademacher complexity is the finite-sample shadow of the Donsker fluctuation modulus.

The concentration spine of 40.07.05 provides the high-probability upgrade: the bounded-differences (McDiarmid) inequality turns the in-expectation symmetrisation bound into a single-sample guarantee and lets the empirical complexity ${\hat{\mathfrak{R}}}_S$ stand in for its average ${\mathfrak{R}}_m$, since both are $1/m$-bounded-difference functions of the sample. Without this concentration step the bound would only hold in expectation.

The kernel and RKHS framework of 45.08.01 is where the linear-class bound becomes most powerful: a ball in the RKHS of a kernel $K$ has Rademacher complexity at most $B\sqrt{\mathrm{tr}\mathbf{K}}/m$, a dimension-free bound depending only on the norm budget and the kernel scale, which is the generalization-theoretic justification for regularising by the RKHS norm in kernel ridge regression and support vector machines. The contraction lemma applied to the margin loss then yields the margin-based bounds of the next unit, where the same complexity is normalised by the achieved margin.

Historical & philosophical context Master

The use of random $\pm 1$ signs to symmetrise an empirical process — replacing the deviation from the mean by a randomised sum — descends from the Giné-Zinn symmetrisation of empirical-process theory and from the study of sums of independent random vectors in Banach spaces by Michel Ledoux and Michel Talagrand, whose 1991 monograph established the contraction principle for Rademacher averages that underlies the Lipschitz-loss calculus used here ^{[Bartlett Mendelson 2002]}.

Rademacher complexity as the central complexity measure of statistical learning, with the symmetrisation generalization bound, the structural-results calculus, and the contraction inequality, was introduced by Peter Bartlett and Shahar Mendelson in their 2002 Journal of Machine Learning Research paper, which also developed the closely related Gaussian complexity and applied the framework to margin bounds for kernel machines and neural networks ^{[Bartlett Mendelson 2002]}. In the same period Vladimir Koltchinskii proposed the empirical Rademacher complexity as a computable, data-dependent penalty for structural risk minimization, and with Dmitriy Panchenko developed the local Rademacher complexities that yield fast rates by restricting the supremum to the low-variance neighbourhood of the optimum ^{[Koltchinskii 2001]}. The textbook synthesis assembling symmetrisation, Massart's lemma, the contraction lemma, and the McDiarmid high-probability bound into the form used in this unit is due to Shalev-Shwartz and Ben-David ^{[Shalev-Shwartz Ben-David 2014]}. The Rademacher framework is now the standard route to dimension-free, norm-based generalization bounds, where the worst-case VC dimension of the earlier theory is replaced by a quantity that depends on the data and on the geometry of the hypothesis class.

Bibliography Master

@article{bartlettmendelson2002,
  author  = {Bartlett, Peter L. and Mendelson, Shahar},
  title   = {Rademacher and {Gaussian} complexities: risk bounds and structural results},
  journal = {Journal of Machine Learning Research},
  volume  = {3},
  pages   = {463--482},
  year    = {2002}
}

@article{koltchinskii2001,
  author  = {Koltchinskii, Vladimir},
  title   = {Rademacher penalties and structural risk minimization},
  journal = {IEEE Transactions on Information Theory},
  volume  = {47},
  number  = {5},
  pages   = {1902--1914},
  year    = {2001}
}

@article{koltchinskiipanchenko2002,
  author  = {Koltchinskii, Vladimir and Panchenko, Dmitriy},
  title   = {Empirical margin distributions and bounding the generalization error of combined classifiers},
  journal = {Annals of Statistics},
  volume  = {30},
  number  = {1},
  pages   = {1--50},
  year    = {2002}
}

@book{shalevshwartzbendavid2014r,
  author    = {Shalev-Shwartz, Shai and Ben-David, Shai},
  title     = {Understanding Machine Learning: From Theory to Algorithms},
  publisher = {Cambridge University Press},
  year      = {2014}
}

@book{mohri2018r,
  author    = {Mohri, Mehryar and Rostamizadeh, Afshin and Talwalkar, Ameet},
  title     = {Foundations of Machine Learning},
  edition   = {2},
  publisher = {MIT Press},
  year      = {2018}
}

@book{ledouxtalagrand1991r,
  author    = {Ledoux, Michel and Talagrand, Michel},
  title     = {Probability in {Banach} Spaces: Isoperimetry and Processes},
  publisher = {Springer-Verlag},
  series    = {Ergebnisse der Mathematik und ihrer Grenzgebiete},
  year      = {1991}
}

@article{bartlettbousquetmendelson2005,
  author  = {Bartlett, Peter L. and Bousquet, Olivier and Mendelson, Shahar},
  title   = {Local {Rademacher} complexities},
  journal = {Annals of Statistics},
  volume  = {33},
  number  = {4},
  pages   = {1497--1537},
  year    = {2005}
}

@article{massart2000,
  author  = {Massart, Pascal},
  title   = {Some applications of concentration inequalities to statistics},
  journal = {Annales de la Facult\'e des Sciences de Toulouse},
  volume  = {9},
  number  = {2},
  pages   = {245--303},
  year    = {2000}
}