Abstract: In the paper, we study a class of nonconvex nonconcave minimax optimization problems (i.e., minxmaxyf(x,y)), where f(x,y) is possible nonconvex in x, and it is nonconcave and satisfies the Polyak-Lojasiewicz (PL) condition in y. Moreover, we propose a class of enhanced momentum-based gradient descent ascent methods (i.e., MSGDA and AdaMSGDA) to solve these stochastic Nonconvex-PL minimax problems. In particular, our AdaMSGDA algorithm can use various adaptive learning rates in updating the variables x and y without relying on any global and coordinate-wise adaptive learning rates. Theoretically, we present an effective convergence analysis framework for our methods. Specifically, we prove that our MSGDA and AdaMSGDA methods have the best known sample (gradient) complexity of O(ε 3) only requiring one sample at each loop in finding an ε-stationary solution (i.e., E F(x) ε, where F(x) maxyf(x,y)).

Abstract: In this paper we study a class of constrained minimax problems. In particular, we propose a first-order augmented Lagrangian method for solving them, whose subproblems turn out to be a much simpler structured minimax problem and are suitably solved by a first-order method recently developed in [26] by the authors. Abstract: Nonconvex-nonconcave minimax optimization has been the focus of intense research over the last decade due to its broad applications in machine learning and operation research. Unfortunately, most existing algorithms cannot be guaranteed to converge and always suffer from limit cycles. Their global convergence relies on certain conditions that are difficult to check, including but not limited to the global Polyak-Łojasiewicz condition, the existence of a solution satisfying the weak Minty variational inequality and α-interaction dominant condition.