mlsanityData to 7 Oct 2026

Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions

arXiv 2302.14043 ↗First posted 27 Feb 2023math.OC cs.GT cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

Single-call stochastic extragradient methods, like stochastic past extragradient (SPEG) and stochastic optimistic gradient (SOG), have gained a lot of interest in recent years and are one of the most efficient algorithms for solving large-scale min-max optimization and variational inequalities problems (VIP) appearing in various machine learning tasks. However, despite their undoubted popularity, current convergence analyses of SPEG and SOG require a bounded variance assumption. In addition, several important questions regarding the convergence properties of these methods are still open, including mini-batching, efficient step-size selection, and convergence guarantees under different sampling strategies. In this work, we address these questions and provide convergence guarantees for two large classes of structured non-monotone VIPs: (i) quasi-strongly monotone problems (a generalization of strongly monotone problems) and (ii) weak Minty variational inequalities (a generalization of monotone and Minty VIPs). We introduce the expected residual condition, explain its benefits, and show how it can be used to obtain a strictly weaker bound than previously used growth conditions, expected co-coercivity, or bounded variance assumptions. Equipped with this condition, we provide theoretical guarantees for the convergence of single-call extragradient methods for different step-size selections, including constant, decreasing, and step-size-switching rules. Furthermore, our convergence analysis holds under the arbitrary sampling paradigm, which includes importance sampling and various mini-batching strategies as special cases.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 59 of its 85 references that are in the map. First posted on arXiv 27 Feb 2023.

Builds on

59 of 85 references.

References · 59

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  2. 2019Implicit Regularization in Deep Matrix Factorizationcited by 402
  3. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  4. 2019SGD: General Analysis and Improved Ratescited by 206
  5. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  6. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  7. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  8. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  9. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  10. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
  11. 2020Combining Deep Reinforcement Learning and Search for Imperfect-Information Gamescited by 110
  12. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
38 more
  1. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  2. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 81
  3. 2020The Complexity of Constrained Min-Max Optimizationcited by 81
  4. 2016Learning in games with continuous action sets and unknown payoff functionscited by 78
  5. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 66
  6. 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 64
  7. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 61
  8. 2017Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methodscited by 49
  9. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  10. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 47
  11. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  12. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  13. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  14. 2020Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimizationcited by 36
  15. 2019Revisiting Stochastic Extragradientcited by 35
  16. 2018First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problemscited by 33
  17. 2019Adversarial Attack Generation Empowered by Min-Max Optimizationcited by 32
  18. 2020Stochastic Hamiltonian Gradient Methods for Smooth Gamescited by 32
  19. 2021Permutation Compressors for Provably Faster Distributed Nonconvex Optimizationcited by 32
  20. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  21. 2013On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operatorscited by 29
  22. 2019Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Netscited by 29
  23. 2021Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalitiescited by 29
  24. 2019Generalized monotone operators and their averaged resolventscited by 27
  25. 2022Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutionscited by 27
  26. 2018L4: Practical loss-based stepsize adaptation for deep learningcited by 26
  27. 2020Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Gamescited by 26
  28. 2019Last-iterate convergence rates for min-max optimizationcited by 25
  29. 2021Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsizecited by 22
  30. 2023Solving stochastic weak Minty variational inequalities without increasing batch sizecited by 21
  31. 2023Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problemscited by 21
  32. 2021Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimizationcited by 19
  33. 2021On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averagingcited by 18
  34. 2017Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theorycited by 16
  35. 2019ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problemscited by 16
  36. 2022Convergence of Proximal Point and Extragradient-Based Methods Beyond Monotonicity: the Case of Negative Comonotonicitycited by 16
  37. 2013On Optimal Probabilities in Stochastic Coordinate Descent Methodscited by 14
  38. 2014Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexitycited by 14

50 most cited of 59 All 59 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 2; 2025: 5; 2026: 5.

14 papers.

Sort:

  1. 2024Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performancecited by 13
  2. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 13
  3. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 10
  4. 2025Sharpness-Aware Minimization: General Analysis and Improved Ratescited by 10
  5. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  6. 2025Expected Variational Inequalitiescited by 5
  7. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  8. 2024Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexitycited by 4
  9. 2025Extragradient Method for (L0, L1)-Lipschitz Root-finding Problemscited by 3
  10. 2026Solving Stochastic Variational Inequalities without the Bounded Variance Assumptioncited by 3
  11. 2026Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGDcited by 0
  12. 2026On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalitiescited by 0
2 more
  1. 2026Polyak-Type Extragradient Methods for Monotone Root-Finding Problemscited by 0
  2. 2026Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Findingcited by 0