The limits of min-max optimization algorithms: convergence to spurious non-critical sets

Introduction

Consider a min-max optimization – or saddle-point – problem of the form

Given an algorithm for solving (SP), it is then natural to ask:

The goal of our paper is to treat ($\star$ ‣ 1) in a general non-convex / non-concave setting and to provide answers for a comprehensive array of state-of-the-art algorithms.

This question has attracted significant interest in the machine learning literature because of its potential implications to generative adversarial networks , robust reinforcement learning , and other models of adversarial training . In this broad setting, it has become empirically clear that the joint training of two neural networks is fundamentally more difficult than that of a single NN of similar size and architecture. The latter task boils down to successfully finding a (good) local minimum of a non-convex function, so it is instructive to revisit ($\star$ ‣ 1) in the context of non-convex minimization.

In this case, the existing convergence theory for stochastic gradient descent (SGD) – the “gold standard” for deep NN training – can be informally summed up as follows:

stochastic gradient descent (SGD) always converges to critical points.

SGD does not converge to strict saddle points or other spurious solutions.

These results could be seen as plausible expectations for algorithmic proposals to solve (SP). Unfortunately however, there are well-known examples of simple bilinear min-max games where stochastic gradient descent/ascent (SGDA), the min-max analogue of SGD, leads to recurrent orbits that do not contain any critical point of $\Phi$. Such spurious convergence phenomena arise from the min-max structure of (SP) and have no counterpart in minimization problems.

This well-documented failure of SGDA has led to an extensive literature that is impossible to survey here. As a purely indicative – and highly incomplete – list, we mention the works of Daskalakis et al , Gidel et al , Mertikopoulos et al and Mokhtari et al , who studied how these failures can be overcome in deterministic bilinear problems by means of an extra-gradient step (or an optimistic proxy thereof). By contrast, in stochastic problems, the convergence of optimistic / extra-gradient methods is compromised unless additional, tailor-made mitigation mechanisms are put in place – such as variance reduction or variable step-size schedules . This shows that the convergence of min-max training methods can be particularly fragile, even in simple, bilinear problems.

Beyond the class of convex-concave problems analyzed above, another vigorous thread of research has focused on the local analysis of a min-max optimization algorithm close to the game’s critical points – typically subject to a second-order sufficient condition; cf. Heusel et al , Nagarajan and Kolter , Daskalakis and Panageas , Adolphs et al , Mazumdar et al , Fiez and Ratliff , Grimmer et al . The global analysis is much more challenging and requires strong structural assumptions such as variational coherence and/or the existence of a Minty-type solution . In the absence of such conditions, Flokas et al showed that periodic and/or Poincaré recurrent behavior may persist in deterministic, continuous-time min-max dynamics.

From a practical viewpoint, these studies have led to a broad array of sophisticated algorithmic proposals for solving min-max games; we review many of these algorithms in Section 3. However, a central question that remains unanswered is whether it is theoretically plausible to expect a qualitatively different behavior relative to SGDA in the full spectrum of non-convex / non-concave games. Our work aims to provide concrete answers to this question.

Our first contribution is to provide a unified framework for a comprehensive selection of first- and zeroth-order min-max optimization methods (including SGDA, proximal point methods, optimistic / extra-gradient schemes, their alternating variants, etc.). The principal ingredients of our approach are twofold: (\edefnit\selectfonti \edefnn) a generalized Robbins–Monro (RM) template that is wide enough to include all the above algorithms; and (\edefnit\selectfonti \edefnn) an analytic framework leveraging the ordinary differential equation (ODE) method of stochastic approximation . Based on these two elements, we prove a precise version of the following general principle: the long-run behavior of all generalized RM methods can be mapped to the study of the same, mean-field dynamical system.

In more detail, we show that the limit points of all generalized RM schemes belong to an internally chain-transitive (ICT) set of these mean dynamics. The notion of an internally chain-transitive (ICT) set is central in the study of dynamical systems and, in some cases, they are easy to characterize: in minimization problems (and possibly up to a “hidden” transformation in the spirit of 27), the dynamics’ ICT sets are the function’s critical points. As such, in this case, we recover exactly the min-min landscape of SGD – but for an entire family of algorithms, not just SGD.

Moving on to general min-max problems, the structure of the dynamics’ ICT sets could be considerably more complicated, so we provide two further, complementing results:

With high probability, all generalized RM methods converge locally to attractors of the mean dynamics.

With probability $1$, all generalized RM methods avoid the mean dynamics’ unstable invariant sets.

As far as we are aware, there are no results of comparable generality in the min-max optimization literature. From a high level, these theoretical contributions would seem to be analogous to existing results for SGD in minimization problems (i.e., that SGD converges to critical points while avoiding strict saddles). However, this similarity is only skin-deep: as we show by a range of concrete, almost bilinear examples, min-max optimization algorithms may encounter a series of immovable roadblocks. Specifically:

An ICT set may contain a globally attracting limit cycle, and the range of algorithms under consideration cannot escape it – even though extra-gradient methods escape recurrent orbits in exact bilinear problems. This suggests that bilinear games may not be representative as a testbed for GAN training algorithms and heuristics.

There exist unstable critical points whose neighborhood contains an (almost) globally stable ICT set. Therefore, in sharp contrast to minimization, “avoiding unstable critical points” does not imply “escaping unstable critical points” in min-max problems.

There exist stable min-max points whose basin of attraction is “shielded” by an unstable ICT set. As a result, if run with non-negligible noise in the gradients, then, with high probability, existing algorithms are repelled away from the desirable solutions.

Our results indicate a steep, qualitative increase in difficulty when passing from min-min to min-max problems, in line with concurrent works by Daskalakis et al and Letcher . In plain terms, Daskalakis et al proved the impossibility of attaining a critical point in polynomial time in deterministic, constrained min-max games. In a similar spirit, the concurrent work of Letcher showed that there are min-max games where all “reasonable” deterministic algorithms may fail to converge. By contrast, our paper focuses on the occurrence of spurious convergence phenomena with probability $1$ in stochastic algorithms. In addition, our avoidance result (Theorem 3) can be seen as a stochastic counterpart of the “reasonableness” requirement of Letcher , thereby enriching the applicability of the results therein. Taken together, these works and our own provide a complementing look into the fundamental limits of min-max optimization algorithms.

Setup and preliminaries

for the (min-max) gradient field of $\Phi$, assumed here to be Lipschitz; in some cases we may also require $V$ to be $C^{1}$ and write $JV(z)$ for its Jacobian. Finally, we will assume that $V$ satisfies the weak asymptotic coercivity condition

This condition is a weaker version of standard coercivity conditions in the literature , it is satisfied by all convex-concave problems (including bilinear ones) and, importantly, it does not impose any growth requirements on the elements of $V$ (as standard coercivity conditions do). We discuss it further in Appendix A.

A solution of (SP) is a tuple $z^{\ast}=(x^{\ast},y^{\ast})$ with $\Phi(x^{\ast},y)\leq\Phi(x^{\ast},y^{\ast})\leq\Phi(x,y^{\ast})$ for all $x\in\mathcal{X}$, $y\in\mathcal{Y}$; likewise, a local solution of (SP) is a tuple $(x^{\ast},y^{\ast})$ that satisfies this inequality locally. Finally, a state $z^{\ast}$ with $V(z^{\ast})=0$ is said to be a critical (or stationary) point of $\Phi$.

From an algorithmic standpoint, we will focus exclusively on the black-box optimization paradigm with stochastic first-order oracle (SFO) feedback. Algorithms with a more complicated feedback structure, such as a best-response oracle or based on mixed-strategy sampling , are not considered in this work.

Specifically, when called at $z=(x,y)$ with random seed $\omega\in\Omega$, an stochastic first-order oracle (SFO) returns a random vector $\operatorname{\mathsf{V}}(z;\omega)\equiv(\operatorname{\mathsf{V}}_{x}(z;\omega),\operatorname{\mathsf{V}}_{y}(z;\omega))$ of the form

