Research map / Optimization / Nonconvex and smooth optimization
Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Adds a quadratic perturbation (tau/2)||x||^2 - (tau/2)||y||^2 to a stochastic convex-concave minimax problem and runs stochastic EG/OGDA on the perturbed operator, proving last-iterate restricted primal-dual gap and gradient-norm rates.
Problem
Last-iterate convergence of stochastic first-order methods (S-EG, S-OGDA) for constrained smooth convex-concave minimax problems under bounded-variance oracles, where vanilla last iterates can fail to converge even on bilinear games.
Approach
Regularize the convex-concave objective into a strongly convex-strongly concave one with a small quadratic perturbation, apply plain stochastic EG or OGDA to the perturbed operator (no extra oracle calls, no variance reduction or batching), prove distance convergence to the perturbed saddle point, and convert it to restricted primal-dual gap or gradient norm bounds; diminishing perturbations give
Key results
- Horizon-dependent PS-EG and PS-OGDA achieve O(T^{-1/4}) last-iterate restricted primal-dual gap rate, improving the prior O~(T^{-1/7}) on compact domains.
- Anytime variant achieves O(T^{-1/5}) restricted gap for general closed convex sets for both PS-EG and PS-OGDA.
- Unconstrained anytime PS-EG achieves O(t^{-1/4}) gradient-norm rate.
Limitations
- Rates are slower than the O(T^{-1/3}) achieved by variance-reduced multi-point oracle methods in the unconstrained setting.
- Anytime constrained rate O(T^{-1/5}) is worse than the horizon-dependent O(T^{-1/4}).
- Analysis of the sharper anytime gradient-norm bound is specific to PS-EG and unconstrained problems.
Experimental setup
Metrics: restricted primal-dual gap gradient norm squared distance to perturbed saddle point
Baselines: S-EG S-OGDA adaptively perturbed mirror descent anchored stochastic methods generalized Frank-Wolfe methods GOMA
Builds on: extragradient optimistic gradient descent-ascent stochastic extragradient
Closest papers by meaning
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods (ICLR 2024 · similarity 0.93)
- Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions (NeurIPS 2024 · similarity 0.91)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.91)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.90)
- Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime (NeurIPS 2025 · similarity 0.90)
- Universal Gradient Methods for Stochastic Convex Optimization (ICML 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.