Rademacher complexity

Given a set ${\displaystyle A\subseteq \mathbb {R} ^{m}}$, the Rademacher complexity of A is defined as follows:[1][2]^:326

${\displaystyle \operatorname {Rad} (A):={\frac {1}{m}}\operatorname {E} \left[\sup _{a\in A}\sum _{i=1}^{m}\sigma _{i}a_{i}\right]}$

where ${\displaystyle \sigma _{1},\sigma _{2},\dots ,\sigma _{m}}$ are independent random variables drawn from the Rademacher distribution i.e. ${\displaystyle \Pr(\sigma _{i}=+1)=\Pr(\sigma _{i}=-1)=1/2}$ for ${\displaystyle i=1,2,\dots ,m}$, and ${\displaystyle a=(a_{1},\ldots ,a_{m})}$. Some authors take the absolute value of the sum before taking the supremum, but if ${\displaystyle A}$ is symmetric this makes no difference.

Given a sample ${\displaystyle S=(z_{1},z_{2},\dots ,z_{m})\in Z^{m}}$, and a class ${\displaystyle F}$ of real-valued functions defined on a domain space ${\displaystyle Z}$, where ${\displaystyle f}$ is the loss function ${\displaystyle f(z)=\ell (h(x),y)}$ of a classifier ${\displaystyle h}$, the empirical Rademacher complexity of ${\displaystyle F}$ given ${\displaystyle S}$ is defined as:

${\displaystyle \operatorname {Rad} _{S}(F)={\frac {1}{m}}\operatorname {E} \left[\sup _{f\in F}\sum _{i=1}^{m}\sigma _{i}f(z_{i})\right]}$

This can also be written using the previous definition:[2]^:326

${\displaystyle \operatorname {Rad} _{S}(F)=\operatorname {Rad} (F\circ S)}$

where ${\displaystyle F\circ S}$ denotes function composition, i.e.:

${\displaystyle F\circ S:=\{(f(z_{1}),\ldots ,f(z_{m}))\mid f\in F\}}$

Let ${\displaystyle P}$ be a probability distribution over ${\displaystyle Z}$. The Rademacher complexity of the function class ${\displaystyle F}$ with respect to ${\displaystyle P}$ for sample size ${\displaystyle m}$ is:

${\displaystyle \operatorname {Rad} _{P,m}(F):=\operatorname {E} _{S\sim P^{m}}\left[\operatorname {Rad} _{S}(F)\right]}$

where the above expectation is taken over an identically independently distributed (i.i.d.) sample ${\displaystyle S=(z_{1},z_{2},\dots ,z_{m})}$ generated according to ${\displaystyle P}$.

In machine learning, it is desired to have a training set that represents the true distribution of some sample data ${\displaystyle S}$. This can be quantified using the notion of representativeness. Denote by ${\displaystyle P}$ the probability distribution from which the samples are drawn. Denote by ${\displaystyle H}$ the set of hypotheses (potential classifiers) and denote by ${\displaystyle F}$ the corresponding set of error functions, i.e., for every hypothesis ${\displaystyle h\in H}$, there is a function ${\displaystyle f_{h}\in F}$, that maps each training sample (features,label) to the error of the classifier ${\displaystyle h}$ (note in this case hypothesis and classifier are used interchangeably). For example, in the case that ${\displaystyle h}$ represents a binary classifier, the error function is a 0–1 loss function, i.e. the error function ${\displaystyle f_{h}}$ returns 1 if ${\displaystyle h}$ correctly classifies a sample and 0 else. We omit the index and write ${\displaystyle f}$ instead of ${\displaystyle f_{h}}$ when the underlying hypothesis is irrelevant. Define:

${\displaystyle L_{P}(f):=\operatorname {E} _{z\sim P}[f(z)]}$ – the expected error of some error function ${\displaystyle f\in F}$ on the real distribution ${\displaystyle P}$;

${\displaystyle L_{S}(f):={1 \over m}\sum _{i=1}^{m}f(z_{i})}$ – the estimated error of some error function ${\displaystyle f\in F}$ on the sample ${\displaystyle S}$.

The representativeness of the sample ${\displaystyle S}$, with respect to ${\displaystyle P}$ and ${\displaystyle F}$, is defined as:

${\displaystyle \operatorname {Rep} _{P}(F,S):=\sup _{f\in F}(L_{P}(f)-L_{S}(f))}$

Smaller representativeness is better, since it provides a way to avoid overfitting: it means that the true error of a classifier is not much higher than its estimated error, and so selecting a classifier that has low estimated error will ensure that the true error is also low. Note however that the concept of representativeness is relative and hence can not be compared across distinct samples.

The expected representativeness of a sample can be bounded above by the Rademacher complexity of the function class:[2]^:326

$${\displaystyle \operatorname {E} _{S\sim P^{m}}[\operatorname {Rep} _{P}(F,S)]\leq 2\cdot \operatorname {E} _{S\sim P^{m}}[\operatorname {Rad} (F\circ S)]}$$

When the Rademacher complexity is small, it is possible to learn the hypothesis class H using empirical risk minimization.

For example, (with binary error function),[2]^:328 for every ${\displaystyle \delta >0}$, with probability at least ${\displaystyle 1-\delta }$, for every hypothesis ${\displaystyle h\in H}$:

${\displaystyle L_{P}(h)-L_{S}(h)\leq 2\operatorname {Rad} (F\circ S)+4{\sqrt {2\ln(4/\delta ) \over m}}}$

Let ${\displaystyle H}$ be a set family whose VC dimension is ${\displaystyle d}$. It is known that the growth function of ${\displaystyle H}$ is bounded as:

for all ${\displaystyle m>d+1}$: ${\displaystyle \operatorname {Growth} (H,m)\leq (em/d)^{d}}$

This means that, for every set ${\displaystyle h}$ with at most ${\displaystyle m}$ elements, ${\displaystyle |H\cap h|\leq (em/d)^{d}}$. The set-family ${\displaystyle H\cap h}$ can be considered as a set of binary vectors over ${\displaystyle \mathbb {R} ^{m}}$. Substituting this in Massart's lemma gives:

${\displaystyle \operatorname {Rad} (H\cap h)\leq {\sqrt {2d\log(em/d) \over m}}}$

With more advanced techniques (Dudley's entropy bound and Haussler's upper bound[4]) one can show, for example, that there exists a constant ${\displaystyle C}$, such that any class of ${\displaystyle \{0,1\}}$-indicator functions with Vapnik–Chervonenkis dimension ${\displaystyle d}$ has Rademacher complexity upper-bounded by ${\displaystyle C{\sqrt {\frac {d}{m}}}}$.

The following bounds are related to linear operations on ${\displaystyle S}$ – a constant set of ${\displaystyle m}$ vectors in ${\displaystyle \mathbb {R} ^{n}}$.[2]^:332–333

1. Define ${\displaystyle A_{2}=\{(w\cdot x_{1},\ldots ,w\cdot x_{m})\mid \|w\|_{2}\leq 1\}=}$ the set of dot-products of the vectors in ${\displaystyle S}$ with vectors in the unit ball. Then:

${\displaystyle \operatorname {Rad} (A_{2})\leq {\max _{i}\|x_{i}\|_{2} \over {\sqrt {m}}}}$

2. Define ${\displaystyle A_{1}=\{(w\cdot x_{1},\ldots ,w\cdot x_{m})\mid \|w\|_{1}\leq 1\}=}$ the set of dot-products of the vectors in ${\displaystyle S}$ with vectors in the unit ball of the 1-norm. Then:

${\displaystyle \operatorname {Rad} (A_{1})\leq \max _{i}\|x_{i}\|_{\infty }\cdot {\sqrt {2\log(2n) \over m}}}$

The following bound relates the Rademacher complexity of a set ${\displaystyle A}$ to its external covering number – the number of balls of a given radius ${\displaystyle r}$ whose union contains ${\displaystyle A}$. The bound is attributed to Dudley.[2]^:338

Suppose ${\displaystyle A\subset \mathbb {R} ^{m}}$ is a set of vectors whose length (norm) is at most ${\displaystyle c}$. Then, for every integer ${\displaystyle M>0}$:

${\displaystyle \operatorname {Rad} (A)\leq {c\cdot 2^{-M} \over {\sqrt {m}}}+{6c \over m}\cdot \sum _{i=1}^{M}2^{-i}{\sqrt {\log \left(N_{c\cdot 2^{-i}}^{\text{ext}}(A)\right)}}}$

In particular, if ${\displaystyle A}$ lies in a d-dimensional subspace of ${\displaystyle \mathbb {R} ^{m}}$, then:

${\displaystyle \forall r>0:N_{r}^{\text{ext}}(A)\leq (2c{\sqrt {d}}/r)^{d}}$

Substituting this in the previous bound gives the following bound on the Rademacher complexity:

${\displaystyle \operatorname {Rad} (A)\leq {6c \over m}\cdot {\bigg (}{\sqrt {d\log(2{\sqrt {d}})}}+2{\sqrt {d}}{\bigg )}=O{\bigg (}{c{\sqrt {d\log(d)}} \over m}{\bigg )}}$