where the error term $\operatorname{\mathsf{U}}(z;\omega)$ captures all sources of uncertainty in the model (e.g., the selection of a minibatch in GAN training, system state observations in reinforcement learning, etc.). As is standard in the literature, we require $\operatorname{\mathsf{U}}(z;\omega)$ to be zero-mean and finite-variance:

These will be our blanket assumptions throughout.

Core algorithmic framework

Much of our analysis will revolve around iterative algorithms that can be cast as generalized Robbins–Monro algorithms of the general form

$Z_{n}=(X_{n},Y_{n})\in\mathcal{Z}$ denotes the state of the algorithm at each stage $n=1,2,\dotsc$

$W_{n}$ is an abstract error term described in detail below.

$\gamma_{n}$ is the method’s step-size hyperparameter, and is typically of the form $\gamma_{n}\propto 1/n^{p}$ for some $p\geq 0$. Throughout the paper, we will always assume $\sum_{n}\gamma_{n}=\infty$ and $\lim_{n}\gamma_{n}=0$.

In the above, the error term $W_{n}$ is generated after $Z_{n}$; thus, by default, $W_{n}$ is not adapted to the history $\mathcal{F}_{n}\coloneqq\mathcal{H}(Z_{1},\dotsc,Z_{n})$ of $Z_{n}$. For concision, we will also write

so $V_{n}$ can be seen as a noisy estimator of $V(Z_{n})$. In more detail, to differentiate between “random” (zero-mean) and “systematic” (non-zero-mean) errors in $V_{n}$ it will be convenient to further decompose the error process $W_{n}$ as

Note that both $B_{n}$ and $\sigma_{n}$ are random (conditioned on $\mathcal{F}_{n}$); this will play an important part in the sequel.

2. Specific algorithms

In the rest of this section, we discuss how a wide range of algorithms used in the literature can be seen as special instances of our general RM template.

The basic SGDA algorithm – also known as the Arrow–Hurwicz method – queries an SFO and proceeds as:

where $\omega_{n}\in\Omega$ ($n=1,2,\dotsc$) is an independent and identically distributed (i.i.d.) sequence of oracle seeds. As such, (SGDA) admits a straightforward RM representation by taking $W_{n}=U_{n}=\operatorname{\mathsf{U}}(Z_{n};\omega_{n})$ and $b_{n}=0$. $\blacktriangle$

The (deterministic) proximal point method (PPM) is an implicit update rule of the form:

The RM representation of (PPM) is obtained by taking $W_{n}=b_{n}=V(Z_{n+1})-V(Z_{n})$ and $U_{n}=0$. $\blacktriangle$

Since (PPM) is only implicitly defined, one can rarely run it in practice. Nonetheless, it is possible to approximate (PPM) by locally querying two (stochastic) gradients at each iteration . This can be achieved by the stochastic extra-gradient (SEG):

To recast (SEG) in the Robbins–Monro framework, simply take $W_{n}=\operatorname{\mathsf{V}}(Z_{n}^{+};\omega_{n}^{+})-V(Z_{n})$, i.e., $U_{n}=\operatorname{\mathsf{U}}(Z_{n}^{+};\omega_{n}^{+})$ and $b_{n}=V(Z_{n}^{+})-V(Z_{n})$. $\blacktriangle$

Compared to (SGDA), the scheme (SEG) involves two oracle queries per iteration, which is considerably more costly. An alternative iterative method with a single oracle query per iteration was proposed by Popov :

Popov’s extra-gradient has been rediscovered several times and is more widely known as the optimistic gradient (OG) method in the machine learning literature . In unconstrained problems, (OG/PEG) turns out to be equivalent to a number of other existing methods, including “extrapolation from the past” and reflected gradient . Its Robbins–Monro representation is obtained by setting $W_{n}=\operatorname{\mathsf{V}}(Z_{n}^{+};\omega_{n})-V(Z_{n})$, i.e., $U_{n}=\operatorname{\mathsf{U}}(Z_{n}^{+};\omega_{n})$ and $b_{n}=V(Z_{n}^{+})-V(Z_{n})$. $\blacktriangle$

When first-order feedback is unavailable, a popular alternative is to obtain gradient information of $\Phi$ via zeroth-order observations . This idea can be traced back to the seminal work of Kiefer and Wolfowitz and the subsequent development of the simultaneous perturbation stochastic approximation (SPSA) method by Spall . In our setting, this leads to the recursion:

where $\delta_{n}\searrow 0$ is a vanishing “sampling radius” parameter, $\omega_{n}$ is drawn uniformly at random from the composite basis $\Omega=\mathcal{E}_{\mathcal{X}}\cup\mathcal{E}_{\mathcal{Y}}$ of $\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$, and the “$\pm$” sign is equal to $-1$ if $\omega_{n}\in\mathcal{E}_{\mathcal{X}}$ and $+1$ if $\omega_{n}\in\mathcal{E}_{\mathcal{Y}}$. Viewed this way, the interpretation of (5) as a Robbins–Monro method is immediate; furthermore, a straightforward calculation (that we defer to Section B.3) shows that the sequence of gradient estimators $V_{n}$ in (5) has $B_{n}=\operatorname{\mathcal{O}}(\delta_{n})$ and $\sigma_{n}^{2}=\operatorname{\mathcal{O}}(1/\delta_{n}^{2})$. $\blacktriangle$

Further examples that can be cast in the RM framework include the negative momentum method , generalized OG schemes , the Chambolle-Pock algorithm , the “prediction method” of Yadav et al , and centripetal acceleration ; the analysis is similar and we omit the details. Certain scalable second-order methods can also be viewed as RM schemes, but the driving vector field $V$ is no longer the gradient field of $\Phi$; we discuss this in the supplement.

3. Alternating updates and moving averages

There are two extremely common heuristics for practitioners in applying min-max algorithms to real applications: alternating and averaging. An alternating algorithm for (SP) updates the $x$ and $y$ variables sequentially (instead of simultaneously as in Section 3.2). An averaged algorithm takes the next state as a convex combination of $Z_{n}$ and $Z_{n+1}$ in (RM), cf. .

An important feature of our framework is that it captures alternating and averaged algorithms in a seamless manner. Indeed, introducing alternating updates or a moving average in RM schemes results in another RM scheme:

Let $Z_{n+1}=Z_{n}+\gamma_{n}[V(Z_{n})+W_{n}]$ be an RM scheme where $W_{n}=U_{n}+b_{n}$ as in (5). Then its $\alpha$-averaged version (where $0<\alpha<1$), defined as

is also an RM scheme: $Z_{n+1}=Z_{n}+\alpha\gamma_{n}[V(Z_{n})+W_{n}]$.

Lemma 1 can be easily adapted to the scenario where one only averages either the $X_{n}$ or $Y_{n}$ variable.

Let $Z_{n+1}=Z_{n}+\gamma_{n}[V(Z_{n})+W_{n}]$ be an RM scheme where $W_{n}=U_{n}+b_{n}$ as in (5). Then its alternating version, defined as

is also an RM scheme: $Z_{n+1}=Z_{n}+\gamma_{n}[V(Z_{n})+U_{n}+b^{\prime}_{n}]$ where

Convergence analysis

The key in providing a unified treatment of all algorithms in Section 3 is the reduction of (RM) to the mean dynamics

To see why (MD) can capture the limiting behavior of a vast family of RM schemes beyond GDA, let us illustrate the high-level intuition on the deterministic version of Algorithm 3 ($U_{n}=0$).

Since $\Phi$ and $V$ are assumed to be Lipschitz (say with constants $M$ and $L$), we see that the bias term in Algorithm 3 satisfies

As a result, we can rewrite Algorithm 3 as

If $\gamma_{n}\searrow 0$, we should then expect (8) to converge to (MD). More generally, if the error term $W_{n}$ in (RM) is sufficiently well-behaved, we should expect the iterates of (RM) and the solutions of (MD) to eventually come together.

