This paper studies the complexity for finding approximate stationary points of nonconvex-strongly-concave (NC-SC) smooth minimax problems, in both general and averaged smooth finite-sum settings. We establish nontrivial lower complexity bounds of $\Omega(\sqrt{\kappa}\Delta L\epsilon^{-2})$ and $\Omega(n+\sqrt{n\kappa}\Delta L\epsilon^{-2})$ for the two settings, respectively, where $\kappa$ is the condition number, $L$ is the smoothness constant, and $\Delta$ is the initial gap. Our result reveals substantial gaps between these limits and best-known upper bounds in the literature. To close these gaps, we introduce a generic acceleration scheme that deploys existing gradient-based methods to solve a sequence of crafted strongly-convex-strongly-concave subproblems. In the general setting, the complexity of our proposed algorithm nearly matches the lower bound; in particular, it removes an additional poly-logarithmic dependence on accuracy present in previous works. In the averaged smooth finite-sum setting, our proposed algorithm improves over previous algorithms by providing a nearly-tight dependence on the condition number.

本文研究非凸强凹（NC-SC）平滑极小值问题的近似稳定点的复杂度，在一般和平均平滑有限和设置中建立了非平凡的较低复杂度下界。我们提出了一种通用的加速方案，使用现有的基于梯度的方法来解决一系列的精心制作的强凸-强凹子问题，进而缩小了复杂度差距，尤其是在一般情况下，我们提出的算法的复杂度几乎与下界相当。

非凸强凹极小-极大优化的复杂性