Escaping limit cycles: Global convergence for nonmonotone inclusions and constrained nonconvex-nonconcave minimax problems
In this work we present a general projective framework for solving nonmonotone inclusions. Specializing the framework to nonconvex-nonconcave minimax problems, we introduce 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. Finally, we show how our framework can be employed to provide provably convergent versions of Douglas-Rachford splitting for structured nonmonotone inclusions.
Large part of the work has been published at ICLR 2022 and is the result of a collaboration with Puya Latafat (KU Leuven), Thomas Pethick, Volkan Cevher (EPFL) and Oliver Fercoq (Télécom Paris).