Résumé Technique : Optimisation Convexe en Ligne à Capacité Contrainte avec Rétroaction Différée

1. Énoncé du Problème

Cet article traite de l'Optimisation Convexe en Ligne (OCO) et de l'Optimisation Convexe de Type Bandit (BCO) sous deux contraintes simultanées : une rétroaction différée et une capacité de suivi limitée.

Dans l'apprentissage en ligne différé standard, un apprenant choisit une action $x_t$ au tour $t$, subissant une perte $f_t(x_t)$, mais ne reçoit la rétroaction (gradient ou perte scalaire) qu'au tour $t + d_t$. La littérature traditionnelle suppose que l'apprenant possède une capacité illimitée pour suivre tous les tours en attente jusqu'à ce que leur rétroaction arrive. Cependant, dans des scénarios pratiques (par exemple, des essais cliniques avec des ressources de surveillance limitées), l'apprenant ne peut suivre qu'un nombre borné de tours en attente, noté capacité $C$. Si un tour n'est pas suivi, sa rétroaction est définitivement perdue.

L'article formalise cela comme un jeu où :

• L'adversaire fixe les pertes convexes $f_t$ et les délais $d_t$.
• Le joueur maintient un ensemble de suivi $S$ de taille au plus $C$.
• À chaque tour, le joueur peut préempter (abandonner) des tours suivis ou ajouter le tour actuel à $S$.
• La rétroaction pour le tour $s$ est observée à $s + d_s$ si et seulement si $s \in S$ à ce moment-là.
• L'objectif est de minimiser le regret $R_T = \sum_{t=1}^T (f_t(x_t) - f_t(x^*))$ par rapport à la meilleure action fixe $x^*$ a posteriori.

L'article considère deux modèles d'information concernant les délais :

1. Clairvoyant : Les délais $d_t$ sont connus au moment de la prédiction.
2. Semi-Clairvoyant : Les délais ne sont révélés qu'à l'expiration (à $t+d_t$), ce qui est cohérent avec les cadres d'apprentissage différé standard.

2. Méthodologie

Les auteurs proposent une approche basée sur la réduction qui décompose le problème à capacité contrainte en deux composantes : un ordonnanceur (scheduler) et un apprenant de base (base learner).

2.1 Le Cadre de Réduction

L'idée centrale est de réduire le problème à capacité contrainte à un nouveau problème d'OCO « différé et pondéré ».

• Ordonnanceur : Un algorithme enveloppe gère l'ensemble de suivi $S$. Il utilise un mécanisme de planification par délai proxy. Pour chaque tour $t$, l'ordonnanceur échantillonne un « délai proxy » $d'_t$ à partir d'une distribution $D_t$. Le tour $t$ est ajouté à $S$ si $d'_t \ge 0$ et si la capacité le permet. Il est retiré de $S$ à $t + d'_t + 1$ si la rétroaction n'est pas encore arrivée.
• Pondération par Importance : Si la rétroaction pour le tour $s$ est observée (c'est-à-dire $s \in S$ et $d'_s \ge d_s$), l'enveloppe transmet la rétroaction au apprenant de base avec un poids d'importance $w_s = 1 / P(d'_s \ge d_s)$. Si la rétroaction est perdue (en raison de la saturation de la capacité ou d'un timeout proxy précoce), le poids est fixé à 0.
• Apprenant de Base : L'apprenant reçoit un flux de rétroactions différées et pondérées. L'article introduit des algorithmes spécifiquement conçus pour gérer ce flux différé et pondéré.

2.2 Algorithmes de Base : DW-FTRL (Delayed-Weighted FTRL)

L'article présente et analyse deux algorithmes de base pour le cadre différé et pondéré :

1. DW-FTRL (Delayed-Weighted Follow-the-Regularized-Leader) : Pour la rétroaction de premier ordre (gradient). Il met à jour l'itération en minimisant un objectif régularisé qui agrège les gradients pondérés de tous les tours observés.
2. DW-FTBL (Delayed-Weighted Follow-the-Bandit-Leader) : Pour la rétroaction de type bandit (perte scalaire). Il utilise l'estimateur de gradient à point unique standard (en perturbant le point central) mais l'applique au flux de rétroaction différé et pondéré.

L'analyse théorique de ces algorithmes de base établit des bornes de regret qui tiennent explicitement compte de l'interaction entre les poids variables dans le temps et l'arrière-plan (backlog) des observations en attente. Une conclusion clé est que le regret dépend des interactions par paires de poids pour les tours ayant des délais chevauchants.

2.3 Ordonnanceurs de Délai Proxy

Pour garantir que la réduction fonctionne, l'ordonnanceur doit équilibrer deux objectifs contradictoires : couvrir les délais réels (pour observer la rétroaction) et éviter la saturation de la capacité. L'article propose deux ordonnanceurs spécifiques :

1. Ordonnanceur de Pareto : S'adapte aux délais individuels $d_t$. Il échantillonne des délais proxy à partir d'une distribution de Pareto décalée, rendant la probabilité de suivi inversement proportionnelle au délai. Cela est adapté aux pertes convexes générales.
2. Ordonnanceur de Bernoulli : Calibré sur le backlog maximal $\sigma_{max}$ (le nombre maximal d'observations en attente à n'importe quel moment). Il échantillonne un délai proxy de $\infty$ avec une probabilité $p \approx C / \sigma_{max}$ et de $-1$ autrement. Cela produit des poids d'importance uniformes, une propriété cruciale pour obtenir des bornes serrées dans les contextes fortement convexes et de type bandit.

