On the Impossibility of Global Convergence in Multi-Loss Optimization
Authors: Alistair Letcher
Venue: ICLR 2021 Poster (2021)
Keywords: impossibility
global
convergence
optimization
multi-loss
multi-player
multi-agent
gradient
descent

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.

Published as a conference paper at ICLR 2021
ON THE IMPOSSIBILITY OF GLOBAL CONVERGENCE IN MULTI-LOSS OPTIMIZATION
Alistair Letcher
aletcher.gine setcher.github.io
ABSTRACT
Under mild regularity conditions, gradient-based methods converge globally to 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 hope 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 two-player game with zero-sum interactions whose losses are both coercive and analytic, but whose only simultancous critical point is a strict maximum. Any 'reasonable' algorithm, defined to avoid strict maxima, will therefore fail to con- verge. This is fundamentally different from single losses, where coercivity implies existence of a global minimum. Moreover, gradient- craddientbbased methods almost surely have bounded but non-convergent iterates in constructed zero-sum game for suitably small learning rates. It nonetheless remains an open question whether such behavior can arise in high-dimensional games interest to ML practitioners, such GANs or multi-agent RL.
prove that wide range of existing
INTRODUCTION
Problem Setting. As multi-agent architectures proliferate in machine learning. it is becoming in- creasingly important to understand the dynamics of gradient- based methods when optimizing multi- ple interacting goals, otherwise known as differentiable games. This framework encompasses GANs (Goodfellow et al., 2014), intrinsic curiosity (Pathak et al., 2017), imaginative agents (Racanière 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 simultancous gradient descent: adaptations of single-loss algorithms such as Extragradient (EG) (Azizian et al., 2019) and Optimistic Mirror Descent (OMD) (Daskalakis et al., 2018), Altemat- ing 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 solv- ing bilinear approximation of the loss functions (Schaefer & Anandkumar, 2019), Symplectic Gradient Adjustment (SGA) based on novel decomposition of game mechanics (Balduzzi et al., 2018; Letcher et al., 2019a), and opponent- shaping-saanggggg algorithms including Learning with Opponent- Learning 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-conver 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 suitable measure of progress (which is given by the function value in the single agent setting), since norms gradients can not be expected to decay monotonously for competitive dynamics in non-convex-concaee games."

---

Published as a conference paper at ICLR 2021
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). Glohal 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 two- sided Polyak-Lojasse Lojasiewii condition (Yang et al., 2020), zero-sum linear quadratic games (Zhang 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 dynamies are bounded under 'negative sentiment" assumption in smooth markets, which do include GANs - but this does not imply convergence, as we will show.
On the other failure of global convergence has been shown for the Multiplicative Weights Up- date method by Palaiopanos al. (2017), for policy-gradien algorithms by Mazumdar et al. (2020), and for simultaneous and alternating gradient descent (simGD and AGD) by Vlatakis-Gkaragkou et al. (2019); Bailey et al. (2019), with interesting connections to Poincaré 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 al., 2019, Example 2).
Finally, Hsieh et al. (2020) uploaded a preprint just after the completion of this work with a similar focus ours. They prove that generalized Robbins-Monro schemes may converge with arbitrarily high probability to spurious attractors, This includes simGD, AGD, stochastic EG, optimistic gradi- ent and Stefer-Wolffwite However, Hsieh et al. (2020) focus on the possible occurrence of undesir- able 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 distinc- tions are further highlighted by Hsieh et al. (2020) the further related work section. Taken together, our works give 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 cero-sum game in which all algorithms in A (as defined in Appendix A) are proven to cycle (Theorem 3).
may be that cycles do not arise in high digh-siimesi 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.
BACKGROUND
2.1
SINGLE LOSSES: GLOBAL CONVERGENCE OF GRADIENT DESCENT
Given continuously differentiable function f : Rd + R, let
0 = 0₁ a a. ((x)
be the iterates of gradient descent with learning rate o, initialised at 0g. Under standard regularity conditions, gradient descent converges globally critical points:
Proposition 1. Assume E C² has compact sublevel sets and is either analytic or has isolated critical points. For any On E Rd, define Un = {f(()) < f(0)) and let L < so be a Lipschitz constant for Vf in Ug. Then for any O < a <, 2/T. we have limg 0g 0 for some critical point 0.
2

---

Published as a conference paper at ICLR 2021
The requirements for convergence relatively mild:
1. f has compact sublevel sets iff f is coercive, 100) f(0) = oc, which mostly holds in machine learning since a loss function.
2. f has isolated critical points if it is Morse function (nondegenerate Hessian at critical points), which holds for almost all C² functions. More precisely, Morse functions form an open, dense subset of all functions f E (TR,, IR.) in the Whitney C2 Cootopology.
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 cannor 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.
2.2 DIFFERENTIABLE GAMES
Following Balduzzi al. (2018), we frame the problem of multi-loss optimization as 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 set of agents with parameters 0 (0' ..... 0a) E IR and twice continuously differentiable losses R2d + I. where 0' E Rdd for each and E, di =
Losses are not assumed be convex/concave in any of the parameters. practice, losses need only be differentiable almost-every think of neural nets with rectified linear units.
If 1, the 'game' is simply minimise given loss function. We write V,L* Voi L and V I = V Vei & for any i, j. k and define the simultaneous gradient of the game
E
Vn,L')² R
as the concatenation of each player's gradient. If each agent independently minimises their loss using GD with learning rate a, the parameter update for all agents given by 0 < aE(O). We call this simultaneous gradient descent (simGD), or GD for short. We call 0 a critical point E(0) = Now introduce the 'Hessian" (or Jacobian) of the game as the block matrix
VnL
V
H =
E RRdxd
VnIL"
vnnL"
Importantly note that H is not symmetric in general unless n in which case we recover the usual Hessian H L However H can be decomposed into symmetric and anti-symment components as H = A (Balduzzi et al., 2018). A second useful decomposition has appeared recently in (Letcher et al., 2019b) and (Schaefer & Anandkumar, 2019): H Ha + H. where Ha and H, are the matrices of diagonal and off-diagonal blocks; formally, Ha = O L. One solution concept for differentiable games, analogous to the single-loss case, is defined as follows.
Definition 2. A critical point 0 is (strict, local) minimum if H (()) 0.
These were named (strict) stable fixed points by Balduzzi et al. (2018), but the term is usually reserved in dynamical systems 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: V L','(()) >- 0. The converse does not hold.
Algorithm class. This paper is concerned with any algorithm whose iterates are obtained by ini- tialising 0g and applying function F to the previous iterates, namely 0c+1 F(....... holds for all gradient-basee methods (deterministic or stochastic); most of them are only functions
00). .efe...,,))), This
For non-symmetric matrices, positive definiteness is defined as H > 0 iff n." Hu > 0 for all non-zero Rdd This is equivalent the symmetric part S of H heing positive definite.
3

---

Published as a conference paper at ICLR 2021
of the current iterate Be. so that 07 F All probabilistic statements in this paper assume that 8g is initialised following any bounded and continuous measure V on R 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-playe games, the goal of such algorithms is for 0g to converge local (perhaps global) minimum as - oc. The goal is less clear for differentiable games, but is generally to reach a minimum Nash equilibrium. In the case of GANs the goal might be reach parameters that produce realistic images, which is more challenging to define formally.
Throughout the text 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.
the term (limit) cycle mean bounded but non-convergent iterates.
Game class. Expecting global guarantees in all differentiable games is excessive, since every continuous dynamical system arises as simultancous GD on the loss functions of 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. (smooth) market is a differentiable game where interactions between players are pairwise zero-sum, namely,
L''0 + g0 ())
jf1
with 9,y (0' 00) + (0: for all i,
This generalises zero-sum games while remaining amenable to optimization and aggregation, mean- ing 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 large num- ber of applications including GANs and related architectures, intrinsic curiosity modules, adversar- ial 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.
2.3 REASONABLE ALGORITHIMS
We wish to prove that global convergence is odds with weak, 'reasonable' desiderata. The first requirement is that fixed points of an optimization algorithm F are critical points. Formally,
F(0) =
{(0) = 0.
(RI)
If not, some agent i could strictly improve its losses by following the gradient - LLL + 0. There is no reason for a gradient-based algorithm to stop improving 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-definie Hessian < O. Converging to such a point the opposite goal of any meaningful algorithm since moving anywhere away from 0 decreases the loss. There are multiple ways of generalising this concept for multiple losses, but Proposition below justifies that H X 0 is the weakest one.
Proposition 2. Write X(A) = Re(Spec(AA A)) for real parts of the eigenvalues of matrix A. We have the following implications, and none of them are equivalences.
max X(H) <0- min X(H) <0
H <
min X(S) <
max X(Ha) < 0 = min X(H)) <
Definition& 4. A critical point 0 is (strict, local) maximum H()) 0.
4

