mlsanityData to 7 Oct 2026

Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling

arXiv 2003.10162 ↗First posted 23 Mar 2020math.OC cs.GT cs.LGcited by 49

Not on the map. Why?

Abstract (arXiv)

Owing to their stability and convergence speed, extragradient methods have become a staple for solving large-scale saddle-point problems in machine learning. The basic premise of these algorithms is the use of an extrapolation step before performing an update; thanks to this exploration step, extra-gradient methods overcome many of the non-convergence issues that plague gradient descent/ascent schemes. On the other hand, as we show in this paper, running vanilla extragradient with stochastic gradients may jeopardize its convergence, even in simple bilinear models. To overcome this failure, we investigate a double stepsize extragradient algorithm where the exploration step evolves at a more aggressive time-scale compared to the update step. We show that this modification allows the method to converge even with stochastic gradients, and we derive sharp convergence rates under an error bound condition.

Key facts. Cited by 49 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 Mar 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 15; 2022: 12; 2023: 11; 2024: 5; 2025: 2; 2026: 4.

49 papers.

Sort:

  1. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  2. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  3. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  4. 2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 38
  5. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  6. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  7. 2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
  8. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  9. 2022A unified stochastic approximation framework for learning in gamescited by 22
  10. 2023Solving stochastic weak Minty variational inequalities without increasing batch sizecited by 21
  11. 2023Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problemscited by 21
  12. 2021On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averagingcited by 18
37 more
  1. 2022No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separationcited by 17
  2. 2021Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guaranteescited by 15
  3. 2022An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Gamescited by 14
  4. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  5. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  6. 2021Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimatorcited by 13
  7. 2022Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noisecited by 13
  8. 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 13
  9. 2021The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalitiescited by 12
  10. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  11. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  12. 2021Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascentcited by 8
  13. 2021Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equationscited by 8
  14. 2022Domain Adversarial Training: A Game Perspectivecited by 7
  15. 2023Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalitiescited by 7
  16. 2023Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinementscited by 6
  17. 2024SDEs for Minimax Optimizationcited by 6
  18. 2023XGrad: Boosting Gradient-Based Optimizers With Weight Predictioncited by 5
  19. 2024Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalitiescited by 5
  20. 2021On the Initialization for Convex-Concave Min-max Problemscited by 4
  21. 2022Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimizationcited by 4
  22. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  23. 2023The equivalence of dynamic and strategic stability under regularized learning in gamescited by 4
  24. 2024A geometric decomposition of finite games: Convergence vs. recurrence under exponential weightscited by 4
  25. 2022On Scaled Methods for Saddle Point Problemscited by 3
  26. 2025Optimism Without Regularization: Constant Regret in Zero-Sum Gamescited by 2
  27. 2021Stochastic Projective Splitting: Solving Saddle-Point Problems with Multiple Regularizerscited by 1
  28. 2022When is Momentum Extragradient Optimal? A Polynomial-Based Analysiscited by 1
  29. 2024Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicitycited by 1
  30. 2025Layer-wise Quantization for Quantized Optimistic Dual Averagingcited by 1
  31. 2022SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalitiescited by 0
  32. 2023A Deep Learning Based Resource Allocator for Communication Networks with Dynamic User Utility Demandscited by 0
  33. 2024Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimizationcited by 0
  34. 2026Accelerated and Stable Convergence with Anchored Generalized Optimistic Methodcited by 0
  35. 2026On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalitiescited by 0
  36. 2026Regret, equilibrium, and learning in games: A guided tourcited by 0
  37. 2026Polyak-Type Extragradient Methods for Monotone Root-Finding Problemscited by 0