On the other hand, bona fide min-max problems are considerably more involved. The most widely known illustration is given by the bilinear objective $\Phi(x,y)=xy$: in this case (see Fig. 1), the trajectories (MD) comprise periodic orbits of perfect circles centered at the origin (the unique critical point of $\Phi$). However, the behavior of different RM schemes can vary wildly, even in the absence of noise ($\sigma=0$): trajectories of (SGDA) spiral outwards, each converging to an initialization-dependent periodic orbit; instead, (SEG) trajectories spiral inwards, eventually converging to the solution $z^{\ast}=(0,0)$.

This particular difference between gradient and extra-gradient schemes has been well-documented in the literature . More pertinent to our theory, it also raises several key questions:

What is the precise link between RM methods and the mean dynamics (MD)?

When does (MD) yield accurate predictions for the long-run behavior of an RM method?

Below, we devote Sections 4.2–4.3 to the first question, and Section 4.4 to the second.

2. Connecting (RM) to (MD)

We begin by introducing a measure of “closeness” between the iterates of (RM) and the solution orbits of (MD). To do so, let $\tau_{n}=\sum\nolimits_{k=1}^{n}\gamma_{k}$ denote the “effective time” that has elapsed at the $n$-th iteration of (RM), and define the continuous-time interpolation $Z(t)$ of $Z_{n}$ as

$Z(t)$ is an asymptotic pseudotrajectory (APT) of (MD) if, for all $T>0$, we have:

This comparison criterion is due to Benaïm and Hirsch and it plays a central role in our analysis. In words, it simply posits that $Z(t)$ eventually tracks the flow of (MD) with arbitrary accuracy over windows of arbitrary length; as a result, if $Z_{n}$ is an asymptotic pseudotrajectory (APT) of (MD), it is reasonable to expect its behavior to be closely correlated to that of (MD).

Our first result below makes this link precise. Consider an RM scheme which satisfies

Suppose that Eqs. A1–A2 hold. Then $Z_{n}$ is an APT of (MD) w.p.$1$.

3. Applications and examples

Of course, applying Theorem 1 to a specific algorithm (e.g., as in Section 3) would first require verifying Eqs. A1–A2. However, even though the noise $\operatorname{\mathsf{U}}(z;\omega)$ in (SFO) is assumed zero-mean and finite-variance, this does not imply that the error term $W_{n}=U_{n}+b_{n}$ in Algorithms 2–5 enjoys the same guarantees. For example, the RM representation of Algorithms 2–4 has non-zero bias, while Algorithm 5 has non-zero bias and unbounded variance (the latter behaving as $\operatorname{\mathcal{O}}(1/\delta_{n}^{2})$ with $\delta_{n}\to 0$).

In the following proposition we prove that Algorithms 1–5 generate asymptotic pseudotrajectories of (MD) for the typical range of hyperparameters used to ensure almost sure convergence of stochastic first-order methods.

Let $Z_{n}$ be a sequence generated by any of the Algorithms 1–5. Assume further that:

For first-order methods (Algorithms 1–4), the algorithm is run with SFO feedback satisfying (3) and a step-size $\gamma_{n}$ such that $A/n\leq\gamma_{n}\leq B/\sqrt{n(\log n)^{1+\varepsilon}}$ for some $A,B,\varepsilon>0$.

For zeroth-order methods (Algorithm 5), the algorithm is run with parameters $\gamma_{n}$ and $\delta_{n}$ such that $\lim_{n}(\gamma_{n}+\delta_{n})=0$, $\sum_{n}\gamma_{n}=\infty$, and $\sum_{n}\gamma_{n}^{2}/\delta_{n}^{2}<\infty$ (e.g., $\gamma_{n}=1/n$, $\delta_{n}=1/n^{1/3}$).

Then $Z_{n}$ is almost surely an APT of (MD).

4. The limit sets of RM schemes

The APT results in Sections 4.2–4.3 can be heuristically interpreted as: “RM schemes eventually behave as some orbits of (MD).” We now further ask: What are the candidate limit orbits of (MD) for RM schemes?

To shed some light on the question, let us recall that, in non-convex minimization problems, SGD enjoys the following properties:

SGD converges to the function’s set of critical points .

This leads to the following “law of the excluded middle”: generically, the only solution candidates left for SGD are stable critical points, i.e., the local minimizers of the problem’s minimization objective.

In the remaining of this section, we will assimilate Items (I) and (II) in the context of RM schemes applied to (SP).

We first focus on generalizing Item (I) for min-max optimization. To proceed, recall first that critical points alone cannot capture the broad spectrum of algorithmic behaviors when (MD) is not a gradient system: already in Fig. 1 we see a critical point surrounded by spurious periodic orbits. In addition, in dynamical systems many other spurious convergence phenomena are known, such as homoclinic loops, limit cycles, or chaos. To account for this considerably richer landscape, we will need some definitions from the theory of dynamical systems.

Let $\mathcal{S}$ be a nonempty compact subset of $\mathcal{Z}$. Then:

$\mathcal{S}$ is attracting if it is invariant and there exists a compact neighborhood $\mathcal{K}$ of $\mathcal{S}$ such that $\lim_{t\to\infty}\operatorname{dist}(\Theta_{t}(z),\mathcal{S})=0$ uniformly in $z\in\mathcal{K}$.

$\mathcal{S}$ is internally chain-transitive (ICT) if it is invariant and $\Theta|_{\mathcal{S}}$ admits no proper attractors in $\mathcal{S}$.

Equivalently, ICT sets can be viewed as “minimal connected periodic orbits up to arbitrarily small numerical errors”, cf. Benaïm [7, Prop. 5.3]. The definition above is more convenient to work with because it provides the key insights in Section 4.4.3 below.

Our next result shows that, with probability $1$, all limit points of (RM) lie in these “approximate periodic orbits”:

If Eqs. A1–A2 hold, then $Z_{n}$ converges almost surely to an ICT set of $\Phi$.

Let $Z_{n}$ be a sequence generated by any of the Algorithms 1–5 with parameters as in Proposition 1. Then $Z_{n}$ converges almost surely to an ICT set of $\Phi$.

4.2. Avoidance of unstable points and sets

Our next result provides an avoidance result for RM schemes in min-max optimization. In analogy with function minimization problems, we will focus on unstable invariant sets of (MD), i.e., invariant sets that admit a nontrivial unstable manifold (for an in-depth discussion and precise definition, see 81 and Section C.1).

In generic minimization problems, these are precisely the sets of strict saddle points of the function being minimized. However, since general min-max problems do not comprise a gradient system, (MD) could exhibit a plethora of unstable sets, not containing any stationary points of $\Phi$ (e.g., periodic orbits, heteroclinic networks, etc.). On account of the above, our result below is stated in terms of invariant sets – and not only points. For convenience, we will assume that $V$ is $C^{2}$ and $\gamma_{n}$ is as in Proposition 1.

We note that Items (i1pt) and (ii1pt) above are standard in the literature for avoidance results of SGD , and are significantly lighter than other “isotropic noise” assumptions that are common in the literature . Specifically, even though Item (ii1pt) looks somewhat obscure, it only posits that the noise is not degeneratively equal to zero along certain directions in space; for a more detailed discussion, see Section C.1. We also stress that neither of these assumptions is required for the rest of our paper.

4.3. When do RM schemes behave the same?

So far, we have successfully generalized Items (I) and (II) to the context of (SP) as follows:To see why this is really a generalization, simply note that the only ICT sets of $V=-\operatorname{\nabla}f$ are connected critical points of $f$; cf. Proposition C.1.

RM schemes always converge to ICT sets, and

Nonetheless, Items I and II still fail to explain the distinct behaviors of RM schemes in bilinear objectives: Why does SGDA converge only to periodic orbits, while deterministic stochastic extra-gradient (SEG) only to critical points? Or, more generally, {quoting} Are different RM schemes more likely to exhibit different convergence topologies – e.g., cycles vs. critical points – in generic min-max problems?

