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

Introduction

The celebrated min-max theorem was a founding stone in the development of Game Theory , and is intimately related to strong linear programming duality , Blackwell’s approachability theory , and the theory of no-regret learning . The theorem states that if $f(\mathbf{x},\mathbf{y})$ is a convex-concave function, and $\cal X$, $\cal Y$ are compact and concave subsets of Euclidean space, then

If $f(\mathbf{x},\mathbf{y})$ represents the payment of the $\cal X$ player to the $\cal Y$ player under choices of strategies $\mathbf{x}\in{\cal X}$ and $\mathbf{y}\in{\cal Y}$ by these two players, the min-max theorem reassures us that an equilibrium of the game exists, and that the equilibrium payoffs to both players are unique.

What does not follow directly from the min-max theorem is whether there exist dynamics via which players would arrive at equilibrium if they were to follow some simple rule to update their current strategies. This has been the topic of a long line of investigation starting with Julia Robinson’s celebrated analysis of fictitious play , and leading to the development of no-regret learning .

Renewed interest in this problem has been recently motivated by the task of training Generative Adversarial Networks (GANs) , where two deep neural networks, the generator and the discriminator, are trained in tandem using first order methods, aiming at solving a min-max problem, of the following form, albeit typically with a non convex-concave objective function $f(\mathbf{x},\mathbf{y})$:

Here $\mathbf{x}$ represents the parameters of the generator deep neural net, $\mathbf{y}$ represents the parameters of the discriminator neural net, and $f(\mathbf{x},\mathbf{y})$ is some measure of how close the distribution generated by the generator appears to the true distribution from the perspective of the discriminator.

Min-max optimization in non convex-concave settings is a central problem for many research communities, however our knowledge is very limited from optimization perspective. Moreover, for such applications of first-order methods to min-max problems in Machine Learning, it is especially important that the last-iterate maintained by the min and the max dynamics converges to a desirable solution. Unfortunately, even when $f(\mathbf{x},\mathbf{y})$ is convex-concave, it is rare that guarantees are known for the last iterate (see for continuous time learning dynamics that may cycle). Some guarantees are known for continuous-time dynamics , but for discrete-time dynamics it is typically only shown that the average-iterates converge to min-max equilibrium. Recent work of shows that, while Gradient Descent/Ascent (GDA) dynamics performed by the min/max players may diverge, the Optimistic version dynamics of exhibit last iterate convergence to min-max solutions (which we shall call Optimistic Gradient Descent/Ascent (OGDA)), whenever $f(\mathbf{x},\mathbf{y})$ is linear in $\mathbf{x}$ and $\mathbf{y}$. The goal of our paper is to understand the limit points of GDA and OGDA dynamics (points that last iterate might converge to) for general functions $f(\mathbf{x},\mathbf{y})$. In particular, we answer the following questions:

are the stable limit points of GDA and OGDA locally min-max solutions?

how do the stable limit points of GDA and OGDA relate to each other?

We provide answers to these questions after defining our dynamics of interest formally.

with some constant step size $\alpha>0$Note that $\alpha>0$ for the rest of this paper.. However, there are examples (functions $f$ and initial points $(\mathbf{x}_{0},\mathbf{y}_{0})$) in which the system of equations (3) cycles (see ). To break down this behavior, the authors in analyzed another optimization algorithm which is called Optimistic Gradient Descent/Ascent (OGDA)We note that OGDA has some resemblance with Polyak’s heavy ball method. However, one important difference is that OGDA has “negative momentum” while the heavy ball method has “positive momentum.”, the equations of which boil down to the following:

One of their key results was to show convergence to the $\min\max$ solution for the case of bilinear objective functions, namely $f(\mathbf{x},\mathbf{y})=\mathbf{x}^{\top}A\mathbf{y}$.

Our contribution and techniques: In this paper we analyze Gradient Descent/Ascent (GDA) and Optimistic Gradient Descent/Ascent (OGDA) dynamics applied to min-max optimization problems. Our starting point is to show that both dynamics avoid their unstable fixed points (GDA-unstable and OGDA-unstable respectively, as defined in Section 1.1). This is shown by using techniques from dynamical systems, following the line of work of recent papers in Optimization and Machine Learning . In a nutshell we show that the update rules of both dynamics are local diffeomorphismsA local diffeomorphism is a function that locally is invertible, smooth and its (local) inverse is also smooth. and we then make use of Center-Stable manifold theorem A.1. These results are given as Theorems 2.2, 3.2. One important step in our approach is the construction of a dynamical system for OGDA in order to apply dynamical systems’ techniques.

