Résumé technique : Adaptativité sous contraintes de réalisabilité

Énoncé du problème

Ce papier examine les limites théoriques de l'apprentissage en contexte (ICL) par rapport à l'apprentissage agentique dans le cadre de l'approximation uniforme pour des familles de fonctions. La question centrale est : Dans quelles conditions une interaction séquentielle et adaptative avec une tâche offre-t-elle un avantage réel par rapport à des requêtes fixes et prédéfinies, et comment cet avantage évolue-t-il lorsque le mécanisme d'apprentissage est contraint par la réalisabilité (spécifiquement, une implémentation via des réseaux de neurones ReLU de taille bornée) ?

Les auteurs formalisent deux axes de comparaison :

1. Stratégie de requête : Requêtes fixes (En contexte) vs Requêtes adaptatives (Agentique).
2. Contrainte représentative : Fonctions générales (sans restriction) vs Fonctions réalisables par ReLU (implémentées par des réseaux ReLU de taille bornée).

Cela donne quatre régimes distincts :

• ICG : Apprentissage en contexte général.
• AG : Apprentissage agentique général.
• ICR : Apprentissage en contexte réalisable par ReLU.
• AR : Apprentissage agentique réalisable par ReLU.

L'objectif est de caractériser la puissance d'approximation de ces régimes les uns par rapport aux autres, sous des budgets d'échantillons et de calcul égaux.

Méthodologie

Les auteurs adoptent un cadre d'approximation uniforme sur un domaine compact $X \subseteq \mathbb{R}^d$. Ils définissent une famille de tâches $\mathcal{T}$ et mesurent la performance via l'erreur uniforme du pire cas (norme $L_\infty$).

Définitions

• Apprenant en contexte ($\Psi_{IC}$) : Utilise un ensemble fixe de $N$ points de requête $x_1, \dots, x_N$ et un prédicteur qui mappe le contexte $C_N = \{(x_i, f(x_i))\}$ et une nouvelle entrée $x$ vers une prédiction.
• Apprenant agentique ($\Psi_{A}$) : Sélectionne les points de requête de manière séquentielle. La $n$-ième requête $x_n$ est déterminée par une application $q_n$ basée sur le contexte précédent $C_{n-1}$.
• Réalisabilité : Un apprenant est « réalisable » si ses applications de requête et son prédicteur final sont implémentés par des réseaux de neurones ReLU avec un nombre borné de poids ($m$).

Métrique de comparaison

Le papier définit une relation $R_1 \leq R_2$ si, pour toute famille de tâches et tout budget, l'erreur du pire cas du régime $R_2$ n'est pas supérieure à celle du régime $R_1$. Une inégalité stricte ($R_1 < R_2$) indique un avantage strict.

Les auteurs établissent la monotonie de base :
$$ICG \leq AG \quad \text{et} \quad ICR \leq AR$$
Cela est vrai car un agent peut toujours choisir d'ignorer l'adaptativité et imiter une stratégie de requête fixe. La contribution principale réside dans l'identification des moments où ces inégalités sont strictes et de la manière dont la réalisabilité les modifie.

Contributions et résultats clés

Le papier isole quatre scénarios d'approximation distincts, chacun démontré par une famille de tâches explicite et construite. Ces scénarios révèlent que l'interaction entre l'adaptativité et les contraintes représentatives n'est pas triviale.

