# Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions arXiv: https://arxiv.org/abs/2302.14043 ยท HTML: https://mlsanity.com/paper/2302.14043/ ## Key facts - Cited by 14 papers in the map (data through 14 Oct 2026). - Builds on 59 of its 85 references that are in the map. - First posted on arXiv 27 Feb 2023. ## Builds on (most cited first, 30 of 59) - [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017) - [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019) - [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019) - [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019) - [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018) - [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018) - [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019) - [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020) - [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018) - [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019) - [Combining Deep Reinforcement Learning and Search for Imperfect-Information Games](https://mlsanity.com/paper/2007.13544/) (2020) - [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020) - [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019) - [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019) - [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020) - [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016) - [SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation](https://mlsanity.com/paper/2006.10311/) (2020) - [A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games](https://mlsanity.com/paper/2206.05825/) (2022) - [Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2106.02326/) (2021) - [Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods](https://mlsanity.com/paper/1712.09677/) (2017) - [Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling](https://mlsanity.com/paper/2003.10162/) (2020) - [Tight last-iterate convergence rates for no-regret learning in multi-player games](https://mlsanity.com/paper/2010.13724/) (2020) - [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021) - [Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity](https://mlsanity.com/paper/2110.04261/) (2021) - [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022) - [Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization](https://mlsanity.com/paper/2006.11573/) (2020) - [Revisiting Stochastic Extragradient](https://mlsanity.com/paper/1905.11373/) (2019) - [First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems](https://mlsanity.com/paper/1810.10207/) (2018) - [Adversarial Attack Generation Empowered by Min-Max Optimization](https://mlsanity.com/paper/1906.03563/) (2019) - [Stochastic Hamiltonian Gradient Methods for Smooth Games](https://mlsanity.com/paper/2007.04202/) (2020) ## Built on by (most cited first, 14 of 14) - [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025) - [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024) - [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023) - [Sharpness-Aware Minimization: General Analysis and Improved Rates](https://mlsanity.com/paper/2503.02225/) (2025) - [Multiplayer Federated Learning: Reaching Equilibrium with Less Communication](https://mlsanity.com/paper/2501.08263/) (2025) - [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025) - [Solving Stochastic Variational Inequalities without the Bounded Variance Assumption](https://mlsanity.com/paper/2602.05531/) (2026) - [Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates](https://mlsanity.com/paper/2306.05100/) (2023) - [Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity](https://mlsanity.com/paper/2402.05071/) (2024) - [Extragradient Method for (L0, L1)-Lipschitz Root-finding Problems](https://mlsanity.com/paper/2510.22421/) (2025) - [Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD](https://mlsanity.com/paper/2604.10373/) (2026) - [On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.06182/) (2026) - [Polyak-Type Extragradient Methods for Monotone Root-Finding Problems](https://mlsanity.com/paper/2609.26581/) (2026) - [Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding](https://mlsanity.com/paper/2609.36033/) (2026) ## 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.