Parameter-Free Non-Ergodic Extragradient Algorithms for Solving Monotone Variational Inequalities

Lingqing Shen; Fatma Kılınç-Karzan

math.OCApr 9, 2026

Parameter-Free Non-Ergodic Extragradient Algorithms for Solving Monotone Variational Inequalities

Authors: Lingqing Shen, Fatma Kılınç-Karzan

Organizations: Tepper School of Business, Carnegie Mellon University

Abstract

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/\sqrt{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/\sqrt{T})$
Gorbunov et al. [2022]	unconstrained	gap , nat res	$O(1/\sqrt{T})$
Cai et al. [2022]	constrained	gap , nat res , tan res	$O(1/\sqrt{T})$
Antonakopoulos [2024]	constrained	gap	$o(1/\sqrt{T})$
Upadhyaya et al. [2026]	constrained	gap , nat res	$o(1/\sqrt{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/\sqrt{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)

\displaystyle\eta_{t}=\min\left\{\lambda_{t-1}\eta_{t-1},\frac{\theta}{L_{t-1}},\frac{\theta}{\hat{L}_{t-1}}\right\},

Algorithm 1 Parameter-free non-ergodic extragradient (PF-NE-EG) algorithm

\displaystyle\bar{\eta}_{t}=\min\left\{\lambda_{t-1}\eta_{t-1},\frac{\theta}{L_{t-1}},\frac{\theta}{\hat{L}_{t-1}}\right\},

Algorithm 2 Parameter-free non-ergodic extragradient (PF-NE-EG) algorithm with non-monotone backtracking line search

Panel of Figure 1 — Figure 1: Convergence comparison of different algorithms on bilinear matrix game instances. Initial stepsizes are all set to $\eta_{0}=0.5$ , except for the top right where $\eta_{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

\varepsilon=10^{-5}

for bilinear matrix game instances. Initial stepsizes are all set to

\eta_{0}=0.5

, except for the second column where

\eta_{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

\varepsilon=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

\varepsilon=10^{-6}

for group fairness classification.

Panel of Figure 4 — 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

	$\displaystyle\eta\frac{\\|F({\bm{w}}_{t}(\eta))-F({\bm{z}}_{t})\\|_{2}}{\\|{\bm{w}}_{t}(\eta)-{\bm{z}}_{t}\\|_{2}}$	$\displaystyle\leq\theta<1,$		(13)
	$\displaystyle\eta\frac{\\|F({\bm{w}}_{t}(\eta))-F({\bm{z}}_{t+1}(\eta))\\|_{2}}{\\|{\bm{w}}_{t}(\eta)-{\bm{z}}_{t+1}(\eta)\\|_{2}}$	$\displaystyle\leq 1,\quad\text{if }{\bm{w}}_{t}(\eta)\neq{\bm{z}}_{t+1}(\eta),$		(14)

Appendix

Algorithm 3 Parameter-free non-ergodic extragradient (PF-NE-EG) algorithm with standard backtracking line search

Explore similar work

On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities
Aug 6, 2026TaeHo Yoon, Nicolas LoizouStochastic Optimization Last-Iterate Convergence
Department of Applied Mathematics and Statistics & Mathematical Institute for Data Science, Johns Hopkins University.
Accelerated and Stable Convergence with Anchored Optimistic Method
Jun 19, 2026Motahareh Sohrabi, Jianxin You, Simon Lacoste-Julien +2Last-Iterate Convergence Gradient Descent
Universit´e de Montr´eal · Mila - Quebec AI Institute · CIFAR AI Chair +1
Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities
Sep 14, 2026Jun-Hyun Kim, Ahmet AlacaogluLast-Iterate Convergence Stochastic Approximation
University of British Columbia, Vancouver. · Department of Mathematics, University of British Columbia, Vancouver.

Aug 6, 2026J/K move · Enter open · S save

On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities

TaeHo Yoon, Nicolas Loizou

Department of Applied Mathematics and Statistics & Mathematical Institute for Data Science, Johns Hopkins University.

Stochastic Optimization Last-Iterate Convergence Stochastic Optimization Convergence

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities

Accelerated and Stable Convergence with Anchored Optimistic Method

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