A first-order method for nonconvex-strongly-concave constrained minimax optimization

Abstract

In this paper we study a nonconvex-strongly-concave constrained minimax problem. Specifically, we propose a first-order augmented Lagrangian method for solving it, whose subproblems are nonconvex-strongly-concave unconstrained minimax problems and suitably solved by a first-order method developed in this paper that leverages the strong concavity structure. Under suitable assumptions, the proposed method achieves an operation complexity of $O({\epsilon }^{-3.5}\log {\epsilon }^{-1})$, measured in terms of its fundamental operations, for finding an $\epsilon$-KKT solution of the constrained minimax problem, which improves the previous best-known operation complexity by a factor of ${\epsilon }^{-0.5}$.

Accepted by Optimization Methods and Software