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 where is smooth and is concave for each . In terms of , we consider two settings -- strongly convex and nonconvex -- and improve upon the best known rates in both. For strongly-convex , we propose a new direct optimal algorithm combining Mirror-Prox and Nesterov's AGD, and show that it can find global optimum in iterations, improving over current state-of-the-art rate of . We use this result along with an inexact proximal point method to provide rate for finding stationary points in the nonconvex setting where can be nonconvex. This improves over current best-known rate of . Finally, we instantiate our result for finite nonconvex minimax problems, i.e., , with nonconvex , to obtain convergence rate of .
Live content is unavailable. Log in and register to view live content