Complexité Rademacher de la composition avec un indicateur

Question

Considérez le paramètre d'apprentissage statistique où vous avez un espace d'hypothèses arbitraires $\mathcal{H}$, un espace de données $\mathcal{Z}$, et une fonction de perte bornée $\ell: \mathcal{H}\times \mathcal{Z} \rightarrow [0,1]$. De plus, pour$c\in(0,1)$, laisser $\mathcal{F}_c$ être la classe de fonctions définie par \begin{align} \mathcal{F}_c := \{ z \mapsto \mathbb{I}\{\ell(h,z) \leq c\}: h \in \mathcal{H}\}. \end{align} Question. Est-il possible de relier de quelque manière que ce soit la complexité Rademacher de la classe de fonctions$\mathcal{F}_c$, pour lequel $\ell \circ \mathcal{H}:= \{z\mapsto \ell(h,z): h \in \mathcal{H}\}$? Mon objectif est de montrer que lorsque la complexité de la seconde classe est faible, la complexité de la première l'est également.

Complexité Rademacher. La complexité Rademacher d'une classe de fonctions$\mathcal{F}$ est défini comme \begin{align} \mathfrak{R}_n(\mathcal{F}) := \mathbb{E}\left[\sup_{f\in \mathcal{F}}\frac{1}{n} \sum_{i=1}^n \sigma_i f(z_i)\right], \quad n \in \mathbb{N}, \end{align} où $(\sigma_i,z_i)$ sont des variables aléatoires iid avec $(\sigma_i)$ ayant une distribution Rademacher.

Tentative échouée. Il y a des résultats sur la complexité Rademacher de la composition des fonctions, mais ceux-ci reposent généralement sur certaines propriétés de Lipschitzness, qui ne sont pas valables pour notre classe de fonctions$\mathcal{F}_c$ puisque nous composons avec une fonction d'indicateur.

Answer 1

En général, composer une fonction de seuil avec une classe de fonctions peut augmenter arbitrairement la complexité de Rademacher (la réponse à votre question est donc négative). Laisser$\Omega$ être un ensemble fini, $|\Omega|=N$, et laissez $F=[-a,a]^\Omega$ être l'ensemble de toutes les fonctions de $\Omega$ à $[-a,a]$. Quand$N\gg n$, la complexité de Rademacher (empirique ou attendue) de $F$ sera $\Theta(a)$. Laisser$F'$ être $F$composé avec la fonction de signe; maintenant$F'=\{-1,1\}^\Omega$ et sa complexité Rademacher dans ce régime est $\Theta(1)$. Depuis$a>0$ peut être pris arbitrairement petit, cela montre que l'écart multiplicatif peut être arbitrairement grand.