Which Spaces can be Embedded in $L_p$-type Reproducing Kernel Banach Space? A Characterization via Metric Entropy

Résumé Technique : « Quels espaces peuvent être incorporés dans un espace de Reproducing Kernel Banach de type $\mathcal{L}_p$ ? Une caractérisation via l'entropie métrique »

Énoncé du Problème
Le papier traite d'une question fondamentale des fondements théoriques de l'apprentissage automatique : déterminer la portée et les limites des espaces de Banach à noyau reproduisant (RKBS), spécifiquement les RKBS de type $\mathcal{L}_p$, en tant que cadre de modélisation pour des classes de fonctions apprenables. Bien que les RKBS offrent un cadre flexible pour caractériser des estimateurs complexes (tels que les réseaux de neurones) et offrent des avantages par rapport aux espaces de Hilbert (par exemple, la parcimonie via les normes $\ell_p$), il reste incertain si les RKBS de type $\mathcal{L}_p$ sont suffisamment généraux pour incorporer des classes de fonctions arbitraires qui sont apprenables efficacement.

La littérature existante établit que l'incorporation d'un espace de fonctions dans un espace de Reproducing Kernel Hilbert (RKHS) implique une borne spécifique sur la croissance de son entropie métrique. Cependant, la converse — si une borne sur la croissance de l'entropie métrique implique l'incorporation dans un type spécifique d'espace de Banach — n'a pas été pleinement caractérisée pour un $p$ général. Les auteurs cherchent à répondre à la question suivante : Chaque classe de fonctions apprenable avec un nombre polynomial de points de données (par rapport à l'excès de risque) peut-elle être incorporée dans un RKBS de type $\mathcal{L}_p$ ?

Méthodologie
Les auteurs établissent une connexion novatrice entre l'entropie métrique et l'incorporation des espaces de fonctions dans les RKBS de type $\mathcal{L}_p$. La méthodologie procède par les étapes logiques suivantes :

1. De l'entropie métrique à la complexité de Rademacher : Les auteurs généralisent les résultats classiques (Lemme de Massart et Théorème de chaînage de Dudley) à des espaces de Banach abstraits. Ils démontrent que si l'entropie métrique d'une boule unité dans un espace de Banach $E$ (mesurée dans un espace cible $F = \ell_\infty(\Omega)$) croît polynomialement comme $\mathcal{E}_E^F(\delta) \leq \delta^{-p}$ pour $p \geq 2$, alors la complexité de Rademacher de l'espace décroît à un taux de $n^{-1/p}$.
2. De la complexité de Rademacher au Type de l'espace de Banach : Une contribution technique clé est un nouveau lemme montrant qu'une borne sur la norme de Rademacher implique le Type de l'espace de Banach. Plus précisément, si la complexité de Rademacher décroît selon $n^{-1/p'}$, l'espace (équipé de la norme cible) est de Type $s'$ pour tout $s' < p'$.
3. De l'indice de Type à l'incorporation de type $\mathcal{L}_p$ : En s'appuyant sur le Théorème 3 (un corollaire du théorème de domination de Pietsch et du théorème de Maurey-Pisier), les auteurs utilisent la propriété de Type établie pour construire une incorporation isomorphe de l'espace d'hypothèses dans un sous-espace fermé de $\mathcal{L}_{s'}(\mu)$.
4. Construction du RKBS : En utilisant le théorème d'extension de Hahn-Banach et la dualité entre $\mathcal{L}_{s'}$ et $\mathcal{L}_s$ (où $1/s + 1/s' = 1$), ils construisent une application de caractéristique $\Phi: \Omega \to \mathcal{L}_s(\mu)$. Cette application de caractéristique induit un RKBS de type $\mathcal{L}_s$ tel que l'espace $E$ d'origine s'incorpore dans $\mathcal{B}_s$, lequel s'incorpore à son tour dans l'espace des fonctions bornées $\ell_\infty(\Omega)$.

Contributions Clés

• Caractérisation Converse : Le papier prouve une converse aux résultats classiques des RKHS. Alors que l'incorporation dans un RKHS implique une borne sur l'entropie métrique, les auteurs prouvent qu'une borne polynomiale sur la croissance de l'entropie métrique ($\delta^{-p}$) est suffisante pour garantir l'incorporation dans un RKBS de type $\mathcal{L}_s$ pour un certain $s > p$.
• Cadre Unifié via l'Entropie Métrique : Contrairement aux approches précédentes qui reposent sur des propriétés géométriques spécifiques (comme les vérifications de Type-2) qui varient selon les espaces de fonctions, ce travail fournit une approche unifiée basée sur l'entropie métrique pour déterminer l'incorporabilité.
• Lien entre Apprenabilité et Géométrie : Les auteurs connectent le concept d'« apprenabilité polynomiale » (apprendre avec un ensemble de données polynomialement grand par rapport à l'erreur) directement à la structure géométrique des RKBS de type $\mathcal{L}_p$. Ils montrent que toute classe de fonctions apprenable dans ce régime possède les bornes d'entropie métrique nécessaires pour être incorporée dans de tels espaces.

Résultats Principaux

• Théorème 4 : Étant donné un domaine borné $\Omega \subset \mathbb{R}^d$ et un RKBS $E$ qui s'incorpore de manière compacte dans $F = \ell_\infty(\Omega)$, si la croissance de l'entropie métrique est bornée par $\mathcal{E}_E^F(\delta) \leq \delta^{-p}$ pour $p \geq 2$, alors pour tout $s > p$, il existe un RKBS de type $\mathcal{L}_s$ tel que $E \hookrightarrow \mathcal{B}_s \hookrightarrow F$.
• Implication pour l'Apprenabilité : Puisque l'apprenabilité polynomiale implique des bornes polynomiales sur l'entropie métrique, le résultat confirme que les RKBS de type $\mathcal{L}_p$ constituent une classe de modèles puissante et expressive capable de représenter toute classe de fonctions apprenable efficacement.
• Bornes Techniques : Le papier fournit des bornes explicites reliant l'exposant d'entropie $p$ au paramètre $s$ du RKBS requis, montrant que $s$ peut être choisi arbitrairement proche de $p$ (spécifiquement $s > p$).

Signification et Revendications
Les auteurs affirment que leurs résultats apportent un nouvel éclairage sur la puissance et les limites des méthodes à noyau pour l'apprentissage d'espaces de fonctions complexes. En établissant que les RKBS de type $\mathcal{L}_p$ sont suffisamment généraux pour modéliser toute classe de fonctions avec une entropie métrique contrôlée (polynomiale), ce papier valide l'utilisation de ces espaces comme un cadre théorique large pour l'apprentissage automatique.

La signification réside dans la praticité de la caractérisation : estimer l'entropie métrique est souvent plus direct en pratique (par exemple, pour les espaces de Sobolev et de Besov classiques) que de trouver des incorporations explicites. Par conséquent, ce travail fournit une condition vérifiable pour déterminer si un espace de fonctions spécifique peut être modélisé efficacement à l'aide de RKBS de type $\mathcal{L}_p$. Les auteurs soulignent que cette approche unifie l'étude des propriétés des espaces de fonctions, de la théorie de l'apprentissage et des incorporations dans des contextes non-hilbertiens, offrant un cadre plus polyvalent que les caractérisations antérieures basées sur le Type-2.