aiqbench analysis
This research introduces single-loop stochastic projected damped extragradient methods that achieve state-of-the-art complexity guarantees for nonconvex minimax optimization while avoiding the computational overhead of multi-loop architectures. By integrating variance reduction techniques, the proposed algorithms improve convergence rates for both game and optimization stationarity under specific gradient conditions. These theoretical advances are critical for scaling efficient training in adversarial machine learning and generative model applications where saddle-point dynamics dominate.
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 $\varepsilon$-game-stationary point with stochastic first-order oracle (SFO) complexities of $O(\kappa\varepsilon^{-4})$ and $O(\varepsilon^{-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}\varepsilon^{-3})$ and $O(\varepsilon^{-9/2})$, respectively. For an $\varepsilon$-optimization-stationary point, SPDE achieves SFO complexities of $O(\kappa\varepsilon^{-4})$ and $O(\varepsilon^{-6})$, while VR-SPDE achieves $O(\kappa^{3/2}\varepsilon^{-3})$ and $O(\varepsilon^{-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.
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 $\varepsilon$-game-stationary point with stochastic first-order oracle (SFO) complexities of $O(\kappa\varepsilon^{-4})$ and $O(\varepsilon^{-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}\varepsilon^{-3})$ and $O(\varepsilon^{-9/2})$, respectively. For an $\varepsilon$-optimization-stationary point, SPDE achieves SFO complexities of $O(\kappa\varepsilon^{-4})$ and $O(\varepsilon^{-6})$, while VR-SPDE achieves $O(\kappa^{3/2}\varepsilon^{-3})$ and $O(\varepsilon^{-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.
Optimization and Control (math.OC); Machine Learning (cs.LG); Machine Learning (stat.ML)
arXiv:2609.21747 [math.OC]
(or arXiv:2609.21747v1 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2609.21747 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.
Full text under the publisher's open licence · 271 words
Related coverage
Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
arXiv · Sep 17, 2026
Near-Optimal Pure Single-Loop Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization
arXiv · Sep 18, 2026
Stochastic Difference-of-Convex Optimization with Momentum
arXiv · Oct 14, 2026
A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization
arXiv · Oct 7, 2026