Complexidade de Rademacher

No modelo estatístico de aprendizado de máquina temos um conjunto de dados $ {\bf o}_n = \{(x_1,y_1), \cdots (x_n , y_n)\}$, no qual admitimos ser uma amostra aleatória simples (iid) da probabilidade $\mathbb{P}$. Uma estratégia é uma função $A$ definida sobre o espaço de dados $\mathbb{O}^n$ a valores no espaço de preditores admissíveis $\mathcal{H}$ que é Borel mensurável. A performance de uma estratégia $A$ é medida pela probabilidade condicional do erro de classificação dado a amostra, isto é

\[
L(\mathbb{P} , A({\bf o}_n )) = \mathbb{P} \left[(x,y) \in \mathbb{O}: y \neq A({\bf o}_n  , x)   \right], ~  {\bf o}_n \in \mathbb{O}^n.
\]

Para mantermos a máxima generalidade possível, vamos tratar durante este módulo com uma função de risco mais abrangente. Considere $\ell: \mathbb{O} \times \mathcal{H} \rightarrow [0,1]$ uma função Borel mensurável qualquer. O objetivo da teoria de classificação binária consiste em encontrar preditores cuja função risco esperado seja o mais próximo possível do risco do preditor de Bayes. Como não temos acesso a probabilidade $\mathbb{P}$, uma estratégia simples e natural é dado pelo princípio da minimização do risco empírico. Considere $\mathcal{H}$ uma subclasse de preditores admissíveis, denotamos por $A_E$ a estratégia que minimiza o risco empírico

\[
L_E ({\bf o}_n , A_E({\bf o}_n)) = \inf_{h \in \mathcal{H}}\frac{1}{n} \sum_{i=1}^n \ell (o_i , h) , ~ {\bf o}_n \in \mathbb{O}^n.
\]  O risco esperado da estratégia $A_E$ que minimiza o risco empírico satisfaz

\[
L(\mathbb{P}, A_E({\bf o}_n)) - \inf_{h \in \mathcal{H}} L(\mathbb{P} , h) = \]  \[ L(\mathbb{P}, A_E({\bf o}_n)) - L_E ({\bf o}_n , h^\star) + L_E ({\bf o}_n , h^\star) -   L(\mathbb{P} , h^\star) \leq \] \[ L(\mathbb{P}, A_E({\bf o}_n)) - L_E ({\bf o}_n ,  A_E({\bf o}_n)) + L_E ({\bf o}_n , h^\star) -   L(\mathbb{P} , h^\star) \leq \] \[ 2 \sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big|, ~ ~ (\text{Desigualdade 1}), \] no qual $h^\star$ é o classificador de Bayes. Além disso, temos que

\[
\mid L(\mathbb{P}, A_E({\bf o}_n)) - L_E ({\bf o}_n, A_E({\bf o}_n)) \mid ~ \leq ~  \sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h) \big|, ~ ~ (\text{Desigualdade 2}),
\] para todo ${\bf o}_n \in \mathbb{O}^n$ e $\mathbb{P} \in \mathcal{P}(\mathbb{O})$. A partir das desigualdades 1 e 2, concluímos que se tivermos estimativas para a probabilidade da diferença uniforme 

\[\sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big| = \sup_{h \in \mathcal{H}} \big| \frac{1}{n} \sum_{i=1}^n \ell (o_i , h) - \mathbb{E}_{\mathbb{P}} \ell (\cdot , h)   \big|
\] suficientemente baixa, garantimos que a probabilidade de erro (risco esperado) da estratégia $A_E$ não é muito maior que a probabilidade de erro do estimador de Bayes na classe $\mathcal{H}$. Além disso, a estimativa empírica $L_E (\cdot, A_E(\cdot))$ também é uma boa aproximação para $\inf_{h \in \mathcal{H}} L(\mathbb{P} , h)$. 

Para todo preditor admissível $h \in \mathcal{H}$, a função $\ell (\cdot , h): \mathbb{O} \rightarrow [0,1]$ Borel mensurável. Desta forma, definimos a seguinte classe de funções $\mathcal{W} = \{\ell (\cdot,h) : h \in \mathcal{H} \}$ como uma composição da função de risco $\ell$ com a classe de preditores admissíveis $\mathcal{H}$. Ao tomarmos $f \in \mathcal{W}$,  $\mathbb{P}(f) = \mathbb{E}_{\mathbb{P}} f((X,Y))$ e $\mathbb{P}_n f= \frac{1}{n} \sum_{i=1}^n f(X_i,Y_i)$, concluímos que a diferença uniforme é dada por

\[\sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big| = \sup_{f \in \mathcal{W}} \left| \mathbb{P}_n (f) -\mathbb{P}(f)  \right| .\]

