Complexité de Rademacher

Étant donné des observations ${\displaystyle S=(z_{1},z_{2},\dots ,z_{m})\in Z^{m}}$, et une classe ${\displaystyle {\mathcal {H}}}$ de fonctions à valeurs réelles définies sur un espace ${\displaystyle Z}$, la complexité empirique de Rademacher de ${\displaystyle {\mathcal {H}}}$ est définie comme :

${\displaystyle {\widehat {\mathcal {R}}}_{S}({\mathcal {H}})={\frac {2}{m}}\mathbb {E} \left[\sup _{h\in {\mathcal {H}}}\left|\sum _{i=1}^{m}\sigma _{i}h(z_{i})\right|\ {\bigg |}\ S\right]}$

où ${\displaystyle \sigma _{1},\sigma _{2},\dots ,\sigma _{m}}$ sont des variables aléatoires indépendantes, tirées selon la loi de Rademacher i.e. ${\displaystyle \mathbb {P} (\sigma _{i}=+1)=\mathbb {P} (\sigma _{i}=-1)=1/2}$ pour ${\displaystyle i=1,2,\dots ,m}$.

Soit ${\displaystyle P}$, la distribution de probabilité sur ${\displaystyle Z}$. La complexité de Rademacher de la classe de fonction ${\displaystyle {\mathcal {H}}}$ selon ${\displaystyle P}$ pour des données de taille ${\displaystyle m}$ est :

${\displaystyle {\mathcal {R}}_{m}({\mathcal {H}})=\mathbb {E} \left[{\widehat {\mathcal {R}}}_{S}({\mathcal {H}})\right]}$

où les espérances, ci-dessus, sont calculées selon des observations indépendantes et identiquement distribuées (i.i.d.) ${\displaystyle S=(z_{1},z_{2},\dots ,z_{m})}$ générées selon ${\displaystyle P}$.