En 20 ans, l'optimisation convexe en ligne est passée de la théorie à Adam et aux LLM

Il y a vingt ans, l'online convex optimization (OCO) était encore un domaine jeune, à la croisée de l'informatique théorique, du machine learning et de l'optimisation. Aujourd'hui, son vocabulaire (regret, mises à jour adaptatives, décisions séquentielles sans connaissance de l'avenir) est ancré dans la manière dont on entraîne les modèles modernes. Le média chinois Jiqizhixin a consacré un long article à ce parcours, sous un titre ironique : l'homme qui a passé sa vie à étudier le « regret » affirme n'avoir aucun regret.

Dans le fragment dont nous disposons, le texte s'interrompt au milieu d'une énumération de méthodes (Online Newton Step, puis la suite manque) et le nom du protagoniste n'est pas indiqué. Nous nous appuyons donc ci-dessous sur l'histoire publique du domaine, et non sur les détails de l'entretien lui-même.

Que mesure le regret

Dans un problème d'optimisation classique, la fonction de perte est connue d'avance. En OCO, c'est tout autre chose. À chaque étape, l'algorithme choisit un point, et ce n'est qu'ensuite que l'environnement révèle une fonction de perte convexe. On mesure la qualité par le regret : la somme des pertes de l'algorithme moins la somme des pertes de la meilleure solution fixe, celle qu'on aurait pu choisir a posteriori.

La grande réussite du domaine est d'avoir rendu le regret sous-linéaire. Les pertes moyennes de l'algorithme tendent alors vers celles du meilleur choix constant, et ce sans aucune hypothèse statistique sur les données. Le travail fondateur de Martin Zinkevich, en 2003, a montré que la descente de gradient en ligne donne un regret de l'ordre de √T sur des fonctions convexes lipschitziennes. Ce résultat a servi de point de départ.

De l'Online Newton Step aux optimiseurs adaptatifs

Vers 2006, Elad Hazan, Amit Agarwal et Satyen Kale ont proposé l'algorithme Online Newton Step. Pour les fonctions dites exp-concaves, il offre un regret de l'ordre de log T, nettement meilleur que √T. L'idée consiste à exploiter l'information de second ordre : le pas s'ajuste à la géométrie des gradients accumulés.

Cette lignée a ensuite donné des méthodes familières à quiconque a déjà lancé un entraînement :

• AdaGrad (Duchi, Hazan, Singer, 2011) : une échelle de pas distincte pour chaque paramètre. Il fonctionne bien sur les caractéristiques creuses.
• RMSProp et Adam (2014) : les descendants pratiques de la même idée, avec une moyenne exponentielle des gradients.
• L'analyse du regret comme standard de preuve : la justification initiale de la convergence d'Adam s'inscrivait précisément dans le cadre de l'OCO.

Un épisode est particulièrement révélateur. En 2018, l'article « On the Convergence of Adam and Beyond » (Reddi et coauteurs, ICLR) a montré que la preuve initiale pour Adam contenait une erreur, et que la méthode pouvait ne pas converger sur certains problèmes convexes. Le correctif, AMSGrad, est lui aussi formulé dans le langage du regret. La théorie ne s'est pas contentée de décrire la pratique : elle l'a prise en défaut.

Pourquoi cela compte aujourd'hui

Les grands modèles de langage sont généralement entraînés avec des variantes d'Adam, le plus souvent AdamW. Le problème y est non convexe, et les garanties de l'OCO ne s'y transposent pas directement. Mais l'intuition, elle, se transpose : pas adaptatifs, préconditionnement, prise en compte de la courbure. Les recherches actuelles sur les optimiseurs à préconditionneurs matriciels prolongent cette même lignée, où l'adaptation diagonale d'AdaGrad cède la place à une structure plus riche.

Une autre branche relève de l'apprentissage en ligne à l'état pur. La minimisation du regret sous-tend des algorithmes pour les jeux, les systèmes de recommandation, la tarification dynamique et l'allocation de ressources. Dans ces problèmes, l'avenir est réellement inconnu, et les données ne sont pas tenues d'être indépendantes.

Que retenir en pratique

Si vous entraînez ou affinez des modèles, il est utile de savoir d'où viennent les hyperparamètres de l'optimiseur. L'epsilon, les coefficients bêta et le calendrier du pas ne sont pas arbitraires : ils ont un sens théorique. Cela aide à déboguer un entraînement instable : la divergence tient souvent au fait que la moyenne adaptative « oublie » des gradients rares mais importants, exactement dans l'esprit du contre-exemple à Adam.

Pour ceux qui construisent des systèmes à décisions séquentielles (recommandation, enchères publicitaires, routage de requêtes entre modèles), l'OCO fournit un cadre prêt à l'emploi. Il permet de comparer des algorithmes à une référence honnête et d'obtenir des garanties sans hypothèse sur la distribution. Pour entrer dans le sujet, le manuel de Hazan, « Introduction to Online Convex Optimization », est un bon point de départ. L'entretien complet sur le site de Jiqizhixin mérite d'être lu dans sa version originale : derrière le titre sur le « zéro regret », il contient, à en juger par l'annonce, l'histoire personnelle de vingt ans de développement de la méthode.