Year: 2021

Abstract:
Under mild regularity conditions, gradient-based methods converge globally to a critical point in the single-loss setting. This is known to break down for vanilla gradient descent when moving to multi-loss optimization, but can we hope to build some algorithm with global guarantees? We negatively resolve this open problem by proving that desirable convergence properties cannot simultaneously hold for any algorithm. Our result has more to do with the existence of games with no satisfactory outcomes, than with algorithms per se. More explicitly we construct a two-player game with zero-sum interactions whose losses are both coercive and analytic, but whose only simultaneous critical point is a strict maximum. Any ‘reasonable’ algorithm, defined to avoid strict maxima, will therefore fail to converge. This is fundamentally different from single losses, where coercivity implies existence of a global minimum. Moreover, we prove that a wide range of existing gradient-based methods almost surely have bounded but non-convergent iterates in a constructed zero-sum game for suitably small learning rates. It nonetheless remains an open question whether such behavior can arise in high-dimensional games of interest to ML practitioners, such as GANs or multi-agent RL.

heading: 1 INTRODUCTION
text: Problem Setting. As multi-agent architectures proliferate in machine learning, it is becoming increasingly important to understand the dynamics of gradient-based methods when optimizing multiple interacting goals, otherwise known as differentiable games. This framework encompasses GANs (Goodfellow et al., 2014), intrinsic curiosity (Pathak et al., 2017), imaginative agents (Racanière et al., 2017), synthetic gradients (Jaderberg et al., 2017), hierarchical reinforcement learning (Wayne & Abbott, 2014; Vezhnevets et al., 2017) and multi-agent RL in general (Busoniu et al., 2008). The interactions between learning agents make for vastly more complex mechanics: naively applying gradient descent on each loss simultaneously is known to diverge even in simple bilinear games.
Related Work. A large number of methods have recently been proposed to alleviate the failings of simultaneous gradient descent: adaptations of single-loss algorithms such as Extragradient (EG) (Azizian et al., 2019) and Optimistic Mirror Descent (OMD) (Daskalakis et al., 2018), Alternating Gradient Descent (AGD) for finite regret (Bailey et al., 2019), Consensus Optimization (CO) for GAN training (Mescheder et al., 2017), Competitive Gradient Descent (CGD) based on solving a bilinear approximation of the loss functions (Schaefer & Anandkumar, 2019), Symplectic Gradient Adjustment (SGA) based on a novel decomposition of game mechanics (Balduzzi et al., 2018; Letcher et al., 2019a), and opponent-shaping algorithms including Learning with OpponentLearning Awareness (LOLA) (Foerster et al., 2018) and its convergent counterpart, Stable Opponent Shaping (SOS) (Letcher et al., 2019b). Let A be this set of algorithms. Each has shown promising theoretical implications and empirical results, but none offers insight into global convergence in the non-convex setting, which includes the vast majority of machine learning applications. One of the main roadblocks compared with single-loss optimization has been noted by Schaefer & Anandkumar (2019): “a convergence proof in the nonconvex case analogue to Lee et al. (2016) is still out of reach in the competitive setting. A major obstacle to this end is the identification of a suitable measure of progress (which is given by the function value in the single agent setting), since norms of gradients can not be expected to decay monotonously for competitive dynamics in non-convex-concave games.”
It has been established that Hamiltonian Gradient Descent converges in two-player zero-sum games under a “sufficiently bilinear” condition by Abernethy et al. (2019), but this algorithm is unsuitable for optimization as it cannot distinguish between minimization and maximization (Hsieh et al., 2020, Appendix C.4). Global convergence has also been established for some algorithms in a few special cases: potential and Hamiltonian games (Balduzzi et al., 2018), zero-sum games satisfying the twosided Polyak-Łojasiewicz condition (Yang et al., 2020), zero-sum linear quadratic games (Zhang et al., 2019) and zero-sum games whose loss and first three derivatives are bounded (Mangoubi & Vishnoi, 2020). These are significant contributions with several applications of interest, but do not include any of the architectures mentioned above. Finally, Balduzzi et al. (2020) show that GD dynamics are bounded under a ‘negative sentiment’ assumption in smooth markets, which do include GANs – but this does not imply convergence, as we will show.
On the other hand, failure of global convergence has been shown for the Multiplicative Weights Update method by Palaiopanos et al. (2017), for policy-gradient algorithms by Mazumdar et al. (2020), and for simultaneous and alternating gradient descent (simGD and AGD) by Vlatakis-Gkaragkounis et al. (2019); Bailey et al. (2019), with interesting connections to Poincaré recurrence. Nonetheless, nothing is claimed about other optimization methods. Farnia & Ozdaglar (2020) show that GANs may have no Nash equilibria, but it does not follow that algorithms fail to converge since there may be locally-attracting but non-Nash critical points (Mazumdar et al., 2019, Example 2).
Finally, Hsieh et al. (2020) uploaded a preprint just after the completion of this work with a similar focus to ours. They prove that generalized Robbins-Monro schemes may converge with arbitrarily high probability to spurious attractors. This includes simGD, AGD, stochastic EG, optimistic gradient and Kiefer-Wolfowitz. However, Hsieh et al. (2020) focus on the possible occurrence of undesirable convergence phenomena for stochastic algorithms. We instead prove that desirable convergence properties cannot simultaneously hold for all algorithms (including deterministic). Moreover, their results apply only to decreasing step-sizes whereas ours include constant step-sizes. These distinctions are further highlighted by Hsieh et al. (2020) in the further related work section. Taken together, our works give a fuller picture of the failure of global convergence in multi-loss optimization.
Contribution. We prove that global convergence in multi-loss optimization is fundamentally incompatible with the ‘reasonable’ requirement that algorithms avoid strict maxima and converge only to critical points. We construct a two-player game with zero-sum interactions whose losses are coercive and analytic, but whose only critical point is a strict maximum (Theorem 1). Reasonable algorithms must either diverge to infinite losses or cycle (bounded non-convergent iterates).
One might hope that global convergence could at least be guaranteed in games with strict minima and no other critical points. On the contrary we show that strict minima can have arbitrarily small regions of attraction, in the sense that reasonable algorithms will fail to converge there with arbitrarily high probability for fixed initial parameter distribution (Theorem 2).
Finally, restricting the game class even further, we construct a zero-sum game in which all algorithms in A (as defined in Appendix A) are proven to cycle (Theorem 3). It may be that cycles do not arise in high-dimensional games of interest including GANs. Proving or disproving this is an important avenue for further research, but requires that we recognise the impossibility of global guarantees in the first place.

heading: 2 BACKGROUND

heading: 2.1 SINGLE LOSSES: GLOBAL CONVERGENCE OF GRADIENT DESCENT
text: Given a continuously differentiable function f : Rd → R, let
θk+1 = θk − α∇f(θk)
be the iterates of gradient descent with learning rate α, initialised at θ0. Under standard regularity conditions, gradient descent converges globally to critical points: Proposition 1. Assume f ∈ C2 has compact sublevel sets and is either analytic or has isolated critical points. For any θ0 ∈ Rd, define U0 = {f(θ) ≤ f(θ0)} and let L < ∞ be a Lipschitz constant for ∇f in U0. Then for any 0 < α < 2/L we have limk θk = θ̄ for some critical point θ̄.
The requirements for convergence are relatively mild:
1. f has compact sublevel sets iff f is coercive, lim‖θ‖→∞ f(θ) =∞, which mostly holds in machine learning since f is a loss function.
2. f has isolated critical points if it is a Morse function (nondegenerate Hessian at critical points), which holds for almost all C2 functions. More precisely, Morse functions form an open, dense subset of all functions f ∈ C2(Rd,R) in the Whitney C2-topology.
3. Global Lipschitz continuity is not assumed, which would fail even for cubic polynomials.
The goal of this paper is to prove that similar (even weaker) guarantees cannot be obtained in the multi-loss setting – not only for GD, but for any reasonable algorithm. This has to do with the more complex nature of gradient vector fields arising from multiple losses.

