# Lower Bounds for Nonconvex-PL Minimax Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Aug 2026.

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

- [Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2609.30877/) (2026)
- [Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games](https://mlsanity.com/paper/2610.07814/) (2026)

## Abstract (arXiv)

We study the deterministic first-order oracle complexity of finding stationary points of the value function in smooth nonconvex-Polyak-Lojasiewicz (NC-PL) minimax optimization. We assume that the objective is jointly ℓ-smooth and satisfies the μ-PL condition in the dual variable, and that its value function Phi(x):=maxy f(x;y) satisfies Phi(0)-infxPhi(x)≤Delta. When kappa:=ℓ/μgtrsim 1 and 0<ε2lesssimℓDelta, we prove that every deterministic first-order method requires Omega(ℓDeltakappa/ε2) oracle queries in the worst case to find x satisfying |nablaPhi(x)|≤ε. This rate matches the known upper bound in its dependence on (ℓ,Delta,kappa,ε) [Yang et al., 2022] and shows that the linear dependence on kappa is unavoidable for deterministic first-order methods.