Parameter-free non-ergodic extragradient algorithms for solving monotone variational inequalities
New math for optimization algorithms removes the need to hand-tune a critical parameter, potentially making iterative solvers faster and easier to deploy in practice.
The Thesis
Variational inequalities (VIs) are a mathematical framework that unifies a surprisingly wide set of practical problems: training machine learning models with fairness constraints, solving game-theoretic equilibria, and running convex optimization. The workhorse algorithm for these problems is the extragradient method — a two-step iterative update — but it requires users to set a stepsize, a tuning parameter that depends on knowing how 'smooth' the problem is globally. This paper removes that requirement entirely, designing algorithms that adapt their own stepsizes on the fly and still come with provable convergence guarantees on the actual last computed answer, not just a running average. The catch is that these are theoretical results with numerical experiments on moderate-scale benchmarks; the gap to large-scale production deployment in ML training pipelines has not been closed.
Catalyst
Last-iterate convergence guarantees — proofs about where the algorithm actually stops, not some average of all prior steps — have only recently become an active research target, driven by practitioners noticing that averaged iterates perform poorly in game-solving and GAN training. Separately, backtracking line search techniques (adaptive step-sizing via local function probes) have matured enough to be analyzed rigorously in the non-ergodic setting. Combining both in a parameter-free framework is a contribution that became technically tractable only as these two streams converged.
What's New
Prior extragradient algorithms — including classical variants and more recent optimistic gradient methods — require the user to supply a global Lipschitz constant, a number that bounds how fast the problem's operator can change. In practice this constant is often unknown, must be estimated conservatively, and can be undefined for locally-smooth problems. This paper replaces that requirement with a backtracking line search, a procedure where the algorithm probes the local smoothness at each step and adjusts automatically. The claimed advantage is an o(1/√T) last-iterate convergence rate (meaning the error shrinks faster than 1/√T as iterations T grow) without any problem-specific tuning, extended to locally Lipschitz operators where global constants simply do not exist.
The Counter
The experiments here are on textbook-scale problems — bilinear matrix games, LASSO regression, and fairness minimax problems — none of which stress-tests the method at the scale where stepsize tuning actually becomes painful. The o(1/√T) rate improvement over 1/√T is a theoretical refinement that may be invisible in wall-clock time on real hardware. Backtracking line search adds extra function evaluations per iteration, which can easily erase the benefit of skipping one tuning step. Most importantly, the ML community has already built robust heuristics (Adam, learning rate schedules, warmup) that handle stepsize adaptation in practice; it is not obvious practitioners will abandon those battle-tested tools for a theoretically cleaner but less familiar algorithm. The paper also does not demonstrate results on large neural network training, which is where the pain of stepsize selection is most acute and most studied.
Longs
- MSFT — Azure ML and solver infrastructure for enterprise optimization
- GUROBI (private) — optimization solver vendors who may integrate adaptive VI methods
- BOTZ (robotics/AI ETF) — broad exposure to ML infrastructure improvements
- ANSS — Ansys, whose simulation and optimization tools underlie engineering equilibrium problems
Shorts
- Vendors selling hand-tuned hyperparameter optimization services: if solvers self-tune, that consulting layer shrinks
- Fixed-stepsize solver libraries that compete on ease-of-use: parameter-free methods erode that advantage
Enablers (Picks & Shovels)
- JAX and PyTorch autograd — automatic differentiation infrastructure that makes implementing custom iterative solvers practical
- NumPy/SciPy ecosystem — the numerical substrate on which these algorithms are prototyped and benchmarked
- arXiv math.OC community — rapid open dissemination that lets practitioners adopt theoretical advances quickly
Private Watchlist
- Gurobi Optimization — mathematical programming solvers
- Mosek — conic and convex optimization software
- Radical Ventures — deep-tech AI research commercialization fund
Resources
The Paper
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.