Perseus: a simple and optimal high-order method for variational inequalities: Perseus: a simple and optimal high-order method for...

This paper settles an open and challenging question pertaining to the design of simple and optimal high-order methods for solving smooth and monotone variational inequalities (VIs). A VI involves finding $x^{\star }\in \mathcal{X}$ such that $⟨F(x),x-x^{\star }⟩\ge 0$ for all $x\in \mathcal{X}$. We consider the setting in which $F:{\mathbb{R}}^d\to {\mathbb{R}}^d$ is smooth with up to ${(p-1)}^{\text{th}}$-order derivatives. For $p=2$, the cubic regularization of Newton’s method has been extended to VIs with a global rate of $O({ϵ}^{-1})$ (Nesterov in Cubic regularization of Newton’s method for convex problems with constraints, Tech. rep., Université catholique de Louvain, Center for Operations Research and Econometrics (CORE), 2006). An improved rate of $O({ϵ}^{-2/3}loglog(1/ϵ))$ can be obtained via an alternative second-order method, but this method requires a nontrivial line-search procedure as an inner loop. Similarly, the existing high-order methods based on line-search procedures have been shown to achieve a rate of $O({ϵ}^{-2/(p+1)}loglog(1/ϵ))$ (Bullins and Lai in SIAM J Optim 32(3):2208–2229, 2022; Jiang and Mokhtari in Generalized optimistic methods for convex–concave saddle point problems, 2022; Lin and Jordan in Math Oper Res 48(4):2353–2382, 2023). As emphasized by Nesterov (Lectures on convex optimization, vol 137, Springer, Berlin, 2018), however, such procedures do not necessarily imply the practical applicability in large-scale applications, and it is desirable to complement these results with a simple high-order VI method that retains the optimality of the more complex methods. We propose a $p^{\text{th}}$-order method that does not require any line search procedure and provably converges to a weak solution at a rate of $O({ϵ}^{-2/(p+1)})$. We prove that our $p^{\text{th}}$-order method is optimal in the monotone setting by establishing a lower bound of $\mathrm{\Omega }({ϵ}^{-2/(p+1)})$ under a generalized linear span assumption. A restarted version of our $p^{\text{th}}$-order method attains a linear rate for smooth and $p^{\text{th}}$-order uniformly monotone VIs and another restarted version of our $p^{\text{th}}$-order method attains a local superlinear rate for smooth and strongly monotone VIs. Further, the similar $p^{\text{th}}$-order method achieves a global rate of $O({ϵ}^{-2/p})$ for solving smooth and nonmonotone VIs satisfying the Minty condition. Two restarted versions attain a global linear rate under additional $p^{\text{th}}$-order uniform Minty condition and a local superlinear rate under additional strong Minty condition.