Single-loop methods improve complex nonconvex concave optimization tasks
Single-Loop Stochastic Projected Damped Extragradient Methods for Stochastic Nonconvex--(Strongly) Concave Minimax Optimization
Machine Learning
Summary
This paper looks at tough mathematical problems where two sides try to optimize opposite goals, like in some AI games or training scenarios. The authors design simple, single-loop algorithms that find good solutions faster and with fewer steps than before, while handling noisy or unpredictable data. These methods improve efficiency without adding extra complicated layers, which can help make these problems easier to solve in practice. The authors provide math-based guarantees showing these are among the best methods for this kind of problem.
What this means in practice
- •For machine learning engineers: Train adversarial machine learning models efficiently using single-loop stochastic methods for nonconvex concave objectives with complexity guarantees.
- •For algorithm designers: Design optimization algorithms that solve challenging minimax problems with fewer computational steps and simpler loop structures.
Authors
Huiling Zhang, Minhao Zhang, Zi Xu
Abstract
We develop single-loop stochastic projected damped extragradient methods for stochastic 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.