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

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 $\tilde{\Theta}(n+\min\{\sqrt{n}\,\kappa,n^{3/4}\sqrt{\kappa}\}\,L\Delta\varepsilon^{-2})$ throughout $\kappa=L/\mu\ge1$, under exact dual initialization and for $0<\varepsilon^2\le c_0L\Delta$, where $c_0>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\ge\sqrt{n}$. For $1\le\kappa\le\sqrt{n}$, we introduce recursive proximal descent-ascent (RPDA), which retains a recursive gradient estimator across proximal subproblems and attains $\tilde{O}(n+\sqrt{n}\,\kappa L\Delta\varepsilon^{-2})$ with a fixed query budget. Both upper bounds guarantee an expected squared primal gradient at most $\varepsilon^2$. Under individual smoothness, we also prove $\Omega(n+\min\{\kappa,\sqrt{n\kappa}\}\,L\Delta\varepsilon^{-2})$ for every $\kappa\ge1$. It matches the polynomial upper rate for a bilinear subclass when $\kappa\ge n$; the intermediate-condition-number gap remains open.

Optimization and Control (math.OC); Machine Learning (cs.LG)

arXiv:2610.04944 [math.OC]

(or arXiv:2610.04944v1 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2610.04944 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.