Como consequência da definição, para todo $h \in \mathcal{H}$, temos que $L_E(\cdot , h)$ é uma variável aleatória com média $L(\mathbb{P},h)$. Portanto, temos que avaliar a diferença uniforme entre uma variável aleatória com valores no intervalo $[0,1]$ e sua média. No caso particular do risco dado pelo erro de classificação, temos que  $nL_E(\cdot , h)$ tem distribuição binomial com parâmetros $n$ e $L(\mathbb{P},h)$. Neste caso, temos que estudar a diferença uniforme entre a distribuição Bernoulli e sua média. 

Na sequência, vamos apresentar algumas propriedades relacionadas com o supremo que serão utilizadas durante esta seção. Sejam $f_1 , f_2 : \mathbb{O} \rightarrow \mathbb{R}$ duas funções satisfazendo $- \infty < \sup_x f_i(x) < \infty$ para $i=1,2$. Então temos que 

\[
\sup_x f_1(x) - \sup_x f_2 (x) \leq \sup_x (f_1(x) - f_2 (x)), ~ ~ (\text{Desigualdade 3}).
\] De fato, para todo $\epsilon > 0$ existe $x_\epsilon \in \mathbb{O}$ tal que $f_1(x_\epsilon) \geq \sup_x f_1 (x) - \epsilon$. Então, temos que

\begin{eqnarray*}
\sup_x f_1(x) - \sup_x f_2 (x) &\leq& \sup_x f_1(x) - f_2 (x_\epsilon) \leq f_1 (x_\epsilon) - f_2 (x_\epsilon) + \epsilon \\ 
&\leq& \sup_x \left( f_1(x) - f_2 (x) \right) + \epsilon.
\end{eqnarray*} Como $\epsilon > 0$ é arbitrário, obtemos a desigualdade 3. Por outro lado, temos que 

\[
\sup_x \left(f_1(x) + f_2 (x)  \right) \leq \sup_x f_1 (x) + \sup_x f_2 (x) ~ ~ (\text{Desigualdade 4}).
\] Como consequência da desigualdade 4, concluímos que o supremo é uma função convexa. Considere $\{a_i : i \in I\}$ e  $\{a_i^\prime : i \in I\}$ duas família de elementos de $\mathbb{R}$ indexadas por $I$. Então, temos que 

\[
 \sup_{i \in I} \left( \lambda a_i + (1-\lambda)a^\prime_i  \right) \leq \lambda  \sup_{i \in I}  a_i + (1-\lambda) \sup_{i \in I} a^\prime_i ,  ~ ~ (\text{Desigualdade 5}),
\] para todo $0 \leq \lambda \leq 1 $.

As desigualdades relacionadas com concentração estão entre as principais ferramentas utilizadas para estudar a diferença uniforme apresentada nas desigualdade 1 e 2 . A mais simples e extremamente útil é denominada desigualdade das diferenças finitas (bounded differences inequality)

Lema 1: Bounded Differences Inequality - BDI

Seja $g: \mathbb{O}^n \rightarrow \mathbb{R}$ uma função Borel mensurável de $n$ variáveis tal que existem constantes não negativas satisfazendo,

\[
\sup_{(x_1 , \cdots , x_n) \in \mathbb{O}^n } ~ \sup_{x^\prime_i \in \mathbb{O} }\big| g(x_1, \cdots , x_n) - g(x_1, \cdots , x_{i-1}, x^\prime_i , x_{i+1} , \cdots , x_n) \big| \leq c_i,  
\] para todo $i=1,2, \cdots , n$. Considere $W_1, W_2 , \cdots , W_n$ variáveis aleatórias independentes. Então a variável aleatória $Z=g(W_1, \cdots , W_n)$ satisfaz
\[
\mathbb{P}^n  \left[ \big| Z - \mathbb{E} Z  \big| > t  \right] \leq 2 e^{-2t^2 / C},
\] no qual $C = \sum_{i=1}^n c_i^2$.

A hipótese de diferenças limitadas relacionada com a função $g$ nos diz que se alterarmos a i-ésima coordenada e mantermos as demais fixas, o valor da função $g$ não se altera mais que $c_i$. O exemplo de interesse é dado por 

\[
Z= \sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big| = \sup_{f \in \mathcal{W}} \left| \mathbb{P}_n (f) - \mathbb{P}(f) \right|.
\]
Como a função $\ell$ assume valores em $[0,1]$, obtemos que $Z$ satisfaz a hipótese de diferenças limitadas com $c_i=1/n$. De fato, considere ${\bf o}_n=(o_1, \cdots , o_n)$ e ${\bf o}_n^\prime = (o_1 , \cdots , o_{i-1}, o^{\prime}_i , o_{i+1} , \cdots , o_n)$. Como consequência da desigualdade 3, temos que 

