# Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization

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

## Key facts

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

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

- [Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization](https://mlsanity.com/paper/2610.01662/) (2026)

## Abstract (arXiv)

We study the deterministic first-order oracle complexity of smooth nonconvex-concave minimax optimization over a bounded convex dual domain. Let ℓ denote the joint smoothness constant, DY the diameter of the dual domain, and Delta the initial gap. We prove that every deterministic first-order algorithm requires Omega(ℓ2DYDelta/ε3) oracle queries in the worst case to find an ε-optimization-stationary point whenever εlesssimminℓ DY,√ℓDelta. We then develop Tracked-FOAM, a first-order method that attains a matching upper bound, removing the logarithmic factor from previous upper bounds. Together, these results establish the optimal dependence on all problem parameters in the stated regime.