{"id":"arxiv/2608.08463","url":"https://arxiv.org/abs/2608.08463","tags":["math.OC","cs.AI"],"score":0,"title":"Halpern Iteration Achieves $\\tilde{\\mathcal{O}}(ε^{-1/p})$ $p$th-Order Oracle Complexity for Monotone Variational Inequalities","domain":"math.OC","source":"arxiv","authors":["Lesi Chen","Xinliang Zhang","Hengyu Wang","Chengchang Liu","Yongchao Chen","Jingzhao Zhang"],"reviews":0,"subject":"math.OC","summary":"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 $\\mathcal{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 $\\tilde{\\mathcal{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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-09","reactions":{}}