Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
Abstract
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(L2DYΔ̅0ε−3), where L is the gradient Lipschitz constant, DY bounds the diameter of the dual feasible set, and Δ̅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(L2DYΔϕε−3), up to an additive lower-order cost, where Δϕ:=ϕ(x0)−infxϕ(x). We further establish a lower bound of Ω(L2DYΔϕε−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 𝒪 (L3/2DY1/2Δϕε−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 (√κ LΔϕε−2) leading complexity for both stationarity criteria, where κ=L/μ is the dual condition number, up to an additive initialization cost. The ε−2 accuracy dependence is optimal under fixed regularity and initialization bounds.
Related
- Deterministic Oracle Complexity for Goldstein Stationarity in Nonsmooth Nonconvex Optimization with Constraints
- Matching Randomized First-Order Bounds for Higher-Order Smooth Nonconvex Optimization
- Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization
- Matching Upper and Lower Bounds for Higher-Order Nonconvex Finite-Sum Optimization
- Matching Randomized Bounds for Finite-Sum Nonconvex-Concave Optimization
BibTeX
@misc{zhang2026matching,
title = {{Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization}},
author = {Minghao Zhang and Zi Xu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17973},
eprint = {2609.17973},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17973},
}
RIS
TY - UNPB
TI - Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
AU - Minghao Zhang
AU - Zi Xu
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.17973
UR - https://arxiv.org/abs/2609.17973
AB - 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Δ̅_0ε^−3), where L is the gradient Lipschitz constant, D_Y bounds the diameter of the dual feasible set, and Δ̅_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Δ_ϕε^−3), up to an additive lower-order cost, where Δ_ϕ:=ϕ(x_0)−inf_xϕ(x). We further establish a lower bound of Ω(L^2D_YΔ_ϕε^−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 𝒪 (L^3/2D_Y^1/2Δ_ϕε^−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 (√κ LΔ_ϕε^−2) leading complexity for both stationarity criteria, where κ=L/μ is the dual condition number, up to an additive initialization cost. The ε^−2 accuracy dependence is optimal under fixed regularity and initialization bounds.
ER -