Rademacher Complexity

Let $\mathcal{F}$ be a class of functions $f: \mathcal{Z} \to [0, 1]$ and let $S = (z_1, \ldots, z_n)$ be drawn i.i.d. from $\mathcal{D}$. Then for any $\delta > 0$, with probability at least $1 - \delta$ over the draw of $S$, simultaneously for all $f \in \mathcal{F}$:

$\mathbb{E}[f(z)] \leq \frac{1}{n}\sum_{i=1}^n f(z_i) + 2\mathfrak{R}_n(\mathcal{F}) + \sqrt{\frac{\log(1/\delta)}{2n}}$

The two-sided version: with probability at least $1 - \delta$,

$\sup_{f \in \mathcal{F}} \left|\mathbb{E}[f(z)] - \frac{1}{n}\sum_{i=1}^n f(z_i)\right| \leq 2\mathfrak{R}_n(\mathcal{F}) + \sqrt{\frac{\log(2/\delta)}{2n}}$

The same bounds hold with $\mathfrak{R}_n(\mathcal{F})$ replaced by $\hat{\mathfrak{R}}_S(\mathcal{F})$ (at the cost of a slightly modified confidence term).

The generalization gap is controlled by two terms: (1) the Rademacher complexity, which measures how well $\mathcal{F}$ can fit random noise. This is the "capacity" term, and (2) a confidence term $\sqrt{\log(1/\delta)/2n}$ from concentration. The factor of 2 in front of $\mathfrak{R}_n$ comes from the symmetrization technique (going from one-sample to two-sample and back).

If the Rademacher complexity is small, the class cannot overfit, so the empirical average is close to the population expectation for all $f$ simultaneously. which is exactly uniform convergence.

This bound is the main reason Rademacher complexity is central to learning theory. It provides a uniform convergence guarantee with a complexity term that is:

• Data-dependent (through $\hat{\mathfrak{R}}_S$): tighter on easy data
• Computable (in principle): you can estimate it by sampling Rademacher vectors
• Applicable to infinite classes: no need for finiteness or VC dimension

For the specific case of learning with a loss class $\mathcal{F} = \{\ell \circ h : h \in \mathcal{H}\}$, this gives $R(h) \leq \hat{R}_n(h) + 2\mathfrak{R}_n(\ell \circ \mathcal{H}) + \sqrt{\log(1/\delta)/2n}$ for all $h$ simultaneously.

The bound requires functions in $[0, 1]$ (or bounded range). For unbounded losses, you need truncation arguments or sub-Gaussian assumptions. Also, the factor of 2 from symmetrization is not always tight. in some cases, local Rademacher complexity or peeling arguments can improve it.

For any class $\mathcal{F}$ of functions $f: \mathcal{Z} \to [0, 1]$:

$\mathbb{E}_S\!\left[\sup_{f \in \mathcal{F}} \left(\mathbb{E}[f] - \frac{1}{n}\sum_{i=1}^n f(z_i)\right)\right] \leq 2\mathfrak{R}_n(\mathcal{F})$

The symmetrization lemma says: the expected uniform convergence gap is at most twice the Rademacher complexity. The factor of 2 arises because going from population to empirical involves introducing a ghost sample (one factor) and then replacing the ghost with Rademacher signs (which can only increase the supremum by symmetry arguments). This lemma is the core engine of the Rademacher approach.

Symmetrization is the technique that connects the generalization gap (a quantity involving the unknown distribution $\mathcal{D}$) to Rademacher complexity (a quantity that can be estimated from data). It is the same symmetrization technique used in the VC dimension proof, but here it is applied directly to the function class rather than going through the growth function.

The factor of 2 can be suboptimal. For one-sided bounds (only the upper tail of the generalization gap), local Rademacher complexity techniques can sometimes remove the factor of 2 at the cost of more complex analysis.

