  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$.
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}(\epsilon^{-2})$ and it is the first step-size search
method for NCSC minimax problems that require only $\mathcal{O}(1)$ calls to
$\nabla f$ per backtracking iteration. The numerical experiments demonstrate
its robustness and efficiency.
