Single-loop algorithm matches multi-loop efficiency in minimax optimization
Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
Machine Learning
Summary
Minimax optimization problems are common in machine learning and require balancing two opposing parts, which can be tricky and slow using standard methods with multiple loops. The authors developed a new single-loop approach that simplifies the process while achieving the best-known efficiency rates seen only in more complex multi-loop methods. Their method uses updated mathematical techniques to improve how quickly it finds good solutions under varying criteria. This simplifies implementation without sacrificing speed or accuracy compared to previous best methods.
What this means in practice
- •For machine learning engineers: Implement more efficient training for adversarial models by using a single-loop optimization algorithm that matches multi-loop complexities.
- •For optimization software developers: Design faster optimization software with a streamlined single-loop method that achieves optimal convergence rates for nonconvex--concave problems.
Authors
Minghao Zhang, Zi Xu
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(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.