Rademacher complexity
In computational learning theory (machine learning and theory of computation), Rademacher complexity, named after Hans Rademacher, measures richness of a class of real-valued functions with respect to a probability distribution. Definitions. Rademacher complexity of a set. Given a set formula_1, the Rademacher complexity of "A" is defined as follows: where formula_3 are independent random variables drawn from the Rademacher distribution i.e. formula_4 for formula_5, and formula_6. Some authors take the absolute value of the sum before taking the supremum, but if formula_7 is symmetric this makes no difference. Rademacher complexity of a function class. Given a sample  formula_8, and a class formula_9 of real-valued functions defined on a domain space formula_10, where formula_11 is the loss function formula_12 of a classifier formula_13, the empirical Rademacher complexity of formula_9 given formula_15 is defined as: This can also be written using the previous definition: where formula_18 denotes function composition, i.e.: Let formula_20 be a probability distribution over formula_10. The Rademacher complexity of the function class formula_9 with respect to formula_20 for sample size formula_24 is: where the above expectation is taken over an identically independently distributed (i.i.d.) sample formula_26 generated according to formula_20. Examples. 1. formula_7 contains a  single vector, e.g., formula_29. Then: The same is true for every singleton hypothesis class. 2. formula_7 contains two vectors, e.g., formula_32. Then: 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 formula_15. This can be quantified using the notion of representativeness. Denote by formula_20 the probability distribution from which the samples are  drawn. Denote by formula_36 the set of hypotheses (potential classifiers) and denote by formula_9 the corresponding set of error functions, i.e., for every hypothesis formula_38, there is a function formula_39, that maps each training sample (features,label) to the error of the classifier formula_13 (note in this case hypothesis and classifier are used interchangeably). For example, in the case that formula_13 represents a binary classifier, the error function is a 0–1 loss function, i.e. the error function formula_42 returns 1 if formula_13 correctly classifies a sample and 0 else. We omit the index and write formula_11 instead of formula_42 when  the underlying hypothesis is irrelevant. Define: The representativeness of the sample formula_15, with respect to formula_20 and formula_9, 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. The expected representativeness of a sample can be bounded above by the Rademacher  complexity of the function class: Bounding the generalization error. 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), for every formula_57, with probability at least formula_58, for every hypothesis formula_38: 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 formula_61. 1. If all vectors in formula_7 are translated by a constant vector formula_63 , then Rad("A") does not change. 2. If all vectors in formula_7 are multiplied by a scalar formula_65, then Rad("A") is multiplied by formula_66. 3. Rad("A" + "B") = Rad("A") + Rad("B"). 4. (Kakade & Tewari Lemma) If all vectors in formula_7 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 formula_7 are operated by a contraction mapping, then Rad("A") strictly decreases. 5. The Rademacher complexity of the convex hull of formula_7 equals Rad("A"). 6. (Massart Lemma) The Rademacher complexity of a finite set grows logarithmically  with the set size. Formally, let formula_7 be a set of formula_71 vectors in formula_72, and let formula_73 be the mean of the vectors in formula_7. Then: In particular, if formula_7 is a set of binary vectors, the norm is at most formula_77, so: Bounds related to the VC dimension. Let formula_36 be a set family whose VC dimension is formula_80. It is known that the growth function of formula_36 is bounded as: This means that, for every set formula_13 with at most formula_24 elements, formula_86. The set-family formula_87 can be considered as a set of binary vectors over  formula_72. Substituting this in Massart's lemma gives: With more advanced techniques (Dudley's entropy bound and Haussler's upper bound) one can show, for example, that there exists a constant formula_90, such that any class of formula_91-indicator functions with Vapnik–Chervonenkis dimension formula_80 has Rademacher complexity upper-bounded by formula_93. Bounds related to linear classes. The following bounds are related to linear operations on formula_15 – a constant set of formula_24 vectors in formula_96. 1. Define formula_97 the set of dot-products of the vectors in formula_15 with vectors in the unit ball. Then: 2. Define formula_100 the set  of dot-products of the vectors in formula_15 with vectors in the unit ball of the 1-norm. Then: Bounds related to covering numbers. The following bound relates the Rademacher complexity of a set formula_7 to its external covering number – the number of balls of a given radius formula_104 whose union contains formula_7. The bound is attributed to Dudley. Suppose formula_106 is a set of vectors whose length (norm) is at most formula_107. Then, for every integer formula_108: In particular, if formula_7 lies in a "d"-dimensional subspace of formula_72, then: Substituting this in the previous bound gives the following bound  on the Rademacher complexity: Gaussian complexity. Gaussian complexity is a similar complexity with similar physical meanings, and can be obtained from the Rademacher complexity using the random variables formula_114 instead of formula_115, where formula_114 are Gaussian i.i.d. random variables with zero-mean and variance 1, i.e. formula_117. Gaussian and Rademacher complexities are known to be equivalent up to logarithmic factors. Equivalence of Rademacher and Gaussian complexity. Given a set formula_118 then it holds that: formula_119 Where formula_120 is the Gaussian Complexity of A