Rademacher complexity

For independent and identically distributed random variables $Z_1,\dots ,Z_n$ and independent Rademacher signs ${\epsilon }_1,\dots ,{\epsilon }_n$, the Rademacher complexity of a function class $\mathcal{F}$ isIt measures how strongly the class can correlate with independent random signs on a random sample.

For a fixed sample $z_{1:n}$, the empirical Rademacher complexity isTaking its expected value over the sample gives ${\mathcal{R}}_n(\mathcal{F})$.

For an i.i.d. sample and an integrable function class $\mathcal{F}$,Introduce an independent ghost sample, replace each expectation by its ghost-sample average using Jensen inequality, and then multiply each paired difference by an independent Rademacher sign. Splitting the resulting supremum into its two sample contributions gives the factor two.

For a zero-one-valued loss class $\mathcal{F}$, the excess misclassification risk of an empirical risk minimizer $\hat{h}$ over a population minimizer $h^{\ast }$ satisfieswith probability at least $1-\delta$. The proof combines Rademacher symmetrization with the Bounded differences inequality for the supremum of the empirical excess-loss process.

The observable version isIt follows by another application of the Bounded differences inequality to the Empirical Rademacher complexity.

For a finite $A\subseteq {\mathbb{R}}^n$ with ${\max }_{a\in A}\Vert a{\Vert }_2\le R$, its empirical Rademacher complexity is at most $R\sqrt{2\log |A|}/n$.

For $|D_i|\le M$ and a binary class $H$ of VC dimension at most $p$, the vectors $(D_{i}h(X_i){)}_{i=1}^n$ have norm at most $M\sqrt{n}$ and at most $(n+1{)}^p$ distinct values. The Massart finite-class lemma gives

A linear functional has the same supremum over a class and its convex hull. Thus taking convex combinations does not increase empirical Rademacher complexity.

Composition with an $L$-Lipschitz scalar map increases Rademacher complexity by at most the factor $L$ after centering at zero.

Independent signs cancel cross terms in $\mathbb{E}\Vert {\sum }_i{\sigma }_i{A}_i{\Vert }_F^2$, leaving ${\sum }_i\Vert A_i{\Vert }_F^2$.

For $h_M(x)=x^{T}Mx$, $M⪰0$, $\mathrm{tr}M\le s$, and $\Vert x\Vert \le C$, the complexity is at most $C^{2}s/\sqrt{n}$.

With the $1/n$ Rademacher convention, an empirical risk minimizer has expected excess risk at most twice the Rademacher complexity of its loss class.