\[
 \left| \sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big| - \sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n^\prime , h) - L(\mathbb{P} , h)   \big|  \right| \leq 
\]

\[
\sup_{h \in \mathcal{H}} \left|  ~ \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big| - \big| L_E ({\bf o}_n^\prime , h) - L(\mathbb{P} , h)   \big| ~ \right| = 
\]

\[
\sup_{h \in \mathcal{H}} \left|  ~ \left| \frac{1}{n}  \left( \sum_{j\neq i} \ell (o_j , h) - L(\mathbb{P} , h)   \right) + 
\frac{1}{n} \ell (o_i , h) \right| \right.  - 
\]

\[
\left. \left| \frac{1}{n}  \left( \sum_{j\neq i} \ell (o_j , h) - L(\mathbb{P} , h)   \right) + 
\frac{1}{n} \ell (o_i^\prime , h) \right| ~ \right| \leq \frac{1}{n}.
\]

Como consequência do lema BDI, para todo $0 < \delta < 1/2$, obtemos que

 \begin{eqnarray*}
\mathbb{P}^n \left[ ( Z - \mathbb{E}_{\mathbb{P}^n } Z ) > \sqrt{\frac{\ln (1/ \delta)}{2n}} \right] &\leq&  \mathbb{P}^n \left[ \mid Z - \mathbb{E}_{\mathbb{P}^n } Z \mid > \sqrt{\frac{-\ln (\delta)}{2n}} \right] \\ &\leq&  \mathbb{P}^n \left[ \mid Z - \mathbb{E}_{\mathbb{P}^n } Z \mid > \sqrt{\frac{-\ln (2 / \delta )}{2n}} \right] \\ 
&\leq& 2 e^{-2n  \ln(2/ \delta) \frac{1}{2n} } = \delta .
 \end{eqnarray*} Portanto, existe um conjunto $G \in \beta (\mathbb{O}^n)$ com probabilidade $\mathbb{P}^n (G) \geq 1-\delta$, tal que

\[
\sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big|   \leq  \mathbb{E}_{\mathbb{P}^n } \sup_{h \in \mathcal{H}} \big| L_E (\cdot , h) - L(\mathbb{P} , h)   \big| + \sqrt{\frac{\ln (1/ \delta)}{2n}} ~ ~ (\text{Desigualdade 6}),
 \]  para todo ${\bf o}_n \in G$. Como consequência deste resultado, podemos nos concentrar no valor esperado $EZ$, que pode ser limitado por uma estratégia de simetrização. Introduzimos uma ``amostra fantasma'' $({\bf X}^\prime , {\bf Y}^\prime) = \{(X_1^\prime, Y_1^\prime), \cdots , (X_n^\prime, Y_n^\prime) \}$ iid com distribuição de probabilidade $\mathbb{P}$ e independente da amostra original $ ({\bf X} , {\bf Y}) =  \{(X_1 , Y_1), \cdots , (X_n, Y_n) \}$. Dado que o vetor aleatório $( ({\bf X} , {\bf Y}) , ({\bf X}^\prime , {\bf Y}^\prime) )$ está definido no espaço de probabilidade produto $(\mathbb{O}^{2n} , \beta (\mathbb{O}^{2n}), \mathbb{P}^{2n})$, segue do fato da função supremo ser convexa (ver desigualdade 5) e da desigualdade de Jensen,  que 

 \[
  \mathbb{E}_{\mathbb{P}^n } \sup_{h \in \mathcal{H}} \big| L_E (({\bf X} , {\bf Y}) , h) - L(\mathbb{P} , h)   \big| = \mathbb{E}_{\mathbb{P}^{2n} } \sup_{h \in \mathcal{H}} \big| L_E (({\bf X} , {\bf Y}) , h) - L(\mathbb{P} , h)   \big| \] \[=
 \mathbb{E}_{\mathbb{P}^{2n} } \sup_{h \in \mathcal{H}} \big| L_E (({\bf X} , {\bf Y}) , h) - \mathbb{E}_{\mathbb{P}^{2n} } \left[ L_E (({\bf X}^\prime , {\bf Y}^\prime) , h) \mid  ({\bf X} , {\bf Y}) \right]   \big| =  \] \[
 \mathbb{E}_{\mathbb{P}^{2n} } \sup_{h \in \mathcal{H}} \big| \mathbb{E}_{\mathbb{P}^{2n} } \left[ L_E (({\bf X} , {\bf Y}) , h) -  L_E (({\bf X}^\prime , {\bf Y}^\prime) , h) \mid  ({\bf X} , {\bf Y}) \right]   \big| \leq \] \[
 \mathbb{E}_{\mathbb{P}^{2n} } \sup_{h \in \mathcal{H}} \big| L_E (({\bf X} , {\bf Y}) , h) -  L_E (({\bf X}^\prime , {\bf Y}^\prime) , h)    \big| ~ ~ (\text{Desigualdade 7}).
 \]

