Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.35206
curl -X POST /api/v1/records/arxiv/2609.35206/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.35206/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'