mlsanityData to 13 Oct 2026

Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements

arXiv 2306.16502 ↗First posted 28 Jun 2023stat.ML cs.LG math.OCcited by 6

Not on the map. Why?

Abstract (arXiv)

For min-max optimization and variational inequalities problems (VIP) encountered in diverse machine learning tasks, Stochastic Extragradient (SEG) and Stochastic Gradient Descent Ascent (SGDA) have emerged as preeminent algorithms. Constant step-size variants of SEG/SGDA have gained popularity, with appealing benefits such as easy tuning and rapid forgiveness of initial conditions, but their convergence behaviors are more complicated even in rudimentary bilinear models. Our work endeavors to elucidate and quantify the probabilistic structures intrinsic to these algorithms. By recasting the constant step-size SEG/SGDA as time-homogeneous Markov Chains, we establish a first-of-its-kind Law of Large Numbers and a Central Limit Theorem, demonstrating that the average iterate is asymptotically normal with a unique invariant distribution for an extensive range of monotone and non-monotone VIPs. Specializing to convex-concave min-max optimization, we characterize the relationship between the step-size and the induced bias with respect to the Von-Neumann's value. Finally, we establish that Richardson-Romberg extrapolation can improve proximity of the average iterate to the global solution for VIPs. Our probabilistic analysis, underpinned by experiments corroborating our theoretical discoveries, harnesses techniques from optimization, Markov chains, and operator theory.

Key facts. Cited by 6 papers in the map (data through 13 Oct 2026). Builds on 34 of its 75 references that are in the map. First posted on arXiv 28 Jun 2023.

Builds on

34 of 75 references.

References · 34

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  2. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
  3. 2017Training GANs with Optimismcited by 217
  4. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  5. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  6. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 134
  7. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  8. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  9. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 85
  10. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  11. 2020The Complexity of Constrained Min-Max Optimizationcited by 82
  12. 2016Learning in games with continuous action sets and unknown payoff functionscited by 79
22 more
  1. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  2. 2016Connecting Generative Adversarial Networks and Actor-Critic Methodscited by 49
  3. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  4. 2020An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Biascited by 47
  5. 2018Global Non-convex Optimization with Discretized Diffusionscited by 44
  6. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  7. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  8. 2019Revisiting Stochastic Extragradientcited by 35
  9. 2019Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrievalcited by 34
  10. 2020Stochastic Hamiltonian Gradient Methods for Smooth Gamescited by 32
  11. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  12. 2020Adaptive extra-gradient methods for min-max optimization and gamescited by 30
  13. 2021Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalitiescited by 29
  14. 2022Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizescited by 29
  15. 2020Convergence of constant step stochastic gradient descent for non-smooth non-convex functionscited by 27
  16. 2020Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Gamescited by 26
  17. 2021Survival of the strictest: Stable and unstable equilibria under regularized learning with partial informationcited by 22
  18. 2014Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variantscited by 19
  19. 2020Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust Algorithmscited by 14
  20. 2021On Riemannian Stochastic Approximation Schemes with Fixed Step-Sizecited by 12
  21. 2022The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Pointscited by 6
  22. 2022A Variance-Reduced Stochastic Accelerated Primal Dual Algorithmcited by 1

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2024: 2; 2025: 3; 2026: 1.

6 papers.

  1. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 14
  2. 2024Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolationcited by 6
  3. 2024Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Waycited by 5
  4. 2025Description of the Training Process of Neural Networks via Ergodic Theorem : Ghost nodescited by 0
  5. 2025Multi-agent learning under uncertainty: Recurrence vs. concentrationcited by 0
  6. 2026Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGDcited by 0