mlsanityData to 14 Oct 2026

On the convergence of single-call stochastic extra-gradient methods

arXiv 1908.08465 ↗First posted 22 Aug 2019math.OC cs.GT cs.LGcited by 89

Not on the map. Why?

Abstract (arXiv)

Variational inequalities have recently attracted considerable interest in machine learning as a flexible paradigm for models that go beyond ordinary loss function minimization (such as generative adversarial networks and related deep learning systems). In this setting, the optimal O(1/t) convergence rate for solving smooth monotone variational inequalities is achieved by the Extra-Gradient (EG) algorithm and its variants. Aiming to alleviate the cost of an extra gradient step per iteration (which can become quite substantial in deep learning applications), several algorithms have been proposed as surrogates to Extra-Gradient with a single oracle call per iteration. In this paper, we develop a synthetic view of such algorithms, and we complement the existing literature by showing that they retain a O(1/t) ergodic convergence rate in smooth, deterministic problems. Subsequently, beyond the monotone deterministic case, we also show that the last iterate of single-call, stochastic extra-gradient methods still enjoys a O(1/t) local convergence rate to solutions of non-monotone variational inequalities that satisfy a second-order sufficient condition.

Key facts. Cited by 89 papers in the map (data through 14 Oct 2026). First posted on arXiv 22 Aug 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 25; 2022: 24; 2023: 18; 2024: 9; 2025: 1; 2026: 12.

89 papers.

Sort:

By area:

  1. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
  2. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 63
  3. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  4. 2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 39
  5. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  6. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  7. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 36
  8. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 36
  9. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 32
  10. 2021Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimizationcited by 31
  11. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  12. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
38 more
  1. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 28
  2. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  3. 2022A unified stochastic approximation framework for learning in gamescited by 23
  4. 2021Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationalitycited by 21
  5. 2021Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusionscited by 21
  6. 2023Solving stochastic weak Minty variational inequalities without increasing batch sizecited by 21
  7. 2021No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimizationcited by 20
  8. 2023ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPscited by 20
  9. 2021Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimizationcited by 19
  10. 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 19
  11. 2021Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problemscited by 17
  12. 2022No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separationcited by 17
  13. 2022Generalized Optimistic Methods for Convex-Concave Saddle Point Problemscited by 16
  14. 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
  15. 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 16
  16. 2021Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guaranteescited by 15
  17. 2021Neural Network Weights Do Not Converge to Stationary Points: An Invariant Measure Perspectivecited by 15
  18. 2021Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedbackcited by 15
  19. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 15
  20. 2022Optimal Algorithms for Decentralized Stochastic Variational Inequalitiescited by 14
  21. 2022Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noisecited by 14
  22. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  23. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 14
  24. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  25. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  26. 2024Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithmscited by 14
  27. 2021The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalitiescited by 12
  28. 2022Beyond the Golden Ratio for Variational Inequality Algorithmscited by 12
  29. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 11
  30. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  31. 2022On Convergence of Gradient Descent Ascent: A Tight Local Analysiscited by 9
  32. 2022Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Gamescited by 9
  33. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  34. 2021Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascentcited by 8
  35. 2021Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equationscited by 8
  36. 2022Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergencecited by 8
  37. 2022Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problemscited by 7
  38. 2021Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Gamescited by 6

50 most cited of 89 All 89 (JSON)