{"id":"arxiv/2609.35206","url":"https://arxiv.org/abs/2609.35206","tags":["math.OC"],"score":0,"title":"Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization","domain":"math.OC","source":"arxiv","authors":["Siqi Zhang","Qilong Wu","Junchi Yang"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}