Monotone variational inequalities (VIs) provide a unifying framework for convex minimization, equilibrium computation, and convex-concave saddle-point problems. Extragradient-type methods are among the most effective first-order algorithms for such problems, but their performance hinges critically on stepsize selection. While most existing theory focuses on ergodic averages of the iterates, practical performance is often driven by the significantly stronger behavior of the last iterate. Moreover, available last-iterate guarantees typically rely on fixed stepsizes chosen using problem-specific global smoothness information, which is often difficult to estimate accurately and may not even be applicable. In this paper, we develop parameter-free extragradient methods with non-asymptotic last-iterate guarantees for constrained monotone VIs. For globally Lipschitz operators, our algorithm achieves an o(1/T) last-iterate rate. We then extend the framework to locally Lipschitz operators via backtracking line search and obtain the same rate while preserving parameter-freeness, thereby making parameter-free last-iterate methods applicable to important problem classes for which global smoothness is unrealistic. Our numerical experiments on bilinear matrix games, LASSO, minimax group fairness, and state-of-the-art maximum entropy sampling relaxations demonstrate wide applicability of our results as well as strong last-iterate performance and significant improvements over existing methods.
Figures & tables
Reference
Domain
Convergence Metric
Rate
Golowich et al. [2020]
unconstrained
gap , nat res
O(1/T)
Gorbunov et al. [2022]
unconstrained
gap , nat res
O(1/T)
Cai et al. [2022]
constrained
gap , nat res , tan res
O(1/T)
Antonakopoulos [2024]
constrained
gap
o(1/T)
Upadhyaya et al. [2026]
constrained
gap , nat res
o(1/T)
Table 1: Summary of last-iterate convergence rates of EG variants with constant stepsizes ( gap = restricted gap function; nat res = natural residual; tan res = tangent residual)
Algorithm
Domain
Operator
Rate
Metric
Ergodicity
Universal MP [ 9 ]
bounded
Lipschitz
* O(1/T) *
gap
ergodic
Adaptive MP [ 6 ]
constrained
Lipschitz
O(1/T)
gap
ergodic
AdaProx [ 5 ]
constrained
Lipschitz
O(1/T)
gap
ergodic
AdaPEG [ 19 ]
constrained
Lipschitz
O(1/T)
gap
ergodic
aGRAAL [ 39 ]
constrained
local Lipschitz
* O(1/T) *
gap
ergodic
Adaptive EG+ [ 10 ]
unconstrained
Lipschitz
O(1/T)
nat res
best-iterate
Table 2: Summary of parameter-free algorithms with non-asymptotic convergence rates ( gap = restricted gap function; nat res = natural residual; tan res = tangent residual; * indicates rates that the corresponding algorithm additionally assumes a bounded operator)
Algorithm 2 Parameter-free non-ergodic extragradient (PF-NE-EG) algorithm with non-monotone backtracking line search
Figure 1: Convergence comparison of different algorithms on bilinear matrix game instances. Initial stepsizes are all set to η0=0.5 , except for the top right where η0=0.02 .
Algorithm
(100, 1.0)
(100, 1.0) *
(500, 0.2)
(1000, 0.1)
EG
0.24
9.01
0.88
0.63
EG (avg)
6.13
32.60
6.95
5.03
Universal MP
18.87
18.70
105.46
64.34
Adaptive MP
7.88
40.35
8.45
5.09
AdaProx
13.59
14.93
74.41
60.51
aGRAAL
20.56
65.51
18.86
13.20
Table 3: Time (in seconds) to reach ε=10−5 for bilinear matrix game instances. Initial stepsizes are all set to η0=0.5 , except for the second column where η0=0.02 .
Figure 2: Convergence comparison of different algorithms for LASSO instances.
Algorithm
(250,1000,0.5)
(500,5000,0.1)
EG
0.42
1.88
Adapt EG
0.13
0.51
PF-NE-EG
0.03
0.10
PF-NE-EG Bt
0.06
0.21
PF-NE-EG AdaBt
0.03
0.10
Table 4: Time (in seconds) to reach ε=10−6 for LASSO instances.
Figure 3: Convergence comparison of different algorithms for solving group fairness classification.
Algorithm
(20,200,50)
(10,200,100)
PF-NE-EG
5.01
3.62
PF-NE-EG Bt
9.76
7.21
PF-NE-EG AdaBt
4.86
3.67
Table 5: Time (in seconds) to reach ε=10−6 for group fairness classification.
Figure 4: Comparison for convergence and iteration count and solution time (seconds) to reach the desired tolerance for solving linx double-scaling instances.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
η∥wt(η)−zt∥2∥F(wt(η))−F(zt)∥2
≤θ<1,
(13)
η∥wt(η)−zt+1(η)∥2∥F(wt(η))−F(zt+1(η))∥2
≤1,if wt(η)=zt+1(η),
(14)
Appendix
Algorithm 3 Parameter-free non-ergodic extragradient (PF-NE-EG) algorithm with standard backtracking line search
We study stochastic extragradient (SEG) methods for solving monotone variational inequality problems (VIPs) over a feasible set. Although extragradient is a foundational algorithm for VIPs and its deterministic convergence theory is well developed, its stochastic counterpart remains less understood. Most existing analyses focus on independent-sample SEG (I-SEG) and assume either that the domain is compact or that the variance of the stochastic operator is uniformly bounded. The behavior of same-sample SEG (S-SEG), a natural variant with materially different properties, has received far less attention. In this work, we address these gaps in the literature. We first show that S-SEG is sensitive to samplewise Lipschitz parameters: mean Lipschitzness and bounded variance alone do not ensure convergence, even on a compact set. Then, for possibly unbounded domains, we establish a high-probability restricted-gap convergence for each SEG variant under a relaxed set of assumptions, and show that certain fundamental improvements to these results are impossible in general. Finally, we show that a known asymmetric double step-size selection that guarantees almost sure last-iterate convergence for I-SEG can fail for S-SEG: there exists a stochastic monotone VIP for which S-SEG diverges almost surely even under the modified step-sizes.
TaeHo Yoon, Nicolas Loizou
Department of Applied Mathematics and Statistics & Mathematical Institute for Data Science, Johns Hopkins University.
We study first-order methods for solving monotone variational inequalities arising in min-max optimization. Classical approaches such as the extragradient method rely on two gradient queries per iteration, which limits their analysis and applicability in the online and stochastic settings. We propose a family of Generalized Optimistic Methods with Anchoring (GOMA), which combine two-time-scale optimistic updates with an anchoring term inspired by Halpern iteration. In the deterministic setting, GOMA achieves the optimal accelerated last-iterate rate O(1/k2) on the squared gradient norm for monotone Lipschitz operators. In the stochastic setting with unbounded variance, a simplified single-call variant of GOMA achieves a last-iterate convergence rate of O(1/k) on the squared gradient norm. To the best of our knowledge, this is the first such guarantee for stochastic monotone Lipschitz variational inequalities in the unconstrained setting without variance reduction or growing batches.
Motahareh Sohrabi, Jianxin You, Simon Lacoste-Julien +2
Universit´e de Montr´eal · Mila - Quebec AI Institute · CIFAR AI Chair +1
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.
Jun-Hyun Kim, Ahmet Alacaoglu
University of British Columbia, Vancouver. · Department of Mathematics, University of British Columbia, Vancouver.