We next study the set of stable fixed points of GDA dynamics and their relation to locally min-max solutions, called local min-max.In optimization literature they are called local saddles.). Informally, a local min-max critical point $(\mathbf{x}^{*},\mathbf{y}^{*})$ satisfies the following: compared to value $f(\mathbf{x}^{*},\mathbf{y}^{*})$, if we fix $\mathbf{x}^{*}$ and perturb $\mathbf{y}^{*}$ infinitesimally, the value of $f$ does not increase and similarly if we fix $\mathbf{y}^{*}$ and perturb $\mathbf{x}^{*}$ infinitesimally, the value of $f$ does not decrease. We show that the set of stable fixed points of GDA is a superset of the set of local min-max and there are functions in which this inclusion is strict. This is given in Lemmas 2.4, 2.7, 2.5.

Finally, we analyze OGDA dynamics which is a bit trickier than GDA due to the nature of the dynamics, namely the existence of memory in the dynamics: the next iterate depends on the gradient of the current and previous point. We construct a dynamical system that captures OGDA dynamics (see Equation (12)), using a construction that is commonly employed in differential equations. Importantly, we establish a mapping (relation) between the eigenvalues of the Jacobian of the update rules of both GDA and OGDA, showing that OGDA stable fixed points is a superset of GDA stable ones (under mild assumptions on the stepsize), namely (we suggest the reader to see first Remark 1.5 to avoid confusion):

We note that the inclusion above are strict.

1 Important Definitions

We have already stated our min-max problem of interest (2) as well as the Gradient Descent/Ascent (GDA) dynamics (3) and Optimistic Gradient Descent/Ascent (OGDA) dynamics (4) that we plan to analyze. We provide some further definitions.

Let $w$ be continuously differentiable. We call a fixed point $\mathbf{z}$ linearly stable or just stable if, for the Jacobian $J$ of $w$ computed at $\mathbf{z}$, it holds that its spectral radius $\rho(J)$ is at most one and otherwise we call it linearly unstable or just unstable.

A fixed point $\mathbf{z}$ of $w$ is called Lyapunov stable if, for every $\epsilon>0$, there exists a $\delta=\delta(\epsilon)>0$ such that if $\mathbf{x}\in\mathcal{B}_{\delta}$ with $\mathcal{B}_{\delta}=\{\mathbf{y}\in\mathcal{S}:\left\|\mathbf{y}-\mathbf{z}\right\|<\delta\}$Ball of radius $\delta$. we have that $\left\|w^{n}(\mathbf{x})-\mathbf{z}\right\|<\epsilon$ for every $n\geq 0$. That is, if dynamics starts close enough to $\mathbf{z}$, it remains close for all times.

A fixed point $\mathbf{z}$ of $w$ is called (locally) asymptotically stable (or attracting) if it is Lyapunov stable and there exists a $\delta>0$ such that, for all $\mathbf{x}\in\mathcal{B}_{\delta}$ we have that $\left\|w^{n}(\mathbf{x})-\mathbf{z}\right\|\to 0$ as $n\to\infty$. That is, there is a small neighborhood around $\mathbf{z}$ so that, for all initializations in that neighborhood, the dynamics converges to $\mathbf{z}$.

We call a fixed point $\mathbf{z}$ hyperbolic iff the Jacobian $J$ of $w$ computed at $\mathbf{z}$ has no eigenvalues with absolute value $1$.

If the Jacobian of the update rule at a stable fixed point $\mathbf{z}$ has spectral radius less than one, then the fixed point is asymptotically stable. Therefore, if a fixed point $\mathbf{z}$ is hyperbolic, then linear stability implies asymptotic stability.

It is easy to see that a fixed point of the GDA dynamics (3) arises whenever $(\mathbf{x}_{t+1},\mathbf{y}_{t+1})=(\mathbf{x}_{t},\mathbf{y}_{t})$, or in other words whenever $(\mathbf{x}_{t},\mathbf{y}_{t})=(\mathbf{x},\mathbf{y})$ such that $\nabla f(\mathbf{x},\mathbf{y})=\mathbf{0}$.

Since the OGDA dynamics (4) has memory, it is more appropriate to think of the dynamics as mapping a quadruple $(\mathbf{x}_{t},\mathbf{y}_{t},\mathbf{x}_{t-1},\mathbf{y}_{t-1})$ to a quadruple $(\mathbf{x}_{t+1},\mathbf{y}_{t+1},\mathbf{x}_{t},\mathbf{y}_{t})$. In this case, a fixed point arises whenever $(\mathbf{x}_{t+1},\mathbf{y}_{t+1},\mathbf{x}_{t},\mathbf{y}_{t})=(\mathbf{x}_{t},\mathbf{y}_{t},\mathbf{x}_{t-1},\mathbf{y}_{t-1})$, or in other words whenever $(\mathbf{x}_{t},\mathbf{y}_{t},\mathbf{x}_{t-1},\mathbf{y}_{t-1})=(\mathbf{x},\mathbf{y},\mathbf{x},\mathbf{y})$ and $\nabla f(\mathbf{x},\mathbf{y})=\mathbf{0}$.

