提出新方法求解非凸-强凹约束极小极大问题，效率提升显著。
A first-order method for nonconvex-strongly-concave constrained minimax optimization
- 基于增广拉格朗日法，结合一阶算法处理子问题的强凹结构。
- 达到 $O(c^{-3.5} \log c^{-1})$ 的运算复杂度，优于此前最优结果。
- 适合需要高效求解此类极小极大问题的研究者或工程师。
本文研究非凸-强凹约束极小极大问题。提出一种一阶增广拉格朗日方法，其子问题为无约束的非凸-强凹极小极大问题，通过本文设计的一阶算法求解，充分利用强凹结构。在合理假设下，该方法以基本运算次数衡量，实现 $O(c^{-3.5} \log c^{-1})$ 的操作复杂度，获得 $c$-KKT 解，相较此前最优复杂度提升 $\u0005c^{-0.5}$ 倍。
原文摘要 · Abstract (English)
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}$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。