# Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 19 references that are in the map.
- First posted on arXiv 1 Oct 2026.

## Builds on (most cited first, 15 of 15)

- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [On the Complexity of First-Order Methods in Stochastic Bilevel Optimization](https://mlsanity.com/paper/2402.07101/) (2024)
- [Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles](https://mlsanity.com/paper/2511.19656/) (2025)
- [Lower Bounds for Nonconvex-Concave Minimax Optimization](https://mlsanity.com/paper/2609.14233/) (2026)
- [Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization](https://mlsanity.com/paper/2609.14235/) (2026)
- [Single-Loop Stochastic Projected Damped Extragradient Methods for Nonconvex--(Strongly) Concave Minimax Optimization](https://mlsanity.com/paper/2609.21747/) (2026)

## Abstract (arXiv)

We establish complexity lower bounds for stochastic first-order algorithms in nonconvex--concave minimax optimization, allowing algorithms to use variance reduction. Our main contribution is a lower bound for a zero-respecting algorithm class that permits variance reduction, extending beyond the algorithmic restrictions imposed by some existing lower bounds. We consider objectives with an L-Lipschitz continuous joint gradient, a compact convex dual domain of Euclidean radius at most DY, and a primal value function, defined by maximizing the objective over the dual variable, with initial suboptimality at most Delta. The target accuracy varepsilon is measured by the gradient norm of the Moreau envelope of the constrained primal value function with parameter 1/(2L). Under an unbiased stochastic first-order oracle with variance at most σ2 and mean-square smoothness, we prove the lower bound Omega!left(L2DYDeltavarepsilon-3+L3DY2Deltaσ2varepsilon-6right). This result quantifies the dependence on accuracy, dual-domain radius, and oracle noise even when variance reduction is allowed. We also establish complementary lower bounds for nonconvex--strongly-concave minimax optimization. With dual strong-concavity parameter μ>0 and condition number kappa:=L/μ, we obtain Omega!left(LDelta√kappa,varepsilon-2+LDeltakappaσ2varepsilon-4right) under the bounded-variance oracle model. Under the additional mean-square smoothness condition with constant bar L, we obtain Omega!left(LDelta√kappa,varepsilon-2+Deltabar Lσkappa3/2varepsilon-3right). Together, these results identify complexity barriers across the concave and strongly concave regimes, with the main nonconvex--concave bound remaining valid for algorithms that use variance reduction.