Considere $\sigma = \{\sigma_1, \cdots , \sigma_n\}$ variáveis aleatórias independentes e identicamente distribuídas tal que $\mu [\sigma_i= 1 ] = \mu [\sigma_i= -1 ] = 1/2$.  Assim, ao tomarmos o espaço de probabilidade produto $ (\mathbb{O}^{2n} \times \{1 , -1\}^n , \beta (\mathbb{O}^{2n} \times \{1 , -1\}^n ) , \mathbb{P}^{2n} \times \mu^n)$, concluímos que os vetores aleatórios $\{\sigma, ( ({\bf X} , {\bf Y}) , ({\bf X}^\prime , {\bf Y}^\prime) )\}$ definidos sobre este espaço de probabilidade são independentes. Desde que a distribuição de probabilidade das variáveis aleatórias $ L_E (({\bf X} , {\bf Y}) , h) -  L_E (({\bf X}^\prime , {\bf Y}^\prime) , h)$ e $ L_E (({\bf X}^\prime , {\bf Y}^\prime) , h)- L_E (({\bf X} , {\bf Y}) , h)  $ são idênticas e $\sigma$ tem distribuição simétrica, concluímos que
 
 \[
 \mathbb{E}_{\mathbb{P}^{2n} } \sup_{h \in \mathcal{H}} \big| L_E (({\bf X} , {\bf Y}) , h) -  L_E (({\bf X}^\prime , {\bf Y}^\prime) , h)    \big| =  \mathbb{E}_{\mathbb{P}^{2n} } \sup_{h \in \mathcal{H}} \frac{1}{n} \left| \sum_{i=1}^n \left( \ell ((X_i , Y_i) , h) - \ell ((X_i^\prime , Y_i^\prime) , h) \right)  \right| =  \]  \[
 \mathbb{E}_{\mathbb{P}^{2n} \times \mu^n } \sup_{h \in \mathcal{H}} \frac{1}{n} \left| \sum_{i=1}^n \sigma_i \left( \ell ((X_i , Y_i) , h) - \ell ((X_i^\prime , Y_i^\prime) , h) \right)  \right| \leq
 \] \[  \mathbb{E}_{\mathbb{P}^{2n} \times \mu^n } \sup_{h \in \mathcal{H}} \frac{1}{n} \left| \sum_{i=1}^n \sigma_i \left( \ell ((X_i , Y_i) , h) \right)  \right| + \mathbb{E}_{\mathbb{P}^{2n} \times \mu^n } \sup_{h \in \mathcal{H}} \frac{1}{n} \left| \sum_{i=1}^n \sigma_i \left( - \ell ((X_i^\prime , Y_i^\prime) , h) \right)  \right| =
 \]  \[ 2 \mathbb{E}_{\mathbb{P}^{n} \times \mu^n } \sup_{h \in \mathcal{H}} \frac{1}{n} \left| \sum_{i=1}^n \sigma_i \ell ((X_i , Y_i) , h) )  \right|~ ~ (\text{Desigualdade 8}).
 \] A complexidade empírica de Rademacher da classe $\mathcal{H}$ é dada por

\[
 \hat{\mathcal{R}}_n ( {\bf o}_n , \mathcal{H} ) := \mathbb{E}_{\mu^n } \sup_{h \in \mathcal{H}} \frac{1}{n} \left| \sum_{i=1}^n \sigma_i \ell (o_i  , h) )  \right|,  ~ {\bf o}_n = (o_1, \cdots , o_n)\in \mathbb{O}^n .
 \] A nomenclatura vem do fato de que  $\{\sigma_1 , \cdots , \sigma_n\}$ são denominadas variáveis aleatórias de Rademacher. Por outro lado, a complexidade de Rademacher (também conhecida como Rademacher Average) é dada por 
 
 \[
 \mathcal{R}_n ( \mathcal{H} ) := \mathbb{E}_{\mathbb{P}^{n} } \hat{\mathcal{R}}_n (\cdot , \mathcal{H} ).
 \] A seguir, apresentamos o teorema da complexidade de Rademacher. 

Teorema 1: Complexidade de Rademacher

