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

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.