A first-order method for nonconvex-strongly-concave constrained minimax optimization
This work addresses constrained minimax optimization, a problem relevant for machine learning and game theory, but it is incremental as it builds on existing methods with a specific complexity improvement.
The paper tackles the problem of nonconvex-strongly-concave constrained minimax optimization by proposing a first-order augmented Lagrangian method, achieving an operation complexity of O(ε^{-3.5} log ε^{-1}) for finding an ε-KKT solution, which improves the previous best by a factor of ε^{-0.5}.
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(\varepsilon^{-3.5}\log\varepsilon^{-1})$, measured in terms of its fundamental operations, for finding an $\varepsilon$-KKT solution of the constrained minimax problem, which improves the previous best-known operation complexity by a factor of $\varepsilon^{-0.5}$.