The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
It addresses computational efficiency for researchers in optimization and machine learning, though it is incremental as it builds on existing gradient-based methods to close known gaps.
This paper tackles the complexity of finding approximate stationary points in nonconvex-strongly-concave minimax optimization, establishing lower bounds of Ω(√κΔLε⁻²) and Ω(n+√nκΔLε⁻²) for general and finite-sum settings, and introduces an acceleration scheme that nearly matches these bounds, removing poly-logarithmic dependencies.
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 $Ω(\sqrtκΔLε^{-2})$ and $Ω(n+\sqrt{nκ}ΔLε^{-2})$ for the two settings, respectively, where $κ$ is the condition number, $L$ is the smoothness constant, and $Δ$ 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.