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

Huiling Zhang; Minhao Zhang; Zi Xu; Yuhong Dai

math.OCSep 18, 2026

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

Authors: Huiling Zhang, Minhao Zhang, Zi Xu, Yuhong Dai

Organizations: LSEC, ICMSEC, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China · Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China

Abstract

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(κ\varepsilon^{-4})$ and $O(\varepsilon^{-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}\varepsilon^{-3})$ and $O(\varepsilon^{-9/2})$ , respectively. For an $\varepsilon$ -optimization-stationary point, SPDE achieves SFO complexities of $O(κ\varepsilon^{-4})$ and $O(\varepsilon^{-6})$ , while VR-SPDE achieves $O(κ^{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.

Figures & tables

Method	Setting	Loop	VR	Criterion	Complexity
SGDA [ 9 ]	NC–SC	Single	No	OS	$O(\kappa^{3}\varepsilon^{-4})$
Acc-MDA [ 7 ]	NC–SC	Single	Yes	OS	$\widetilde{O}(\kappa^{9/2}\varepsilon^{-3})$
SREDA [ 10 ]	NC–SC	Multi	Yes	OS	$O(\kappa^{3}\varepsilon^{-3})$
SAPD+ [ 17 ]	NC–SC	Multi	No	OS	$O(\kappa\varepsilon^{-4})$
VR-SAPD+ [ 17 ]	NC–SC	Multi	Yes	OS	$O(\kappa^{2}\varepsilon^{-3})$
SPDE (this paper)	NC–SC	Single	No	GS/OS	$\bm{O(\kappa\varepsilon^{-4})}$

Table 1: Representative complexity guarantees for stochastic nonconvex minimax optimization. Bounds are total SFO complexities unless marked by

\dagger

, which denotes an iteration complexity. The dependence on

L

is suppressed in this comparison.

Figure 1: Performance of six algorithms for Toy WGAN with linear generator problem.

Figure 2: Performance of five algorithms for the group robust learning.

Min-Max Optimization

Min-max optimization studies algorithms for objectives where one decision-maker minimizes loss while an adversary or opponent maximizes it.

See all 38 papers

Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
Sep 16, 2026Minghao Zhang, Zi XuMin-Max Optimization Extragradient Methods
Department of Mathematics, College of Sciences, Shanghai University, Shanghai, 200444, P.R.China.
Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization
Sep 17, 2026Minhao Zhang, Zi XuLast-Iterate Convergence Min-Max Optimization
Department of Mathematics, Shanghai University, Shanghai 200444, People’s Republic of China
Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization
Sep 25, 2026Qihao ZhouOracle Complexity Min-Max Optimization
Independent Researcher

Sep 16, 2026J/K move · Enter open · S save

Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization

Minghao Zhang, Zi Xu

Department of Mathematics, College of Sciences, Shanghai University, Shanghai, 200444, P.R.China.

Min-Max Optimization Extragradient Methods

Open paper AskPDF arXiv

We introduce a new single-loop algorithmic framework for smooth nonconvex--concave minimax optimization. The resulting projected damped extragradient method combines projected extragradient updates, dual momentum, and a moving proximal center. Under both the optimization-stationarity and game-stationarity criteria, our method achieves the best-known complexity among single-loop first-order methods. For optimization stationarity, our method achieves a gradient complexity of

O(L^2D_Y\barΔ_0\varepsilon^{-3})

, where

L

is the gradient Lipschitz constant,

D_Y

bounds the diameter of the dual feasible set, and

\barΔ_0

is an initialization quantity involving the value-function gap and the initial gradients. Moreover, by incorporating a fixed-center warm-up phase, the complexity can be improved to

O(L^2D_YΔ_φ\varepsilon^{-3})

, up to an additive lower-order cost, where

Δ_φ:=φ(x_0)-\inf_xφ(x)

. We further establish a lower bound of

Ω(L^2D_YΔ_φ\varepsilon^{-3})

for optimization stationarity over projected zero-respecting first-order methods. This lower bound proves that the warm-started version of our algorithm is optimal up to a constant factor for optimization stationarity within this oracle class. For game stationarity, our method achieves

\mathcal{O}\!(L^{3/2}D_Y^{1/2}Δ_φ\varepsilon^{-5/2})

gradient complexity. This matches the best-known complexity of multi-loop first-order methods, thereby establishing the same complexity with a single-loop algorithmic structure. Under dual strong concavity, the proposed framework achieves

O\!(\sqrtκ\,LΔ_φ\varepsilon^{-2})

leading complexity for both stationarity criteria, where

κ=L/μ

is the dual condition number, up to an additive initialization cost. The

\varepsilon^{-2}

accuracy dependence is optimal under fixed regularity and initialization bounds.

Abstract

Min-Max Optimization

Explore similar work

Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization

Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization

Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization