View source for Rademacher complexity

{{Short description|Measure of complexity of real-valued functions}}
In [[computational learning theory]] ([[machine learning]] and [[theory of computation]]), '''Rademacher complexity''', named after [[Hans Rademacher]], measures richness of a class of sets with respect to a [[probability distribution]]. The concept can also be extended to real valued functions. 

== Definitions ==
=== Rademacher complexity of a set ===
Given a set <math>A\subseteq \mathbb{R}^m</math>, the '''Rademacher complexity of''' ''A'' is defined as follows:<ref name=b11>{{cite web|last1=Balcan|first1=Maria-Florina|authorlink= Maria-Florina Balcan |title=Machine Learning Theory – Rademacher Complexity|url=https://www.cs.cmu.edu/~ninamf/ML11/lect1117.pdf|accessdate=10 December 2016|date=November 15–17, 2011}}</ref><ref name=book14>Chapter 26 in {{Cite Shai Shai 2014}}</ref>{{rp|326}}
:<math>
\operatorname{Rad}(A)
:= 
\frac{1}{m}
   \mathbb{E}_\sigma \left[
   \sup_{a \in A}
      \sum_{i=1}^m \sigma_i a_i
\right]
</math>

where <math>\sigma_1, \sigma_2, \dots, \sigma_m</math> are independent random variables drawn from the [[Rademacher distribution]] i.e. <math>\Pr(\sigma_i = +1) = \Pr(\sigma_i = -1) = 1/2</math> for <math>i=1,2,\dots,m</math>, and <math> a=(a_1, \ldots, a_m)</math>. Some authors take the absolute value of the sum before taking the supremum, but if <math>A</math> is [[Symmetric set|symmetric]] this makes no difference.

=== Rademacher complexity of a function class ===
Let <math>S=\{z_1, z_2, \dots, z_m\} \subset Z</math> be a sample of points and consider a function class <math>\mathcal{F}</math> of real-valued functions over <math>Z</math>. Then, the '''empirical Rademacher complexity''' of <math>\mathcal{F}</math> given <math>S</math> is defined as:
:<math>
\operatorname{Rad}_S(\mathcal{F}) 
= 
\frac{1}{m}
   \mathbb{E}_\sigma \left[
   \sup_{f \in \mathcal{F}}
   \left|\sum_{i=1}^m \sigma_i f(z_i)  \right|
\right]
</math>

This can also be written using the previous definition:<ref name="book14" />{{rp|326}}
:<math>\operatorname{Rad}_S(\mathcal{F}) = \operatorname{Rad}(\mathcal{F} \circ S) </math>
where <math>\mathcal{F} \circ S</math> denotes [[function composition]], i.e.:
:<math>\mathcal{F} \circ S := \{ (f(z_1),\ldots,f(z_m))\mid  f\in \mathcal{F}\}</math>

The '''worst case empirical Rademacher complexity''' is<math display="block">
\overline{\operatorname{Rad}}_m(\mathcal{F}) 
= \sup_{S = \{z_1, \dots, z_m\}}\operatorname{Rad}_{S}(\mathcal{F})
</math>Let <math>P</math> be a probability distribution over <math>Z</math>. The '''Rademacher complexity''' of the function class <math>\mathcal{F}</math> with respect to <math>P</math> for sample size <math>m</math> is:

:<math>
\operatorname{Rad}_{P,m}(\mathcal{F}) 
:= 
\mathbb{E}_{S\sim P^m} \left[ \operatorname{Rad}_S(\mathcal{F}) \right]
</math>

where the above expectation is taken over an [[identically independently distributed]] (i.i.d.) sample <math>S=(z_1, z_2, \dots, z_m)</math> generated according to <math>P</math>.

== Intuition ==
The Rademacher complexity is typically applied on a function class of models that are used for classification, with the goal of measuring their ability to classify points drawn from a probability space under arbitrary labellings. When the function class is rich enough, it contains functions that can appropriately adapt for each arrangement of labels, simulated by the random draw of <math>\sigma_i</math> under the expectation, so that this quantity in the sum is maximised.

== Examples ==
1. <math>A</math> contains a single vector, e.g., <math>A = \{(a,b)\} \subset \mathbb{R}^2</math>. Then:
:: <math>\operatorname{Rad}(A) = {1\over 2}\cdot \left({1\over 4}\cdot(a+b) + {1\over 4}\cdot(a-b) + {1\over 4}\cdot(-a+b) + {1\over 4}\cdot(-a-b)\right) = 0</math>
The same is true for every singleton hypothesis class.<ref name=book12>{{Cite Mehryar Afshin Ameet 2012}}</ref>{{rp|56}}

2. <math>A</math> contains two vectors, e.g., <math>A = \{(1,1),(1,2)\} \subset \mathbb{R}^2</math>. Then:
:: <math>
\begin{align}
\operatorname{Rad}(A) & = {1\over 2}\cdot \left({1\over 4}\cdot\max(1+1, 1+2) + {1\over 4}\cdot\max(1-1, 1-2) + {1\over 4} \cdot \max(-1+1, -1+2) + {1\over 4}\cdot\max(-1-1, -1-2)\right) \\[5pt]
& = {1\over 8}(3+0+1-2) = {1\over 4}
\end{align}
</math>

== Using the Rademacher complexity ==
The Rademacher complexity can be used to derive data-dependent upper-bounds on the [[learnability]] of function classes. Intuitively, a function-class with smaller Rademacher complexity is easier to learn.

=== Bounding the representativeness ===
In [[machine learning]], it is desired to have a [[training set]] that represents the true distribution of some sample data <math>S</math>. This can be quantified using the notion of '''representativeness'''. Denote by <math>P</math> the [[probability distribution]] from which the samples are drawn. Denote by <math>H</math> the set of hypotheses (potential classifiers) and denote by <math>\mathcal F</math> the corresponding set of error functions, i.e., for every hypothesis <math>h\in H</math>, there is a function <math>f_h\in F</math>, that maps each training sample (features,label) to the error of the classifier <math>h</math> (note in this case hypothesis and classifier are used interchangeably). For example, in the case that <math>h</math> represents a binary classifier, the error function is a 0–1 loss function, i.e. the error function <math>f_h</math> returns 0 if <math>h</math> correctly classifies a sample and 1 else. We omit the index and write <math>f</math> instead of <math>f_h</math> when the underlying hypothesis is irrelevant. Define:
:<math>L_P(f) := \mathbb E_{z\sim P}[f(z)]</math> – the expected error of some error function <math>f\in \mathcal F</math> on the real distribution <math>P</math>;
:<math>L_S(f) := {1\over m} \sum_{i=1}^m f(z_i)</math> – the estimated error of some error function <math>f\in \mathcal F</math> on the sample <math>S</math>.
The representativeness of the sample <math>S</math>, with respect to <math>P</math> and <math>\mathcal F</math>, is defined as:
:<math>\operatorname{Rep}_P(\mathcal F,S) := \sup_{f\in F} (L_P(f) - L_S(f))</math>

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: If <math>\mathcal F</math> is a set of functions with range within <math>[0, 1]</math>, then<ref name=book14/>{{rp|326}}<ref name=":1">{{Cite journal |last=Bartlett |first=Peter L. |last2=Montanari |first2=Andrea |last3=Rakhlin |first3=Alexander |date=May 2021 |title=Deep learning: a statistical viewpoint |url=https://www.cambridge.org/core/journals/acta-numerica/article/deep-learning-a-statistical-viewpoint/7BCB89D860CEDDD5726088FAD64F2A5A |journal=Acta Numerica |language=en |volume=30 |pages=87–201 |doi=10.1017/S0962492921000027 |issn=0962-4929|arxiv=2103.09177 }}</ref>
:<math display="block"> \operatorname{Rad}_{P,m}(\mathcal{F}) - \sqrt{\frac{\ln 2}{2 m}} \leq \mathbb E_{S\sim P^m} [\operatorname{Rep}_P(\mathcal F,S)] \leq 2 \operatorname{Rad}_{P,m}(\mathcal{F}) </math>
Furthermore, the representativeness is [[Concentration inequality|concentrated]] around its expectation:<ref name=":1" /> For any <math> \epsilon</math>, with probability <math> \geq 1 - 2e^{-2\epsilon^2 m}</math>,<math display="block"> \operatorname{Rep}_P(\mathcal F,S) \in \mathbb E_{S\sim P^m} [\operatorname{Rep}_P(\mathcal F,S)] \pm \epsilon</math>

=== Bounding the generalization error ===
The Rademacher complexity is a theoretical justification for [[empirical risk minimization]].

When the error function is binary (0-1 loss), for every <math>\delta>0</math>, 
:<math>\sup_{f \in \mathcal F}(L_P(f) - L_S(f)) \leq 2 \operatorname{Rad}_S(\mathcal F) + 4 \sqrt{2\ln(4/\delta)\over m}</math>
with probability at least <math>1-\delta</math>.<ref name="book14" />{{rp|328}}

There exists a constant <math>c > 0</math>, such that when the error function is squared <math>\ell(\hat y, y) := (\hat y - y)^2</math>, and the function class <math>\mathcal F</math> consists of functions with range within <math>[-1, +1]</math>, then for any <math>\delta > 0</math><math display="block">L_P(f) - L_S(f) \leq c\left[ L_S(f) + 
(\ln m)^4\overline{\operatorname{Rad}}_m(\mathcal F)^2 + 
\frac{\ln (1/\delta)}{m} \right], \quad \forall f \in \mathcal F  </math>with probability at least <math>1-\delta</math>.<ref name=":1" />{{Pg|location=Theorem 2.2}}

=== Oracle inequalities ===
Let the [[Bayes risk]] <math>L^* = \inf_f L_P(f)</math>, where <math>f</math> can be ''any'' measurable function.

Let the function class <math>\mathcal F</math> be split into "complexity classes" <math>\mathcal F_r</math>, where <math>r \in \R</math> are levels of complexity. Let <math>p_r</math> be real numbers. Let the complexity measure function <math>p</math> be defined such that <math>p(f) := \min \{p_r : f \in \mathcal F_r\}</math>.

For any dataset <math>S</math>, let <math>\hat f</math> be a minimizer of <math>L_S(f) + p(f) </math>. If<math display="block">\sup_{f \in \mathcal F_r}|L_P(f) - L_S(f)| \leq p_r, \quad \forall r</math>then we have the oracle inequality<math display="block">L(\hat f) - L^* \leq  \inf _r\left(\inf _{f \in \mathcal{F}_r} L(f)- L^*+2 p_r\right)  </math>Define <math>f_r^* \in \arg \min _{f \in \mathcal{F}_r} L(f)</math>. If we further assume<math display="block">r \leq s \text { implies } \mathcal{F}_r \subseteq \mathcal{F}_s \text { and } p_r \leq p_s</math>and <math display="block">\begin{aligned}
\forall r, \sup _{f \in \mathcal{F}_r}\left(L_P(f)-L_P\left(f_r^*\right)-2\left(L_S(f)-L_S\left(f_r^*\right)\right)\right) &\leq 2 p_r / 7 \\
\sup _{f \in \mathcal{F}_r}\left(L_S(f)-L_S\left(f_r^*\right)-2\left(L_P(f)-L_P\left(f_r^*\right)\right)\right) &\leq 2 p_r / 7
\end{aligned}</math>then we have the oracle inequality <math display="block">L_P(\widehat{f})- L^* \leq \inf _r\left(\inf _{f \in \mathcal{F}_r} L_P (f)- L^* +3 p_r\right)</math>

<ref name=":1" />{{Pg|location=Theorem 2.3}}

== Bounding the Rademacher complexity ==
Since smaller Rademacher complexity is better, it is useful to have upper bounds on the Rademacher complexity of various function sets. The following rules can be used to upper-bound the Rademacher complexity of a set <math>A \subset \mathbb{R}^m</math>.<ref name=book14/>{{rp|329–330}}

1. If all vectors in <math>A</math> are translated by a constant vector <math>a_0 \in \mathbb{R}^m</math>, then Rad(''A'') does not change.

2. If all vectors in <math>A</math> are multiplied by a scalar <math>c\in \mathbb{R}</math>, then Rad(''A'') is multiplied by <math>|c|</math>.

3. <math> \operatorname{Rad}(A+B) = \operatorname{Rad}(A) + \operatorname{Rad}(B)</math>.<ref name=book12/>{{rp|56}}

4. (Kakade & Tewari Lemma) If all vectors in <math>A</math> are operated by a [[Lipschitz function]], then Rad(''A'') is (at most) multiplied by the [[Lipschitz constant]] of the function. In particular, if all vectors in <math>A</math> are operated by a [[contraction mapping]], then Rad(''A'') strictly decreases.

5. The Rademacher complexity of the [[convex hull]] of <math>A</math> equals Rad(''A'').

6. (Massart Lemma) The Rademacher complexity of a finite set grows logarithmically with the set size. Formally, let <math>A</math> be a set of <math>N</math> vectors in <math>\mathbb{R}^m</math>, and let <math>\bar{a}</math> be the mean of the vectors in <math>A</math>. Then:
:<math>\operatorname{Rad}(A) \leq \max_{a\in A} \|a-\bar{a}\| \cdot {\sqrt{2\log N}\over m}</math>
In particular, if <math>A</math> is a set of binary vectors, the norm is at most <math>\sqrt{m}</math>, so:
:<math>\operatorname{Rad}(A) \leq \sqrt{2\log N \over m} </math>

=== Bounds related to the VC dimension ===
Let <math>H</math> be a [[set family]] whose  [[VC dimension]]  is <math>d</math>. It is known that the [[growth function]] of <math>H</math> is bounded as:
:for all <math>m>d+1</math>: <math>\operatorname{Growth}(H,m)\leq (em/d)^d</math>
This means that, for every set <math>h</math> with at most <math>m</math> elements, <math>|H\cap h|\leq (em/d)^d</math>. The set-family <math>H\cap h</math> can be considered as a set of binary vectors over <math>\mathbb{R}^m</math>. Substituting this in Massart's lemma gives:
:<math>\operatorname{Rad}(H\cap h) \leq {\sqrt{2 d \log(em/d) \over m}}</math>

With more advanced techniques ([[Dudley's theorem|Dudley's entropy bound]] and Haussler's upper bound<ref>Bousquet, O. (2004). Introduction to Statistical Learning Theory. ''Biological Cybernetics'', ''3176''(1), 169–207. {{doi|10.1007/978-3-540-28650-9_8}}</ref>) one can show, for example, that there exists a constant <math>C</math>, such that any class of <math>\{0,1\}</math>-indicator functions with [[Vapnik–Chervonenkis dimension]] <math>d</math> has Rademacher complexity upper-bounded by <math>C\sqrt{\frac{d}{m}}</math>.

=== Bounds related to linear classes ===
The following bounds are related to linear operations on <math>S</math> – a constant set of <math>m</math> vectors in <math>\mathbb{R}^n</math>.<ref name=book14/>{{rp|332–333}}

1. Define <math>A_2 = \{(w\cdot x_1,\ldots,w\cdot x_m) \mid \|w\|_2\leq 1\} = </math> the set of dot-products of the vectors in <math>S</math> with vectors in the [[unit ball]]. Then:
:<math>\operatorname{Rad}(A_2) \leq {\max_i\|x_i\|_2 \over \sqrt{m}}</math>

2. Define <math>A_1 = \{(w\cdot x_1,\ldots,w\cdot x_m) \mid \|w\|_1\leq 1\} = </math> the set of dot-products of the vectors in <math>S</math> with vectors in the unit ball of the 1-norm. Then:
:<math>\operatorname{Rad}(A_1) \leq \max_i\|x_i\|_\infty\cdot \sqrt{2\log(2n) \over m}</math>

=== Bounds related to covering numbers ===
The following bound relates the Rademacher complexity of a set <math>A</math> to its external [[covering number]] – the number of balls of a given radius <math>r</math> whose union contains <math>A</math>. The bound is attributed to Dudley.<ref name=book14/>{{rp|338}}

Suppose <math>A\subset \mathbb{R}^m</math> is a set of vectors whose length (norm) is at most <math>c</math>. Then, for every integer <math>M>0</math>:
:<math>
\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^{\text{ext}}_{c\cdot 2^{-i}}(A)\right)} 
</math>

In particular, if <math>A</math> lies in a ''d''-dimensional subspace of <math>\mathbb{R}^m</math>, then:
:<math>\forall r>0: N^{\text{ext}}_r(A) \leq (2 c \sqrt{d}/r)^d</math>
Substituting this in the previous bound gives the following bound on the Rademacher complexity:
:<math>
\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)
</math>

== Gaussian complexity ==
'''Gaussian complexity''' is a similar complexity with similar physical meanings, and can be obtained from the Rademacher complexity using the random variables <math>g_i</math> instead of <math>\sigma_i</math>, where <math>g_i</math> are [[Normal distribution|Gaussian]] [[Independent and identically distributed random variables|i.i.d.]] random variables with zero-mean and variance 1, i.e. <math>g_i \sim \mathcal{N}(0,1)</math>. Gaussian and Rademacher complexities are known to be equivalent up to logarithmic factors.
=== Equivalence of Rademacher and Gaussian complexity ===
Given a set <math>A\subseteq\mathbb{R}^n</math> then it holds that<ref name=":0">{{Cite book |last=Wainwright |first=Martin |url=https://www.worldcat.org/oclc/1089254580 |title=High-dimensional statistics : a non-asymptotic viewpoint |date=2019 |isbn=978-1-108-62777-1 |location=Cambridge, United Kingdom |pages=Exercise 5.5 |oclc=1089254580}}</ref>:<br />
<math>\frac{G(A)}{2\sqrt{\log{n}}} \leq \text{Rad}(A) \leq \sqrt{\frac{\pi}{2}}G(A)</math><br />
Where <math>G(A)</math> is the Gaussian Complexity of A. As an example, consider the rademacher and gaussian complexities of the L1 ball. The Rademacher complexity is given by exactly 1, whereas the Gaussian complexity is on the order of <math>\sqrt {\log d}</math> (which can be shown by applying known properties of suprema of a set of [[Sub-Gaussian distribution|subgaussian]] random variables).<ref name=":0" />

==References==
{{reflist}}
* Peter L. Bartlett, Shahar Mendelson (2002) ''Rademacher and Gaussian Complexities: Risk Bounds and Structural Results''. Journal of Machine Learning Research 3 463–482
* Giorgio Gnecco, Marcello Sanguineti (2008) ''Approximation Error Bounds via Rademacher's Complexity''. Applied Mathematical Sciences, Vol. 2, 2008, no. 4, 153–176

[[Category:Machine learning]]
[[Category:Measures of complexity]]