Higher-order methods for convex-concave min-max optimization and monotone variational inequalities
| Title: | Higher-order methods for convex-concave min-max optimization and monotone variational inequalities |
|---|---|
| Authors: | Bullins, Brian, Lai, Kevin A. |
| Publication Year: | 2020 |
| Collection: | Computer Science Mathematics Statistics |
| Subject Terms: | Mathematics - Optimization and Control, Computer Science - Machine Learning, Statistics - Machine Learning |
| More Details: | 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. |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2007.04528 |
| Accession Number: | edsarx.2007.04528 |
| Database: | arXiv |
| Description not available. |