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

arXiv: https://arxiv.org/abs/2609.21747 · HTML: https://mlsanity.com/paper/2609.21747/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 15 references that are in the map.
- First posted on arXiv 18 Sep 2026.

## Builds on (most cited first, 14 of 14)

- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [Learning with Average Top-k Loss](https://mlsanity.com/paper/1705.08826/) (2017)
- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization](https://mlsanity.com/paper/2008.08170/) (2020)
- [SAPD+: An Accelerated Stochastic Method for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/2205.15084/) (2022)
- [Decentralized learning for wireless communications and networking](https://mlsanity.com/paper/1503.08855/) (2015)
- [An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problems](https://mlsanity.com/paper/2310.15448/) (2023)
- [Efficient Single-Loop Stochastic Algorithms for Nonconvex-Concave Minimax Optimization](https://mlsanity.com/paper/2501.05677/) (2025)

## Built on by (most cited first, 1 of 1)

- [Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization](https://mlsanity.com/paper/2610.01662/) (2026)

## Abstract (arXiv)

We develop single-loop stochastic projected damped extragradient methods for 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(kappavarepsilon-4) and O(varepsilon-5) in the nonconvex--strongly concave and nonconvex--concave settings, respectively, where kappa=L/μ. Under an additional mean-square Lipschitz condition on the stochastic gradients, VR-SPDE improves these GS complexities to O(kappa3/2varepsilon-3) and O(varepsilon-9/2), respectively. For an varepsilon-optimization-stationary point, SPDE achieves SFO complexities of O(kappavarepsilon-4) and O(varepsilon-6), while VR-SPDE achieves O(kappa3/2varepsilon-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.