# Lower Bounds for Nonconvex-Concave Minimax Optimization

arXiv: https://arxiv.org/abs/2609.14233 · HTML: https://mlsanity.com/paper/2609.14233/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Sep 2026.

## Built on by (most cited first, 3 of 3)

- [Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2609.30877/) (2026)
- [Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization](https://mlsanity.com/paper/2610.01662/) (2026)
- [Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2610.04944/) (2026)

## Abstract (arXiv)

We study lower bounds on the first-order oracle complexity of smooth nonconvex-concave minimax optimization. We consider objectives f that are jointly L-smooth in the primal and dual variables (x,y), concave in y, and whose primal value function Phi(x) := maxy∈mathcal Y f(x,y) satisfies the initial-gap condition Phi(0)-infx∈mathcal XPhi(x)≤ Delta_Phi, with a bounded dual domain satisfying operatornamediam(mathcal Y)≤ Dmathcal Y. We measure stationarity by the norm of the gradient of the Moreau envelope of Phi+iotamathcal X with parameter 1/(2L). We prove that any deterministic zero-respecting first-order algorithm requires Omegaleft(L2Dmathcal YDelta_Phiε-3right) oracle evaluations to find an ε-stationary point. Under an unbiased stochastic first-order oracle with bounded variance, any stochastic zero-respecting algorithm requires Omegaleft(L3Dmathcal Y2Delta_Phiε-6right) oracle evaluations. The same lower bounds hold when Delta_Phi is replaced by the initial primal-dual gap mathcal G0. These deterministic and stochastic lower bounds match the corresponding upper bounds of [14] and [29], respectively, up to a logarithmic factor in the deterministic setting.