Article · IA & agents
Stable Movement : des pas fiables en optimisation convexe
Une étude théorique analyse des méthodes d'optimisation pour des fonctions convexes lipschitziennes non duales et leurs taux d'oracle.
Pourquoi la stabilité compte
Dans l'optimisation en boîte noire, chaque appel à l'oracle coûte cher. Une méthode doit progresser avec peu d'informations tout en évitant des déplacements qui amplifient le bruit ou rendent l'analyse impossible.
Le cadre théorique
Le preprint étudie la minimisation d’une fonction convexe G-Lipschitz sur une boule ℓp de rayon R, avec une régularité mesurée dans une norme ℓq différente. Le régime non dual traité est p < q. Après T requêtes d’un oracle du premier ordre, les auteurs obtiennent une erreur en Õp,q(GR/T1/p−(1/q−1/2)+) ; pour p = 1 et q = 2, elle devient Õ(GR/T), là où les méthodes efficaces précédentes restaient typiquement à l’échelle de 1/√T dans les géométries les plus favorables.
L’algorithme transforme l’optimisation en un problème de chasing d’ensembles convexes emboîtés : les coupes de l’oracle rétrécissent un modèle inférieur et un centre stable doit bouger peu dans la norme de mesure. Une moyenne de Monte-Carlo du sélecteur fournit l’algorithme annoncé en temps polynomial dans le modèle d’arithmétique réelle. La contribution vise en particulier le régime de haute dimension et de faible horizon T ≤ d, où des taux informationnels proches étaient auparavant réalisables en temps exponentiel plutôt qu’avec une méthode efficace.
Lecture pratique
La contribution est principalement théorique : elle ferme l’extrémité non lisse d’un problème ouvert formulé à COLT 2015 et aide à comparer des garanties de convergence et les hypothèses nécessaires, mais ne fournit pas automatiquement un réglage universel pour un modèle d'apprentissage.
Limites et source
Les garanties suivent les hypothèses mathématiques du papier, de l’oracle du premier ordre, des normes ℓp/ℓq et de l’arithmétique réelle ; elles comportent des facteurs logarithmiques et ne doivent pas être transposées à un problème non convexe sans nouvelle démonstration. La randomisation et l’implémentation Monte-Carlo ne constituent pas non plus une mesure de robustesse pour une bibliothèque numérique. Il s'agit d'un preprint ArXiv.
Source
David Martínez-Rubio et Cristóbal Guzmán, « Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates », ArXiv 2609.20701v1 : résumé et preprint, PDF.