Rademacher complexity measures the ability of a real-valued class to correlate with pure noise on the observed sample. It is a data-dependent and geometry-sensitive alternative to pure counting.
Empirical complexity
The empirical complexity is computed on the realized design points and then averaged over random signs.
Definition. For functions \(\mathcal G\) on \(\mathcal Z\), the empirical Rademacher complexity is \[ \widehat{\mathfrak R}_n(\mathcal G) =\mathbb E_\varepsilon\sup_{g\in\mathcal G}\frac1n\sum_{i=1}^n\varepsilon_i g(Z_i), \] where \(\varepsilon_i\) are independent signs with \(P(\varepsilon_i=1)=P(\varepsilon_i=-1)=1/2\).
Remark. If a class can fit random signs well, it can also fit noise in the sample. This is why \(\widehat{\mathfrak R}_n\) appears naturally in generalization bounds.
Symmetrization
Symmetrization is the main bridge from unknown expectations to observable random fluctuations.
Theorem. For any class \(\mathcal G\) with integrable envelope, \[ \mathbb E\sup_{g\in\mathcal G}|(P_n-P)g| \le 2\,\mathbb E\widehat{\mathfrak R}_n(\mathcal G). \]
Proof. Let \(Z_1',\ldots,Z_n'\) be an independent ghost sample. Jensen's inequality gives \[ \mathbb E\sup_g(P-P_n)g \le \mathbb E\sup_g(P_n'-P_n)g. \] Conditioning on both samples, the distribution of \(\sum_i(g(Z_i')-g(Z_i))\) is unchanged after multiplying each paired difference by an independent sign. The supremum of the signed difference is bounded by the sum of two signed empirical suprema, giving the factor \(2\). Apply the same argument to the negative class for absolute values.
Contraction
Lipschitz transformations of a class do not increase Rademacher complexity beyond the Lipschitz factor.
Theorem. If \(\phi_i:\mathbb R\to\mathbb R\) are \(L\)-Lipschitz and \(\phi_i(0)=0\), then \[ \mathbb E_\varepsilon\sup_{g\in\mathcal G}\frac1n\sum_i\varepsilon_i\phi_i(g(Z_i)) \le L\,\mathbb E_\varepsilon\sup_{g\in\mathcal G}\frac1n\sum_i\varepsilon_i g(Z_i). \]
Proof. This is the Ledoux-Talagrand contraction inequality. The proof replaces coordinates one at a time and uses the fact that, conditional on the other signs, the two-point oscillation of \(\phi_i\circ g\) is at most \(L\) times the oscillation of \(g\). Iterating over coordinates gives the result.
Linear classes
For linear prediction, complexity is controlled by the dual norm of the design.
Proposition. Let \(\mathcal G=\{z\mapsto\langle w,z\rangle:\|w\|\le B\}\) for a norm with dual \(\|\cdot\|_*\). Then \[ \widehat{\mathfrak R}_n(\mathcal G) =\frac{B}{n}\mathbb E_\varepsilon\left\|\sum_{i=1}^n\varepsilon_iZ_i\right\|_*. \]
Proof. By duality, \[ \sup_{\|w\|\le B}\left\langle w,\sum_i\varepsilon_iZ_i\right\rangle =B\left\|\sum_i\varepsilon_iZ_i\right\|_*. \] Divide by \(n\) and take the conditional expectation over the signs.
A data-dependent generalization theorem
Theorem. Suppose \(0\le g\le1\) for every \(g\in\mathcal G\). With probability at least \(1-\delta\), simultaneously for all \(g\in\mathcal G\), \[ Pg\le P_ng+2\widehat{\mathfrak R}_n(\mathcal G) +3\sqrt{\frac{\log(2/\delta)}{2n}}. \]
Proof. Define \(\Phi(Z_1,\ldots,Z_n)=\sup_g(Pg-P_ng)\). Replacing one observation changes \(\Phi\) by at most \(1/n\), so bounded differences gives \[ \Phi\le\mathbb E\Phi+\sqrt{\frac{\log(2/\delta)}{2n}}. \] Symmetrization bounds \(\mathbb E\Phi\) by \(2\mathbb E\widehat{\mathfrak R}_n(\mathcal G)\). The empirical complexity itself changes by at most \(1/n\) under one replacement, so a second bounded-differences argument gives \[ \mathbb E\widehat{\mathfrak R}_n(\mathcal G) \le\widehat{\mathfrak R}_n(\mathcal G) \sqrt{\frac{\log(2/\delta)}{2n}}. \] Combine the events by a union bound and absorb constants.
Massart's finite-class lemma
Lemma. Let \(A\subset\mathbb R^n\) be finite and \(r=\max_{a\in A}\|a\|_2\). Then \[ \mathbb E_\varepsilon\max_{a\in A}\langle\varepsilon,a\rangle \le r\sqrt{2\log|A|}. \]
Proof. For every \(\lambda>0\), \[ e^{\lambda\mathbb E\max_a\langle\varepsilon,a\rangle} \le \mathbb E e^{\lambda\max_a\langle\varepsilon,a\rangle} \le\sum_{a\in A}\mathbb Ee^{\lambda\langle\varepsilon,a\rangle} \le |A|e^{\lambda^2r^2/2}. \] Taking logarithms gives \(\mathbb E\max_a\langle\varepsilon,a\rangle \le\log|A|/\lambda+\lambda r^2/2\). Optimize at \(\lambda=\sqrt{2\log|A|}/r\).
Corollary. If \(|g(Z_i)|\le B\) for every \(g\in\mathcal G\), and the sample realizes only \(M\) distinct evaluation vectors \((g(Z_1),\ldots,g(Z_n))\), then \[ \widehat{\mathfrak R}_n(\mathcal G) \le B\sqrt{\frac{2\log M}{n}}. \]
Euclidean and sparse linear prediction
Example. If \(\|w\|_2\le B\) and \(\|Z_i\|_2\le R\), then \[ \widehat{\mathfrak R}_n \le\frac{B}{n}\left(\sum_{i=1}^n\|Z_i\|_2^2\right)^{1/2} \le\frac{BR}{\sqrt n}. \] If instead \(\|w\|_1\le B\) and \(\|Z_i\|_\infty\le R\), then \[ \widehat{\mathfrak R}_n \lesssim BR\sqrt{\frac{\log(2p)}{n}}. \] Thus an \(\ell^1\) constraint replaces ambient dimension \(p\) by \(\log p\).
Proof. In the Euclidean case, Jensen and sign orthogonality give \[ \mathbb E_\varepsilon\Big\|\sum_i\varepsilon_iZ_i\Big\|_2 \le\left(\sum_i\|Z_i\|_2^2\right)^{1/2}. \] For the \(\ell^1\) class, the dual norm is \(\ell^\infty\). Apply the sub-Gaussian maximal inequality to the \(2p\) signed coordinate sums.
Loss contraction and risk bounds
Corollary. Suppose \(u\mapsto\ell(u,y)\) is \(L\)-Lipschitz for every \(y\), and let \(\ell\circ\mathcal F=\{(x,y)\mapsto\ell(f(x),y):f\in\mathcal F\}\). Then \[ \widehat{\mathfrak R}_n(\ell\circ\mathcal F) \le L\widehat{\mathfrak R}_n(\mathcal F), \] after subtracting the irrelevant constants \(\ell(0,Y_i)\). Consequently an ERM over a bounded loss class has excess risk of order \(\mathfrak R_n(\mathcal F)+\sqrt{\log(1/\delta)/n}\).
Proof. Constants disappear after multiplication by centered Rademacher signs in expectation. Apply the contraction inequality to each coordinate map \(u\mapsto\ell(u,Y_i)-\ell(0,Y_i)\), then combine with the data-dependent generalization theorem and the basic ERM inequality.
Local Rademacher complexity
Definition. For an excess-loss class \(\mathcal G\) and \(r>0\), define \[ \mathfrak R_n(r)= \mathbb E\sup_{\substack{g\in\mathcal G\\Pg^2\le r}} \frac1n\sum_{i=1}^n\varepsilon_i g(Z_i). \] A sub-root function \(\psi\) is nonnegative, nondecreasing, and has \(\psi(r)/\sqrt r\) nonincreasing. It has a unique positive fixed point \(r_*\) satisfying \(\psi(r_*)=r_*\).
Theorem. Assume \(0\le g\le1\), \(Pg^2\le B\,Pg\), and \(\mathfrak R_n(r)\le\psi(r)\) for a sub-root \(\psi\). Then an ERM satisfies \[ Pg_{\widehat f}\lesssim r_*+ \frac{B\log(1/\delta)}{n} \] with probability at least \(1-\delta\).
Proof outline. The Bernstein condition converts an excess-risk radius into an \(L^2(P)\) radius. On dyadic shells, symmetrization and concentration bound empirical fluctuations by \(\psi(B\,2^jr_*)\), which is at most a constant fraction of \(2^jr_*\) by the sub-root property. Peeling and a union bound show that no function with excess risk substantially above the fixed point can beat \(f^*\) empirically.
Gaussian complexity
Replacing Rademacher signs by iid standard Gaussians defines Gaussian complexity. Comparison inequalities show that the two complexities agree up to universal constants for symmetric classes. Gaussian processes are often algebraically easier, while signs give sharper bounded-difference arguments and direct data-dependent estimates.
Metric entropy provides a multiscale upper bound for these complexities; that relation is developed on the covering numbers and entropy page.