Timezone: »

 
Poster
Efficient Algorithms for Smooth Minimax Optimization
Kiran Thekumparampil · Prateek Jain · Praneeth Netrapalli · Sewoong Oh

Thu Dec 12 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #213
in Optimization -- Non-Convex Optimization »
This paper studies first order methods for solving smooth minimax optimization problems $\min_x \max_y g(x,y)$ where $g(\cdot,\cdot)$ is smooth and $g(x,\cdot)$ is concave for each $x$. In terms of $g(\cdot,y)$, we consider two settings -- strongly convex and nonconvex -- and improve upon the best known rates in both. For strongly-convex $g(\cdot, y),\ \forall y$, we propose a new direct optimal algorithm combining Mirror-Prox and Nesterov's AGD, and show that it can find global optimum in $\widetilde{O}\left(1/k^2 \right)$ 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 $\widetilde{O}\left(1/k^{1/3} \right)$ rate for finding stationary points in the nonconvex setting where $g(\cdot, y)$ can be nonconvex. This improves over current best-known rate of $O(1/k^{1/5})$. Finally, we instantiate our result for finite nonconvex minimax problems, i.e., $\min_x \max_{1\leq i\leq m} f_i(x)$, with nonconvex $f_i(\cdot)$, to obtain convergence rate of $O(m^{1/3}\sqrt{\log m}/k^{1/3})$.
Keywords: Optimization · Non-Convex Optimization · Optimization -> Convex Optimization; Optimization
[ Paper]  [ Slides] 

Author Information

Kiran Thekumparampil (Univ. of Illinois at Urbana-Champaign)
Prateek Jain (Microsoft Research)
Praneeth Netrapalli (Microsoft Research)
Sewoong Oh (University of Washington)

More from the Same Authors