Importantly, the celebrated Kupka-Smale theorem asserts that systems with degenerate periodic orbits (such as bilinear games) occur “almost never” in the Baire category sense. More precisely, an arbitrarily small perturbation can fundamentally destroy the topological properties of their ICT sets and give rise to proper, non-trivial attractors; cf. Example 5.1. In contrast, systems with nontrivial attractors are known to be robust under perturbations , and our final result in the section shows that it is precisely the existence of nontrivial attractors that makes the discrepancy of RM schemes disappear, at least locally.

In short, Theorem 4 asserts that any non-degenerate ICT set dictates the local convergence of all RM schemes under the general Eqs. A1–A2.

On a positive note, since the Hartman-Grobman Theorem implies that all critical points of $\Phi$ with $\Re\{\lambda(JV(z^{\ast}))\}<0$ for all engenvalues $\lambda$ are attractors of (MD), Theorem 4 immediately yields:

Let $z^{\ast}$ be a critical point of $\Phi$ such that $\Re\{\lambda(JV(z^{\ast}))\}<0$ for all engenvalues of $JV(z^{\ast})$. Then all RM schemes satisfying Eqs. A1–A2 locally converge to $z^{\ast}$ with high probability.

Corollary 3 generalizes the local convergence of deterministic SGDA and SEG studied by Daskalakis and Panageas . It also extends [37, Theorem 5] from (OG/PEG) to all generalized RM schemes.

On the flip side, however, Theorem 4 also bears an undesirable consequence: it implies that many RM schemes designed to improve SGDA (e.g., Algorithms 2–4) may in fact be trapped by spurious ICT sets in exactly the same way as SGDA. Thus, even though many of these algorithms have been motivated by their appealing properties in bilinear games, it is not clear whether they offer any significant advantages beyond the convex-concave case. We examine this issue in detail in the next section.

Spurious attractors: Illustrations and examples

Consider an arbitrarily small perturbation of a bilinear game:

where $\varepsilon>0$ and $\phi(y)=\frac{1}{2}y^{2}-\frac{1}{4}y^{4}$. There is an unstable critical point at the origin; further, Lemma D.1 asserts, for small $\varepsilon$, the existence of an attracting ICT set $\mathcal{S}$ in a neighborhood of the circle $\{z:\lVert z\rVert^{2}=4/3\}$. By Corollary 2, any RM scheme of Section 3 thus gets trapped by $\mathcal{S}$; see Fig. 2(a) for an illustration for (SEG).

This example brings two issues of existing studies to light. First, it shows that “almost bilinear games” can still trap many methods for solving exact bilinear games. Second, in contrast to minimization problems, the region around an unstable critical point can in fact be fully stable. Thus, one has to be careful when interpreting algorithms that “locally avoid unstable critical points”, since they might be incapable of escaping their neighborhoods. $\blacktriangle$

Suppose we apply Algorithms 1–5 to the objective

where $\phi(z)=\frac{1}{4}z^{2}-\frac{1}{2}z^{4}+\frac{1}{6}z^{6}$. This problem has a desirable $(x^{\ast},y^{\ast})\simeq(0.08,0.4)$. However, as we show in Section D.2, there exist two spurious limit cycles that do not contain any critical point of $\Phi$. Worse, the limit cycle closer to the solution is unstable and repels any trajectory that comes close to the solution; see Fig. 2(b) for an illustration for (SEG). As a result, the “shielded” solution is highly unlikely to be discovered by existing algorithms, even though it is perfectly stable. $\blacktriangle$

We conclude the paper by further examining several important settings that are not covered by our theory:

Instead of the “moving average” in Lemma 1, one can take the ergodic average ($Z^{\prime}_{n}=\frac{1}{n}\sum\nolimits_{k=1}^{n}Z_{k}$) as is customary in convex-concave problems . We plot one such trajectory in Fig. 2 (the blue curves). Evidently, we see that ergodic average can force the algorithms to halt at non-critical points, and this convergence is by no means min-max optimal.

Many recent works attempt to address the cycling issues of min-max algorithms via incorporating second-order oracles. For completeness, we also study a range of popular second-order methods in Section D.3. Our analysis shows that these algorithms suffer similar symptoms as first-order schemes in our examples, cf. Figs. 4–5.

In addition to the diminishing step-size policies studied here, another common strategy in practice is to simply set $\gamma_{n}$ to a constant step-size. While our analysis does not cover this setting, there exist several techniques in stochastic approximation to boost from our “almost surely” statements for $\gamma_{n}\searrow 0$ to concentration or high-probability results when $\gamma_{n}\equiv\gamma$ is small .

For completeness, in Section D.4 we examine various constant step-size RM schemes applied to (11) and (12). The outcome coincides with our intuition that these schemes should concentrate around the spurious attracting ICT sets, and hence exhibit similar behaviors as RM schemes with $\gamma_{n}\searrow 0$; see Fig. 6.

Adaptive methods such as Adam are ubiquitous in GAN training. We study such methods in Section D.5: our results show tha they fail solve the simple objectives (11) and (12). Moreover, some methods even show a potentially detrimental tendency of converging to max-min points, the exact opposite of desirable solutions; see Fig. 7.

In closing, we should clarify that these illustrations are not meant to suggest that the algorithms and practical tweaks discussed above are always doomed, or that they comprise the principal cause of failure in GAN training. However, we do believe that they constitute an important cautionary tale to the effect that, in min-max problems, convergence does not imply optimality – or even stationarity.

Appendix A Stabilization of RM schemes

Our aim in this appendix will be to prove the stability of generalized RM schemes, namely that asymptotic pseudotrajectories generated by (RM) are bounded with probability $1$. The key ingredient in our analysis is the weak asymptotic coercivity (WAC) condition (2), which, as we discussed in the main body of our paper, is a relaxation of the standard coercivity requirement

The hypothesis (A.1) is a mainstay in the analysis of monotone operators and variational inequalities . Roughly speaking, it states that the “radial component”

of $V(z)$ grows to $-\infty$ as $\lVert z\rVert\to\infty$. In other words, any vector field that satisfies (A.1) has an inward-pointing component that grows infinitely large for large $\lVert z\rVert$.

In view of the above, the coercivity assumption (A.1) suggests that any process that takes successive steps along $V(z)$ will be subject to an “inwards drift” towards regions with smaller norm, and this drift will be more and more pronounced the farther one moves away from the origin. On that account, (A.1) is a natural candidate for showing that RM processes based on $V$ never escape to infinity. On the other hand, vector fields that do not have a strong radial component – such as the bilinear game field $V(x,y)=(-y,x)$ which has $V_{r}(x,y)=0$ – are not covered by (A.1). In this regard, the WAC condition (2) provides an important relaxation of (A.1), because it only posits that the radial component of $V(z)$ is asymptotically non-positive – or, more simply, that $V(z)$ does not have a persistent outward-pointing component.

Before proving the stability of generalized RM schemes under (2), we provide below a series of important examples that satisfy the WAC condition (2):

$V$ satisfies (A.1). Indeed, in this case, for all $M>0$, there exists some $R\equiv R(M)$ such that

whenever $\lVert z\rVert\geq R$, i.e., (2) holds

$\Phi$ is convex-concave and it admits a critical point. By shifting the problem’s frame of reference if necessary, we can assume without loss of generality that $z^{\ast}=0$ is a critical point of $\Phi$. Then, with $\Phi$ assumed convex-concave, we readily get $\langle V(z),z\rangle\leq\langle V(z^{\ast}),z-z^{\ast}\rangle=0$, i.e., (2) holds

The first item above justifies the terminology “weak asymptotic coercivity”; for a geometric illustration, see Fig. 3 below.

We now proceed to establish our main stability result for generalized RM schemes under the WAC condition (2):

Suppose that $V$ satisfies Eq. 2. Then, under Eqs. A1–A2, the sequence $Z_{n}$ generated by (RM) is bounded (a.s.).

