Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems

Abstract : This paper introduces a new extragradient-type algorithm for a class of nonconvex-nonconcave minimax problems. It is well-known that finding a local solution for general minimax problems is computationally intractable. This observation has recently motivated the study of structures sufficient for convergence of first order methods in the more general setting of variational inequalities when the so-called weak Minty variational inequality (MVI) holds. This problem class captures non-trivial structures as we demonstrate with examples, for which a large family of existing algorithms provably converge to limit cycles. Our results require a less restrictive parameter range in the weak MVI compared to what is previously known, thus extending the applicability of our scheme. The proposed algorithm is applicable to constrained and regularized problems, and involves an adaptive stepsize allowing for potentially larger stepsizes. Our scheme also converges globally even in settings where the underlying operator exhibits limit cycles. Moreover, a variant with stochastic oracles is proposed-making it directly relevant for training of generative adversarial networks. For the stochastic algorithm only one of the stepsizes is required to be diminishing while the other may remain constant, making it interesting even in the monotone setting.
Document type :
Conference papers
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03602455
Contributor : Olivier Fercoq Connect in order to contact the contributor
Submitted on : Wednesday, March 9, 2022 - 10:32:30 AM
Last modification on : Tuesday, June 21, 2022 - 3:39:07 AM

File

escaping_limit_cycles_global_c...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03602455, version 1

Citation

Thomas Pethick, Panagiotis Patrinos, Olivier Fercoq, Volkan Cevherå, Puya Latafat. Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems. International Conference on Learning Representations, 2022, online, France. ⟨hal-03602455v1⟩

Share

Metrics

Record views

2541

Files downloads

19575