Halpern Iteration Achieves $\tilde{\mathcal{O}}(\varepsilon^{-1/p})$ $p$th-Order Oracle Complexity for Monotone Variational Inequalities

Authors: Lesi Chen, Xinliang Zhang, Hengyu Wang, Chengchang Liu, Yongchao Chen, and Jingzhao Zhang

Preprint: arXiv:2608.08463

Abstract

We study second- and higher-order methods for solving smooth monotone variational inequalities (MVI). The paper introduces a Halpern-NPE method based on a large-step inexact Halpern iteration, obtaining a rate of $\tilde{\mathcal{O}}(T^{-2})$ for MVIs. It also gives a $p$th-order generalization: an Anchored Tensor Method achieves $\mathcal{O}(T^{-(p-1)})$, and combining it with Halpern iteration yields the faster $\tilde{\mathcal{O}}(T^{-p})$ convergence rate. These results improve prior bounds for every $p \geq 2$ while matching the classical extragradient rate when $p=1$.

This work was posted to arXiv on August 9, 2026. See the official arXiv record for the full paper and citation details.