Our proof hinges on the introduction of a suitable “energy function” for (MD). To define it, recall that that $\langle V(z),-z\rangle\geq 0$ whenever $\lVert z\rVert\geq R$. Then, with a fair amount of hindsight, fix some $\lambda>0$ and let

By a direct calculation, we can verify the following:

$E$ is continuously differentiable and its gradient is given by $\nabla E(z)=\phi(\lVert z\rVert/R)\,z$ where $\phi(u)=0$ if $u\leq 1$, $\phi(u)=1-1/u$ if $1\leq u\leq 1+\lambda$, and $\phi(u)=\lambda/u$ if $1+\lambda\leq u$.

$E$ is negatively correlated to $V$, i.e., $\langle V(z),-\nabla E(z)\rangle\geq 0$ for all $z\in\mathcal{Z}$.

$E$ is $1$-smooth, i.e., $E(z^{\prime})\leq E(z)+\langle\nabla E(z),z^{\prime}-z\rangle+(1/2)\lVert z^{\prime}-z\rVert^{2}$ for all $z,z^{\prime}\in\mathcal{Z}$.

Then, letting $E_{n}=E(Z_{n})$ and $\phi_{n}=\phi(\lVert Z_{n}\rVert/R)$, we get

where the second line follows from the properties of $E$, the definition (4) of $V_{n}$, and the Cauchy-Schwarz inequality. Hence, conditioning on $\mathcal{F}_{n}$ and taking expectations, we obtain:

where we made a second use of the Cauchy-Schwarz inequality in the term involving $B_{n}$ and $M$ is the Lipschitz constant of $\Phi$.

Appendix B Proof of Theorems 1 and 1

In this appendix, we discuss how the algorithms in Section 3 fit within the general stochastic approximation framework of Section 4.2. Specifically, we prove the general conditions of Theorems 1 and 1 which guarantee that Algorithms 1–5 generate asymptotic pseudotrajectories of the mean dynamics (MD).

Before doing so, we will require some background material on asymptotic pseudotrajectories. Following Benaïm and Hirsch and Benaïm , we first recall the definition of the “effective time” $\tau_{n}=\sum_{k=1}^{n}\gamma_{k}$ as the time that has elapsed at the $n$-th iteration of the discrete-time process $Z_{n}$; recall also the definition (9) of the continuous-time interpolation $Z(t)$ of $Z_{n}$ as

We will further require the “continuous-to-discrete” correspondence

which measures the number of iterations required for the effective time $\tau_{n}$ of the process to reach the timestamp $t$; for future use, we also define the quantity

Finally, given an arbitrary sequence $A_{n}$, we will denote its piecewise constant interpolation as

Using this notation, the (affinely) interpolated process $Z(t)$ can be expressed in integral form as

where $W_{n}$ denotes the generalized error term of (RM).

With all this in hand, Benaïm [7, Prop. 4.1] provides the following general condition for $Z(t)$ to be an APT of the mean dynamics (10):

Suppose that $Z(t)$ is bounded and satisfies the general condition

B.2. Proof of Theorem 1

Our proof of Theorem 1 revolves around the direct verification of the requirement (B.5) of Proposition B.1 via the use of maximal inequalities and martingale limit theory.Benaïm provides a set of sufficient conditions for (B.5) to hold when $Z(t)$ is generated by a RM scheme with $B_{n}=0$ and $\sup_{n}\sigma_{n}<\infty$; however, our setting requires a more general treatment. For convenience, we restate the theorem below in full:

Since we have shown that $Z_{n}$ remains bounded in Proposition A.1, it suffices to verify (B.5).

Our proof relies on the Burkholder–Davis–Gundy (BDG) inequality which bounds the maximal value of a martingale $S_{n}$ via its quadratic variation as

where $c_{2},C_{2}>0$ are universal constants. As such, applying (BDG) to the martingale $S_{m}=\sum_{k=n}^{m}\gamma_{k}U_{k}$ (after an appropriate shift of the starting time), we get

where $M_{n}=M_{n}(T)=M(\tau_{n}+T)$ is defined as in (B.2). Now, mimicking (B.6), let

We will proceed to show that $\lim_{t\to\infty}\Delta_{0}(t;T)=0$ for all $T>0$ by considering the sequence of intervals $[kT,(k+1)T]$ and using the Borel-Cantelli lemma in order to show that $\Delta_{0}(kT;T)\to 0$ as $k\to\infty$. Indeed, we have

with the last step following from Eq. A2. Then, if we consider the event $\mathcal{E}_{k}(\varepsilon)=\{\Delta_{0}(kT;T)>\varepsilon\}$, Chebysev’s inequality gives

and hence, by the Borel-Cantelli lemma, we get

i.e., $\Delta_{0}(kT;T)\to 0$ with probability $1$.

Thus, going back to the requirements of Proposition B.1, we get

Given that $\lim_{k\to\infty}B_{k}=0$, the above shows that $\Delta(kT;T)\to 0$ as $k\to\infty$. Moreover, for all $t\in[kT,(k+1)T]$, we have $\Delta(t;T)\leq 2\Delta(kT;T)+\Delta((k+1)T;T)$ so $\Delta(t;T)\to 0$ with probability $1$. With $T>0$ arbitrary, we conclude that (B.5) holds with probability $1$, so our claim follows from Proposition B.1. ∎

B.3. Proof of Proposition 1

We are now in a position to prove that the generalized RM schemes presented in Section 3 comprise asymptotic pseudotrajectories of the mean dynamics (MD). For convenience, we state the relevant result below:

For (SGDA), we have $W_{n}=U_{n}=\operatorname{\mathsf{U}}(Z_{n};\omega_{n})$ and $b_{n}=0$, so Eq. A1 is satisfied automatically (since $B_{n}=0$). Our claim then follows from the stated assumptions for (SFO).

where $L$ and $M$ are the Lipschitz constant of $V$ and $\Phi$, respectively.

where $\varepsilon$ is the same as in our choice of step-size in Proposition 1. In turn, this implies that

so, by the Borel-Cantelli lemma, we have $\lVert\operatorname{\mathsf{U}}(Z_{n};\omega_{n})\rVert=\operatorname{\mathcal{O}}\left(\sqrt{n\log^{1+\frac{\epsilon}{2}}n}\right)$ with probability $1$. Hence, by our assumptions for the method’s step-size, we get

so that, in view of (B.3), $B_{n}\to 0$ with probability $1$.

We now show that the alternating version of Algorithms 1–4 still constitute an APT of (MD).

By Lemma 2, we know that the alternating version of an RM scheme is another RM scheme with the same noise and new bias satisfying:

by the definition of an RM scheme. Since $\gamma_{n}L\lVert b_{n}\rVert=o\left(\lVert b_{n}\rVert\right)$, the rest is the same as Algorithm 3.

We also note that (B.18) can be applied recursively to show that the bias term $b_{n}^{(k_{1},k_{2})}$ of any $(k_{1},k_{2})$ version of RM schemes satisfy

thus enjoying the same properties as the vanilla alternating $(1,1)$-RM schemes in view of (B.18).

Because of the algorithm’s different oracle structure (zeroth- vs. first-order feedback), the analysis of (5) is different. We begin with the algorithm’s bias term, given here by

denoting the method’s one-shot SPSA estimator. To bound it, let

Since $V$ is Lipschitz continuous, it follows that

Appendix C Convergence analysis: Proof of Theorems 3–4

With all this preliminary work in hand, we are finally in a position to prove Theorems 3–4.

The heavy lifting for Theorem 2 is already provided by the fact that, under the requirements of Theorem 1 and/or Proposition 1, $Z_{n}$ is an APT of the mean dynamics (MD), so it inherits its limit structure. Theorems 3 and 4 on the other hand require a completely different set of techniques and involve a much finer analysis of the process in hand.

