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

Lesi Chen, Xinliang Zhang, Hengyu Wang +3

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,…