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

arXiv:2610.04944v1 Announce Type: cross Abstract: 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 ilde{Theta}(n+min{sqrt{n},kappa,n^{3/4}sqrt{kappa}},LDeltaarepsilon^{-2}) throughout kappa=L/muge1, under exact dual initialization and for 00 is universal. This characterization is our main result. A dual-chain construction provides the lower bound and matches the existing Catalyst upper bound for kappagesqrt{n}. For 1lekappalesqrt{n}, we introduce recursive proximal descent-ascent (RPDA), which retains a recursive gradient estimator across proximal subproblems and attains ilde{O}(n+sqrt{n},kappa LDeltaarepsilon^{-2}) with a fixed query budget. Both upper bounds guarantee an expected squared primal gradient at most arepsilon^2. Under individual smoothness, we also prove Omega(n+min{kappa,sqrt{nkappa}},LDeltaarepsilon^{-2}) for every kappage1. It matches the polynomial upper rate for a bilinear subclass when kappage n; the intermediate-condition-number gap remains open.

Related

• Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
• Single-Loop Stochastic Projected Damped Extragradient Methods for Stochastic Nonconvex--(Strongly) Concave Minimax Optimization
• Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems

Source: arXiv cs.LG | 2026-10-06