mlsanityData to 7 Oct 2026

Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey

arXiv 2208.13592 ↗First posted 29 Aug 2022math.OC cs.GT cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

This paper is a survey of methods for solving smooth (strongly) monotone stochastic variational inequalities. To begin with, we give the deterministic foundation from which the stochastic methods eventually evolved. Then we review methods for the general stochastic formulation, and look at the finite sum setup. The last parts of the paper are devoted to various recent (not necessarily stochastic) advances in algorithms for variational inequalities.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 78 of its 130 references that are in the map. First posted on arXiv 29 Aug 2022.

Builds on

78 of 130 references.

References · 78

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2022Generative Adversarial Networkscited by 5,603
  3. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  4. 2019SGD: General Analysis and Improved Ratescited by 206
  5. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  6. 2017Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observabilitycited by 143
  7. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  8. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  9. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  10. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  11. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  12. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
38 more
  1. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 71
  2. 2019Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loopcited by 68
  3. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  4. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 61
  5. 2018Negative Momentum for Improved Game Dynamicscited by 59
  6. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 57
  7. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 55
  8. 2015A Universal Catalyst for First-Order Optimizationcited by 54
  9. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  10. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  11. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46
  12. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  13. 2019Variance Reduction for Matrix Gamescited by 37
  14. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  15. 2018A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivitycited by 35
  16. 2019Revisiting Stochastic Extragradientcited by 35
  17. 2020Simple and optimal methods for stochastic variational inequalities, I: operator extrapolationcited by 35
  18. 2019The Complexity of Making the Gradient Small in Stochastic Convex Optimizationcited by 33
  19. 2021Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimizationcited by 31
  20. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  21. 2020Adaptive extra-gradient methods for min-max optimization and gamescited by 30
  22. 2019Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Netscited by 29
  23. 2019On Lower Iteration Complexity Bounds for the Saddle Point Problemscited by 28
  24. 2019A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noisecited by 26
  25. 2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
  26. 2022Optimal and Adaptive Monteiro-Svaiter Accelerationcited by 23
  27. 2020Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learningcited by 22
  28. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 22
  29. 2022The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimizationcited by 20
  30. 2022The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimizationcited by 19
  31. 2022Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Proxcited by 19
  32. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 19
  33. 2020Accelerating Smooth Games by Manipulating Spectral Shapescited by 18
  34. 2020Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalitiescited by 18
  35. 2020Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Accelerationcited by 18
  36. 2021Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Couplingcited by 16
  37. 2020Coordinate Methods for Matrix Gamescited by 15
  38. 2021Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimizationcited by 15

50 most cited of 78 All 78 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 4; 2024: 1; 2025: 2; 2026: 2.

10 papers.

  1. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  2. 2023Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalitiescited by 7
  3. 2024Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimizationcited by 4
  4. 2022Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimizationcited by 2
  5. 2025Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shufflingcited by 2
  6. 2026Stochastic variance reduced extragradient methods for solving hierarchical variational inequalitiescited by 1
  7. 2023Unified analysis of SGD-type methodscited by 0
  8. 2023Omega: Optimistic EMA Gradientscited by 0
  9. 2025Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guaranteescited by 0
  10. 2026Accelerated and Stable Convergence with Anchored Generalized Optimistic Methodcited by 0