While the proof of Theorem 3 is highly technical, the high-level intuition for its conclusion is crystal clear: Assume that we are given an unstable critical point $z^{*}$. Then, by the stable manifold theorem , the set of all initializations such that the flow of (MD) converges to $z^{*}$ is of measure 0 in $\mathcal{Z}$. Consequently, if the noise process $\{U_{n}\}$ is such that it has “non-negligible” magnitude in the unstable directions near $z^{*}$, then it is plausible that the RM scheme should escape $z^{*}$ along these directions. Item (ii1pt) in Theorem 3 quantifies exactly the magnitude of noise for which we can formalize this heuristic argument.

Throughout this section we assume that we are given:

We further assume that for every point $z\in\mathcal{K}$, we have

There exist $\lambda,C>0$ such that for all $z\in\mathcal{K},w\in\mathcal{E}^{u}_{{z}}$ and $t\geq 0$

We call any $\mathcal{K}$ satisfying the above an unstable invariant set. As a simple illustration we show:

If $z^{\ast}$ is a critical point of $\Phi$ with any eigenvalue $\lambda$ of $JV(z^{\ast})$ such that $\Re\{\lambda(JV(z^{\ast}))\}>0$. Then $z^{\ast}$ verifies all the assumptions of an unstable invariant set.

As a corollary, $Z_{n}$ generated by any of the Algorithms 1–4 in Theorem 3 avoids $z^{\ast}$ almost surely.

All the requirements for an unstable invariant set are readily verified by the Stable Manifold Theorem . The lemma follows by noting the the dimension for the unstable manifold is greater than or equal to 1; see [78, Chap 5]. ∎

A further justification of these technical assumptions is the following: Suppose $\mathcal{K}$ is a periodic orbit. We then say that $\mathcal{K}$ is (linearly) unstable if 1 is a Floquet multiplier of $\mathcal{K}$ and some multipliers have modulus strictly greater than 1 . If the vector field $V$ is assumed to be $C^{2}$, then a classical result in dynamical systems (see e.g., ) states that $\mathcal{K}$ verifies all the above assumptions.

We now proceed to the proof of Theorem 3. For ease of reading we reformulate its statements in the following more convenient form:

Let $\mathcal{K}$ be an unstable invariant set of $V$. Assume that

There exists $K>0$ such that $\lVert U_{n}\rVert\leq K$ for all $n$.

Then $Z_{n}$ generated by any of the Algorithms 1–4 satisfies

We first note that, for our choice of $\gamma_{n}$,

so $\gamma_{n}=o\left(\sqrt{\sum\nolimits_{k=n}^{\infty}\gamma_{k}^{2}}\right)$. This fact will be used in the proof when we invoke Lemma C.3 below with $\varepsilon_{n}=\operatorname{\mathcal{O}}(\gamma_{n})$ and $\alpha_{n}=\sum\nolimits_{k=n}^{\infty}\gamma_{k}^{2}$ therein.

We will need some technical lemmas. The first one is a deep result by Benaïm and Hirsch , which asserts the existence of a local Lyapunov function near the unstable periodic orbits.

If $\eta$ is differentiable, then (C.5) is simply $\langle\operatorname{\nabla}\eta(z),h\rangle$.

$\eta$ is $C^{2}$ on $\ \mathcal{U}(\mathcal{K})\setminus\mathcal{S}$.

There exists $c_{1}>0$ such that for all $z\in\mathcal{U}(\mathcal{K})\setminus\mathcal{S}$

For all $z\in\mathcal{U}(\mathcal{K})$ we have

The second lemma we need is a probabilistic estimate from .

Let $S_{n}$ be a nonnegative stochastic process, $S_{n}=S_{0}+\sum\nolimits_{k=1}^{n}X_{k}$ where $X_{n}$ is $\mathcal{F}_{n}$-measurable. Let $\alpha_{n}\coloneqq\sum\nolimits_{k=n}^{\infty}\gamma_{k}^{2}$.

Assume there exist a sequence $0\leq\varepsilon_{n}=o(\sqrt{\alpha_{n}})$, constants $a_{1},a_{2}>0$ and an integer $N_{0}$ such that for all $n\geq N_{0}$,

$\lvert X_{n}\rvert=o(\sqrt{\alpha_{n}})$.

Armed with Lemmas C.2 and C.3 we are now ready to prove Theorem 3.

Define two sequences of random variables $\{X_{n}\}_{n\geq 2}$ and $\{S_{n}\}$ as

Note that $S_{n}\geq 0$ (a.s.) for every $n$. Our proof will revolve around verifying Lemma C.3Items 1–4.

By Lipschitz continuity of $\eta$ we know that

where $L^{\prime}$ is the Lipschitz constant of $\eta$. We have seen in the proof of Proposition 1 that $\lVert b_{n}\rVert=\operatorname{\mathcal{O}}\left(\gamma_{n}(\lVert V(Z_{n})\rVert+\lVert U_{n}\rVert)\right)$. By Proposition A.1 and Item (i1pt) in Theorem 3, we then have $\lvert X_{n+1}\rvert=\operatorname{\mathcal{O}}({\gamma_{n}})=o(\sqrt{\alpha_{n}})$ which implies both Lemma C.3Items 1 and 4.

Let $k^{\prime}=k\lVert V\rVert+K$ where $k$ is given by Lemma C.2Item iii and $\lVert V\rVert\coloneqq\sup\{V(z):z\in\mathcal{U}(\mathcal{K})\}$ and $K$ is the uniform bound of $U_{n}$. If $n\leq T$, using Lemma C.2Items ii, iii, v and vi we have

By the same calculation leading up to (B.3), Item (i1pt) in Theorem 3, and the Lipschitz continuity of $\Phi$, there exists a constant $c^{\prime}>0$ such that the bias sequence for Algorithms 1–4 can be bounded as $-\lVert b_{n}\rVert\geq-c^{\prime}\gamma_{n}$ (a.s.). Combining this with the Lipschitz continuity of $\eta$, we can merge the last three terms in (C.1) as

for some constant $k^{\prime\prime}>0$. Thus

since we have assumed noise to be zero mean. Combining (C.16) and (C.17), we then get

If $n>T$, $X_{n+1}=\gamma_{n}$ so trivially

Combining (C.18) with (C.19), we see that Lemma C.3Item 2 is satisfied with $\varepsilon_{n}=\frac{k^{\prime\prime}}{\beta}\gamma_{n}$.

Invoking Lemma C.2Item iv and Item (ii1pt) in Theorem 3, we see that

If $Z_{n}\in\mathcal{S}$, we can choose a unit vector $v_{n}\in\ker(I-\operatorname{D}\operatorname{\Pi}(Z_{n}))^{\perp}$ where $\operatorname{\Pi}$ denotes the projection operator onto $\mathcal{S}$. By the definition of $v_{n}$, we have $\langle U_{n},v_{n}\rangle=\langle U_{n}-\operatorname{D}\operatorname{\Pi}(Z_{n})U_{n},v_{n}\rangle$. Let $\mathcal{H}=\{n\leq T\}\cap\{Z_{n}\notin\mathcal{S}\}.$ By Lemma C.2Item iv, Cauchy-Schwartz, and Item (ii1pt) of Theorem 3 we get

Combining Eqs. C.19, C.22, C.23 and C.24 then gives

We have now verified Lemma C.3Items 1–4. Thus, Lemma C.3 concludes that

We will use (C.26) to show that $T<\infty$ (a.s.).

C.2. Convergence to ICTs

We now prove Theorem 2, which we restate below for convenience:

By Theorem 1, $Z_{n}$ generates APT of the mean dynamics (MD). Now, let $\mathcal{L}=\operatorname*{\bigcap}_{t\geq 0}\operatorname{cl}(Z(t,\infty))$ be the limit set of $Z(t)$, i.e., the set of limit points of convergent sequences $Z(t_{n})$ with $\lim_{n}t_{n}=\infty$. Our claim then follows by the limit set theorem of Benaïm and Hirsch [9, Theorem 8.2]. ∎

