{"id":"arxiv/2609.30877","url":"https://arxiv.org/abs/2609.30877","tags":["math.OC","cs.LG"],"score":0,"title":"Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization","domain":"math.OC","source":"arxiv","authors":["Qihao Zhou"],"reviews":0,"subject":"math.OC","summary":"We study whether the linear condition-number dependence in the stochastic complexity of SAPD+ is necessary for nonconvex-strongly-concave minimax optimization. For jointly $L$-smooth objectives with dual strong-concavity parameter $μ$, we prove a lower bound that matches the SAPD+ upper bound under the same Moreau-envelope stationarity criterion and the same primal-dual initialization gap. Specifically, when $σ\\ge\\varepsilon$, the worst-case complexity of zero-respecting algorithms is $Θ(κLGσ^2\\varepsilon^{-4})$ in the stated accuracy regime, where $κ=L/μ$, $G$ bounds the initial primal-dual…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{}}