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 , 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. Rademacher complexity of a function class 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 . 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 under the expectation, so that this quantity in the sum is maximised. Examples 1. contains a single vector, e.g., . Then: The same is true for every singleton hypothesis class. 2. contains two vectors, e.g., . 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 . This can be quantified using the notion of representativeness. Denote by the probability distribution from which the samples are drawn. Denote by the set of hypotheses (potential classifiers) and denote by the corresponding set of error functions, i.e., for every hypothesis , there is a function , that maps each training sample (features,label) to the error of the classifier (note in this case hypothesis and classifier are used interchangeably). For example, in the case that represents a binary