Under the stated conditions, the critical set $\mathcal{Z}^{\ast}\coloneqq\operatorname{crit}(f)$ of $f$ coincides with the set of rest points of (MD). Moreover, by Sard’s theorem , $f(\mathcal{Z}^{\ast})$ has zero Lebesgue measure and hence empty interior. Our claim then follows from Proposition 6.4 of Benaïm . ∎

C.3. Convergence to attractors

We now proceed with the analysis of RM schemes in the presence of an attractor; the relevant result is Theorem 4:

Because of the generality of our assumptions, the proof of Theorem 4 requires a range of completely different arguments and techniques. We illustrate the main steps of our technical trajectory below:

The first crucial component of our proof is to establish an energy function for (RM) in a neighborhood of $\mathcal{S}$. To do this, we rely on Conley’s decomposition theorem (the so-called “fundamental theorem of dynamical systems”) which states that the mean dynamics (MD) are “gradient-like” in a neighborhood of an attractor, i.e., they admit a (local) Lyapunov function.

Because of the noise in (RM), the evolution of $E$ along the trajectories of (RM) could present signifcant jumps: in particular, a single “bad” realization of the noise could carry $Z_{n}$ out of the basin of attraction of $\mathcal{S}$, possibly never to return. A major difficulty here is that the driving vector field $V$ is not assumed bounded, so it is not straightforward to establish proper control over the error terms of (RM). However, we show that, with high probability (and, in particular, with probability at least $1-\alpha$), the aggregation of these errors remains controllably small; this is the most technically challenging part of our argument and it unfolds in a series of lemmas below.

Conditioning on the above, we will show that, with probability at least $1-\alpha$, the value of the trajectory’s energy cannot grow more than a token threshold $\varepsilon$; as a result, if (RM) is initialized close to $\mathcal{S}$, it will remain in a neighborhood thereof for all $n$ (again, with probability at least $1-\alpha$).

Thanks to this “stochastic Lyapunov stability” result, we can regain control of the variance of the process and use martingale limit and maximal inequality arguments to show that $Z_{n}$ converges to $\mathcal{S}$.

In the rest of this section, we make this roadmap precise via a series of technical lemmas and intermediate results.

In the discrete-time context of (RM), the energy $E_{n}\coloneqq E(Z_{n})$ of $Z_{n}$ may fail to be decreasing (strictly or otherwise). However, a simple Taylor expansion with Lagrange remainder yields the basic energy bound

where the error terms $\xi_{n}$, $\psi_{n}$ and $\theta_{n}$ are defined as

with $\beta$ denoting the strong smoothness modulus of $E$ over the compact set $\mathcal{K}$. Clearly, each of these error terms can be positive, so $E_{n}$ may fail to be decreasing; we discuss how these errors can be controlled below.

We begin by encoding the aggregation of the error terms in (C.27) as

so the jumps of $M_{n}$ can become arbitrarily big if $Z_{n}$ escapes $\mathcal{K}$ (which is the event we are trying to discount in the first place). On that account, we will instead bound the total error increments by conditioning everything on the event that $Z_{n}$ remains within $\mathcal{K}$.

To make this precise, consider the “mean square” error process

with the convention $\mathcal{E}_{0}=\mathcal{H}_{0}=\Omega$. Moving forward, with significant hindsight, we will choose $\varepsilon$ small enough so that

and we will assume that $Z_{1}$ is initialized in a neighborhood $\mathcal{U}\subseteq\mathcal{K}$ such that

Suppose that $Z_{1}\in\mathcal{U}$ and Eqs. A1 and A2 hold. Then

$\mathcal{E}_{n+1}\subseteq\mathcal{E}_{n}$ and $\mathcal{H}_{n+1}\subseteq\mathcal{H}_{n}$.

$\mathcal{H}_{n-1}\subseteq\mathcal{E}_{n}$.

The first claim is obvious. For the second, we proceed inductively:

For the base case $n=1$, we have $\mathcal{E}_{1}=\{Z_{1}\in\mathcal{K}\}\supseteq\{Z_{1}\in\mathcal{U}\}=\Omega$ (recall that $Z_{1}$ is initialized in $\mathcal{U}\subseteq\mathcal{K}$). Since $\mathcal{H}_{0}=\Omega$, our claim follows.

Inductively, suppose that $\mathcal{H}_{n-1}\subseteq\mathcal{E}_{n}$ for some $n\geq 1$. To show that $\mathcal{H}_{n}\subseteq\mathcal{E}_{n+1}$, suppose that $R_{k}\leq\varepsilon$ for all $k=1,2,\dotsc,n$. Since $\mathcal{H}_{n}\subseteq\mathcal{H}_{n-1}$, this implies that $\mathcal{E}_{n}$ also occurs, i.e., $Z_{k}\in\mathcal{K}$ for all $k=1,2,\dotsc,n$; as such, it suffices to show that $Z_{n+1}\in\mathcal{K}$.

To do so, given that $Z_{k}\in\mathcal{U}\subseteq\mathcal{K}$ for all $k=1,2,\dotsc n$, the bound (C.27) gives

and hence, after telescoping over $k=1,2,\dotsc,n$, we get

We conclude that $E(Z_{n+1})\leq 2\varepsilon+\sqrt{\varepsilon}$, i.e., $Z_{n+1}\in\mathcal{K}$, as required for the induction.

However, since $\mathcal{H}_{n-1}$ and $M_{n-1}$ are both $\mathcal{F}_{n}$-measurable, we have the following estimates:

The term (C.44b) is where the reduction to $\mathcal{H}_{n-1}$ kicks in; indeed:

where $G^{2}=\sup_{z\in\mathcal{K}}\{\lVert\nabla E(z)\rVert^{2}+\lVert V(z)\rVert^{2}\}$.

where we used the fact that $\operatorname{\mathds{1}}_{\mathcal{H}_{n-1}}\leq\operatorname{\mathds{1}}_{\mathcal{E}_{n}}\leq 1$. Likewise,

Thus, putting together all of the above, we obtain:

Our claim then follows by combining Sections C.3, C.46, LABEL:, C.47 and C.49. ∎

Lemma C.4 is the key to showing that $Z_{n}$ remains close to $\mathcal{S}$ with high probability: we formalize this in a final intermediate result below.

Fix some confidence threshold $\alpha>0$. If (RM) is run with sufficiently small $\gamma_{n}$ satisfying the conditions of Proposition 1, then

i.e., $Z$ remains within the basin of attraction $\mathcal{K}$ of $\mathcal{S}$ with probability at least $1-\alpha$.

where, in the second-to-last line, we used the fact that $R_{n}\geq 0$ (so $\operatorname{\mathds{1}}_{\{R_{n}>\varepsilon\}}\leq R_{n}/\varepsilon$). Telescoping (C.37) yields

We are finally in a position to prove the convergence of generalized RM algorithms:

Now, if we write $\mathcal{L}=\operatorname*{\bigcap}_{t\geq 0}\operatorname{cl}(Z(t,\infty))$ for the limit set of $Z(t)$, we will have $\mathcal{K}\cap\mathcal{L}\neq\varnothing$ by the compactness of $\mathcal{K}$ and the fact that $Z_{n}\in\mathcal{K}$ for all $n\geq 1$; moreover, $\mathcal{L}$ is itself compact as a closed subset of the compact set $\{\Theta_{t}(z){t}{z}:0\leq t\leq T,z\in\mathcal{K}\}$. Since points in $\mathcal{L}\cap\mathcal{K}$ are attracted to $\mathcal{S}$ under (MD) and $\mathcal{L}$ is invariant under (MD), we conclude that $\mathcal{L}\cap\mathcal{S}\neq\varnothing$. However, since $\mathcal{L}$ is internally chain-transitive (by Theorem 2) and internally chain-transitive sets do not contain any proper attractors, we conclude that $\mathcal{L}\subseteq\mathcal{S}$. This shows that $Z(t)$ – and hence $Z_{n}$ – converges to $\mathcal{S}$, and our proof is complete. ∎