Given Proposition 1.4, it follows that spectral analysis of the Jacobian of the fixed points can give us qualitative information about the local behavior of the dynamics. Unless otherwise specified, throughout this paper, whenever we say “stable” we mean linearly stable. GDA/OGDA-stable critical points are critical points that are stable with respect to GDA/OGDA dynamics (for fixed stepsize $\alpha$, otherwise are unstable). Moreover since different choices of stepsize $\alpha$ might give different stability for GDA and OGDA dynamics, we are interested in the case $\alpha$ is “sufficiently” small. Therefore in the sections we characterize the GDA/OGDA-stable critical points, a point $(\mathbf{x}^{*},\mathbf{y}^{*})$ is classified as GDA/OGDA-stable if there exists a sufficiently small number $\beta>0$ such that for all stepsizes $0<\alpha<\beta$ we have that the $(\mathbf{x}^{*},\mathbf{y}^{*})$ is a stable fixed point of GDA/OGDA dynamics (in case there exists a small $\beta>0$ so that for all stepsizes $0<\alpha<\beta$ we have that $(\mathbf{x}^{*},\mathbf{y}^{*})$ is an unstable fixed point of GDA/OGDA dynamics, it is classified as GDA/OGDA-unstable).

Optimization.

We use the following standard terminology.

For a min-max problem (2) where $f$ is twice continuously differentiable,

A point $(\mathbf{x}^{*},\mathbf{y}^{*})$ is a critical point of $f$ if $\nabla f(\mathbf{x}^{*},\mathbf{y}^{*})=\mathbf{0}$.

A critical point $(\mathbf{x}^{*},\mathbf{y}^{*})$ is isolated if there is a neighborhood $U$ around $(\mathbf{x}^{*},\mathbf{y}^{*})$ where $(\mathbf{x}^{*},\mathbf{y}^{*})$ is the only critical point.If the critical points are isolated then they are countably many or finite. Otherwise it is called non-isolated.

A critical point $(\mathbf{x}^{*},\mathbf{y}^{*})$ is a local min-max point if there exists a neighborhood $U$ around $(\mathbf{x}^{*},\mathbf{y}^{*})$ so that for all $(\mathbf{x},\mathbf{y})\in U$ we have that $f(\mathbf{x}^{*},\mathbf{y})\leq f(\mathbf{x}^{*},\mathbf{y}^{*})\leq f(\mathbf{x},\mathbf{y}^{*})$.In optimization literature these critical points are also called local saddle points. If $U$ is the whole domain then we call it global min-max.

A critical point $(\mathbf{x}^{*},\mathbf{y}^{*})$ is a strongly local min-max point if $\lambda_{\min}(\nabla^{2}_{\mathbf{x}\mathbf{x}}f(\mathbf{x}^{*},\mathbf{y}^{*}))>0$ and $\lambda_{\max}(\nabla^{2}_{\mathbf{y}\mathbf{y}}f(\mathbf{x}^{*},\mathbf{y}^{*}))<0$.

2 Formal Statement of Results

We present our main results for GDA and OGDA, to be proven in Sections 2 and 3. Some of our claims make use of the following assumptions about the objective function $f$ of (2):

$\nabla^{2}f$ (the Hessian of $f$) is invertible for all $\mathbf{x},\mathbf{y}$.

GDA is non-imaginary at a critical point $(x^{*},y^{*})$ of $f$ iff

has no eigenvalue whose real part is . $H$ captures the difference $\frac{1}{\alpha}(J(\mathbf{x}^{*},\mathbf{y}^{*})-\mathbf{I}_{n+m})$ where $J$ is the Jacobian of GDA dynamics and $\mathbf{I}_{n+m}$ the identity matrix.

Our two main results are stated as follows:

Assume $f$ is twice differentiable and $\nabla f$ is Lipschitz with constant $L$.

Let $(\mathbf{x}^{*},\mathbf{y}^{*})$ be a local min max critical point that satisfies Assumption 1.8. For $\alpha>0$ sufficiently small it holds that $(\mathbf{x}^{*},\mathbf{y}^{*})$ is GDA-stable fixed point. There is a function with critical point $(\mathbf{x}^{*},\mathbf{y}^{*})$ which violates Assumption 1.8, $(\mathbf{x}^{*},\mathbf{y}^{*})$ is local min-max but not GDA-stable for any $0<\alpha<\frac{1}{L}$ (Lemmas 2.4, 2.7 and 2.6).

Additionally, if $(\mathbf{x}^{*},\mathbf{y}^{*})$ is a strongly local min max critical point then Assumption 1.8 is satisfied and for $\alpha>0$ sufficiently small we get $(\mathbf{x}^{*},\mathbf{y}^{*})$ is GDA-stable (Remark 2.8).

