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 (NCSC) minimax problems of the form $(P):{\min }_{x\in \mathcal{X}}{\max }_{y\in \mathcal{Y}}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$ and the concavity modulus $\hat{I}¼$. 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 $\mathcal{O}(\hat{I}{\mu }^{-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.

In this version, the AGDA+ algorithm does not require the concavity modulus be given as an input. The gradient complexity bound is provided for this version of AGDA+ that is agnostic to both the Lipschitz constant and the concavity modulus