mlsanityData to 7 Oct 2026

Stochastic Variance Reduction for Variational Inequality Methods

arXiv 2102.08352 ↗First posted 16 Feb 2021math.OC cs.LG stat.MLcited by 46

Not on the map. Why?

Abstract (arXiv)

We propose stochastic variance reduced algorithms for solving convex-concave saddle point problems, monotone variational inequalities, and monotone inclusions. Our framework applies to extragradient, forward-backward-forward, and forward-reflected-backward methods both in Euclidean and Bregman setups. All proposed methods converge in the same setting as their deterministic counterparts and they either match or improve the best-known complexities for solving structured min-max problems. Our results reinforce the correspondence between variance reduction in variational inequalities and minimization. We also illustrate the improvements of our approach with numerical evaluations on matrix games.

Key facts. Cited by 46 papers in the map (data through 7 Oct 2026). Builds on 27 of its 56 references that are in the map. First posted on arXiv 16 Feb 2021.

Builds on

27 of 56 references.

References · 27

  1. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  2. 2017Training GANs with Optimismcited by 217
  3. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  4. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
  5. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  6. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  7. 2020Variance-Reduced Methods for Machine Learningcited by 79
  8. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
  9. 2019Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loopcited by 68
  10. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  11. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 59
  12. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 57
15 more
  1. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 47
  2. 2015Variance Reduced Stochastic Gradient Descent with Neighborscited by 39
  3. 2015Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectivescited by 38
  4. 2019Variance Reduction for Matrix Gamescited by 37
  5. 2018A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivitycited by 35
  6. 2019Revisiting Stochastic Extragradientcited by 35
  7. 2017Extragradient method with variance reduction for stochastic variational inequalitiescited by 33
  8. 2017Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applicationscited by 29
  9. 2015Projected Reflected Gradient Methods for Monotone Variational Inequalitiescited by 27
  10. 2018Global Convergence to the Equilibrium of GANs using Variational Inequalitiescited by 15
  11. 2020Coordinate Methods for Matrix Gamescited by 15
  12. 2019On the convergence of stochastic primal-dual hybrid gradientcited by 8
  13. 2020Two steps at a time -- taking GAN training in stride with Tseng's methodcited by 8
  14. 2019Forward-backward-forward methods with variance reduction for stochastic variational inequalitiescited by 5
  15. 2021Extragradient and Extrapolation Methods with Generalized Bregman Distances for Saddle Point Problemscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 14; 2023: 9; 2024: 6; 2025: 2; 2026: 6.

46 papers.

Sort:

  1. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  2. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 22
  3. 2023Solving stochastic weak Minty variational inequalities without increasing batch sizecited by 21
  4. 2021Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimizationcited by 19
  5. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 19
  6. 2021On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averagingcited by 18
  7. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 17
  8. 2021Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimizationcited by 15
  9. 2021Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guaranteescited by 15
  10. 2024Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimizationcited by 15
  11. 2022Optimal Algorithms for Decentralized Stochastic Variational Inequalitiescited by 14
  12. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 14
34 more
  1. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  2. 2024Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyondcited by 11
  3. 2021Coordinate Linear Variance Reduction for Generalized Linear Programmingcited by 10
  4. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  5. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 10
  6. 2022Compression and Data Similarity: Combination of Two Techniques for Communication-Efficient Solving of Distributed Variational Inequalitiescited by 8
  7. 2023Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalitiescited by 7
  8. 2022On the Complexity of a Practical Primal-Dual Coordinate Methodcited by 6
  9. 2023Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedbackcited by 6
  10. 2023Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developmentscited by 5
  11. 2021Decentralized Personalized Federated Learning for Min-Max Problemscited by 4
  12. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  13. 2023Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditionscited by 4
  14. 2021Cyclic Coordinate Dual Averaging with Extrapolationcited by 3
  15. 2022Decentralized Stochastic Variance Reduced Extragradient Methodcited by 3
  16. 2022On Scaled Methods for Saddle Point Problemscited by 3
  17. 2024Primal Methods for Variational Inequality Problems with Functional Constraintscited by 3
  18. 2024Multiple Greedy Quasi-Newton Methods for Saddle Point Problemscited by 3
  19. 2022Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimizationcited by 2
  20. 2024Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problemscited by 2
  21. 2026Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusionscited by 2
  22. 2021Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programmingcited by 1
  23. 2022A Variance-Reduced Stochastic Accelerated Primal Dual Algorithmcited by 1
  24. 2025Finite-sample guarantees for data-driven forward-backward operator methodscited by 1
  25. 2026Stochastic variance reduced extragradient methods for solving hierarchical variational inequalitiescited by 1
  26. 2026A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Mapscited by 1
  27. 2022SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalitiescited by 0
  28. 2022Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysiscited by 0
  29. 2023Omega: Optimistic EMA Gradientscited by 0
  30. 2024Near-Optimal Distributed Minimax Optimization under the Second-Order Similaritycited by 0
  31. 2025Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guaranteescited by 0
  32. 2026Exploring New Frontiers in Vertical Federated Learning: the Role of Saddle Point Reformulationcited by 0
  33. 2026Accelerated and Stable Convergence with Anchored Generalized Optimistic Methodcited by 0
  34. 2026Optimal High-Order Methods for Solving Monotone Variational Inequalitiescited by 0