Para todo $0 < \delta < 1$, existe um conjunto $G \in \beta (\mathbb{O}^n)$ com $\mathbb{P}(G) \geq 1 - \delta$, tal que
 \[
\sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big|   \leq  2 \mathcal{R}_n ( \mathcal{H} )  + \sqrt{\frac{\ln (1/ \delta)}{2n}}, ~ {\bf o}_n \in G ~ ~ (\text{Desigualdade 10}). 
 \]  Para todo $0 < \delta < 1/2$, existe um conjunto $\hat{G} \in \beta (\mathbb{O}^n)$ com $\mathbb{P}^n(\hat{G}) \geq 1 - \delta$, tal que 
 \[
 \sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big| \leq  2 \hat{\mathcal{R}}_n ({\bf o}_n , \mathcal{H} ) + 3
    \sqrt{\frac{\ln (2/ \delta)}{2n}}, ~ {\bf o}_n \in \hat{G} ~ ~ (\text{Desigualdade 11}).
 \]

Prova: 

A desigualdade 10 é consequência das desigualdades 7, 8 e 9. Para demonstrarmos a desigualdade 11, vamos aplicar novamente o lema 1 com $g ({\bf o}_n) = \hat{\mathcal{R}}_n ({\bf o}_n , \mathcal{H} )$ para todo ${\bf o}_n \in \mathbb{O}^n$. Considere ${\bf o}_n=(o_1, \cdots , o_n)$ e ${\bf o}_n^\prime = (o_1 , \cdots , o_{i-1}, o^{\prime}_i , o_{i+1} , \cdots , o_n)$. Como consequência da desigualdade 3, obtemos que 
  \[
 g ({\bf o}_n) - g ({\bf o}_n^\prime) =  \hat{\mathcal{R}}_n ({\bf o}_n , \mathcal{H} ) -  \hat{\mathcal{R}}_n ({\bf o}_n^\prime , \mathcal{H} ) =
 \] 
 \[
 \mathbb{E}_{\mu^n} \left[ \sup_{h \in \mathcal{H}} \frac{1}{n} \left| \sum_{j \neq i } \sigma_j \ell (o_j  , h) ) + \sigma_i \ell (o_i , h) \right| - \sup_{h \in \mathcal{H}} \frac{1}{n} \left| \sum_{j \neq i} \sigma_j \ell (o_j  , h) ) + \sigma_i \ell (o^\prime_i , h) \right|  \right] \leq
 \]
 \[
 \mathbb{E}_{\mu^n} \left[ \sup_{h \in \mathcal{H}} \left\{ \frac{1}{n} \left| \sum_{j \neq i } \sigma_j \ell (o_j  , h) ) + \sigma_i \ell (o_i , h) \right| -  \frac{1}{n} \left| \sum_{j \neq i} \sigma_j \ell (o_j  , h) ) + \sigma_i \ell (o^\prime_i , h) \right| \right\}  \right] \leq
 \]
 \[
 \sup_{h \in \mathcal{H}} \frac{1}{n}   \left|\ell (o_i , h) -  \ell (o^\prime_i , h) \right|  \leq \frac{1}{n} .
 \] De forma similar podemos mostrar que $ g ({\bf o}_n^\prime) - g ({\bf o}_n) \leq 1/n$ e portanto, temos que $\mid  g ({\bf o}_n^\prime) - g ({\bf o}_n) \mid \leq 1/n $. Ao aplicarmos o lema 1, obtemos a existência de um conjunto $G_1 \in \beta(\mathbb{O}^n)$ com $\mathbb{P}^n (G_1) \geq 1 - \delta/2$ tal que 
 \[
\left| \hat{\mathcal{R}}_n ( {\bf o}_n , \mathcal{H} ) -  \mathcal{R}_n ( \mathcal{H} ) \right| \leq \sqrt{\frac{\ln (2/ \delta)}{2n}}, ~ {\bf o}_n \in G_1 ~ ~ (\text{Desigualdade 12}).
 \] Nas desigualdades 10 e 12 tomamos $G$ e $G_1$ com probabilidade de ocorrência maior que $1- \delta/2$. Assim, existe $\hat{G} = G \cap G_1$ satisfazendo 
 \[
 \sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big|   \leq  2 \mathcal{R}_n ( \mathcal{H} )  + \sqrt{\frac{\ln (1/ \delta)}{2n}} = 
 \]
 \[
  2 \left( \mathcal{R}_n ( \mathcal{H} ) -  \hat{\mathcal{R}}_n ({\bf o}_n , \mathcal{H} )  \right) +  2 \hat{\mathcal{R}}_n ({\bf o}_n , \mathcal{H} ) + \sqrt{\frac{\ln (2/ \delta)}{2n}} \leq
 \] 
  \[
  2 \sqrt{\frac{\ln (2/ \delta)}{2n}} +  2 \hat{\mathcal{R}}_n ({\bf o}_n , \mathcal{H} ) + \sqrt{\frac{\ln (2/ \delta)}{2n}} \leq
    2 \hat{\mathcal{R}}_n ({\bf o}_n , \mathcal{H} ) + 3
    \sqrt{\frac{\ln (2/ \delta)}{2n}} .
 \] Segue o teorema.

