Article · IA & agents
Un extragradient minimax sans boucle interne
Une méthode amortie à boucle unique atteint l'ordre optimal en nombre de gradients pour des problèmes fortement convexe-concaves à couplage non linéaire.
Éviter les solveurs imbriqués
Les problèmes minimax fortement convexes-concaves apparaissent dans l'apprentissage adversarial et la régression régularisée. Les méthodes accélérées peuvent atteindre de bons taux au prix de sous-problèmes internes, de calendriers de précision ou de redémarrages. Minhao Zhang et Zi Xu cherchent une séquence d'updates explicites et fixe.
Une variable de feedback
La méthode conserve trois variables : le point primal, le point dual et une variable auxiliaire. Chaque itération prédit un point, corrige les deux gradients, puis met à jour le feedback avec le gradient au point corrigé. Après une requête d'initialisation, une itération demande exactement deux gradients complets.
Le feedback contrôle le résidu introduit par la discrétisation explicite. Une fonction de Lyapunov absorbe ce résidu et fournit une contraction du dernier itéré, sans moyenne des itérés ni boucle de résolution interne.
La complexité rapportée
Pour une précision relative epsilon en distance quadratique au point selle, le nombre de gradients est de l'ordre de O~(sqrt(kappa_x kappa_y) log(2 kappa_x kappa_y / epsilon)). L'ordre en nombre de conditionnement atteint la borne inférieure connue à des facteurs logarithmiques près. Les expériences couvrent une régression linéaire régularisée et un modèle logistique non linéaire sur Arcene ; dans le cas de courbure très déséquilibrée r = 10000, la méthode atteint 10^-6 en 2 675 requêtes dans le tableau rapporté.
Limites et statut de la source
La garantie suppose un problème déterministe, lisse, non contraint et fortement convexe-concave. Elle ne couvre pas directement les contraintes, le bruit stochastique, la non-lissité ou les problèmes non convexes. Le document est un preprint ArXiv.
Sources
Minhao Zhang et Zi Xu, « Near-Optimal Pure Single-Loop Extragradient Method for Strongly Convex–Strongly Concave Minimax Optimization », ArXiv 2609.20327v1 : résumé et preprint, PDF.