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):minx∈X maxy∈Yg(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 and the concavity modulus μ. 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 3 calls to nabla f on average per backtracking iteration. The numerical experiments demonstrate its robustness and efficiency.