Optimal higher order methods speed up solving monotone variational inequalities
Optimal High-Order Methods for Solving Monotone Variational Inequalities
Computer Science and Game Theory
Summary
This paper tackles the problem of solving a special kind of mathematical puzzle called monotone variational inequalities, which appear in many optimization tasks. The authors improve how fast we can solve these puzzles by designing new algorithms that use higher-level math steps, called higher-order methods. They show that their new methods reach the fastest possible speeds for any order of method used. This advances previous work that was close but not quite optimal.
What this means in practice
- •For machine learning engineers: Accelerate algorithms for training models involving minimax optimization problems using the optimal higher-order methods developed here.
- •For operations research teams: Improve solution speed for equilibrium and optimization problems modeled as monotone variational inequalities with the newly established optimal algorithms.
Authors
Xinliang Zhang, Lesi Chen, Linxuan Pan, Chengchang Liu, Junchi Yang, Jingzhao Zhang
Abstract
We study second- and higher-order methods for solving smooth monotone variational inequalities (MVI). Monteiro and Svaiter (SIAM J. Optim., 2012) showed that a second-order method, NPE, converges at a rate of $\mathcal{O}(T^{-1.5})$. For convex-concave minimax optimization, a subclass of MVI problems, Chen, Liu, Luo, and Zhang (COLT 2025) recently improved this rate to $\tilde{\mathcal{O}}( T^{-1.75})$. However, the result has a substantial gap compared to the lower bound of $Ω(T^{-2.5})$ established by Chen et al. (2026). In this paper, we propose a novel second-order method that achieves the optimal rate of $\mathcal{O}(T^{-2.5})$. Our algorithm also extends to higher-order methods: for any integer $ p \ge 1$, we obtain a $p$th-order method with a convergence rate of $\mathcal{O}(T^{-(3p-1)/2})$, matching the known lower bounds and therefore establishing optimal rates across all orders.