classifier, the error function is a 0–1 loss function, i.e. the error function returns 1 if correctly classifies a sample and 0 else. We omit the index and write instead of when the underlying hypothesis is irrelevant. Define: – the expected error of some error function on the real distribution ; – the estimated error of some error function on the sample . The representativeness of the sample , with respect to and , 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 , with probability at least , for every hypothesis : 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 . 1. If all vectors in are translated by a constant vector , then Rad(A) does not change. 2. If all vectors in are multiplied by a scalar , then Rad(A) is multiplied by . 3. . 4. (Kakade & Tewari Lemma) If all vectors in 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 are operated by a contraction mapping, then Rad(A) strictly decreases. 5. The Rademacher complexity of the convex hull of equals Rad(A). 6. (Massart Lemma) The Rademacher complexity of a finite set grows logarithmically with the set size. Formally, let be a set of vectors in , and let be the mean of the vectors in . Then: In particular, if is a set of binary vectors, the norm is at most , so: Bounds related to the VC dimension Let be a set family whose VC dimension is