Finally there is a function with a critical point $(\mathbf{x}^{*},\mathbf{y}^{*})$ which is not local min-max but it is GDA-stable (for sufficiently small $\alpha>0$, Lemma 2.5).

Let $(\mathbf{x}^{*},\mathbf{y}^{*})$ be a GDA-stable fixed point. For $0<\alpha<\frac{1}{2L}$ it holds that $(\mathbf{x}^{*},\mathbf{y}^{*})$ is OGDA-stable. Moreover the inclusion is strict, i.e., there is a function with critical point $(\mathbf{x}^{*},\mathbf{y}^{*})$ which is OGDA-stable but not GDA-stable (for small enough $\alpha>0$, Lemmas 3.4 and 3.5).

Assume $f$ is twice differentiable and $\nabla f$ is Lipschitz with constant $L$. The set of initial vectors $(\mathbf{x}_{0},\mathbf{y}_{0})$ so that GDA converges to (linearly) GDA-unstable fixed points (critical points) is of measure zero. Under Assumption 1.7, the set of initial vectors $(\mathbf{x}_{1},\mathbf{y}_{1},\mathbf{x}_{0},\mathbf{y}_{0})$ so that OGDA converges to (linearly) OGDA-unstable fixed points (critical points) is of measure zero. These statements are captured by Theorems 2.2 and 3.2.

Analysis of Gradient Descent/Ascent

In this section we analyze the local behavior (which carries over to a global characterization under Lemma 2.1 and Center-stable manifold theorem A.1) of GDA dynamics (3). In all our statements (theorems, lemmas etc) we work with real-valued function $f$ that is twice differentiable and we also assume $\nabla f$ is Lipschitz with constant $L$ and that the stepsize satisfies $0<\alpha<\frac{1}{L}$ (unless stated otherwise in the statement of a lemma/theorem).

We need to show the following lemma in order to use the stable manifold theorem (see Theorem A.1).

Let $f$ be twice differentiable and $\nabla f$ is Lipschitz with constant $L$. Assume that $0<\alpha<\frac{1}{L}$. The update rule of the GDA dynamics (3) is a local diffeomorphism.

Let $h(\mathbf{x},\mathbf{y})$ be the update rule of the dynamics (3). It suffices to show that the Jacobian $J_{\textrm{GDA}}$ of $h$ is invertible and by the use of Inverse Function theorem, the claim follows. After straightforward calculations we get

It suffices to show that the matrix below does not have an eigenvalue that is equal to $-1/\alpha$ (by just subtracting the identity matrix),

If the function $\nabla f$ is L-Lipschitz, it follows that $\left\|\nabla^{2}f\right\|_{2}\leq L$ (Lemma 6 in ). Therefore by equation (9) we have that $\rho(H_{\textrm{GDA}})\leq\left\|H_{\textrm{GDA}}\right\|_{2}\leq\left\|\nabla^{2}f\right\|_{2}\leq L<\frac{1}{\alpha}$. The claim follows. ∎

Let $f$ be twice differentiable and $\nabla f$ is Lipschitz with constant $L$. Assume that $0<\alpha<\frac{1}{L}$ and let $h$ be the update rule of the GDA dynamics (3), $(\mathbf{x}^{*},\mathbf{y}^{*})$ be a GDA-unstable critical point and $W_{\textrm{GDA}}(x^{*},y^{*})$ be its stable set, i.e.,

It holds that $W_{\textrm{GDA}}(x^{*},y^{*})$ is of Lebesgue measure zero. Moreover if $W_{\textrm{GDA}}$ is union of the stable sets of all GDA-unstable critical points, then $W_{\textrm{GDA}}$ has also measure zero (namely the proof works for non-isolated critical points).

The following corollary is immediate from Theorem 2.2.

2 Characterizing GDA-stability

Assume that $0<\alpha<\frac{1}{L}$ and let $(\mathbf{x}^{*},\mathbf{y}^{*})$ be a local min-max critical point of $f$ and matrix $H$ (see equations (5)) computed at $(\mathbf{x}^{*},\mathbf{y}^{*})$ has real eigenvalues. It holds that $(\mathbf{x}^{*},\mathbf{y}^{*})$ is GDA-stable.

By definition of local min-max, it holds that $\nabla_{\mathbf{x}\mathbf{x}}^{2}f$ is positive semi-definite and also $\nabla_{\mathbf{y}\mathbf{y}}^{2}f$ is negative semi-definite. Hence the symmetric matrix below (matrix $H_{\textrm{GDA}}$ is given by equation (8))

