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
]
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., minxmax1≤i≤mfi(x), with nonconvex fi(⋅), to obtain convergence rate of O(m1/3√logm/k1/3).
Live content is unavailable. Log in and register to view live content