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 training sample , and a hypotheses set (where is a class of real-valued functions defined on a domain space ), the empirical Rademacher complexity of is defined as:
where are independent random variables such that for . The random variables are referred to as Rademacher variables.
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 .
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 .
Gaussian complexity is a similar complexity with similar physical meanings, and can be obtained from the previous complexity using the random variables instead of , where are Gaussian i.i.d. random variables with zero-mean and variance 1, i.e. .
- 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 (2008) Approximation Error Bounds via Rademacher's Complexity. Applied Mathematical Sciences, Vol. 2, 2008, no. 4, 153 - 176