Efficient Algorithms for Smooth Minimax Optimization

This paper studies first order methods for solving smooth minimax optimization problems minx 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), forall y, we propose a new algorithm combining Mirror-Prox and Nesterov's AGD, and show that it can find global optimum in tildeO(1/k2) 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 tildeO(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., minx max1≤ i≤ m fi(x), with nonconvex fi(·), to obtain convergence rate of O(m(log m)3/2/k1/3) total gradient evaluations for finding a stationary point.