PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Constantinos Daskalakis, Ioannis Panageas

arXiv:1807.03907v2math.OCcs.LGstat.ML

TL;DR

The paper addresses the limited understanding of last-iterate limit points for GDA and OGDA in min-max optimization, where discrete-time dynamics may cycle. It analyzes these methods through dynamical-systems techniques and shows that unstable critical points are avoided for almost all initializations, while stable-point inclusions hold for small step sizes under stated assumptions. These inclusions can be strict, so stability is broader than local min-max structure.

  • Problem

    Last-iterate limit points of GDA and OGDA are poorly understood in general min-max optimization, especially when discrete-time dynamics cycle or lack convergence guarantees.

  • Method

    The paper analyzes GDA and OGDA locally around critical points using Jacobian spectral analysis, local diffeomorphisms, center-stable manifolds, and an auxiliary dynamical system for OGDA.

  • Results

    Both dynamics avoid unstable critical points for almost all initializations; for small step sizes, OGDA-stable critical points contain GDA-stable ones, which contain suitable local min-max points, with strict inclusions in some cases.

  • Takeaways & Limitations

    Convergence of these first-order dynamics does not restrict limit points to local min-max solutions, and OGDA admits a broader stable set than GDA under the stated conditions.

  • Takeaways & Limitations

    Some OGDA results require an invertible Hessian and therefore do not apply to generic bilinear objectives with a nonsquare matrix.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies whether GDA and OGDA converge to meaningful limit points in min-max optimization, where discrete-time methods may cycle or lack last-iterate guarantees. Using dynamical-systems analysis, it characterizes stability, instability avoidance, and relations among stable critical points.

  • Motivation: GDA and OGDA are studied because discrete-time min-max dynamics may cycle, while known guarantees often concern average iterates rather than last-iterate convergence.The paper targets general, including non-convex-concave, objectives motivated partly by GAN training.
  • Research questions: The paper asks whether stable limit points are local min-max solutions and how GDA- and OGDA-stable points relate.
  • Dynamics: GDA updates x by descent and y by ascent using the current gradients, whereas OGDA also incorporates gradients from the previous iterate.
  • Main results: Both dynamics avoid their respective unstable fixed points for almost all initializations, under the paper’s stated differentiability, Lipschitz, and OGDA assumptions.The exceptional initialization sets have measure zero.
  • Main results: For sufficiently small step sizes, local min-max points satisfying Assumption 1.8 are GDA-stable, but the inclusion can be strict in both directions of the broader stability relationships.Strongly local min-max points satisfy Assumption 1.8; some GDA-stable points are not local min-max.
  • Main results: For 0 < α < 1/(2L), every GDA-stable fixed point is OGDA-stable, and the inclusion is strict: some points are OGDA-stable but not GDA-stable.

2 Analysis of Gradient Descent/Ascent

The paper analyzes local GDA behavior through Jacobian stability and dynamical-systems tools, showing that unstable critical points attract only a measure-zero set of initializations. It characterizes how GDA stability relates to local min-max structure, including strict separations.

  • Analyzing GDA: Under Lipschitz-gradient and small-step assumptions, the GDA update is a local diffeomorphism, enabling center-stable manifold analysis.The analysis assumes a twice-differentiable objective and 0 < α < 1/L.
  • Avoiding unstable points: The stable set of every GDA-unstable critical point, and their union, has Lebesgue measure zero.This extends to non-isolated critical points under the stated argument.
  • GDA stability and local min-max: Local min-max critical points with real Hessian-derived eigenvalues are GDA-stable for sufficiently small step sizes.Strongly local min-max points are attracting under GDA for sufficiently small α.
  • GDA stability and local min-max: GDA-stable critical points can include points that are not local min-max solutions, so the converse of local-min-max stability fails.The paper gives an explicit two-variable example whose dynamics converge to a non-local-min-max critical point.
  • GDA stability and local min-max: Some local min-max points are not GDA-stable when the relevant matrix has imaginary eigenvalues.For f(x, y) = xy, the Jacobian eigenvalues are 1 ± αi, whose magnitudes exceed one for every α > 0.

3 Optimistic Gradient Descent/Ascent

The paper reformulates OGDA as a higher-dimensional dynamical system because its memory makes direct analysis more difficult. It then uses Jacobian and eigenvalue arguments to show avoidance of unstable points and a strict stability enlargement over GDA.

  • Dynamical-system formulation: OGDA is represented by a four-component dynamical system whose state records current and previous iterates.The construction satisfies (x_{t+1}, y_{t+1}, x_t, y_t) = g(x_t, y_t, x_{t-1}, y_{t-1}).
  • Dynamical-system formulation: Under Assumption 1.7 and a small-step Lipschitz-gradient condition, the OGDA update map is a local diffeomorphism.The proof establishes invertibility of its Jacobian using the invertibility assumption on the Hessian.
  • Avoiding unstable points: The stable set of every OGDA-unstable critical point, and their union, has Lebesgue measure zero.The result also applies when the critical points are non-isolated.
  • Relating GDA and OGDA stability: For 0 < α < 1/(2L), every GDA-stable critical point is OGDA-stable.The result follows by mapping GDA Jacobian eigenvalues to roots governing the OGDA Jacobian.
  • Relating GDA and OGDA stability: The inclusion is strict: some critical points are OGDA-stable but not GDA-stable.For f(x, y) = xy, (0, 0) is GDA-unstable but OGDA-stable when 0 < α < 1/2.
  • Scope boundary: Some OGDA stability results do not apply to generic bilinear objectives when the matrix is nonsquare because the Hessian is not invertible.The stated results apply to bilinear objectives only when the matrix is square and invertible.