A desigualdade 11 é um limitante que depende dos dados, pois envolve a complexidade de Rademacher no ponto ${\bf o}_n \in \mathbb{O}^n$. Condicionada aos dados, a complexidade  $\hat{\mathcal{R}}_n ( {\bf o}_n , \mathcal{H} )$ pode ser calculada, por exemplo, por simulação Monte Carlo. A complexidade de Rademacher $\hat{\mathcal{R}}_n ( \cdot , \mathcal{H} )$  depende da função risco relacionado com o problema de classificação binária. Considere a projeção $\mathcal{W} ({\bf o}_n )= \{(\ell (o_1 , h) , \cdots , \ell (o_n , h)) : h \in \mathcal{H}\} \subset [0,1]^n$ da classe de preditores admissíveis com respeito ao conjunto de dados ${\bf o}_n$. Desta forma, dado uma amostra fixa ${\bf o}_n \in \mathbb{O}^n$, podemos tratar a complexidade de Rademacher como uma função sobre a família de subconjuntos do espaço $\{0,1\}^n$. Dado um subconjunto $A \subset [0,1]^n$ com vetores ${\bf a}=(a_1 , \cdots , a_n)$, introduzimos a seguinte quantidade

\[
\hat{\mathcal{R}}_n (A) := \mathbb{E}_{\mu^n} \sup_{{\bf a} \in A} \frac{1}{n} \left| \sum_{i=1}^n \sigma_i a_i \right| =
\]

\[
\mathbb{E}_{\mu^n} \sup_{a \in A} \left\{\frac{1}{n} -  \sum_{i=1}^n \sigma_i a_i 1\!\!1_{ \{\sum_{i=1}^n \sigma_i  <0  \}} +  \frac{1}{n}  \sum_{i=1}^n \sigma_i a_i 1\!\!1_{ \{\sum_{i=1}^n \sigma_i  \geq 0  \}} \right\} =
\] 

\[
\mathbb{E}_{\mu^n} \sup_{a \in A} \left\{\frac{1}{n} \sum_{i=1}^n (-\sigma_i) a_i 1\!\!1_{ \{\sum_{i=1}^n \sigma_i  <0  \}} +  \frac{1}{n}  \sum_{i=1}^n \sigma_i a_i 1\!\!1_{ \{\sum_{i=1}^n \sigma_i  \geq 0  \}} \right\} = 
\]

\[
\mathbb{E}_{\mu^n} \sup_{a \in A} \left\{\frac{1}{n} \sum_{i=1}^n \sigma_i a_i 1\!\!1_{ \{\sum_{i=1}^n \sigma_i  <0  \}} +  \frac{1}{n}  \sum_{i=1}^n \sigma_i a_i 1\!\!1_{ \{\sum_{i=1}^n \sigma_i  \geq 0  \}} \right\} = 
\]

\[
\mathbb{E}_{\mu^n} \sup_{a \in A} \frac{1}{n}  \sum_{i=1}^n \sigma_i a_i, ~ ~ (\text{Desigualdade 13}),
\] pois as variáveis aleatórias $\{\sigma_1, \cdots , \sigma_n\}$ são iid e tem distribuição simétrica. A função $\hat{\mathcal{R}}_n (A)$ corresponde a complexidade de Rademacher relacionada com o conjunto $A$. Por definição temos que $\hat{\mathcal{R}}_n (\mathcal{W} ({\bf o}_n ))=  \hat{\mathcal{R}}_n ({\bf o}_n , \mathcal{H} )$ para todo ${\bf o}_n \in \mathbb{O}^n$. Com isso, a desigualdade 11 pode escrita na forma

\[
 \sup_{h \in \mathcal{H}} \big| L_E ({\bf o}_n , h) - L(\mathbb{P} , h)   \big| \leq  2 \hat{\mathcal{R}}_n (\mathcal{W} ({\bf o}_n ) ) + 3
    \sqrt{\frac{\ln (2/ \delta)}{2n}}, ~ {\bf o}_n \in \hat{G}, ~ ~ (\text{Desigualdade 14}),
 \] com $\mathbb{P}^n(\hat{G}) \geq 1 - \delta$ e $0 < \delta < 1/2$.  A seguir, apresentamos a desigualdade de Massart para a complexidade de Rademacher. 

