Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities

In this work, we present new simple and optimal algorithms for solving the variational inequality (VI) problem for pth-order smooth, monotone operators -- a problem that generalizes convex optimization and saddle-point problems. Recent works (Bullins and Lai (2020), Lin and Jordan (2021), Jiang and Mokhtari (2022)) present methods that achieve a rate of tildeO(ε-2/(p+1)) for p≥ 1, extending results by (Nemirovski (2004)) and (Monteiro and Svaiter (2012)) for p=1,2. A drawback to these approaches, however, is their reliance on a line search scheme. We provide the first p^textrmth-order method that achieves a rate of O(ε-2/(p+1)). Our method does not rely on a line search routine, thereby improving upon previous rates by a logarithmic factor. Building on the Mirror Prox method of Nemirovski (2004), our algorithm works even in the constrained, non-Euclidean setting. Furthermore, we prove the optimality of our algorithm by constructing matching lower bounds. These are the first lower bounds for smooth MVIs beyond convex optimization for p > 1. This establishes a separation between solving smooth MVIs and smooth convex optimization, and settles the oracle complexity of solving p^textrmth-order smooth MVIs.