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

arXiv:2609.21747v1 Announce Type: cross 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 arepsilon-game-stationary point with stochastic first-order oracle (SFO) complexities of O(kappaarepsilon^{-4}) and O(arepsilon^{-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}arepsilon^{-3}) and O(arepsilon^{-9/2}), respectively. For an arepsilon-optimization-stationary point, SPDE achieves SFO complexities of O(kappaarepsilon^{-4}) and O(arepsilon^{-6}), while VR-SPDE achieves O(kappa^{3/2}arepsilon^{-3}) and O(arepsilon^{-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.

Source: arXiv cs.LG | 2026-09-21