论文标题
凸 - 孔洞中最小最大优化和单调变化不平等的高阶方法
Higher-order methods for convex-concave min-max optimization and monotone variational inequalities
论文作者
论文摘要
我们为受约束的凸孔concave min-max问题和单调变异不等式提供提高的收敛速率，具有较高的平滑度。在最低限度的设置中，$ p^{th} $ - 订单衍生物是Lipschitz的连续，我们给出了一种算法较高ordrodermirrorprox，它实现了$ o的迭代复杂性（1/t^{\ frac {p+1}} {2}}}} $时，可以访问point $p。我们给出了弱单调变异不平等问题的类似率。对于$ p> 2 $，我们的结果改善了Nemirovski的一阶镜像方法的迭代复杂性[2004]和Monteiro and Svaiter [2012]的二阶方法。我们进一步实例化了整个算法，以无约束的$ p = 2 $ case。
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.
