%0 Journal Article %1 bullins2020higherorder %A Bullins, Brian %A Lai, Kevin A. %D 2020 %K game-theory optimization readings variational %T Higher-order methods for convex-concave min-max optimization and monotone variational inequalities %U http://arxiv.org/abs/2007.04528 %X 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^p+12)$ 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.

@article{bullins2020higherorder, 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 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.}, added-at = {2020-07-16T12:02:39.000+0200}, author = {Bullins, Brian and Lai, Kevin A.}, biburl = {https://www.bibsonomy.org/bibtex/2c83b0a341c56af01a80724827e7dcc21/kirk86}, description = {[2007.04528] Higher-order methods for convex-concave min-max optimization and monotone variational inequalities}, interhash = {97909ac38af723da07fdf58a7fbe1070}, intrahash = {c83b0a341c56af01a80724827e7dcc21}, keywords = {game-theory optimization readings variational}, note = {cite arxiv:2007.04528}, timestamp = {2020-07-16T12:02:39.000+0200}, title = {Higher-order methods for convex-concave min-max optimization and monotone variational inequalities}, url = {http://arxiv.org/abs/2007.04528}, year = 2020 }