Teorema 2: Propriedade da Complexidade de Rademacher

Sejam $A$ e $B$ subconjuntos de Borel do espaço $[0,1]^n$. Então, temos que 

•      $\hat{\mathcal{R}}_n (A \cup B) \leq \hat{\mathcal{R}}_n (A ) + \hat{\mathcal{R}}_n ( B)$.
•     A desigualdade de Massart é válida:

    \[
    \hat{\mathcal{R}}_n (A) \leq  r \frac{\sqrt{2 Ln (Card(A))}}{n}, ~ ~ (\text{Desigualdade 15}),
    \] no qual $r^2 = \max_{a \in A} \sum_{i=1}^n a_i $  representa a norma do conjunto $A$ e $Card(A)$ sua respectiva cardinalidade.

• Princípio da contração de Ledoux e Talagrand: Seja $\Phi: \mathbb{R} \rightarrow \mathbb{R}$ uma função Lipschitz com constante $C>0$ (isto é, $\mid \Phi(a) - \Phi(b)\mid \leq C \mid a - b \mid $ para todo $a,b \in \mathbb{R}$). Então, temos que

\[  \hat{\mathcal{R}}_n (\Phi \circ A) \leq C ~  \hat{\mathcal{R}}_n (A) ,\] no qual $\Phi \circ A = \{ (\Phi(a_1) , \cdots , \Phi(a_n)) : (a_1 , \cdots , a_n) \in A \} $. 

Prova: 

A primeira propriedade da complexidade de Rademacher é consequência da desigualdade 4.  Na sequência, vamos derivar a desigualdade 15 a partir da desigualdade de Hoeffding. Seja $Z$ uma variável aleatória com valor esperado nulo e limitada no intervalo $[a,b]$. Então, para todo $s>0$, temos que 

\[
\mathbb{E} \exp (sZ) \leq \exp\left(s^2 \frac{(b-a)^2}{8} \right).
\] Como consequência da desigualdade de Hoeffding e do fato de que as variáveis aleatórias $\{\sigma_1, \cdots , \sigma_n\}$ são iid e tem distribuição simétrica, temos que

\[
 \exp^{s \mathbb{E}_{\sigma} \sup_{a \in A}  \sum_{i=1}^n \sigma_i a_i } \leq \mathbb{E}_{\sigma} \left[ \exp^{\sup_{a \in A}   \sum_{i=1}^n \sigma_i a_i } \right] = 
\mathbb{E}_{\sigma} \sup_{a \in A}  \exp^{   \sum_{i=1}^n \sigma_i a_i } \leq 
\]

\[
\sum_{a \in A} \mathbb{E}_{\sigma} \exp^{   \sum_{i=1}^n \sigma_i a_i } = \sum_{a \in A}  \prod_{i=1}^n \mathbb{E}_{\sigma} \exp^{  \sigma_i a_i } \leq \sum_{a \in A}  \prod_{i=1}^n \exp^{\frac{s^2 a_i}{2}} \leq 
\]

\[
\sum_{a \in A} \exp^{\frac{s^2}{2} \max_{a \in A} \sum_{i=1}^n a_i } = \sum_{a \in A} \exp^{\frac{s^2}{2} r^2 } = Card(A) \exp^{\frac{s^2}{2} r^2 }.
\] Com isso, obtemos que 

\[
\mathbb{E}_{\sigma} \sup_{a \in A}  \sum_{i=1}^n \sigma_i a_i \leq \frac{1}{s} \ln(Card(A)) + \frac{s}{2} r^2.
\] Ao tomarmos $s= \frac{\sqrt{2 \ln (Card(A))}}{r}$ deduzimos a desigualdade de Massart,

\[
\frac{1}{n} \mathbb{E}_{\mu^n} \sup_{a \in A}  \sum_{i=1}^n \sigma_i a_i \leq r \frac{\sqrt{2 \ln (Card(A))}}{n}.
\] 
Na sequência, vamos demonstrar o princípio da contração de Ledoux e Talagrand. A complexidade empírica de Rademacher pode ser escrita na forma 

\[ \hat{\mathcal{R}}_n (\Phi \circ A)  = \mathbb{E}_{\mu^n} \sup_{a \in A} \frac{1}{n}  \sum_{i=1}^n \sigma_i \Phi(a_i) =  \mathbb{E}_{\mu^{n-1}} \mathbb{E}_{\mu}\sup_{a \in A} \left[ \frac{1}{n}  \sum_{i=1}^{n-1} \sigma_i \Phi(a_i) +  \sigma_n \Phi(a_n)  \right]. \]  Assuma que o supremo existe (caso contrario, utilizamos solução $\epsilon$-ótima). Assim, existe $c^\star , d^\star \in A$ tais que 

