Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
This provides foundational complexity limits for a class of min-max optimization problems relevant to machine learning and game theory, though it is incremental as it refines existing bounds.
The paper tackles the problem of finding stationary points in min-max optimization with nonconvex-strongly-concave objectives, establishing a lower bound of Ω(√κε⁻²) for deterministic oracles and Ω(√κε⁻² + κ¹ᐟ³ε⁻⁴) for stochastic oracles, showing optimality of prior upper bounds in some cases and a gap in others.
We provide a first-order oracle complexity lower bound for finding stationary points of min-max optimization problems where the objective function is smooth, nonconvex in the minimization variable, and strongly concave in the maximization variable. We establish a lower bound of $Ω\left(\sqrtκε^{-2}\right)$ for deterministic oracles, where $ε$ defines the level of approximate stationarity and $κ$ is the condition number. Our analysis shows that the upper bound achieved in (Lin et al., 2020b) is optimal in the $ε$ and $κ$ dependence up to logarithmic factors. For stochastic oracles, we provide a lower bound of $Ω\left(\sqrtκε^{-2} + κ^{1/3}ε^{-4}\right)$. It suggests that there is a significant gap between the upper bound $\mathcal{O}(κ^3 ε^{-4})$ in (Lin et al., 2020a) and our lower bound in the condition number dependence.