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

Abstract

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.

Appeared in NeurIPS 2018. The new version fixes typos

References in corpus (6)

• Online Learning with Predictable Sequences
• First-order Methods Almost Always Avoid Saddle Points
• Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos
• Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
• Natural Selection as an Inhibitor of Genetic Diversity: Multiplicative Weights Updates Algorithm and a Conjecture of Haploid Genetics
• Rock-Paper-Scissors, Differential Games and Biological Diversity

Cited by in corpus (3)

• Accelerating Smooth Games by Manipulating Spectral Shapes
• Towards a Better Understanding and Regularization of GAN Training Dynamics
• On the Impossibility of Global Convergence in Multi-Loss Optimization