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

Abstract.

We consider double-regularized nonconvex–strongly concave minimax problems of the form [Formula: see text], where [Formula: see text] are closed convex and [Formula: see text] is [Formula: see text]-smooth in [Formula: see text] and [Formula: see text]-strongly concave in [Formula: see text]. We propose a proximal alternating gradient descent ascent method AGDA+, which can adaptively choose nonmonotone primal-dual step sizes to compute an approximate stationary point for [Formula: see text] without requiring the knowledge of the global Lipschitz constant [Formula: see text] and the concavity modulus [Formula: see text]. Using a nonmonotone step-size search (backtracking) scheme, AGDA+ stands out for its ability to exploit the local Lipschitz structure and eliminates the need for precise tuning of hyperparameters. AGDA+ achieves the optimal iteration complexity of [Formula: see text], and it is the first step-size search method for nonconvex–strongly concave minimax problems that require only [Formula: see text] calls to [Formula: see text] per backtracking iteration. The numerical experiments demonstrate its robustness and efficiency.