mlsanityData to 7 Oct 2026

The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities

arXiv 2107.01906 ↗First posted 5 Jul 2021math.OC cs.LGcited by 12

Not on the map. Why?

Abstract (arXiv)

In this paper, we analyze the local convergence rate of optimistic mirror descent methods in stochastic variational inequalities, a class of optimization problems with important applications to learning theory and machine learning. Our analysis reveals an intricate relation between the algorithm's rate of convergence and the local geometry induced by the method's underlying Bregman function. We quantify this relation by means of the Legendre exponent, a notion that we introduce to measure the growth rate of the Bregman divergence relative to the ambient norm near a solution. We show that this exponent determines both the optimal step-size policy of the algorithm and the optimal rates attained, explaining in this way the differences observed for some popular Bregman functions (Euclidean projection, negative entropy, fractional power, etc.).

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 19 of its 55 references that are in the map. First posted on arXiv 5 Jul 2021.

Builds on

19 of 55 references.

References · 19

  1. 2014Convex Optimization: Algorithms and Complexitycited by 569
  2. 2017Training GANs with Optimismcited by 217
  3. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  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 132
  7. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 97
  8. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  9. 2016Learning in games with continuous action sets and unknown payoff functionscited by 78
  10. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 59
  11. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  12. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
7 more
  1. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 47
  2. 2017Extragradient method with variance reduction for stochastic variational inequalitiescited by 33
  3. 2015Projected Reflected Gradient Methods for Monotone Variational Inequalitiescited by 27
  4. 2018Hessian Riemannian gradient flows in convex programmingcited by 25
  5. 2016Riemannian game dynamicscited by 18
  6. 2018Hessian barrier algorithms for linearly constrained optimization problemscited by 8
  7. 2017Stochastic mirror descent dynamics and their convergence in monotone variational inequalitiescited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 4; 2023: 1; 2024: 0; 2025: 1; 2026: 3.

12 papers.

  1. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  2. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  3. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  4. 2022No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separationcited by 17
  5. 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 13
  6. 2022Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Gamescited by 9
  7. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  8. 2021Adaptive first-order methods revisited: Convex optimization without Lipschitz requirementscited by 4
  9. 2026The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedbackcited by 3
  10. 2026Stochastic variance reduced extragradient methods for solving hierarchical variational inequalitiescited by 1
  11. 2025Last-Iterate Convergence of No-Regret Learning for Equilibria in Bargaining Gamescited by 0
  12. 2026Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalitiescited by 0