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

A first-order method for nonconvex-strongly-concave constrained minimax optimization Zhaosong Lu Sanyou Mei May 12, 2024 (Revised: October 23, 2025) 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(ε 3.5 log ε 1), measured in terms of its fundamental operations, for finding an ε-KKT solution of the constrained minimax problem, which improves the previous best-known operation complexity by a factor of ε 0.5 . Keywords: minimax optimization, augmented Lagrangian method, first-order method, operation complexity Mathematics Subject Classification: 90C26, 90C30, 90C47, 90C99, 65K05 1 Introduction In this paper, we consider a nonconvex-strongly-concave constrained minimax problem F = min c(x) 0 max d(x,y) 0 {F (x,y):= f (x, y) + p(x) q(y)}. Assume that problem (1) has at least one optimal solution and the following additional assumptions hold.