Skip to yearly menu bar Skip to main content


Poster

Efficient Algorithms for Smooth Minimax Optimization

Kiran Thekumparampil · Prateek Jain · Praneeth Netrapalli · Sewoong Oh

East Exhibition Hall B, C #213

Keywords: [ Optimization ] [ Optimization -> Convex Optimization; Optimization ] [ Non-Convex Optimization ]


Abstract: This paper studies first order methods for solving smooth minimax optimization problems minxmaxyg(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 direct optimal algorithm combining Mirror-Prox and Nesterov's AGD, and show that it can find global optimum in O~(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 O~(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., minxmax1imfi(x), with nonconvex fi(), to obtain convergence rate of O(m1/3logm/k1/3).

Live content is unavailable. Log in and register to view live content