Résumé technique : Régression en ligne réalisable et applications pour les réseaux ReLU

Énoncé du problème

Cet article étudie la régression en ligne réalisable dans le cadre adversaire, où aucune hypothèse stochastique ou de marge n'est imposée. Le problème central est de déterminer quand la réalisabilité (l'existence d'une hypothèse cible $h^* \in \mathcal{H}$ générant parfaitement les étiquettes) implique une borne de perte cumulative sans horizon (finie), et d'identifier les paramètres de complexité qui régissent cette borne.

Les auteurs contrastent cela avec la classification en ligne, où même des classes simples comme les Perceptrons peuvent présenter des bornes d'erreur infinies sans hypothèses de marge. En régression, cependant, la réalisabilité peut imposer une perte totale finie sous des pertes de type métrique, même lorsque le problème de classification analogue est apprenable. L'étude se concentre sur des fonctions de perte $\ell$ qui satisfont une inégalité triangulaire approximative (pseudo-métriques approximatives), une condition nécessaire pour éviter les scénarios dégénérés où un apprenant peut prédire des étiquettes intermédiaires avec une perte négligeable malgré des écarts importants dans l'espace des hypothèses.

Méthodologie

Le papier introduit une méthode de potentiel générique pour borner supérieurement la dimension de Littlestone mise à l'échelle ($D_{\text{onl}}$), une dimension abstraite introduite par Attias et al. [2] qui caractérise la perte cumulative réalisable minimax.

Le cadre du potentiel d'entropie

Au lieu de calculer directement $D_{\text{onl}}$, ce qui peut être difficile, les auteurs la borment supérieurement en utilisant un intégrale d'entropie de type Dudley basée sur les nombres de recouvrement de la classe d'hypothèses $\mathcal{H}$ sous la pseudo-métrique de sup normée induite $d_\ell(f, g) = \sup_{x} \ell(f(x), g(x))$.

1. Définition du potentiel d'entropie : Pour une classe d'hypothèses $\mathcal{H}$ de diamètre fini, le potentiel d'entropie est défini par :
   $$\Phi(\mathcal{H}) = \int_{0}^{\text{diam}(\mathcal{H})} \log_2 N(\mathcal{H}, \varepsilon) \, d\varepsilon$$
   où $N(\mathcal{H}, \varepsilon)$ est le nombre de recouvrement en $\varepsilon$ de $\mathcal{H}$ par rapport à $d_\ell$.

2. Théorème principal : Les auteurs prouvent que pour toute perte de pseudo-métrique $c$-approximative, la dimension de Littlestone mise à l'échelle est bornée par le potentiel d'entropie :
   $$D_{\text{onl}}(\mathcal{H}) \leq 4c \cdot \Phi(\mathcal{H})$$
   La preuve utilise un argument de branchement de bornes (branch bound) sur les arbres de Littlestone mis à l'échelle réalisables. En analysant les espaces de versions à chaque nœud, ils montrent que l'inégalité triangulaire approximative force tout recouvrement en $\varepsilon$ à se diviser entre les enfants d'un nœud avec un écart $\gamma$ lorsque $\varepsilon < \gamma/(2c)$. L'intégration de cette « division de recouvrement » à travers les échelles produit une chute de potentiel proportionnelle à l'écart, bornant l'écart total le long de toute branche par $\Phi(\mathcal{H})$.

