The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization

By Constantinos Daskalakis, Ioannis Panageas. 2018

294 citations recorded by the source corpus.

Motivated by applications in Optimization, Game Theory, and the training of Generative Adversarial Networks, the convergence properties of first order methods in min-max problems have received extensive study. It has been recognized that they may cycle, and there is no good understanding of their limit points when they do not. When they converge, do they converge to local min-max solutions? We characterize the limit points of two basic first order methods, namely Gradient Descent/Ascent (GDA) and Optimistic Gradient Descent Ascent (OGDA). We show that both dynamics avoid unstable critical points for almost all initializations. Moreover, for small step sizes and under mild assumptions, the set of \{OGDA\}-stable critical points is a superset of \{GDA\}-stable critical points, which is a superset of local min-max solutions (strict in some cases). The connecting thread is that the behavior of these dynamics can be studied from a dynamical systems perspective.

Subfields: Artificial Intelligence, 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 Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Negative Momentum for Improved Game Dynamics (2018, methodology): “For instance, some stable stationary points of the dynamics may not be (local) Nash equilibria (Adolphs et al., 2018; Daskalakis and Panageas, 2018).”
The complexity of constrained min-max optimization (2020, background): “Several kinds of those have been proposed in the literature [14, 24, 30].”
What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization? (2019, methodology): “Most previous work [e.g., Daskalakis and Panageas, 2018, Mazumdar and Ratliff, 2018, Adolphs et al., 2018] studied a notion of local Nash equilibrium which replaces all the global minima or maxima in the deﬁnition of Nash equilibrium by their local counterparts.”
Accelerating Smooth Games by Manipulating Spectral Shapes (2020, methodology): “…papers (Korpelevich, 1976; Tseng, 1995) and many recent ones (Nemirovski, 2004; Chen et al., 2014; Palaniappan and Bach, 2016; Mescheder et al., 2017; Gidel et al., 2019a,b; Daskalakis et al., 2018; Mokhtari et al., 2019; Azizian et al., 2019) suggest new methods and provide better upper bounds.”
ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems and GANs (2019, unknown): “Optimism is a simple modiﬁcation to remedy the cycling behavior of simGD, which can occur even under the bilinear convex-concave setup [8, 9, 10, 36, 17, 28, 42, 50].”
On the convergence of single-call stochastic extra-gradient methods (2019, background): “2 At the local level, the geometric convergence results discussed above echo a surge of interest in local convergence guarantees of optimization algorithms applied to games and saddle-point problems, see e.g., [1, 3, 15, 24] and references therein.”
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, background): “Our focus in the current paper is the simplest such notion, namely ﬁrst-order local optimality, where, despite the simplicity, many general challenges arise [14,35].”
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 ”
Minmax Optimization: Stable Limit Points of Gradient Descent Ascent are Locally Optimal (2019, methodology): “Theorem 22 (Daskalakis and Panageas [2018]) .”
On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach (2019, background): “First, it has undesirable convergence properties: it fails to converge to some local minimax and can converge to ﬁxed points that are not local minimax (Jin et al., 2019; Daskalakis and Panageas, 2018).”
Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods (2019, methodology): “This failure was fixed by adding negative momentum or by using primal-dual methods proposed by [22, 21, 8, 13, 15, 33].”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, background): “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”
Solving Weakly-Convex-Weakly-Concave Saddle-Point Problems as Successive Strongly Monotone Variational Inequalities (2018, background): “Daskalakis & Panageas [23] analyzed the limiting behavior of two gradient-based dynamics, namely gradient dynamics and optimistic gradient dynamics for a min-max problem with a twice-continuously diﬀerentiable objective function with Lipschitz continuous gradient and no constraint.”
Making Method of Moments Great Again? -- How can GANs learn the target distribution (2020, background): “2 Related works Generative Adversarial Networks The works [62, 41, 58, 28, 29, 37, 54, 61, 55] considered 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 b”
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2019, methodology): “Most recent work aims at defining a notion of goodness or the development of new procedures for reducing oscillations [Daskalakis and Panageas, 2018b, Adolphs et al., 2018, Mazumdar et al., 2019] and speeding up the convergence of gradient dynamics [Heusel et al., 2017, Balduzzi et al., 2018,…”
Convergence of Learning Dynamics in Stackelberg Games (2019, background): “The select few recent works in the machine learning literature on learning in games considering a hierarchical decision-making structure exclusively focus on zero-sum games [18, 28, 34, 42, 46], unlike our work, which extends to general-sum games.”