Let $\phi: \mathbb{R} \to \mathbb{R}$ be $L$-Lipschitz (i.e., $|\phi(a) - \phi(b)| \leq L|a - b|$) with $\phi(0) = 0$. For any class $\mathcal{F}$ of real-valued functions:

$\hat{\mathfrak{R}}_S(\phi \circ \mathcal{F}) \leq L \cdot \hat{\mathfrak{R}}_S(\mathcal{F})$

where $\phi \circ \mathcal{F} = \{\phi \circ f : f \in \mathcal{F}\}$.

Applying an $L$-Lipschitz function to the outputs of your hypothesis class scales the Rademacher complexity by at most $L$. The lemma is a contraction in the technical sense (the Lipschitz constant cannot create new correlation structure), but the absolute complexity can grow when $L > 1$ — for instance, $\phi(a) = 2a$ doubles every output. The "shrinkage" picture is only accurate for $L \le 1$. The general statement is the linear bound $L \cdot \hat{\mathfrak{R}}_S(\mathcal{F})$.

The contraction lemma lets you bound the Rademacher complexity of the loss class $\ell \circ \mathcal{H}$ in terms of the Rademacher complexity of the hypothesis class $\mathcal{H}$. If the loss $\ell$ is $L$-Lipschitz, then:

$\mathfrak{R}_n(\ell \circ \mathcal{H}) \leq L \cdot \mathfrak{R}_n(\mathcal{H})$

The Lipschitz constant depends on the prediction/label range. For the ramp loss, $L = 1$. For squared loss $\phi(t) = (t-y)^2$ with derivative $\phi'(t) = 2(t-y)$, the Lipschitz constant is $L = 2 \cdot \max|t-y|$, which gives:

• $L = 2$ when $t, y \in [0, 1]$ (so $|t - y| \leq 1$), the convention used throughout this page.
• $L = 4B$ when $t, y \in [-B, B]$ (so $|t - y| \leq 2B$), the convention used in the worked exercise below.

Pick the convention deliberately and state it. A single $L = 2$ written without the bounded range is a recurring source of off-by-2 errors in generalization bounds.

This is practical: you compute the Rademacher complexity of $\mathcal{H}$ (which is often easier) and multiply by the Lipschitz constant of the loss.

The contraction lemma requires $\phi(0) = 0$. If the loss does not satisfy this (e.g., constant offset), you can center it first. Also, the Lipschitz constant $L$ can be conservative: if $\phi$ is Lipschitz with constant $L$ globally but much smoother in the range actually used, the bound is loose.

For a finite sample $S = (z_1,\ldots,z_n)$, a finite nonempty class $\mathcal{F}$ of scalar-valued functions, and a map $\phi : \mathbb{R}\to\mathbb{R}$ satisfying $|\phi(s)-\phi(t)| \le L|s-t|$ with positive $L$:

$\hat{\mathfrak{R}}_S(\phi\circ\mathcal{F}) \le L\cdot \hat{\mathfrak{R}}_S(\mathcal{F}).$

The Lean statement is the finite-sample, finite-class empirical Rademacher wrapper around a coordinate-by-coordinate contraction proof.

The proof contracts one sample coordinate at a time. At each coordinate, the one-step comparison lemma shows that replacing $f_i(z_k)$ by $\phi(f_i(z_k))$ cannot increase the sign-average supremum by more than the Lipschitz factor. Iterating over all coordinates gives the finite-sample bound.

This is deliberately scoped: finite sample, finite nonempty hypothesis class, scalar outputs, empirical Rademacher complexity, and a positive Lipschitz constant. It is not the full general Talagrand contraction principle for infinite classes or stochastic processes.

For a finite hypothesis index set, finite sample $z$, loss family $\ell_i$, and a 1-Lipschitz map $\phi:\mathbb{R}\to\mathbb{R}$:

$\hat{\mathfrak{R}}_n(\phi \circ \ell, z) \leq \hat{\mathfrak{R}}_n(\ell, z).$

The Lean theorem is TheoremPath.LearningTheory.RademacherContraction.contraction_empirical.

