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

Abstract

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 ⋆ ∈ X such that ⟨ F ( x ) , x - x ⋆ ⟩ ≥ 0 for all x ∈ X . We consider the setting in which F : R d → R d is smooth with up to ( p - 1 ) 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 log log ( 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 ) log log ( 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 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 th -order method is optimal in the monotone setting by establishing a lower bound of Ω ( ϵ - 2 / ( p + 1 ) ) under a generalized linear span assumption. A restarted version of our p th -order method attains a linear rate for smooth and p th -order uniformly monotone VIs and another restarted version of our p th -order method attains a local superlinear rate for smooth and strongly monotone VIs. Further, the similar p 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 th -order uniform Minty condition and a local superlinear rate under additional strong Minty condition.