Preprint
Aug 2026
Halpern Iteration Achieves $\tilde{\mathcal{O}}(\epsilon^{-1/p})$ $p$th-Order Oracle Complexity for Monotone Variational Inequalities
By using a large-step inexact Halpern iteration, a novel Halpern-NPE method is proposed that achieves an even faster rate of $\tilde{\mathcal{O}}(T^{-2})$ for solving MVIs and improves all prior results for $p \ge 2$ and matches the classical extragradient method for p=1.
Le-Si Chen, Xin-Liang Zhang, He Wang et al.
· 0 citations