Efficient Algorithms for Smooth Minimax Optimization

Kiran Koshy Thekumparampil, Prateek Jain, Praneeth Netrapalli, Sewoong Oh

Abstract

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 algorithm combining Mirror-Prox and Nesterov's AGD, and show that it can find global optimum in $\tilde{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 $\tilde{O}(1/k^{1/3})$ 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(\log m)^{3/2}/k^{1/3})$ total gradient evaluations for finding a stationary point.

Introduction

Minimax optimization—the "game" of finding a point that minimizes a maximum—is the engine behind some of the most exciting developments in modern AI, from training Generative Adversarial Networks (GANs) to building robust machine learning models. However, these problems are notoriously difficult to solve efficiently.

In their paper "Efficient Algorithms for Smooth Minimax Optimization," researchers from UIUC, Microsoft Research, and the University of Washington introduce new algorithms that significantly accelerate convergence rates for two critical classes of minimax problems, matching theoretical lower bounds and outperforming previous state-of-the-art methods.

Problem Formulation

The paper focuses on smooth minimax problems of the form $\min_x \max_y g(x, y)$. While the "convex-concave" version (where $g$ is convex in $x$ and concave in $y$) is well-understood with a standard convergence rate of $O(1/k)$, many real-world applications do not fit this standard model:

  1. Strongly Convex-Concave: If $g$ is strongly convex in $x$, theory suggests faster convergence should be possible. However, existing general algorithms were previously limited to $O(1/k)$.
  2. Nonconvex-Concave: In many machine learning tasks (like GANs), the objective is nonconvex in the parameters $x$. Finding a global optimum is NP-hard, so researchers aim for "stationary points." Previous best rates for finding these points were a sluggish $O(1/k^{1/5})$.

Proposed Methods

The authors introduce two primary algorithmic frameworks to address these gaps:

  • DIAG (Dual Implicit Accelerated Gradient): This is the core innovation for the strongly convex setting. It combines Mirror-Prox (effective for minimax) and Nesterov’s Accelerated Gradient Descent (AGD) (effective for fast convex optimization). The algorithm uses an implicit update step where it simultaneously finds a new $x$ that minimizes the function and a new $y$ that corresponds to an accelerated step.
  • Prox-DIAG: For the nonconvex setting, the authors use an inexact proximal point method. They exploit the fact that even if $g(x, y)$ is nonconvex in $x$, the "max-function" $f(x) = \max_y g(x, y)$ is often weakly convex. By adding a quadratic regularization term, they transform the difficult nonconvex problem into a sequence of strongly convex-concave sub-problems, which are then solved efficiently using DIAG.

Key Results and Theoretical Impact

The primary contribution of this work is the significant improvement in convergence rates across different settings. As summarized in the table below, the proposed algorithms either match theoretical lower bounds or substantially outperform previous state-of-the-art (SOTA) methods.

Comparison of convergence rates for different settings against previous state-of-the-art and lower bounds.
  • Strongly Convex-Concave: The DIAG algorithm improves the convergence rate from $O(1/k)$ to $\tilde{O}(1/k^2)$. This matches the known theoretical lower bound $\Omega(k^{-2})$, effectively "solving" this class of problems up to a logarithmic factor.
  • Nonconvex-Concave: The Prox-DIAG framework improves the rate for finding stationary points from $O(1/k^{1/5})$ to $\tilde{O}(1/k^{1/3})$.
  • Finite Max-Type Problems: For problems involving the maximum of $m$ nonconvex functions, the authors achieved a rate of $O(m(\log m)^{3/2}/k^{1/3})$ total gradient evaluations.

Limitations and Future Work

While these results represent a major step forward, several avenues for future research remain:

  • Euclidean Focus: The current analysis is primarily for Euclidean spaces. Extending this to non-Euclidean settings using Bregman divergences is a natural next step.
  • Condition Number Dependence: The authors note that the dependence of DIAG on the "condition number" (the ratio of smoothness to strong convexity) might be sub-optimal and could be improved.
  • Stochastic Setting: This paper focuses on deterministic gradients. Extending these accelerated rates to the stochastic setting (where we only have noisy estimates of the gradient, as in deep learning) remains a major open challenge.

Summary updated

Abstract

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 algorithm combining Mirror-Prox and Nesterov's AGD, and show that it can find global optimum in $\tilde{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 $\tilde{O}(1/k^{1/3})$ 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(\log m)^{3/2}/k^{1/3})$ total gradient evaluations for finding a stationary point.
BibTeX
@inproceedings{thekumparampil2019efficient,
  author = {Kiran Koshy Thekumparampil and Prateek Jain and Praneeth Netrapalli and Sewoong Oh},
  title = {{Efficient Algorithms for Smooth Minimax Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=7fHJqqq9UQ9},
}
Figure