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

@misc{zhang2026singleloop,
  title = {{Single-Loop Stochastic Projected Damped Extragradient Methods for Nonconvex--(Strongly) Concave Minimax Optimization}},
  author = {Huiling Zhang and Minhao Zhang and Zi Xu and Yuhong Dai},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.21747},
  eprint = {2609.21747},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.21747},
}

TY  - UNPB
TI  - Single-Loop Stochastic Projected Damped Extragradient Methods for Nonconvex--(Strongly) Concave Minimax Optimization
AU  - Huiling Zhang
AU  - Minhao Zhang
AU  - Zi Xu
AU  - Yuhong Dai
PY  - 2026
DA  - 2026/10/12
PB  - arXiv
DO  - 10.48550/arxiv.2609.21747
UR  - https://arxiv.org/abs/2609.21747
AB  - 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 ε-game-stationary point with stochastic first-order oracle (SFO) complexities of O(κε^−4) and O(ε^−5) in the nonconvex--strongly concave and nonconvex--concave settings, respectively, where κ=L/μ. Under an additional mean-square Lipschitz condition on the stochastic gradients, VR-SPDE improves these GS complexities to O(κ^3/2ε^−3) and O(ε^−9/2), respectively. For an ε-optimization-stationary point, SPDE achieves SFO complexities of O(κε^−4) and O(ε^−6), while VR-SPDE achieves O(κ^3/2ε^−3) and O(ε^−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.
ER  -