Halpern Iteration Achieves ilde{O}(epsilon^{-1/p}) pth-Order Oracle Complexity for Monotone Variational Inequalities

arXiv:2608.08463v1 Announce Type: cross 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 the rate of O(T^{-1.5}). For convex-concave minimax optimization, a subset of MVI problems, Chen, Liu, Luo, and Zhang (COLT 2025) recently improved the complexity to ilde{O}( T^{-1.75}) . However, it is open whether the conjectured complexity for MVI can be improved. In this paper, by using a large-step inexact Halpern iteration, we propose a novel Halpern-NPE method that achieves an even faster rate of ilde{O}(T^{-2}) for solving MVIs. We also provide the pth-order generalization of our method. We first introduce an Anchored Tensor Method (ATM) that achieves the rate of O(T^{-(p-1)}), and then combine it with the Halpern iteration to achieve a faster convergence rate of ilde{O}(T^{-p}). This improves all prior results for p ge 2 and matches the classical extragradient method for p=1.

Source: arXiv cs.AI | 2026-08-11