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):minₓ maxyg(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(ε⁻²) 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.