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

, the Rademacher complexity of A is defined as follows:

are independent random variables drawn from the Rademacher distribution. Some authors take the absolute value of the sum before taking the supremum is symmetric this makes no difference.

Rademacher complexity of a function class

. Then, the empirical Rademacher complexity is defined as:

This can also be written using the previous definition:

denotes function composition, i.e.:

The worst case empirical Rademacher complexity. The Rademacher complexity is:

where the above expectation is taken over an identically independently distributed.

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 the expectation, so that this quantity in the sum is maximized.

. The directions are along the vertices of a hypercube denotes half of the vertices of a hypercube, selected so that each diagonal has exactly one vertex selected. along all diagonal directions of a hypercube.

Examples

A singleton set has 0 width in any direction, so it has Rademacher complexity 0.

.

The unit cube. Similarly, the unit cross-polytope.

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. This can be quantified using the notion of representativeness the probability distribution represents a binary classifier, the error function is a 0–1 loss function when the underlying hypothesis is irrelevant. Define:

1. ;

2. .

, is defined as:

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.

, then

Furthermore, the representativeness is concentrated around its expectation:

Bounding the generalization error

The Rademacher complexity is a theoretical justification for empirical risk minimization.

,

.

.

Oracle inequalities

Let the Bayes risk can be any measurable function.

.

Bounding the Rademacher complexity

.

• , then Rad(A) does not change.

• , then Rad(A.

• .

• are operated by a Lipschitz function, then Rad(A) is (at most) multiplied by the Lipschitz constant are operated by a contraction mapping, then Rad(A) strictly decreases.

• The Rademacher complexity of the convex hull equals Rad(A).

• (Massart Lemma) The Rademacher complexity of a finite set. Then:

, so:

Bounds related to the VC dimension

be a set family whose VC dimension. It is known that the growth function is bounded as:

. Substituting this in Massart's lemma gives:

With more advanced techniques (Dudley's entropy bound and Haussler's upper bound-indicator functions with Vapnik–Chervonenkis dimension.

Bounds related to linear classes

.

• with vectors in the unit ball. Then:

  with vectors in the unit ball of the 1-norm. Then:

Bounds related to covering numbers

to its external covering number. The bound is attributed to Dudley.

:

lies in a d, then:

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

Gaussian complexity

Gaussian complexity are Gaussian i.i.d.. Gaussian and Rademacher complexities are known to be equivalent up to logarithmic factors.

Equivalence of Rademacher and Gaussian complexity

then it holds that: (which can be shown by applying known properties of suprema of a set of subgaussian random variables).

References

• 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