{"id":"arxiv/2610.04944","url":"https://arxiv.org/abs/2610.04944","tags":["math.OC","cs.LG"],"score":0,"title":"Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization","domain":"math.OC","source":"arxiv","authors":["Qihao Zhou"],"reviews":0,"subject":"math.OC","summary":"We characterize, up to logarithmic factors, the minimax expected query complexity of finite-sum nonconvex-strongly-concave optimization under mean-squared averaged smoothness. For randomized zero-respecting incremental first-order algorithms, the complexity is $\\tildeΘ(n+\\min\\{\\sqrt{n}\\,κ,n^{3/4}\\sqrtκ\\}\\,LΔ\\varepsilon^{-2})$ throughout $κ=L/μ\\ge1$, under exact dual initialization and for $0 0$ is universal. This characterization is our main result. A dual-chain construction provides the lower bound and matches the existing Catalyst upper bound for $κ\\ge\\sqrt{n}$. For $1\\leκ\\le\\sqrt{n}$, we…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-04","reactions":{}}