Na teoria da aprendizagem computacional (aprendizado de máquina e teoria da computação), Complexidade de Rademacher, em homenagem a Hans Rademacher, mede a riqueza de uma classe com funções de valores reais, com respeito a uma distribuição de probabilidade.
Dada uma amostra de treinamento
, e uma classe
de valores reais das funções definidas em um espaço de domínio
, a complexidade empírica de Rademacher de
é definida como:
onde
são variáveis aleatórias independentes extraídas a partir da distribuição de Rademacher i.e.
para
.
Seja
uma distribuição de probabilidade sobre
.
A complexidade de Rademacher da classe de funções
com respeito a
para o tamanho da amostra
é:
onde a expectância acima é tomada de mais de uma amostra idêntica e independentemente distribuída (i.i.d.)
gerada de acordo com
.
Pode-se mostrar, por exemplo, que existe uma constante
, tal que qualquer classe de funções
-indicadoras com a dimensão de Vapnik-Chervonenkis
tem a complexidade de Radamacher superiormente delimitada por
.
Complexidade Gaussiana
Complexidade Gaussiana é uma complexidade semelhante com significados físicos parecidos, e pode ser obtido a partir da complexidade anterior utilizando as variáveis aleatórias
em vez de
, onde
são variáveis aleatórias Gaussianas i.i.d. com média zero e variância 1, i.e.
.