The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization
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.
The paper studies stability of gradient and optimistic gradient dynamics for C^2 saddle-point problems.  The main contribution of the paper can be summarized in two results (stated in the inclusion following line 83): - local saddles are stable for GDA (under Assumption 8.1) - stable equilibria of GDA are also stable for OGDA. (note that results on unstable critical points were previously known).  Quality: The results are interesting, and the paper is well written. There are some typos in the proofs, but I believe these are omissions that can be corrected, rather than major flaws.  Significance: I would love to see further discussion of the consequences of this result, and its relevance to the NIPS community, both theoreticians and practitioners. For example, do these results suggest that GDA should be preferred to OGDA (since the latter has a larger equilibrium set)? Does the analysis extend to time-varying step sizes? In the concluding remarks, the authors mention that some saddle points (local min max) can be better than others. Can the authors expand on how the quality of an equilibrium can be measured?  Originality: It takes some effort to tease out the contributions of the paper from existing results. Existing results should be cited but not part of the main paper (they can potentially be moved to the appendix) in favor of an expanded discussion of Theorem 1.10 and its consequences. - Theorems 1.11, 2.2 and 3.2 (that a dynamical system a.s. does not converge to an unstable equilibrium when the Hessian is invertible) are known. Note that the particular form of the dynamics is irrelevant to the result, only the fact that the spectral radius of the Jacobian at the equilibrium is greater than one. I don't think one can claim this is a contribution of this paper. - Similarly, Corollary 2.3 and 3.3 are immediate consequences of these known results, and are stated without discussion. I do not see what they bring to the picture. - The literature review needs to be expanded. Similar techniques have been used to prove stability of gradient algorithms (e.g. [1]), and for GAN training [2], which seems particularly relevant, since they use similar techniques (analyzing the Jacobian at the equilibrium, albeit for continuous time dynamics) and this paper is motivated by GAN training.  Typos and minor suggestions: - Line 18: "compact and concave subsets": do you mean convex? - In the analysis of OGDA dynamics, what is the advantage of introducing the functions F and F'? One can simply express the dynamics (and the proof of Lemma 3.1 in the appendix) in terms of f. Defining F, F' introduces unnecessary additional notation. - Second experiment (4.2): how is this experiment related to the results of the paper? - Statement of Theorem B.1: what is E? What is Dg(x^*), is this the Jacobian? Please use notation consistent with the rest of the paper. - Please define "C^r embedded disk" in Theorem B.1. - In the proof of Theorem 2.2 and 3.2, you can extract a finite sub-cover simply by the compactness assumption. Why mention second-countability? - In the proof of Lemma 2.4: I + a H should be I + \alpha H. The proof only provides an upper bound on the eigenvalues of H. Note that this is not sufficient, a lower bound is also needed to conclude. - Proof of Lemma 2.7: Incomplete sentence "Hence we conclude that Re(\lambda)". There is also a missing factor 2 in the expression of the eigenvalue magnitude.  [1] L. Lessard, B. Recht and A. Packard. Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints. SIAM Journal on Optimization - 26(1): 57-95 [2] V. Nagarajan and J. Zico Kolter, Gradient descent GAN optimization is locally stable. NIPS 2017.  ======== post rebuttal Thank you for your responses, and for the corrections to the proofs. Regarding Theorem 2.2, 3.2 and Corollaries 2.3 and 3.3: I agree that proving the invertibility of the Jacobian for these particular dynamics is new, but the rest of the argument is identical to previous results, and this minor contribution hardly justifies stating two lemmas, two theorems and two corollaries, especially when much of this space can be used to improve the discussion of the new results. I strongly encourage the authors to move these to the supplement, and clarify that these mostly follow existing arguments.