Efficient Algorithms for Smooth Minimax Optimization

This paper studies first order methods for solving smooth minimax optimization problems minₓ maxy g(x,y) where g(·,·) is smooth and g(x,·) is concave for each x. In terms of g(·,y), we consider two settings -- strongly convex and nonconvex -- and improve upon the best known rates in both. For strongly-convex g(·, y),\ ∀ y, we propose a new algorithm combining Mirror-Prox and Nesterov's AGD, and show that it can find global optimum in Õ(1/k²) iterations, improving over current state-of-the-art rate of $O(1/k)$. We use this result along with an inexact proximal point method to provide Õ(1/k1/3) rate for finding stationary points in the nonconvex setting where g(·, y) can be nonconvex. This improves over current best-known rate of O(1/k1/5). Finally, we instantiate our result for finite nonconvex minimax problems, i.e., minₓ max1≤ i≤ m fᵢ(x), with nonconvex fᵢ(·), to obtain convergence rate of O(m(log m)3/2/k1/3) total gradient evaluations for finding a stationary point.