is negative semi-definite. We use the Ky Fan inequality which states that the sequence (in decreasing order) of the eigenvalues of $\frac{1}{2}(H_{\textrm{GDA}}+H_{\textrm{GDA}}^{\top})$ majorizes the real part of the sequence of the eigenvalues of $H_{\textrm{GDA}}$ (see , page 4). By assumption that $H_{\textrm{GDA}}$ has real eigenvalues we conclude that $\lambda_{\max}(H_{\textrm{GDA}})\leq\frac{1}{2}\lambda_{\max}(H_{\textrm{GDA}}+H_{\textrm{GDA}}^{\top})\leq 0$ since $H_{\textrm{GDA}}+H_{\textrm{GDA}}^{\top}$ is negative semi-definite. Therefore the spectrum of $I+\alpha H_{\textrm{GDA}}$ lies in $$, thus$(\mathbf{x}^{*},\mathbf{y}^{*})$ is GDA-stable. ∎

The converse of Lemma 2.4 is false. There are functions with critical points that are GDA-stable but not local min-max. An example is $f(x,y)=-\frac{1}{8}x^{2}-\frac{1}{2}y^{2}+\frac{6}{10}xy$See Figure 1..

We provide an example with two variables (so that we can also give a figure). Let $f(x,y)=-\frac{1}{8}x^{2}-\frac{1}{2}y^{2}+\frac{6}{10}xy$. Computing the Jacobian of the update rule of dynamics (3) at point $(0,0)$ we get that

Both eigenvalues of $J_{\textrm{GDA}}$ have magnitude less than 1 (for any $0<\alpha<\frac{1}{L}$ where $L\leq 1.34$). Finally matrix $H_{\textrm{GDA}}$ has real eigenvalues. Therefore there exists a neighborhood $U$ of $(0,0)$ so that for all $(x_{0},y_{0})\in U$, we get that $\lim_{t}(x_{t},y_{t})=(0,0)$ for GDA dynamics (3). However it is clear that $(0,0)$ is not a local min-max. See also Figure 1 for a pictorial illustration of the result. ∎

We end Section 2 by characterizing the case in which $H$ has complex eigenvalues.

There are functions with critical points that are not GDA-stable but are local min-max when matrix $H$ (see equations (5)) has imaginary eigenvalues.

Let $f(x,y)=xy$. It is clear that critical point $(0,0)$ is a local min-max point. Computing the Jacobian of the update rule of dynamics (3) at point $(0,0)$ we get that

For any $\alpha>0$ we have that the eigenvalues of $J_{\textrm{GDA}}$ are $1\pm\alpha i$,We denote $i:=\sqrt{-1}$. so they have magnitude greater than $1$ (and is clear that $H_{\textrm{GDA}}$ has complex eigenvalues). It is easy to see that $x_{t+1}^{2}+y_{t+1}^{2}=(1+\alpha^{2})(x_{t}^{2}+y_{t}^{2})$, i.e., inductively we have

We complete the characterization for the relation between GDA-stable critical points and local min-max with the following lemma:

Let $(\mathbf{x}^{*},\mathbf{y}^{*})$ be a local min-max critical point of $f$ and matrix $H$ (see equations (5)) computed at $(\mathbf{x}^{*},\mathbf{y}^{*})$ has all its eigenvalues with real part nonzero (i.e., Assumption 1.8). There is a small enough step-size $\alpha>0$ so that $(\mathbf{x}^{*},\mathbf{y}^{*})$ is GDA-stable.

The proof follows the steps of the proof of Lemma 2.4. Similarly, using Ky Fan inequality we know that for any eigenvalue $\lambda$ of $H_{\textrm{GDA}}$ it holds that

Hence we conclude that $\textrm{Re}(\lambda)$. Additionally, the corresponding eigenvalue of $J_{\textrm{GDA}}$ is $1+\alpha\lambda$. By choosing $\alpha<\min_{\lambda}\{-\frac{\textrm{Re}(\lambda)}{|\lambda|^{2}}\}$, it is easy to see that $|1+\alpha\lambda|^{2}=1+\alpha\textrm{Re}(\lambda)+\alpha^{2}|\lambda|^{2}<1$ for all the eigenvalues $\lambda$ of $H_{\textrm{GDA}}$, hence the eigenvalues of $J_{\textrm{GDA}}$ have magnitude less than one. ∎

If the critical point $(\mathbf{x}^{*},\mathbf{y}^{*})$ is strongly local min-max then $\lambda_{\max}(H)<0$ and hence $(\mathbf{x}^{*},\mathbf{y}^{*})$ is attracting under GDA dynamics, i.e., it holds that $\mbox{Strongly Local min-max}\;\subset\;\mbox{GDA-stable}$.

Optimistic Gradient Descent/Ascent

The results of the previous section cannot carry over to Optimistic Gradient Descent/Ascent due to the fact that the dynamics has memory and is more challenging to analyze. Here we show that Optimistic Gradient Descent/Ascent avoid OGDA-unstable critical points and we also relate the eigenvalues of the Jacobian of OGDA to the eigenvalues of the Jacobian of GDA. In particular we show that $\mbox{GDA-stable}\ \subset\mbox{OGDA-stable}$ (inclusion strict). In the beginning we will construct a dynamical system that captures the dynamics of OGDA (4).

