Higher-order methods for convex-concave min-max optimization and monotone variational inequalities

2020/07/09 by Bullins, Brian, Lai, Kevin A. · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2007.04528

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^(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.

Cited by

• On Non-Monotone Variational Inequalities

Related

• Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities
• Exploiting higher-order derivatives in convex optimization methods
• Beyond first-order methods for non-convex non-concave min-max optimization
• Improved Algorithms for Convex-Concave Minimax Optimization
• Min-Max Optimization Is Strictly Easier Than Variational Inequalities