AGDA+: Proximal Alternating Gradient Descent Ascent Method With a Nonmonotone Adaptive Step-Size Search For Nonconvex Minimax Problems

We consider double-regularized nonconvex-strongly concave (NCSC) minimax problems of the form (P): ₗ ₘg (x) +f (x, y) -h (y), where g, h are closed convex, f is L-smooth in (x, y) and strongly concave in y. We propose a proximal alternating gradient descent ascent method AGDA+ that can adaptively choose nonmonotone primal-dual stepsizes to compute an approximate stationary point for (P) without requiring the knowledge of the global Lipschitz constant L. Using a nonmonotone step-size search (backtracking) scheme, AGDA+ stands out by its ability to exploit the local Lipschitz structure and eliminates the need for precise tuning of hyper-parameters. AGDA+ achieves the optimal iteration complexity of O (^-2) and it is the first step-size search method for NCSC minimax problems that require only O (1) calls to f per backtracking iteration. The numerical experiments demonstrate its robustness and efficiency.