Research map / Optimization / Nonconvex and smooth optimization
Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements
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.
Shows that shuffling-based same-sample stochastic extragradient (RR, flip-flop) can diverge in unconstrained monotone finite-sum problems, and proposes SEG-FFA (flip-flop sampling plus anchoring at epoch end) that matches EG to second order and converges in monotone and strongly monotone settings.
Problem
Stochastic extragradient for unconstrained finite-sum minimax problems has limited convergence guarantees in convex-concave (monotone) settings; shuffling-based variants (random reshuffling, flip-flop) are unproven or divergent there.
Approach
Adds an anchoring step (averaging the epoch's final iterate with the epoch's initial iterate) to flip-flop shuffled same-sample SEG, so each epoch deterministically matches the EG/EG+ update up to second-order Taylor terms, giving O(eta^3) error and convergence in monotone problems.
Key results
- SEG-FFA converges on monotone quadratic problems while SEG-US, SEG-RR, and SEG-FF diverge in the long run.
- SEG-FFA achieves O((log K)^2 / K^{1/3}) rate for monotone problems with decaying stepsizes.
- In strongly monotone case SEG-FFA attains tilde-O(1/(nK^4)) rate, versus Omega(1/(nK^3)) lower bounds for SGDA-RR and SEG-RR with constant stepsizes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add anchoring to flip-flop-shuffled same-sample SEG (ablation) | SEG-FF · Convex-concave finite-sum minimax | minimum expected squared gradient norm: $\Omega(1)$ -> $\tilde{\gO}(\frac{1}{K^{1/3}})$ | Helped |
| Add anchoring to flip-flop-shuffled same-sample SEG (ablation) | SEG-FF · Strongly-convex-strongly-concave finite-sum minimax | expected squared distance to optimum: $\tilde{\gO} ( \frac{1}{nK^2} )$ -> $\tilde{\gO} ( \frac{1}{nK^4} )$ | Helped |
| Use random reshuffling without anchoring (ablation) | same-sample SEG · Convex-concave finite-sum minimax | minimum expected squared gradient norm: $\Omega(1)$ | Hurt |
| Use flip-flop shuffling without anchoring (ablation) | same-sample SEG · Convex-concave finite-sum minimax | minimum expected squared gradient norm: $\Omega(1)$ | Hurt |
| Use with-replacement uniform sampling instead of flip-flop anchoring (ablation) | same-sample SEG · Convex-concave finite-sum minimax | minimum expected squared gradient norm: $\Omega(1)$ | Hurt |
| Use random reshuffling without anchoring (ablation) | same-sample SEG · Strongly-convex-strongly-concave finite-sum minimax | expected squared distance to optimum: $\tilde \gO ( \frac{1}{nK^2} )$; lower bound $\Omega ( \frac{1}{nK^3} )$ | Hurt |
Surprising findings
- SEG with random reshuffling and with flip-flop shuffling can diverge in convex-concave (monotone) problems, even though shuffling helps in minimization.
- The claimed monotone convergence of SEG-RR in a recent AISTATS 2024 paper appears to rely on an invalid Jensen's inequality step.
Limitations
- Requires strong assumptions: Lipschitz Hessian of saddle operator (M-smoothness) and component variance bound (rho, sigma).
- Convex-concave rate is O((log K)^2/K^{1/3}) with decaying stepsizes, and the analysis is limited to monotone/star-monotone settings and quadratic-style experiments.
- Experiments are on randomly generated quadratic problems only.
Experimental setup
Datasets: randomly generated quadratic minimax problems
Benchmarks: randomly generated monotone quadratic minimax problems randomly generated strongly monotone quadratic minimax problems
Metrics: squared gradient norm squared distance to optimum
Baselines: SEG-US SEG-RR SEG-FF SGDA-RR SGDA-US
Builds on: extragradient random reshuffling flip-flop shuffling Krasnoselskii-Mann iteration EG+
Closest papers by meaning
- Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization (NeurIPS 2024 · similarity 0.91)
- Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization (ICML 2025 · similarity 0.90)
- On the Last-Iterate Convergence of Shuffling Gradient Methods (ICML 2024 · similarity 0.89)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.88)
- Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion (ICML 2024 · similarity 0.87)
- Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness (ICML 2025 · similarity 0.87)
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.