Extragradient and Past Extragradient Methods for (L0,L1)-Lipschitz Variational Inequalities
Abstract
Variational inequalities (VIs) capture a broad class of optimization problems central to modern machine learning, including min-max optimization and equilibrium computation in multiplayer games. Traditionally, algorithms for solving VIs, such as Extragradient (EG) and Past Extragradient (PEG), have been analyzed under the standard L-Lipschitz assumption. However, this condition is often overly restrictive, and recent works have instead turned to the more relaxed (L0,L1)-Lipschitz setting. Existing guarantees for (L0,L1)-Lipschitz VIs require a quasi-sharpness condition [Vankov et al., 2024], while monotone guarantees for EG cover only unconstrained root finding [Choudhury and Loizou, 2025]. In this work, we provide the first convergence guarantees for EG and PEG for monotone (L0,L1)-Lipschitz VIs. We also improve upon prior convergence guarantees for strongly monotone VIs by supporting larger stepsizes in the constrained setting and eliminating exponential dependence on the initial distance from the solution for convergence rates in the unconstrained setting. Lastly, we propose line-search variants for when Lipschitz parameters are unknown. Numerical experiments complement our theoretical results and demonstrate the practical efficacy of our methods.
Related
- Parameter-Free Adaptive Extragradient Methods for Generalized-Smooth Variational Inequalities
- An Adaptive Linesearch-free Method for Monotone Variational Inequalities under Local Lipschitz Continuity
- Optimal High-Order Methods for Solving Monotone Variational Inequalities
- Certified Residual Quasi-Newton Methods for Distributed Variational Inequalities
- Primal Methods for Constrained Variational Inequalities: Optimal Rates, Feasibility Trade-offs, and Lower Bounds
BibTeX
@misc{greenberg2026extragradient,
title = {{Extragradient and Past Extragradient Methods for $(L_0,L_1)$-Lipschitz Variational Inequalities}},
author = {Ezra Greenberg and Nicolas Loizou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16886},
eprint = {2610.16886},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16886},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Extragradient and Past Extragradient Methods for (L_0,L_1)-Lipschitz Variational Inequalities
AU - Ezra Greenberg
AU - Nicolas Loizou
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16886
UR - https://arxiv.org/abs/2610.16886
AB - Variational inequalities (VIs) capture a broad class of optimization problems central to modern machine learning, including min-max optimization and equilibrium computation in multiplayer games. Traditionally, algorithms for solving VIs, such as Extragradient (EG) and Past Extragradient (PEG), have been analyzed under the standard L-Lipschitz assumption. However, this condition is often overly restrictive, and recent works have instead turned to the more relaxed (L_0,L_1)-Lipschitz setting. Existing guarantees for (L_0,L_1)-Lipschitz VIs require a quasi-sharpness condition [Vankov et al., 2024], while monotone guarantees for EG cover only unconstrained root finding [Choudhury and Loizou, 2025]. In this work, we provide the first convergence guarantees for EG and PEG for monotone (L_0,L_1)-Lipschitz VIs. We also improve upon prior convergence guarantees for strongly monotone VIs by supporting larger stepsizes in the constrained setting and eliminating exponential dependence on the initial distance from the solution for convergence rates in the unconstrained setting. Lastly, we propose line-search variants for when Lipschitz parameters are unknown. Numerical experiments complement our theoretical results and demonstrate the practical efficacy of our methods.
ER -