Adaptive extra-gradient methods for min-max optimization and games - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Adaptive extra-gradient methods for min-max optimization and games

Résumé

We present a new family of min-max optimization algorithms that automatically exploit the geometry of the gradient data observed at earlier iterations to perform more informative extra-gradient steps in later ones. Thanks to this adaptation mechanism, the proposed method automatically detects whether the problem is smooth or not, without requiring any prior tuning by the optimizer. As a result, the algorithm simultaneously achieves order-optimal convergence rates, i.e., it converges to an ε-optimal solution within O(1/ε) iterations in smooth problems, and within O(1/ε 2) iterations in non-smooth ones.Importantly, these guarantees do not require any of the standard boundedness or Lipschitz continuity conditions that are typically assumed in the literature; in particular, they apply even to problems with singularities (such as resource allocation problems and the like). This adaptation is achieved through the use of a geometric apparatus based on Finsler metrics and a suitably chosen mirror-prox template that allows us to derive sharp convergence rates for the methods at hand.
Fichier principal
Vignette du fichier
2021-ICLR-AdaProx.pdf (1.21 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03342601 , version 1 (13-09-2021)

Identifiants

  • HAL Id : hal-03342601 , version 1

Citer

Kimon Antonakopoulos, Veronica E Belmega, Panayotis Mertikopoulos. Adaptive extra-gradient methods for min-max optimization and games. ICLR 2021 - 9th International Conference on Learning Representations, May 2021, Virtual, Unknown Region. pp.1-28. ⟨hal-03342601⟩
88 Consultations
107 Téléchargements

Partager

Gmail Facebook X LinkedIn More