Higher-order methods for convex-concave min-max optimization and monotone variational inequalities
This work addresses optimization efficiency for researchers and practitioners in machine learning and operations research, but it is incremental as it builds on existing higher-order methods with specific improvements.
The paper tackles the problem of improving convergence rates for convex-concave min-max optimization and monotone variational inequalities by developing a higher-order method, achieving an iteration complexity of O(1/T^{(p+1)/2}) for p-th order smoothness, which improves upon prior first and second-order methods.
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 HigherOrderMirrorProx 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 of Nemirovski [2004] and the second-order method of Monteiro and Svaiter [2012]. We further instantiate our entire algorithm in the unconstrained $p=2$ case.