mlsanityData to 7 Oct 2026

Solving Stochastic Variational Inequalities without the Bounded Variance Assumption

arXiv 2602.05531 ↗First posted 5 Feb 2026math.OC cs.LG stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

We analyze algorithms for solving stochastic variational inequalities (VI) without the bounded variance or bounded domain assumptions, where our main focus is min-max optimization with possibly unbounded constraint sets. We focus on two classes of problems: monotone VIs; and structured nonmonotone VIs that admit a solution to the weak Minty VI. The latter assumption allows us to solve structured nonconvex-nonconcave min-max problems. For both classes of VIs, to make the expected residual norm less than varepsilon, we show an oracle complexity of widetildeO(varepsilon-4), which is the best-known for constrained VIs. In our setting, this complexity had been obtained with the bounded variance assumption in the literature, which is not even satisfied for bilinear min-max problems with an unbounded domain. We obtain this complexity for stochastic oracles whose variance can grow as fast as the squared norm of the optimization variable.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 26 of its 43 references that are in the map. First posted on arXiv 5 Feb 2026.

Builds on

26 of 43 references.

References · 26

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  2. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 334
  3. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  4. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  5. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  6. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  7. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  8. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  9. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 71
  10. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 61
  11. 2020Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimizationcited by 36
  12. 2017Extragradient method with variance reduction for stochastic variational inequalitiescited by 33
14 more
  1. 2019Generalized monotone operators and their averaged resolventscited by 27
  2. 2021Stochastic Bias-Reduced Gradient Methodscited by 25
  3. 2020Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learningcited by 22
  4. 2023Solving stochastic weak Minty variational inequalities without increasing batch sizecited by 21
  5. 2023Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problemscited by 21
  6. 2022Convergence of Proximal Point and Extragradient-Based Methods Beyond Monotonicity: the Case of Negative Comonotonicitycited by 16
  7. 2024Dealing with unbounded gradients in stochastic saddle-point optimizationcited by 15
  8. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  9. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 13
  10. 2022Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysiscited by 12
  11. 2022Beyond the Golden Ratio for Variational Inequality Algorithmscited by 12
  12. 2020Two steps at a time -- taking GAN training in stride with Tseng's methodcited by 8
  13. 2019Nonlinear Forward-Backward Splitting with Projection Correctioncited by 4
  14. 2024Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexitycited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Accelerated and Stable Convergence with Anchored Generalized Optimistic Methodcited by 0
  2. 2026On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalitiescited by 0
  3. 2026Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalitiescited by 0