3. Implication : Si $\mathcal{H}$ possède des nombres de recouvrement polynomiaux (c'est-à-dire $N(\mathcal{H}, \varepsilon) \leq (A/\varepsilon)^p$), alors $\Phi(\mathcal{H}) < \infty$, impliquant une borne de perte cumulative réalisable sans horizon.

Contributions clés et résultats

1. Régression Lipschitzienne sous perte $\ell_q$

Les auteurs appliquent leur cadre à la classe $\mathcal{H}_L$ des fonctions $L$-Lipschitziennes sur $[-1, 1]^d$ sous la perte $\ell_q(y, y') = |y - y'|^q$. Ils établissent une transition de phase nette basée sur la relation entre $q$ et la dimension $d$ :

• Régime apprenable ($q > d$) : Le potentiel d'entropie est fini. La perte cumulative réalisable minimax est $\Theta_{d,q}(L^d)$. Les auteurs fournissent un algorithme propre déterministe efficace basé sur des enveloppes Lipschitziennes (bornes inférieures et supérieures) qui atteint cette borne.
• Régime non apprenable ($q \leq d$) : Le potentiel d'entropie diverge.
  • Si $q < d$, la perte cumulative minimax croît polynomialement avec l'horizon $T$.
  • Si $q = d$, la perte croît logarithmiquement avec $T$.
  • Dans les deux cas, $D_{\text{onl}}(\mathcal{H}_L) = \infty$.
• Apprentissage éventuel : Pour toute perte continue $\ell$ telle que $\ell(y,y)=0$, les auteurs montrent que pour les fonctions $L$-Lipschitziennes, la perte instantanée $\ell(\hat{y}_t, y_t)$ converge vers 0 quand $t \to \infty$, indépendamment du fait que la perte cumulative totale soit finie ou non.

2. Réseaux ReLU bornés $k$-ReLU

Le papier étudie la classe $\mathcal{H}_{k,d}$ des réseaux $k$-ReLU bornés (sommes de $k$ ReLU avec des poids bornés) sur $[-1, 1]^d$ avec la perte au carré.

• Séparation Régression vs Classification :
  • Classification : Sous la perte 0/1, la classification en ligne réalisable est impossible pour $\mathcal{H}_{2,1}$ (deux neurones cachés, entrée 1D), car la dimension de Littlestone est infinie même avec des poids bornés.
  • Régression : Sous la perte au carré, la régression en ligne réalisable admet une perte totale finie.
• Bornes supérieures :
  • Il existe un algorithme en ligne (informationnel) avec une perte cumulative $O(k^2 \log^4 d) = \tilde{O}(k^2)$.
  • Pour un seul ReLU ($k=1$), il existe un algorithme efficace avec une perte cumulative $O(1)$, indépendante de la dimension $d$.
• Bornes inférieures :
  • Une borne inférieure de $\Omega(k^2 \log(d/k^2))$ est prouvée, montant que la dépendance envers $k$ et $\log d$ est nécessaire.
• Complexité computationnelle :
  • En supposant l'hypothèse Gap-ETH, les auteurs excluent l'existence d'un apprenant en ligne propre et efficace pour $k \geq 2$ qui atteigne une perte accumulée $e^{o(d)}$ en temps polynomial en $d$. Cela suggère que bien qu'une perte finie soit informationnellement possible, la calculer efficacement pour des apprenants propres est probablement difficile.

3. Généralisation aux réseaux profonds

Les résultats sont étendus aux réseaux de profondeur $L$ et de largeur $k$. La perte au carré cumulative minimax réalisable est montrée être $\tilde{O}(k^L)$, avec une borne inférieure correspondante de $\Omega(k^L \log(d/k^L))$ quand $d/k^L \to \infty$.

Signification et affirmations

Le papier affirme que la réalisabilité modifie fondamentalement le paysage de l'apprentissage en ligne par rapport au cadre agnostique. Plus précisément :

1. L'entropie métrique comme mesure de complexité : Les auteurs établissent que pour la régression réalisable sous des pseudo-métriques approximatives, l'entropie métrique (via le potentiel d'entropie $\Phi$) est un substitut suffisant et souvent serré pour la dimension en ligne $D_{\text{onl}}$. Cela fournit un outil concret et calculable pour analyser l'apprenabilité là où les dimensions abstraites sont intraitables.
2. Transitions de phase dans la régression non paramétrique : Le travail identifie les conditions précises ($q > d$) sous lesquelles la régression Lipschitzienne non paramétrique est sans horizon, contrastant nettement avec l'impossibilité de la classification ou de la régression avec $q \leq d$.
3. Apprentissage des réseaux de neurones : Le papier met en évidence une séparation marquée entre la classification et la régression pour les réseaux ReLU. Bien que les réseaux ReLU bornés soient impossibles à apprendre dans le cadre de la classification (dimension de Littlestone infinie), ils admettent une perte cumulative finie dans le cadre de la régression. Cependant, cet apprentissage comporte des réserves : pour $k \geq 2$, atteindre cette perte efficacement via des apprenants propres est probablement complexe sur le plan computationnel.
4. Limites : Les auteurs notent que la borne du potentiel d'entropie n'est pas toujours serrée ; il existe des classes où $\Phi(\mathcal{H}) = \infty$ mais $D_{\text{onl}}(\mathcal{H}) < \infty$. Ainsi, $\Phi$ sert de substitut de borne supérieure explicite plutôt que de caractérisation complète dans tous les cas.

Le travail s'appuie sur les avancées récentes de la théorie de la dimension en ligne [2] et adapte les techniques des processus stochastiques (intégrales de Dudley) au cadre en ligne adversaire, évitant le chaînage séquentiel au profit de recouvrements standards en raison de l'hypothèse de réalisabilité.