Efficient Algorithms for Smooth Minimax Optimization

Code

• github.com/POLane16/DIAG
  Officialnone★ 0
• github.com/tkkiran/DIAG
  none★ 0

Abstract

This paper studies first order methods for solving smooth minimax optimization problems _x _y 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),\ y, we propose a new algorithm combining Mirror-Prox and Nesterov's AGD, and show that it can find global optimum in O(1/k^2) 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/k^1/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/k^1/5). Finally, we instantiate our result for finite nonconvex minimax problems, i.e., _x _1 i m f_i(x), with nonconvex f_i(), to obtain convergence rate of O(m( m)^3/2/k^1/3) total gradient evaluations for finding a stationary point.

Reproductions