1. L'adaptativité révèle plus d'informations (l'avantage survit à la réalisabilité)

• Famille de tâches : Tâches de chemin cubique ($\mathcal{T}^{path}_{d,L}$). Les tâches sont définies par une séquence imbriquée de cubes dyadiques.
• Mécanisme : Un agent adaptatif peut effectuer une recherche binaire (en 1D) ou une recherche généralisée pour identifier le chemin caché de cubes niveau par niveau.
• Résultat :
  • Général : $ICG < AG$. Les requêtes fixes manquent des informations que les requêtes adaptatives peuvent découvrir séquentiellement.
  • Réalisable : $ICR < AR$. La stratégie adaptative (interroger les centres des cubes enfants et utiliser les résidus) peut être implémentée exactement par des réseaux ReLU.
• Implication : Dans ce scénario, l'avantage informationnel de l'adaptativité est robuste face aux contraintes des réseaux ReLU.

2. La réalisabilité génère un avantage adaptatif

• Famille de tâches : Famille de valeurs ponctuelles ($\mathcal{T}^{val}_{N,m}$). Les tâches consistent en des « chapeaux » fixes à des emplacements connus portant des coefficients, et un « chapeau mobile » à un emplacement $q^*$ portant une valeur $g_m(s)$, où $g_m$ est une fonction difficile à approximer.
• Mécanisme :
  • Général : $ICG = AG$. Les apprenants fixes et adaptatifs peuvent tous deux lire l'emplacement $q^*$ depuis le contexte, puis calculer $g_m(s)$ (puisque ils sont sans restriction).
  • Réalisable : $ICR < AR$. Un apprenant en contexte ReLU doit approximer en interne la application difficile $s \mapsto g_m(s)$, ce qui est impossible avec des poids bornés. Cependant, un agent ReLU peut interroger la valeur $g_m(s)$ directement à l'emplacement $q^*$ (qu'il a déterminé de manière adaptative), contournant ainsi le besoin de calcul interne.
• Implication : Les contraintes de réalisabilité peuvent créer un scénario où l'adaptativité est strictement supérieure, même lorsqu'elle n'offre aucun avantage dans le cadre sans restriction.

3. L'avantage adaptatif éliminé par la réalisabilité

• Famille de tâches : Famille de pics d'adresse ($\mathcal{T}^{addr}_{N,m}$). Similaire à la famille de valeurs ponctuelles, mais l'emplacement du chapeau mobile $q^*(s)$ est déterminé par une fonction difficile à approximer $g_m(s)$. Le bit caché $\beta$ est situé à $q^*(s)$.
• Mécanisme :
  • Général : $ICG < AG$. Un agent sans restriction peut calculer $q^*(s)$ à partir des coefficients statiques et interroger le bit caché.
  • Réalisable : $ICR = AR$. Pour trouver le point de requête informatif $q^*(s)$, l'agent doit approximer l'application difficile $s \mapsto q^*(s)$. Puisque les applications de requête de l'agent sont également contraintes d'être des réseaux ReLU à poids bornés, il ne peut pas calculer l'emplacement mieux que l'apprenant en contexte. Le « calcul difficile » requis pour déterminer où interroger annule le bénéfice de l'adaptativité.
• Implication : Les contraintes représentatives peuvent éliminer l'avantage de l'adaptativité qui existe dans le cadre général.

4. Aucun avantage

• Scénario : Pour des familles de tâches à singleton ou des cas triviaux spécifiques, l'adaptativité n'apporte aucune amélioration ($ICG = AG$ et $ICR = AR$).

Importance et affirmations

Le papier prétend fournir une classification conceptuelle de la manière dont l'adaptativité interagit avec les contraintes architecturales. L'importance principale réside dans la démonstration que :

1. L'adaptativité n'est pas universellement supérieure : Son bénéfice dépend de la structure spécifique de la famille de tâches et des capacités computationnelles de l'apprenant.
2. La réalisabilité est une variable critique : La transition d'un cadre sans restriction vers un cadre réalisable par ReLU ne fait pas qu'échelonner la performance ; elle modifie qualitativement la relation entre l'apprentissage en contexte et l'apprentissage agentique.
   • Les avantages peuvent survivre (Chemin cubique).
   • Les avantages peuvent émerger (Valeur ponctuelle).
   • Les avantages peuvent disparaître (Pic d'adresse).

Les auteurs soulignent que ces résultats sont dérivés de la théorie de l'approximation uniforme du pire cas, isolant les phénomènes fondamentaux de l'acquisition d'informations et de la capacité représentative sans s'appuyer sur des hypothèses statistiques ou des modèles de bruit. Ils notent en outre que leurs résultats s'étendent aux architectures Transformer via une conversion canonique à partir de MLP ReLU, suggérant que ces limitations théoriques s'appliquent également aux modèles de langage modernes de grande taille.

Ce travail étend les résultats classiques sur l'approximation non adaptative par des MLP, affirmant que la structure de l'acquisition d'informations (adaptativité) joue un rôle central, aux côtés de la complexité de la classe de fonctions, dans la détermination des limites de l'apprentissage.