Perseus: A Simple and Optimal High-Order Method for Variational Inequalities

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 ∈ X such that langle F(x), x - x^starrangle ≥ 0 for all x ∈ X. We consider the setting in which F is smooth with up to (p-1)th-order derivatives. For p = 2, the cubic regularized Newton method was extended to VIs with a global rate of O(ε-1). An improved rate of O(ε-2/3loglog(1/ε)) can be obtained via an alternative second-order method, but this method requires a nontrivial line-search procedure as an inner loop. Similarly, high-order methods based on line-search procedures have been shown to achieve a rate of O(ε-2/(p+1)loglog(1/ε)). As emphasized by Nesterov, however, such procedures do not necessarily imply practical applicability in large-scale applications, and it would be desirable to complement these results with a simple high-order VI method that retains the optimality of the more complex methods. We propose a pth-order method that does textitnot require any line search procedure and provably converges to a weak solution at a rate of O(ε-2/(p+1)). We prove that our pth-order method is optimal in the monotone setting by establishing a matching lower bound under a generalized linear span assumption. Our method with restarting attains a linear rate for smooth and uniformly monotone VIs and a local superlinear rate for smooth and strongly monotone VIs. Our method also achieves a global rate of O(ε-2/p) for solving smooth and nonmonotone VIs satisfying the Minty condition and when augmented with restarting it attains a global linear and local superlinear rate for smooth and nonmonotone VIs satisfying the uniform/strong Minty condition.