Optimal High-Order Methods for Solving Monotone Variational Inequalities

Xinliang Zhang; Lesi Chen; Linxuan Pan; Chengchang Liu; Junchi Yang; Jingzhao Zhang

In the authors' words

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 $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 $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 $O (T^{- 2.5})$ . Our algorithm also extends to higher-order methods: for any integer $p \geq 1$ , we obtain a $p$ th-order method with a convergence rate of $O (T^{- (3 p - 1) /2})$ , matching the known lower bounds and therefore establishing optimal rates across all orders.

Main resultThe abstract does not state a limitation.

Optimal High-Order Methods for Solving Monotone Variational Inequalities

In the authors' words

More on Optimization that day

A General Multicriteria Optimization Perspective on Resilience

The logarithmic spiral is optimal for shoreline search: a computer-assisted proof

The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization

Convergence of Rotation-based Matrix Optimizers: A Unified Analysis of SOAP, Conda, and SPlus

Scalable Incremental Robustness Analysis of Neural Network Feedback Systems