We define the function $F$ to be $F(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w})=f(\mathbf{x},\mathbf{y})$ for all $(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w})\in\mathcal{X}\times\mathcal{Y}\times\mathcal{X}\times\mathcal{Y}$ (think of the last two vector components as dummy for function $F$, its value does not depend on them). Hence it is clear that $\nabla_{\mathbf{z}}F(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w})=\mathbf{0}$ and $\nabla_{\mathbf{w}}F(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w})=\mathbf{0}$. The same holds for $\nabla_{\mathbf{x}}F(\mathbf{z},\mathbf{w},\mathbf{x},\mathbf{y})=\mathbf{0}$ and $\nabla_{\mathbf{y}}F(\mathbf{z},\mathbf{w},\mathbf{x},\mathbf{y})=\mathbf{0}$.

We define the following function $g$ which consists of 4 components:

It is not hard to check that $(\mathbf{x}_{t+1},\mathbf{y}_{t+1},\mathbf{x}_{t},\mathbf{y}_{t})=g(\mathbf{x}_{t},\mathbf{y}_{t},\mathbf{x}_{t-1},\mathbf{y}_{t-1}),$ so $g$ captures exactly the dynamics of OGDA (4). The idea behind the construction of the dynamical system above is common in the literature of ODEs (ordinal differential equations) where in order to solve (typically to understand the qualitative behavior) a higher order ODE, one approach is to express it as a linear system of ODEs.

2 Analyzing OGDA via system (12)

As in the case of GDA, we need to show the following key lemma in order to use the Center-stable manifold theorem.

Let $f$ is real-valued $C^{2}$ and $\nabla f$ is Lipschitz with constant $L$ and $0<\alpha<\frac{1}{L}$. Under the Assumption 1.7 we get that the update rule $g$ of the OGDA dynamics (12) is a local diffeomorphism.

It suffices to show that the Jacobian of $g$, denoted by $J_{\textrm{OGDA}}$ is invertible and then by Inverse Function theorem the claim follows. After calculations the Jacobian boils down to the following (we set $F^{\prime}(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w})=F(\mathbf{z},\mathbf{w},\mathbf{x},\mathbf{y})$) :

Observe that for $\alpha=0$, the matrix $J_{\textrm{GDA}}$ is not invertible, as opposed to the case of GDA which is the identity matrix $\mathbf{I}_{n+m}$ and hence is invertible. It is easy to see that for $\alpha=0$, then $g(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w})=(\mathbf{x},\mathbf{y},\mathbf{x},\mathbf{y})$, namely it is not even $1-1$ (not even locally).

The null space of $J_{\textrm{OGDA}}$ is the same as the null space of the following matrix $H_{\textrm{OGDA}}$ (after row and column operations)

It is clear that under the assumption that the Hessian is invertible (see Assumption 1.7), we get that

Again as in Section 2, we are able to prove the following measure zero argument using Lemma 3.1 and Center-Stable manifold theorem.

Let $f$ be twice differentiable and $\nabla f$ is Lipschitz with constant $L$. Suppose that Assumption 1.7 holds and $0<\alpha<\frac{1}{L}$. Let $g$ be the update rule of the OGDA dynamics (4), $(\mathbf{x}^{*},\mathbf{y}^{*},\mathbf{x}^{*},\mathbf{y}^{*})$ be a OGDA-unstable critical point and $W_{\textrm{OGDA}}(x^{*},y^{*},x^{*},y^{*})$ be its stable set, i.e.,

It holds that $W_{\textrm{OGDA}}(x^{*},y^{*},\mathbf{x}^{*},\mathbf{y}^{*})$ is of Lebesgue measure zero. Moreover if $W_{\textrm{OGDA}}$ is union of the stable sets of all OGDA-unstable critical points, then $W_{\textrm{OGDA}}$ has also measure zero (namely the proof works for non-isolated critical points).

The following corollary is immediate from Theorem 3.2.

3 Characterizing OGDA-stability

In this subsection we provide an analysis for the eigenvalues of the Jacobian matrix $J_{\textrm{OGDA}}$ of the update rule $g$ of the system (12). We begin by claiming that the set of GDA-stable critical points is a subset of the set of OGDA-critical points. We manage to show this by constructing a mapping between the eigenvalues of $J_{\textrm{GDA}}$ and $J_{\textrm{OGDA}}$.

Let $f$ be twice differentiable and $\nabla f$ be L-Lipschitz. Assume that $0<\alpha<\frac{1}{2L}$ and suppose $(\mathbf{x}^{*},\mathbf{y}^{*})$ is a critical point that is GDA-stable (i.e., stable according to dynamics (3)). The critical point $(\mathbf{x}^{*},\mathbf{y}^{*},\mathbf{x}^{*},\mathbf{y}^{*})$ is stable according to OGDA dynamics (4).

