mlsanityData to 14 Oct 2026

Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities

arXiv 2609.15257 ↗First posted 14 Sep 2026math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We analyze a stochastic algorithm with Halpern-type anchoring for constrained convex-concave problems and monotone variational inequalities. This single-loop and single-call algorithm uses one unbiased sample of the gradient operator at every iteration, to be applicable to monotone games with noisy feedback. With t denoting the iteration counter, we prove an anytime last-iterate convergence rate of O(t-1/4) for both the gradient-mapping norm and restricted gap, bypassing the O(t-1/5) constrained-anytime bottleneck in the literature. Specializing then to multi-point oracles, we use variance reduction to achieve the O(t-1/2) rate with an anytime single-loop algorithm using 2 samples per iteration. Our results allow constrained problems with a potentially unbounded feasible set; as well as a structured class of stochastic oracles whose variance need not be uniformly bounded.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 32 of its 42 references that are in the map. First posted on arXiv 14 Sep 2026.

Builds on

32 of 42 references.

References · 32

  1. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  2. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  3. 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
  4. 2016Learning in games with continuous action sets and unknown payoff functionscited by 81
  5. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 73
  6. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 62
  7. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 60
  8. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 49
  9. 2020Simple and optimal methods for stochastic variational inequalities, I: operator extrapolationcited by 35
  10. 2019The Complexity of Making the Gradient Small in Stochastic Convex Optimizationcited by 34
  11. 2017Extragradient method with variance reduction for stochastic variational inequalitiescited by 33
  12. 2022Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalitiescited by 33
20 more
  1. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 32
  2. 2023Solving stochastic weak Minty variational inequalities without increasing batch sizecited by 21
  3. 2022The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimizationcited by 20
  4. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 20
  5. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 20
  6. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 19
  7. 2022No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separationcited by 17
  8. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 17
  9. 2024Dealing with unbounded gradients in stochastic saddle-point optimizationcited by 16
  10. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 14
  11. 2021The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalitiescited by 12
  12. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  13. 2024Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Gamescited by 5
  14. 2026Solving Stochastic Variational Inequalities without the Bounded Variance Assumptioncited by 5
  15. 2026Computation of Strong Solutions to Stochastic Variational Inequalitiescited by 4
  16. 2023Stable Nonconvex-Nonconcave Training via Linear Interpolationcited by 3
  17. 2026Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusionscited by 3
  18. 2026Last-Iterate Convergence of Anchored Gradient Descentcited by 3
  19. 2026How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyondcited by 2
  20. 2026Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problemscited by 1

Built on by

Not cited yet.