heading: 2.2 DIFFERENTIABLE GAMES
text: Following Balduzzi et al. (2018), we frame the problem of multi-loss optimization as a differentiable game among cooperating and competing agents/players. These may simply be different internal components of a single system, like the generator and discriminator in GANs.
Definition 1. A differentiable game is a set of n agents with parameters θ = (θ1, . . . , θn) ∈ Rd and twice continuously differentiable losses Li : Rd → R, where θi ∈ Rdi for each i and ∑ i di = d.
Losses are not assumed to be convex/concave in any of the parameters. In practice, losses need only be differentiable almost-everywhere: think of neural nets with rectified linear units.
If n = 1, the ‘game’ is simply to minimise a given loss function. We write ∇iLk = ∇θiLk and ∇ijLk = ∇θj∇θiLk for any i, j, k, and define the simultaneous gradient of the game
ξ = ( ∇1L1, . . . ,∇nLn )T ∈ Rd as the concatenation of each player’s gradient. If each agent independently minimises their loss using GD with learning rate α, the parameter update for all agents is given by θ ← θ − αξ(θ). We call this simultaneous gradient descent (simGD), or GD for short. We call θ̄ a critical point if ξ(θ̄) = 0. Now introduce the ‘Hessian’ (or Jacobian) of the game as the block matrix
H = ∇ξ = ∇11L 1 · · · ∇1nL1 ... . . .
... ∇n1Ln · · · ∇nnLn  ∈ Rd×d . Importantly note that H is not symmetric in general unless n = 1, in which case we recover the usual Hessian H = ∇2L. However H can be decomposed into symmetric and anti-symmetric components as H = S + A (Balduzzi et al., 2018). A second useful decomposition has appeared recently in (Letcher et al., 2019b) and (Schaefer & Anandkumar, 2019): H = Hd + Ho where Hd and Ho are the matrices of diagonal and off-diagonal blocks; formally, Hd = ⊕ i∇iiLi. One solution concept for differentiable games, analogous to the single-loss case, is defined as follows.
Definition 2. A critical point θ̄ is a (strict, local) minimum if H(θ̄) 0.1
These were named (strict) stable fixed points by Balduzzi et al. (2018), but the term is usually reserved in dynamical systems to the larger class defined by Hessian eigenvalues with positive real parts, which is implied but not equivalent to H 0 for non-symmetric matrices. In particular, strict minima are (differential) Nash equilibria as defined by Mazumdar et al. (2019), since diagonal blocks must also be positive definite: ∇iiLi(θ̄) 0. The converse does not hold.
Algorithm class. This paper is concerned with any algorithm whose iterates are obtained by initialising θ0 and applying a function F to the previous iterates, namely θk+1 = F (θk, . . . , θ0). This holds for all gradient-based methods (deterministic or stochastic); most of them are only functions
1For non-symmetric matrices, positive definiteness is defined as H 0 iff uTHu > 0 for all non-zero u ∈ Rd. This is equivalent to the symmetric part S of H being positive definite.
of the current iterate θk, so that θk = F k(θ0). All probabilistic statements in this paper assume that θ0 is initialised following any bounded and continuous measure ν on Rd. Continuity is a weak requirement and widely holds across machine learning, while boundedness mostly holds in practice since the bounded region can be made large enough to accommodate required initial points.
For single-player games, the goal of such algorithms is for θk to converge to a local (perhaps global) minimum as k → ∞. The goal is less clear for differentiable games, but is generally to reach a minimum or a Nash equilibrium. In the case of GANs the goal might be to reach parameters that produce realistic images, which is more challenging to define formally.
Throughout the text we use the term (limit) cycle to mean bounded but non-convergent iterates. This terminology is used because bounded iterates are non-convergent if and only if they have at least two accumulation points, between which they must ‘cycle’ infinitely often. This is not to be taken literally: the set of accumulation points may not even be connected. Hsieh et al. (2020) provide a more complete characterisation of these cycles.
Game class. Expecting global guarantees in all differentiable games is excessive, since every continuous dynamical system arises as simultaneous GD on the loss functions of a differentiable game (Balduzzi et al., 2020, Lemma 1). For this reason, the aforementioned authors have introduced a vastly more tractable class of games called markets. Definition 3. A (smooth) market is a differentiable game where interactions between players are pairwise zero-sum, namely,
Li(θ) = Li(θi) + ∑ j 6=i gij(θ i, θj)
with gij(θi, θj) + gji(θj , θi) = 0 for all i, j.
This generalises zero-sum games while remaining amenable to optimization and aggregation, meaning that “we can draw conclusions about the gradient-based dynamics of the collective by summing over properties of its members” (Balduzzi et al., 2020). Moreover, this class captures a large number of applications including GANs and related architectures, intrinsic curiosity modules, adversarial training, task-suites and population self-play. One would modestly hope for some reasonable algorithm to converge globally in markets. We will prove that even this is too much to ask.

heading: 2.3 REASONABLE ALGORITHMS
text: We wish to prove that global convergence is at odds with weak, ‘reasonable’ desiderata. The first requirement is that fixed points of an optimization algorithm F are critical points. Formally,
F (θ) = θ =⇒ ξ(θ) = 0 . (R1)
If not, some agent i could strictly improve its losses by following the gradient −∇iLi 6= 0. There is no reason for a gradient-based algorithm to stop improving if its gradient is non-zero.
The second requirement is that algorithms avoid strict maxima. Analogous to strict minima, they are defined for single losses by a negative-definite Hessian H ≺ 0. Converging to such a point θ̄ is the opposite goal of any meaningful algorithm since moving anywhere away from θ̄ decreases the loss. There are multiple ways of generalising this concept for multiple losses, but Proposition 2 below justifies that H ≺ 0 is the weakest one. Proposition 2. Write λ(A) = Re(Spec(A)) for real parts of the eigenvalues of a matrix A. We have the following implications, and none of them are equivalences.
maxλ(H) < 0 minλ(H) < 0
H ≺ 0 minλ(S) < 0
maxλ(Hd) < 0 minλ(Hd) < 0
Definition 4. A critical point θ̄ is a (strict, local) maximum if H(θ̄) ≺ 0.
Imposing that algorithms avoid strict maxima is therefore the weakest possible requirement of its kind. Note that the bottom-left implication Proposition 2 is equivalent to ∇iiLi ≺ 0 for all i, so strict maxima are also strict maxima of each player’s individual loss function. Players can all decrease their losses by moving anywhere away from them. It is exceedingly reasonable to ask that optimization algorithms avoid these points almost surely. Formally, we require that for any strict maximum θ̄ and bounded region U there are hyperparameters such that
µ ( {θ0 ∈ U | lim
k θk = θ̄}
) = 0 . (R2)
µ denotes Lebesgue measure. Hyperparameters may depend on the given game and the region U , as is typical for learning rates in gradient-based methods. Definition 5 (Reason). An algorithm is reasonable if it satisfies R1 and R2.
Reason is not equivalent to rationality or self-interest. Reason is much weaker, imposing only that agents are well-behaved regarding strict maxima even if their individual behavior is not selfinterested. For instance, SGA agents do not behave out of self-interest (Balduzzi et al., 2018).

heading: 3 GLOBAL CONVERGENCE IN DIFFERENTIABLE GAMES

heading: 3.1 REASONABLE ALGORITHMS FAIL TO CONVERGE GLOBALLY
text: Our main contribution is to show that global guarantees do not exist for any reasonable algorithm. First recall that global convergence should not be expected in all games, since there may be a divergent direction with minimal loss (imagine minimising L = ex). It should however be asked that algorithms have bounded iterates in coercive games, defined by coercive losses
lim ‖θ‖→∞
Li(θ) =∞
for all i. Indeed, unbounded iterates in coercive games would lead to infinite losses for all agents, the worst possible outcome. Given bounded iterates, convergence should hold if the Hessian is nondegenerate at critical points (which must therefore be isolated, recall Proposition 1). We call such a game nondegenerate. This condition can also be replaced by analyticity of the loss. In the spirit of weakest assumptions, we ask for convergence when both conditions hold. Definition 6 (Globality). An algorithm is global if, in a coercive, analytic and nondegenerate game, for any fixed θ0, iterates θk are bounded and converge for suitable hyperparameters. (G1)
Note that GD is global for single-player games by Proposition 1. Unfortunately, reason and globality are fundamentally at odds as soon as we move to two-player markets. Theorem 1. There is a coercive, nondegenerate, analytic two-player marketM whose only critical point is a strict maximum. In particular, algorithms only have four possible outcomes inM:
1. Iterates are unbounded, and all players diverge to infinite loss. [Not global]
2. Iterates are bounded and converge to the strict maximum. [Not reasonable]
3. Iterates are bounded and converge to a non-critical point. [Not reasonable]
4. Iterates are bounded but do not converge (cycle). [Not global]
Proof. Consider the analytic marketM given by
L1(x, y) = x6/6− x2/2 + xy + 1 4
( y4
1 + x2 − x
4
1 + y2 ) L2(x, y) = y6/6− y2/2− xy − 1
4
( y4
1 + x2 − x
4
1 + y2
) .
We prove in Appendix D thatM is coercive, nondegenerate, and has a unique critical point at the origin, which is a strict maximum.
Constructing an algorithm with global guarantees is therefore doomed to be unreasonable in that it will converge to strict maxima or non-critical points inM. None of the outcomes ofM are satisfactory. The first three are highly objectionable, as already discussed. The fourth is less obvious, and may even have game-theoretic significance (Papadimitriou & Piliouras, 2019), but is counter-intuitive from an optimization standpoint. Terminating the iteration would lead to a non-critical point, much like the third outcome. Even if we let agents update parameters continuously as they play a game or solve a task, they will have oscillatory behavior and fail to produce consistent outcomes (e.g. when generating an image or playing Starcraft).
The hope for machine learning is that such predicaments do not arise in applications we care about, such as GANs or intrinsic curiosity. This may well be the case, but proving or disproving global convergence in these specific settings is beyond the scope of this paper.
Remark. Why can this approach not be used to disprove global convergence for single losses? One reason is that we cannot construct a coercive loss with no critical points other than strict maxima: coercive losses, unlike games, always have a global minimum.