This is the finite-sample, unit-Lipschitz version of the contraction principle. It says that applying a non-expansive scalar transformation to each loss value cannot increase the empirical Rademacher complexity on that sample.

This Lean wrapper proves the 1-Lipschitz empirical statement. Scaled $L$-Lipschitz formulations and infinite-index variants are tracked as separate Rademacher extension targets.

For a finite nonempty hypothesis class with losses bounded by $B$ and an iid sample $S \sim \mu^n$:

$\mu^n\!\left\{S \mid \mathrm{genGap}(S) \geq 2\mathbb{E}_S[\hat{\mathfrak{R}}_n(\ell, S)] + \varepsilon\right\} \leq \exp\!\left(-\frac{\varepsilon^2 n}{8B^2}\right)$

where $\mathrm{genGap}(S) = \sup_i [R_\mu(\ell_i) - \hat{R}_n(\ell_i, S)]$. Combines expected Rademacher symmetrization with the Azuma-style genGap tail bound.

The expected Rademacher complexity controls the average generalization gap; the Azuma concentration step turns this into a high-probability bound with an additive slack $\varepsilon$. The Azuma constant ($8B^2$ in the exponent) is a factor of 4 looser than the sharp McDiarmid form ($2B^2$).

For a finite hypothesis class with losses bounded by $B$ and a sample of size $n$, the empirical Rademacher complexity is bounded by the number of distinct loss patterns (effective class) on the sample:

$\hat{\mathfrak{R}}_n(\ell, z) \leq B \sqrt{\frac{2 \log K}{n}}$

where $K = |\mathrm{effectiveClass}(\ell, z)|$ is the number of distinct loss vectors $(\ell_i(z_1), \ldots, \ell_i(z_n))$ as $i$ ranges over the hypothesis class.

The empirical Rademacher complexity depends on the hypothesis class only through the distinct loss patterns it produces on the sample. Redundant hypotheses that agree on every sample point contribute nothing. This is the bridge between combinatorial growth functions (Sauer-Shelah, VC dimension) and Rademacher complexity.

For a hypothesis class whose effective class cardinality on every sample of size $n$ is bounded by $\sum_{k=0}^{d} \binom{n}{k}$ (the Sauer-Shelah growth function with parameter $d$), the empirical Rademacher complexity satisfies:

$\hat{\mathfrak{R}}_n(\ell, z) \leq B \sqrt{\frac{2d \log(en/d)}{n}}$

The singleton effective-class case (all hypotheses agree on the sample) is handled by showing $\hat{\mathfrak{R}}_n = 0$.

Composing the Sauer-Shelah polynomial bound $(en/d)^d$ with the Massart effective-class bound replaces $\log |H|$ with $d \log(en/d)$. The parameter $d$ plays the role of the VC dimension. For generic real-valued losses, the user still supplies the effective-growth assumption. For binary classifiers with 0-1 loss, the binary VC bridge is now Lean-verified and derives the effective loss-pattern bound from the binary trace.

For a finite nonempty family of Euclidean weights with norm at most $R$ and a finite sample with positive $n$, let $\mathcal{G}$ be the corresponding indexed class of linear predictors.

$\hat{\mathfrak{R}}_S(\mathcal{G}) \le \frac{R}{n}\sqrt{\sum_{k=1}^n \|x_k\|^2}.$

The Lean file also proves the bounded-input corollary:

$\|x_k\|\le B \Rightarrow \hat{\mathfrak{R}}_S(\mathcal{G}) \le \frac{RB}{\sqrt{n}}.$

The Rademacher supremum over norm-bounded linear predictors reduces to the norm of the signed feature sum. Cauchy-Schwarz pulls out the weight radius $R$, and Jensen converts the expected norm into the square root of the sum of squared feature norms.

This is the finite-dimensional Euclidean, finite-index version. It does not claim an arbitrary Hilbert-space theorem, an infinite weight ball as an unindexed hypothesis class, or a neural-network generalization bound.