Article · IA & agents
La géométrie du domaine peut changer la vitesse d’un optimiseur
Un résultat théorique relie optimisation convexe non duale, max-regret et dimension de fat-shattering séquentielle.
Le problème n’est pas seulement la fonction
David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán et Mathieu Molina étudient l’optimisation convexe en accès boîte noire : l’algorithme ne voit qu’une valeur et un sous-gradient à chaque requête. La particularité est géométrique : le domaine est une boule en norme ℓp, tandis que la régularité de l’objectif est mesurée en norme ℓq. Ces normes ne sont pas forcément duales.
Un résultat en 1 sur T
Dans le cas convexe lipschitzien euclidien sur la boule ℓ1, les auteurs obtiennent une vitesse en Õ(1/T), à comparer au O(1/√T) classique sous des hypothèses générales. Plus généralement, leurs bornes pour les couples (p,q) approchent les bornes inférieures à des facteurs logarithmiques près. Le cœur technique est un jeu d’apprentissage en ligne où le comparateur regarde le maximum des pertes précédentes : le « max-regret ».
Pourquoi cela intéresse les agents
Un agent qui choisit des requêtes, des outils ou des hyperparamètres peut exploiter une géométrie de recherche plus fine que la simple moyenne des pertes. La dimension de fat-shattering séquentielle fournit ici un langage pour relier la richesse des trajectoires observables à la complexité d’optimisation. C’est une boussole théorique, pas une recette de planification prête à l’emploi.
Interprétation éditoriale : mesurer la bonne notion de regret
Réduire tout problème à un regret additif peut masquer une structure utile des requêtes. Avant de comparer deux boucles d’optimisation, il faut donc demander si le domaine, la norme de Lipschitz et la forme des pertes correspondent réellement au scénario de production.
Limites et statut de la source
Le résultat est mathématique et repose sur des hypothèses précises de convexité, de géométrie et d’accès à un oracle. La stratégie qui atteint les bornes via programmation dynamique peut avoir un temps d’exécution exponentiel en la dimension et en T ; les auteurs laissent l’algorithme simultanément optimal et polynomial pour des travaux futurs. Il ne s’agit pas d’une mesure de performance d’un agent logiciel.
Source
David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán et Mathieu Molina, « The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings », ArXiv 2609.20687v1 : résumé et preprint, PDF.