3. Contributions Clés

1. Premières Garanties de Regret pour l'OCO/BCO à Capacité Contrainte : L'article fournit les premières bornes de regret sous-linéaires pour l'apprentissage en ligne à capacité contrainte avec rétroaction différée, tant dans les domaines convexes que fortement convexes, pour les rétroactions de premier ordre et de type bandit.
2. Cadre OCO « Différé et Pondéré » : Il introduit un nouveau cadre de problème (rétroaction différée et pondérée) et analyse les variantes de FTRL pour celui-ci. Ce cadre est d'un intérêt indépendant pour l'apprentissage en ligne sans échelle (scale-free) sous délais.
3. Ordonnancement de Délai Proxy Unifié : Les auteurs unifient les idées d'ordonnancement précédentes et introduisent un nouvel ordonnanceur (Bernoulli) qui produit des poids uniformes, permettant des garanties plus fortes pour les contextes fortement convexes et de type bandit.
4. Gestion des Paramètres Inconnus : Le cadre accepte le modèle semi-clairvoyant (délais inconnus au moment de la prédiction) et utilise la technique du doublement (doubling trick) pour gérer un $\sigma_{max}$ inconnu sans connaissance préalable.

4. Résultats Principaux

Les bornes de regret dépendent de l'horizon $T$, de la dimension $k$, du délai total $d_{tot}$, du backlog maximal $\sigma_{max}$ et de la capacité $C$.

4.1 Rétroaction de Premier Ordre (OCO)

• Pertes Convexes : Avec une capacité $C = \Omega(\log T)$, le regret correspond au taux optimal non contraint à un facteur logarithmique près :
  $$\tilde{O}\left( G D \sqrt{d_{tot} + T} \right)$$
• Pertes Fortement Convexes : Le regret est :
  $$\tilde{O}\left( \frac{G^2}{\lambda} (\sigma_{max} + 1) \log T \right)$$
  Cela correspond à la dépendance optimale vis-à-vis de $\sigma_{max}$ trouvée dans les contextes non contraints.

4.2 Rétroaction de Type Bandit (BCO)

Pour la rétroaction de type bandit, la contrainte de capacité intervient dans les termes dépendant de la dimension via des facteurs de $(1 + \sigma_{max}/C)$.

• Pertes Convexes :
  $$\tilde{O}\left( GD \left( \sqrt{T \sigma_{max}} + T^{3/4} \left(1 + \frac{\sigma_{max}}{C}\right)^{1/4} \sqrt{\nu k} \right) \right)$$
  où $\nu$ est le ratio d'échelle des valeurs de fonction par rapport aux gradients. La borne se dégrade progressivement à mesure que $C$ diminue.
• Pertes Fortement Convexes :
  $$\tilde{O}\left( \frac{G^2}{\lambda} \left( \sigma_{max} \log T + (T^2 \log T)^{1/3} \left(1 + \frac{\sigma_{max}}{C}\right)^{1/3} (\nu k)^{2/3} \right) \right)$$

Observation Clé : Lorsque $C \ge \sigma_{max}$, les bornes retrouvent les taux non contraints. Lorsque $C < \sigma_{max}$, le regret augmente mais reste sous-linéaire. La dépendance vis-à-vis de $\sigma_{max}$ (concurrence de pointe) est montrée comme étant plus naturelle que la dépendance vis-à-vis de $d_{max}$ (délai maximal) dans les systèmes de type file d'attente.

5. Signification et Revendications

L'article affirme être le premier à dériver des garanties de regret pour l'OCO et le BCO à capacité contrainte. Sa signification réside dans :

• Pont entre Théorie et Pratique : Il aborde la contrainte réaliste que les ressources de suivi sont finies, une limitation ignorée par la majeure partie de la littérature précédente sur l'apprentissage différé qui suppose une capacité infinie.
• Affinement du Modèle de Délai : En adoptant un modèle semi-clairvoyant (délais révélés uniquement à l'expiration), ce travail s'aligne plus étroitement sur l'apprentissage en ligne standard et la planification de tâches en ligne que les précédents modèles « clairvoyants ».
• Dégradation Gracieuse : Les résultats démontent qu'une capacité logarithmique ($C = \Omega(\log T)$) est suffisante pour retrouver les taux différés standards pour la rétroaction de premier ordre, tandis que pour la rétroaction de type bandit, la performance se dégrade gracieusement lorsque la capacité tombe en dessous du backlog de pointe.
• Nouveauté Théorique : L'introduction du problème OCO « différé et pondéré » et l'analyse spécifique de l'interaction entre les poids et les délais dans FTRL fournissent de nouveaux outils pour analyser l'apprentissage en ligne sous contraintes de ressources.

Les auteurs notent que bien que leurs bornes pour le bandit convexe dépendent de $\sqrt{T \sigma_{max}}$ plutôt que du $\sqrt{d_{tot}}$ optimal du cadre non contraint, elles améliorent néanmoins les bornes précédentes dépendant de $\sqrt{T d_{max}}$. Ils identifient la fermeture de cet écart comme un problème ouvert. De plus, ils suggèrent que la similitude structurelle entre leur modèle et les systèmes de files d'attente à tampon fini mérite une exploration plus approfondie.