Higher-Order Methods for Convex-Concave Min-Max Optimization and Monotone Variational Inequalities

Abstract

We provide improved convergence rates for constrained convex-concave min-max problems and monotone variational inequalities with higher-order smoothness. In min-max settings where the $p$th-order derivatives are Lipschitz continuous, we give an algorithm that achieves an iteration complexity of $O(1/T^{\frac{p+1}{2}})$ when given access to an oracle for finding a fixed point of a $p$th-order equation. We give analogous rates for the weak monotone variational inequality problem. For $p>2$, our results improve upon the iteration complexity of the first-order Mirror Prox method by Nemirovski [SIAM J. Optim., 15 (2004), pp. 229--251] and the second-order method by Monteiro and Svaiter [SIAM J. Optim., 22 (2012), pp. 914--935]. We further instantiate our entire algorithm in the unconstrained $p=2$ case.