Minmax Optimization: Stable Limit Points of Gradient Descent Ascent are Locally Optimal

By Chi Jin, Praneeth Netrapalli, Michael I. Jordan. 2019

87 citations recorded by the source corpus.

Minmax optimization, especially in its general nonconvex-nonconcave formulation, has found extensive applications in modern machine learning frameworks such as generative adversarial networks (GAN), adversarial training and multi-agent reinforcement learning. Gradient-based algorithms, in particular gradient descent ascent (GDA), are widely used in practice to solve these problems. Despite the practical popularity of GDA, however, its theoretical behavior has been considered highly undesirable. Indeed, apart from possiblity of non-convergence, recent results (Daskalakis and Panageas, 2018; Mazumdar and Ratliff, 2018; Adolphs et al., 2018) show that even when GDA converges, its stable limit points can be points that are not local Nash equilibria, thus not game-theoretically meaningful. In this paper, we initiate a discussion on the proper optimality measures for minmax optimization, and introduce a new notion of local optimality---local minmax---as a more suitable alternative to the notion of local Nash equilibrium. We establish favorable properties of local minmax points, and show, most importantly, that as the ratio of the ascent step size to the descent step size goes to infinity, stable limit points of GDA are exactly local minmax points up to degenerate points, demonstrating that all stable limit points of GDA have a game-theoretic meaning for minmax problems.

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

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

Citations in the corpus

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…”
Rényi Fair Inference (2019, methodology): “Several algorithms have been recently proposed for solving such non-convex min-max optimization problems Sanjabi et al. (2018); Nouiehed et al. (2019); Jin et al. (2019).”
Convergence of Learning Dynamics in Stackelberg Games (2019, result): “[21] proposes a local minmax equilibrium notion that is similar to the Stackelberg equilibrium notion we adopt.”
Tilted Empirical Risk Minimization (2020, methodology): “While minimizing the k-loss is more desirable than ERM in many applications, the k-loss (or the VaR) is non-smooth (and generally non-convex), and hence requires the use of non-smooth or difference-of-convex optimization techniques [27, 44, 45].”
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2019, methodology): “In contrast to [20], we obtain an nonasymptotic result that ηy/ηx = O(ǫ4) by exploiting the problem structure with new technique.”
A Primal Dual Formulation For Deep Learning With Constraints (2019, methodology): “Convergence to local min-max points (Jin et al. [2019]) in the limit follows from the theory of min-max optimization.”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “As a consequence, most of the convergence results are local (Mescheder et al., 2017; Mazumdar and Ratliff, 2018; Adolphs et al., 2018; Daskalakis and Panageas, 2018; Mertikopoulos et al., 2019; Fiez et al., 2019; Mazumdar et al., 2019; Jin et al., 2019), in the sense that they address the convergenc”
Variance Reduction for Matrix Games (2019, background): “In recent years, minimax formulations for neural network training rose to prominence [14, 20], leading to intense interest in algorithms for solving large scale minimax games [10, 13, 18, 9, 16, 21].”
Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods (2019, methodology): “In convex-concave games, such a Nash equilibrium always exists [28] and several algorithms were proposed to find Nash equilibria [23, 26].”