A fixed point of the dynamics (4) is of the form $(\mathbf{x},\mathbf{y},\mathbf{x},\mathbf{y})$ (see Remark 1.5). The Jacobian of the update rule $g$ becomes as follows:

We would like to find a relation between the eigenvalues of matrix (16) and matrix (6) (relate the Jacobian of both dynamics GDA and OGDA). We start with the matrix

The absolute value of the determinant of a matrix remains invariant under row/column operations (add a multiple of a row/column to another row/column or exchange rows/columns). After such operations, the determinant of the matrix above has determinant in absolute value equal to (we assume that $\lambda\neq 0$)

The determinant above is equal to $\lambda^{m+n}p(\lambda)$, where

It is clear that $\lambda=\frac{1}{2}$ is not an eigenvalue of $J_{\textrm{OGDA}}$. Let $q_{\textrm{GDA}}(\lambda)$ be the characteristic polynomial of $J_{\textrm{GDA}}$ (6, Jacobian of GDA dynamics at $(\mathbf{x},\mathbf{y})$). The characteristic polynomial $q_{\textrm{OGDA}}$ of $J_{\textrm{OGDA}}$ ends up being equal to

Let $r$ be an eigenvalue of matrix $H_{\textrm{GDA}}$ (8), i.e., $r+1$ is an eigenvalue of $J_{\textrm{GDA}}$. From relation (17) it turns out that the roots of the polynomial

are eigenvalues of the matrix $J_{\textrm{OGDA}}$. For $\alpha<\frac{1}{2L}$ it holds that $|r|<\frac{1}{2}$ and it turns out that all the roots of the quadratic equation (18) have magnitude at most one (see Mathematica code in Section A.1 for a proof of the inequality). ∎

We conclude the subsection with the following claim and a remark.

There are functions with critical points that are OGDA-stable but not GDA-stable.

The easiest example is $f(x,y)=xy$. It is clear that the Jacobian of GDA dynamics (3) is given by

which has eigenvalues $1\pm\alpha i$ (magnitude greater than one) and hence the critical point $(0,0)$ is GDA-unstable. However, the Jacobian of OGDA dynamics (4) is given by

which has the four eigenvalues $\frac{1}{2}(1\pm\sqrt{1-8\alpha^{2}\pm 4\sqrt{4\alpha^{4}-\alpha^{2}}})$. For $0<\alpha<1/2$ all the four eigenvalues have magnitude less than or equal to 1, hence $(0,0)$ is OGDA-stable (see mathematica code A.2 for the inequality claim). Another example which is not bilinear (Assumption 1.7 is satisfied) is the function $\frac{1}{2}x^{2}+\frac{1}{2}y^{2}+4xy$ (this is used in the example section). ∎

We would like to note that some of our results (e.g., Lemma 3.1 and Theorem 3.2) are not applicable to a generic bilinear function $f(\mathbf{x},\mathbf{y})=\mathbf{x}^{\top}A\mathbf{y}$, since if $A$ is not a square matrix, the Hessian $\nabla^{2}f$ is not invertible (they are applicable only when $A$ is square matrix and invertible).

Examples and Experiments

The function $f_{1}(x,y)=-\frac{1}{8}x^{2}-\frac{1}{2}y^{2}+\frac{6}{10}xy$ has the property that the critical point $(0,0)$ is GDA-stable but not local min-max (see Lemma 2.5). Moreover, consider $f_{2}(x,y)=\frac{1}{2}x^{2}+\frac{1}{2}y^{2}+4xy$. This function has the property that the critical point $(0,0)$ is GDA-unstable and is easy to check that is not a local min-max. We construct the polynomial function $f(x,y)=f_{1}(x,y)(x-1)^{2}(y-1)^{2}+f_{2}(x,y)x^{2}y^{2}$. Function $f$ has the property that around $(0,0)$ behaves like $f_{1}$ and around $(1,1)$ behaves like $f_{2}$. The GDA dynamics of $f$ can be seen in Figure 2. However more critical points are created. There are five critical points, i.e, $(0,0),(0,1),(1,0),(1,1),(0.3301,0.3357)$ (in interval $R$, the last critical point is computed approximately). In Table 1 we observe that the critical point $(0,0)$ is stable for OGDA but unstable for GDA (essentially OGDA has more attracting critical points). Moreover, our theorems of avoiding unstable fixed points are verified with this experiment. Note that there are some initial conditions that GDA and OGDA dynamics don’t converge (3% and 9.8% respectively).

2 Higher dimensional

