Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This work establishes tight stochastic first-order lower bounds for finding $\epsilon$-stationary primal points in smooth nonconvex-strongly-concave minimax optimization under both bounded-variance and averaged-smoothness regimes. The authors improve the condition-number dependence from $\kappa^{1/3}$ to $\kappa$ to yield an optimal $\Omega(\kappa L\Delta\sigma^2\epsilon^{-4})$ bound, while proving the first lower bound of $\Omega(\kappa^{3/2}\bar{L}\Delta\sigma\epsilon^{-3})$ under averaged smoothness. These results exactly match known upper bounds in both $\kappa$ and $\epsilon$, completely closing the theoretical complexity gap for this class of problems.
Stochastic nonconvex-strongly-concave minimax optimization is officially closed: new $\Omega(\kappa \epsilon^{-4})$ and $\Omega(\kappa^{3/2}\epsilon^{-3})$ lower bounds prove that standard first-order algorithms have already hit the fundamental limits of sample complexity.
We study the stochastic first-order oracle complexity of finding $ε$-stationary points of the primal function in smooth nonconvex-strongly-concave minimax optimization. For sufficiently small $ε$, we establish lower bounds of $Ω(κLΔσ^2ε^{-4})$ under the bounded-variance assumption and $Ω(κ^{3/2}\bar LΔσε^{-3})$ under the additional assumption of averaged smoothness. Here, $L$ and $\bar L$ denote the smoothness and averaged-smoothness constants, respectively, $Δ$ is the initial primal gap, $σ^2$ bounds the oracle variance, and $κ=L/μ$ or $\bar L/μ$ in the respective settings, where $μ$ is the strong-concavity parameter. Our bounded-variance lower bound improves the dependence on the condition number from $κ^{1/3}$ in previous lower bounds to $κ$, while our averaged-smoothness lower bound is the first of its kind. In both settings, the resulting lower bounds match existing upper bounds in their dependence on $κ$ and $ε$. Our proofs are based on a unified quadratic lifting construction that transfers a hardness instance for stochastic nonconvex minimization to unconstrained minimax optimization while preserving the required variance and smoothness properties.