On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems

By Tianyi Lin, Chi Jin, Michael I. Jordan. 2019

610 citations recorded by the source corpus.

We consider nonconvex-concave minimax problems, $\min_{\mathbf{x}} \max_{\mathbf{y} \in \mathcal{Y}} f(\mathbf{x}, \mathbf{y})$, where $f$ is nonconvex in $\mathbf{x}$ but concave in $\mathbf{y}$ and $\mathcal{Y}$ is a convex and bounded set. One of the most popular algorithms for solving this problem is the celebrated gradient descent ascent (GDA) algorithm, which has been widely used in machine learning, control theory and economics. Despite the extensive convergence results for the convex-concave setting, GDA with equal stepsize can converge to limit cycles or even diverge in a general setting. In this paper, we present the complexity results on two-time-scale GDA for solving nonconvex-concave minimax problems, showing that the algorithm can find a stationary point of the function $\Phi(\cdot) := \max_{\mathbf{y} \in \mathcal{Y}} f(\cdot, \mathbf{y})$ efficiently. To the best our knowledge, this is the first nonasymptotic analysis for two-time-scale GDA in this setting, shedding light on its superior practical performance in training generative adversarial networks (GANs) and other real applications.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Controlled Sparsity via Constrained Optimization or: How I Learned to Stop Tuning Penalties and Love Constraints (2022, methodology): “A commonly used approach to optimize this Lagrangian is simultaneous gradient descent on ( ˜ θ , ϕ ) and projected (to R + ) gradient ascent on λ co [30]: λ t +1 co ≜ max 0 , ˆ λ t +1 The gradient update for λ co matches the value of the violation of each constraint.”
Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “…for the analysis of stochastic algorithms, papers assume either bounded operators [Nemirovski et al., 2009, Abernethy et al., 2021] or bounded variance [Juditsky et al., 2011, Yang et al., 2020, Lin et al., 2020a, Luo et al., 2020, Tran Dinh et al., 2020] and growth condition [Lin et al., 2020b].”
GenDICE: Generalized Offline Estimation of Stationary Values (2020, background): “For the general neural network for (τ, f), although there are several progress recently (Lin et al., 2018; Jin et al., 2019; Lin et al., 2019) about the convergence to a stationary point or local minimum, it remains a largely open problem to quantify the optimization error, which is out of the…”
There is Strength in Numbers: Avoiding the Hypothesis-Only Bias in Natural Language Inference via Ensemble Adversarial Training (2020, methodology): “(1) using gradient reversal (Ganin and Lem-pitsky, 2015b), which leads to an optimisation procedure equivalent to the popular gradient descent ascent algorithm (Lin et al., 2019).”
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, background): “This work has focused on attaining improved rates [3, 4,19,21,26,29–31,41,45,48] and/or obtaining last-iterate convergence guarantees [1,2,13–15,20,22,28,35,37,38,43].”
When can Wasserstein GANs minimize Wasserstein Distance? (2020, background): “2 Related works Generative Adversarial Networks The works [29, 16, 25, 9, 10, 13, 21, 28, 22] considers either local convergence property of the GAN training, or the global convergence property when the objective is convex-concave However, there is no clear evidence of how the local property can be ”
Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems (2020, background): “Indeed, it is common to use diﬀerent learning rates for x and y in GDA algorithms for nonconvex minimax problems; see e.g., Jin et al. [2019] and Lin et al. [2019].”
Convergence of Learning Dynamics in Stackelberg Games (2019, background): “Formal convergence guarantees to minimax equilibria in zero-sum games characterizing the limiting behavior of simultaneous individual gradient descent with timescale separation were recently obtained [28, 34].”
AUC Maximization in the Era of Big Data and AI: A Survey (2022, methodology): “SGDA [100] Single-loop 𝑂 ( 1 / 𝜖 2 ) 𝑂 ( 1 / 𝜖 4 ) General No PDAda [56] Single-loop 𝑂 ( 1 ) 𝑂 ( 1 / 𝜖 4 ) General Yes AccMDA [75] Single-loop 𝑂 ( 1 ) 𝑂 ( 1 / 𝜖 3 ) Lipschitz No Stoc-AGDA [182] Single-loop Yes propose a single-loop algorithm named AccMDA to enjoy a fast rate of 𝑂 ( 1 / 𝜖”
Hybrid Variance-Reduced SGD Algorithms For Minimax Problems with Nonconvex-Linear Function (2020, background): “Although (1) is a special case of a general model in [17, 18, 40], it almost covers all examples in [17, 40].”