# Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization

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

## Key facts

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

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

- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [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)
- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [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)
- [Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction](https://mlsanity.com/paper/2103.08280/) (2021)
- [Lower Bounds for Smooth Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/1901.11224/) (2019)
- [Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2106.01761/) (2021)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [Lower Bounds for Nonconvex-Concave Minimax Optimization](https://mlsanity.com/paper/2609.14233/) (2026)
- [Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness](https://mlsanity.com/paper/2609.00045/) (2026)
- [Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2609.30877/) (2026)

## Abstract (arXiv)

We characterize, up to logarithmic factors, the minimax expected query complexity of finite-sum nonconvex-strongly-concave optimization under mean-squared averaged smoothness. For randomized zero-respecting incremental first-order algorithms, the complexity is tildeTheta(n+min√n,kappa,n3/4√kappa,LDeltavarepsilon-2) throughout kappa=L/μ≥1, under exact dual initialization and for 0<varepsilon2≤ c0LDelta, where c0>0 is universal. This characterization is our main result. A dual-chain construction provides the lower bound and matches the existing Catalyst upper bound for kappa≥√n. For 1≤kappa≤√n, we introduce recursive proximal descent-ascent (RPDA), which retains a recursive gradient estimator across proximal subproblems and attains tildeO(n+√n,kappa LDeltavarepsilon-2) with a fixed query budget. Both upper bounds guarantee an expected squared primal gradient at most varepsilon2. Under individual smoothness, we also prove Omega(n+minkappa,√nkappa,LDeltavarepsilon-2) for every kappa≥1. It matches the polynomial upper rate for a bilinear subclass when kappa≥ n; the intermediate-condition-number gap remains open.