Single-Loop Stochastic Projected Damped Extragradient Methods for Stochastic Nonconvex--(Strongly) Concave Minimax Optimization

Abstract

We develop single-loop stochastic projected damped extragradient methods for stochastic nonconvex--(strongly) concave minimax optimization, with complexity guarantees for both game stationarity (GS) and optimization stationarity (OS). Our approach combines a stochastic projected damped extragradient (SPDE) method with a recursive variance-reduced variant, VR-SPDE, both of which retain a single-loop structure. Under an unbiased stochastic gradient oracle with uniformly bounded variance, SPDE finds an $\epsilon$-game-stationary point with stochastic first-order oracle (SFO) complexities of $O(\kappa {\epsilon }^{-4})$ and $O({\epsilon }^{-5})$ in the nonconvex--strongly concave and nonconvex--concave settings, respectively, where $\kappa =L/\mu$. Under an additional mean-square Lipschitz condition on the stochastic gradients, VR-SPDE improves these GS complexities to $O({\kappa }^{3/2}{\epsilon }^{-3})$ and $O({\epsilon }^{-9/2})$, respectively. For an $\epsilon$-optimization-stationary point, SPDE achieves SFO complexities of $O(\kappa {\epsilon }^{-4})$ and $O({\epsilon }^{-6})$, while VR-SPDE achieves $O({\kappa }^{3/2}{\epsilon }^{-3})$ and $O({\epsilon }^{-6})$, in the two settings, respectively. These OS guarantees match the best-known bounds achieved by multi-loop methods while preserving a single-loop implementation. To the best of our knowledge, our results provide the best-known SFO complexity guarantees among single-loop stochastic first-order methods for the respective stationarity criteria and problem classes.