Higher-order methods for convex-concave min-max optimization and monotone variational inequalities
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Beyond first-order methods for non-convex non-concave min-max optimization
We propose a study of structured non-convex non-concave min-max problems which goes beyond standard first-order approaches. Inspired by the tight understanding established in recent works [Adil et al., 2022, Lin and Jord…
Generalized Optimistic Methods for Convex-Concave Saddle Point Problems
The optimistic gradient method has seen increasing popularity for solving convex-concave saddle point problems. To analyze its iteration complexity, a recent work [arXiv:1906.01115] proposed an interesting perspective th…
Second-order methodsNear-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization
We study the problem of finding a near-stationary point for smooth minimax optimization. The recent proposed extra anchored gradient (EAG) methods achieve the optimal convergence rate for the convex-concave minimax probl…
Stochastic OptimizationSolving Convex-Concave Problems with $\tilde{\mathcal{O}}(ε^{-4/7})$ Second-Order Oracle Complexity
Previous algorithms can solve convex-concave minimax problems $\min_{x \in \mathcal{X}} \max_{y \in \mathcal{Y}} f(x,y)$ with $\mathcal{O}(\epsilon^{-2/3})$ second-order oracle calls using Newton-type methods. This resul…
EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimization
Min-max optimization arises in many domains such as game theory, adversarial machine learning, etc. For these problems, gradient-based methods are well understood and enjoy strong guarantees. However, in the absence of c…