Let $f(\mathbf{x},\mathbf{y}):=p(\mathbf{x},\mathbf{y})\cdot(\sum_{i=1}^{5}x_{i}^{3}+y_{i}^{3})+w(\mathbf{x},\mathbf{y})$, where $p$ is the random 3-degree polynomial as mentioned above and $w(\mathbf{x},\mathbf{y})=\sum_{i=1}^{5}(x_{i}^{2}-y_{i}^{2})$. It is clear that $f$ locally at $(0,...,0)$ behaves like function $w$ (which has $\mathbf{0}$ as a local min-max critical point). We run for 10000 uniformly random points in $R$ and it turns out that 87% of initial points converge to $\mathbf{0}$ in OGDA as opposed to GDA which 79.3% fraction converged. This experiment indicates qualitative difference between the two methods, where the area of region of attraction in OGDA is a bit larger.

Conclusion

In this paper we made a step towards understanding first order methods which are used to solve min-max optimization problems, by analyzing the local behavior of GDA and OGDA dynamics around critical points. Our paper is an indication that important first order methods we analyze fail to converge to only local min-max solutions(standard concept in optimization literature). Whether or not local min-max solutions is a good concept is out of the scope of this paper. Local min-max solutions might not be all equally good and some may be bad, which is really important in applications such as training GANs. Nevertheless, even for minimization problems, finding good local minima is a hard task that is not well understood in the literature (most first order methods guarantee convergence to some local minimum, without guarantees about its quality). A forteriori guaranteeing good solutions in a min-max problem is a harder proposition and an important open question.

References

Appendix A Missing theorems and proofs

Let $x^{*}$ be a fixed point for the $C^{r}$ local diffeomorphism $g:\mathcal{X}\to\mathcal{X}$. Suppose that $E=E_{s}\oplus E_{u}$, where $E_{s}$ is the span of the eigenvectors corresponding to eigenvalues of magnitude less than or equal to one of $Dg(x^{*})$, and $E_{u}$ is the span of the eigenvectors corresponding to eigenvalues of magnitude greater than one of $Dg(x^{*})$Jacobian of function $g$.. Then there exists a $C^{r}$ embedded disk $W^{cs}_{loc}$ of dimension $dim(E^{s})$ that is tangent to $E_{s}$ at $x^{*}$ called the local stable center manifold. Moreover, there exists a neighborhood $B$ of $x^{*}$, such that $g(W^{cs}_{loc})\cap B\subset W^{cs}_{loc}$, and $\cap_{k=0}^{\infty}g^{-k}(B)\subset W^{cs}_{loc}$.

It follows the general line of the papers . We assume that the update rule of GDA, OGDA dynamics is a diffeomorphism (as proved in Lemmas 2.1 and 3.1). The proof is generic and has appeared in . Let $A$ be the set of unstable critical points $x^{*}$ of a dynamical system with update rule a function $g:\mathcal{X}\to\mathcal{X}$ (in $C^{2}$). For each $x^{*}\in A$, there is an associated open neighborhood $B_{x^{*}}$ promised by the Stable Manifold Theorem A.1. $\cup_{x^{*}\in A}B_{x^{*}}$ forms an open cover, and since $\mathcal{X}$ is second-countable we can extract a countable subcover, so that $\cup_{x^{*}\in A}B_{x^{*}}=\cup_{i=1}^{\infty}B_{x^{*}_{i}}$.

Define $W=\{x_{0}:\lim_{k}x_{k}\in A\}$ (stable set of $A$). Fix a point $x_{0}\in W$. Since $x_{k}\to x^{*}\in A$, then for some non-negative integer $T$ and all $t\geq T$, $g^{t}(x_{0})\in\cup_{x^{*}\in A}B_{x^{*}}$. Since we have a countable sub-cover, $g^{t}(x_{0})\in B_{x^{*}_{i}}$ for some $x^{*}_{i}\in A$ and all $t\geq T$. This implies that $g^{t}(x_{0})\in\cap_{k=0}^{\infty}\ g^{-k}(B_{x^{*}_{i}})$ for all $t\geq T$. By Theorem A.1, $S_{i}\triangleq\cap_{k=0}^{\infty}g^{-k}(B_{x^{*}_{i}})$ is a subset of the local center stable manifold which has co-dimension at least one, and $S_{i}$ is thus measure zero.

Finally, $g^{T}(x_{0})\in S_{i}$ implies that $x_{0}\in g^{-T}(S_{i})$. Since $T$ is unknown we union over all non-negative integers, to obtain $x_{0}\in\cup_{j=0}^{\infty}g^{-j}(S_{i})$. Since $x_{0}$ was arbitrary, we have shown that $W\subset\cup_{i=1}^{\infty}\cup_{j=0}^{\infty}g^{-j}(S_{i})$. Using Lemma 1 of page 5 in and that countable union of measure zero sets is measure zero, $W$ has measure zero.

A.2 Mathematica code for proving claim in Lemma 3.5