\[  \frac{1}{n}  \sum_{i=1}^{n-1} \sigma_i \Phi(c_i^\star) +  \Phi(c_n^\star) =  \sup_{a \in A} \left[ \frac{1}{n}  \sum_{i=1}^{n-1} \sigma_i \Phi(a_i) +   \Phi(a_n)  \right] \]  e \[  \frac{1}{n}  \sum_{i=1}^{n-1} \sigma_i \Phi(d_i^\star) -  \Phi(d_n^\star) =  \sup_{a \in A} \left[ \frac{1}{n}  \sum_{i=1}^{n-1} \sigma_i \Phi(a_i) -   \Phi(a_n)  \right] .\] Desde que $\sigma_n$ tem distribuição simétrica no conjunto $\{-1 , 1\}$, concluímos que 

\[  \mathbb{E}_{\mu}\sup_{a \in A} \left[ \frac{1}{n}  \sum_{i=1}^{n-1} \sigma_i \Phi(a_i) +  \sigma_n \Phi(a_n)  \right] = \frac{1}{2} \sup_{a \in A} \left[ \frac{1}{n}  \sum_{i=1}^{n-1} \sigma_i \Phi(a_i) +   \Phi(a_n)  \right] + \frac{1}{2}  \sup_{a \in A} \left[ \frac{1}{n}  \sum_{i=1}^{n-1} \sigma_i \Phi(a_i) -   \Phi(a_n)  \right]  =  \] 

\[ \frac{1}{2} \frac{1}{n}  \sum_{i=1}^{n-1} \sigma_i \Phi(c_i^\star) +  \Phi(c_n^\star) + \frac{1}{2}  \frac{1}{n}  \sum_{i=1}^{n-1} \sigma_i \Phi(d_i^\star) -  \Phi(d_n^\star) = \frac{1}{2n} \left[  \sum_{i=1}^{n-1} \sigma_i \Phi(c_i^\star)  + \sum_{i=1}^{n-1} \sigma_i \Phi(d_i^\star) + \Phi(c_n^\star) -  \Phi(d_n^\star) \right] . \] Na sequência, tomamos $s=sgn(c_n^\star -  d_n^\star )$ no qual $sgn$ representa a função sinal. Com isso, temos que 

\[ \mathbb{E}_{\mu}\sup_{a \in A} \left[ \frac{1}{n}  \sum_{i=1}^{n-1} \sigma_i \Phi(a_i) +  \sigma_n \Phi(a_n)  \right] \leq  \frac{1}{2n} \left[  \sum_{i=1}^{n-1} \sigma_i \Phi(c_i^\star)  + \sum_{i=1}^{n-1} \sigma_i \Phi(d_i^\star) + \mid  \Phi(c_n^\star) -  \Phi(d_n^\star) \mid \right]  \leq \] \[ \frac{1}{2n} \left[  \sum_{i=1}^{n-1} \sigma_i \Phi(c_i^\star)  + \sum_{i=1}^{n-1} \sigma_i \Phi(d_i^\star) + C \mid  c_n^\star -  d_n^\star \mid \right] = \frac{1}{2n} \left[  \sum_{i=1}^{n-1} \sigma_i \Phi(c_i^\star)  + \sum_{i=1}^{n-1} \sigma_i \Phi(d_i^\star) + s C \left( c_n^\star -  d_n^\star \right) \right] =\] \[ \frac{1}{2n} \left[  \sum_{i=1}^{n-1} \sigma_i \Phi(c_i^\star) + s C  c_n^\star \right] + \frac{1}{2n} \left[  \sum_{i=1}^{n-1} \sigma_i \Phi(d_i^\star) - s C  d_n^\star \right] \leq \] \[\frac{1}{n} \left\{ \frac{1}{2} \sup_{a \in A} \left[  \sum_{i=1}^{n-1} \sigma_i \Phi(a_i) + s C  a_n \right]  + \frac{1}{2} \sup_{a \in A} \left[  \sum_{i=1}^{n-1} \sigma_i \Phi(a_i) - s C  a_n \right]\right\} = \] \[ \mathbb{E}_{\mu} \sup_{a \in A} \left[  \sum_{i=1}^{n-1} \sigma_i \Phi(a_i) +  C \sigma_n  a_n \right] ,\] no qual $C$ é a constante de Lipschitz da função $\Phi$. Procedendo da mesma forma para todo $i <m$, obtemos o princípio da contração de Ledoux e Talagrand.

Este resultado é crucial para que possamos conectar a complexidade de Rademacher com  dimensão de Vapnik e Chervonenkis.