heading: 3.2 WHAT IF THERE ARE STRICT MINIMA?
text: One might wonder if it is purely the absence of strict minima that causes non-convergence, since strict minima are locally attracting under gradient dynamics. Can we guarantee global convergence if we impose existence of a minimum, and more, the absence of any other critical points?
Unfortunately, strict minima may have an arbitrarily small region of attraction. Assuming parameters are initialised following any bounded continuous measure ν on Rd, we can always modifyM by deforming a correspondingly small region around the origin, turning it into a minimum while leaving the dynamics unchanged outside of this region.
For a fixed initial distribution, any reasonable algorithm can therefore enter a limit cycle or diverge to infinite losses with arbitrarily high probability. Theorem 2. Given a reasonable algorithm with bounded continuous distribution on θ0 and a real number > 0, there exists a coercive, nondegenerate, almost-everywhere analytic two-player marketMσ with a strict minimum and no other critical points, such that θk either cycles or diverges to infinite losses for both players with probability at least 1− .
Proof. Let 0 < σ < 0.1 and define
fσ(θ) =
{ (x2 + y2 − σ2)/2 if ‖θ‖ ≥ σ
(y2 − 3x2)(x2 + y2 − σ2)/(2σ2) otherwise, where θ = (x, y) and ‖θ‖ = √ x2 + y2 is the standard L2-norm. Note that fσ is continuous since
lim ‖θ‖→σ+ fσ(x, y) = 0 = lim ‖θ‖→σ− fσ(x) .
Now consider the two-player marketMσ given by
L1(x, y) = x6/6− x2 + fσ(x, y) + xy + 1
4
( y4
1 + x2 − x
4
1 + y2 ) L2(x, y) = y6/6− fσ(x, y)− xy − 1
4
( y4
1 + x2 − x
4
1 + y2
) .
We prove in Appendix E thatMσ is a coercive, nondegenerate, almost-everywhere analytic game whose only critical point is a strict minimum at the origin. We then prove that θk cycles or diverges with probability at least 1− , and plot iterates for each algorithm in A.

heading: 3.3 HOW DO EXISTING ALGORITHMS BEHAVE?
text: Any algorithm will either fail to be reasonable or global inM. Nonetheless, it would be interesting to determine the specific failure that each algorithm in A exhibits. Each of them is defined in
Appendix A, writing α for the learning rate and γ for the Consensus Optimization hyperparameter. We expect each algorithm to be reasonable and moreover to have bounded iterates inM for suitably small hyperparameters. If this holds, they must cycle by Theorem 1.
This was witnessed experimentally across 1000 runs for α = γ = 0.01, with every run resulting in cycles. A single such run is illustrated in Figure 1. Algorithms may follow one of the three other outcomes for other hyperparameters, for instance diverging to infinite loss if α is too large or converging to the strict maximum for CO if γ is too large. The point here is to characterise the ‘regular’ behavior which can be seen as that occurring for sufficiently small hyperparameters.
Instead of proving that algorithms must cycle inM, we construct a zero-sum game N with similar properties asM and prove below that algorithms in A almost surely fail to converge there for small α, γ. This is stronger than proving the analogous result forM, since N belongs to the even smaller class of zero-sum games which one might have hoped was well-behaved.
In this light, one might wish to extend Theorem 1 to zero-sum games. However, zero-sum games cannot be coercive since L1 → ∞ implies L2 → −∞. It is therefore unclear whether global guarantees should be expected. Note however that N will be weakly-coercive in the sense that
lim ‖θi‖→∞
Li(θi, θ−i) =∞
for all i and fixed θ−i.
Theorem 3. There is a weakly-coercive, nondegenerate, analytic two-player zero-sum game N whose only critical point is a strict maximum. Algorithms in A almost surely have bounded nonconvergent iterates in N for α, γ sufficiently small.
Proof. Consider the analytic zero-sum game N given by
L1 = xy − x2/2 + y2/2 + x4/4− y4/4 = −L2 .
We prove in Appendix F that N is weakly-coercive, nondegenerate, and has a unique critical point at the origin which is a strict maximum. We prove that algorithms in A have the origin as unique fixed points, with negative-definite Jacobian for α, γ small, hence failing to converge almost surely. We moreover prove that algorithms have bounded non-convergent iterates inN for α, γ sufficiently small. Iterates are plotted for a single run of each algorithm in Figure 3 with α = γ = 0.01.
As in M, the behavior of each algorithm may differ for larger hyperparameters. All algorithms may have unbounded iterates or converge to the strict maximum for large α, while EG and OMD may even converge to a non-critical point (see proof). All such outcomes are unsatisfactory, though unbounded iteration will not result in positive infinite losses for both players since L1 = −L2.

heading: 3.4 COROLLARY: THERE ARE NO SUITABLE MEASURES OF PROGRESS
text: A crucial step in proving global convergence of GD on single losses is showing that the set of accumulation points is a subset of critical points, using the function value as a ‘measure of progress’. The fact that this fails for differentiable games implies that there can be no suitable measures of progress for reasonable algorithms with bounded iterates. We formalise this below, answering the question of Schaefer & Anandkumar (2019) quoted in the introduction. Definition 7. A measure of progress for an algorithm given by θk+1 = F (θk) is a continuous map M : Rd → R, bounded below, such that M(F (θ)) ≤M(θ) and M(F (θ)) = M(θ) iff F (θ) = θ.
Measures of progress are very similar to descent functions, as defined by Luenberger & Ye (1984), and somewhat akin to Lyapunov functions. The function value f is a measure of progress for singleloss GD under the usual regularity conditions, while the gradient norm ‖ξ‖ is a measure of progress for GD in strictly convex differentiable games:
‖ξ(θ − αξ)‖2 = ‖ξ‖2 − αξTHtξ + o(α) ≤ ‖ξ‖2
for small α. Unfortunately, games likeM prevent the existence of such measures in general. Corollary 1. There are no measures of progress for reasonable algorithms which produce bounded iterates inM or N .
Assuming the algorithm to be reasonable is necessary: any map is a measure of progress for the unreasonable algorithm F (θ) = θ. Assuming the algorithm to have bounded iterates inM or N is necessary: M(θ) = exp (− θ · 1) is a measure of progress for the reasonable but always-divergent algorithm F (θ) = θ + 1, where 1 is the constant vector of ones.

heading: 4 CONCLUSION
text: We have proven that global convergence is fundamentally at odds with weak, desirable requirements in multi-loss optimization. Any reasonable algorithm can cycle or diverge to infinite losses, even in two-player markets. This arises because coercive games, unlike losses, may have no critical points other than strict maxima. However, this is not the only point of failure: strict minima may have arbitrarily small regions of attraction, making convergence arbitrarily unlikely.
Limit cycles are not necessarily bad: they may even have game-theoretic significance (Papadimitriou & Piliouras, 2019). This paper nonetheless shows that some games have no satisfactory outcome in the usual sense, even in the class of two-player markets. Players should neither escape to infinite losses, nor converge to strict maxima or non-critical points, so cycling may be the lesser evil. The community is accustomed to optimization problems whose solutions are single points, but cycles may have to be accepted as solutions in themselves.
The hope for machine learning practitioners is that local minima with large regions of attraction prevent limit cycles from arising in applications of interest, including GANs. Proving or disproving this is an interesting and important avenue for further research, with real implications on what to expect when agents learn while interacting with others. Cycles may for instance be unacceptable in self-driving cars, where oscillatory predictions may have life-threatening implications.

heading: A ALGORITHMS AND EXPERIMENT HYPERPARAMETERS
text: Each algorithm in A cited in the ‘Related Work’ section can be defined as F (θ) = θ − αG(θ) for some continuous G : Rd → Rd. We have already seen that simultaneous GD is given by GGD = ξ. The only examples in this paper are two-player games, for which AGD is given by
GAGD =
( ξ1(θ1, θ2)
ξ2(θ1 − αξ1, θ2) ) The other algorithms are given by
GEG = ξ ◦ (id− αξ) GOMD = 2ξ(θk)− ξ(θk−1) GSGA = (I + λA T )ξ GCO = (I + γH T )ξ
GCGD = (I + αHo) −1ξ GLA = (I − αHo)ξ
GLOLA = (I − αHo)ξ − α diag(HTo ∇L) GSOS = (I − αHo)ξ − pα diag(HTo ∇L) . For OMD, the previous iterate can be uniquely recovered as θk−1 = (id − αξ)−1(θk) using the proximal point algorithm if ‖H‖ ≤ L and α < 1/L, giving
GOMD = 2ξ − ξ ◦ (id− αξ)−1 .
In all experiments we initialise θ0 following a standard normal distribution and use a learning rate α = 0.01, with γ = 0.01 for CO. Learning rates αi could be chosen to be different for each player i, but we set them to be equal throughout this paper for simplicity. Claims regarding the behavior of each algorithm for sufficiently small αmean that all αi should be sufficiently small. The λ parameter for SGA is obtained by the alignment criterion introduced in the original paper,
λ = sign ( 〈ξ,HT ξ〉〈AT ξ,HT ξ〉 ) .
Similarly, the p parameter for SOS is given by a two-part criterion which need not be described here.
Accompanying code for all experiments can be found at https://github.com/aletcher/ impossibility-global-convergence.

heading: B PROOF OF PROPOSITION 1
text: We first prove a lemma and state a standard optimization result. Lemma 0. Let G ∈ C1(U,Rd) for an open set U . If G is L-Lipschitz then supθ∈U ‖∇G(θ)‖ ≤ L.
The proof is an adaptation of (Panageas & Piliouras, 2017, Lemma 7) for non-convex sets.
Proof. Fix any θ ∈ U and > 0. Since U is open, the ball Br(θ) of radius r centered at θ is contained in U for some r > 0. By Taylor expansion, for any unit vector θ′,
‖G(θ + rθ′)−G(θ)‖ ≥ r ‖∇G(θ)θ′‖ − o(r) ≥ r ‖∇G(θ)θ′‖ − r for r sufficiently small. Since G is L-Lipschitz, we obtain
r ‖∇G(θ)θ′‖ ≤ ‖G(θ + rθ′)−G(θ)‖+ r ≤ r(L+ ) . Since was arbitrary, ‖∇G(θ)θ′‖ ≤ L for any unit θ′. By definition of the norm, we obtain
‖∇G(θ)‖ = sup ‖θ′‖=1
‖∇G(θ)θ′‖ ≤ L
for all θ ∈ U and hence supθ∈U ‖∇G(θ)‖ ≤ L.
Proposition ((Lange, 2013, Prop. 12.4.4) and (Absil et al., 2005, Th. 4.1)). Assume f has LLipschitz gradient and is either analytic or has isolated critical points. Then for any 0 < α < 2/L and θ0 ∈ Rd we have
lim k ‖θk‖ =∞ or lim k θk = θ̄
for some critical point θ̄. If f moreover has compact sublevel sets then the latter holds, limk θk = θ̄.
We can now prove Proposition 1, which avoids requiring Lipschitz continuity by proving that iterates are contained in the sublevel set given by θ0 for appropriate learning rate α.
Proposition 1. Assume f ∈ C2 has compact sublevel sets and is either analytic or has isolated critical points. For any θ0 ∈ Rd, define U0 = {f(θ) ≤ f(θ0)} and let L < ∞ be a Lipschitz constant for ∇f in U0. Then for any 0 < α < 2/L we have limk θk = θ̄ for some critical point θ̄.
Proof. Note that ∇f ∈ C1, so f has L-Lipschitz gradient inside any compact set U for some finite L, and supθ∈U‖∇2f(θ)‖ ≤ L by Lemma 0. Now define Uα = {θ − tα∇f(θ) | t ∈ [0, 1], θ ∈ U0} and the continuous function L(α) = supθ∈Uα ∥∥∇2f(θ)∥∥. Notice that U0 ⊂ Uα′ for all α. We prove that αL(α) < 2 implies Uα = U0 and in particular, L(α) = L(0). By Taylor expansion,
f(θ − tα∇f) = f(θ)− α ‖∇f(θ)‖2 + t 2α2
2 ∇f(θ)T∇2f(θ − t′α∇f)f(θ)
for some t′ ∈ [0, t] ⊂ [0, 1]. Since θ − t′α∇f ∈ Uα, it follows that
f(θ − tα∇f) ≤ f(θ)− α ‖∇f(θ)‖2 (1− αL(α)/2) ≤ f(θ)
for all αL(α) < 2. In particular, θ− tα∇f ∈ U0 and hence Uα = U0. We conclude that αL(α) < 2 implies L(α) = L(0), implying in turn αL(0) < 2. We now claim the converse, namely that αL(0) < 2 implies αL(α) < 2. For contradiction, assume otherwise that there exists α′L(0) < 2 with α′L(α′) ≥ 2. Since αL(α) is continuous and 0L(0) = 0 < 2, there exists ᾱ ≤ α′ such that ᾱL(0) < 2 and ᾱL(ᾱ) = 2. This is in contradiction with continuity:
2 = ᾱL(ᾱ) = lim α→ᾱ− αL(α) = lim α→ᾱ− αL(0) = ᾱL(0) .
Finally we conclude that Uα = U0 for all αL(0) < 2, and in particular, for all αL < 2. Finally, θk ∈ U0 implies θk+1 ∈ Uα = U0 and hence θk ∈ U0 by induction. The result now follows by applying the previous proposition to f |U0 .

heading: C PROOF OF PROPOSITION 2
text: Proposition 2. Write λ(A) = Re(Spec(A)) for real parts of the eigenvalues of a matrix A. We have the following implications, and none of them are equivalences.
maxλ(H) < 0 minλ(H) < 0
H ≺ 0 minλ(S) < 0
maxλ(Hd) < 0 minλ(Hd) < 0
The top row is dynamics-based, governed by the collective Hessian, while the bottom row is gametheoretic wherebyHd = ⊕ ∇iiLi decomposes into agentwise Hessians. The left and right triangles collide respectively to strict maxima and saddles for single losses, since H = S = Hd = ∇2L.
Proof. First note that H ≺ 0 ⇐⇒ S ≺ 0 ⇐⇒ maxλ(S) < 0, so the leftmost term can be replaced by maxλ(S) < 0.
We begin with the leftmost implications. If maxλ(S) < 0 then S ≺ 0 by symmetry of S, implying both H ≺ 0 since uTHu = uTSu for all u ∈ Rd, and negative definite diagonal blocks∇2Lii ≺ 0; finally Hd ≺ 0. In particular this implies maxλ(H) < 0 and maxλ(Hd) ≺ 0 since real parts of eigenvalues of a negative definite matrix are negative.
The rightmost implications follow as above by contraposition: if minλ(S) ≥ 0 then S 0, which implies H 0 and Hd 0 and hence minλ(H) ≥ 0, minλ(Hd) ≥ 0. The top and bottom implications are trivial.
The diagonal implications hold by a trace argument:∑ i λi(H) = Tr(H) = Tr(Hd) = ∑ i λi(Hd) ,
hence maxλ(H) < 0 implies the LHS is negative and thus ∑ i λi(Hd) < 0. It follows that λi(Hd) < 0 for some i and finally minλ(Hd) < 0. The other diagonal holds identically.
We now prove that no implication is an equivalence. For the leftmost implications,
H = ( −1 2 2 −1 ) has maxλ(Hd) = −1 < 0 while maxλ(S) = 3 > 0, and
H = ( 2 4 −4 −4 ) has maxλ(H) = −1 < 0 while maxλ(S) = 2 > 0. This also proves the diagonal implications: the first matrix has minλ(Hd) = −1 < 0 but maxλ(H) = 3 > 0, and the second matrix has minλ(H) = −1 < 0 but maxλ(Hd) = 2 > 0. For the rightmost implications, swap the sign of the diagonal elements for the two matrices above.
The top and bottom implications are trivially not equivalences:
H = Hd = ( 1 0 0 −1 ) has minλ(H) = minλ(Hd) = −1 < 0 but maxλ(H) = maxλ(Hd) = 1 > 0.

heading: D PROOF OF THEOREM 1
text: The variable changes
(x′, y′) = (y,−x) , (x′, y′) = (−y, x) , (x′, y′) = (−x,−y) (†)
will be useful, taking the positive quadrant x, y ≥ 0 to the other three. Theorem 1. There is a coercive, nondegenerate, analytic two-player marketM whose only critical point is a strict maximum. In particular, algorithms only have four possible outcomes inM:
1. Iterates are unbounded, and all players diverge to infinite loss. [Not global]
2. Iterates are bounded and converge to the strict maximum. [Not reasonable]
3. Iterates are bounded and converge to a non-critical point. [Not reasonable]
4. Iterates are bounded but do not converge (cycle). [Not global]
For intuition purposes, M was constructed by noticing that there is no necessary reason for the local minima of two coercive losses to coincide: the gradients of each loss may only simultaneously vanish at a local maximum in each player’s respective coordinate. The highest-order terms (first and last) provide coercivity in both coordinates while still having zero-sum interactions. The −x2 and −y2 terms yield a strict local maximum at the origin, while the ±xy terms provide opposite incentives around the origin, preventing any other simultaneous critical point to arise.
Proof. Write θ = (x, y) and consider the analytic marketM given by
L1 = x6/6− x2/2 + xy + 1 4
( y4
1 + x2 − x
4
1 + y2 ) L2 = y6/6− y2/2− xy − 1
4
( y4
1 + x2 − x
4
1 + y2
)
with simultaneous gradient
ξ = x5 − x+ y − y4x2(1+x2)2 − x31+y2 y5 − y − x− x
4y 2(1+y2)2 − y3 1+x2  . We prove ‘by hand’ that the origin θ̄ = 0 is the only critical point (solution to ξ = 0). See further down for an easier approach based on Sturm’s theorem, computer-assisted though equally rigorous.
We can assume x, y ≥ 0 since any other solution can be obtained by a quadrant variable change (†). Now assume for contradiction that ξ = 0 with y 6= 0.
1. We first show that y > 1. Indeed,
0 = ξ2 = y 5 − y − x− x
4y
2(1 + y2)2 − y
3
1 + x2 < y5 − y = y(y4 − 1)
implies y > 1 since y ≥ 0.
2. We now show that y < 1.5. First assume for contradiction that x ≥ y, then
ξ1 = y − x+ x5 − xy4 2(1 + x2)2 − x 3 1 + y2 > 1− x+ x5 − x5/8− x3/2 := h(x) .
Now h′(x) = 35
8 x4 − 3 2 x2 − 1
has unique positive root
x0 =
√ 6 + 2 √ 79
35
and h(x)→∞ as x→∞, hence h attains its minimum at x0 and plugging x0 yields a contradiction
ξ1 > h(x0) > 0 .
We conclude that x < y, but combining this with x ≥ 0 yields
ξ2 > −2y + y5 − y5/8− y3 = y(7y4/8− y2 − 2) > 7y4/8− y2 − 2 > 0
for all y ≥ 1.5, since the rightmost polynomial is positive at y = 1.5 and has positive derivative
7y3/2− 2y = y(7y2/2− 2) ≥ 7(1.5)2/2− 2 > 0 .
We must therefore have y < 1.5 as required.
3. It remains only to show that ξ1 > 0 for all 1 < y < 1.5. First notice that fx(y) = ξ1(x, y) is concave in y for any fixed x ≥ 0 since
f ′x(y) = 1− 2y3x
(1 + x2)2 + 2x3
y
(1 + y2)2
and so
f ′′x (y) = − 6y2x
(1 + x2)2 + 2x3
1 + y2 − 4y2
(1 + y2)3 = − 6y
2x
(1 + x2)2 − 2x3 3y 2 − 1 (1 + y2)3 ≤ 0
for y > 1. It follows that fx attains its infimum on the boundary y ∈ {1, 1.5}, so it suffices to check that ξ1(x, 1) > 0 and ξ1(x, 1.5) > 0 for all x ≥ 0. First notice that
g(x) := x
2(1 + x2)2
satisfies
g′(x) = 1 + x2 − 4x2
2(1 + x2)2 =
1− 3x2
2(1 + x2)2 ,
which has a unique positive root at x0 = 1/ √
3. This critical point of g must be a maximum since g(x) > 0 for x > 0 and g(x)→ 0 as x→∞. It follows that
g(x) ≤ g(x0) = 1
2 √ 3(1 + 1/3)2 = 3 √ 3/32 .
We now obtain ξ1(x, 1) ≥ x5 − x3/2− x+ 1− 3 √ 3/32 := p(x)
and ξ1(x, 1.5) ≥ x5 − 4x3/13− x+ 1.5− (1.5)43 √ 3/32 := q(x) .
Notice that p′(x) = 5x4 − 3x2/2− 1
has unique positive root
x0 =
√ 3 + √ 89
20
and p(x)→∞ as x→∞, hence p attains its minimum at x0 and plugging x0 yields
ξ1(x, 1) ≥ p(x0) > 0 .
Similarly for q we have q′(x) = 5x4 − 12x2/13− 1
has unique positive root
x0 =
√ 6 + √ 881
65
and plugging x0 yields ξ1(x, 1.5) ≥ q(x0) > 0 .
We conclude that ξ1(x, y) ≥ min(ξ1(x, 1), ξ1(x, 1.5)) > 0
and the contradiction is complete, hence y = 0. Finally ξ2 = 0 = x, so θ̄ = 0 is the unique critical point as required. Now the Hessian at θ̄ is
H(θ̄) = ( −1 1 −1 −1 ) ,
which is negative definite since S(θ̄) = −I ≺ 0, so θ̄ is a nondegenerate strict maximum and M is nondegenerate. It remains only to prove coercivity of M, namely coercivity of L1 and L2. Coercivity of L1 follows by noticing that the dominant terms are x6/6 and y4/(1 + x2). Formally, first note that x 4
1+y2 ≤ x 4, hence
L1 ≥ x6/6− x4/4− x2/2 + xy + 1 4
( y4
1 + x2
) .
Now xy ≥ −|xy| ≥ −(2x2 + y2/8) by Young’s inequality, hence
L1 ≥ x6/6− x4/4− 5x2/2− y2/8 + 1 4
( y4
1 + x2
) .
For any sequence ‖θ‖ → ∞, either |x| → ∞ or |x| is bounded above by some k ∈ R and |y| → ∞. In the latter case, we have
lim ‖θ‖→∞ L1 ≥ lim |y|→∞
−k4/4− 5k2/2− y2/8 + y 4
4(1 + k2) =∞
since the leading term y4 is of even degree and has positive coefficient, so we are done. Otherwise, for |x| → ∞, we pursue the previous inequality to obtain
L1 ≥ x6/6− x4/4− 5x2/2 + y 2
8
( 2y2 1 + x2 − 1 ) .
Now notice that y2 ≥ x2 ≥ 1 implies
L1 ≥ x6/6− x4/4− 5x2/2 + x 2
8 ( x2 − 1 1 + x2 ) ≥ x6/6− x4/4− 5x2/2− x2/8 .
On the other hand, x2 ≥ y2 also implies L1 ≥ x6/6− x4/4− 5x2/2− x2/8
by discarding the first (positive) term in the brackets. Both cases lead to the same inequality and hence, for any sequence with |x| → ∞,
lim ‖θ‖→∞ L1 ≥ lim |x|→∞ x6/6− x4/4− 5x2/2− x2/8 =∞
since the leading term x6 has even degree and positive coefficient. Hence L1 is coercive, and the same argument holds for L2 by swapping x and y. As required we have constructed a coercive, nondegenerate, analytic two-player marketM whose only critical point is a strict maximum. In particular, any algorithm either has unbounded iterates with infinite losses or bounded iterates. If they are bounded, they either fail to converge or converge. If they converge, they either converge to a non-critical point or a critical point, which can only be the strict maximum.
[For an alternative proof that θ̄ = 0 is the only critical point, we may take advantage of computer algebra systems to find the exact number of real roots using the resultant matrix and Sturm’s theorem. Singular (Decker et al., 2019) is one such free and open-source system for polynomial computations, backed by published computer algebra references. In particular, the rootsur library used below is based on the book by Basu et al. (2006). First convert the equations into polynomials:{
2(1 + x2)2(1 + y2)(x5 − x+ y)− y4x(1 + y2)− 2x3(1 + x2)2 = 0 2(1 + y2)2(1 + x2)(y5 − y − x)− x4y(1 + x2)− 2y3(1 + y2)2 = 0 .
We compute the resultant matrix determinant of the system with respect to y, a univariate polynomial P in x whose zeros are guaranteed to contain all solutions in x of the initial system. We then use the Sturm sequence of P to find its exact number of real roots. This is implemented with the Singular code below, whose output is 1.
LIB "solve.lib"; LIB "rootsur.lib"; ring r = (0,x),(y),dp; poly p1 = 2*(1+xˆ2)ˆ2*(1+yˆ2)*(xˆ5-x+y)-yˆ4*x*(1+yˆ2)-2*xˆ3*(1+xˆ2)ˆ2; poly p2 = 2*(1+yˆ2)ˆ2*(1+xˆ2)*(yˆ5-y-x)-xˆ4*y*(1+xˆ2)-2*yˆ3*(1+yˆ2)ˆ2; ideal i = p1,p2; poly f = det(mp_res_mat(i)); ring s = 0,(x,y),dp; poly f = imap(r, f); nrroots(f);
We know that θ̄ = 0 is a real solution, so θ̄ must be the unique critical point.]

heading: E PROOF OF THEOREM 2
text: Theorem 2. Given a reasonable algorithm with bounded continuous distribution on θ0 and a real number > 0, there exists a coercive, nondegenerate, almost-everywhere analytic two-player marketMσ with a strict minimum and no other critical points, such that θk either cycles or diverges to infinite losses for both players with probability at least 1− .
Proof. We modify the construction from Theorem 1 by deforming a small region around the maximum to replace it with a minimum. First let 0 < σ < 0.1 and define
fσ(θ) =
{ (x2 + y2 − σ2)/2 if ‖θ‖ ≥ σ
(y2 − 3x2)(x2 + y2 − σ2)/(2σ2) otherwise, where θ = (x, y) and ‖θ‖ = √ x2 + y2 is the standard L2-norm. Note that fσ is continuous since
lim ‖θ‖→σ+ fσ(θ) = 0 = lim ‖θ‖→σ− fσ(θ) .
Now consider the two-player marketMσ given by
L1 = x6/6− x2 + fσ + xy + 1
4
( y4
1 + x2 − x
4
1 + y2 ) L2 = y6/6− fσ − xy − 1
4
( y4
1 + x2 − x
4
1 + y2
) .
The resulting losses are continuous but not differentiable; however, they are analytic (in particular smooth) almost everywhere, namely, for all θ not on the circle of radius σ. This is sufficient for the purposes of gradient-based optimization, noting that neural nets also fail to be everywheredifferentiable in the presence of rectified linear units.
We claim thatMσ has a single critical point at the origin θ̄ = 0. First note that
ξMσ = ξM0 = x5 − x+ y − y4x2(1+x2)2 − x31+y2 y5 − y − x− x
4y 2(1+y2)2 − y3 1+x2  = ξM for all ‖θ‖ ≥ σ, where M is the game from Theorem 1. It was proved there that the only real solution to ξ = 0 is the origin, which does not satisfy ‖θ‖ ≥ σ. Any critical point must therefore satisfy ‖θ‖ < σ, for which
ξ = ξMσ = x5 + x+ y − 2x(3x2 + y2)/σ2 − y4x2(1+x2)2 − x31+y2 y5 + y − x− 2y(y2 − x2)/σ2 − x
4y 2(1+y2)2 − y3 1+x2  . First note that θ̄ = 0 is a critical point; we prove that there are no others. The continuous parameter σ prevents us from using a formal verification system, so we must work ‘by hand’. Warning: the proof is a long inelegant string of case-by-case inequalities.
Assume for contradiction that ξ = 0 with θ 6= 0. First note that ‖θ‖ < σ implies |x|, |y| < σ, and x = 0 or y = 0 implies x = y = 0 using ξ1 = 0 or ξ2 = 0 respectively. We can therefore assume 0 < |x|, |y| < σ. We can moreover assume that x > 0, the opposite case following by the quadrant change of variables (x′, y′) = (−x,−y).
1. We begin with the case σ/2 ≤ x < σ. First notice that
x+ y − 2x(3x2 + y2)/σ2 = x(1− 6x2/σ2) + y(1− 2xy/σ2) ≤ x(1− 3/2) + y(1− y/σ)
and the rightmost term attains its maximum value for y = σ/2, hence
x+ y − 2x(3x2 + y2)/σ2 ≤ −x/2 + σ/4 ≤ 0 .
This implies
ξ1 ≤ x5 − y4x 2(1 + x2)2 − x 3 1 + y2 < x5 − x 3 1 + y2 < x3
( 1− y2 − 1
1 + y2
) = −x3y4
1 + y2 < 0
using x2 + y2 < 1, which is a contradiction to ξ = 0.
2. We proceed with the case x < σ/2 and |y| ≤ σ/2. First, y < 0 implies the contradiction
ξ2 < y − 2y3/σ2 − x4y 2(1 + y2)2 − y 3 1 + x2 < y/2− y
( σ4
25 + σ2 22
) < y ( 1
2 − 1 25 − 1 22
) < 0 ,
so we can assume y > 0. In particular we have (1− 2y(y + x)/σ2) > 0. If y ≤ x, we also obtain
ξ2 < y 5 + (y − x) ( 1− 2y(y + x)/σ2 ) − y 3
1 + x2 < y3
( y2 − 1
1 + x2
) < −y3x4
1 + x2 < 0 ,
so we can assume x < y. There are again two cases to distinguish. If x < σ/2− bσ2 with b = 0.08,
x(1− 6x2/σ2) + y(1− 2xy/σ2) > x(1− 3(1/2− σb)) + x(1− (1/2− σb)) > 4σbx
which implies the contradiction
ξ1 > 4σbx− y4x 2(1 + x2)2 − x 3 1 + y2 > σx
( 4b− σ 4
25 − σ
2
22
) > σx ( 4b− 1
25 − 1 22
) > 0 .
Finally assume x ≥ σ/2− bσ2. Then we have
(y−x)(1− 2y(x+ y)/σ2) < bσ2(1− 4x2/σ2) < bσ2(1− (1− 2σb)2) = 4σ3b2(1−σb) < 4σ3b2
and obtain
ξ2 < y 5 + 4σ3b2 − y
3
1 + x2 < σ3
( σ2/25 + 4b2 − (1/2− σb) 3
1 + σ2/4
) .
We claim that the rightmost term is negative. Indeed, the quantity inside the brackets has derivative
σ/24 + (1/2− σb)2 (1 + σ2/4)2 ( 3b(1 + σ2/4) + σ(1/2− σb)/2 ) > 0
and so its supremum across σ ∈ [0, 0.1] must be attained at σ = 0.1. We obtain the contradiction
ξ2 < σ 3 ( 0.01/25 + 4b2 − (1/2− b) 3
1 + 0.01/4
) < 0
for b = 0.08 and σ > 0, as required.
3. Finally, consider the case x < σ/2 and |y| > σ/2. First, y < 0 implies the contradiction
ξ1 < x+ y − 2x(3x2 + y2)/σ2 < −2x(3x2 + y2) < 0
so we can assume y > 0. Now assume y < σ − x(1 + σ2). Then
x(1− 6x2/σ2) + y(1− 2xy/σ2) > −x/2 + y(1− y/σ) > −x/2 + x(1 + σ2) > x(1/2 + σ2) ,
which yields the contradiction
ξ1 > x
( 1
2 + σ2 − y
4
2(1 + x2)2 − x
2
1 + y2
) > x ( 1/2 + σ2 − σ4 − σ2/4 ) > x(1/2− 1/4) > 0 .
We can therefore assume y ≥ σ − x(1 + σ2). We have
(y − x)(1− 2y(y + x)/σ2) < (y − x)(1− (y + x)/σ) ≤ (y − x)(1− (1− σx)) < σx(y − x)
which attains its maximum in x at x = y/2, hence
ξ2 < y 5 − y
3 1 + x2 + σy2 4 < σy2 4
( 4σ2 − 2
1 + σ2 + 4
) .
Finally we obtain the contradiction
ξ2 < σy2
4
( 5σ2 + 4σ4 − 1
1 + σ2
) < 0
for all σ < 0.1. All cases lead to contradictions, so we conclude that θ̄ is the only critical point, with positive definite Hessian
H(θ̄) = ( 1 1 −1 1 ) 0 ,
hence θ̄ is a strict minimum. Now notice thatM0 has the same dominant terms asM from Theorem 1, so coercivity ofM0 follows from the same argument. SinceMσ is identical toM0 outside the σ-ball Bσ = {(x, y) ∈ R2 | ‖θ‖ < σ}, coercivity ofM0 implies coercivity ofMσ for any σ. Fix any reasonable algorithm F , any bounded continuous measure ν on Rd with initial region U , and any > 0. We abuse notation somewhat and write F kσ (θ0) for the kth iterate of F inMσ with initial parameters θ0. We claim that there exists σ > 0 such that
Pν ( θ0 ∈ U and lim
k F kσ (θ0) = θ̄
) < .
Since θ̄ is the only critical point and Mσ is coercive, this implies bounded but non-convergent iterates or divergent iterates with infinite losses with probability at least 1− , proving the theorem. To begin, µ(Bσ)→ 0 as σ → 0 implies that we can pick σ′ > 0 such that Pν(θ0 ∈ Bσ′) < /2 by continuity of ν with respect to Lebesgue measure.
Now let Ū be the closure of U and define D = Ū ∩ {‖θ‖ ≥ σ′}. Note that D is compact since Ū is compact and closed subsets of a compact set are compact. F is reasonable, D is bounded and θ̄ = 0 is a strict maximum inM0, so there are hyperparameters such that the stable set
Z = {θ0 ∈ D | lim k F k0 (θ0) = 0}
has zero measure. We claim that Zδ := {θ0 ∈ D | inf
k∈N ∥∥F k0 (θ0)∥∥ < δ} has arbitrarily small measure as δ → 0. Assume for contradiction that there exists α > 0 such that µ(Zδ) ≥ α for all δ > 0. Then Zδ ⊂ Zδ′ and µ(Zδ) ≤ µ(D) <∞ for all δ < δ′ implies
µ (⋂ n∈N Z 1 n ) = lim n→∞ µ ( Z 1 n ) ≥ α
by Nelson (2015, Exercise 1.19). On the other hand,⋂ n∈N Z 1 n = Z0
yields the contradiction 0 = µ(Z0) ≥ α. We conclude that Zδ has arbitrarily small measure, hence there exists δ > 0 such that Pν(θ0 ∈ Zδ) < /2 by continuity of ν. Now let σ = min{σ′, δ} and notice that
θ0 ∈ D \ Zδ =⇒ inf k ∥∥F k0 (θ0)∥∥ ≥ δ ≥ σ =⇒ inf k ∥∥F kσ (θ0)∥∥ ≥ σ , where the last implication holds since Mσ and M0 are indistinguishable in {‖θ‖ ≥ σ}, so the algorithm must have identical iterates F kσ (θ0) = F k 0 (θ0) for all k. It follows by contraposition that limk F k σ (θ0) = θ̄ implies infk
∥∥F kσ (θ0)∥∥ < σ and so θ0 ∈ Zδ or θ0 /∈ D. Finally we obtain Pν ( θ0 ∈ U and lim
k F kσ (θ0) = θ̄
) = Pν (θ0 ∈ U ∩ Zδ or θ0 ∈ U \D)
≤ Pν (θ0 ∈ U ∩ Zδ) + Pν (θ0 ∈ U \D) ≤ Pν (θ0 ∈ Zδ) + Pν (θ0 ∈ Bσ′) < /2 + /2 =
as required. We plot iterates for a single run of each algorithm in Figure 3 with α = γ = 0.01.

heading: F PROOF OF THEOREM 3
text: Theorem 3. There is a weakly-coercive, nondegenerate, analytic two-player zero-sum game N whose only critical point is a strict maximum. Algorithms in A almost surely have bounded nonconvergent iterates in N for α, γ sufficiently small.
Proof. Consider the analytic zero-sum game N given by L1 = xy − x2/2 + y2/2 + x4/4− y4/4 = −L2
with simultaneous gradient
ξ = ( y − x+ x3 −x− y + y3 ) and Hessian
H = ( −1 + 3x2 1 −1 −1 + 3y2 ) .
We show that the only solution to ξ = 0 is the origin. First we can assume x, y ≥ 0 since any other solution can be obtained by a quadrant variable change (†). Now assume for contradiction that y 6= 0, then ξ2 = 0 = −x− y + y3 ≤ −y + y3 = y(y2 − 1) implies y ≥ 1 and hence
ξ1 = 0 = y − x+ x3 ≥ 1− x+ x3 = (x+ 1)(x− 1)2 + x2 > 0 which is a contradiction. It follows that y = 0 and hence ξ2 = 0 = x as required. Now the origin has invertible, negative-definite Hessian
H(0) = ( −1 1 −1 −1 ) ≺ 0
so the unique critical point is a strict maximum. The game is nondegenerate since the only critical point has invertible Hessian. The game is weakly-coercive since L1(x, ȳ) → ∞ for any fixed ȳ by domination of the x4 term; similarly for L2(x̄, y) by domination of the y4 term.
Bounded iterates: strategy. We begin by showing that all algorithms have bounded iterates inN for α, γ sufficiently small. For each algorithm F , our strategy is to show that there exists r > 0 such that for any s > 0 we have ‖F (θ)‖ < ‖θ‖ for all r < ‖θ‖ < s and α, γ sufficiently small. This will be enough to prove bounded iteration upon bounded initialisation. Denote by Br the ball of radius r centered at the origin.
GD. We have θT ξ = x(y − x+ x3) + y(−x− y + y3)
= x4 − x2 + y4 − y2
= (x2 − 1)2 + (y2 − 1)2 + x2 + y2 − 2 > 1
for all ‖θ‖2 = x2 + y2 > 3. For any s > 0 we obtain ‖F (θ)‖2 = ‖θ − αξ‖2 = ‖θ‖2 − 2αθT ξ + α2 ‖ξ‖2 < ‖θ‖ − α ( 2− α ‖ξ‖2 ) < ‖θ‖2
for all √
3 < ‖θ‖ < s and α sufficiently small, namely 0 < α < 2/ supθ∈Bs ‖ξ‖ 2.
EG. For any s > 0 and √
4 < ‖θ‖ < s we have ‖θ − αξ(θ)‖2 > 4− 2αθT ξ > 3
for α < 1/ supθ∈Bs 2θ T ξ. Now using θT ξ > 1 for all ‖θ‖2 > 3 by the argument for GD above,
‖F (θ)‖2 = ‖θ‖2 − 2αθT ξ(θ − αξ(θ)) + α2 ‖ξ(θ − αξ(θ))‖2
= ‖θ‖2 − 2α(θ − αξ(θ))T ξ(θ − αξ(θ)) +O(α2) < ‖θ‖2 − α (2−O(α)) < ‖θ‖2
for α sufficiently small.
AGD. For any s > 0, notice by continuity of ξ that there exists δ > 0 such that
θT (ξ1, ξ2(θ1 − αξ1, θ2)) > θT ξ − 1/2 for all α < δ and θ ∈ Bs, since Bs is bounded and θ1 − αξ1 → θ1 as α→ 0. It follows that
‖F (θ)‖2 = ‖θ‖2 − 2αθT (ξ1, ξ2(θ1 − αξ1, θ2)) +O(α2) < ‖θ‖2 − 2α(θT ξ − 1/2) +O(α2) < ‖θ‖2 − 2α(1− 1/2) +O(α2) < ‖θ‖2 − α(1−O(α)) < ‖θ‖2
for all √ 3 < ‖θ‖ < s and α < δ sufficiently small.
OMD. For any s > 0, notice by continuity of ξ that there exists δ > 0 such that∣∣θT (ξ(θ)− ξ((id− αξ)−1(θ))∣∣ < 1/2 for all α < δ and θ ∈ Bs, since Bs is bounded and (id− αξ)−1(θ)→ θ as α→ 0. It follows that
‖F (θ)‖2 = ‖θ‖2 − 2αθT ξ − 2αθT (ξ(θ)− ξ((id− αξ)−1(θ)) +O(α2) < ‖θ‖2 − 2α+ α+O(α2) = ‖θ‖2 − α(1−O(α)) < ‖θ‖2
for all √ 3 < ‖θ‖ < s and α < δ sufficiently small.
CO, CGD, LA, LOLA, SOS. Writing ν for γ if F = FCO and ν for α otherwise, for each algorithm we have F (θ) = θ − αξ + ανK for some continuous function K : Rd → R. For instance, K = −HT ξ for CO (see Appendix A). We obtain
‖F (θ)‖2 = ‖θ − αξ + ανK‖2
= ‖θ‖2 − 2αθT ξ + 2ανθTK − 2α2νξTK + α2 ‖ξ‖2 + α2ν2 ‖K‖ = ‖θ‖2 − α ( 2θT ξ − 2νθTK + 2ανξTK − α ‖ξ‖2 − αν2 ‖K‖ ) .
Notice that every term in the brackets contains an α or ν except for the first. We have already shown that θT ξ > 1 for all ‖θ‖2 > 3 for GD above, hence for any s > 0 we have
‖F (θ)‖2 < ‖θ‖2 − α (
2− 2ν sup θ∈Bs θTK + 2αν inf θ∈Bs ξTK − α sup θ∈Bs ‖ξ‖2 − α sup θ∈Bs
ν2 ‖K‖ )
= ‖θ‖2 − α (2−O(α, ν)) < ‖θ‖2
for all √ 3 < ‖θ‖2 < s and α, ν sufficiently small.
SGA. The situation differs from the above since parameter λ follows an alignment criterion, namely λ = sign ( 〈ξ,HT ξ〉〈AT ξ,HT ξ〉 ) , which cannot be made small. First note that
θTGSGA = θ tξ + λθT (AT ξ) = x4 + y4 − x2 − y2 + λ(x2 + y2 + x3y − xy3) .
If λ = −1, θTGSGA = x 4 + y4 − 2x2 − 2y2 − x3y + xy3 and splitting x4 + y4 in two yields
x4 + y4
2 − 2x2 − 2y2 = 1 4
[ (x2 − y2)2 + (x2 + y2)(x2 + y2 − 8) ] > 1
for ‖θ‖2 = x2 + y2 > 9, while
x4 + y4
2 − x3y + xy3 = 1 2
[ (−x2 + xy + y2)2 + x2y2 ] > 0
for ‖θ‖ > 0. Summing the two yields θTGSGA > 1 for ‖θ‖2 > 9 and λ = −1. If λ = 1,
θTGSGA = x 4 + y4 + x3y − xy3
= x4 + y4 − 2x2 − 2y2 + x3y − xy3 + 2(x2 + y2) ≥ x4 + y4 − 2x2 − 2y2 + x3y − xy3 > 1
for ‖θ‖2 > 9 by swapping x and y in the λ = −1 case above. We conclude θTGSGA > 1 for ‖θ‖2 > 9 regardless of λ. For any s > 0 we obtain
‖F (θ)‖2 = ‖θ‖2 − 2αθTGSGA + α2 ‖GSGA‖2 < ‖θ‖2 − α ( 2− α ‖GSGA‖2 ) < ‖θ‖2
for all 3 < ‖θ‖ < s and α < 2/ supθ∈Bs GSGA.
Bounded iterates: conclusion. Now assume as usual that θ0 is initalised in any bounded region U . For each algorithm we have found r such that for any s > 0 we have ‖F (θ)‖ < ‖θ‖ for all r < ‖θ‖ < s and α, γ sufficiently small. Now pick r′ ≥ r such that U ⊂ Br′ . Define the bounded region V = {θ − tG(θ) | t ∈ [0, 1], θ ∈ Br′} . and pick s ≥ r′ such that V ⊂ Bs. By the above we have ‖F (θ)‖ < ‖θ‖ for all r < ‖θ‖ < s and α, γ sufficiently small. In particular, fix any α, γ < 1 satisfying this condition. We claim that F (θ) ∈ Bs for all θ ∈ Bs. Indeed, either θ ∈ Br implies F (θ) = θ − αG(θ) ∈ V ⊂ Bs or θ /∈ Br implies ‖F (θ)‖ < ‖θ‖ < s and so F (θ) ∈ Bs. We conclude that θ0 ∈ U ⊂ Bs implies bounded iterates θk = F k(θ) ∈ Bs for all k.
Non-convergence: strategy. We show that all methods inA have the origin as unique fixed points for α, γ sufficiently small. Fixed points of each gradient-based method are given by G = 0, where G is given in Appendix A, and we moreover show that the Jacobian ∇G at the origin is negativedefinite. Non-convergence will follow from this for α sufficiently small.
GD. Fixed points of simultaneous GD correspond by definition to critical points:
GGD = ξ = 0 ⇐⇒ θ = 0 .
The Jacobian of G at 0 is
∇ξ = H = ( −1 1 −1 −1 ) ≺ 0 .
AGD. We have GAGD = 0 ⇐⇒ { ξ1 = 0
ξ2(θ1 − αξ1, θ2) = 0 ⇐⇒
{ ξ1 = 0
ξ2 = 0 ⇐⇒ ξ = 0 ⇐⇒ θ = 0 .
Now
ξ2(x− αξ1(x, y), y) = −(x− α(y − x+ x3))− y + y3
= x(−1− α) + y(−1 + α) + αx3 + y3
so the Jacobian at the origin is
JAGD = ( −1 1 −1− α −1 + α ) with symmetric part
SAGD = ( −1 −α/2 −α/2 −1 + α ) which has negative trace for all α < 2 and positive determinant
−α2/2− α+ 1 = −(α+ 1)2/2 + 3/2 > −9/8 + 3/2 > 0
for all α < 1/2, which together imply negative eigenvalues and hence SAGD ≺ 0. Recall that a matrix is negative-definite iff its symmetric part is, hence JAGD ≺ 0 for all α < 1/2.
EG. We have
GEG = ξ ◦ (id− αξ) = 0 ⇐⇒ id− αξ = 0 ⇐⇒
{ x− α(y − x+ x3) = 0
y − α(−x− y + y3) = 0 .
We have shown that any bounded initialisation results in bounded iterates for EG for α sufficiently small. Let U be this bounded region and assume for contradiction that id − αξ = 0 with x, y 6= 0 (noting that x = 0 implies y = 0 by the first equation and vice-versa). We can assume x, y > 0 since any other solution can be obtained by a quadrant change of variable (†). We first prove that x, y < 1 for 0 < α < 1/ supθ∈U{y − x+ x3}. Indeed we have
0 = ξ1 > x− α sup θ∈U > x− 1
hence x < 1. A similar derivation holds for y, hence 0 < x, y < 1. But now x ≥ y implies
0 = ξ1 ≥ x− α(y − y + x3) = x(1− αx2) ≥ x(1− α) > 0
for α < 1 while x < y implies
0 = ξ2 ≥ y − α(−x− x+ y3) = y(1− αy2) ≥ y(1− α) > 0
and the contradiction is complete, hence θ = 0 is the only fixed point of EG. Now JEG = H(I − αH) = ( −1 1 −1 −1 )( 1 + α −α α 1 + α ) = ( −1 1 + 2α −1− 2α −1 ) with SEG = −I ≺ 0, hence JEG ≺ 0 for all α.
OMD. By Daskalakis & Panageas (2018, Remark 1.5), fixed points of OMD must satisfy ξ = 0 by viewing OMD as mapping pairs (θk, θk−1) to pairs (θk+1, θk), hence θ = 0. Now
JOMD = 2H −H(I − αH)−1 = 2 ( −1 1 −1 −1 ) − 1
1 + 2α+ 2α2
( −1− 2α 1 −1 −1− 2α ) .
Now notice that 1 + 2α
1 + 2α+ 2α2 ≤ 1
and so
SOMD =
( −2 + 1+2α1+2α+2α2 0
0 −2 + 1+2α1+2α+2α2
) ≺ 0
for all α.
CO. We have GCO = (I + γH T )ξ = 0 ⇐⇒ ξ = 0 ⇐⇒ θ = 0
for all γ since the matrix
(I + γHT ) = ( 1− γ −γ γ 1− γ ) is always invertible with determinant (1− γ)2 + γ2 > 0. Now
JCO = (I + γH T )H = ( 1− γ −γ γ 1− γ )( −1 1 −1 −1 ) = ( −1 + 2γ 1 −1 −1 + 2γ ) ≺ 0
for all γ < 1/2.
SGA. We have GSGA = (I + λA
T )ξ = 0 ⇐⇒ ξ = 0 ⇐⇒ θ = 0 since antisymmetric A with eigenvalues ia, a ∈ R implies that I + λAT is always invertible with eigenvalues 1 + iλa 6= 0. Now recall that λ is given by
λ = sign ( 〈ξ,HT ξ〉〈AT , HT ξ〉 ) = sign ( ξTHT ξ · ξTAHT ξ ) .
We have
HT =
( −1 + 3x2 −1 1 −1 + 3y2 ) ≺ 0
and
AHT =
( 1 −1 + 3y2
1− 3x2 1
) 0
for all ‖θ‖ sufficiently small, hence ξTHT ξ ≤ 0 and ξTAHT ξ ≥ 0 and thus λ = sign ( 〈ξ,HT ξ〉〈AT , HT ξ〉 ) = sign ( ξTHT ξ · ξTAHT ξ ) ≤ 0
around the origin. Now
JSGA = (I + λA T )H = ( 1 −λ λ 1 )( −1 1 −1 −1 ) = ( −1 + λ 1 + λ −1− λ −1 + λ ) ≺ 0
for all λ < 1, which holds in particular for λ ≤ 0.
CGD. Note that Ho = ( 0 1 −1 0 ) = A
is antisymmetric, hence I + αHo is always invertible as for SGA and
GCGD = (I + αHo) −1ξ = 0 ⇐⇒ ξ = 0 ⇐⇒ θ = 0 .
Now
JCGD = (I + αHo) −1H =
1
1 + α2
( 1 −α α 1 )( −1 1 −1 −1 ) =
1
1 + α2
( −1 + α 1 + α −1− α −1 + α ) ≺ 0
for all α < 1.
LA. As above, GLA = (I − αHo)ξ = 0 ⇐⇒ ξ = 0 ⇐⇒ θ = 0
since (I − αHo) is always invertible. Now JLA = (I − αHo)H = (I − αA)H = ( −1 + α 1 + α −1− α −1 + α ) ≺ 0
for all α < 1.
LOLA. Notice that
diag ( HTo ∇L ) = diag (( 0 −1 1 0 )( y − x+ x3 −y + x− x3 x+ y − y3 −x− y + y3 )) = ( −x− y + y3 −y + x− x3 ) = Hoξ
and so GLOLA = (I − αHo)ξ − α diag ( HTo ∇L ) = (I − 2αHo)ξ ⇐⇒ ξ = 0 ⇐⇒ θ = 0
as for LA. Similarly, substituting 2α for α in the derivation for LA yields
JLOLA = (I − 2αHo)H ≺ 0
for all α < 1/2.
SOS. As for LOLA we have GSOS = (I − αHo)ξ − pα diag ( HTo ∇L ) = (I − α(1 + p)Ho)ξ ⇐⇒ ξ = 0 ⇐⇒ θ = 0
for any α, p. Now p(θ̄) = 0 for fixed points θ̄ by Letcher et al. (2019b, Lemma D.7), hence
JSOS = JLA = ( −1 + α 1 + α −1− α −1 + α ) ≺ 0
for all α < 1.
Non-convergence: conclusion. We conclude that all algorithms in A have the origin as unique fixed points, with negative-definite Jacobian, for α, γ sufficiently small. If a method converges, it must therefore converge to the origin. We show that this occurs with zero probability. One may invoke the Stable Manifold Theorem from dynamical systems, but there is a more direct proof.
Take any algorithm F in A and let U be the initialisation region. We prove that the stable set
Z = {θ0 ∈ U | lim k F k(θ0) = 0}
has Lebesgue measure zero for α sufficiently small. First assume for contradiction that θk → 0 with θk 6= 0 for all k. Then
G(θk) = G(0) +∇G(0)θk +O(‖θk‖2) = ∇G(θ̄)(θk) +O(‖θk‖2)
since G(0) = 0, and we obtain
‖θk+1‖2 = ‖θk − αG(θk)‖2
= ‖θk‖2 − 2αθTkG(θk) + α2 ‖G(θk)‖ 2
≥ ‖θk‖2 − 2αθTk∇G(0)θk +O(‖θk‖ 3 ) > ‖θk‖2
for all k sufficiently large, since ∇G(0) ≺ 0. This is a contradiction to θk → 0, so θk → 0 implies θk = 0 for some k and so, writing FU : U → Rd for the restriction of F to U ,
Z ⊂ ∪∞k=0F−kU ({0}) .
We claim that FU is a C1 local diffeomorphism, and a diffeomorphism onto its image. Now GU is C1 with bounded domain, hence L-Lipschitz for some finite L. By Lemma 0, the eigenvalues of∇G in U satisfy |λ| ≤ ‖∇G‖ ≤ L, hence ∇FU = I − α∇GU has eigenvalues 1 − αλ ≥ 1 − α|λ| ≥ 1 − αL > 0. It follows that ∇FU is invertible everywhere, so FU is a local diffeomorphism by the Inverse Function Theorem (Spivak, 1971, Th. 2.11). To prove that FU : U → F (U) is a diffeomorphism, it is sufficient to show injectivity of FU . Assume for contradiction that FU (θ) = FU (θ ′) with θ 6= θ′. Then by definition,
θ − θ′ = α(GU (θ′)−GU (θ))
and so ‖θ − θ′‖ = α ‖GU (θ′)−GU (θ)‖ ≤ αL ‖θ − θ′‖ < ‖θ − θ′‖ ,
a contradiction. We conclude that FU is a diffeomorphism onto its image with continuously differentiable inverse F−1U , hence F −1 U is locally Lipschitz and preserves measure zero sets. It follows by induction that µ(F−kU ({0})) = 0 for all k, and so
µ(Z) ≤ µ ( ∪∞k=0F−kU ({0}) ) = 0
since countable unions of measure zero sets have zero measure. Since θ0 follows a continuous distribution ν, we conclude
Pν ( lim k F k(θ0) = 0 ) = 0
as required. Since all algorithms were also shown to produce bounded iterates, they almost surely have bounded non-convergent iterates for α, γ sufficiently small. The proof is complete; iterates are plotted for a single run of each algorithm in Figure 3 with α = γ = 0.01.

heading: G PROOF OF COROLLARY 1
text: Corollary 1. There are no measures of progress for reasonable algorithms which produce bounded iterates inM or N .
Proof. Assume for contradiction that a measure of progressM exists for some reasonable algorithm F and consider the iterates θk produced in the gameM orN . We prove that the set of accumulation points of θk is a subset of critical points, following Lange (2013, Prop. 12.4.2). Consider any accumulation point θ̄ = limm→∞ θkm . The sequence M(θk) is monotonically decreasing and bounded below, hence convergent. In particular,
lim m M(F (θkm)) = lim m M(θkm+1) = lim m M(θkm) .
By continuity of M and F , we obtain
M(F (θ̄)) = M(lim m F (θkm)) = lim m M(F (θkm)) = lim m M(θkm) = M(θ̄)
and hence F (θ̄) = θ̄. Since F is reasonable, θ̄ must be a critical point. Now the only critical point of M orN is the strict maximum θ̄ = 0, so any accumulation point of θk must be θ̄. The sequence θk is assumed to be bounded, so it must have at least one accumulation point by Bolzano-Weierstrass. A sequence with exactly one accumulation point is convergent, hence θk → θ̄. This is in contradiction with the algorithm being reasonable.

Review summaries:
1. For Theorem 1, as the reviewer understands it, for an optimization problem whose only critical point is a strict maxima, it only has four outcomes, which are listed in the theorem. The result seems quite intuitive and provides very limited understanding for the problem. Please list other possible outcomes for the general problem and state in such way that the paper finds some impossible outcomes which can be excluded for consideration.