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. Given a set , the Rademacher complexity of A is defined as follows: where are independent random variables drawn from the Rademacher distribution i.e. for , and . Some authors take the absolute value of the sum before taking the supremum, but if is symmetric this makes no difference. Let be a sample of points and consider a function class of real-valued functions over . Then, the empirical Rademacher complexity of given is defined as: This can also be written using the previous definition: where denotes function composition, i.e.: Let be a probability distribution over . The Rademacher complexity of the function class with respect to for sample size is: where the above expectation is taken over an identically independently distributed (i.i.d.) sample generated according to . 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 under the expectation, so that this quantity in the sum is maximised.

1. contains a single vector, e.g., . Then: The same is true for every singleton hypothesis class.
2. contains two vectors, e.g., . Then: 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. In machine learning, it is desired to have a training set that represents the true distribution of some sample data . This can be quantified using the notion of representativeness. Denote by the probability distribution from which the samples are drawn.