---

Published as a conference paper at ICLR 2021
Imposing that algorithms avoid strict maxima is therefore the weakest possible requirement of its kind. Note that the bottom-left implication Proposition is equivalent to V < 0 for all i, also strict maxima of each player's individual loss function. Players can all decrease their losses by moving anywhere away from them. is exceedingly reasonable to ask that optimization algorithms avoid these points almost surely. Formally, require that for any strict maximum 0 and bounded region U there are hyperparameters such that
strict maxima
(100 E U lim 02 = 0] = 0.
(R2)
I denotes Lebesgue measure. Hyperparameters may depend on the given game and the region U, as typical for learning rates in bastie methods.
Definition 5 (Reason). An algorithm is reasonable if it satisfies RI and R2.
Reason is not equivalent to rationality or self-interest. Reason is much weaker, imposing only that agents well-behaved regarding strict maxima even if their individual behavior is not self- interested. For instance, SGA agents do not behave out self-interest (Balduzzi et al., 2018).
3 GLOBAL CONVERGENCE IN DIFFERENTIABLE GAMES
3.1 REASONABLE ALGORITHMS FAIL. TO CONVERGE GLOBALLY
Our main contribution 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 di- vergent direction with minimal loss (imagine minimising L e*). should however be asked that algorithms have bounded iterates in coercive games, defined by coercive losses
lim (0())= = 0
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 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 (Globality). An algorithm global if. in a coercive, analytic and nondegenerate game, for any fixed fo. iterates 0g 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 coercive, nondegenerate, analytic two-player market M whose only critical point is strict maximum. In particular, algorithms only have four possible outcomes in M:
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 non-critical point. [Not reasonable]
4. Iterates are bounded but do not converge (cycle). [Not global]
Proof. Consider the analytic market M given by
y²
4
L' u) = 1./6///66 12/2+ xy
+
4
1 + x
1 y²
1
y
4
(x( 1 / 66 / xy
+ x
1 y²
We prove in Appendix D that M is coercive, nondegenerate, and has a unique critical point at the origin, which is strict maximum.
5

---

Published as a conference paper at ICLR 2021
Constructing algorithm with global guarantees is therefore doomed be unreasonable in that it will converge to strict maxima or non-critical points in M.
None of the outcomes of M are satisfactory. The first three are highly objectionable, already dis- cussed. 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 itera- tion would lead to a non-critical point, much like the third outcome. Even if we let agents update parameters continuously as they play game or solve 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 arise in applications 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.
Why can this approach not be used to disprove global convergence for single losses? One reason is that we cannot construct coercive loss with no critical points other than strict maxima: coercive losses, unlike games, always have global minimum.
Remark.
3.2 WHAT IF THERE ARE STRICT MINIMA?
One might wonder if it is purely the absence of strict minima that causes non-convergence, since strict minima locally attracting under gradient dynamics. Can 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 parame- ters are initialised following any bounded continuous measure v on Rd, we can always modify M by deforming a correspondingly small region around the origin, turning it into a minimum while leaving the dynamics unchanged outside of this region.
For fixed initial distribution, any reasonable algorithm can therefore enter limit cycle or diverge to infinite losses with arbitrarily high probability.
Theorem 2. Given a reasonable algorithm with bounded continuous distribution on Og and a real number O, there exists coercive, nondegenerate, almost-everywhere analytic two-player mar- ket M, with a strict minimum and no other critical points, such that 0g either cycles or diverges to infinite losses for both players with probability least -
Proof. Let 0 < < 0.1 and define
(2² +2² 002222
if | 2
fo( (1² 3x² + 12² 02)/(202) otherwise,
where 0 = (I. v) and ||0|| = /x² + 2² is the standard 1.2-norm Note that fa is continuous since
lim lim fa 3) 10|| ||0|
fo().
Now consider the two-player market M, given by
1 1/ y
x
L' v) 2//6 x² fo ry
-
4
1+
x²
y²
y¹
x1
(xx - fa(,
-4 1+ 1+
We prove in Appendix E that M2 is a coercive, nondegenerate, almost-everywhere analytic game whose only critical point is a striet minimum at the origin. We then prove that 0g cycles or diverges with probability at least and plot iterates for each algorithm in A.
3.3 HOW DO EXISTING ALGORITHMS BEHAVE?
Any algorithm will either fail to be reasonable or global in M. Nonetheless, would interesting to determine the specific failure that each algorithm in A exhibits. Each of them is defined in

---

Published as a conference paper at ICLR 2021
90
CO CCD
LOLA 525
Figure Algorithms in fail to converge M with a = 7 0.01. Single run with standard normal initialisation, 3000 iterations. The behavior of SGA is slightly different, explained by the presence of non-continuous parameter À jumping between #1 according to an alignment criterion.
Appendix A, writing a for the learning rate and y for the Consensus Optimization hyperparameter. We expect each algorithm be reasonable and moreover have bounded iterates in M for suitably small hyperparameters. this holds, they must cycle by Theorem 1.
This witnessed experimentally across 1000 runs for a - 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 infinite loss if is too large or converging to the strict maximum for CO if y 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 in M, we construct a zero-sum game M with similar properties as M and prove below that algorithms A almost surely fail converge there for small r. This is stronger than proving the analogous result for M, since A 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 I,- > oc implies T,2 - -00. is therefore unclear whether global guarantees should be expected. Note however that N will be weakly-coercive in the sense that
lim L' 0-1) ||00||00000
for and fixed 0-i
Theorem 3. There is weakly-coercive, nondegenerate, analytic two-player zero-sum game N whose only critical point is a strict maximum. Algorithms in almost surely have bounded non- convergent iterates in N for a, y sufficiently small.
Proof. Consider the analytic zero-sum game A given by
I xy 22
-I2.
We prove in Appendix that N is weakly-coercive, nondegenerate, and has a unique critical point the origin which is striet maximum. We prove that algorithms in A have the origin unique fixed points, with negative-definite Jacobian for a, 7 small, hence failing to converge almost surely. We moreover prove that algorithms have bounded non-convergent iterates in / for a, 7 sufficiently small. Iterates are plotted for single run of each algorithm in Figure 3 with
= 0.01.
As M, the behavior each algorithm may differ for larger hyperparameters. All algorithms may have unbounded iterates converge to the strict maximum for large a, while EG and OMD may even converge to a non non-critical point (see proof). All such outcomes are unsatisfactory. though unbounded iteration will not result in positive infinite losses for both players since I,1 -

---

Published as a conference paper at ICLR 2021
3.4 COROLLARY: THERE ARE NO SUITABLE MEASURES PROGRESS
A crucial step in proving global convergence of GD on single losses is showing that the set of accumulation points is subset of critical points, using the function value '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 0x+1 = F(0g) ) is a continuous map M TRd > R. bounded below, such that M (F(()) M(0) and M(F(0)) M(() iff F 0.
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 progress for single- loss GD under the usual regularity conditions, while the gradient norm ||E|| is measure of progress for GD in strictly convex differentiable games:
(E a²)l = ||El| ac at" o(a) S |Ell
small a. Unfortunately, games like M prevent the existence of such measures general.
Corollary 1. There are no measures of progress for reasonable algorithms which produce bounded iterates in M or N.
Assuming the algorithm to be reasonable is necessary: any map is a measure of progress for the unreasonable algorithm F(0) 0. Assuming the algorithm have bounded iterates in M or / is necessary: (0) = exp (-0 0 1) is a measure of progress for the reasonable but always-divergent algorithm F(0)= + where is the constant vector of ones.
CONCLUSION
We have proven that global convergence 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 interesting and important avenue for further research, with real implications what to expect when agents learn while interacting with others. Cycles may for instance he unacceptable in self-driving cars, where oscillatory predictions may have life-threatening implications.
8

---

Published as a conference paper at ICLR 2021
REFERENCES
Jacob Abernethy, Kevin A. Lai, and Andre Wibisono. Last-iterate convergence rates for min-max optimization. ArXiv e-prints, 2019.
PA Absil, Robert Mahony, and Ben Andrews. Convergence of the iterates of descent methods for analytic cost functions. SIAM Journal on Optimization, 16, 01 2005.
Waiss Azizian, loannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. A tight and unified analysis of extragradient for whole spectrum of differentiable games. ArXiv e-prints, 2019,
James P. Bailey, Gauthier Gidel, and Georgios Piliouras. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent. ArXiv e-prints, 2019.
D. Balduzzi, S. Racaniere, J. Martens, J. Foerster, K. Tuyls, and T. Graepel. The Mechanics of n-Player Differentiable Games. JCML, 2018.
David Balduzzi, Wojciech M. Czarnecki, Tom Anthony, Ian Gemp, Edward Hughes, Joel Leibo, Georgios Piliouras, and Thore Graepel. Smooth markets: basic mechanism for organizing gradient-based learners. In International Conference on Learning Representations, 2020.
Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in Real Algebraic Geometry. Springer-Veriie Berlin Heidelberg, 2006.
L. Busoniu, R. Babuska, and B. De Schutter. A comprehensive survey of multiagent reinforce- ment learning. IEEE Transactions on Systems, Man, and Cybernetics, Part (Applications and Reviews), 38(2):156-177 March 2008.
C. Daskalakis, A. Iyas, Syrgkanis, and H. Zeng. Training GANs with Optimism. In International Conference on Learning Representations, 2018.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. NIPS, 2018
W. Decker, G.-M. Greuel, G. Pfister, and H. Schönemann. Singular 4-1-2 - A computer algebra system for polynomial computations. http:/ www. singular........... uni kki--1... de, 2019.
Farzan Farnia and Asuman Ozdaglar. Do GANs always have Nash equilibria? ICML, 2020.
J. N. Foerster, R. Y. Chen, M. Al-Shedivat, S. Whiteson, P. Abbeel, and I. Mordatch. Learning with Opponent-Learning Awareness. AAMAS, 2018.
I. Goodfellow, J. Pouget-Abbdie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative Adversarial Networks. NIPS, 2014.
Ya-Ping Hsich, Panayotis Mertikopoulos, and Volkan Cevher. The limits min-max optimization algorithms: convergence spurious non-critical sets. ArXiv e-prints, 2020.
M. Jaderberg, M. Czarnecki S. Osindero, O. Vinyals, Graves, Silver, and K. Kavukcuoglu. Decoupled Neural Interfaces using Synthetic Gradients. ICML, 2017.
K. Lange. Optimization. Springer Texts in Statisties. Springer New York, 2013.
D. Lee, M. Simchowitz, M. I. Jordan, and B. Recht. Gradient Descent Only Converges to Mini- mizers. In 29th Annual Conference Learning Theory, volume 49 of Proceedingy of Machine Learning Research, pp. 1246-1257, 2016.
Alistair Letcher, David Balduzzi, Sébastien Racanière, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. Differentiable game mechanics. Journal of Machine Learning Research, 2019a.
Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, and Shimon Whiteson. Stable opponent shaping in differentiable games. In International Conference on Learning Representa- fions, 2019b.

---

Published as a conference paper at ICLR 2021
David Luenberger and Yinyu Ye. Linear and Nonlinear Programming, volume 67. 01 1984.
Oren Mangoubi and Nisheeth K. Vishnoi. A second-order equilibrium in noncomvex-nonccocavve min-max optimization: Existence and algorithm. ArXiv e-prints, 2020.
Eric Mazumdar, Lillian J. Ratliff, Michael I. Jordan, and S. Shankar Sastry. Policy-gradient al- gorithms have no guarantees of convergence in linear quadratic games. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '20, pp- 560-868. International Foundation for Autonomous Agents and Multiagent Systems, 2020.
Eric V. Mazumdar, Michael I. Jordan, and S. Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. ArXiv e-prints, 2019.
L.. Mescheder, S. Nowozin, and A. Geiger. The Numerics of GANs. NIPS, 2017.
G.S. Nelson. Usser-Friendyy Introduction Lebesgue Measure and Integration. Student Mathe- matical Library. American Mathematical Society, 2015.
Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. NIPS, 2017.
I. Panageas and G. Piliouras. Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions. In ITCS 20/7, volume 67 of Leibniz International Proceedings in Informatics, pp. 2:1-2:12, 2017.
Christos Papadimitriou and Georgios Piliouras. Game dynamics as the meaning of game. SIGecom Exch., 16(2):53-63. May 2019.
D. Pathak, P. Agrawal, A. A. Efros, and Darrell. Curiosity-driven Exploration by Self-supervised Prediction. ICML, 2017.
S. Racanière, T. Weber, D. P. Reichert, L. Buesing, A. Guez, D. Jimenez Rezende, A. Puigdomènech Badia, O. Vinyals, N. Heess, Y. Li, R. Pascanu, P. Battaglia, D. Hassabis, D. Silver, and D. Wier- stra. Imagination-Auugmente Agents for Deep Reinforcement Learning. NIPS, 2017.
Florian Schaefer and Anima Anandkumar. Competitive gradient descent. NIPS, 2019.
M. Spivak. Calculus On Manifolds: Modern Approach Classical Theorems Of Advanced Calculus. Avalon Publishing, 1971.
A. S. Vezhnevets, S. Osindero, T. Schaul, N. Heess, M. Jaderberg, D. Silver, and K. Kavukcuoglu. FeUdal Networks for Hierarchical Reinforcement Learning. ICMI,, 2017.
Emmanouil-Vasileen Vlatakis Kaaraks-G. Lampros Flokas, and Georgios Piliouras. Poincaré recurrence, eycles and spurious equilibria in gradient-descent-aseer for non-convex non-concave zero-sum games. NIPS, 2019.
G. Wayne and L. F. Abbott. Hierarchical control using networks trained with higher-level forward models. Neural Computation, 26(10)2113-2199, 2014.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance-reduced optimization for a class of nonconvex-noncomeane minimax problems. ArXiv e-prints, 2020.
Kaiging Zhang. Zhuoran Yang, and Tamer Basar. Policy optimization provably converges nash cquilibria in zero-sum linear quadratic games. NIPS, 2019.
10

---

Published as a conference paper at ICLR 2021
APPENDIX
A ALGORITHMS AND EXPERIMENT HYPERPARAMETERS
Each algorithm in A cited in the 'Related Work' section be defined F(0) 0 aG((0) for some continuous G R² + RR We have already seen that simultancous GD is given by GGD = &. The only examples in this paper are two-player games, for which AGD given by
E1 (2 -0:01-061,000
GAGD
The other algorithms are given by
GBG Ço (id ox)
GOMD 2g(0%) E(Ok-1)
GSga (I )E
Geo (I+ 7
GGGD (I + aHHo)
GLA = - -HHH..
GLOLA = (1 - -aH.) a diag(Hg
Gsos = (1 - aHo)E - pa diagdaa VH) VL).
For OMD, the previous iterate can be uniquely recovered as 0:-1 (id (0x) using the proximal point algorithm | S L and a L/L, giving
GOMD 25 - 5 o (id aE)
In all experiments we initialise On following a standard normal distribution and use learning rate 0.01, with y 0.01 for CO. Learning rates a, 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 on should be sufficiently small. The À parameter for SGA is obtained by the alignment criterion introduced in the original paper,
À = sign ((s, H" H) (A HT
Similarly, the parameter for SOS is given by two-part part criterion which need not be described here.
Accompanying code for all experiments can be found impossibility gl obal cobal-cooveeeencce
com/ al aletcher/
B PROOF OF PROPOSITION 1
We first prove a lemma and state a standard optimization result.
Lemma 0. Let G E C² (U, R for an open set U. G is L-Lipschitz then supseu [|V)(()) S L.
The proof is an adaptation of (Panageas Piliouras, 2017, Lemma 7) for non-convex sets.
Proof. Fix any 0 U and 0. Since U is open, the ball (0) of radius r centered at 0 is contained in U for some > By Taylor expansion, for any unit vector 0',
|[G(0 + r0') G(#) 2 [|VG())) o(r) 2 \
for sufficiently small. Since G L-Lipschitz, we obtain
|V < ||G(0 + r0') G(Ø) re E rr([+
Since was arbitrary, [G < L for any unit 6'. By definition of the norm, obtain ||VG(0)] = sup
|VG S
||||||=1
for all 0 E U and hence supeet VG L.
Proposition ((Lange, 2013, Prop. 12.4.4) and (Absil et al., 2005, Th. 4.1)). Assume f has L.- Lipschitz gradient and is either analytic or has isolated critical points. Then for any O < < 2/T, and Og E R2d we have
lim 0m
lim =
for some critical point 0. If moreover has compact sublevel sets then the latter holds, limg Os 0.
11

---

Published as a conference paper at ICLR 2021
We now prove Proposition 1, which avoids requiring Lipschitz continuity by proving that iterates are contained in the sublevel set given by 8g for appropriate learning rate a.
Proposition Assume E C has compact sublevel sets and either analytic or has isolated critical points. For any 0g R., define Uo {f(()) < f(0o)) and let L < co be Lipschitz constant for f in Ug. Then for any 0 < a < 2 we have lim, 8g = 0 for some critical point 0.
Proof. Note that V C². f has I.-1 I.-L.ipchitz gradient inside any compact set U for some finite L, and supoeu [()i] & by Lemma O. Now define Ua = {0 Va t [0, 1]. E Uo} and the continuous function L(xx) = supseu. [() ||. Notice that Uo C Un for all a. We prove that (a(a)= < 2 implies U, = Un and in particular, L(a) L(0). By Taylor expansion.
fa
f(0 - 1t0-taVf) = f()) - a -[V[[[
2
for some t' E [0, C [0, 1]. Since 0 fooV Ua, it follows that
f(O - ta - f()) - (0)] (1- (1-
for all (L) < 2. In particular, 0 9 f E Uo and hence U. = Un. We conclude that aL(a) < 2 We now claim the converse, namely that aT(0) < 2 implies aT(a) < 2. For contradiction, assume otherwise that there exists a' ((T.(0) 2 with a (a)) 2 Since al(a) is continuous and 0Z.(0) = < 2, there exists ā a' such that (L( < 2 and āL(a) 2. This is in contradiction with continuity:
implies L(a) L(0). implying in turn aL(O)
2 = aL(ā)
lim al(a) = lim aL(O) = aT(()) a-a
a-a
Finally we conclude that Ua = Uo for all aL()) < 2, and in particular, for all aL < 2. Finally, Og E Un implies Ok+1 E Ua Un and hence 02 E Up by induction. The result now follows by applying the previous proposition to flu.-
C PROOF OF PROPOSITION 2
Proposition 2. Write X(A) Re(Spec(A)) ()) for real parts of the eigenvalues of matrix A. We have the following implications, and none of them are equivalences.
max A(I) <0 - min A(H) <
H 0
min X(S) <
max X(Ha) <0- = min X(Ha) <0
The top row is dynamics-based. governed by the collective Hessian, while the bottom row game- theoretic whereby Ha + L' decomposes into agentwise Hessians. The left and right triangles
collide respectively to strict maxima and saddles for single losses, since H = S = Ha L
Proof. First note that H < 0 = S replaced by max X(S) < 0.
max A(S) 0, so the leftmost term can be
We begin with the leftmost implications. If max maS) < 0 then S < 0 by symmetry of S, implying both < 0 since x² Hu = -² Su for all u e Rd. and negative definite diagonal blocks V²L - 0; finally Ha 0. In particular this implies max X(H) < O and max ((Ha) x O since real parts of eigenvalues of negative definite matrix are negative.
The rightmost implications follow above by contraposition: if min X(S) then S / 0, which implies H 2 0 and Ha Z 0 and hence min X(H) 2 O, min A(Ha) 2 0.
The top and bottom implications are trivial.
12

---

Published as a conference paper at ICLR 2021
The diagonal implications hold by trace argument:
Σ - - - Tr(Ha) = - Ai(H)),
hence max X(H) < 0 implies the LHS is negative and thus (HH,) < 0. It follows that (Ha)) < for some and finally min (Ha) < The other diagonal holds identically.
We now prove that no implication is an equivalence. For the leftmost implications.
H = -1 2
-1
has max A(Ha) -1 < O while max X(5) = 3 > 0, and
4
H -4 -4
has max XH) -1 < 0 while max X(S) 2 > 0. This also proves the diagonal implications:
the first matrix has min X(Ha) = -1 < 0 but max X(H) = 3 0, and the second matrix has min X(H)= 1 0 but max X(Ha) 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. -1)
has min X(H) min X(Ha) < 0 but max X(H) max A(Ha) -1> 0.
D PROOF OF THEOREM
The variable changes
(x'.0') 22) (d'.v) (-y.
(d'.)) (-2, -9)
(t)
will be useful, taking the positive quadrant 2 0 to the other three.
Theorem 1. There is coercive, nondegenerate, analytic two-player market M whose only critical point is strict maximum. In particular, algorithms only have four possible outcomes M:
1. Iterates unbounded, and all players diverge to infinite loss. [Not global]
2. Iterates bounded and converge the strict maximum. [Not reasonable)
3. Iterates are bounded and converge to non-critical point. [Not reasonable]
4. Iterates are bounded but do not converge (cycle). [Not global]
For intuition purposes, MM was constructed by noticing that there 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 -x? and - terms yield strict local maximum at the origin, while the +-yy terms provide opposite incentives around the origin, preventing any other simultaneous critical point to arise.
Proof. Write 0 = yI and consider the analytic market M given by
L' = 2 2/ + xy +
y²
+ x2
1 + y2
1
y2
x.
1 ///6 y2 /2 xy
4
1 x
1 1 y2
13

---

Published as a conference paper at ICLR 2021
with simultaneous gradient
x + y x
I4y
y x 2(1+2
14-22
We prove bby hand' that the origin 0 is the only critical point (solution to 0). See further down for an easier approach based on Sturm's 's theorem, computer-assisted though equally rigorous.
We assume x, y 2 0 since any other solution can be obtained by quadrant variable change (i).
Now assume for contradiction that = 0 with 7 O.
We first show that y > Indeed,
z²y y
y
0 = y² y 2(1 1
v. y =v( 1) 1 1 x²
implies
since 2 0.
We now show that < 1.5. First assume for contradiction that æ 2 y, then
xy
3
y 2
2(1 + 22
1
1 y²
I
13/8 x² 22/2 h(x).
Now
35
11(x))
8
2
has unique positive root
6 + 29
20
35
and h(x)) - 0o as + oc, hence l attains its minimum at up and plugging zo yields a contradiction
h(wo)) > 0.
We conclude that x < y. but combining this with æ 2 0 yields
ε 2y + y /²/8 2²² v7 /8 y² - 2) Ty /8 y2
for all y 2 1.5, since the rightmost polynomial is positive y 1.5 and has positive derivative
7y 2y = y(70"/222222 - 2 7(1.5) -
We must therefore have < 1.5 as required.
It remains only to show that & 0 for all y < 1.5. First notice that fa(y) (x1, v) is concave in for any fixed x 2 0 since
3.
2
f2(2) =
2r
y
(1 + x2)2
(1+ y2)
and so
6
1 1 2²2 4y²
6y2xx
31/
(1)
2r
2x
0
(1 + 20
(1 + y2)
22+
(1+ 22
for y > 1. follows that fo attains its infimum on the boundary y E 1.5), so suffices to check that (2, 1) and (xx 1.5) 0 for all 0. First notice that
(
I
2(1 + 22
satisfics
1 2 4x
1 3x
g'(x) =
2(1 + 22)2
2(1 + 22/2
14

---

Published as a conference paper at ICLR 2021
which has unique positive root Zo 1/v3.. This critical point of must be maximum since g(x) for a and g(x) + as x + oo. follows that
1
g(x) S g( 2v3(1 + 1/3)2 =3v3/32.
We now obtain
(I, 1) 2 x³ x² - x + 3/3/32 = p(x)
and
(1 1.5) 2 x. 4x - x + 1.5 - 3V3332 = q()).
Notice that
p'(x) 5x - -3x 32
has unique positive root
3 3 v 89
20
20
and p(x) + 0o as x + oc, hence attains its minimum at zu and plugging zo yields
(1 1) 2 p(ro) > 0.
Similarly for q we have
d(xx) = 5x* - 12xx 12xx/113 113
has unique positive root
6 V881
30
65
and plugging zo yields
E1 (x, 1.5) 2 g(x0) > 0.
We conclude that
(z, 2 min(fi 1), (r,, 1.5)) > 0 and the contradiction complete, hence y = 0. Finally & =0 = r, so is the unique critical point required. Now the Hessian at 0 is
( (=1 1))
which is negative definite since S(0) -I 0 is a nondegenerate strict maximum and M is nondegenerate. It remains only to prove coercivity of M. namely coercivity of L and L Coercivity of L follows by noticing that the dominant terms are x6 /6 and y /1 x²). Formally, first note that _² I+yz
S x4, hence
L' 2 2222/-==//4 /22-22 -'22//6--/a- 1
y
1 1+ x²
Now zy 2 -lay| 2 - 222=2 + ///8) by Young's inequality, hence
L' 2 x /6 x== /4 5x /2 - 12/8 8
1 11
For any sequence ||||| + oo, either |x|| + xc or |2|| is bounded above by some E and lyl + co. In the latter case, we have
lim +
L
522 1 + 4(1 R2)) 00
lim 10
since the leading term d is of even degree and has positive coefficient, for [ar] + oo, we pursue the previous inequality to obtain
done. Otherwise,
y²
2y²
-1)
I.1 > 2//6 x+/4 -
5/
-1)
8
1 x??
15

---

Published as a conference paper at ICLR 2021
Now notice that y² 2 x² implies
x² x2=-1)
1 2 2 /
x2/4 5x² /2+
2 2//6 x//4 5x2/2 x2/88.
8 11 x²
On the other hand, x² 2 1¹² also implies
L' 2 x² x² /4 5222 x² /8
by discarding the first (positive) term in the brackets. Both cases lead to the same inequality and hence, for any sequence with |x|| + x.,
lim T,a lim ///6- [0||
x-/2//4 5x /2 x²
x1-000
since the leading term de has even degree and positive coefficient. Hence L is coercive, and the same argument holds for L by swapping and y. As required have constructed a coercive, nondegenerate, analytic two-player market M 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 = 0 is the only critical point, we may take advantage of computer algebra systems 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 reotsur library used below based on the book by Basu et al. (2006). First convert the equations into polynomials:
2(1 ((1+2))(1+ - -1 -
2(1 +
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 of the initial system. We then use the Sturm sequence of P to find its exact number of real roots. This implemented with the Singular code below, whose output is
LIB "solve. 1ib"; LIB "rootsur. lib"; ring r x0,x), dp;
poly pl (++xx "2x (x (x 4x** 22 (1+x"2) 22
poly p2 (1+y "2 (1) (-y-)) -x 4xxx (1 (1+x22)22 (1+y"2)
ideal i p1,p2;
poly f det [mp_res_mat (1));
ring s 0, (x,y) , dp; poly imap (r, f)
hrrcots (f);
We know that 0 0 is a real solution, must be the unique critical point.]
E PROOF OF THEOREM 2
Theorem 2. Given reasonable algorithm with bounded continuous distribution dg and real number e > O, there exists a coercive, nondegenerate, dimost-everywher analytic two-player mar- ket Mr with strict minimum and other critical points, such that 02 either cycles or diverges to infinite losses for both players with probability at least -
Proof. We modify the construction from Theorem by deforming a small region around the maxi- mum to replace it with a minimum. First let ( < a < 0.1 and define
(x2 + -
if | 2
(0)
(12 3x2) + 2²² 02) 02)/(202) otherwise,
where 0 = (x, 3) and ||0|| = / 22 + 2 is the standard L2- L2-norm. Note that fo is continuous since
lim (0) = 0 = lim fa (0).
|10| -
||||
16

---

Published as a conference paper at ICLR 2021
Now consider the two-player market Ma given by
y
x4
= x²+ fa + xz +
1
x²2
1 y²
v/ fo zy 1 y²
x²a
1 x2
The resulting losses are continuous but not differentiable; however, they are analytic (in particular smooth) almost everywhere, namely, for all 0 not on the circle of radius o. This sufficient for the purpsses of gradient- based optimization, noting that neural nets also fail to be everywhere- differentiable in the presence of rectified linear units.
We claim that Ma has single critical point at the origin 0 = O. First note that
5
x + y
Ity
EMM EMo
EM
x² I+27
2
for all ||0| 2 a, where M is the game from Theorem 1. It was proved there that the only real
solution to c 0 is the origin, which does satisfy ||0|| 2 a. Any critical point must therefore
satisfy ||0| < a. for which
+ + //2)/0²
v x
21+221
I-g"
EMM
- 2yl
21+
I+27
First note that 0= 0 is critical point; prove that there are others. The continuous parameter a prevents us from using a formal verification system, so we must work 'by hand'. Warning: the proof is long inelegant string of case-by-case inequalities.
Assume for contradiction that & = 0 with 0 + 0. First note that ||0|| < implies lz]. < a, and 0 or y 0 implies æ y 0 using
&2 = 0 respectively. We can therefore assume 0 < | |y| < a. We can moreover assume that x > 0, the opposite case following by the quadrant change of variables (x', s/) (-x.- y)
1. We begin with the case 0 S x < First notice that
x + y 2x(3x² + /²2 = x(1 - 6x² 60² + y(1 2ry/ S x(1 3/2) + u(1 100-y/11 y/o)
and the rightmost term attains its maximum value for = 22, hence
x マサ
2xx + + < - 5/450.
This implies
Ax
2
3
- x33
1 S 5
3
1 1-
2(1 + 22)2
y²
y2
y²
+
y2
using x² n²² < 1, which is contradiction to E 0.
2. We proceed with the case < 0/2 and |v| S 0/2. First, < 0 implies the contradiction
x
y
04
1 1
& < 22y-2y' 2/2 002
1+ Z < 4/2
< y
0,
2(1
22)2
25
2
2
25
2
so we can assume y > 0. In particular we have (1 2y( + x)/o²)
> 0. If S x, we also obtain
y3
1
& < "و + (y x) (1 2y +)//0²)
+ x y
1 2 <0,
+ x2
so we can assume x < y. There are again cases distinguish. If a/2 hoz with b 0.08,
x01 6a2 / v 2ry/ s01 3(1/2 ab)) x(1 (1/2 ab)) 4abx
17

---

Published as a conference paper at ICLR 2021
which implies the contradiction
y x
x3
0
1
1
Ei > 4oba
> or
4b
> dx
4b
> 0.
2(1 + x2)2
1+ y²
25
2
2
2
Finally assume 0/2 o0² Then we have
(y ---2 =1 2y( + y)/o²) < <bo
4x
<
(1-((120ob))) = 40 12 -ob) < 40
-
and obtain
y² o² (22/25 462
(1/2 - (1/2-ab)3
& <² + 4
1 x²
+ o²
We claim that the rightmost term is negative. Indeed, the quantity inside the brackets has derivative
a/2² + (1/2 1/2-abh) ob)²
(1 + o2 (3b(1 +
>
and its supremum across [0, 0.1] must be attained 0.1.
We obtain the contradiction
& 0² (0.01/2² 402 (1/2 - 6)3
<0
1.0.4/
for b = 0.08 and > 0, required.
Finally, consider the case x < 0 and |y| > 0/2. First, y < 0 implies the contradiction
ε < x y 2x(3x² + /²/ < (3x + x²) <
assume Y > O. Now assume y< r(1 /²). Then
x(1 - 6x /oa) + y(1 2xy/ -1/2 + y(1 3/0) > - x = x(1/2++++++++)
which yields the contradiction
S1 x ( - 2(1 + x2)2
y²
x.2
> x (1/2+02- >
1/4) -
1 y²
We can therefore assume y 2 o - x(1 + 02). We have
(y - =1 - 2y(y + =)/0²) < (y - x1 - (y + x)/o) s (y-x)(1 (1 - σz)) < corly x)
which attains its maximum in x y 2, hence
yd
ay²
oy²
2
& <
40
1 a2 +
1+
Finally we obtain the contradiction
1502 + 40 - oy²
(
<
1 + o²
for all σ < 0.1. All cases lead to contradictions, so we conclude that 0 is the only critical point, with positive definite Hessian
(()) (1 1) 00
hence Ø is strict minimum. Now notice that My has the same dominant terms as M from Theorem 1, so coercivity of Mo follows from the same argument. Since M, is identical to Ma outside the o-ball B, (( v) TR. |0|| < a). coercivity of MM implies coercivity of M2 for any a.
Fix any reasonable algorithm F, any bounded continuous measure on Idd with initial region U. and any c > We abuse notation somewhat and write F* (0,) for the kth iterate of F in M, with initial parameters 0g. We claim that there exists such that
Py 00 E U and lim (06) = 8) <c
18

---

Published as a conference paper at ICLR 2021
60
CO
CGD
LOLA
525
Figure Algorithms A fail to converge in Ma with a = a = = 0.01. Single run with standard normal initialisation, 3000 iterations.
Since 0 is the only critical point and Mg is coercive, this implies bounded but non-convergent iterates or divergent iterates with infinite losses with probability at least 1 - c, proving the theorem. To begin, p(B,) + 0 as o 0 implies that we can pick o' > 0 such that (o0 E B.,) c/2 by continuity of with respect to Lebesgue measure.
Now let Ü be the closure of U and define D Ü n [Il@|] 2 d'). Note that D is compact since Ü compact and closed subsets of compact set are compact. F is reasonable, D is bounded and 0 = 0 strict maximum in Mo. so there are hyperparameters such that the stable set
= 10u E D lim F (fn) 0}
&
has zero measure. We claim that
Z8 = 10o E D
inf F+ (0o) < 5}
KEN
has arbitrarily small measure as 8 + 0. Assume for contradiction that there exists >> 0 such that # ((s) 2 a for all 8 > 0. Then Z8 Zg. and μ ((z))= I p(D) < oo for < 8' implics
n
Z1 "
=
lim x+
| 2 a
MEN
by Nelson (2015, Exercise 1.19). On the other hand,
n
2 7o
BEN
yields the contradiction = (( 2 a. We conclude that Zg has arbitrarily small measure, hence there exists
such that
(00 E 2σ) < e/2
by continuity of v. Now let min(o', 5) and notice that inf [ 2 222 A
0u D Zs
infll= 2 20,
where the last implication holds since .M, and Mo are indistinguishable in {1|0] 2 a), so the algorithm must have identical iterates F (9%) Ft (0,) for all It follows by contraposition that limg Fk (fo) 0 implies inf [00)] < and 6 E Za 0o D. Finally we obtain
Py 0o and lim (0)) = =0) P. (0. EU n Zs or EU ()
&
Pr (fl
Zz) + P, (0, \ D)
< Py (fl E 2z) + P, (60 B.))
< </2 + =/2=
required. We plot iterates for single run of each algorithm in Figure with = 7 0.01. n
19

---

Published as a conference paper at ICLR 2021
F PROOF OF THEOREM 3
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 non- convergent iterates in N for o, y sufficiently small.
Proof. Consider the analytic zero-sum game N given by
L xy - /2 /2/2
1 -I²
with simultaneous gradient
y - + x3
-x y y²)
and Hessian
- 1 + 3x
1
-1
-1+3y²
We show that the only solution to & = 0 is the origin. First we can assume z, 2 0 since any other solution can be obtained by quadrant variable change (t). Now assume for contradiction that
y A 0, then
= = x y + 3² S - + 2/² = y0أ²² - 1)
implies 2 and hence
f = y 3 2 x + x² (x 1) [ 1)2 + 2 > 0
which is contradiction. It follows that y 0 and hence & 0 required. Now the origin has invertible, negative-definite Hessian
(0) = (- 11) 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 L (x. f) + oo for any fixed by domination of the 24 term; similarly for L y) by domination the y term.
Bounded iterates: strategy. We begin by showing that all algorithms have bounded iterates in / for a, y sufficiently small. For each algorithm F, our strategy is to show that there exists r >> 0 such that for any > 0 we have [0)] < ||0|| for all < ||0|] < and a, 7 sufficiently small. This will be enough to prove bounded iteration upon bounded initialisation. Denote by B, the ball of radius centered at the origin.
GD. We have
E sly + x²) y 1 x 4 3²)
x² x² + 1² y²2
(x² 1)2 + (1² - 1) + x 1)2
+ 12² -2>1
for all |10|2= x² + y² >3 3. For any s 0 obtain
||((0]]] ||0 -ogl]= |1012 2000 & a² ||E] < |10|| (2- a [|<](²) 11011
for all v3 < |||| < and sufficiently small, namely 0 < < 2/ supoe B, ||E]1
EG. For any 0 and v < |@|| < we have
|0 a{())]] > 4 - 2a0 <= >3
for a < 1 suPseB, _0 Now using 8T for all ||0|| > 3 by the argument for GD above,
[[]())] = |0]| - n {(0 - aE(()) + a² |IE(0 a
|l@l2 2a(0 aε(()))((() -a(()) O(a²)
< |10|12 - a (2 O(a)) < 1101
for a sufficiently small.
20

---

Published as a conference paper at ICLR 2021
AGD.
For any 0, notice by continuity of & that there exists 6 >> 0 such that
(E1, E2 (0: o 02)) > 0" - 1/2
for all a < 8 and 0 Bs since B, is bounded and 01 aε1 + 01 + 0. It follows that
||F(0)]] = |01|² 2007 (51, - a61, 02)) + +((²))
< |10|2 2ax00 - 1/2) O(a²)
< |10] 20((1 - 1/2) +/2)++((c)) 0
||0]] - a(1 0(a)) ||0|
for all v3 < ||||| and
sufficiently small.
OMD. For any s > 0, notice by continuity of & that there exists 5 > 0 such that
10" (E(0) E((id aς) (())= 1/2
for all 8 and 0 Bg, since B, is bounded and (id (()
0. It follows that
[[](0)]| |10| 2 2a02 & 2a0" (E(0) E((id aς) (()) O(a²)
< ||0| 3 2a + a + 0(a²)
= ||0| aa11 ((1)) < ||0|
for all v3 < |00|| < and < 6 sufficiently small.
CO, CGD, LA, LOLA, SOS. algorithm we have
Writing for y if F Fco and for a otherwise, for each
F(0) = at + avK
for continuous function K : Rd R. For instance, K =- - for CO (see Appendix A). We obtain
[F(O)]] = |10 oaf + cvk112
= ||0| 2000 & + 20vØ" K 20²vg² K K a² |KE u²2 |||
= |1012 a (20 & 2002 K 2av K || - |
Notice that every term in the brackets contains an except for the first. We have already shown that g"'g for all |101² > 3 for GD above, hence for any 0 we have
|[F(0)]1 < |1012 a 2 2v sup 0" K + 200 inf <= a sup ||&]| - a sup v² || BE
BE
EE
| 2 (2- v)) |0]
for v3 |01 < s and a, v sufficiently small.
SGA. The situation differs from the above since parameter À follows alignment criterion, namely = sign "E H)), which cannot be made small. First note that
GT = 0/g - 00 (AT {) = x + y² x² 22² + A(2² 8² + x xy²)
8 GsGA a + 22222 -2y²
x3 y zyj
and splitting
x y in two yields
x + n² 2x² 2y² (x² - 2822 + (x² ))2 + 2- - 8)]
2
for |101|2 x² + 2 > 9, while
4
1 |(-22 + ry + +2) x >
x y
+ ry =
2
21

---

Published as a conference paper at ICLR 2021
for ||0|| > 0. Summing the two yields 0* GSGA 1 for |10|2 9 and A -. If =
GsGA x² y² + + xyy"
r² 8² 2n2 2y² + x² xy + +222² + x²)
2 x 3² 2x 2y²² x²y zy
for |00|2= > 9 by swapping x and y in the À = -1 case above. We conclude f GSGA > for
|0112 > 9 regardless of X. For any > 0 we obtain
|[((O]| = |1o|² 200" GSaa + a² ||ssaall < 1101 a (2 (2-alIGssaal() < =11012
for 3 < ||0| < 8 and a < supseB, GSGA.
Bounded iterates: conclusion. Now assume usual that 8g is initalised in any bounded region U. For each algorithm we have found r such that for any s > we have [() < ||@]] for all < ||0|| and a, y sufficiently small. Now pick r' 2 such that U c Bpr. Define the bounded region
V (0- LG(O) L E [0, E B,,).
and pick 2 r' such that V C B. By the above we have |[[(]]] < ||0]| for all r < ||||| < and ax 7 sufficiently small. In particular, fix any a, < satisfying this condition. We claim that F(0) E B, for all 0 E B,. Indeed, either 0 E B, implies F(0)
aG(0) E EV B, or 0 B, implies [[(0)] || < ||]|| < s and so (()) E Bg. We conclude that 0g E U C B, implics bounded iterates 0g F (0) E B, for all K.
Non-convergence: strategy. We show that all methods in A have the origin as unique fixed points for y 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 VG at the origin is negative- definite. 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
Vg = H = -1 1
00.
-1 -1
AGD,
We have
[61 =
[1 = 0
GAGD =0 +
- =
0 0.
(() aE1, 02) =0
{2 =0
Now
Ez(x - adı (x, v). -x (r- aly - x x y yd
xx(-1 - a) + -1 + a) + ax +
so the Jacobian at the origin is
-1 1
JAGD =
-1 -1+a
with symmetric part
-1 -a/2
SAGD
-a/2 -1+a
which has negative trace for all a < and positive determinant
a²/2 + (a 1) + -
for all a < 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 a 1/2.
22

---

Published as a conference paper at ICLR 2021
EG.
We have
GEG = [id og) id of =0 I aly x x²) = 0
v a - y v²) = 0.
We have shown that any bounded initialisation results in bounded iterates for EG for a sufficiently small. Let U be this bounded region and assume for contradiction that id a 0 with æ, y * (noting that = 0 implies = 0 by the first equation and vice-versa). We can assume I, y > since any other solution can be obtained by a quadrant change of variable (f). We first prove that 2, < for 0 < 1/ supseu (y + x J. Indeed we have
0 E > x a sup > x
DEU
hence x < 1. similar derivation holds y, hence < x, < 1. But now x 2 y implies
E aly y + و²) x01 ax²²) 2 xx1 a) >
for a < 1 while < implies
E 2 -
- x - v²) = y(1 - a1y) 2 y a)) >
and the contradiction complete, hence 0 0 the only fixed point of EG. Now
JEG H(1 aH)) (11 .) ()+ +
-a
--1 (1 2a
-1 1 20x
a 1
-1
with SEG = =1 < 0, hence JEG - for all a.
OMD. By Daskalakis Panageas (2018, Remark 1.5), fixed points of OMD must satisfy & by viewing OMD as mapping pairs (0z, O2-1) to pairs 10 0k), hence 0 = 0. Now
-1
11)
1
-1 2a
JOMD = 2H - H(I aH) 2
-1
1 +
2a + 2a
-1
-1 20x
Now notice that
1 2a:
1 + 2o + 2a S 1
and
-22
1+2a
SOMD =
I +2a 0
-2
1+2a
x0
142a+ 2n²
for all
CO. We have
Gco = (I (I+ = = 5= + 0
for all y since the matrix
(T (T+ = (1-7 -
always invertible with determinant (1 7)² + 22 0. Now
Jco = -I+ -I++ (1-7 1-m) (=1 1) -11 2y
-1
20
-1
-1 2
for all 7 1/22.
23

---

Published as a conference paper at ICLR 2021
SGA.
We have
GSGA = (I+ =0 = f=0 +
==
since antisymmetric with eigenvalues ia, E R implies that XA" is always invertible with eigenvalues 1 + iA + 0. Now recall that À is given by
A = sign (15, H {)A HH E)) sign (5" H 5" AH'
We have
HT ( - + +xx²
-1
00
-1+
and
-1+ -1+3y2 > 0
AH 1 3r. 1
for all ||0|| sufficiently small, hence 5" H g S 0 and E9 AH g 2 and thus
À = sign (15, H² <AAA" H T 2)) sign (5" T H g AHH 0
around the origin. Now
JSGA = (T+ (1 - ( ( -) =+*) x0
for all À < 1. which holds in particular for À S 0.
CGD.
Note that
Ho = (-) 0) =A
0
antisymmetric, hence + oHH always invertible as for SGA and
GOOD (I + aHo) = f=0 = 0=
Now
{ -a (=t -) 1+a² -1-a -1+a x0
1
-l+a 1+a )
JCGD = (T + aH.
l+a2 a
for all a <
LA. As above,
GLA = (1 (1-
alla){ =0 + = + 0=0
since - allo) is always invertible. Now
1
JLA = (I - - -T-
-1
-1+a
for all a < 1.
LOLA.
Notice that
diag (H = diag
(
-1
y y x
-y + z3
- y + y3 )
x + 3²
y + yd
Hof
y + x 33
and so
GLOLA (I (H.) - diag (H. =
(I -I-22HHa) + {=0 - 0=0
as for LA. Similarly, substituting 2a for in the derivation for LA yields
JLOLA = (I - - -
for all 1/2.
24

---

Published as a conference paper at ICLR 2021
SOS. As for LOLA we have
Gsos = - afH.) pa diag (H) = = =
$-= == 0 == 0
for any a,p. Now p0)) 0 for fixed points 0 by Letcher al. (2019b, Lemma D.7), hence
(=1+a a -11-a -1+a 0
1+a
)
Jsos = JI.A
for all a < 1.
covvconveree conclusion. We conclude that all algorithms in A have the origin as unique fixed points, with negative-definite Jacobian, for a, sufficiently small. If method converges, 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 more direct proof.
Take any algorithm in A and let U the initialisation region. We prove that the stable set
Z = 100 E U
lim F* (0o) =0}
k
has Lebesgue measure zero for sufficiently small. First assume for contradiction that 0g - 0 with Og 7 for all k. Then
G(Ox) G(O) + (G(0)), - 0(110 +
since G(0) = 0, and we obtain
| 11 = |10, aG(Oaa)l
||0x 2 200h G(O+) + a² |
> ||0,12 - VG(()0 + 0(11=11)) > ||0x1|
for & sufficiently large, since VG(0) < This a contradiction to 0g + 0, so 0g + implies
8g 0 for some l and so, writing Fu U - Rd for the restriction of F to
c OC
We claim that Fu a C local diffcomorphism, and diffcomorphism onto its image. Now Gy is
C with bounded domain, hence L-Lipschitz for some finite L. By Lemma O, the cigenvalues of VG in U satisfy [A] S ||VG|| < L, hence VFu I VVG has eigenvalues 1 1-at aL > O. It follows that V. is invertible everywhere, the Inverse Function Theorem (Spivak, 1971, Th. 2.11). To prove that Fy U + F(U) diffeomorphism, it is sufficient to show injectivity of Fv. Assume for contradiction that Fir (0) (8') with 8 + Then by definition,
at 2 1 a|\| > Fy is a local diffeomorphism by
0' = aGGu (()))
and
| 8'1l = a (f') - Go (0) s aL ||e - 8 < -
contradiction. We conclude that Fu is a diffeomorphism onto its image with continuously differ- entiable inverse F-11 hence FT1 is locally Lipschitz and preserves measure zero sets. It follows by induction that 1a( F ({0))) = 0 for all k and
m(Z) < p (U ((oO)) ((0))) =
since countable unions of measure zero sets have zero measure. Since 6g follows continuous distribution V, we conclude
Pe lim limm (0)) (0o) (000)==0= =0)= -0)=
required. Since all algorithms were also shown to produce bounded iterates, they almost surely have bounded non-convergent iterates for a, 7 sufficiently small. The proof is complete; iterates are plotted for single run of each algorithm in Figure with 7 0.01.
L
25

---

Published as a conference paper at ICLR 2021
8o
C00
LOLA
525
Figure 3: Algorithms in fail converge in N with a = = 0.01. Single run with standard
normal initialisation, 3000 iterations.
G PROOF OF COROLLARY
Corollary 1. There are no measures of progress for reasonable algorithms which produce bounded iterates in M or N.
Proof. Assume for contradiction that measure of progress M exists for some reasonable algorithm and consider the iterates 0% produced in the game M or A. prove that the set of accumulation points of 0g is subset of critical points, following Lange (2013, Prop. 12.4.2). Consider any accumulation point 8 = limm-+oc 9x... The sequence (0x) is monotonically decreasing and bounded below, hence convergent. In particular,
lim ((F(O....)) lim M(O = lim M(0k....
By continuity of M and F, we obtain
M(F = (lim F(O = lim M(F(O...)) =
lim M (0
and hence F(O) 0. Since reasonable, 0 must be critical point. Now the only critical point of M N is the strict maximum 0 = O, so any accumulation point of 0g must be 0. The sequence 0g is assumed be bounded, so it must have least one accumulation point by Bolzano- Weierstrass. A sequence with exactly one accumulation point is convergent, hence 0g + 0. This is in contradiction with the algorithm being reasonable.
26


Reviews:
[{"review_id": "w01IQE1Upfw", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper shows that the class of two-player markets have no satisfactory outcome in the usual sense. Players should neither escape to infinite losses nor converge to strict maxima or non-critical point. Some concrete examples are analyzed with negative results. \n\nThis paper is a reminder of researchers: we should carefully model the objective functions of multiple interacting intelligent agents and the interactions between them.\n\nWeakness:\nIt is better to describe the \\alpha and \\gamma in Sec. 3.3.", "extra_scores": {}, "extra_text": {}}, {"review_id": "DKr1SDLtYi", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary:\n\nThis paper deals with the impossibility of global convergence to stationary points in multi-loss optimization. The authors introduce some problems for which any “reasonable“ method has an undesired behavior.  \nThe notion of “reasonable method” is quite general and makes the result of this paper interesting. \n\n\n### pros: \n- The framework of “reasonable methods” is quite general. \n- The paper answers an important question of the game optimization community. \n- The paper is easy to read and well written.\n\n### cons:\n- there are some imprecisions (see my section about questions) \n\n\n## Questions: \nThe questions are asked by decreasing order of importance. \n\n### Proof of Theorem 2\n\nIn the proof of Theorem 2 (page 19) you claim that the function $h(\\theta):= \\inf_k (\\|F_0^k(\\theta)\\|)$ is continuous. I do not know if it is true or false (it is likely to be true), but this claim is not obvious (since it is an infimum of continuous functions). \n\nAlso, the statement in your theorems only considers the reasonable algorithms with the hyperparameters, ensuring that (R2) is valid. An easy way to get rid of this additional assumption may be to remove the mention of hyperparameter (in the sense that an algorithm with hyperparameters that make it locally converge to local maxima is not a reasonable algorithm). \n\n### Definition of $F(\\theta)$ \nAt the end of page 3, you have $F$ that can depend on all the previous iterates $F(\\theta_k,\\ldots,\\theta_0)$ but then in your definition R1 $F$ only depend on a single iterate $\\theta$. \nHow can you reconcile that a method may depend on all the previous iterates and Assumption R1? One simple way is maybe to consider a time-dependent operator $F_k$ such that $F_k(\\theta_0) = \\theta_{k+1}$.  .\n\n### About Proposition 2\n\nIt seems to me that most of the results of this proposition have been already covered by \n [Daskalakis and Panageas, 2018] [Adolphs et al., 2018] [Mazumdar et al. 2020] and[Berard et al. 2020]. What is your relative contribution?\nAlso, note that $H_d$ and $S$ are not defined.\n\n### Global convergence in Balduzzi et al. 2018\nI am not sure what global convergence result you are mentioning. Also, in your related work section, you should differentiate Hsieh et al. 2020 from the other related work. While  Hsieh et al. 2020 is trying to tackle the general nonconvex-nonconcave (which is very related to your work), the other related work mentioned in the first paragraph of Page 2 consider restrictive assumptions that allow them to get a Lyapunov function related to convex optimization (while your work implies that such a function does not exist in general).\n\n\n\n### Minor comment \n- the sentence “Lipschitz continuity of $\\nabla f$ is not assumed, which would fail even for cubic polynomials” is a bit confusing since you mention the Lipschitz constant of $\\nabla f$ in Proposition 1. I suggest emphasizing that the *global* (outside of $U_0$) Lipschitz continuity is not assumed. \n- In the contribution section, $\\mathcal A$ is not defined. (I suggest to point to the appendix or specify that $\\mathcal A$ is the restricted class of function you mentioned at the beginning of your sentence)\n- Note that it would be interesting to discuss the Lyapunov function used to show the global convergence in the non-convex minimization setting (the suboptimality f(\\theta) -f^*). The current illustration you have  (page 8) also works in the multi-objective setting (by considering that H has a positive definite symmetric part). Thus, it is not very insightful of the main difference between single and multi-objective minimization.  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9vRKMxOqyJn", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\n1. 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.\n2. Theorem 2 states that a two-player game with a specific loss cannot converge to the only strict minimum. As the major result of the paper, this finding however has very limited value in practice. The specifically designed loss is not justified to be used in reality, and the result is built upon this loss. If the loss has nowhere to be found in use, investigating such a loss inspires the community very little.\n3. Similar to Theorem 2, it states in Theorem 3 that a two-player game with a specific loss cannot converge to the only strict maximum. Even more unclear to the reviewer, such a result can provide useful value to the community or not. A game with only strict maximum cannot converge to the maximum is not quite interesting to the community (as the reviewer believes).\nSome minor comments:\nThe paper use the term of “simultaneous” quite a lot in the first part of the paper. This is quite confusing for the readers as this term is not quite acknowledged.", "extra_scores": {}, "extra_text": {}}, {"review_id": "44ORizNn3p", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Thank you for the explanation and the update of the writeup.\nI still find the main message interesting but not critical for any real application. \nHence my evaluation remains as weak accept.\nThank you.  \n\n\n\n%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n\n\nThe paper provides an impossibility type of result for convergence of reasonable dynamics in general multi-loss settings. Specifically, the paper constructs a game between two agents whose only simultaneous critical point is a strict maximum. Thus under the definition of a 'reasonable' algorithm as an algorithm that avoids strict maxima, the dynamics cannot converge to equilibria in this case and has to therefore cycle.\n\nThe paper builds on a series of recent papers that show that many reasonable dynamics fail to converge in reasonable multi-loss settings (e.g. GD in zero-sum games). On the positive side, the results accounts for a large class of optimization/gradient driven dynamics. Also, the example of the multi-agent setting is relatively small. Two agents/two degrees of freedom. On the negative side, the example is rather artificial and it does not seem to capture any specific setting of independent interest. Moreover, there is little intuition in the current writeup behind the construction of the example. The appendix just shows that this example satisfies the target properties.\n\nThe main of message of the paper is that multi-loss settings are very different from single loss settings and we cannot quickly and easily apply tools from optimization and hope to succeed at least not in all cases. The predominance of multi-loss architectures in AI settings makes this a reasonable message for ICLR.  On the other hand, it is clear that we are not moving away from these architectures any time soon, so such a message is less effective than explanation/tools of how to understand multi-loss environments or make them work better. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a series of negative results regarding the convergence of deterministic, "reasonable" algorithms in min-max games. The defining characteristic of such algorithms is that (a) the algorithm's fixed points are critical points of the game; and (b) they avoid strict maxima from almost any initialization. The authors then construct a range of simple $2$-dimensional "market games" in which every reasonable algorithm fails to converge, from almost any initialization.

The paper received three positive recommendations and one negative, with all reviewers indicating high confidence. After my own reading of the paper, I concur with the majority view that the paper's message is an interesting one for the community and will likely attract interest in ICLR.

In more detail, I view the authors' result as a cautionary tale, not unlike the NeurIPS 2019 spotlight paper of Vlatakis-Gkaragkounis et al, and a concurrent arxiv preprint by Hsieh et al. (2020). In contrast to the type of cycling/recurrence phenomena that are well-documented in bilinear games (and which can be resolved through the use of extra-gradient methods), the non-convergence phenomena described by the authors of this paper appear to be considerably more resilient, as they apply to all "reasonable" algorithms. Determining whether GANs (or other practical applications of min-max optimization) can exhibit such phenomena is an important open question, and one which needs to be informed by a deeper understanding of the theory. I find this paper successful in this regard and I am happy to recommend acceptance.
Decision: Accept (Poster)