Appendix D Omitted details for Section 5

We first provide a generic criterion for the existence of spurious ICT sets in almost bilinear games (11); cf. Lemma D.1. We then verify that the perturbation $\phi(y)=\frac{1}{2}y^{2}-\frac{1}{4}y^{4}$ employed in Example 5.1 indeed satisfies the required conditions.

Let $\phi(y)=\sum_{k}a_{k}y^{k}$ be an analytic function such that

has a solution with $h>0$. Then, for small enough $\varepsilon$, there is an ICT set of mean dynamics (MD) with objective $\Phi(x,y)=xy+\varepsilon\phi(y)$ such that it does not contain any critical point.

In the case of $\Phi(x,y)=xy+\varepsilon\phi(y)$, (MD) reads:

The most important tool of the proof is the Abelian integral :

where $h>0$ is a parameter and $\gamma_{h}$ is a family of ovals defined as in (2.3) of .

Suppose $\phi(y)=a_{k}y^{k}$, so that $\phi^{\prime}(y)=ka_{k}y^{k-1}$. We choose $\gamma_{h}=\{z:\lVert z\rVert=h\}.$ Then, using the polar coordinate representation, we get

Since contour integrals are linear in the integrands, when $\phi(y)=\sum_{k}a_{k}y^{k}$ in (AI), we have

Therefore, $I(h)=0$ if and only if (D.1) holds. By Theorem 2.4 in , the solution $h^{*}$ of $I(h^{*})=0$ then implies the existence of a limit cycle in a neighborhood of the oval $\gamma_{h^{*}}\coloneqq\{z:\lVert z\rVert=h^{*}\}.$ ∎

Finally, it is easy to verify that for $\phi(y)=\frac{1}{2}y^{2}-\frac{1}{4}y^{4}$, the condition (D.1) is satisfied with $h^{*}=\sqrt{\frac{4}{3}}$, thus implying the existence of a spurious ICT set near the neighborhood of $\{z:\lVert z\rVert=\sqrt{\frac{4}{3}}\}.$

D.2. Proof of spurious ICT sets in Example 5.2

We show the existence of two spurious ICT sets in Example 5.2.

Define $r^{2}\coloneqq x^{2}+y^{2}$. Then straightforward calculations show that:

Substituting the value $r^{2}=\frac{4}{3}$ into (D.7), we get

since $\lvert x\rvert\leq\sqrt{\frac{4}{3}}$ on $\{r\geq 0:r^{2}=\frac{4}{3}\}$, whence $\dot{r}>0$ on $\{r\geq 0:r^{2}=\frac{4}{3}\}$. Likewise, one can check that $\dot{r}<0$ on $\{r\geq 0:r^{2}=2\}$, and that there is no stationary point in the region $\mathcal{S}\coloneqq\{r\geq 0:\frac{4}{3}\leq r^{2}\leq 2\}$. By the Poincaré-Bendixson theorem , there exists at least a limit cycle in $\mathcal{S}$.

Finally, it is easy to see that $(x^{\ast},y^{\ast})\simeq(0,0.49)$ is a stable critical point of (12). Since the region $\mathcal{S}$ is trapping, Poincaré’s index theorem then dictates that there exists at least another unstable limit cycle inside $\mathcal{S}$, establishing the claim.

D.3. Second-order methods

In this section, we discuss how to cast existing second-order methods as an RM scheme with different driving vector fields, and show that their ICT sets are similar to the first-order methods under practical settings.

Thanks to the efficient implementation of Hessian-gradient multiplications , a popular second-order method for min-max optimization in machine learning is the Hamiltonian descent method . The idea is simply to run SGD on $f=\lVert\nabla\Phi\rVert^{2}/2$, giving

As a (discretized) gradient system, our theory in Section 4 shows that (HD) does not possess ICT sets other than critical points of $f$. However, a serious issue of (HD) is that it ignores the sign of gradients, i.e., it does not distinguish between minimization and maximization. As such, it has mostly been used as a gradient penalty scheme by mixing (HD) (or its variants) with (SGDA), giving rise to a number of other second-order methods such as symplectic gradient adjustment (SGA) and consensus optimization (ConO) . As in Section 3, one can cast these algorithms as RM schemes with $V(Z_{n})$ replaced by $(I-\lambda JV(Z_{n}))V(Z_{n})$, where $\lambda$ is the regularization parameter. The analysis can then proceed as in Section 4 by replacing (MD) with the appropriate continuous-time systems.

Fig. 4(a) shows the spurious convergence of symplectic gradient adjustment (SGA) with $\lambda=0.2$ applied to (12). The ICT sets of SGA are only slightly different from Algorithms 1–5 and, in a certain precise sense, are perturbations thereof (so they suffer the same symptoms). $\blacktriangle$

We now discuss how to model second-order methods as RM schemes. We will showcase on the consensus optimization (ConO):

where $\lambda>0$ is the regularization parameter. Recalling the efficient implementation scheme of Hessian-gradient multiplication , we make the following assumption on the stochastic second-order oracles (SSO): when called at $z=(x,y)$ with random seed $\omega^{\prime}\in\Omega$, an SSO returns a random vector $\mathsf{JV}(z;\omega^{\prime})$ of the form

where $\operatorname{\mathsf{U}}^{\prime}(z;\omega^{\prime})$ is assumed to be unbiased and sub-Gaussian as in (3). With these assumptions, one can then proceed exactly as in Section B.3 for the Algorithms 1–4 cases to show that ConO, and its alternating version, give rise to asymptotic pseudotrajectories of the continuous-time dynamics:

Fig. 4(b) demonstrates that the spurious ICT sets of ConO for (12) is similar to that of SGA.

Similarly, one can show (under appropriate assumptions of the oracles) the continuous-time dynamics of symplectic gradient adjustment (SGA) is

As explained in Example D.1, it is undesirable to set a large number of $\lambda$, since then we are essentially treating $\min\max$ and $\max\min$ as the same problem. However, if $\lambda$ is small, then the structure stability of hyperbolic orbits (which holds for any stable/unstable ICT sets) implies that any stable (unstable) ICT set of (MD) remains stable (unstable) under perturbations . We therefore expect the ICT sets of various second-order algorithms in Example D.1 be to similar to that of first-order RM schemes.

In addition, we have included yet another second-order method, the Competitive Gradient Descent (CGD) , in Fig. 5(a). For ease of comparison, we run (OG/PEG) with the same initialization in Fig. 5(b). As is evident from the figure, both algorithms perform similarly and converge straight to the spurious ICT set.

Finally, we report the behavior of various algorithms applied to the “almost bilinear game” (11) in Fig. 5(c). In this case, all algorithms fail to escape the spurious ICT set, with the sole exception of ConO. Intriguingly, ConO converges to the unstable critical point. A plausible explanation of this phenomenon is provided by , where it is shown that the Hamiltonian descent (HD) converges to critical points for any almost bilinear game. Therefore, it is not surprising that ConO, being a mixture of SGDA and HD, also enjoys similar guarantees. Such a convergence is nonetheless highly undesirable in our example, echoing the concern that gradient penalty schemes cannot distinguish (local) $\min\max$ from $\max\min$.

D.4. Constant step-sizes

We report in Fig. 6 the behaviors of constant step-size RM schemes. In accord with our intuition, these schemes exhibit concentration behaviors around the attractors.

D.5. Adaptive methods

We report in Fig. 7 the behaviors of popular adaptive algorithms for min-max optimization, including Adam and its extra-gradient variant , both set to default hyperparameter values in PyTorch. The result reveals a potentially dangerous trend: while both Adam and ExtraAdam are able to somewhat mitigate cycling phenomena, this comes at the cost of converging to the max-min point $(0,0)$ of (11). In other words, the algorithm has converged, but to a very bad solution point – an observation which, in the terminology of Letcher , would mean that Adam is not a “reasonable” algorithm. Moreover, as all RM schemes, both adaptive methods fail to reach the “forsaken” solutions in Example 5.2.

References