Rademacher Complexity

Definition

With i.i.d. fair signs ${\sigma }_1,\dots ,{\sigma }_n\in \{\pm 1\}$:

$${\mathrm{Rad}}_n(\mathcal{F}):=E\underset{f\in \mathcal{F}}{\sup }\frac{1}{n}\sum _{i=1}^n{\sigma }_{i}f(X_i)$$

with the expectation over the points $X_i$ and the signs ${\sigma }_i$.

Formula

With probability at least $1-\delta$, for all $f\in \mathcal{F}$:

$$R(f)\le R_n(f)+2{\mathrm{Rad}}_n(\mathcal{F})+\sqrt{\frac{\log (1/\delta )}{2n}}$$

Unlike the shattering coefficient, it takes the data distribution into account; such bounds tend to be sharper and are often easier to compute. A single function has ${\mathrm{Rad}}_n=0$; the class of all functions has ${\mathrm{Rad}}_n=1$ (it fits every labeling).

Appears in

• Lecture 3, definition and Theorem 17
• Lecture 3, summary

Related concepts

• Generalization Bound
• VC Dimension