4 Examples and Experiments

The experiments construct low-dimensional examples separating GDA stability from local min-max structure and compare GDA and OGDA attraction in higher dimensions.

  • 4 Examples and Experiments: The two-dimensional experiment constructs critical points that are local min-max, GDA/OGDA-stable, and GDA/OGDA-unstable.The function combines polynomial components so its behavior differs near selected critical points.
  • 4 Examples and Experiments: GDA stability can occur without local min-max structure, while another constructed critical point is GDA-unstable and not local min-max.The example uses f1 near (0, 0) and f2 near (1, 1) to realize these cases.
  • 4.2 Higher dimensional: The higher-dimensional experiment evaluates convergence from 10000 uniformly random initializations in a five-dimensional min-max setting.The construction is based on a random polynomial and a function locally behaving like a local min-max function at the origin.
  • 4.2 Higher dimensional: 87% of initial points converge to 0 in OGDA, compared with 79.3% in GDA.The experiment characterizes this as a slightly larger OGDA region of attraction.
  • 4 Examples and Experiments: Table 1 summarizes the critical points of the constructed function.The supplied table passage provides the table’s caption but no numerical entries.

5 Conclusion

The paper studies the local behavior of GDA and OGDA around critical points and finds that these methods need not converge only to local min-max solutions. It leaves the quality of such solutions as an open question.

  • 5 Conclusion: The paper analyzes the local behavior of GDA and OGDA dynamics around critical points.
  • 5 Conclusion: The analyzed first-order methods can fail to converge exclusively to local min-max solutions.The conclusion notes that local min-max solutions may differ in quality and that guaranteeing good min-max solutions remains open.
  • 5 Conclusion: Guaranteeing good solutions in min-max problems is identified as an important open question.

A Missing theorems and proofs

The appendix proves avoidance of unstable critical points using stable-manifold arguments for the GDA and OGDA update maps. The unstable points’ stable sets are shown to have measure zero.

  • A Missing theorems and proofs: A center-stable manifold is tangent to the eigenspace associated with Jacobian eigenvalues of magnitude at most one.The theorem provides a local invariant manifold near a fixed point.
  • A Missing theorems and proofs: The proofs assume that the GDA and OGDA update rules are diffeomorphisms and apply a generic stable-manifold argument.The update maps are treated as C2 dynamical systems.
  • A Missing theorems and proofs: Points converging to unstable critical points eventually enter one of their associated neighborhoods and lie in a corresponding center-stable manifold.
  • A Missing theorems and proofs: The stable set of unstable critical points is contained in a countable union of inverse images of measure-zero sets, and therefore has measure zero.

A.1 Mathematica code for proving claim in Lemma 3.4

This appendix section contains Mathematica code for verifying the stated spectral condition in Lemma 3.4.

  • A.1 Mathematica code for proving claim in Lemma 3.4: The code uses Reduce over complex r subject to norm inequalities involving r and two expressions containing sqrt(4r^2 + 1).

A.2 Mathematica code for proving claim in Lemma 3.5

The appendix presents Mathematica `Reduce` checks for whether several expressions involving nested square roots exceed 1 in absolute value over 0 < x < 1/2, alongside a reference to the Jacobian of function g.

  • Symbolic checks: Mathematica `Reduce` tests whether a nested-square-root expression with the positive inner branch has absolute value greater than 1 for 0 < x < 1/2.The tested expression is 1/2 (1 + Sqrt[1 - 8 x^2 + 4 Sqrt[-x^2 + 4 x^4]]).
  • Context: The surrounding material identifies the Jacobian of function g as relevant background for the claim.
  • Symbolic checks: Two further `Reduce` checks replace the inner radicand's plus sign with a minus sign and test both outer branches over 0 < x < 1/2.These checks use 1 - 8 x^2 - 4 Sqrt[-x^2 + 4 x^4] inside the outer square root.
  • Symbolic checks: A second `Reduce` check tests the corresponding negative outer branch with the same positive inner radicand over 0 < x < 1/2.The expression uses 1/2 (1 - Sqrt[1 - 8 x^2 + 4 Sqrt[-x^2 + 4 x^4]]).
Loading 1807.03907v2…