Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization

@misc{zhang2026tight,
  title = {{Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization}},
  author = {Siqi Zhang and Qilong Wu and Junchi Yang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.35206},
  eprint = {2609.35206},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.35206},
}

TY  - UNPB
TI  - Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization
AU  - Siqi Zhang
AU  - Qilong Wu
AU  - Junchi Yang
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.35206
UR  - https://arxiv.org/abs/2609.35206
AB  - 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/2L̅Δσε^−3) under the additional assumption of averaged smoothness. Here, L and L̅ denote the smoothness and averaged-smoothness constants, respectively, Δ is the initial primal gap, σ^2 bounds the oracle variance, and κ=L/μ or 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.
ER  -