. It is known that the growth function of is bounded as: for all : This means that, for every set with at most elements, . The set-family can be considered as a set of binary vectors over . 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 , such that any class of -indicator functions with Vapnik–Chervonenkis dimension has Rademacher complexity upper-bounded by . Bounds related to linear classes The following bounds are related to linear operations on – a constant set of vectors in . 1. Define the set of dot-products of the vectors in with vectors in the unit ball. Then: 2. Define the set of dot-products of the vectors in 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 to its external covering number – the number of balls of a given radius whose union contains . The bound is attributed to Dudley. Suppose is a set of vectors whose length (norm) is at most . Then, for every integer : In particular, if lies in a d-dimensional subspace of , 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 instead of , where are Gaussian i.i.d. random variables with zero-mean and variance 1, i.e. . Gaussian and Rademacher complexities are known to be equivalent up to logarithmic factors. Equivalence of Rademacher and Gaussian complexity Given a set then it holds that: Where is the Gaussian Complexity of A 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 Machine learning Measures of complexity