{"ID":2824632,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.22909","arxiv_id":"2512.22909","title":"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(\\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}$.","short_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 lev...","url_abs":"https://arxiv.org/abs/2512.22909","url_pdf":"https://arxiv.org/pdf/2512.22909v2","authors":"[\"Zhaosong Lu\",\"Sanyou Mei\"]","published":"2025-12-28T12:31:56Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.LG\",\"math.NA\",\"stat.ML\"]","methods":"[]","has_code":false}