arXiv preprint ·
Single-Loop Stochastic Projected Damped Extragradient Methods for Stochastic Nonconvex--(Strongly) Concave Minimax Optimization
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
Nested Clustered Optimization Is One End of a Schur Bridge, and the Interior Is Sometimes Provably Better
Density-Driven Area Coverage for Nonholonomic Multi-Robot Systems with Safety Guarantee
Deep Reinforcement Learning with Buffered Quantile Objectives
Riemannian Density-Driven Optimal Control: Tangent-Space LQR for Second-Order Multi-Agent Systems on Curved Manifolds
Tilt as a Certified Resource: Preserving Motor Wrench-Rate Authority on Articulated Multirotors
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.