Local Convergence Analysis of Gradient Descent Ascent with Finite Timescale Separation
Authors: Tanner Fiez
Lillian J Ratliff
Venue: ICLR 2021 Poster (2021)
Keywords: game theory
continuous games
generative adversarial networks
theory
gradient descent-ascent
equilibrium
convergence

Abstract: We study the role that a finite timescale separation parameter $\tau$ has on gradient descent-ascent in non-convex, non-concave zero-sum games where the learning rate of player 1 is denoted by $\gamma_1$ and the learning rate of player 2 is defined to be $\gamma_2=\tau\gamma_1$. We provide a non-asymptotic construction of the finite timescale separation parameter $\tau^{\ast}$ such that gradient descent-ascent locally converges to  $x^{\ast}$ for all $\tau \in (\tau^{\ast}, \infty)$ if and only if it is a strict local minmax equilibrium. Moreover, we provide explicit local convergence rates given the finite timescale separation. The convergence results we present are complemented by a non-convergence result: given a critical point $x^{\ast}$ that is not a strict local minmax equilibrium, we present a non-asymptotic construction of a finite timescale separation $\tau_{0}$ such that gradient descent-ascent with timescale separation $\tau\in (\tau_0, \infty)$ does not converge to $x^{\ast}$. Finally, we extend the results to gradient penalty regularization methods for generative adversarial networks and empirically demonstrate on CIFAR-10 and CelebA the significant impact timescale separation has on training performance. 

Published as a conference paper at ICLR 2021
LOCAL CONVERGENCE ANALYSIS OF GRADIENT DE- SCENT ASCENT WITH FINITE TIMESCALE SEPARATION
Tanner Fiez& & Lillian J. Ratliff
Department of Electrical and Computer Engineering University Washington
Seattle, WA 98195
{fiezt, ratliffl]ed Guw. @uw. edu
ABSTRACT
We study the role that a finite timescale separation parameter has gradient descent-ascent in non-convex, non-concave zero-sum games where the learning rate of player 1 is denoted by ?1 and the learning rate of player is defined be = 7711 We provide a non-asymptotic construction of the finite timescale sepa- ration parameter such that gradient descent-ascent locally converges x for all T E (T", oo) if and only if it is strict local minmax equilibrium. Moreover, we provide explicit local convergence rates given the finite timescale separation. The convergence results we present are complemented by non-convergence re- sult: given a critical point x² that not strict local minmax equilibrium, we present a non-asymptotic construction of a finite timescale separation To such that gradient descent-ascent with timescale scparation T E (To, oo) does not converge to.r.. Finally, extend the results to gradient penalty regularization methods for generative adversarial networks and empirically demonstrate on CIFAR-10 and CelebA the significant impact timescale separation has training performance.
INTRODUCTION
In this paper we study learning in zero-sum games the form
min max f(11,22) E, EX;
where the objective function of the game ff is assumed to be sufficiently smooth and potentially non- convex and non-concave in the strategy spaces X, and X₂ respectively with each X; a precompact subset of Rh This general problem formulation has long been fundamental in game theory (Başar) Olsder 1998) and recently has become central to machine learning with applications in genera-
tive adversarial networks (Goodfellow et al.) 2014), robust supervised learning (Madry et al. 2018
Sinha et al. 2018), reinforcement and multi-agent reinforcement learning (Rajeswaran et al. 2020
Zhang et al. 2019), imitation learning (Ho & Ermon 2016), constrained optimization (Cherukuri
et al. 2017). and hyperparameter optimization (Lorraine et al.) 2020 MacKay et al., 2019).
The gradient descent-ascent learning dynamics widely studied as potential method for effi- ciently computing equilibria in game formulations. However, in zero-sum games, number of past works highlight problems with this learning dynamic including both non-convergence to meaning- ful critical points as well as convergence to critical points devoid of game theoretic meaning, where common notions of 'maanngfull' equilibria include the local Nash and local minmax (Stackelberg) concepts. For instance, in bilinear games, gradient bascent-ascenn avoids local Nash and Stackel- berg equilibria due the inherent instability of the update rule for this class. Fortunately, this class of games, regularization or gradient- based learning dynamics that employ different numerical discretization schemes (as compared to forward Euler for gradient descent-ascent) are known to al- leviate this issue (Daskalakis et al. 2018 Mertikopoulos et al.) 2019 Zhang & Yul 2020). For the more general nonlinear nonconvex nonconvex-nonconcee nonconcave class of games, has been shown gradient descent- ascent with shared learning rate is prone reaching critical points that are neither local Nash equilibria nor local Stackelberg equilibria (Daskalakis & Panageas] 2018 Jin et al.) 2020 Mazum dar et al. 2020). While important negative result, it does not rule the prospect that gradient

---

Published as a conference paper at ICLR 2021
descent-ascent may be able to guarantee equilibrium convergence it fails to account for a key structural parameter of the dynamics, namely the ratio of learning rates between the players.
Motivated by the observation that the order of play between players is fundamental to the definition of the game, the role of timescale separation in gradient descent-ascent has recently been explored theoretically (Chasnov et al.. 2019 Heusel et al. 2017 Jin et al. 2020). On the empirical side, it has been widely demonstrated that timescale separation in gradient descent-ascent is crucial to im- proving the solution quality when training generative adversarial networks (Arjovsky et al. 2017 Goodfellow et al. 2014, Heusel et al. 2017). Denoting 71 as the learning rate of the player 1, the learingg rate of player 2 can be redefined as 7/2 = Ty1 where T = 72/21 > 0 is the learning rate ratio. Toward understanding the effect of timescale separation, Jiin et al. (2020) show the locally sta- ble critical points of gradient descent-ascent coincide with the set of strict local minnax/Stackelberg equilibrium across the spectrum of sufficiently smooth zero-sum games as - co. In other words, all 'bad critical points' (critical points lacking game-theoretic meaning) become unstable and all "good critical points' (game-theoretically meaningful equilibria) remain or become locally expo- nentially stable (cf. Definition g as + co. While a promising theoretical development, gradient descent-ascent with timescale separation approaching infinity does not lead to practical learning rule and the analysis of it does not necessarily provide insights into the common usage of a reason- able finite timescale separation. An important observation is that choosing arbitrarily large with the goal of ensuring local equilibrium convergence can lead to numerically ill-conditioned prob- lems. This highlights the significance of understanding the exact range of learning rate ratios that guarantee local stability. Moreover, our experiments in Section 5 (Dirac-GAN) and in Appendix K show that modest values of are typically sufficient to guarantee stability of only equilibria which allows for larger choices of ?/1 and results in faster convergence to an equilibrium.
Contributions. We show gradient descent- ascent locally converges a critical point for range of finite learning rate ratios if and only if the critical point is a strict local Stackelberg equilibria (Theorem This result is constructive in the sense that we explicitly characterize the exact range of learning rate ratios for which the guarantee holds. Furthermore, we show all other critical points are unstable for a range of finite learning rate ratios that we explicitly construct (Theorem 2 To our knowledge, the aforementioned guarantees are the first of their kind in zero-sum games for an implementable first-order method. Moreover, the technical results in this work rely tools that have not appeared in the machine learning and optimization communities analyzing games. Finally, we extend these results to gradient penalty regularization methods in gen- erative adversarial networks (Theorem 3), thereby providing theoretical guarantees for common combination of heuristics used in practice, and empirically demonstrate the benefits and trade-offs of regularization and timescale separation on the Dirac-GAN along with image datasets.
2 PRELIMINARIES
A two-player zero-sum continuous game is defined by a collection of costs (fi, f2) where f1 = f and f2 = =f with f E C² RR) for some r 2 2 and where X X, X X2 with each X; precompact subset of RT for E {1, 2} and n = nı + 722. Each player i E I seeks to minimize their cost fz,,, xx) with respect to their choice variable x, where x=; the vector of all other actions 2, with j # i. We denote D.fr as the derivative of f: with respect to 24, Dij as the partial derivative of D.J; with respect to Ij. and D.. fa as the partial derivative of Daf, with respect to I;-
Mathematical Notation. Given matrix A E R=1x"2, let voc(A) E R be its vectorization such that vec(A A) takes rows a; of A, transposes them and stacks them vertically in order of their index. Let & and + denote the Kronecker product and sum respectively, where A @ B A & I + I & B. Moreover, Hi is an operator that generates an ( (1)+1) matrix from a matrix A E Bax= such that A A = H (A @ H)H,, where H [ H - is the (left) pseudo- inverse of H,, a full column rank duplication matrix. Let A (-) be the largest positive real root of its argument it exists and zero otherwise. See Lancaster & Tismenetsky (1885) and Appendix B for more detail.
Equilibrium. There are natural equilibrium concepts depending on the order of play: the (local) Nash equilibrium concept in the case of simultaneous play and the (local) Stackelberg (equivalently minmax in zero-sum games) cquilibrium concept in the case of hicrarchical play (Başar & Olsder,
Following Fiez et al. 2020), we refer to strict local Stackelherg as differential Stackelherg throughout.
2

---

Published as a conference paper at ICLR 2021
1998). Formal local equilibrium definitions are provided in Appendix B while here characterize the different equilibrium notions in terms of sufficient conditions on player costs as is typical in the
machine learning and optimization literature (see, c.g., Berard al. 2020; Daskalakis & Panageas
2018 Fiez et al. 2020 Goodfellow 2016 Jin et al. 2020 Mazumdar et al. 2020: Wang et al. 2020).
The following definition is characterized by sufficient conditions for local Nash equilibrium.
Definition 1 (Differential Nash Equilibrium, Ratliff et al. 2013). The joint strategy x E X is differential Nash equilibrium if (a)()) = 0. - D2f = 0, (ff(2) > 0, and D < O.
The Jacobian of the vector of individual gradients g(x) ( is defined by
Dzf(x) D12S(x) -D)2f(x) (z)
J(x)
Let (-) denote the Schur complement of (.) with respect the n2 ng block in (-). The following definition is characterized by sufficient conditions for a local Stackelberg equilibrium.
Definition (Differential Stackelberg Equilibrium, Fiez et al. 2020). The joint strategy x E is
differential Stackelberg equilibrium if (2) = 0, - D2] = 0, S (J(x)) > 0, Dzf(x) <
Learning Dynamics. We study agents seeking equilibria of the game via a learning algorithm and consider arguably the most natural learning rule in zero-sum continuous games: gradient descent- ascent (GDA). Moreover, we investigate this learning rule with timescale separation between the players. Let 72/71 be the learning rate ratio and define A, blockdiag (Ing. : where In, is a n. x n; identity matrix. The T-GDA dynamics with g(x) = (Dif -Daf) -D2((x) are given by
Tk+1 = Ik - 71
3 STABILITY OF CONTINUOUS TIME GDA WITH TIMESCALE SEPARATION
To characterize the convergence of 7-GDA, we begin by studying its continuous time limiting system
i i= -zg(().
The Jacobian of the system from (3) is given by J, = J()) where Jzx defined in [I] Observe that critical points (x* such that g(x*) = 0) are shared between 7-GDA and (3). Thus, by analyzing the stability of the continuous time system around critical points as a function of the timescale separation using the Jacobian J-(z"), ), we can draw conclusions about the stability and convergence of the discrete time system T-GDA. well known that a critical point locally (exponentially) stable when the spectrum of (xx(") is in the open left-half complex plane C² (cf. Theorem B.I Appendix B). Throughout, we use the broader term "stable" to mean the following.
Definition critical point locally exponentially stable for i = -A)((z) if an only if (,ec(-J,(2") )2))) C. C (or, equivalently, spec(J) (x*)) C C.)) where Co and C₁ denote the open lefi-half and right-half complex plane, respectively.
We now show differential Stackelberg equilibria are the only critical points that are stable for range of finite learning rate ratios whereas the remainder of critical points are unstable for range of finite learning rate ratios. Importantly, we characterize the learning rate ratios for which the results hold.
3.1 NECESSARY AND SUFFICIENT CONDITIONS FOR STABILITY
To motivate our main stability result, the following example shows the existence of a differential Stackelberg which is unstable for T = 1, but is stable all for T E (r*, where T" is finite.
Example 1. Consider the quadratic zero-sum game defined by the cost
f(11, = (-2 1 2
1 2 + T12
2
2 22
1222
where v > 0 and 21, I.a. The unique critical point x² (0.0) is differential Stackelberg
equilibrium since g(x*) = 0, S (J(())) = diag(v, :) > 0, and D3 = - diag( 2, v) < O.
Note that di differential Nash are subset of differential Stackelberg (Fiez al. 2020 Jin al. 2020
3

---

Published as a conference paper at ICLR 2021
Moreover, that for any v > 0, x" is unstable for = since spec J (x*) )) g C_ but x² is stable for a range of learning rates since (pec C for all
=
- 8r - 1), - (T-2 /² 1-2--27-11 4)). Observe
(2, 00).
In other words, GDA fails converge to the equilibrium but a finite timescale separation is sufficient to remedy this problem. We now fully characterize this phenomenon. To provide some background, we remark it is known that the spectrum of J, (x"")) asymptotically splits as T + oo such that ni eigenvalues tend to fixed positions defined by the eigenvalues of (J=")=))) while the remaining ng eigenvalues tend to infinity at a linear rate т along asymptotes defined by the eigenvalues of Dx=("") This result is known from Klimushchev & Krasovskii (961) and further discussion can be found in Appendix [ as well as from Kokotovic et al. (1986 Chap. 2. Thm. 3.1). The previ- ous fact is specialized from the class of singularly perturbed linear systems to T-GDA by JJin et al. (0200) which directly results in the connection between critical points of co-CDA and differential Stackelberg equilibrium. Specifically, the result Jin et al.] (2020) is showing that for the class of all sufficiently smooth games the stable critical points of (o-GDA are exactly the strict local min- max. As corollary of this fact, there exists T < 00, such that 7-GDA is stable for all > л1 Kokotovic et al. 1986, Chap. 2, Cor. 3.1); this can be inferred from the proof of Theorem 28 in Jin et al. (2020) as well. Indeed, Jin al. (2020) gives an asymptotic expansion showing that Mn eigenvalues valuss of - -+(x)) are in spec - S1 (J J]] + ((T and the remaining n2 eigenvalues are in (spocc [[spoc(D3f( (x") + O). Using the limit definition for the asymptotic expansion, for any fixed game and striet local minmax xx, one can show that there exists a finite such that x" is stable, We provide a detailed discussion of the relationship between the results of [Jin et al.) 2020) and Kokotovic et al. (1986) in Appendices [ [ Unfortunately, the finite obtainable from the asymptotic expansion method can be arbitrarily large. From a practical perspective, this poses significant problems for the implementation and performance of T-GDA. Indeed, the eigen- value gap between () ))) and spec(rD3f(x")) has a linear dependence on T and, in turn, the problem may become highly ill-conditioned from numerical perspective as becomes large (Kokotovic 1975). In contrast, we determine exactly the range of 7 such that the spectrum of (x) remains Co and hence, remedy this problem.
For the statement of the following theorem on the non-asymptotic construction of T², we define the following matrices: for a critical point x", let S -=)(-)(a")) An
A12 A and
fD)f(x*) - -D22f(x)) - -D(es(>)) +DZs(**]
An
A12
- (x")
-TA
TA22]
Theorem 1 (Non-Asymptotic Construction of Necessary and Sufficient Conditions for Stability). (ff))==f--aa -f--f) defined by (X, R) for some r 2 2. Suppose that x² is such that g(x²)) 0 and det( (D212(x))) + O. There exists 7² [0, x0) such that (x C C2 for all T E (7*, ifd only if xf is differential Stackelberg equilibrium.
Consider a zero-sum game f2) =
Moreover, 7" = =>==xxxx (Q) where
A H (A @ Lnz) S H (S1 @ A12 (A11 @ A
Q=2 A (mn, @ A A
with Ap2 = A2 H A22 and S S S.S. S.. Sj.
While first glance Q may appear difficult to understand, it is efficiently computable and can be used to understand the typical value for important classes of games. Indeed, many problems like generative adversarial networks have specific structure for the individual Hessians of each player and the interaction matrix D (cf. Assumption [ Section 3.3) and are in sense subject to design via network architecture and loss function selection. This result opens up an interesting future direction of research on understanding and potentially designing the structure of Q. To take step in this direction, we explore a number of games in SectionSSJand Appendix K where we compute 7 by the construction and validate it is tight empirically. Along the way, we discover that 7" is typically a reasonable value that is amenable to practical implementations.
As direct consequence of Theorem T-GDA converges locally asymptotically for any sufficiently small (7) and for all 5 E (r*, bo) if and only if x² is a differential Stackelberg equilibrium; for a formal statement see Corollary
in Appendix C
Proof Sketch of Theorem ? The full proof is contained in Appendix C The key tools used this proof are a combination of Lyapunov stability and the notion of guard map (Saydy et al.) 1990).
4

---

Published as a conference paper at ICLR 2021
new tool to the learning community. Recall that a matrix is exponentially stable if and only if
there exists a symmetric positive definite = PT > 0 such that PJ, (x") + JJ (x*) > 0 (cf.
Theorem B.1 Appendix B). Hence. given positive definite = Q" > 0, -x")(xx) is stable if and only if there exists a unique solution P = PT to
(JJ (x" 2 (1 J, (x ())")))) vec (J @ J (2") vecc(P) = vec(Q)
(4)
where @ and @ denote the Kronecker product and Kronecker sum, respectively The existence of unique solution P occurs if and only if J. and -J, have no eigenvalues in common. Hence, using the fact that eigenvalues vary continuously, if we vary T and examine the eigenvalues of the map J. (x*) ① J, (a"), this tells us the range of for which spec(-J, remains in C2. This method of varying parameters and determining when the roots of polynomial (or correspondingly, the eigenvalues of a map) cross the boundary of domain uses a guard map; it provides a certificate that the roots of a polynomial lie in particular guarded domain for a range of parameter values.
Formally. let X' be the set of all n x n real matrices or the set of all polynomials of degree n with real coefficients. Consider S an open subset of X' with closure S and boundary as. The map v: - C said to be guardian map for S if for all x E S, v(x) =0 > x E as. Elements of S(C = {A E R=x= : spec(A) A) C C2 } are (Hurwitz) stable. Given a pathwise connected
set U S R, the parameterized family {A(T): T E U} is stable and only if (i) it is nominally
stable meaning A(T)) E S(C=) for some Ti E U-and (ti) v(A(T)) L 0 for all
U (Saydy)
et al. 1990 Prop. 1). The map v(T) = (ct @ I)) = det(- (x=(2") @ (+(x))) guards
S where 3 is the bialternate product and is defined by A B 2 (A @ B) for matrices A and
B (Govaerts 2000 Sec. 4.4.4). For intuition, consider the case where each 21, I2 E R so that
b rd] E 2x2
Jx(x") -bb
is known that (pec(-J,(z")) c C if det( (x)(-)))'=")))) > and tr(-J, < 0 so that v/r) = de tr tx(-",(x")) is guard map for the 2 2x2 2 stable matrices S(C2), ). Since the bialternate product generalizes the trace operator and det(- )) = n d fx=" (J (z)))) # 0 for r * 0 by the facts (S ))) + 0 and det (Df(( + 0) for a differential Stackelberg equilibrium xx" a guard map in the general n x n case is (T) det (Jt( (x*) $ J+(x))))
This guard map in r is closely related to the vectorization in 4 for any symmetric positive definite Q=Q== > 0, there will be a symmetric positive definite solution p = PT of (J, (a*) @ J. vee))))))(P)) P) vec(- )) if and only if det( (J,, ( J, (x (z"))) & 0. Hence, to find the range of for which, given any Q = Q > 0, the solution P p= PT is no longer positive definite, we need to find the value of r such that v(T) =
@ (+))))) = 0-that is, where it hits the boundary (SC).. Through algebraic manipulation, this problem reduces to an eigenvalue problem in r, giving rise to an explicit construction of r"
3.2 SUFFICIENT CONDITIONS FOR INSTABILITY
To motivate our main instability result, the following example shows a non-equilibrium critical point that is stable for = 1, but is unstable for all T E (To. oo) where To is finite.
Example 2. Consider the quadratic zero-sum game defined by the cost
f(e1. [2 1 + 2r11 + 1 + 2x x22)
where x1, E R² and v > 0. The unique critical point x= (0, is not a differential Stackelberg
(nor Nash) equilibrium since f+f(=*)= = 2 7 0, fx²((x) = diag(u/4, -v/2) & O. Moreover, spec(-J, (x'xx )) = (2T - 1 + V 12r + 1), = (2 - - - 1 + 4)). Observe that for any 0 > x= is stable for T =1 since spec(-J,
C2 but x" unstable
for a range of learning rates since Jr (z*)) & C for all + E (2, x)). This is not an artifact of the quadratic example: games can be constructed in which stable critical points lacking game- theoretic meaning become unstable for all T > To even in the presence of multiple equilibria.
SSe Lancaster & Tismenetsky 1985 Magnus 1 1988 for more detail on the definition and properties of these mathematical operators, and Appendix C for more detail directly related their in this paper.
5

---

Published as a conference paper at ICLR 2021
This example demonstrates finite timescale separation can prevent convergence to critical points lacking
meaning. We now characterize this behavior generally. Note that Theorem implies that for any critical point which is not differential Stackelberg equilibrium, there is no finite r" such that (peo(-J+(x") C C for all T E (T" oo). In particular, there exists at least one finite, positive value of such that spec(-J+ (xx)) )) & C2. We can extend this result to answer the question of whether there exists finite learning rate ratio To such that -J, -2²(x") has at least one eigenvalue with strictly positive real part for all T E (To, 00). thereby implying that x² is unstable.
Theorem 2 Non-Asymptotic Construction of Sufficient Condition for Instability.). Consider zero-sum game (f1, f2) = (f.-f) defined by f C* R) for some 2 2. Suppose that x² such that g(x*) O, (et(D2f2(x*) + O, and x² not differential Stackelberg equilibrium. Then spee( J- (xx)) & C for all T E (T),20) with
+ + ())) L Pb) - (B
TO
where PL, P2, Q1, are any non-singular Hermitian matrices such that (a) Qi > 0 for each i 1,2, (b) (-J((z)) + (
Q1 and D2f(x*))' P2D f(x")())))) Q2, and (c)
the following matrix pairs have the same inertia: (1,,S(-J1)
and (P2. (x*))
Proof Sketch. The full proof is provided in Appendix D The key idea is to leverage the Lyapunov equation and Lemma B.3 to show that (x") has at least one eigenvalue with strictly positive real eigenvalues, then there exists matri- QI where P1 and ()(-)(x*)) have the same inertia-that is, the number of eigenvalues with positive, negative and zero real parts, respectively, are the same. An analogous statement applies to - -Dz with some Ps and Q2- Since x" non-equilibrium critical point, without loss of generality, let (i(-((x*)) have at least one strictly positive eigenvalue so that Pi does as well. Next, we construct a matrix P that is congruent to blo, P2) and matrix Q+ such that -P'+ Since P and blockdiag( P1, P2) are congruent, Sylvester's 's law of inertia implies that they have the same number of eigenvalues with positive, negative, and zero real parts, respectively. Hence, P has at least one eigenvalue with strictly positive real part. We then construct To via an eigenvalue problem such that for all r > To. Q, > O. Applying Lemma B.3 again, for any T > To. (x*) has at least one eigenvalue with strictly positive real part that spec(- J, (x") CO.
part. Indeed, Lemma B.3 states that if S1 (1(-J((x)) )) has
ces P1 = PJT and Q = Q > such that PiS ( (=J(x")) + S1(-J(x*))
J (x ) Q
3.3 REGULARIZATION WITH APPLICATIONS TO ADVERSARIAL LEARNING
In this section, we focus on generative adversaria networks with regularization and using the theory developed so far extend the results to provide stability guarantee for a range of regularization parameters and learning rate ratios. Consider the training objective
f(0,w) = Exte) ((D)) + (poo())((-D(r:u)))
where (x) and Gø(2) are discriminator and generator networks, PD(z) is the data distribution while p(z) is the latent distribution, and é (²(RR) is some real-value function Nagarajan & Kolter (2017) show, under suitable assumptions, that gradient- methods for training generative adversarial networks are locally convergent assuming the data distributions are absolutely contin- uous. However, as observed by [Mschhder et al. (2018), such assumptions not only may not be satisfied by many practical generative adversarial network training scenarios such as natural im- ages, but often the data distribution is concentrated on a lower dimensional manifold. The latter characteristic leads to highly ill-conditioned problems and nearly purely imaginary eigenvalues.
Gradient penalties ensure that the discriminator cannot create a non-zero gradient which is orthog- onal to the data manifold without suffering loss. Introduced by Roth et al. (2017) and refined in Mescheder et al. (2018), we consider training generative adversarial networks with one of two fairly natural penalttessee used to regularize the discriminator:
R, w) _TT ppp
D(;; ( and R2(0, w) B
Pa (V D(::
For example, f(x) = log(1 + +ex((-o)) gives the original formulation of Gondfellow al. 2014

---

Published as a conference paper at ICLR 2021
where, by slight abuse of notation, (.(+) denotes the partial gradient with respect to of the argument (.) when the argument is the discriminator D(-:w) in order prevent any conflation between the notation (-)) elsewhere for derivatives. Let h1 (0) VV - and hz(ww) Epn (x) [[)()a:)]= (Z;
Define reparameterizatiio manifolds Ma {0 : pa = PD} and MD {w hy(w) 0} and let MM and MM denote their respective tangent spaces at 6* and wn As in Mescheder et al. (2018), we make the following assumption.
Assumption 1. Consider zero-sum game of the form given in ( where f E CR xR R) and G(:;0) 0) and D(;:w) are the generator and discriminator networks, respectively, and = (0. w) E IRn x m Suppose that x² = =(0",- (0","") is an equilibrium. Then, (u) at (0",""), pa- = pD and D(z; w = 0 in some neighborhood of supp(pp) ), (b) the function & E (2 satisfies (0) & 0
and (0) < 0, (c) there are e-balls B.(0") and B. (.(w") centered around 6* and w', respectively, so that Mg n (ft) and MD n Be(w") define C¹ ""-maifoods. Moreover, (i) if To-Me, then O.
w V Whhh (6*) w + O, and (ii) if & Mw- then e Vihz(w"
We note that as explained by Mescheder al. 2018), Assumption Ici) implies that the discrim- inator is capable of detecting deviations from the generator distribution in equilibrium, and As- sumption [ii)) implies that the manifold MD is sufficiently regular and, in particular, its (local) geometry is captured by the second (directional) derivative of h22
Theorem 3. Consider training a generative adversarial network via a zero-sum game with genera- tor network Gg, discriminator network Dw, and loss [(0,c) w) with regularization R2(0, w) (for either j == 1 or j = 2) and any regularization parameter E (0, co) such that Assumption
! is satisfied for an equilibrium x= (8*,w* w of the regularized dynamics. Then, x² (0", w.w is a differential Stackelberg equilibrium. Furthermore, for any T E (0, oo), Spec(-J(r.))
C C2.
4 PROVABLE CONVERGENCE OF GDA WITH TIMESCALE SEPARATION
In this section, we characterize the asymptotic convergence rate for 7-GDA to differential Stackelberg equilibria, and provide a finite time guarantee for convergence to an E e-approximate equilibrium. The asymptotic convergence rate result uses Theorem [ to construct finite T' E (0, oo) such that x is stable, meaning spec(- J_ J+(")) (a*)) C C and then for any T E (T", oo), the two key lemmas namely, Lemmas F.I and F2 in Appendix [ imply a local asymptotic convergence rate.
Theorem 4. Consider a zero-sum game (fi, f2) = (f:-f) defined by f E C"(XX R) for r > 2 and let x* be a differential Stackelberg equilibrium of the game. There exists a E 00) such that for any T E (5", (0) and a E (0, T-GDA. with learning rate 7/2 = 7 a converges locally asymptotically at a rate of O0(11 (k3)))/ where 7 = minxespee(), (x')) 2Re(A)/1X13,
>= arg min x (x*)) 2Rc(A)/1A and 3 = (2Ro(2a) -a)aa?)-1 Moreover, if x" is differential Nash equilibrium, T* = 0 so that for any T E (0) and a E (0,7). T-GDA with
71 = a converges with a rate O(11 a/ 4/3))
To build some intuition, consider differential Stackelberg equilibrium xt and its corresponding T" obtained via Theorem ss that for any fixed E (r", oo), spec(-J-(x") (x))) C C For the discrete time system T = I& -1 ((AAg((x)) if 71 is chosen such that the spectral radius of the local linearization of the discrete time map is contraction, then 2ą locally (exponentially) converges to x² (cf. Proposition B.I.. With this in mind, we formulate an optimization problem to find the upper bound 7 on the learning rate 71 such that for all 71 (0, p(T )1J+(=")) < 1; indeed, |1 < 1}. The intuition is as follows. The inner maximization problem is over finite set spec(J, = (A.....,A ), where (x*)) E R=**" As y increases away from zero, each |1->A, shrinks in magnitude. The last A such that Y- hits the boundary of the unit circle in the complex plane gives the optimal y and the \ (Je (x*)) that achieves it. Examining the constraint, we have that for each X, 7///2,12 - 2R)();) < 0 for any 7 > 0. As noted this constraint will be tight for one of the X, in which case 7 2Re (R(A)/ since 7 > 0. Hence, by selecting 7 = min minxespec(J=((""
let 7 min {7: maxxespec(J,
2Re(A)/ we have that |1 >1 < 1 for all E (x=c()+(z")) and any 71 E (0.7). From here, one can use standard arguments from numerical analysis show that for the choice of and 8, the claimed asymptotic rate holds.
TheoremAddin direetly implies a finite time convergence guarantee for obtaining an e-differential Stack- elberg equilibrium, that is, a point with an e-ball around a differential Stackelherg equilibrium x".
7

---

Published as a conference paper at ICLR 2021
Corollary 1. Given 0, under the assumptions of Theorem 4 T-GDA obtains d-diferrentia Stackleberg equilibrium in [433 a log(l - x" [=]]]]]] iterations for any 20 E Bs(x*) with a/(LB) where L is the local Lipschitz constant of (z="))
Moreover, the convergence rates and finite time guarantees extend to the gradient penalty regularized generative adversarial network described in the preceeding section.
Corollary 2. Under the assumptions of Theorems and 4 for any fixed p E (0, 0o) and (0, 7-GDA converges locally asymptotically rate of O(11 a/(48))//2), and achieves E-equilibrium in [(43/o) [og(1=z - x² x=11/e)] iterations for any Io E Bs(x*).
In Appendix we extend the convergence analysis to the stochastic setting.
EXPERIMENTS
We now present numerical experiments and Appendix contains further simulations and details.
Regularization, Timescale Separation, and Convergence Rate. The Dirac- GAN (Mescheder et al. 2018) consists of a univariate generator distribution po = âg and linear where the real data distribution pD is given by dirac-distribution
Dirac-GAN:
discriminator D( =)) concentrated at zero. The resulting zero-sum game is defined by the cost f(0, w) = ((ww) + ((0) and the unique critical point (0*, w²) (0, 0) is local Nash equilibrium. However, the eigenvalues of the Jacobian are purely imaginary regardless of the choice of timescale separation so that T-GDA oscillates and fails to converge. This behavior is expected since the equilibrium is not hyperbolic and corresponds to neither a differential Nash equilibrium nor a differential Stackelberg equilibrium but it is undesirable nonetheless. The zero-sum game corresponding the Dirac-GAN with regular- ization can be defined by the cost f00 w) = E(Ow) + E(0) Hw². The unique critical point remains unchanged, but for all E (0, 00) and μ (0, 2o) the equilibrium of the unregularized game is stable and corresponds to differential Stackelberg equilibrium of the regularized game.
observe that the impact of timescale separation with regularization 0.3 is that the trajectory is not oscillatory since it moves faster to the zero line of - D2 (0, w) and then follows along that line until reaching the equilibrium. We further see from Figure Ib that with regularization
From Figures La and If
0.3, 7-GDA with 5 8 converges faster to the equilibrium than 7-GDA with т = 16, despite the fact that the former exhibits some cyclic behavior the dynamics while the
39
RatAc ROCAL
88
Rof
-e-tnglA))
10-11
(8-0%1|
LME
355 002
3.00
0,25
050
835
1,00
2000
2000
3002
4C0E
20
20
Iterations
Trajectories of 7-GDA (b) Distance equilibrium
(c) (ppc((+)..1 0.3
(d) spec (J+):
0.3
0.3
==
T=1,==1
1 0.3
== 4, 0.3
==
8
== 16,u 0.3
T= 1 1.0
(f) Trajectories 7-GDA overlayed on vector fields generated by choices of and μ.
Figure 1: Experimental results for the Dirac-GAN game of Section 5
8

---

Published as a conference paper at ICLR 2021
t=1
T=2
T=4
T=
t= 16
CI AR-10 10
Ci N0- u=1
Cenebi ut
40
20
Number Miri-Bitch Updities 1Dc
Number Nini-atch Upcates
2
4
8
WAT
2
8
16
37.0
27.1
26.3
29.1
14.6
11.7
10.7
10.1
11.2
26.7/21.6
21.6/18.1
20.1/17.6
20.7/18.6
13.1/8.5
10.3/68
8.8/6.1
8.0/5.8
8.1/6.2
Figure 2: CIFAR-10 FID
Figure 3: CelebA FID
latter does not. The eigenvalues of the Jacobian with regularization μ 0.3 presented in Figure Tc explains this behavior since the imaginary parts are non-zero with = 8 and zero with T = 16, while the eigenvalue with the minimum real part is greater at than at 16. This highlights that some oscillatory behavior in the dynamics is not always harmful for convergence. For f and f 1, Figures Ta| and [b] show that even though 7-GDA does not cycle since the eigenvalues of the Jacobian are purely real, the trajectory converges slowly to the equilibrium. Indeed, for each regularization parameter, the eigenvalues of J, 1.000,w"" w*) split after becoming purely real and then converge toward the cigenvalues of S (J("", and f f("",w")))))))) w") & TP, there is a trade-off between the choice of regularization j and the the conditioning of the Jacobian matrix that dictates the convergence rate.
and -7 Df w²). Since (J w²)) x 1/μ
timescale separation
Generative Adversarial Networks: Image Datasets. We build the implementations of Mescheder et al. (2018) and train with the non-saturating objective and the R₁ gradient penalty. The network architectures are both ResNet based. We fix the initial learning rate for the generator to be 71 0.0001 with CIFAR-10 and 71 = 0.00005 for CelebA. The learning rates are decayed so that 71,6 - 71 + w**h and 72,6 771, are the generator and discriminator learning rates update k where = 0.005. The batch size is 64, the latent data is drawn from standard normal of dimension 256, and the resolution of the images 32 x 32 x 3. We run RMSprop with param- eter a 0.99 and retain exponential moving average of the generator parameters for evaluation with parameter / 0.9999. We remark that RMSprop is an adaptive method that builds on GDA and is commonly used in training for image datasets. It is adopted here to explore the interplay with timescale separation and to determine similar observations emerge compared to our exten- sive experiments with 7-GDA (see Appendix K). The FID scores (Heusel et al. 2017) along the learning path and in numeric form at 150k/300k mini-batch updates for CIFAR- 10 and CelebA with regularization parameters μ = 10 and f = experiments were each repeated with 3 random seeds which yielded similar results and the mean scores reported. The choices of parameter for CIFAR-10 10 and CelebA, respectively. The performance with regularization μ is superior to that with ş 10, which highlights the interplay between timescale separation and regu- larization. Moreover, we see that timescale separation improves convergence until hitting a limiting value. These conclusions agree with the insights from the simple Dirac-GAN experiment. Finally, is worth reiterating there is coupling between and ?1: must be selected so that the continuous- time system is stable and then 71 must chosen so that the discrete-time update is both stable and numerically well-conditioned for the choice of 7.
presented in Figures 2 and B respectively. The
4 and
8 converge fastest with each regularization
6 CONCLUSION
We prove gradient descent-ascent locally converges to critical point for a range of finite learning rate ratios and only if the critical point is a differential Stackelberg equilibrium. This answers a standing open question about the local convergence of first order methods to local minimax equilib- ria. A key component of the proof is the construction of a (tight) finite lower bound on the learning rate ratio for which stability is guaranteed, and hence local asymptotic convergence of 7-GDA.

---

Published as a conference paper at ICLR 2021
REFERENCES
EH Abed, I. Saydy, and AL Tits. Generalized stability of linear singularly perturbed systems includ- ing calculation of maximal parameter range. In Robust Control of Linear Systems and Nonlinear Control, pp. 197-203, Springer, 1990.
Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmann. Local saddle point optimization: A curvature exploitation approach. International Conference on Artificial Intel- ligence and Statistics, pp. 486-495 696,499,220 2019.
John M Alongi and Gail Susan Nelson. Recurrence and lopology, volume 85, American Mathemat- ical Society, 2007.
K. Argyros, A generalization of ostrowski's theorem on fixed points. Applied Mathematics Letters, 12:77-79, 1999.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, pp. 214-223, 2017.
James P. Bailey, Gauthier Gidel, and Georgios Piliouras. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent. In Conference Learning Theory, pp. 391-407, 2020.
D Balduzzi, Racaniere, J Martens, Foerster, K Tuyls, and T Graepel. The mechanics of n-player differentiable games. In International Conference on Machine Learning, volume 80, pp. 363-372, 2018.
Tamer Başar and Geert Jan Olsder. Dynamic noncooperative game theory. SIAM, 1998.
Michel Benaim. A Dynamical System Approach Stochastic Approximations. SIAM Journal on Control and Optimization, 34(2):437-472, 1996.
Hugo Berard, Gauthier Gidel, Amjad Almahairi, Pascal Vincent, and Simon Lacoste-Julien A Closer Look at the Optimization Landscapes of Generative Adversarial Networks. Interna- fional Conference on Learning Representations, 2020.
Vivek Borkar. Stochastic Approximation: A Dynamical Systems Approach. Springer, 2008
Benjamin Chasnov, Lillian J. Ratliff, Eric Mazumdar, and Samuel A. Burden. Convergence anal- ysis of gradient-based learning in continuous games. Conference on Uncertainty in Artificial Intelligence, 2019.
Ashish Cherukuri, Bahman Gharesifard, and Jorge Cortes. Saddle-point dynamics: conditions for asymptotic stability of saddle points. SIAM Journal on Control and Optimization, 55(1):486-511, 2017.
Constantinos Daskalakis and Joannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems, pp. 9236-9246,
2018.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. International Conference on Learning Representationss 2018.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. ACM Symposium on Theory of Computing, 2021.
Farzan Farnia and Asuman Ozdaglar. Do gans always have nash equilibria? International Confer- ence on Machine Learning, 2020.
Tanner Fiez, Benjamin Chasnov, and Lillian J Ratliff. Implicit learning dynamics in stackelberg games: Equilibria charactcrization, convergence analysis, and empirical study. International Con- ference Machine Learning. 2020.
Jakob Foerster, Richard Y Chen. Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-learingg awareness. In International Conference on Au- tonomous Agents and MultiAgent Systems, pp. 122-130, 2018.
10

---

Published as a conference paper at ICLR 2021
Gauthier Gidel, Hugo Berard, Gačtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A varia- tional inequality perspective on generative adversarial networks. International Conference on Learning Representations, 2019a.
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Si- mon Lacoste-Julien, and Ioannis Mitliagkas. Negative momentum for improved game dynamics. In International Conference on Artificial Intelligence and Statistics, pp. 1802-1811, 2019b. 2019b..
lan Goodfellow. Nips 2016 tutorial:
Generative adversarial networks.
arXiv preprint
arXiv:1701.00100 2016.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Infor- mation Processing Systems, pp. 2672-2680, 2014.
Willy J. F. Govaerts. Numerical Methods for Bifurcations of Dynamical Equilibria. Society for Industrial and Applied Mathematics, 2000.
Joao P Hespanha. Linear Systems Theory. Princeton University Press, 2nd edition, 2018.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge local nash equilibrium. In Advances in Neural Information Processing Systems, pp. 6626-6637, 2017.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning, In Advances in neural information processing systems, pp. 4565 4573, 2016.
Roger Horn and Charles R Johnson. Matrix Analysis. Cambridge University Press, 1985.
Chi Jin, Praneeth Netrapalli, and Michael I Jordan. What is local optimality nonconvex- nonconcave minimax optimization? International Conference on Machine Learning. 2020.
Sameer Kamal. On the convergence, lock-in probability, and sample complexity of stochastic ap- proximation. SIAM Journal on Control and Optimization, 48(8):5178-5)) -192, 2010.
Hassan Khalil. Nonlinear Systems. Prentice Hall, 3rd edition, 2002.
AI Klimushchev and NN Krasovskii. Uniform asymptotic stability of systems of differential equa- tions with small parameter the derivative terms. Journal of Applied Mathematics and me- chanics, 25(4): ((44):00110 1-1025, 1961.
P. Kokotovic. A Riccati equation for block-diagonalizatin of ill-conditioned systems. IEEE Trans- actions on Automatic Control, 20(6):12--144 1975.
Peter V Kokotovic, John O Reilly, and Hassan K Khalil. Singular Perturbation Methods Control: Analysis and Design. Academic Press, Inc., 1986.
NN Krasovskii. Stability of Motion: Application of Lyapunov's Second Method to Differential Systems and Equations with Time-Delay, 1963.
PA Lagerstrom and RG Casten. Basic concepts underlying singular perturbation techniques. Siam Review,
1972.
Peter Lancaster and Miron Tismenetsky. The theory matrices: with applications. Elsevier, 1985.
Alistair Letcher, David Balduzzi, Sébastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. Differentiable game mechanics. Journal of Machine Learning Research, 20: 14-1,00194
Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, and Shimon Whiteson. Stable opponent shaping in differentiable games. International Conference Learning Representations, 2019b.
Tianyi Lin, Chi Jin, Michael Jordan, et al. Near-optimal algorithms for minimax optimization. Conference Learning Theory, 2020a.

---

Published as a conference paper at ICLR 2021
Tianyi Lin, Chi Jin, and Michael I Jordan. On gradient descent ascent for nonconvex--oneave minimax problems. International Conference on Machine Learning, 2020b.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters' by implicit differentiation. In International Conference on Artificial Intelligence and Statistics, pp. 1540-1552, 2020.
Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive ap- proximation one-sided non-convex min-max problems: algorithms and applications. IEEE Transactions Signal Processing, 2020.
Matthew MacKay, Paul Vicol, Jon Lorraine, David Duvenaud, and Roger Grosse. Self-tuning net- works: Bilevel optimization of hyperparameters using structured best-response functions. Inter- national Conference on Learning Representations, 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Jan Magnus. Linear Structures. Griffin, 1988.
E. Mazumdar and L. J. Ratliff. Local Nash Equilibria are Isolated, Strict Local Nash Equilibria in "Almost All' Zero-Sum Continuous Games. In IEEE Conference on Decision and Control, pp- 6899-6904, 2019.
Eric Mazumdar, Lillian J Ratliff, and S Shankar Sastry. On Gradient-Based Learning in Continuous Games. SIAM Journal on Mathematics of Data Science, 2(1):103-131, 2020.
Eric V Mazumdar, Michael Jordan, and Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. arXiv preprint arXiv: (eX1v0:901.0088: 000088 2019.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Shuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In International Conference on Learning Representations, 2019.
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of gans. In Advances in Neural Information Processing Systems, pp. 1825-1835, 2017.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for gans do actually converge? In International Conference on Machine learning, pp. 3481-3490, 2018.
Luke Metz, Ben Poole, David Pfau, and Jascha Sohl-Dickstein. Unrolled generative adversarial networks. International Conference on Learning Representations, 2017.
Mustafa and TN Davidson. Generalized integral controllability. IEEE Conference on Decision and Control, volume 1, pp. 898 903.900330 IEEE, 1994.
Vaishnavh Nagarajan and Zico Kolter. Gradient descent gan optimization is locally stable. In Advances in Neural Information Processing Systems, pp. 5585-5599 2017.
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class non-convex min-max games using iterative first order methods. In Advances in Neural Information Processing Systems, pp. 14934-14942, 2019.
J. M. Ortega and W. C. Rheinboldt. Iterative Solutions Nonlinear Equations in Several Variables. Academic Press, 1970.
Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first-order nash equilibria in nonconvex-coneave smooth min-max problems. arXiv preprint urXiv:2002.07919, 2020.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization:
Provable algorithms and applications in machine learning. arXiv preprint arX1v:1810.02060, 2018.
12

---

Published as a conference paper at ICLR 2021
Aravind Rajeswaran, Igor Mordatch, and Vikash Kumar. A game theoretic framework for model based reinforcement learning. International Conference on Machine Learning, 2020.
L. J. Ratliff, S. A. Burden, and S. S. Sastry, Characterization and computation of local Nash equi- libria in continuous games. In Allerton Conference on Communication, Control, and Computing. pp. 917-924, 2013.
L. J. Ratifff, S. A. Burden, and S. S. Sastry. Genericity and structural stability of non-degenerate differential Nash equilibria. In American Control Conference, pp. 3990-3995, 2014.
Lillian J Ratliff, Samuel A Burden, and S Shankar Sastry. On the characterization of local Nash equilibria in continuous games. IEEE Transactions on Automatic Control, 61(8):3301-2077, 2016.
Kevin Roth, Aurelien Lucchi, Sebastian Nowozin, and Thomas Hofmann. Stabilizing training of generative adversarial networks through regularization. In Advances Neural Information Pro- cessing Systems, pp.
2017.
Shankar Sastry. Nonlinear Systems Theory. Springer-Verte Verlag, 1999.
Shankar Sastry and C Desoer. Jump behavior of circuits and systems. IEEE Transactions on Circuits and Systems, 28(12):1109-1122 1981.
Lahcen Saydy. New stabilityyperffrmmncee results for singularly perturbed systems, Automatica, 32 (6):807 818, 1996.
Lahcen Saydy, André L Tits, and Eyad H Abed. Guardian maps and the generalized stability of parametrized families matrices and polynomials. Mathematics of Control, Signals and Systems, 3(4):345-371, 1990.
Florian Schäfer and Anima Anandkumar. Competitive gradient descent. In Advances in Neural Information Processing Systems, pp. 7625-7635, 2019.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with
principled adversarial training. International Conference on Learning Representations, 2018.
Gerald Teschl. Ordinary differential equations and dynamical systems. Graduate Studies in Mathe- matics, 140:08854-8019, 2000.
Gugan Thoppe and Vivek Borkar. A concentration bound stochastic approximation via alekseev's formula. Stochastic Systems, 91)::122,, 2019.
Christiane Tretter. Spectral theory of block operator matrices and applications. World Scientific, 2008.
Emmanouil- Vasileiis Vlatakis Vlatakis-GKaragee Gkaragkounis, Lampros Flokas, and Georgios Piliouras. Poincaré recurrence, cycles and spurious equilibria in gradient-descent-assell for non-convex non-concave zero-sum games. In Advances in Neural Information Processing Systems, pp. 10450-10461, 2019.
Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A follow-the-ridge approach. International Conference on Learning Representations, 2020.
Yasin Yazici, Chuan-Sheng Foo, Stefan Winkler, Kim-Hui Yap, Georgios Piliouras, and Vijay Chan- drasekhar. The unusual effectiveness of averaging in gan training. International Conference on Learning Representations, 2019.
Chongjie Zhang and Victor Lesser. Multi-agent learning with policy prediction. In AAAI Confer- ence on Artificial Intelligence, volume 3, pp. 8, 2010.
Guojun Zhang and Yaoliang Yu. Convergence of gradient methods on bilinear zero-sum games. In International Conference on Learning Representations, 2020.
Guojun Zhang, Pascal Poupart, and Yaoliang Yu. Optimality and stability in non-convex-non- concave min-max optimization. arXiv preprint a1Xiv=2002.11885, 2020a.
13

---

Published as a conference paper at ICLR 2021
Guojun Zhang, Kaiwen Wu, Pascal Poupart, and Yaoliang Yu. Newton-type methods for minimax optimization. arXiv preprint arXiv:2006. 2020b.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. arXiv preprint 1rX1v:1911.10655, 2019.
14

---

Published as a conference paper at ICLR 2021
APPENDIX
Below we provide table of contents as guide to the appendix.
TABLE OF CONTENTS
Related Work
16
Section A contains an extensive discussion of related work at the intersection of machine learning and game theory as well historical connections control theory and dynamical systems.
B Mathematical and Game Theoretic Preliminaries
20
Section B includes mathematical and game theoretic preliminaries not covered in the main text and it contains proofs of short technical helper lemmas.
C Proof of Theorem 1; Stability of T-GDA
24
Section C contains the proof of our main stability result: a critical point of the continuous time dynamical system á = -A) is stable for range of r if and only if x" is differential Stackel- berg equilibrium. Moreover this range of timescale separation parameters is characterized.
D Proof of Theorem 2; Instability T-GDA
29
Section containns the proof of our second main result on the existence of finite range of values of such that non-equilibrium critical points which are stable for some т, become unstable for all in a range of r's lower bounded by finite value.
Proof of Theoremm3) Stability of r-GDA in Regularized GANS
30
Section E contains the proof of Theorem which is application of the main results to the impor- tant adversarial learning application of training generative adversarial networks. Within the section, also provide necessary conditions the sizes of the network architectures for the discriminator and generator network for stability.
Proof of Helper Lemmas and Theorem 4 for T-GDA Convergence
32
Section F contains the statement and proofs of two core technical lemmas on the convergence rate of T-GDA. We then show how to invoke them together with the stability results to obtain Theorem
Proof of Corollary 1; Finite Time Convergence of T-GDA
35
Section G contains the proof of finite time convergence guarantee on achieving an E-diffcrential Stackelberg equilibrium, including an estimate on the size of the ball and commentary on how to improve that estimate with alternative techniques.
H Convergence of Stochastic GDA with Timescale Separation
35
Section H contains extension of the deterministic convergence guarantees to the stochastic setting in which agents have access only to an unbiased estimator of their gradient. We provide convergence guarantees for 7-GDA in this setting well under the least restrictive, to our knowledge, assumptions on stochastic approximation updates to date.
Stability of co-GD: A singular perturbation approach
38
Section I contains proof of the result for the limiting of 3o. While this result appeared recently in Jin et al. (2020), an analogous result has been known for some time in the theory of singularly perturbed dynamical systems. Since the proof techniques particularly illuminating
15

---

Published as a conference paper at ICLR 2021
and expose set of tools to this community, provide this alternative proof from the singular perturbation theory perspective.
J Further Details on Related Work
42
Section J contains an extended discussion on the related work by Jin et al. (202)). Specifically, we expand on the relationship between Proposition 27 in Jin et al. (020), which provides examples of games such that the stable critical points of T-GDA are not subset of local minmax and vice versa, and our main results. We show that the examples in these results, while illustrative of the fact intended to be shown by the proposition stated, do not conflict with out findings.
K Experiments Supplement
44
Section K contains extended experimental results including applications to illustrative games (such as those examples included in the main body) as well as extended GAN experiments. Our results show that we are able to leverage т and improve training results. These results are promising as they suggest that understanding the relationship between the three key hyperparameters-tinnee separation т, regularization Jı, and exponential moving averaging weight / can improve first order training (and hence, scalable) algorithms.
Alternative Proof of Theorem (a via T" Construction from Theorem
60
In order to highlight the utility of Theorem D along with future directions of obtaining values of T' for structured games, we revisit the proof of Theorem 3 and derive the result directly from the construction. The purpose of this section is to illustrate that the structure of equilibria considered in Theorem 3 can be exploited to obtain the value of r" for the entire class of games using properties of the Kronecker product and sum.
A RELATED WORK
In this section, we provide a review of related work at the intersection machine learning and game theory, as well as connections to dynamical systems theory and control.
A.1 MACHINE LEARNING AND LEARNING IN GAMES
Given the extensive work on the topic of learning in games in machine learning that has gone on over the last several years, we cannot cover all of it and instead focus attention on only the most relevant to this paper. We begin by reviewing solution concepts developed for the class of games under consideration and then discuss some learning dynamics studied in the literature beyond gradient descent-ascent. Following this, we delineate the related work studying gradient descent- ascent in non-come con-convex, non-con non-concave zero-sum games and finish by making note of the literature on bilinear and non-convex, concave zero-sum games.
Solution Concepts. Owing to the numerous applications in machine learning, a significant portion of the modern work on learning in games has focused on the zero-sum formulation with non-convex, non-concave cost functions. Most recently, Daskalakis et al. (2021) tout the importance and signif- icance of this class of games in paper on the complexity of finding equílibria (in particular, in the constrained setting) in such games. Consequently, local solution concepts have been broadly adopted. Compared to the standard game-theoretie notions of equilibrium that characterize player's incentive to deviate given the game and information structure, local equilibrium concepts restrict the deviation search space to a suitable local neighborhood. Following the standard game-theoretic viewpoint, vast number of works in machine learning study the local Nash equilibrium concept and critical points satisfying gradient-basee sufficient conditions for the equilibrium, which are often re- ferred to differential Nash equilibria (Ratiff et al. 2013 2014 Ratliff et al. 20166). Based on the observation that in non-convex, non-comee non-concave zero-sum games the order of play is fundamental in the definition of the game, there has been push toward considering local notions of the Stackelberg equilibrium concept, which is the usual theorttecoetic equilibrium when there is an explicit order of play between players. In the zero-sum formulation, Stackelberg equilibrium are often referred to
16

---

Published as a conference paper at ICLR 2021
as minmax equilibria. Similar to for the Nash equilibrium, gradient-baseee sufficient conditions for local minnax/Stuckellbrrg equilibrium have been given (Fiez et al., 2020; Jin et al.
2020) and
such critical points have been referred to as differential Stackelberg equilibria (Fiez et al. 2020 We
remark that it has been shown that local/differential Nash equilibria are a subset of loca//differential
Stackelberg equilibria (Fiez et al. 2020 Jin al.) 2020). Following past works, we adopt the termi- nology of differential Nash equilibrium and differential Stackelberg equilibrium in this paper as the meaning of strict local Nash equilibrium and strict local minmax/Stackelberg equilibrium, respec- tively. It is also worth mentioning the proximal equilibria proposed by Farnia & Ozdaglar (2020), which we do not consider in this work, that depending on a regularization parameter can interpolate between the local Nash and local Stackelberg equilibrium notions. Finally, Zhang et al. (2020a)
propose a local robust point as an equilibrium definition that contains both local minmax and local maxmin equilibrium and V Vltaakis- Vllaaaaii-Gkarggkannn Gkaragkounis et al. (219)) consider an equilibrium concept in what they deem hidden bilinear games.
Learning Dynamics. Given that the focus of this work is on gradient descent-ascent, we center our coverage of related work on papers analyzing its behavior. Nonetheless, we mention that a sig- nificant number of learning dynamics for zero-sum games have been developed in the past few years, in some cases motivated by the shortcomings of gradient descent-ascent without timescale separa- tion. The methods include optimistic and extra-gradient algorithms (Daskalakis et al.) [018 Gidel jet al., 2019 Mertikopoulos et al. 2019), negative momentum (Gidel et al.) 2019b), gradient adjust- ments (Balduzzi et al. [2018] Letcher et al. 2019 Mescheder et al. 2017). and opponent modeling methods (Foerster et al. [2188] Leteher et al. 2019b] Metz et al.; 2017 Schäter & Anandkumar
2019 Zhang & Lesser 2010), among others. While the aforementioned learning dynamics possess some desirable characteristics, they cannot guarantee that the set of stable critical points coincide with a set of local equilibria for the class of games under consideration. However, there have been a select few learning dynamics proposed that can guarantee the stable critical points coincide with either the set of differential Nash equilibria (Adolphs et al. 2019 Mazumdar et al., 2019) or the set of differential Stackelberg equilibria (Fiez et al.) [0200] Wang et al. 2020;] Zhang et al. (020b) effectively solving the problem of guaranteeing local convergence to only class of local equilibria. However, since each of the algorithms achieving the equilibrium stability guarantee require solving a linear equation in each update step, they are not efficient and can potentially suffer from degenera- cies along the learning path in applications such as generative adversarial networks. These practical shortcomings motivate either proving that existing learning dynamics using only first-order gradi- ent feedback achieve analogous theoretical guarantees or developing novel computationally efficient learning dynamics that can match the theoretical guarantee of interest.
Gradient Descent-Ascent. Gradient descent-ascent has been studied extensively in non-convex, non-concave zero-sum games since it is a natural analogue to gradient descent from optimization, is computationally efficient, and has been shown to be effective in practice for applications of interest when combined with common heuristics. A prevailing approach toward gaining understanding of the convergence characteristies of gradient descent-ascent has been to analyze the local stability around critical points of the continuous time limiting dynamical system. The majority of this work has not considered the impact of timescale separation. Numerous papers have pointed out that the stable critical points of gradient descent-ascent without timescale separation may not be game- theoretically meaningful. In particular, it has been shown that there can exist stable critical points that are not differential Nash equilibrium (Daskalakis & Panageas 2018 Mazumdar et al.) 2020). Furthermore, it known that there can exist stable critical points that are not differential Stackelberg equilibria (Jin et al. 2020). The aforementioned results rule out the possibility that gradient descent- ascent without timescale separation can guarantee equilibrium convergence. In terms of the stability of equilibria, it is known that differential Nash equilibrium are stable for gradient descent-ascent without timescale separation (Daskalakis & Panageas) 2018 Mazumdar et al., 2020), but that there can exist differential Stackelberg equilibria which are not stable with respect to gradient descent- ascent without timescale separation.
The work of Jin et al. (2200) is the most relevant exploring how the aforementioned stability prop- erties of gradient descent-ascent change with timescale separation. In particular, JJin et al. (2020) investigate whether the desirable stability characteristies (stability of differential Nash equilibria) and undesirable stability characteristics (stability of cquuiuuiiir critical points and instability of differential Stackelherg equilibria) of gradient descent without timescale separation are main-
17

---

Published as a conference paper at ICLR 2021
tained and remedied, respectively with timescale separation. In terms of the former query, extending
the examples shown in [Mazumdar et al. (2020) and Daskalakis & Panageas (2018). Jin et al. (2020)
show that differential Nash equilibrium are stable for gradient descent-ascons with any amount of timescale separation.
On the other hand, for the latter query, Jin al. (2020) shows (in Proposition 27) two interesting examples: (a) for an a priori fixed 7, there exists a game with a differential Stackelberg equilibrium that is not stable and (b) for an priori fixed т, there exists a game with a stable critical point that is not differential Stackelberg equilibrium. However, (a) does not imply that for the constructed game, there does not exist another (finite) independdnt of the game parameters such the differ- ential Stackelebrg equilibrium is stable for all larger T. In simple language, the result summarized in (a) says the following: if a bad timescale separation is chosen, then convergence may not be guar- anteed. Similarly, (b) does not imply that there is no such that for all larger for the constructed game instance, the critical point becomes unstable. Again, in simple language, the result summa- rized in (b) says the following: if a bad timescale separation is chosen, then non-game theoretically meaningful equilibria may persist. While at first glance this set of results may appear to indicate that the undesirable stability characteristics of gradient descent without timescale separation cannot be averted by any finite timescale separation, it is important to emphasize that these results do not answer the questions of whether there (a) exists game with a critical point that is not differential Stackelberg equilibrium which is stable with respect to gradient descent-ascent without timescale separation and remains stable for all finite timescale separation ratios or (b) exists game with a differential Stackelberg equilibrium that is not stable for all finite timescale separation ratios. The preceding questions are left open from previous work and are exactly the focus of this paper. In Appendix [ as we believe this to be an important point of distinction between Theorem [ and 2 in this paper.
we go into greater detail on the comparison between Proposition 27 of Jin et al. (2020)
Finally, Jin et al. (2020) study GDA with timescale separation approaching infinity and show that the stable critical points of gradient descent-ascent coincide with the set of differential Stackelberg equilibria in this regime. This result effectively shows that gradient descent-ascent can guarantee only equilibrium convergence with timescale separation, albeit only when it becomes arbitrarily large. We remark that an equivalent result in the context of general singularly perturbed systems has been known in the literature (Kokotovic et al. 1986 Chap. 2) as we discuss further in Section [ Finally, point out that since timescale separation approaching infinity does not result in an implementable algorithm, fully understanding the behavior with a finite timescale separation is of fundamental importance and the motivation for our work.
Beyond the work Jf et al. 2020) considering timescale separation in gradient descent- asccnt,, it is worth mentioning the work of Chasnov et al. (2019) and Heusel et al. (2017). Chasnov et al. (2019) study the impact of timescale separation on gradient descent-ascent, but focus on the convergence rate as a function of it given an initialization around differential Nash equilibrium and do not consider the stability questions examined in this paper. Heusel et al. (017)) study stochastic gradient descent-ascens ascent with timescale separation and invoke the results of Borkar (2008) for analysis. The stochastic approximation results the claims rely on guarantee the convergence of the system locally to stable critical point. Consequently, the claim of convergence to differential Nash equílibria of stochastic gradient descent-ascent given by Heusel et al. (2017) only holds given an initialization in a local neighborhood around a differential Nash equilibrium. In this regard, the issue of the local stability of the types of critical point is effectively assumed away and not considered. In contrast, we are able to combine our stability results for gradient descent-ascent with timescale separation together with the stochastic approximation theory of [Brkar (2008) to guarantee local convergence to a differential Stackelberg equilibrium in Section H We remark that Heusel et al.) (0117) empirically demonstrate that timescale separation can significantly improve the performance of gradient descent-ascent when training generative adversarial networks.
The final relevant line of work studying gradient descent-ascent is specific to generative adversarial networks. The results from this literature develop assumptions relevant to generative adversarial networks and then analyze the stability and convergence properties of gradient descent-ascent un- der them (see, e.g., works by Daskalakis et al. (2018); Goodffllow et al. (2014): Mescheder et al. (2088;: Metz et al.] (2017): Nagarajan & Kolter (2017). Within this body of work, there has been significant amount of effort focusing on how the stability (and, hence, convergence properties) of gradient descent-ascent in generative adversarial networks can be enhanced with regularization methods. Nagarajan & Kolter 2017) show, under suitable assumptions, that gradient- brasdd methods
18

---

Published as a conference paper at ICLR 2021
for training generative adversarial networks are locally convergent assuming the data distributions are absolutely continuous. However, as observed by Mesehheerrr et al. (2018), such assumptions not only may not be satisfied by many practical generative adversarial network training scenarios such as natural images, but it can often be the case that the data distribution is concentrated on a lower dimensional manifold. The latter characteristic leads to nearly purely imaginary eigenvalues and highly ill-condition problems. Mescheder et al. (0188) provide an explanation for observed insta- bilities consequent of the true data distribution being concentrated on a lower dimensional manifold using discriminator gradients orthogonal to the tangent space of the data manifold. Further, the au- thors introduce regularization via gradient penalties that leads to convergence guarantees under less restrictive assumptions than were previously known. In this paper, we further extend these results to show that convergence to differential Stackelberg equilibria is guaranteed under a wide array of hyperparameter configurations (i.e., learning rate ratio and regularization).
Bilinear Games. We would be remiss to not include a discussion of gradient methods applied to an important class of zero-sum games: bilinear games. Bilinear games fall within a mea- sure zero set of C2 games that do not possess the generic properties that at critical points x², det(Dīf(x") )) # O, ) (J(x)) & 0 (see Fiez et al. 2020 for the genericity statements regarding local minmax equilibria in zero-sum games). This means they need special treatment. For zero-sum bilinear unconstrained games, however, the behavior of gradient descent- is already known. In particular, the zero point is always a center type equilibrium of the continuous time dynamics so that the continuous time dynamics are recurrent. A forward Euler discretization of the continuous time dynamics gives gradient descent-ascent and such dynamics will always diverge. The alternat- ing gradient descent update introduced by Bailey et al., (2020) is one solution to this problem such that the behavior of the continuous time dynamics is preserved under the discretization. This method simply uses different discretization scheme that respects the continuous time behavior. We also note that due to the fact that zero-sum bilinear games do not admit equilibria with generic properties, simply introducing regularization can remedy the problem. In particular, the maximizing player's update is modified to include the derivative of - - llvllž then the local minmax (which is not strict) becomes a strict local minmax for the regularized game. In this case, our results do apply.
Nonconvex-Concave Optimization. A final related line of work is on nonconvex-concal opti- mization (Lin et al., 2020a Lu et al., 2020; Nouiehed et al, 2019) Ostrovski et al. 2020 Rañique et al. 2018). The focus in this set of works (among many others the topic) is on characterizing the iteration complexity to stationary points, rather than stability and asymptotic convergence as in the non-convex, non-concave zero-sum game setting. The primary relevance of work this problem is that a number of the algorithms rely on timescale separation and variations of gradient descent- ascent. Moreover, the methods for obtaining fast convergence rates may be relevant to future work attempting to characterize fast rates in the non-convex, non-concave setting after there is a more fundamental understanding of the stability and asymptotic convergence.
A.2 HISTORICAL PERSPECTIVE: DYNAMICAL SYSTEMS AND CONTROI.
The study of gradient descent-ascent dynamics with timescale separation between the minimizing and maximizing players is closely related to that of singularly perturbed dynamical systems (Koko- tovic et al. 1986). Such systems arise in classical control and dynamical systems in the context of physical systems that either have multiple states which evolve on different timescales due to some underlying immutable physical process or property, or a single dynamical system which evolves on sub-manifold of the larger state-space. For example, robot manipulators or end effectors often have have slower mechanical dynamics than electrical dynamics. On the other hand, in electrical circuits or mechanical systems, certain resistor-capaciin circuits or spring- mass systems have a state which evolves subject to a constraint equation (Lagerstrom & Casten 1972 Sastry & Desoer 198T). Due to their prevalence, singularly perturbed systems have been studied extensively with one of the out- comes being a number of works on determining the range of perturbation parameters for which the overall system is stable (Kokotovic et al. 1986, Saydy 1996| Saydy et al. 1990). We exploit these results and analysis techniques to develop novel results for learning in games. One of contributions of this work is the introduction of the algebraic analysis techniques the machine learning and game theory communities. These tools open up new avenues for algorithm synthesis; we comment on potential directions in the concluding discussion section.
19

---

Published as a conference paper at ICLR 2021
This being said, there couple key difference between the present setting and that of the classical literature including the following:
1. The perturbation parameter is no longer immutable characteristic of the physical system, but rather hyperparameter subject to design. Indeed, in singular perturbation theory, the typical dynamical system studied takes the form
i 91 (z. y) cÿ 92(x,y)
where is a small parameter that abstracts some physical characteristics of the state vari- ables. On the other hand, in learning in games, the continuous time limiting dynamical system of gradient descent-ascent for a zero-sum game defined by f E C²(X x Y, takes the form
(7) where the x-player seeks to minimize with respect to x and the y-player seeks max- imize f with respect to y. and 7 is the ratio of learning rates (without loss of generality) of the maximizing to the minimizing player. These learning rates rates-and and hence the value of T-are hyperparameters subject to design in most machine learning and optimization ap- plications. Another feature of (7) as compared (6) is that the dynamies D are partial derivatives of a function f. which leads to the second key difference.
4 == = v) أ = 1==
2. There is structure in the dynamical system that arises from gradient-play which flects the underlying game theoretic interactions between players. This structure can be exploited in obtaining convergence guarantees in machine learning and optimization ap- plications of game theory. For instance, minmax optimization is analogous to a zero sum game for which the local linearization of gradient descent- dynamics has the structure
_
J TB
where AT and C CT and T the learning rate ratio or timescale separation parameter. Such block matrices have very interesting properties. In particular, second order optimality conditions for a minmax equilibrium correspond positive definiteness of the first Schur complement S (J) A BC-1BT 0, and of -C > 0 (Fiez et al. 2020)) This turns out to be keenly important for understanding convergence of gradient descent- ascent. Furthermore, due to the structure of J, tools from the theory of block operators (see, e.g., works Lancaster & Tismenetsky (1985); Magnus ( [1988); Tretter (2008) such the quadratic numerical range can be exploited (and combined with singular perturbation theory) to understand the effects of hyperparameters such as 7 (the learning rate ratio) and regularization (which is common in applications such as generative adversarial networks) on convergence.
B MATHEMATICAL AND GAME THEORETIC PRELIMINARIES
In this appendix section, we review mathematical and game theoretic preliminaries needed for the technical details of the proofs. We also include some short technical lemmas from algebra that are used in the proofs.
B. GAME THEORY
We now formally present the local equilibrium definitions (see Başar & Olsder 1998) that we char- acterize in the main body by gradient-bases based sufficient conditions as is typical in the literature.
Definition B.1 (Local Nash Equilibrium).
X is a local Nash equilibrium on ThEE U, C X, where U; S X,, if f2) S faa,, ( 22), for all x E Un C X2 and f*11 Z (11, 22)) for all zl2 E U2 C X2. Furthermore, if the inequalities are strict, we say x is a strict local Nash equilibrium.
The joint strategy
Definition B.2 (Local Stackelberg Equilibrium). Consider U, C X 1,2 where, without loss of generality, player I is the leuder (minimizing player) and player is the follower (maximizing player). The strategy xt Un is local Stackelberg solution for the leader if. Van E U,,
SUPz2eru, (wi) [0 222 S sup sup22Eru, (21) I (21,
20

---

Published as a conference paper at ICLR 2021
where ru, = Ey E U2lf(21,9) 2 f(x1, Va2 U2] } is the reaction curve. Moreover, for any zá E TU,(2]) the joint strategy profile (2q,2)) E U1 x U2 is a local Stackelberg equilibrium on U1 x Uz-
While characterizing existence of equilibria is outside the scope of this work, we remark that Nash equilibria exist for convex costs on compact and convex strategy spaces and Stackelberg equilibria exist on compact strategy spaces (Başar& & Olsder, 1998] Thm. 4.3, Thm. 4.8, & Sec. 4.9). Exis- tence of local equilibria is guaranteed the neighborhoods and cost functions restricted to those neighborhoods satisfy the assumptions of the cited results. The differential characterization of local Nash equilibria in continuous games was first reported in (Ratliff et al. 2013). Genericity and struc- tural stability studied in general-sum settings in (Ratlift al.) (014)) and in zero-sum settings in (Mazumdar & Ratlifi 2019). Fiez et al. (2020); Jin et al. (2020) present sufficient conditions for a local Stackelberg equilibrii and Fiez al. (2020) studied the genericity and structural stability.
B.2 DYNAMICAL SYSTEMS THEORY
Recall the following equivalent characterizations of stability for an equilibrium of i = -9(x) in terms of the Jacobian matrix ((x) = Dg(x).
Theorem B.1 (Theorem 4.15, Khalil 2002). Consider a critical point x² of g(x)) The follow-
ing are equivalent: (a) x² is locally exponentially stable equilibrium of it =((x); (b)
speo(-J(x")) C C2; (c) there exists symmetric positive-defune matrix PT such
that PJ(x')+ J(x)TP>>0.
Leveraging Linearization Infer Qualitative Properties. The Hartman-Grobmann theorem as- serts that it is possible to continuously deform all trajectories of nonlinear system onto trajectories of the linearization at fixed point of the nonlinear system. Informally, the theorem states that if the linearization of the nonlinear dynamical system Æ = Fzz) around a fixed point v- ø-i.e., F(z) 0- has no zero or purely imaginary eigenvalues, then there exists a neighborhood U of and home- omorphism h U + i.... h, h E CUU, ) -aking trajectories of à F(x) and mapping them onto those of 1 = F()) In particular, h(z) = O.
Given dynamical system _ F(x), the state solution of the system at time starting from time to is called the flow and is denoted (x)).
Theorem B.2 (Hartman- (Hartman-Grobman: Theorem 7.3, Sastry 1999. Theorem 9.9, Teschl 2000). Con- sider the n-dimensional dynamical system à = F(x) with equilibrium point x. If DF has no zero or purely imaginary eigenvalues, there homeomorphism h defined on a neighborhood U of ā taking orbits of the flow o' those of the linear flow eD(()) of ā = F(x) is, the flows are topologically conjugate, The homeonorphism preserves the sense of the orbits and is chosen to preserve parameterization by time.
The above theorem says that the qualitative properties of the nonlinear system 1 = F(z) in the vicinity (which is determined by the neighborhood U)) of an isolated equilibrium z are determined by its linearization if the linearization has no eigenvalues on the imaginary axes in the complex plane. We also remark that Hartman-Grobman can also be applied to discrete time maps (Sastry) 1999
Thm. 2818) with the same qualitative outcome.
Limiting dynamical systems and connections to singular perturbation theory. The continu- ous time dynamical system takes the form ; -A) due to the timescale separation т. Such system is known as a singularly perturbed system or a multi-timescale system in the dynamical sys- tems theory literature (Kokotovic et al. 1986). particularly where - is small. Singularly perturbed systems are classically expressed as
- (z,,) ei (D,
i
(8)
where e = -- is most often a physically meaningful quantity inherent to some dynamical system that describes the evolution of some physical phenomena; e.g., in circuits it may be a constant related to device material properties, and in communication networks, it is often the speed at which data flows through physical medium such cable. This brings up one key point of separation in
21

---

Published as a conference paper at ICLR 2021
applying dynamical systems theory the study of algorithms versus physical system dynamics: is no longer necessarily a physical quantity but is most often hhper-parametee subject to design.
Internally Chain Transitivity. In proving results for stochastic gradient descent-ascent, we lever- age what is known as the ordinary differential equation method in which the flow of the limiting continuous time system starting sample points from the stochastic updates of the players actions is compared to asymptotic To understand stability in the stochastic case, we need the notion of internally chain transitive sets. For more detail, the reader is referred to (Alongi & Nelson 2007 Chap. 2-3).
trredo--rjjetooiiss- i.e., linear interpolations between sample points.
closed set C TR is an invariant set for differential equation & F(x)) any trajectory s<t)) with (0) E U satisfies xtt) E U for all t E IR. Let ø² be a flow on metric space (X, d). Given E > O, T > and x, E X, an (s, -cchain from æ to y with respect to of and d is a pair of finite sequences I To. 21, ................................ Zk- 1, TA y in X and .......,--.. in [T,, oo), denoted together to: 11) such that d( (zt), T++1) < for = 0, 2......... ., 1. A set U S X is (internally) chain transitive with respect to Ø² if U is non-empty closed invariant set with respect to o' such that for each z E U. > 0 and T > 0 there exists an (E, -chaiin from y- A compact invariant set U is invariantly connected if it cannot be decomposed into two disjoint closed nonempty invariant sets. It is easy to see that every internally chain transitive set is invariantly connected.
by (mg, 21.... 1.
B.3 TOOLS FOR CONVERGENCE ANALYSIS
The following proposition is a well-known result in numerical analysis and can be found in number of books and papers on the subject. Essentially, provides an asymptotic convergence guarantee for discrete time update process dynamical system.
Proposition B.1 (Ostrowski's Theorem Argyros 1999 Theorem 10.1.2, Ortega & Rheinboldt 1970). Let x" be a fixed point for the discrete dynamical system Ig+1 F(*x). If the spectral radius of the Jacobian satisfies p(DF(x*)) < 1, then F is a contraction at x² and hence, x² is asymptotically stable.
We analyze the iteration complexity local asymptotic rate of convergence of learning rules of the form T = h(xx) in the neighborhood of an equilibrium. Given two real valued functions such that [F()) S (k)( For example, consider iterates generated by 2s+1 = h(Tx) with initial condition To and critical point x², Then, if F(k) = ||xx+1 I'll < M Io 2=1 ||. we write F(k) (
F(k) and G(k), we write F(k) O(G(k)) if there exists positive constant
where e = -00 x
B.4 NUMERICAL AND QUADRATIC NUMERICAL RANGE.
The numerical range and quadratic numerical range a block operator matrix are particularly use- ful for proving results about the spectrum of block operator matrix they are supersets of the spectrum Tretter 2008). Given a matrix A E _ the numerical range is defined by
W(A) {a E C (Az, 2), ||=|| =1},
and is a convex subset of C. Define spaces W; = {= E CR |||||| 1) for each i E (1,2).
Consider block operator
A Ag1
A1
A=
A2
where Ass E R and Agg E Rn.xn for each i,j E (1,2). Given v W1 and w W2, let A0, E 22x2 be defined by
(A1u,,)) ot (Arr w)
(Azu u) (Azww, w))
A P.
The quadratic numerical range of defined by
(+)))
U
spec(A500)
vEWL.EW
22

---

Published as a conference paper at ICLR 2021
where spec(-) denotes the spectrum of its argument.
The quadratic numerical range can be described as the set of solutions of the characteristic polyno- mial
X X((A11U, v) + (Azzw, w)) + (A119, u) (A22w, w) (A12u, w> (A21 u; v)
(9)
for U E W1 and w E W2. We use the notation (Av, w) = T Aw to denote the inner product. Note that (AA) is (potentially non-convex) subset of ((A) and contains spec(A).
B.5 TECHNICAL LEMMAS
In this appendix, we present handful of technical lemmas and review some additional mathematical preliminaries excluded from the main body but which are important in proving the results in the paper.
The following technical lemma is used in proving an upper bound on the spectral radius of the linearization of the discrete time update 7-GDA requirement for obtaining the convergence rate results.
Lemma B.1. The function c(z) (1 211-2)1/22 1/2 +
1- satisfies c(z) for all [0, 1].
Proof. Since c(0) and c(1) to get that e(z) is a decreasing function on [0, 1]. and hence negative on [0, 1]. Indeed, c'(z)
1 S 0, we simply need to show that dz) S on (0,1) v2
2v1-; < 0 since (1 - 2 (4 22) 2 1/2 for all (0, 1).
2
The following technical lemma, due Mustata & Davidson (1994), is used in constructing the finite learning rate ratio.
Lemma B.2 (Lemma 15, Mustafa Davidson 1994.. Let V, E Rexp, W E Rx and Y Rox0 V and Y - XV- W are non-singular then
V X
W Y
det
For completeness (and because there is typo in the original manuscript), we provide the proof here.
Proof. Suppose that V and Y - XV 'y W are non non-singular so that the partial Schur decomposition
V
W
V
0
v-iW
X
Y
X
Y - XV
1
holds, and
(x
W
det
Y
(o)(V))et()) - XV-
(10)
Further,
V
W
I
v-l
V-1 -V -V-- (Y - XV XV-VV-- >
X
I
Applying the determinant operator, we have that
([
(V
V
Z
W y
det (xx
W ) det
109
T
0
V
W
()
det
7
+
X
Y
(II)
so that
[ I
100+0
0
V
W
Z 0
det
10++
1
+
0
WY -WWVY-XV-WW---- 1)2 + I).
(12)
Combining 10) with 12 in
gives exactly the claimed result.
23

---

Published as a conference paper at ICLR 2021
Chap. 13.1). We this lemma several times in the proofs of Theorem and 2 so we include it here for ease of reference. For given matrix A. u4 (A), w- (A), and ((A) are the number of eigenvalues of the argument that have positive, negative and zero real parts, respectively.
The following lemma is Theorem 2 Lancaster & Tismenetsky 1985
Lemma B.3. Consider a matrix A R=x*
(a) If P is symmetric matrix such that AP + PAT = Q where Q = Q > 0, then P is nonsingular and and have the same inertia, meaning that
(A(A) (P), v- =A)= 5(A) ((P)-
(13)
(b) On the other hand, if ((A) O, then there exists matrix P PT and matrix Q
Q' > 0 such that AP + PA Q and P and A have the same inertia ((13) holds).
C PROOF OF THEOREM STABILITY OF T-GDA
To prove Theorem T and Corollary we introduce some techniques that are arguably new to the machine learning and artificial inte intelligence communities. The first the notion of guard map. A guard map can be used to provide a certificate of particular behavior for dynamical system parameter(s) varies. A critical point of a dynamical systems is known to be stable if the spectrum of the Jacobian at the critical point lies in the open left-half complex plane, denoted C2. Hence, construct a guard map as a function of r and show that it guards C Specifically we show that the existence of 7* (0, oc) such that v(r*) 0 and v(T) * 0 for all (r", oo) is equivalent to (i([(x)) > 0 and - D
[xx"()) (xx)) > O where
{i({(z)) = Si (J, Dif(=)) Diaf(=")( D2if((x")
Towards this end, we need to introduced some notation as well as formal definitions for important concepts such as the guard map.
C.I NOTATION AND PRELIMINARIES
Given matrix A E R. X let (A) T be the vectorization of A. We the convention that rows are transposed and stacked order. That is,
a1
Q1
On1
Let 69 and ( denote the Kronecker product and Kronecker sum respectively. Recall that A @ A ( T + T B. A less common operator, we define Hll as an operator that generates an jn(n + 1) x
nn(n 1) matrix from matrix A p such that
A f A (A A)H,
where H = (H, H. is the (left) inverre of Hn, a full column rank duplication matrix. A duplication matrix Hn xR²xxm(+11/2 is clever linear algebra tool for mapping 2 1n++1) vector to n vector generated by applying veo(-) to symmetric matrix and is designed to respect the vectorization map vec(.). In particular, if vech(X) is the veff-vectorizattio map of
any symmetric matrix X R then veo(X) = vech( and vech(X) = H1 vec(X).
Given square matrix A, let (A)x(( (A) be the largest positive real eigenvalue of A and if A does not have a positive real eigenvalue then zero.
Guardian maps. The of guardian maps for studying stability of parameterized families of dynamical systems was arguably introduced by (aydy et al. (1990). Guardian or guard maps act as certificate for performance criteria such as stability.
Formally. let X' be the set of all n x n real matrices or the set all polynomials of degree n with real coefficients. Consider S open subset of X' with closure S and boundary as.
24

---

Published as a conference paper at ICLR 2021
Definition C.1. The map X - C is said to be guardian map for S if for all S, v(x) 0 + x E äs
Consider open subset Ω of the complex plane that is symmetric with respect to the real axis. Then, elements of S(2) = {A E Raxx; spec(A) C [} are said to be stable relative to S2.
The following result gives a necessary and sufficient condition for stability of parameterized families of matrices relative to some open subset of the complex plane.
Proposition C.1 (Proposition 1 (Saydy al. to be a pathwise connected subset of R and (T) E R a matrix which depends continuously on Let S(It) be guarded by the map The family {A(T) T U} is stable relative to D if and
1990); Theorem 2 (Abed et al. 1990)). Consider U
only if (i) it is nominally stable stabl-mmanning meaning A(Ti) E S(2) for some T1 E U a-d (ii) v(A(T) #
for all 7 E U.
In proving Theorem ! is denoted by S(C2).
we define a guard map for the space of n x n Hurwitz stable matrices which
Lemma C.I. The map u: ++ det(A B A) guards the set of non-singular n X n Hurwitz stable matrices S(C)).
Proof. This follows from the following observation: for A E Rax".
vech(AX + XAT)= HH vec(AX XAT) -H (A @ A)vec(X)= H @ vech))) from which it can be shown that the eigenvalues of A + A are d; + by for S S is n where X; for = 1,..., n are the eigenvalues of A.
Indeed, let S be non-singular matrix such that S-1AS = M where M is upper triangular with on its diagonal. Observe that for any n x n matrix P. H, H (P H)H, (P& H) and H1 (P H H, (P & P). Hence, using properties of the Kronecker product (namely, that (A1 @ (1, & B₂) = (A, B1 @ AzB))), we have that
Xy A1,...,
H HS @ S HH,, (1 @ A + A H,, (S @ S)H,, =
so that the spectrum of H. (I @ A A H)H, and H. (I & M M & I)H, coincide. Now, since M M & I)H, is upper triangular with diagonal elements A, + X3 (1 ز S < n) which can be verified by direct computation and using the definition of Hn. This implies that \ + X, (1 S j S n) are exactly the eigenvalues of H (I 8 A + A H)H,.
M is upper triangular, H (I
We note that there are several other guard maps for the space of Hurwtiz stable matrices including
v : A + dct(A @ A). To give some intuition for this map. it is fairly straightforward to see that the Kronecker sum A ④ A A @ I + I 8 A has spectrum {Λ₃ + Ax} where di X; spec(A). The operator A I A is simply a more computationally efficient expression of A @ A, and as such the eigenvalues of A E A are those of A A removing redundancies. We use A E A specifically because of its computational advantages in computing T"
C.2 PROOF OF THEOREM 1
We first prove that if x² is a differential Stackelberg equilibrium (that is. (1(J+(z*) > and - DD (x=) 0), then there exists finite 7" E (0, oo) such that for all 7 E (T", 00), x. is locally exponentially stable for
(a) (that is, spec(-J-(x")) C C2) Towards this end, we construct guard map for the space of n x Hurwtiz stable matrices and explicitly construct the r" using it.
Then we prove the other direction. That is, if there exists finite T" E oo) such that for all т E (7", oo), x² is exponentially stable for = -Agg(x), then x² is a differential Stackelberg equilibrium. We prove this by contradiction.
C.2.1 PROOF THAT IF x= IS A DIFFERENTIAL STACKELBERG THEN FINITE T EXISTS
For a critical point x², let
(D}f(xx* -Dief(z*) (x*=)(**) fD²)(x*)
An
A12
-J+("") =
-TAT
T
25

---

Published as a conference paper at ICLR 2021
and define
S =)=s(()J((=)) = An - -112A2 A
Note that this is equívalent to the first Schur complement of -J(=") (i.e., when T = 1) since the T and -- cancel, and by assumption the first Schur complement (x is positive definite. Suppose that x" is differential Stackelberg equilibrium so that -1 > 0 and -A2 > 0.
Polynomial guard map with family of matrices parameterized by By Lemma C.I V: A - (et((AAA))) a guard map for S(C2), Indeed, using the fact that the determinant the product the eigenvalues of a matrix and the fact that A))c(AAAA) = {,++ 1 sisj n, Ar, E spec((A)) we have that
det (et(AAA)
II Isisin
(1+
2Re(A) (Av) + 4lm)(A)) 1885
II
II (g+
ActtAs
Hence, consider S(C2), (et(AAA)) if and only if AAW A is singular if and only if A has purely imaginary cigenvalue-thee that is, if and only if A E ) Now, consider the parameterized family of matrices - J- (x*), parameterized by т. By an abuse of notation, let v(T) = J- (x=) m (x,""") )). If we consider the subset of this family of matrices that lies in S(C2) (this subset could priori be empty thought we show it is not), then for any such that -J, (z*) ) is in this subset, we have that v(T) 0 and only if -xx") H (xx)(x))) is singular if and only if (1,,,(x")
aS(C2).
Hence, v(T)
[+ B J+((x") guards S(C2).
In particular, if we envision "ovision-J(11""" (x*) as the input v : A + det E A) and simply vary (holding all the entries of -J (x)) otherwise fixed), then 1/ T + det(-J,(x") E (=J+(x") ))) can be thought of simply as a function
which guards the set of Hurwitz stable matrices via the reasoning describe above. Indeed, by slightly overloading the notation for v,
((T) == vn VIT ... 17-17 + Upp v(-J+(x"))
Hence, for intuition, observe that as decreases (towards zero) stability is first lost when at least one eigenvalue of J, (x*) reaches the imaginary axis, which point v(T) 0.
There are two cases to consider:
Case 1: v(T) is identically zero polynomial. In this case, (x*) is in the interior of the complement of the set of Hurwitz stable matrices for all values of t > 0-that is, -J+(=") int(S*(CL)) for all 7 R. oo).
Case 2: u(T) is not an identically zemo polynomial. In this case, v(T) has finitely many zeros.
u((T) has no positive real roots, then as varies in R,, -="xx) does not cross AS(C2- i.e., the boundary of the space of n x n Hurwitz stable matrices. Hence, {-Jz(x*)
E } C iCt() It suffices to check -++(x*) E (C2 or -z-((x** E int((S(C2)) for an arbitrary 7 E R..
T E ] C (²CC) or (=))(x")
On the other hand, if (T) has f > 1 real positive zeros, say 0 <<< TI <T..TTTT: then by Proposition C.I (=") E S(C2) for all > 7" if and only if ---((x") E S(C2) for arbitrarily chosen т > r" We choose the largest positive root because we are guaranteed that v(T) stops changing sign for 7 > -*. Further, the largest neighborhood in R for which -J- (x*) E S(C2) is 00).
Recall that have assumed that x= is differential Stackelberg equilibrium (that is, S1 0 and -A > 0). We will show next (by way of explicit construction of 7*) that we are always in case 2.
Construction of. We note that there are more elegant, simpler constructions, but to our knowl- edge this construction gives the tightest bound on the range of for which J (x*) is guarnateed to be Hurwitz stable. Recall that
(x") -Dif(()* -Dief(x*)
An
Ay
(DT)((>) TDzs(x*)
-TA
TA2
Indeed, this holds since the only scenarios in which det R A) = 0 are such that the eigenvalues of A do not lie in S(C_).
26

---

Published as a conference paper at ICLR 2021
and
A - A12 4
Let Im denote the m x m identity matrix for some m.
Claim C.1. The finite learning rate ratio T Max (Q) where
Ag H (Aj2 @ Lnz)
Q 2 [(A12 @ A22) (In, @ Agg A Hml
(A11 @ A
ST H (Si @ A12
(14)
with A22 A2 W A22 and S1 S H St.
Proof. Recall that U(T) = (- M (-J+()))) is a guard map for S(C2).
We apply basic properties of the Kronecker product and sum as well Schur's determinant formula to obtain a reduced form of the guard map. To this end, we have that
Au W Au T(n, @ (-AT2)) H
2H (4n, @ A12) An @ T
0
-x(x') B (-J+(==))
(A12 @ Inz H
H ( (-A @ 1n
T(A22 EB A22)
m2
Now, we apply Schur's determinant formula to get that
v(r) -0= det (A22 Ea A22) det (1r(to)
An R An
2 mi (Jn, A12)
(15)
@ (-A
An @ T + Mi
where
M1 = -HH (-A @ (A2e E A22) -1 (A12 & Inz H
From here, apply Lemma [B.2 to further reduce the guard map. First, note that
An A22 Au @ Lng + In TA22.
Let V = Ing 8 T A22, Z An @ In2 + M1, Y An E An, W - @ ( and
X = =HHH 2HH @ A12). Using the two properties of the Kronecker product (B1 @ (2) & B,) =
(B,By Ba) and (B1 @ B2)-1 (BT* < ), have that
Y - XV- W = An 0 An + +H (Im @ AIn) @ A22) @ AT2)!ln
(16)
An = An +H (In, A12422 )
(17)
-An An H ((In & A12 AT2) + (A12A A @ Ln, H)
(18)
= S S
(19)
where 18) holds since H (Ln, & A12 AT2 = H (A12 A72 x Ln, Mn, Now, define
V-1 V--VW - XV XV--W)-1 W)
-V - - where
M2 = In, 8 Ap 2(h, 2 A Hn, (S1 = S1) HT (Ln, @ A12472)
so that applying Lemma B.2 we have
v(T) - 1)/2 det (22)
(I,, Am2) (et Blng + +M)
(20)
The assumptions that S and AA2 together imply that det E S1) # and det &
A22) * 0. Hence, =(T)= = 0 if and only if det(rIn,mz + (211 @ In, + M1)) = 0 since
< < co. The determinant expression is exactly an eigenvalue problem.
Since by assumption the Schur complement of J(x")) and the individual Hessian - are positive definite (that is, x² a differential Stackelberg equilibrium). Thus, the largest positive real root of v(T) = 0 is
-'= A (2 @ Ing + Mi))
where X+ A (.) is the largest positive real eigenvalue of its argument if one exists and otherwise its zero. Using properties of the Kronecker product and duplication matrices, it can easily be seen that Q, as defined in [4). is equivalent to -M2(A1 X Ing M1).
The result of this claim concludes the proof that if xx is a differential Stackelberg, then there exists finite -" [0, oo) such that for all E (7", 2o), spec(- - (xx)) C2.
27

---

Published as a conference paper at ICLR 2021
C.2.2 PROOF THAT EXISTENCE OF FINITE T" IMPLIES THAT X" DIFFERENTIAL STACKELBERG
To begin, consider a critical point x¹ such that g(x*) = 0 and (et((()())) A 0. Then, det( det(-J((x")) nn2 f det(-S((((x"))) so that det(-J,(z") 0 if and only
if det( det(-S)(J((")) = 0 which implies (J=(2") is unstable for all T E (0, when
(J(("))(
As result, we are left to consider when (st(s) # for the
remainder of the proof.
We proceed by arguing a contradiction. - (zef(=") ( (x") have no zero eigenvalues that is, det(Si) # 0 and det(C)) +
(D3 -
and S (J((²))) = Dff(x*)
Suppose that there exists a T* E (0, oo) such that for all 7 E (7", 00), spec(-J+ xx is not differential Stackelberg equilibrium. That is, either -1 or C' have at least one positive eigenvalue. Without loss of generality, let -1 have least one positive eigenvalue.
C C2 yet
Since (S) * 0 and det(C") * O. by Lemma B.3 b. there exists non-singular Hermitian matrices Pt. P2 and positive definite Hermitian matrices Q1. Q2 such that S - P1S = Q1 and CP2 + P&C' Q2 Further, S1 and P1 have the same inertia, meaning
S1) u+ (Pa), e- (-5)
(Pi), <(-S;) (Pai)
where for a given matrix A, v- (A), u- (A), and ((A) are the number of eigenvalues of the argument that have positive, negative and zero real parts, respectively. Similarly, C and P3 have the same inertia:
U+ (C) u+ (Pa), (C) e- (P2), ((C) = ((P)). Since -1 has least one strictly positive eigenvalue, 2+ (P1) (+(- 2 Define
I 1
P O
1 0 Lo
P
0
1
P₂
1
(21)
where Lo = (D2f(x"))-
fTx) -
= CD fz²"). Since P is congruent to blockdiag (P, P. P2),
by Sylvester's law of inertia (Horn & Johnson 1985 Thm. 4.5.8), P and blockdiag (P have the
same inertia, meaning that (P) = 24 (blockdiag( P1, P2)). (P(P) v- (blockdiag P1, P2)
and ((P) = ((blockdiag( (P1, P2)). Consider the matrix equation ---((x))-J)))) (x ) Q for -x* where
I
L
I
0 i
Q =
B
1
Lo
with
Q B, B ( P2) Pal,Drs("") + (PsloDre2(("") + TQ2
-
which can be verified by straightforward calculations.
Observe that Q, > equivalent to B, > 0 and both matrices are symmetric so that B, > and only if Q > 0 and (B,) > 0 where
S2 =
+ T
S...PP).
-
Now, S2(B, (B,) is also real symmetric matrix, and hence, it is positive definite if and only if all its eigenvalues are positive. To determine the range of T such that S2(Br) is positive definite, we can formulate eigenvalue problem to determine the value of 7 such that the matrix (2,) becomes singular. This is analogous to the guard map approach used in the proof in the previous subsection for the other direction of the proof, and in this case, we varying 7 from zero to infinity and finding the point such that for all larger т, S2(B, (B,) is positive definite. Intuitively, such an argument works since scales the positive definite matrix Q2. Towards this end, consider the eigenvalue problem in t given by
0 = det (Tl -2 -
S1L Pa)
28

---

Published as a conference paper at ICLR 2021
Let To be the maximum positive eigenvalue, and zero otherwise. Then, since eigenvalues vary continuously, for all T E (To, 00), Q, > so that by Lemma B.3 we conclude that P and -J, (x*) have the same inertia, but this contradicts the stability of (xx)) for all T (0))
since 24 (P) 2 1.
Remark on the tightness of r* The construction of r" is right in the following sense. While it is possible to construct multiple guard maps for a domain, all guard maps have the same positive real roots by definition (Saydy) 1996 Remark 2). Hence, independent of the guard map choice, we will get the same value of T". Moreover, r" tells us exactly when the eigenvalues move into the open left-half complex plane C and remain there. Hence, this gives us the precise, tight lower bound on the value of T"
C.3 7- TDGA PROVABLE CONVERGES TO DIFFERENTIAL STACKELEBRG EQUILIBRIA
As corollary to Theorem I] first show that the discrete time F-GDA update is locally asymptot- ically stable for a range of learning rates "/1
Corollary C.1 (Asymptotic convergence of T-GDA). Suppose the assumptions of Theorem 7 hold so that x² is a critical points of 9 and S (J(z)) and D2fz(=") are non-singular. There exists a
r' (0, oo) such that 7-GDA with 71 E (0, (T)) where >(re = arg minxespec(JJ (x*)) 2Re(A)/1A
converges locally asymptotically for all E (T",00) if and only if x² is differential Stackelberg equilibrium.
The proceeding corollary to Theorem I follows immediately from Lemma F.1 given in Appendix F
Proof. Suppose that x" is a differential Stackelberg equilibrium so that by Theorem I there exists a E (0, oo) such that spec(-J- (x*)) C C for all 7 E (r*, oo). Now that we have guarantee that (x+(x" is Hurwitz stable for any T E (r", oo), we apply Hartman-Grobne
to get that the
nonlinear system & = (x) is stable in a neighborhood of x=" Fix any (7", 00) and let
y = arg g (a=)) 2 Then, applying Lemma for any 71 E (0, T-GDA converges locally asymptotically x².
On the other hand, suppose that there exists a r E (0, 20) such that spec(-J+(x") C C2 for all E (T" 00). Then by Theorem 1 if is differential Stackelberg equilibrium. Furthermore, since J, C C2 for all T E oo), if we let 7 arg einxespee(J (x+)) 2Re(A)/ then by Lemma T- GDD converges locally asymptotically to xt for any choice of E (0,
D PROOF OF THEOREM 2 INSTABILITY OF T-GDA
To begin, consider critical point x² defined by g(x²) ential Stackelberg equilibria such that det(D3f(x*)) * 0. Then, (x=)))xxx)) = 7 det(1) fx²)) (
0 which is not differ-
if and only if det( (J 0 which implies J- (x)) is unstable for all E (To, o0) where To 0 when det(- (J 0. We now consider when (J (=(xz)) ))) + 0 for the remainder of the proof.
so that det(-J,
Let x² be stable critical point of 1-GDA (without loss of generality) which is not differential Stackelberg equilibrium. Without loss of generality, suppose that S (-J(x*)) has at least one strictly positive eigenvalue. Note that both (=(=)(=") and [D]((=)) are symmetric matrices and hence, have purely real eigenvalues.
Since both (-J((x))) and D fx=)) have no zero valued eigenvalues, by Lemma B.3 b, there exists non-singular Hermitian matrices Pt, P2 P2 and positive definite Hermitian matrices Q7, Q2 such that + P Si (I(-(xx") = Q1 and (² P2 P2D Q2. Further, S (xx")())))
and Pı have the same inertia, meaning
u4 (+1(((_)(=))) ))) = u (P:), V- (L ((S (P-(),
((P)
where for a given matrix A, w_ (A), v_ (A), and (A) are the number of cigenvalues of the argument that have positive, negative and zero real parts, respectively. Similarly, D²f(2*) and Pa have the same inertia:
44 (D}((")) u+ (Pa), v- (DZ((>)) u u <(D)S(>")) ((P2).
29

---

Published as a conference paper at ICLR 2021
Recall that we assumed 8ı(-J(z²)) has least eigenvalue with strictly positive real part. Hence, (Pt) = 24 (01((((111) (x))
Define
Lo
P 0
P
Ps
To
where Lo = (D
[xx) Since P is congruent to blockdiag( P1, P2). by Sylvester's
law of inertia (Horn & Johnson 1985 Thm. 4.5.8), P and blockdiag( Pi, P2) have the same inertia,
meaning that 4i (P) = v+ (blockdiag( P1. P2)), v_(P) e- =bllockdiagg P1, P2)). and ((P) ((blockdiag(P) (P,, P2)). Consider now the Lyapunov equation -P),(z)) - J, (x Q, for
-J, (x*) where
I Q.
1 Lo
0 I
B
0
1
with
Q B, = ([(((DD)) + +si P3)
P (2D + PaloDus(r") + (PoLoDia(((")) + =Q2
+
which can be verified by straightforward calculations.
Since v4 (Pi) 2 1, we have that (P) 2 1. Now, we find the value of such that for all >>>>>>>> To. Qr > 0 so that, in turn, we can apply Lemma B.3 a, to conclude that spec(-J+ & C Indeed, observe that Q+ > is equivalent to B, > 0 and both matrices are symmetric that B, if and only if Q > 0 and (B,) > where
S2(B,r (
TQ2
Pa). Now, (2,) is also real symmetric matrix, and hence, it positive definite if and only if all its cigenvalues are positive. To determine the range of T for which Q, > 0, we simply need to solve the eigenvalue problem
-(DDDaa((()) (PDDDff +
0 - - ((((A)DD(((())++(()())()))))+))) (B +
- PPLoDDuf(2") - (144DDofft))(PPooD1)11((((1 (P2
and extract the maximum eigenvalue, namely,
=mmax (Q, (1L
- (PPoooo(d
Hence, as noted previously, by Lemma B.3 a. conclude that for all 5 (To, 0o). spec(-J, & C2. This concludes the proof.
Additional context/intuition for the proof approach. To provide some context for the proof approach, remark that it follows the same idea as the proof of Theorem i Appendix C.2.2 Indeed, to determine the range of r such that S2 (B,) is positive definite, we can formulate an eigenvalue problem to determine the value of such that the matrix S2 (B, becomes singular. We vary T from zero to infinity in order to find the point such that for all larger т, Sy(B,) is positive definite. Intuitively, such an argument works since T scales the positive definite matrix Q2-
E PROOF OF THEOREM 3 STABILITY OF T-GDA IN REGULARIZED GANS
As in Mescheder et al. 2018), we only apply the regularization to the discriminator. In the following proof, use v.(.) denote the partial gradient with respect to of the argument (-) when the argument is the discriminator D(::w) in order prevent any confusion between the notation D(.) which we elsewhere for derivatives.
To prove the first part of this result, we following similar arguments to Theorem 4.1 of (Mescheder al. 2018). To prove the second part, leverage the concept of the quadratic numerical range.
30

---

Published as a conference paper at ICLR 2021
For both components of the proof, we will use the following form of the Jacobian of the regularized
game. Indeed, first observe that the structural form of J ((r.)) (x*) is
0 J1 (x - - -TBT T(C + PR)
B
(22)
where B = D12f(a" (2=), ('= -D3 and = (x")) where RS is either gradient penalty indexed by j = 1, 2 This follows from Assumption a. which implies that D( w") = 0 in some neighborhood of supp(pp) and hence, v,D(x;w") = and V.D(x; 0 for supp(pp). In turn, we have that -
Proof that x² = (0", w)) is a differential Stackelberg equilibrium. For any fixed μ (0, oo), then we first observe that x² is also a critical point of the unregularized dynamics. Indeed, by As- sumption I a., (2 w²) = 0 in some neighborhood of supp(pp) and hence, VzD(z;w") = 0 and V2D( ~ = 0 for x E supp(pp). Further, D2R, w) = pll
w)] for j = 1,2 where (xr = (2) and (x:) = Po (2). Thus, using the above observation that v, w = O, we have that (2R, w = for 1, meaning that the derivative of the regularizer with respect to w is zero at x= = (0", w²) which in turn implies that Dxf(x=) = 0 and -D2f(x*) 0. Hence, x² is a critical point of the unregularized dynamies as claimed. Further, > 0 which follows from Lemma D.5 in (Mescheder et al.) (018). From Lemma D.6 in Mescheder et al. 2018), due to Assumption [c., if f 0 and v & TT-Mc, then Be + 0 which im- plies that B can only be rank deficient on To Ta-Ma. Using this fact along with the structure of the Ja- cobian as in (22 we have that the Schur complement of J(r,u) (x*) is equal to B (C+yR) >B>0 ) is a differential Stackelberg equilibrium.
since C + R > O. Hence, x= (6*, w²)
Proof of stability. Examining (22) it is straightforward to see that the quadratic numerical range (J)))))) has eigenvalues of the form
Ae. [ pr)) + / pr))² 47766/
w) and r (D) (x" ,w, w) for vectors E W1 n (Ta) and w E W2 n MD)) where U denotes the orthogonal complement of U. We claim that for any value of μ (0, 00) and any - (0, oc), Re(Ar,u) > O. Indeed, argue this by considering the two possible cases: (1) (T(c+ (r)) < 2 or (2) (r(c+ + pr)) > 47 1b/2
where b = (Dia (2" Jo,"", w) c= (-D
Case 1: Suppose that (T(C+ - T Then, Re(Ar,n) = (T vr)) > 0 trivially
since + par O.
Case 2: Suppose that (7 + /r)) > 4r 2 In this case, we want to ensure that
Re(A+) [ pr) /v[ ur))² 4r > 0.
which holds since
(r))+ > (-7(c+ (u))² 4 0 1
This concludes the proof.
E.1 NECESSARY CONDITIONS ON GAN ARCHITECTURE
The following proposition provides necessary conditions on the sizes of the network architectures for the discriminator and generator network for stability.
Theorem A.7 of Mescheder et al. (2018) shows that matrices of the form
0
B
-J
(23)
B
C
are stable if B is full rank and C > The following proposition provides necessary conditions on the sizes of the network architectures for the discriminator and generator network for stability.
MMecchderr et al. (2018) imply that their results hold for convex combination of the two gradient penalties, which would in imply our results will hold in this case. However, we have included the details here.
31

---

Published as a conference paper at ICLR 2021
Proposition E.1. Consider training a generative adversarial network via a zero-sum game with generator network Gg, discriminator network D.,, and loss f(8,w) with regularization R,(0, w) (for some j {1, such that Assumption 7 is satisfied for equilibrium x' = (0" ,.).. Independent of the learning rate ratio and the regularization parameter ps, for x² to be stable is necessary that the dimension of the discriminator network parameter vector is at least half as large as the corresponding generator network parameter vector: 122 2 n1/2 where 0 E Ru and w E IR
The intuition for the why this proposition should hold follows immediately from observing the struc- ture of the Jacobian: for any matrix of the form (23) at least one eigenvalue will be purely imaginary if n2 n1/2 where B E x observing the structure of the Jacobian: for any matrix of the form
X and C E R 22,, This proposition follows immediately from
0
-B -
J
B
at least one eigenvalue will be purely imaginary if n2 < n2/2 where B E R and C E R Indeed, by Lyapunov's 's stability theorem for linear systems (Hespanha 2018 Theorem 8.2), matrix A is Hurwitz stable if and only if for every symmetric positive definite Q Q > 0, there exists
a unique symmetric positive definite P = pT > 0, such that A P + PA Q. Hence, -J is
Hurwitz stable if and only if there exists P P > 0 such that
0 B
P
P2
P1
P2 P3
B
0 Q<Q=
=
C
P
P3
P
-
B
C
P - P3BT BT - BP3 + P P2C
- BPG - P2B
CPs
P3C
Since this is a symmetric positive definite matrix, the block diagonal components must also be symmetric positive definite so that -BP, P.B > of Recall that B E R X and P2 e R=.X"1, Hence, necessary condition for this matrix be positive definite is that 72 2 n2/2 for - -BP2 - P2B to have full rank; of course this is not sufficient, but it is necessary. It is easy to see this argument is independent of whether learning rate ratio 7 O regularization is incorporated.
F PROOF OF HELPER LEMMAS AND THEOREM 4 FOR T-GDA CONVERGENCE
In this appendix section, we prove the following two lemmas. The proofs build on one another so state them jointly here. We then invoke them to prove Theorem 4
Lemma F.I. Consider zero-sum game (J1: J2) = (J--J) defined by J E CT(X, RR) for some r 2 2. Suppose that x² is differential Stackelberg equilibrium and that given T > 0, (pec(-J,(z*)) C CO Let Y = minxespec(J=(""")) 2Re(A)/ For any Y E (0, 7), T-GDA converges locally asymptotically.
Lemma F.2. Consider zero-sum game f2) (f. defined by f C" for some
r r 2. Suppose that x" is a differential Stackelberg equilibrium and that given spec( (x+(x))
C2. Let 7 minxxspecc (x 2 and Xm arg minxespe (=*)) 2 For
any a E 70, 7-GDA with learning rate 7/1 7 a converges locally asymptotically a rate of
O((1 - 433 1//2) where 3 = (2Re(>a) ca>anl?) 12)
F.1 PROOF OF LEMMA
Suppose that x= is a differential Stackelberg or Nash equilibrium and that 0 < T 0o is such that spec(-J, (z") )) C C2. For the discrete time dynamical system Ik+1 It - 71 (zgg)())), it is well known that 21 is chosen such that J (z*) (z))) < 1, then 23 locally (exponentially) converges to x (Ortega & Rheinboldi, 1970). With this in mind, we formulate an optimization problem to find the upper bound 7 on the learning rate "1 such that for all 71 E (0, the spectral radius of the local linearization of the discrete time map is contraction which is precisely p( (x*"))) < 1.
The optimization problem is given by
max XEspee(J- (a=)) |1- 7A/ $1
7
min <>0
(7)
(24)
IIf a block matrix Q with block entries Qú, for i,j {1,2) is positive definite symmetric, then Qu > 0 for 1, 2.
32

---

Published as a conference paper at ICLR 2021
The intuition is as follows. The inner maximization problem is over finite set spec (x*)) {Ai...., An where Jr (x") E R=x" As y increases away from zero, each |l - ? shrinks in magnitude. The last A such that - - hits the boundary of the unit circle in the complex plane (that is, |1 ydg 1) gives us the optimal value of y and the element of speo(J=(x")) that achieves it. Examining the constraint,
have that for each Ai 70y|2,12 2Re(A:)) S 0 for any
> O. As noted this constraint will be tight for one of the X, in which case 7 = 2Re(A)/ since y O. Hence, by selecting ? (iixxspec(J,(==") 2Re(A)/AA we have that |1 - 7i < 1 for all spec(J+(x*)) and any 71 (0,
To see this is the case, let
7 min
2Re(A)/
(E)pec(J,(z"))
and
Am arg
min AEspec(J.)
2Re (Re(A)/12
Using the expression for 7, we have that
1 - 27) + ((Re(A)) + Tm{A)9)= = (Re(
(2Re(da) 2
Re(A) +
1212.
1aa1
Maal
Now, using the fact that Re(A)//2R3>>> Re(Aa) we have
Ro(An)
(2Ro(An))
2
[A/2 $1 (2R(An) Re(A) + (2R((>n)
2 (n((
1
Re(A)+
An1
|Aal
Aa 12
Re(An)
Re(>a)
+4 Re(Aal Re(A)
4 |aal 1
Re(A)
|2al 12
=1
as claimed. From this argument, it is clear that for any 71 E (0,7), 11 >1 < for all X E spec(Jr (x*)).
Now, consider any a E 70, and let 8 = (2Re(Au) ar a1\a1²)= Observe that 71 = 7 - a so that 71 70, Hence,
2Re(An)
a) - Re().)) +
(2e(An) -a) -a) Im(2w)2
))
[1 - (7 aa)aa
Re(Ax)²
Re(An)²
1 4 Din2
+ -2aReedda) +
4aRe(Ao) + aaala
121
1 2aRe(Na) + a aala
1
so that
p(I - (d-))((=")) (1
1/2
3
Hence, the p(I-71 < 1 so that an application of Proposition B.1 gives us the desired result.
F.2 PROOF OF LEMMA
To prove this lemma, we build directly on the conclusion of the proof of Lemma F. Indeed, since
(1
1/2
p( - -J+(("))
given E 48
0 there exists norm || (cf. Lemma 5.6.10 in Horn & Johnson (1885) such that
1/2
1/2
a
a
a
+
<
3
43
2
'The norm that exists can easily be constructed as essentially a weighted induced 1-norm. Note that the norm construction is not unique. The proof in Hom & Johnson (1985) is construction and the construction of this can be found there.
33

---

Published as a conference paper at ICLR 2021
where the last inequality holds by Lemma B.1 x², we have
Taking the Taylor expansion of I - (1)+ around
T- 119 (T (19. + J1 (x)))() x²) + R2( -x*)
where R2 x²) is the remainder term satisfying Rz x²) o{1 x= [1) + x." This
implies that there is a 8 > 0 such that || )
I 80 x- x=11 whenever || x²1 < 6. Hence,
a
|| T19 (2) (1 719. (x") 1)1 s 11--71J+(2 (1>+<"")1
+
| x=
43
1/2
+
| x='
2,3
8,
a
|| x11l
48
where the last inequality holds again by Lemma B.1
Hence,
k/2
late x"1 1
2100
x.
(25)
4,3
whenever |aao x=Il < 8 which verifies the claimed convergence rate.
F.3 PROOF OF THEOREM 4
This result follows directly from Theorem 1 Theorem B.2 Lemma F.2
and the following result.
Proposition F.1 (Jin et al. 2020 Consider a zero-sum game f2) = (f--f) defined by
C" R) for some spec(-Jr(2') C C2 for all T E (0, 20).
2. Suppose that x² is differential Nash equilibrium. Then,
Now prove Theorem we apply Theorem to construct 7" via the guard map v(T) dr B -J+(x")) such that for all r E [T" oo), spec(J+(x") C CJ This guarantees that spec(- (+(x")) C for any T E (r", 20) and hence the nonlinear dynamical system
4 -
locally asymptotically (in fact, exponentially) stable by the Hartman-Grobnen theorem (cf. The- orem B.2 Therefore, for any т E (0", by Lemma F22 T-GDA converges with rate of O((1 4/ k/2). Finally, 7" by Proposition R1 if x= is differential Nash equilibrium. This
concludes the proof.
While this result was shown in Jin et al. (020), we give some intuition for why it holds based on the quadratic numerical range tool. Indeed simple observation of the eigenvalues of the quadratic numerical range show that spec(J=(x") C Ca for any r E (0, co). Recall that
Intuition for Proposition F1
U wEW,
"p
where
(x") (DFf(x*)e,))
(Di2f (a=) )w, (-r Dz (x*) )w,w)
(TeDDT)("")) (x=)),, w))
and W {a C
|||||| = 13 for each i 1.2. Fix E W1 and w E W2 and consider
b
J m.
-b Td
Then, the elements of ( ()+(())) are of the form
A = _ (a + rd) + V (a - rd)2 1T
The notation R2(2 -=(===") x²) 0011= x ||) xn" means lim |a x" 1//1// x"1
34

---

Published as a conference paper at ICLR 2021
where f(= (1,)), v), b= (Di2f(=")w.)) and d = ff yw, w) for vectors W1 and w E W2. Since (xf((")= >>0 and -D2f(x*) > 0, Re(A(JJ,w (z) > 0 since {(Jv, (x*) )) =
(a + d) + 2 (a - d)2 -4/b/2. The introduction of T E (0, oc) does not alter the sign. This is
obvious when Im(),) * 0. On the other hand, if Im(A,) = 0 so that (a - rd)² > 47/ then
Re(A-) > {a + rd) - 1 V(a (a- -dd² 4T|b/2 > 0.
The last inequality is easily seen to be equivalent to aad < |b|2 which holds for any pair of vectors (v, w) such that E Wi and
W2 since > 0 and d > 0. Hence, for any E (0, oo), spec(J+ (x=)) C Ch since the spectrum of an operator is contained in its quadratic numerical range and the above argument shows that (J (x*)) C C.
G PROOF OF COROLLARY
I FINITE TIME CONVERGENCE OF T-GDA
Let || Il be the norm that exists (via construction a la Horn & Johnson 1985 Lem. 5.6.10) in
Following standard arguments, (25) in the proof of Lemma F.2 implies a finite time convergence guarantee. Indeed, let be given. Since Hence,
the proof of Lemma F22 which is given in Appendix r
0 < 43 < we have that (1 a4(3)) exp(-ka/((
|00 I' S exp(_ka/443)]lxz I1 =
In turn, this implies that Ik (x meaning that zy is a e-differential Stackelberg equilibrium for all & 2 (1 - x 1=()/ whenever ||000 - x=1 < 5.
Now, given that Ji C" R) for r 2 I (rx) is locally Lipschitz with constant L so that
we can find an explicit expression for 5 in terms of L. Indeed, recall that R2(x - x²) o(I x. x0))
as + x² which means lim [ x") (1/\ll//== xx I| so that
[2 - x1)| L. |1
n1 + n 7
x²)) - (1 - -n M|l x²1 l| dn S 2 || - x²1
Observing that
(R2(x=>')1l S / || x= x=1 = 2
L
L
x² |||| x²11,
have that the 8 > 0 such that |2( x")ll (8(88)) |r x' is ē a/ (4TB4))
Comments on computing the neighborhood Bs(x)). We note that we have essentially given a proof that there exists a neighborhood on which F-GDA converges. Of course, due to the non- convexity of the problem in general, this neighborhood could be arbitrarily small. We provide an estimate of the neighborhood size using the local Lipschitz constant of the local linearization I - -=*"" One way to better understand the size of this neighborhood is to use Lyapunov analysis, a tool which is well explored in the singular perturbation theory (Kokotovic et al.) 1986). In particular, Lyapunov methods can be applied directly to the nonlinear system if one can construct Lyapunov functions for the fast and slow subsystems individually-alss known as the boundary layer model and reduced order model. With these Lyapunov functions in hand, one can "stitch" the two together (via convex combination) and show under some reasonable assumptions that this combined function is Lyapunov function for the overall singularly perturbed system. The benefit of this analysis is that the Lyapunov function gives one an estimate of the region of attraction (via, e.g., the level sets); however, it is not easy to construct Lyapunov function for nonlinear system in general. We leave expanding to such methods to future work.
H CONVERGENCE OF STOCHASTIC GDA WITH TIMESCALE SEPARATION
In this section, we analyze convergence when players do not have oracle access to their gradients but instead have an unbiased estimator in the presence of zero mean, finite variance noise. Specif- ically, we show that the agents will converge locally asymptotically almost surely to a differential Stackelberg equilibrium.
The key insight in this section is that due to Theorem I in the main body, we know that a critical point xt is stable for å (x) for range of finite learning rates E (T", oo) if and only
35

---

Published as a conference paper at ICLR 2021
if x² is a differential Stackelberg equilibrium. Hence, treating A (z)(2) the continuous time limiting differential equation in the so-called ordinary differential equation (ODE) method in stochastic approximation (Borkar 2008), apply classical stochastic approximation analysis to conclude that the stochastic gradient descent-ascent update with timescale separation converges.
H.1 ASYMPTOTIC CONVERGENCE GUARANTEES VIA STOCHASTIC APPROXIMATION
The stochastic form of the update is given by
Øk+1 = 2y - The (A+g(()))) + wx+1)
(26)
where Wk++1 is a zero mean, finite variance random variable and {(u} is the learning rate sequence. Assumption 2. The stochastic process {wx} is a martingale difference sequence with respect to the increasing family of a o-fields defined by
F& = ofre we, l S k), Wk 2
so that Elwa+1| Fu] 0 almost surely (a.s.) for all k 2 0. Moreover, wy is square-integrable so that, for some constant C O.
E|| wk 11 Ful S C(1 + | a.s., Ak 2 0.
We note that this assumption has been relaxed in the literature (Thoppe & Borkar 2019), however simplicity, we state the theorem with the most accessible criteria. We remark below in the paragraph on extensions to concentration bounds on the nature of the relaxed assumptions.
Theorem H.1. Consider zero-sum game (f.-f) such that f C") for some 2 2. Suppose that Assumption 2 holds and that {rx} is square summable but not summable i.e,
E <0,, yet Σx 7 oc. For any (0, oc), the sequence {ar} generated by (26) converges to a, possibly sample path dependent, internally chain transitive invariant set of it - -A)g(r).
Moreover, x" is a differential Stackelberg equilibrium, then there exists a finite T" E [0, 0o) such that } almost surely converges locally asymptotically to x" for every T E (7",
Proof. The convergence of { to possibly sample path dependent, compact connected inter- nally chain transitive invariant set of -A)((z) follows from classical results in stochastic approximation theory (Borkar (2008 Chap. 2); Benaim 1996)).
Suppose that x= is a differential Stackelberg equilibrium. By Theorem T' [0, oo) such that for all E (r", o0). x² is a locally exponentially stable equilibrium of the continuous time dynamics i = -A,g())) that is, spec(-J,(x")) c C2 for all 7 E (r", oo).
|| there exists a finite
C2. det(-J, * so that x² is an isolated critical point. Furthermore, exponentially stability of x implies that there exists a (local) Lyapunov function defined
Fix arbitrary T oo). Since spec(-J-
neighborhood of x" by the converse Lyapunov theorem (Sastry [1999] Thm. 5.17), Krasovskiil (1963, Thm. 4.3)). Let U be the neighborhood of x on which the local Lyapunov function is defined, such that U contains no other critical points (which is possible since x² is isolated). That is, let & : U + [0, oo) be the local Lyapunov function defined on U where x² E U, & is positive definite on U. and for all I E U. -. (x)) < 0 where equality holds for 2 U if and only if ((2) O. By Corollary 3 (Borkar) 20008, Chap. 2), {aa} converges to an internally chain transitive invariant set contained in T almost surely. The only internally chain transitive invariant set in U is x..
The following corollary shows that if there is finite 7" such that x" is stable for i = (x)) then by Theorem x must be differential Stackelberg equilibrium and in turn, {xx} almost surely converges locally asymptotically to x² by the above theorem.
Corollary H.1. Consider a zero-sum game (f--f) such that f E (X, RR). Suppose that Assump- tion 2 holds and that {rk} } is square summable but summable: En 2 < cc. yet Σx 7kk If there exists a finite T" E [0, oo) such that spec(- Jr (x*)) C. C2 for all T E (7",0)), then x" is a differential Stackelberg equilibrium and { almost surely converges locally asymptotically to x².
36

---

Published as a conference paper at ICLR 2021
While (local) almost sure convergence in gradient descent- (Chasnov et al. 2019) to critical poin in the stochastic setting, the result requires time varying learning rates with a sufficient separation in timescale. Specifically, the players need to be using learning rate sequences {Tr,) ) for each i E {1,2] such that (without loss of generality) not only is it assumed that 7i,k = o(22.)), but also >x 7T. + +22.. < oo and Σx Ki,k oo for each E {1, The challenge with these assumptions on the learning rate sequences is that empirically the sequences that satisfy them result in poor behavior along the learning path such as getting stuck at saddle points making progress. This is, in essence, due to the fact that the faster player-that is, player "1.K = 0(72,)) equilibriates too quickly causing progress to stall. This can result in undesirable behavior such as vanishing gradients (so that the discriminator does not provide enough information for the generator to make progress), mode collapse, failure to converge in practical applications such as generative adversarial networks.
On the other hand, our convergence result gives similar guarantee with less restrictive requirements on the learning rate sequence. In particular, only a single learning rate sequence is required (so that the algorithm can be viewed as single timescale stochastic approximation update) as long as the fast player (who, without loss of generality, is player 2 in this paper) scales their estimated gradient by E (T", 00) where T" is as in Theorem
H.2 EXTENSIONS TO CONCENTRATION BOUNDS AND RELAXED ASSUMPTIONS ON STEPSIZES
possible to obtain concentration bounds and even finite time, high probability guarantees on convergence leveraging recent advances in stochastic approximation (Borkar) 20088] Kamal 2010 Thoppe & Borkar 2019). To our knowledge, the concentration bounds in (Thoppe & Borkar 2019) require the weakest assumptions on learning rates cates-c.g.. the learning rate sequence {nks} needs only to satisfy Σ, 7h = co, lim 7 0. and Σx " I 1. Specifically, since is assumed, for the zero sum game (f), that I C² R) and x a differential Stackelberg equilibrium, Theorem I implies that x= is a locally asymptotically stable attractor of ă -A, g(x) for arbitrary fixed r Tr,, oc). and hence, the concentration bounds in Theorem 1.1 and 1.2 of (Thoppe & Borkar 2019 directly apply.
Furthermore, we note that in applications such as generative adversarial networks, while has been observed that timescale separation heuristics such unrolling annealing the stepsize of the dis- criminator work well, in the stochastic case, gunnmable/ssuurr--uummaaa generally too restrictive in practice since they lead to a rapid decay in the stepsize which, in turn, can stall progress. On the other hand, stepsize sequences such as 7/k = 1/(k + +1) for B E (0, 1]- a sequence which satisfies the assumptions posed in (Thoppe & Borkar 2019) tten not to have this issue of decaying too rapidly for appropriately chosen B, while also maintaining the guaran- tees of the theoretical results. We state convergence guarantee under these relaxed assumptions in Proposition beloo...
assumptions on stepsizes
Let a(t) be the asymptotic pseudo-trajectories of the stochastic approximation process {xx). That is, ā(() are linear interpolates between the sample points 2i generated by the stochastic 7-GDA process, and are defined by
(1. (1-4x) (F(te+2)) - =(tx))
a(t) = i(tx) +
where t. = + 7/k and O. Assumption 3. The stochastic process }wa} is martingale differrence sequence with respect to the increasing family of o-fields defined by
Fs = (Ie, We, l S k), Vk vk200 0,
so that E[wx+11 Ful such that
0 almost surely for all l 2 0. Furthermore, there exists 01 C(Rd, Rso)
Pr Pr[[lux+1] vl F&) & c1(2x) exp(-c2(z1)1), 0
for all v 2 ē where i is some sufficiently large, fixed number.
1o date it has not been shown that for sufficient separation in timescale the only critical point attractors are local minmax.
37

---

Published as a conference paper at ICLR 2021
Proposition H.1. Suppose that Assumption 3 holds and that x² is a differential Stackelberg equi-
librium. Let "/k = 1/ + 1) where 3 E (0, 1]. There exists a T E [0, oo) and an en E (0. 0o) such that for any fixed so that when T r2 (c) and Ko 2 K where Kr is such that 1 1/v 2 h2(e) ) for all 2 K the
co). there exists functions h (e) ((1og(1/e) and h2(c) (11cc)
stochastic iterates of T-GDA with stepsize sequence "n and timescale separation E (T", 00) satisfy
(t( x111 Vt 2 the + ((ta)))))))))))))))tt) = =1 -//2
(xp(-C,hip 1))
for some constant C, > 0.
The proof largely follows from the proofs of Theorem 1.1 and 1.2 in (hoppe & Borkar 2019) combined with the existence of finite timescale separation parameter obtained via Theorem Indeed, since x² is a differential Stackelberg equilibrium, by Theorem there exists range of T namely, (T", such that for any T E (7", 00), x locally asymptotically stable equillibrium for à = -A (x)) Hence, fixing any T E (r" oo), converse Lyapunov theorem can be applied to construct local Lyapunov function. Let V R - R be this Lyapunov function so that there exists ro, 6D > 0 such that r > ro. and
Bx(x") C T C (VT)) CV
for any c E (0, col where, for a given g > 0, V = fx dVm( : V(z) S q) and No. (V+) is an eg-neighborhood of Vro_ie. Noo (VT))= far R"I By E Vio |xr y c0 From here, the result follows from an application of the results in the work by Thoppe & Borkar (201)).
The utility of this result is that it provides a guarantee in the stochastic setting for more reasonable and practically useful stepsize sequence. However, constructing the constants such as K,, C2 and eo is highly non-trivial as can be seen in the work of Thoppe & Borkar (2019) and similar works in the area of stochastic approximation (Borkar 2008). One direction of future work is examining the Lyapunov approach for directly analyzing the nonlinear singularly perturbed system; it is known, however, that the stochastic singularly perturbed systems have much weaker guarantees in terms of stability (Kokotovic et al. 1986 Chap. 4).
I STABILITY OF oo-GD: A SINGULAR PERTURBATION APPROACH
The examples included in Section provide evidence that there exists a range of finite learning rate ratios for which differential Stackelberg equilibrium are stable and a range of learning rate ratios for which non-equilibrium critical points are unstable. Yet, until this paper, no result has appeared in the literature gradient descent-ascent with timescale separation confirming this behavior in general.
The closest existing result studies the limiting case T + 0o. As mentioned previously Jiin et al. 2020) show that 7 - co, the of stable critical points with respect the dynamics & (x) coincide with the set of differential Stackelberg equilibrium. However, an equivalent result the context of general singularly perturbed systems has been known in the literature ( (Kokotovic et al. 1986) Chap. 2). We give a proof based on this type of analysis because it reveals a new set of analysis tools to the study of game-theoretic formulations of machine learning and optimization problems. The formal statement (which is restatement of the result from Jin et al. 2020 in our notation) is given below.
Proposition I.1. Consider zero-sum game (f1, -U, defined by f E (X, IR) for some r 2 2. Suppose that x" is such that g(x*) = 0 and (2 fx²)) * 0. Then, as 7 + co, spec(- J+ C C2 if and only if x² a differential Stackelberg equilibrium.
The structure of this proof is as follows. We begin by introducing general background for analyzing general singularly perturbed systems. Following this, we consider the linearization of the singularly perturbed system that approximates the simultancous gradient dynamics and describe how insights made about this system translate to the corresponding nonlinear system. Finally, we analyze the stability of the linear system around a critical point to arrive at the stated result. The analysis primarily from Kokotovic et al. (1986).
Analysis of General Singularly Perturbed Systems. Let us begin by considering a general sin- gularly perturbed system for Ra, Rm, and sufficiently small parameter 8 > given by
38

---

Published as a conference paper at ICLR 2021
Σ 2,,,,, x(to,E) 20, x R :: - 2,,, 2(4u,e) = 20. E 1
(27)
where f and are assumed to be sufficiently many times continuously differential functions of the arguments 2; 2, c, and Observe that when 0, the dimension of the system given in (27) drops from + m to since å degenerates into the equation
0 g 2, 0,t)
(28)
where the notation of ă. indicates that the variables belong to the system with 0. We further require the assumption that (28) has k 2 isolated roots, which for each i (1..... , k) are given by
2 = (ā,tt.
We now define an n--imensional manifold Me for any > 0 characterized by the expression
(t, c) = ((x(tt(x)).))) e),
(29)
where @ is sufficiently many times continuously differentiable function of x and For M2 to be an invariant manifold of the system given in (2)). the expression in must hold for all if holds for = t². Formally, if
=(1", <lx(1" e),,)) + =(1,e) (xx(1,)), 1221,
(30)
then M, is an invariant manifold for (7 Differentiating the expression in 30 with respect to t, we obtain
dg dt d()(t,)),)) = Oz x.
2 Now, multiplying the expression in (31) by and substituting in the forms of i, 2, and z from (27
(31)
and 229. the manifold condition becomes
dó 1 ((,,,,),, g(,, -
(32)
which ((x, E) must satisfy for all x of interest and all E [0,="] where e" is a positive constant.
We now define
===- ((x,))
Then, in terms of and 77, the system becomes
fæ, pl n,E,t)
de Oz
a = g(,, olz, + t, - - f(r, 6(x,=) + n.e,t).
Remark 1. One interesting observation is that the above system is exactly the continuous time limit- ing system for the T Sttackelberg learning update in Fiez et al. (2020) under a simple transformation of coordinates.
Observe that the invariant manifold M, is characterized by the fact that 7 0 implies ij = 0 for all x for which the manifold condition from 32) holds. This implies that if 17(1,, 8) 0, it sufficient to solve the system
i = f(x, ((z,,)) E,) (t,o =)
This system is often referred to as the exact slow model and is valid for all x, e Me and Me known as the slow manifold of (35)
Linearization of Simultaneous Gradient Descent Singularly Perturbed System. sider the singularly perturbed system for simulataneous gradient descent given by
We now con-
f 1
(33)
Ei = D2,f2
39

---

Published as a conference paper at ICLR 2021
Let us linearize the system around a point (x*,²") Then 11
(1 2) 2 (1fi(0", ;-"=((""")))>>>"""""))")"" Di (x"; ,= (x) - x²) + 112/(10 2* (= (=-=")
(34)
D2)2(x,2) = D2f2(2", =²)+ D21 f2"", =x" 11 -2)
12 (²)(=- -=)).
Defining u = (x-x*) and v = (z-z") and considering a point (=",==" such that (ifi(a", and D2/2(x", ,²*) O. then linearized singularly perturbed system is given by
à - ( = (12/1 )0))
(35)
eú D211f((1* ,2 12 ;2)00
To simplify notation, let define Jr as follows
( x*) = = E D21 2²))
D12fi x*) e D2/22"" ,*))
AnI
A12
=
E A21
e- A22
along with
w
i and
w
Then, an equivalent form of (35) is given by
- J, w.
(36)
In what follows, we make insights about the behavior of the nonlinear system given in a critical point (x", =*) ) by analyzing the linear system given in (36). Recall that (x ;=*) is asymptotically stable with respect to the lincar system in (36). then it is also asymptotically stable
33 around
with respect to the nonlinear system from (33) Moreover, to determine asymptotic stability, it is
sufficient to prove that spec(J- x))) Ct. In what follows, we specialize the general analysis
of singularly perturbed systems to the singularly perturbed linear system given in (36).
Stability of Critical Points of Simutancous Gradient Descent. The manifold condition
from 32 for the system in (36) is given by
OΦ (Auı + A12Φ(u,
12 + Amo((,, = Ou
(37)
We claim that
37 can be satisfied by function & that is linear in u. Indeed, defining
e= (u, s) = -(suu
and then substituting back into 332 get the simplified manifold condition of
A21 L = - [() + (L(e) (1)
(38)
Before we prove that an L(s) always exists to satisfy
38
consider the change of variables
= v + L(E)u.
The change of variables transforms the system from 36 into the equivalent representation
i
[A A12
A12
(39)
R(L,E)
Ag2 - EL(E)
n
where
R(L = A21 - (() + (L((s))
-
(40)
Consider that R(L, = 0. Then, the system from (39) has the upper Hlck-triingull form
i
An A1)L(e) 0
A12
x
(41)
Ag +c)(
[
which has the effect of generating replacement fast subsystem given by Erj = (Ag2 + ELA12)
We now proceed to show that an L(E) such that R(L, +) always exists.
HHere the means, e.g., (1f "
=²) + fi (z) x²) + D ,=)((
=²) O(I =1 + || - 2111²), and similarly for D2f2(=22).
40

---

Published as a conference paper at ICLR 2021
Lemma L1. If A22 is such that dee((Az) O, there is e* such that all E [0,E*], there exists a solution L(e) to the matrix quadratic equation
R(L,E) = A21 - (2) + -
(42)
which is approximated according to
L(e) A32 A21 EAA2 A21 Ao +
(43)
where
Aa An A12 A21
(44)
Proof. To begin, observe that for e == 0, the unique solution to (42) is given by L(0) A A21.
Now, differentiating E( from (42) with respect to E, we find
dL dL L(e)A1 (A)-)))((e))
A22 + A1( de
7 (An
(12))12((E).
The unique solution of this equation at
dL A (n) A12[(0)) A32 1522Ap) A21 Ao-
de
c=u
Accordingly,
433 represents the first two terms the MacLaurin series for L(E).
We remark that L(s) as defined in 43 is unique in the sense that even though R(L, e) as given in (42) may have several real solutions, only is approximated by
The characteristic equation of (41) is equivalent to that for the system from 366 owing to the sim- ilarity transform between the systems. The Block-triangul form of (36) admits characteristic equation given by
((s,e)
_ e
(,, -0
(45)
where
(s,, det(s/ A12((e))
(46)
the characteristic polynomial of the slow subsystem, and
(p, det(pl (A22 + =Ai2L(s)))
(47)
the characteristic polynomial of the fast subsystem in the timescale p se. Consequently, of the eigenvalues of (36) denoted by {Ai,..., An} are the roots of the slow characteristic equation (s, E) and the rest of the eigenvalues {An+1..... An+m) are denoted by A 2,/E for i == n + and j E {1......o m where (Vi...., ] are the roots of the fast characteristic equation (p)(p.)) 0.
The roots of (s,e) a = O, given by the solution to
(x, 0) = det(ss - (A11 - A12 = 0,
(48)
the eigenvalues of the matrix Au defined in (4 since L(0) AAg A21 shown in Lemma
L.1
The roots of the fast characteristic equation at e = 0, given by the solution to
(p 0) = det(pT A22) =
(49)
are the eigenvalues the matrix Ag2. The roots of the systems correspond to the conditions for differential Stackelberg equilibrium, which thus gives the result.
We now proceed by characterizing how closely the eigenvalues of the system at a = approximate the eigenvalues of the system from (36)
0.
det det(Agz) (Agz) * O, then as E - 0, n eigenvalues the system given in 36 tend toward the eigen- values of the matrix Ag while the remaining cigenvalues of the system from (36) tend to infinity
with the rate 1/e along asymptotes defined by the eigenvalues of A22 given as spec(A22)/= as a result of the continuity of coefficients of the polynomials from (46) and (47) with respect to
41

---

Published as a conference paper at ICLR 2021
Now, consider the special (but generic) case in which the eigenvalues of Au are distinct and the eigenvalues of A22 are distinct, but Ag and A22 may have common eigenvalues. Then, taking the total derivative of (45) with respect to we have that
0v. ds
0v. de
Os ds
Now, observe that tv../ds f 0 since the eigenvalues of Ao = A11 - A12222 A21 are distinct 12 For each = ...... n, this gives us a well-defined derivative ds/ /e (by the implicit mapping theorem) and hence, with s(0) = X (Ao), the (e) approximation of s(e) follows directly. That is,
A = (Ao) + O(s), i i= ,,...,
Similarly, taking the total derivative of (p, =) 0 and again applying the implicit function theo- rem, we have
Aptn (> (A22 O())), i= 1......, where we have used the fact that p 86.
J FURTHER DETAILS ON RELATED WORK
In this section, we provide further details on the discussion from Section A regarding the results presented by Jin al. (2020) the local stability of gradient descent-ascent with finite timescale separation. The purpose of this discussion to make clear that Proposition 27 from the work of Jin jet al.] (2020) does not disagree with the results we provide in Theorem T and Theorem and is instead complementary. In what follows, we recall Proposition 27 of Jin et al. (2020) in separate pieces the terminology of this paper and delineate its meaning from our results on the stability of gradient descent-ascent with finite timescale separation.
To begin, we consider the component of Proposition 27 from Jin al. (2020) which says that given any fixed and finite timescale separation т > 0, a zero-sum game can be constructed with differ- ential Stackelberg equilibrium that is not stable with respect to the continuous time limiting system of 7-GDA given by the dynamics à = -A,g(x).
Proposition J.1 (Rephrasing of Jin et al. 2020] Proposition 27(a)). For any fixed T > O, there exists zero-sum game G (J, -)) such that (x=)()+(x*)) & C2 for differential Stackelberg equilibrium x".
We now explain the proof. Let us consider any 6 >> and the game
f(z, v) = =z² + 2/ery - (c/2)y². At the unique critical point (x*, ,y²" = (0,0), 0). the Jacobian of the dynamics given by
(50)
-2
2
(x y²" -2TV
Moreover, observe that (x",y") is differential Stackelberg equilibrium and not differential Nash cquilibrium since fif(=" .)")= -2 > 0, ffa .y") = e 0 and (J y²)) = 2 0.
Finally, the spectrum of the Jacobian is
spec(J+ .²)) -2 2 V72 12re + 4
Let us now fix as any arbitrary positive value. Then, consider the game construction from (50) with c 1/r. For the fixed choice of 7 and subsequent game construction, we get that
spec(J, (x", v²)) = ( of C..
This in turn means the differential Stackelberg equilibrium is not stable with respect to the dynamics = - ) for the given choice of r. Since the choice was arbitrary, this a valid procedure
Recall that having distinct eigenvalues is a generic condition for matrix explicitly required for the asymptotic results; its only condition for the big-O approximation X; (A)) + ((e) for 1,... ny and E (Ay(As2) Ō(E)) where n1 + for 1,...:72.
X nu matrix, though not
42

---

Published as a conference paper at ICLR 2021
to generate a game with differential Stackelberg equilibrium that is not stable with respect to -x) given a choice of beforchand.
This result contrasts with that of Theorem [ in the following fundamental way. In the proof of Proposition I.I] т is fixed and then the game is constructed, whereas in Theorem I the game is fixed and then the conditions from (50) with c fixed to be an arbitrary positive value. It can be verified that spce(J, (x", ; v²)) C C for all > 2/e. This means that given the differential Stackelberg equilibria in this game construction, there is indeed a finite r such that the equilibrium is stable with respect to ă (2) for all continuum of games for which a differential Stackelberg equilibrium is unstable with an improper choice of finite learning rate ratio т. On the other hand, Theorem T is proving that given game with differential Stackelberg equilibrium, there exists a range of suitable finite learning rate ratios such that the differential Stackelberg equilibrium guaranteed be stable.
7 given. To illustrate this point, consider the game construction
(r", 20). Put concisely, Proposition J.1 is showing that there is exists
We now move to examining the portion of Proposition 27 from Jin et al. (020)) which says that given any fixed and finite timescale separation > O, a zero-sum game can be constructed with a critical point that is not a differential Stackelberg equilibrium which is stable with respect to the continuous time limiting system of T-GDA given by 1 = gA)
Proposition J.2 (Rephrasing of Jin et al. 2020 Proposition 27(b)). For any fixed T, there exists zerv-sum game G = (J- such that spec(J+(x*)) C C+ for critical point x² satisfying g(x") = O that not a differential Stackelberg equilibrium.
In a similar manner as following Proposition J.1 we now explain the proof of Proposition J.2 and then contrast the result with Theorem Again, consider any > 0, along with the game construc- tion
f(z v) 2 + 22/c2191 + (c/2)yî 22/2 2- 2/ cy2
(51)
At the unique critical point (x* y²) (0,0), 0). the Jacobian of the dynamics is given by
2
0
2 2
0
0
-1
0
2/(
J+ 1=(x"v²))
2
0
TC
0
0
-E
0
2TE
Observe that (x", y*) is neither differential Nash equilibrium nor a differential Stackelberg equi- librium since fff(=", yy" ) (2, -1) and - D3"f(",, = diag(c, 2c) are both indefinite. The
spectrum of the Jacobian
2 2 TE 222 12TE + -1+ 2re + v4r2e² 12Te + I
spec(Jr v²
2
2
Now, fix 7 as any arbitrary positive value, then consider the game construction from (5T) with e = 1/T. For the fixed choice of T and resulting game construction given the choice of e, we have that
(pec(J,(z'.v")) +1 iV7) C..
(1
This indicates that the non-equilibrium critical point is stable with respect to the dynamics -2, where z = (x, y) for the given choice of r. Similar to the proof of Proposition J.1] since the choice of T was arbitrary, the procedure to generate game with a non-equilibrium critical point that is stable with respect to å = (2) is valid given choice of beforehand.
The key distinction between Proposition J.2 and Theorem is analogous to that between Proposi- tion and Theorem Indeed, the proof and result of Proposition rely being fixed followed by the game being constructed. On the other hand, in Theorem 2 the game is fixed and then the con- ditions 7 given. To make this clear, consider the game construction from (51) with fixed to be an arbitrary positive value. It turns out that (pec(Jr(x*,,)) & C2 for all 2/e since
2 TC V22² 12tc + 4
Re
< O.
2
As a result, given the unique critical point of the game there is finite To such that the non- equilibrium critical point is not stable with respect to á -xzg(z) for all (Ta, In
43

---

Published as a conference paper at ICLR 2021
summary. Proposition J.2 is showing that there is exists continuum of games for which non- equilibrium critical point is stable given an unsuitable choice of finite learning rate ratio т. In contrast, Theorem is showing that given a game with non-equilibrium critical point, there exists a range of finite learning rate ratios such that it is not stable.
To recap, the diseussion in this section is meant to explicitly contrast Proposition 27 from the work of et al. (2020) with Theorem I and Theorem 2 since they may potentially appear contradictory each other without close inspection. The result of Jin al. (2020) shows that (i) given fixed finite learning ratio, there exists a game for with a differential Stackelberg equilibria that is not stable and (ii) given fixed finite learning ratio, there exists game with non-equilibrium critical point that is stable. From a different perspective, we show that (i) given a fixed game and differential Stackelherg equilibrium, there exists range of finite learning rate ratios for which the equilibrium is stable (Theorem (T) and (ii) given fixed game and non-equilibrimm critical point, there exists range of finite learning rate ratios for which the critical point not stable (Theorem
K EXPERIMENTS SUPPLEMENT
In this section we present several experiments not included in the body of the paper along with sup-
plemental simulation results and details for the experiments presented in Section We numerically investigate Example]] D in Section K.I and a game similar to that from Example
2
in Section K.2, Af-
ter that, we investigate a polynomial game with multiple equilibria in Section K. We study torus
game in Section K.4 and examine the connection between timescale separation and the region of
attraction. Then, in Section K.5 we return to the Dirac-GAN game and consider the non-saturating objective function. In Section K.6] we explore a generative adversarial network formulation using the Wasserstein cost function with a linear generator and quadratic discriminator for the problem of learning a covariance matrix. We finish in Section K.7 by presenting further results and details on our experiments training generative adversarial networks on image datasets along with additional generative adversarial network experiments parameterized by neural networks with mixture of Gaussians. Code for the experiments is included in the supplemental material.
K.1 QUADRATIC GAME: TIMESCALE SEPARATION AND STACKELBERG STABILITY
We revisit the game from Example that demonstrated there exists differential Stackelberg equilibrium that are unstable for choices of the timescale separation т. To be clear, we repeat the game construction and some characteristics of the game. Let us consider the quadratic zero-sum game defined by the cost
0
-
0
f(11, x2)
1
x1
20
(52)
2
D2
v
[2
where 31, x2 E R.2 and > 0. The unique critical point of the game given by x (= a differential Stackelberg equilibrium. The spectrum of the Jacobian evaluated the equilibrium is given by
(0.0)
spcc(J+(x*)) u22 1 47 87 +1+1) 1), v(r - 2 V72 12r + 4)
4
4
As mentioned in Example turns out that spec(J, C only when 7 E (2, oc). We remark that we computed r* using the theoretical construction from Theorem and found that it recovered the precise value of 7* 2 such that the equilibrium is stable for all T (r", oo) with respect to the dynamics f = gA,g(x) In the experiments that follow, we consistently observe that the construction of 7*
* from the theory tight.
4 and simulate T-GDA from the initial condition (zf, z.)) (5, 3, 2) with 71 = 0.0005 and r E {2, 2.5, 5, 10). In Figures 4a and 4b we show the tra- jectories of the players coordinate pairs (I11, T21) and (I21, T22), respectively. We observe that T-GDA cycles around the equilibrium with - = 2 since it is marginally stable with respect to the dynamics. For (2, oo), the equilibrium stable and 7-GDA ends up converging to it at rate
For this experiment, we select
44

---

Published as a conference paper at ICLR 2021
2.0
Of KS1
10
Org KS1
1.5
X51
0.5
11A 45
-15
0.0
Iterations
(c)
T= 2
2.5
T=
T=5
10
80
Img(4:3 Img(Ag)
Re(A2]
Imglspec(-)
Re(A.]
Img(4g)
2.
Re(Aal
Img(Aa)
0
10
16.5
20
40
60
10.0
Re(spec(/,)
(I)
Figure 4: Experimental results for the quadratic game defined in 52 of Section K. and presented in Example [ Figures 4a| and 44b show trajectories of the players coordinate pairs (I11 Ø21) and (I21.I22) for range of learning rate ratios, respectively. Figures 4c shows the distance from the equilibrium along the learning paths. Figures 4e] and the trajectories of the eigenvalues, the real parts of the eigenvalues, and the imaginary parts of the eigenvalues for the Jr J+(x") function of the respectively.
that depends the choice of т. We demonstrate how the convergence rate depends the choice of r in Figure by by showing the distance from the equilibrium along the learning path for each of the trajectories. The primary observation is that the cyclic behavior F-GDA dissipates as 7 grows and as a result the dynamics then rapidly converge to the equilibrium.
The behavior of the learning dynamics as function of the timescale separation т can be further explained by evaluating the eigenvalues of the game Jacobian at the equilibrium. We show the eigenvalues of the Jacobian at the equilibrium several forms in Figures 4e 41 and 4g Analyzing the spectrum, we are able to verify that for all E (2, oo) the equilibrium is indeed stable. Moreover, we see that the imaginary parts of the conjugate pairs of eigenvalues decay after r = and = 6, and then the cigenvalues of the conjugate pairs eventually become purely real at
1.87 and
т = 11.66, respectively. After the eigenvalues of a conjugate pair become purely real, they split so that of the cigenvalues asymptotically converges an eigenvalue of S (J (J(x)) by moving back along the real line, while the other eigenvalue tends toward an eigenvalue of -r -DD This occurrence is exactly what described in Section
immediate implication of Proposition when the eigenvalues of S (Jxx)) and 7 DD (x*) are distinct. The convergence rate is in fact limited by the eigenvalues splitting since as grows, the spectrum of the Jacobian is limited by the cigenvalues of the Schur complement which remain constant. A related open question centers on finding the worst case convergence rate as a function of the spectral properties of S (J(x)) and f² Finally, the evolution of the eigenvalues demonstrates that the rotational dynamics in 7-GDA vanish as the ratio between the magnitude of the real and imaginary parts of the eigenvalues grows.
function of the timescale separation
K.2 POLYNOMIAL GAME: TIMESCALE SEPARATION AND NON-EQUIL STABILITY
We now return to a game similar to that from Example 2 with a coueeuuiiirrium critical point which stable without timescale separation and becomes unstable for range of finite learning ratios with
45

---

Published as a conference paper at ICLR 2021
(x X22
DNE
Equillbiibr
1.5
X32
X22
1.0
0.5
DNE
0.0
Non-Equilibriu
-0.3
-1.0
-0.5
0.0
1.0
X11
X12
(a)
(b)
T= 0.75
T=2
T=5
t=
12
(c)
Re(A:)
Imgik Imgt4g)
60
Re(As)
Img(spec(-))
RelAs)
ImglAs)
40
Re(Ag)
Img(Aa)
Re(spec()-))
(e)
(f)
Figure 5: Experimental results for the polynomial game defined (53) of Section K.2 and presented
in Example 2 Figures 5a and 5b show trajectories of the players coordinate pairs (æ11: 2211 and (121, F22) for range of learning rate ratios, respectively. Figures Se (f|soow the trajectories of the eigenvalues, the real parts of the eigenvalues, and the imaginary parts of the eigenvalues for J+(x*) as function of the т, respectively where the non-equilibrium critical point.
multiple equilibria in the vicinity. Consider zero-sum game defined by the cost
f(z x2) ] (ii 22 + 1 J 2x 22 x22) (x11 1)2
(53)
+ की E (#1 1) (I2 1)2).
This game has critical points at (0. 0. 11, and (-4.73,0.2 -9.2277700 0.53). Among the critical points, only 1, and (-4.73.0.28. -92.47, 0.53) are game-theon tune-thhoreeicclly meaningful equilibrium. In fact, they each differential Nash equilibrium and are locally stable for any choice of r E (0, oc) as a result of Proposition F.1 On the other hand, the critical point x = (0, 0, O, 0) neither differential Nash equilibrium nor a differential Stackelberg equilibrium. However, is stable for E (0, and it is marginally stable for 7 2. In general, convergence to the non- equilibrium critical point x= in the presence of multiple game-theon thee--theoreticallyy meaningful equilibrium would be viewed undesirable. In fact, this is precisely the type of critical point that sophisticated schemes for converging only differential Nash equilibria or only differential Stackelberg equilibria seek to avoid (Adolphs et al. 2019: Fiez et al. 2020: Mazumdar et al. 2019: Wang et al.) (020). We show in this example that the simple inclusion timescale separation in gradient descent-ascent sufficient to avoid x² and instead converge differential Nash equilibrium.
Indeed, for all 7 E (2, oo) the non-equilibrium critical point x² is unstable with respect to -A) We simulate 7-GDA from the initial condition (xf, xz4) = (-1.5, 2.5, 2.5, 3) with 71 0.0005 and 7 E {0.75, 2, 5, 12}, where we use the superscript to denote the time index so as not to show the trajectories of the players coordinate pairs (I11, 221) and (I21, I222) respectively. We observe that 7- GDA converges to the non-equilibrium critical point x with 0.75 expected and the dynamics
be confused with the multiple indexes for player choice variables. In Baluuesssaaan5555
46

---

Published as a conference paper at ICLR 2021
(xf
500
400
200
DNE DSE
-11
150
10
10
0
0
11
10
X2
20
-12
-10
X1
(a)
(b)
A
125
Rc(A.)
A2
Re(A2)
img (ppe((/))
10
Inig(As)
Img(Ap)
75
0-
25
==0
60
-25
0
25
50
75
100
125
40
Re(spec(/))
T
(c)
Figure 6: Experimental results for the polynomial game defined in (54) of Section K.3 Figures 6a provides view the cost function - -f(11, along with the cost contours critical point locations. Figure 6b) shows trajectories of 7-GDA for range of learning rate ratios given an initial- ization around the differential Stackelberg equilibrium (zi, x5) (-11.03, 11.03)). Figures 6c and 6d show the evolution of the eigenvalues from J, (x*) function of 5 where x² is the differ- ential Stackelberg equilibrium (æt, 25)) = (-1..3 - 11.03).
move near and then cycle around it with 7 = since the critical point becomes marginally stable. However, for and 12. 7-GDA avoids the non-equilibrium critical point since it becomes unstable and instead the dynamics converge to the nearby differential Nash equilibrium. We show the eigenvalues of the Jacobian the non-equilibrium critical point xx (0, O, O, 0) in several forms in Figures Again, we observe that the eigenvalues quickly become purely real as grows and then they split, and asymptotically converge toward the eigenvalues of S (J(x)) and D fx=), Together, this example demonstrates that often there is a reasonable finite learning rate ratio such that non- meaningful critical points become unstable for G-GDA.
K.3 POLYNOMIAL GAME: VECTOR FIELD WARPING AND REGION OF ATTRACTION
Consider zero-sum game defined by the cost
f( x2) = - -0.0))))==--0-++++-t---a--11 (0.0127+0.0133) (00.3z + 23)² + (0.3z² + xz))))
(54)
The cost structure this game is visualized Figure 6a where we present a three dimensional view of -f(;x, x2) along with the cost contours and the locations of critical points. This game has eleven critical points including one differential Nash equilibrium and two differential Stackel- berg equilibria that not differential Nash equilibrium. The critical points that neither
47

---

Published as a conference paper at ICLR 2021
12
-22
12
-11
-10
12
11
-10
-12
-11
10
11
10
T=
1
T
T=
20
-15
X:
T=
[x] x1 (10.57. -.95
=x1xx) 11.03)
(xf.xf)
-.62)
Figure 7: Experimental results for the polynomial game defined in 54 of Section K.3 In Figure 7a we overlay the trajectories from Figure 6b| produced by T-GDA onto the vector field generated by the choice of timescale separation selection The shading of the vector field is dictated by its magnitude so that lighter shading corresponds to higher magnitude and darker shading corresponds to lower magnitude. Figure 7bb demonstrates the effect of timescale separation attractions around critical points by coloring points in the strategy space according to the equilibrium 7-GDA converges. We remark that areas without coloring indicate where 7-GDA did not converge in the time horizon.
the region of
differential Nash equilibrium nor a differential Stackelberg equilibrium are unstable for any choice of timescale separation т. The differential Nash equilibrium is (x,, = (10.57,-8.9) and it is stable for all (2)) = (-1.625, 1.625) and (sï, ( (T..03 -11.03) each is stable for all r E (1, oo). We computed r* for the pair of differential Stackelberg equilibrium using the theoretical construc- tion from Theorem [ and observed that it properly recovered 7" = 1 for each equilibrium as the timescale separation such that the continuous time system is stable for all we note that while the set of equilibrium follow a línear translation, this game is generic and the equilibria
(0, oo) by Proposition F.1 The differential Stackelberg equilibria are at
(r", (r", oc). Finally,
fact isolated.
In Figure 6b we show the trajectories of T-GDA with = 0.0001 and T (1, 20} given the initialization (x²,=²)) (-9, -9) the differential Stackelberg equilibrium (aī, =5) 1-11.03, -11.03). Moreover, in Figure 7a we overlay the trajectories on the vector field gener- ated by the respective timescale separation parameters. As expected, the choice of 1 results in trajectory that cycles around the equilibrium in closed curve since it is marginally stable and (x")") ) has purely imaginary eigenvalues. Notably, as т grows, the cyclic behavior dissipates as the timescale separation reshapes the vector field until the trajectory moves near directly to the zero derivative line of the maximizing player and then follows path along that line toward the equilib- rium and converges rapidly. The eigenvalues of (zx") as function of are presented in Figures 6c and [d As was the case for the previous experiments, we observe that after the eigenvalues be- come purely real grows, they then split and asymptotically converge toward the eigenvalues of S, (J((x)) and D (x*). is worth noting that much of the rotational behavior in the dynamics and vector field disappears result of timescale separation well before the eigenvalues become
48

---

Published as a conference paper at ICLR 2021
purely real; this seems to occur after the timescale separation is such that the magnitude of the real part of the eigenvalues is greater than that of the imaginary part.
Finally, in Figure 7b we demonstrate how the choice of timescale separation not only warps the vector field but also shapes the regions of attraction around critical points. The vector field is again shown for each 7 E {1, 5, 20). but now zoomed out to include each of the equilibria. The colors overlayed on the vector field indicate the equilibria that the dynamics converge to given an initialization at that position. Positions in the strategy space without color did not converge to an equilibrium in the fixed horizon of 75000 iterations with 71 = 0.001. This is explained by the fact that the dynamics are not guaranteed to be globally convergent and may get stuck in limit cycles or may simply move slowly for a long time in flat regions of the optimization landscape. We produced this experiment by running 7-GDA for dense set of initial conditions chosen uniformly over the space of interest. It is clear from the experiment that the choice of timescale separation determines not only the stability of equilibria, but also has fundamental impact on the equilibria the dynamics converge to from given initial condition example, given an initialization of (I1, = (-10, -2), the dynamics with T = 1 converge to the differential Nash equilibria at (21, [22 (10.57, -8.95.. However, for any > 1, the dynamics instead converge to the differential Stackelberg equilibrium at (I1, .22) = (-11.03, - -11.0) that significantly closer the initial condition. This example motivates future work on methods for obtaining accurate estimates of the regions of attraction around critical points and techniques to design in order to explicitly shape the region of attraction around an equilibrium of interest. We refer to the end of Section G for further discussion on potentially relevant analysis methods in this direction.
result of the warping of the vector field. As a concrete
K.4 LOCATION GAME ON THE TORUS
We use the example in this section further study the role of timescale separation the regions of attraction around critical points. Consider the zero-sum game defined by the cost
[ x2) = 0.15 cos(1)) + cos(11 - x2) + 0.15 cos(2))
(55)
This game can be interpreted as a location game on the torus. Specifically, the first player seeks to be far from the second player but near zero, while the second player seeks to be near the first player. This is non-convex game on a non-convex strategy space. The critical points are given by the se
{o: : g(x) = 0}- = {(0, 0), (H, T), (T, 0), (0, R), (-1.646, 1.449), (1.646, 1.496)).
The critical points (0, 0) and (T,, æ) are the only differential Stackelberg equilibrium and neither is a differential Nash equilibrium. The differential Stackelberg equilibrium at (0, 0) is stable for all T E (T" 0c) where -- = 0.74 and the differential Stackelberg equilibrium (T, x) is stable for all (r* 00) where = 1.35. The rest of the critical points are unstable for any choice of r. We remark that we computed n" for each differential Stackelberg equilibrium using the construction from Theorem T in Section and it again gave the exact value of 7" such that the system is stable for all r >T"
21, given the initializations (x))=2) = (2, -1) and (xf, = (1.9, (1.9,-2.) 2211) overlayed on the vector field gener- ated by the respective timescale separation parameters. We observe that as the timescale separation T grows, the rotational dynamics in the vector field dissipate and the directions of movement be- come sharp. As we mentioned in previous examples, T-GDA moves directly to the zero line of -D2f I22) and then along that line to an equilibrium given sufficient timescale separation. The warping of the vector field that occurs as a result of timescale separation impacts the equilibrium that the dynamics converge to from fixed initial condition and the neighborhood on which T-GDA converges to an equilibrium. In other words, the region of attraction around critical points depends heavily on the timescale separation T.
In Figure Sa show the trajectories of 7-GDA with 71 0.001 and
To illustrate this fact, in Figure 8b we show the regions of attraction for each choice of timescale sep- aration. The vector fields again shown for each E {1, 5, 10). but now with colors overlayed indicating the equilibria that the dynamics converge to given an initialization at that position. This
13 Note that hecause the joint strategy space is torus, (+T, .T) (F., tT), (T, 0) (-T, 0), and (0, (0) (0, m)
49

---

Published as a conference paper at ICLR 2021
x2
0
-2
T=1 1
T= 2
== 5
T= 10
(a)
0
T X1
7
T- 10
xxxxx)== (0.0)
(xI.x]) = (#m, 2
(b)
Figure 8: Experimental results for the torus game defined in (55) of Appendix K.4 In Figure Sa overlay multiple trajectories produced by r-GDA onto the vector field generated by the choice of timescale separation selection т. The shading of the vector field is dictated by its magnitude so that lighter shading corresponds to higher magnitude and darker shading corresponds magnitude. Figure [b) demonstratts the effect of timescale separation on the regions of attraction around critical points by coloring points in the strategy space according the equilibrium 7-GDA converges. We remark that areas without coloring indicate where T-GDA did not converge in the time horizon.
lower
experiment was generated by running T-GDA with a dense set of initial conditions chosen uniformly over the strategy space. Positions in the strategy space without color did not converge an equilib- rium in the fixed horizon of 20000 iterations with 71 0.04. This happens when 7-GDA is not ini- tialized in the local neighborhood of attraction around a stable equilibrium. For the choice of = 1,
(0,0) is the only stable equilibrium. However, as demonstrated in Figure Sa 7-GDA fails to con-
verge to the equilibrium from the initial conditions (xf. ag) = (2, (2.-1) and (x x.)) (1.9.-2.11 2211). This behavior is further demonstrated over the strategy space in Figure 8b and highlights the local nature of the guarantees since convergence is only assured given an initialization in a suitable local neighborhood around stable critical point. On the other hand, 7-GDA converges
equilibrium from any initial condition for 7 E {2, 5, 10} as can be seen by Figure 8b Notably, the equilibrium to which the learning dynamics converge depends give a concrete example, consider the initial conditions shown in Figure (xf xx2) = (2, -1) and (uf.29) (1.9. 2.1). For the initial condition (zf.x=9)
the timescale separation and initial condition. To
(2, 1),, 7-GDA converges to the equi- librium at (0, 0) for each E {2, 5, 10). Yet, for the initial condition (af, x (1.9. -2.1), 7-GDA converges the equilibrium [(0. 0). (T, (Ir, r)} for the respective choices of r E (2, 5, 10). In other words, the region of attraction around the critical points changes so that from a fixed ini- tial condition T-GDA may converge to distinct equilibrium depending on the initial condition. From Figure 8b we that the region of attraction around (xf.*%) (1.9.-2.1) grows from = 1 to T = and -= 4. but then shrinks at т = 10. This example highlights that timescale separation has fundamental impact the region of attraction around critical points and grows it is possible for the region of attraction around an equilibrium to shrink. Collectively, this motivates explicit methods for trying shape the region of attraction around desirable equilibria.
50

---

Published as a conference paper at ICLR 2021
10a
0.8
0.6
10-9
0.4
10
0.2
0.0
10 10
( (1g)
1
1|2
-0.2
LNNE
10-20
-0.50 -0.25 0.00
0.25
0.50
0.75
1.00
1000
2000
3000
4000
Iterations
(a)
(b)
T= -=1,p=00
0.3
8,
T 16, 0.3
T 1, ==
0.3
8.
0.3
Figure 9: Experimental results for the Dirac-Gard GANN game defined in (56) of Appendix K.5 Figure 9a shows trajectories of 7-GDA for E {1, 4, 8, 16] with regularization μ 0.3 and regularization μ 1. Figure shows the distance from the equilibrium along the learning paths. Figure Dd shows the trajectories of T-GDA overlayed on the vector field generated by the respective timescale separation and regularization parameters. The shading of the vector field is dictated by its magnitude so that lighter shading corresponds to higher magnitude and darker shading corresponds to lower magnitude.
with
K.S DIRAC-GAN AND REGULARIZATION: NON-SATURATING FORMULATION
In Section 5 presented experiments for the Dirac-GAN game studied by Mescheder et al.) (2017) using the original generative adversarial network formulation of Goodfellow et al. (2014). In this section, revisit the Dirac-GAN game using the non-saturating generative adversarial network formulation also proposed by Goodfellow et al. (2014). Recall that the zero-sum game which arises from the original objective with regularization μ is defined by the cost
f(0, = ((ww) + ((0)
2 2
As discussed in Section 5 the unique critical point of the game is (8","") = (0, 0) and it cor- responds to the local Nash equilibrium of the unregularized game and a differential Stackelberg equilibrium of the regularized game. Moreover, the equilibrium stable with respect to the conti- time dynamics for all 0 and μ 0 so that the discrete time update 7-GDA converges with a suitable learning rate
The non-saturating generative adversarial network formulation proposed by Goodfellow at. 22014)
in the context of the Dirac-GAN game corresponds to player maximizing E ((-0w) instead of min- imizing ((ww). This results in the general-sune game defined by the costs
w)) = (-f( (-[(-Ow)
(w) + ((0) w2 -((ww) ((0) + W2)
(56)
As shown by Mescheder et al. (0018), the unique critical point of the game remains at (#* (,") = 0). Moreover, it can be observed that J- (0", w²) in this formulation is identical to the game
51

---

Published as a conference paper at ICLR 2021
Jacobian for the Dirac-GAR Mrac-GGN, which is given by
( tH
J+ (00""")= = (0)
(57)
so this game is locally equivalent to the zero-sum game that arises from the original objective pro- posed by Goodfellow et al. (214)) This is despite the fact that the non non-saturating objective was motivated by global concerns (vanishing gradients early the training process) rather than local considerations. In Figure 2 we present experiments with T-GDA for the regularized Dirac-GAN game with the non-saturating objective and {(() = - f[1 + exp(-()), We observe similar behavior as the experiments with the standard objective and refer back to Section for the insights we draw from the simulation. This experiment is primarily included for completeness and to motivate our of the non-saturating objective in the generative adversarial networks experiments we perform on image datasets in Section 5
K.6 GENERATIVE ADVERSARIAL NETWORK: LEARNING A COVARIANCE MATRIX
We now consider a generative adversarial network formulation presented by Daskalakis et al. (2088) for learning a covariance matrix. This is simple example with degeneracies much like the Dirac- GAN game, but it can be generalized arbitrary dimensional strategy spaces and has served benchmark for comparing convergence rates in a number of recent papers on learning in games. Of- ten, the example is used to show that gradient descent- -eccentt cycles and converges slowly. However, by and large, timescale separation is not considered. We show that gradient descent-ascent con- verges fast in this game with suitable timescale separation and further explore the interplay between timescale separation, regularization, and rate of convergence. We primarily follow the notation of Daskalakis et al. (018) when describing the problem.
The objective of this problem is to learn covariance matrix using the Wasserstein GAN formula- tion. The real data æ is drawn from a mean- zero multivariate normal distribution with an unknown covariance matrix Σ. The generator is restricted to be linear function of the random input noise z ~ NNO, 7) and is of the form Gy (z) = -V2. The discriminator is restricted to the set of all quadratic functions, which we represent by Dw
x Wa. The parameters of the generator and the discriminator are given by W E Rddx and V E Rdxd respectively. For the given generator and discriminator classes the Wasserstein GAN game defined by the cost
S(V, W) = (o (a Wa) B V VVTTTWW WVz..
As shown by Daskalakis et al. (2018), the cost function can be simplified to be expressed as
S(V, W) ΣΣ
k=1
With this cost, the individual gradients for gradient descent-ascent are given by
gVV W) -- --W--=-VV.---VV'
From the individual gradients, it is clear that the critical points of the game are given by (V, W) such that VVT Σ and W + WT = O. Moreover, given the form of gVV W), the game Jacobian at any critical point (V*, W*) is of the form
DiaS(V*, W*) 0
J, (V* W
(VV ww*)
Consequently, the eigenvalues of the game Jacobian are purely imaginary and the critical points are not stable. To fix this problem, [Daskalakis et al.] (2018) regularized both the generator and discriminator. We only regularize the discriminator in this example. The cost function of the zero- sum game with regularization μ > is given by
f(V. W) = ΣΣ W
Σ ViL
Vm)
)
H "Tr(WTT) w). 2
(58)
k=1
The individual gradients for gradient descent-ascent in this regularized game are then
gVV w) = (- (- VVT) (w)
52

---

Published as a conference paper at ICLR 2021
10.
10-1
10-
10:1
10-1
10"1
10-
10
10
10
10"4
1000
2000
4000
1000
3000
4000
5000
1000
2000
3000
4000
5000
Iterations
Iserations
Iterations
(a) = 1, 1z
0.5
(b) 1, 0.75
(c) d 1,
40
25
RoCAi
Re(2.)
Re(Ag)
30
1mg
Re(A2)
25
RelAs)
20
-mn[hh]
Re(As)
Img(Ap)
20
Inig(As)
Ingffs)
20
10
10
-10
(d)
16a
10
100
10-2
10
10.9
1014
10-1
10"*
10-9
10
10-11
1000
2000 Iterations
4000
1000
1000
3000
5000
Iterations
Iterations
(g) /
(h) d 10, 11
d 20. lr
||z - W'
IIW W
==1
T=
==
10 T 25
(i Legend for Figures 10a
10b
10c
10g
10h
and
10i
Figure 10: Experimental results for the generative adversarial network formulation for learning a covariance matrix defined by the cost from (58) of Section K.6 Figures [0a TOb and 10c show
the distance from the equilibrium along the learning paths of 7-GDA with d 1. Figures 10d [0c]
and 10f show the trajectories of the eigenvalues of J,(x*) as function of the т, respectively. Figures 10g 10h and show the distance from the equilibrium along the learning paths of T-GDA with d 5, 10.20.
We begin by considering the simplest form of this problem, which that d 1. The critical points with this restriction are (V* W*) (a, 0) and (V*, W²) (-o, 0) and the game Jacobian evaluated at them is
0
20
(V (') = 2TO
TH
Each critical point is local Nash equilibrium of the unregularized game and differential Stackel- berg equilibrium the regularized game since fV3 W²) = μ and S (JV(", W+)) 40²/p > Furthermore, spec(J]+ W*)) = [( 22 16ra3) /22 so that each critical point is stable for all r (0, oc) and μ (0, oo) since spee(J, -w*)) suitably chosen learning rate 71, the discrete time update F-GDA locally converges to an equilib- rium. For this reason, focus studying the rate of convergence for the problem as function
C². Thus, given
53

---

Published as a conference paper at ICLR 2021
90
20
(a) d 1, 1z
(b) 1p 0.75
-10
20
13
(c) 14
Figure 11: Experimental results for learning covariance matrix defined by the cost from (58) of Section K.6 We overlay the trajectories produced by r-GDA onto the vector field generated by the choices of r and μ.. The shading of the vector field is dictated by its magnitude that lighter shading corresponds to a higher magnitude and darker shading corresponds to lower magnitude.
of timescale separation and regularization. Figures 10a equilibrium along the learning path of T-GDA with 1, 10, 25 given a fixed initial condition with learning rate Y1 0.001 and regularization μ [0.5, 0.75, 1). respectively. Moreover, Fig- ures 10d 10e and 10f show the trajectories of the eigenvalues for (V W as function for the regularization parameters μ {0.5, 0.75, 1). Finally, Figures 11a 1lb and I1c show the trajectories of T-GDA overlayed on the vector field generated by the respective timescale separation and regularization parameters.
10b and 10c show the distance from an
From the eigenvalue trajectories, we see that as / grows, the eigenvalues become purely real at a smaller value of Moreover, as μ increases, the magnitude of the real and imaginary parts of the cigenvalues decreases. We observe the effect of this on the convergence, where the dynamics do not cycles much for larger μ.. Again, see the trade-off between timescale separation, regularization, and convergence. For example, despite the eigenvalues being purely real with so that there is no rotational dynamics, the convergence slower than for μ 0.75 where there is some non-zero imaginary piece of the eigenvalues.
1 and 25
Figures T0g 10h and TOi show the distance from critical point along the learning path of 7-GDA with r E 1 5, 10, 25 given fixed initial condition with learning rate ? 0.001, regularization = 1, and the dimension
the problem among the set (5, 10, 20). respectively. The primary purpose of showing this set of results is simply be clear that the behavior for d 1, which is easier to explain and visualize, transfers over to higher dimensional formulations of this problem. This is to be expected since the problem dimension is not necessarily fundamental to the convergence rate, but rather it depends on the conditioning of Σ and each was chosen so that the behavior was comparable for each choice of dimension.
54

---

Published as a conference paper at ICLR 2021
K.7 GENERATIVE ADVERSARIAL NETWORKS PARAMETERIZED BY NEURAL NETWORKS
In this section, we provide a much more detailed discussion of our experiments training generative adversarial networks on image datasets than was included in Section 5 and also present more the results at greater depth. We also present experiments training a generative adversarial network with T-GDA to learn a mixture of Gaussians.
Background. The empirical benefits of training with timescale separation have been documented previously, For example. Heusel et al. (2017) showed on a number of image datasets that a timescale separation between the generator and discriminator improves generation performance as measured by the Frechet Inception Distance (FID). Since then significant number of papers have presented results training generative adversarial networks with timescale separation. Moreover, is common in the literature for the discriminator to be updated multiple times between each update of the gen- erator (Arjovsky et al. 2017). Indeed, it has been widely demonstrated that this heuristic improves the stability and convergence of the training process and locally it has similar effect as including timescale separation between the generator and discriminator. The disadvantage of this approach is that the number of gradient calls per generator update increases and consequently the convergence is then slower in terms of wall clock time when a similar effect could potentially be achieved by a learning rate separation between the generator and discriminator. We remark that it appears to be reasonably common for practitioners to fix shared learning rate for the generator and discriminator along with a pre-selected number of discriminator updates per generator update and not thoroughly investigate the impact timescale separation has on the training process.
The goal of our generative adversarial network experiments to reinforee the importance of the timescale separation between the generator and the discriminator as a hyperparameter in the training process, demonstrate how it changes the behavior along the learning path, and show that it is com- patible with a number of common training heuristics. This is to say that our goal is not necessarily to show state-of-the art performance, but rather to perform experiments that allow us to make insights relevant to the theory in this paper. We remark that our empirical work on training generative adver- sarial networks is distinct from and complimentary to that of Heusel et al. (2017) in several ways. The theory given by Heusel et al. (2017) only applies stochastic stepsizes, however in the exper- iments they implemented constant step sizes. We train with mini-batches and decaying stepsizes in our image dataset experiments. which does satisfy the theory we provide as detailed in Section [.] Moreover, by and large, the experiments by [Heusel et al. (2017) compare a fixed learning rate ratio between the generator and discriminator to multiple fixed shared learning rates for the generator and discriminator. In contrast, we fix learning rate for the generator and explore the behavior of the training process as the timescale parameter is swept over given range.
K.7.1 GENERATIVE ADVERSARIAL NETWORKS: MIXTURE OF GAUSSIANS
We now provide the results from training generative adversarial networks to learn a mixture of Gaussians. The underlying data distribution consists of Gaussian distributions configured in circle arrangement with means given by μ = [win(w), cos(w)) for w E {kx/4)k=0> each with covariance r²I where x² 0.05. Fach sample of real data given to the discriminator is selected uniformly at random from the set of Gaussian distributions. We train the generator using latent vectors = E iR sampled from standard normal distribution in each training batch. The batch size for each player in the game is 512. The network for the generator and discriminator contain two and one hidden layers respectively, each which contain 32 neurons and ReLU activation functions. The training objective is the non-saturating objective and we run experiments without and with the R1 gradient penalty proposed by MMschhder al. (2018) using parameter μ4 0.1. The generator learning rate is fixed to be 71 = 0.005 and the discriminator learning rate is fixed as 7/2 7?1 where we experiment with T E (4, 8, 16, 32, 64, 100). For each parameter choice (timescale separation 7 and regularization j1), the experiment is repeated with 50 random seeds. The training does not rely on any adaptive gradient methods (Adam, RMSprop, etc.) and is the 'vanilla' stochastic F-GDA dynamics. We evaluate the performance along the learning path by computing the KL-divergence between the generated data and the real data, where we sample 4096 data points from each.
The results of this experiment are presented in Figure 12 and the standard error of the means across the runs along the learning path without (μ = 0) and with regularization (μ 0.1) in Figures 12aland and 12h respectively. Moreover, Figures T2c and 12d
We show the mean of the KL-divergence
55

---

Published as a conference paper at ICLR 2021
Divergence
Divergence
0.4
0.4
0.3
0.3
0.2
0.2
10000
20000
30000
40000
50000
60000
10000
20000
300000
40000
50000
60000
Number Mini-Baton Updates
Number Mini-Batch Updates
(a) /r 0: Mcan KL Divergence
(b) μr 0.1: Mcan KL Divergence
0.7
0.6
0.6
KL Divergence
Divergence
0.5
0.3
0.0
0.0
40000
50000
10000
20030
40000
50003
Number Mini- Mini-Batch Updates
Number Mini-Batch Updates
(c) μ = 0: Median Divergence
(d) F 0.1: Median KL. Divergence
16
32
64
100
Figure 12: KL-divergence between generated and real data for mixture of Gaussians.
show the medians the KL-divergence across the runs without (μ+ = 0) and with regularization and 100 do
(u 0.1), respectively. From Figure [2a] we observe that the choices show on the plot since they perform poorly, which may be a result of equilibrium not being stable for т and numerically conditioning for 100. Furthermore, we see that timescale separa- tion improves the results up to reasonable timescale parameter and after which the performance degrades. Furthermore, Figure 12b reveals that the results are improved with regularization and we see that 100 ends up performing well, potentially since the regularization can alleviate some of the problems of numerical stability. In general, we draw similar conclusions from the median scores reported in Figures
12c and
12d
The primary purpose this experiment is to train generative adversarial networks parameterized by neural networks using 7-GDA without heuristics such adaptive gradient methods parameter av- eraging as is employed on the image dataset experiments from Section and expanded on further in Appendix K.7.2 Notably,
that consistent themes emerge that timescale separation improves convergence until hitting limiting value and regularization can improve the rate convergence but there is an interplay with the timescale separation.
K.7.2 GENERATIVE ADVERSARIAL NETWORKS: IMAGE DATASETS
now provide further details on the methods for experiments training generative adversarial networks with image datasets presented in Section 5 Jalong with more in-depth results.
Methods. We again note that we built experiments based the methods and implementa- tions of Mescheder et al. (0118) and used the publicly available code from the paper available at htttps://gituub com. LMeschedes GAN stability. We effectively only changed the learning rates, retained multiple exponential averages at once, and modified the updates to be simultaneous in the code. In Figure 17 we provide the network architectures from our exper-
56

---

Published as a conference paper at ICLR 2021
iments and in Figure 18 include the hyperparameters that were selected. The architectures are analogous to that reported in Mescheder et al. (2018), but scaled down since we run exper- iments with 32 x 32 3 images. For evaluation, computed the Frechet Inception Distance using 10k samples from the real and generated data. For both experiments and across the set of hyperparameters we performed the evaluation using a fixed random noise vector to make for an equal comparison and fixed set of real images which were randomly selected. The evalua- tion was done using the training data. We used the FID score implementation in pytorch available at htttts::/ /ightb.t.bb......g com mse i t w peterr/ptoocc-fft.
We train the generative adversarial networks with the non-saturating objective function and the R1 gradient penalty proposed by Mescheder et al. (2018) with regularization parameters μ E {1, 10). We note that the non-saturating objective results in a game that is not zero-sum, however it is com- monly used in practice and under the realizable assumptions it can be locally equivalent to the zero-sum objective as discussed in Section K.3] The theory we provide does not apply to using RMSprop, but it is ubiquitous in practice for training generative adversarial networks and we are interested in exploring the interplay of timescale separation with common heuristics to understand if similar conclusions hold when using them from the previous experiments regarding timescale separation with the 'vanilla' T-GDA dynamics. Moreover, we note that similarly [Heusel et al. (2017) and Mescheder et al. (2018) also rely upon Adam or RMSprop in generative adversarial experiments. A final heuristic and hyperparameter that we explore in conjunction with the timescale separation T that of using an exponential moving average to produce the model that is evaluated. This means that at each update k, given that the parameters of the generator are given by T1,k. the moving av- erage T& x + T1.A-1
3) is kept where 3 (0, 1). Experimental studies have shown that this heuristic can yield significant improvement in terms of both the inception score and the FID (Gidel et al.] [019a] Yazici et al., 2019). The success of this method is thought to be a result of dampening both rotational dynamics and the noise from the randomness in the mini-batches of data.
Experimental Results. We run the training algorithm with the Iearning rate ratio belonging to the set {1, 8} for CIFAR-I0 and {1, 4, 16} for CelebA along with the regularization pa- rameter μu belonging to the set (1, 10). For each choice of and Jr, retain exponential moving averages of the generator parameters for 3 E (0.99, 0.999, 0.9999}. The training process is repeated 2 times for each hyperparameter configuration in the CIFAR-I0 experiments and the experiments with CelebA are simulated once. The performance is evaluated along the learning path at every 10,000 updates in terms of the FID score. We report the mean scores and the standard error of the mean over the repeated experiments for each dataset. The FID score is such that a lower score beats higher score. The experiments are computationally intensive which limits the number of repeats of experiments that can be simulated, however, we observed that the scores were quite consistent between random seeds particularly with exponential averaging of the parameters. We run the ex- periments with μ = for 150k mini-batch updates and the experiments with μ 10 for 300k mini-batch updates.
The results for each dataset across the hyperparameter configurations are presented in numeric form in Figure 15] Figure 16 shows some generated samples selected at random for each dataset with the hyperparameter configuration that performed best in terms of the FID score at the end of the training process. We now describe the key observations from the experiments for each dataset.
CIFAR-10. The FID scores along the learning path for CIFAR-I0 with = 10 and = 1 are presented in Figures 13a and 13b respectively. The corresponding scores in numeric form given in Figures 15a 15c and 15e for 10 at 150k iterations and μ = 1 at 150k and 300k iterations, respectively. To begin, we observe that the exponential moving average significantly improves performance, and of the parameters considered, 3 0.9999 performed best. This may be a result of removing noise as mentioned previously or potentially could be from dampening oscillatory behavior in the dynamics. Moreover, we that timescale separation also has a significant impact on the FID score of the training process. Indeed, even selecting 7 = 2 versus T = 1 can yield an impressive performance gain. In this experiment for each regularization parameter, т 4 converges fastest and performs the best. We see that T = 2 outperforms т = 8 when μı = 10 and the relationship is flipped when viewing the evaluation at 150k updates with μ = 1 and then returns back when looking at the evaluation at 300k updates. The choice of T = performs the worst for each regularization parameter by wide margin. Finally, observe that the performance with
57

---

Published as a conference paper at ICLR 2021
55
10
11
12
13
15
16
11
12
34
10
13
15
0.99
==0.999
8
0.9999
Number Mini-Batch Updates
(a) μr
10
25
30
30
20
25
B 0.99
= 0.999
0 0.9999
Namber of Mini Datch Updates 10k
(b) p
T=2
T=
Figure 13: CIFAR-I0 FID scores with regularization μ 10 in Figure 13a and μ
1 Figure 13b
regularization μ 1 is much better than with regularization = 10 for each timescale separation parameter and exponential averaging parameter.
CelebA. The FID scores along the learning path for CIFAR-10 with μ 10 and μ
presented in Figures 14a and 14b respectively. The corresponding scores numeric form are given in Figures 15b 13d and [5f for μ 10 150k iterations and μ 1 150k and 300k iterations, respectively. In this experiment we observe that while the exponential moving average was for CIFAR-10. It is not entirely clear if this
helps performance, the gain is not as drastic is a consequence of the scores being lower or something fundamental to the optimization landscape and dynamics for the dataset. The timescale separation combination with the regularization again has major effect on the the FID score of the training process in this experiment. For regularization and
== 10, the timescale parameters of wide margin, again highlighting that timescale separation can speed up convergence until a certain point where it can potentially slow down owing to the effect on the conditioning locally. A similar trend can be observed with regularization μ 1, but with = 16 performing closer to 7 4 and = 8. For each regularization parameter and timescale parameter, we see that performs the best. We again observe in this experiment that for all timescale separation parameters, the performance is significantly improved with regularization = as compared with f 10. This once again highlights the importance of considering how this the hyperparameters of regularization and timescale interact and dictate the local convergence rates.
outperform 7 1, T 2, and 16 by
the problem
Summary. In summary, we took a well-performing method and implementation for training gen- erative adversarial networks and demonstrated that timescale separation is an extremely important, and easy to implement, hyperparameter that is worth careful consideration since it can have major impact on the convergence speed and final performance of the training process. Interestingly. the conclusions we draw are in line with the insights drawn from the simple Dirac-GAN experiment in Section 5 and from the mixture of Gaussian experiments from Appendix K.7.1 In particular, timescale separation only speeds up to convergence until hitting a limiting value and there a key interplay between timescale separation, regularization, and convergence rate.
58

---

Published as a conference paper at ICLR 2021
35
30
25
10
21
12
23
15
16
11
12
15
34
10
13
0
B
0.999
8
= 0.9999
Number Mini-Batch Updates
(a) μr
10
25
20
R10
10
25
30
10
20
25
B
0.99
B
0.999
B 0.9999
Namber of Mini Datch Updates 10k
Figure 14: CelebA FID scores with regularizationy: 10 in Figure 14a and μ
1 in Figure 14b
T/
0.99
0.999
0.9999
0.99
0,999
0,9999
16.08 + 0.44
14.9
0.26
14.63 + 0.26
39.18 1,23
37.55
1.27
37.04
1.46
2
12.46 1 0.05
11885 1 0.11
11.72 1: 0.11
29.33
0.65
27.84
27.14
0.34
4
11.24 + 0.13
10.9 + 0.12
10.72 + 0.13
27.91
0.17
27.14
0.22
26.26 0.25
8
10.62 1 0,22
10.16 1 0.25
10.08 + 0.25
30,99
29.86
29.07
16
12.4
0.28
11.64 : 0.05
11.22 + 0.07
(a) CIFAR 10 FID at 150k updates with
10
(b) CelebA
150k updates with J
r/33
0.99
0.999
0,9999
0.99
0.999
0.9999
13.98 + 0.51
13.38 : 0.33
13.13 1 0.29
28.87 1 0.92
27.47 1 1.14
26.69 1 1.02
2
10.51 + 0.28
10.29 + 0.32
10.33 + 0,36
24.18 + 0.28
22.65 + 0.15
21.63 +: 0.12
4
9.01 +: 0.27
8.83 -: 0.25
8.78 4: 0.26
22.38 + 0.36
21.05 1 0.21
20.12 1: 0.13
8
8.32 1 0.1
8,04 2 0.14
7.98 1 0.15
22.74 + 0.15
21.71 + 0.11
20.72 + 0.08
16
8.47
0.04
8.19 0.07
8.13 + 0.07
(c) CIFAR 10 FID at 150k updates with
(d) CelebA FID at updates with μ
T/
0.99
0.999
0.9999
T 3
0.99
0.999
0.9999
9.16 + 0.29
8.77 + 0.25
8.52 + 0.22
24.46 + 0.32
23.14
21.59 0.5
2
7,22 = 0.11
6.91 4 0.19
6.82 = 0.18
21.37 1 0.11
19.51 + 0.07
18.08 1 0.19
4
6.47 - 0.13
6.2 0.11
6.07 = 0.10
20.75 1 0.19
19.08 1 0.08
17.61 1 0.18
6.25
5,95 - 0.05
5.81 : 0.05
21.94 + 0.16
19.87 + 0.1
18.64 + 0.08
16
6.65
= 0.12
6.35 = 0.11
6.17 = 0.06
(e) CIFAR-10 FID 300k updates with μ
(l) CelebA FID at 300k updates with
Figure 15: FID Scores on CIFAR-10 and CelebA.
59

---

Published as a conference paper at ICLR 2021
(a) CIFAR- 10 generated sample images
(b) CelebA generated sample images
Figure 16: Generated sample images with r 4 and B 0.9999
Layer
Output Size
Filter
Fully Connected
512 4
206 + 512.4.0
Layer
Output Size
Filter
Reshape
Conv2D
64 x 32 32
3 64
Resnet-Block
61 x 32 x 32
61 61 61
Resnet Block
256 4
512 - 256 + 256
Avg-Pool2D
64
NN-Upsampling
256 x
Resnet- Resnet-Block
128
16
64
128
NN-Upsampling
Resnet-Block
Resnet-Block
128
64 16 16
128 x 8
x
256 + 128 -> 128
64
Resnet-Bluck Blick
Avg. Nyg-Poo12D
256 x 8 x
128 8 8
128 - 128 - 256
Avg-Poo12D
256 x 4 x
NN- Upsampling
64 32 32
Resnet-Block
256 - 256 512
Resnet Block
64 32 32
64 - 64 - 64
Fully Connected
512 4-2-4-4
512 512-4-4-1
Conv2ID
3 x 64 x
64
+ 3
Discriminator Network Architecture
(a) Generator Network Architecture
Figure 17: Network Architectures for GAN experiments on CIFAR-10 and CelebA
Hyperparameter
Value(s) NSGAN
Objective
Batch Size
64
Latent Distribution
R236
Generator Learning Rate
CIFAR- 10: 0,0001; CelebA: 0.00005
Timescale Sepuration T
CIFAR 10: (1, 4, 8); CelebA: 21, 4, 16)
Learning Rate Decay
(1 x) 0.000
Optimizer
RMSprop
RMSprop Smoothing Constant a
0.99
RMSprop Regularization μ
10-6
[L. 10]
Parameter
0.999, 0.9999
Figure 18: Hyperparameters for GAN experiments on CIFAR-10 and CelebA
L ALTERNATIVE PROOF OF THEOREM VIA T" CONSTRUCTION FROM THEOREM
In order to highlight the utility of Theorem along with future directions of obtaining values of T* for structured games, we revisit the proof of Theorem 3 and derive the result directly from the construction. The purpose of this section is to illustrate that the structure of equilibria considered in Theorem 3 can be exploited to obtain the value of r" for the entire class of games using properties of the Kronecker product and sum.
Consider the generative adversarial network example under Assumption Then, we can show precise from the construction that for all games of this class that 7" 0 as long P 0. Fix
60

---

Published as a conference paper at ICLR 2021
regularization parameter μ 0. Then,
0 -B 7(uR+0)
Au
A12
J -,,,((z²))
TBT
-TA
T
Note that A22 < and A11 is the zero matrix and
$ = B ((JR++C) + = A12 11222-44 1 <0
by Assumption Now, we can conclude for this entire class of games that precisely because has positive real roots. Indeed, to start recall from the proof that we need to find
- (An @ In + M))
max
where
M1 = -2H (- 1220 @ n2n (A2 A @ ) Haz
and
M2 Ln, X A - -2( A H (S BS,) (Ln, @ A22
Plugging in the generative adversarial network parameters we see that we need
max (-M2
where
Mi = 21= (B (n.) (pR C)) @ Hnn <0
and
M2 = I, @ (uR CC @ ( Hn,
(B(uR+ B B (In, & BBuR++CT
For later use, let us define
M3 2(In @ (xR+C))
(B(uR+C)-1 0 BBuR+++) (B(uR+C)-BBT-1111 (In, @ B(uR-C)-1)
=-2m,, & (HR + BB) (H, (B(uR (B) @In
+h, @ B(uR + C Hn,,) )H,,
(In, @ B(uR+C)-
Hence, as long M2 0 know that 0. Here is where from Magnus (1988) on the and @ operators. Specifically, let us use the property that H (G & In, Hn. = H (In, & G)H,, H (Ln, @ G G @ In Hn, for a matrix G which in turn implies that
exploit the properties
(H (T,, 8 H,H,,,, ) = 2H (I, @ G G - to get the following:
2H, C) ( -
( (Ing @ B(RR+ M B(uR+C)+BBB
Hence,
M3 (In, ② (mR & B(uR+C) & B(uR+C)-)
- (In, 2 (uR+ (xR+C)- & [B @ B(uR+C)
(Tn, 8 (uR+C) (B(uR (B & B(uR+0)-1
-In, & (I, & B(uR B(uR+C)-) -)-1)
=-(n, @ (nR +)
which clearly holds since B is full rank in general by Assumption [ for which it is necessary that n2 2 n1/2 by Proposition E.1
61


Reviews:
[{"review_id": "yP-fM74kyAS", "reviewer": "AnonReviewer3", "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": "The main result of the paper states that a strict local minmax point is a stable critical point of t-GDA for some large enough t, and that any non-strict local minmax can be made unstable by s-GDA if we choose s large enough.\n\n\n-Major issues\n\nMy greatest concern is that the first part of the main result, that a strict local minmax is stable for t-GDA with all large, but finite t, is already known (Jin et al. 2020). Specifically, the proof of Lemma 40 in (Jin et al. 2020) shows that for all large enough finite t, the Jacobian of t-GDA only has eigenvalues whose real part is smaller than 0, which then implies the stability of t-GDA for a finite t. \n\nFrom what I can see, the reason why Jin et al. 2020 stated their results in terms of infinite timescale separation is because they did not have a uniform bound on how large the timescale t should be, and therefore in general it can be made as large as possible (but finite). The proof in the current submission has exactly the same feature: for every game, there is a finite t that makes t-GDA stable, but in general this t can be made arbitrarily large. It seems to me that the authors have not qualitatively improved over (Jin et al. 2020) (although I believe the bounds in this paper are tighter).\n\nIn the same vein, the converse statement also more or less appeared in (Jin et al. 2020); see the proof of Theorem 28, p.24-25 therein.\n\nDue to the above, I cannot see the claimed novelty of providing the first finite timescale separation for GDA, hence my rating. I'm willing to change my score should the authors convince me that I have misunderstand something.\n\n\n-Minor issues\n1. The authors claimed that \"On the empirical side, it has been widely demonstrated that timescale separation in gradient descent-ascent is crucial to improving the solution quality when training generative adversarial networks.\" I believe this is an overstatement of what we currently know about GANs; see \n\nhttps://arxiv.org/pdf/1711.10337.pdf\n\nfor a comprehensive empirical study of the effects on the timescale for GDA, which is not as conclusive as the authors stated. I would therefore suggest to tone down the sentence.\n\n2. Appendix B.3 is quite weird. F(x_k) here should be a vector-valued mapping but the authors seem to view it as a function. Also, by F(k) = O(M^k), did the authors mean ||x_{k+1} − x*|| = O(M^k)?\n\n\n----\n\nPost-revision evaluation:\n\nThe authors have modified the statements of the main theorems as well as including a more detailed comparison to previous works, which clarifies my concern. I have thus increased my score. \n\nThe technical contributions bring new insight into the studying of scale separation of GDA, and enables a tight characterization of many toy examples. I believe these are solid contributions and should be valued.\n\nOn the down side, I'd like to point out that the \"practical implication\" in this paper is a bit of stretch since the ImageNet experiments are run with RMSprop, whereas the analysis of this paper is highly specialized to GDA. \n\nOf course, studying adaptive algorithms in min-max games is exceedingly hard and well beyond the scope of this paper. What I recommend the authors is then:\n\n1. Explicitly notify the readers of the difference between RMSprop and GDA.\n\n2. Find a nontrivial but simple example where 1-GDA provides an okay baseline (say 7-layer CNNs for mixture of Gaussians or MNIST). Increase the time scale to show if it exhibits a similar behavior that a small $\\tau$ gives the best result. This is directly verifying what the theory is saying, and hence feels more valuable to me.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "juhaQEPLmZG", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Motivated by the many applications of min-max optimization problems in Machine Learning, the authors examine the effect of using different learning rates for each player in Gradient Descent Ascent (GDA) for non-convex non-concave optimization problems. Prior work has already established that making the learning rate of one player infinitely larger than other player's learning rate alleviates the cycling problems of GDA and makes game-theoretically meaningful equilibria the only asymptotically stable fixed points. The main contribution of this work is that it proves that we can get the same stability guarantees while keeping the learning rates of both players finite. This is crucial for practical applications where using unbounded learning rates in not an option. The authors employ this result to prove a variety of local convergence results in both deterministic ans stochastic settings.\n\nPros:\n1) The finite time scale separation is necessary in order to make the theoretical intuitions in prior work applicable for practical problems like trainings GANs. \n2) The proof techniques used for this separation results are, to the best of my knowledge, significantly different and elaborate than the ones used in prior work (Jin et al., 2020).\n3) The theoretical findings are complemented with empirical evaluations both on small min-max problems and on complex ones like training GAN architectures. \n\nCons:\nTheorem 28 in the arxiv version of Jin et al. 2020 does not explicitly reference the existence of a finite time scale that satisfies their inclusion results. However,  it is clear from the proof of Theorem 28 on page 24 that such a finite time-scale separation exists even though they do not provide an explicit formula for it.  At least for one of the inclusion statements they explicitly mention that it holds for $\\epsilon < \\epsilon_0$  for some $\\epsilon_0$ where $\\epsilon$ corresponds to $1/\\tau$.\n\nOf course the result of the authors gives a more direct construction of the threshold $\\tau^*$ by reducing the search for it to an eignenvalue problem. From a practical standpoint though, both results are existential. Neither proof approach gives particular intuition on how this time scale can be found in a computationally efficient way.  The added value of leveraging an array of mathematical tools to provide this explicit construction is unclear to me. \n\nGiven the above concern and that the convergence results essentially leverage the asymptotic stability properties provided by Theorems 1 and 2,  I am assigning a weak reject score. However, I am willing to substantially increase my score if the authors address the above concern. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "b1Hy1zNAOmS", "reviewer": "AnonReviewer1", "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": "The paper studies  the local asymptotic stability of a specific class of solutions points, referred to as strict local minmax equilibria (or differential Stackelberg equilibria), in the case of Gradient Descent-Ascent Dynamics with a finite time-scale separation. The time-scale separation (\\tau) is being captured by the ratio of the step-sizes between the min and max agents respectively. Recently, Jin et al. showed the set of asymptotically stable critical points of gradient descent-ascent coincide with the set of differential Stackelberg equilibrium as the time separation goes to infinity. The paper shows that an infinitely large separation is not needed and some finite but large enough separation suffices.  The paper provides a close analogue of another previous result by Mescheder about local stability of gradient descent dynamics in GANs under strong technical assumptions. The paper ends with GAN experiments where \\tau=1, 2, 4, 8 are tested and the performance seems to peak at 4. \n\nThe paper performs a detailed theoretical analysis of the coupling between GDA and diff Stackelberg equilibria. Although this is positive, the results are not particularly surprising given the prior work. The writing of the paper could also be significantly improved.\n\nOne issue that I had reading the paper is that at times and especially in the introduction the \ntreatment of (asymptotically stable), stable, unstable fixed points seem to be a little ambiguous.The paper only formally defines locally exponentially stable equilibrium in the preliminaries which is a notion that is not used in the introduction. I think it is important to set early on a clear terminology that is consistent throughout the whole paper. \nI am also a bit confused about some statements in the paper about which type of solution concepts are game theoretically meaningful. The paper seems to state that any critical point that does not satisfy the definitions of differential Stackelberg equilibria lack game theoretic meaning.  From the paper\n\nthe stable critical points of gradient descent-ascent coincide with the set of differential Stackelberg equilibrium as \\tau goes to infinity. All ‘bad critical points’ (critical points lacking game-theoretic meaning) become unstable and all ‘good critical points’ (game-theoretically meaningful equilibria) remain or become stable as \\tau goes to infinity.\n\nThis seems like a strong statement. It seems to me that min-max solutions of bilinear zero-sum games does not satisfy the differential Stackelberg definition. Such statements would imply that min-max solutions are 1) bad critical points and 2) lack game theoretic meaning despite being the golden standard of a solution concept in game theory. \nMaybe I am missing something here? \n\n[1] has recently shown that alternating GDA with fixed time-separation does not converge in the case of bilinear zero-sum games but is instead recurrent with the min-max equilibrium being stable but not asymptotically stable. This seems to be exactly the setting that you are studying. How are the results of [1] connected to yours? I think that due to the tight match between the two settings a thorough discussion is needed. \n\nThe definitions of differential/strict Nash/Stackelberg equilibria are two of several alternative definition/solution concepts that have only been recently introduced in the context of non-convex non-concave games. The paper should compare and contrast to other notions ideas  (e.g. proximal equilibria are only mentioned briefly [2], see also [3], [4]).\n\n Although one should of course not expect a global convergence as such a result would be too ambitious, the title could be interpreted as such a result by non-specialists. I think it might be better if the term local analysis is used instead. A more thorough discussion about non-convergence results for GDA and variants in zero-sum games could be also helpful [1,3,5-8] to dispel any possible confusion.\n\nIn terms of the experimental results why do the simulations stop with \\tau=8? The theoretical results as well as the prior work by Jin et. al are supportive of arbitrary large \\tau. What happens e.g. for tau= 2^4, 2^8, .... It already seems that performance starts dropping for \\tau>4. Does this trend continue? Does the performance have a unique peak? or does it fluctuate?\nThe regularization results (Theorem 3) remain true even for \\tau<<1 e.g. \\tau = 2^{-4}, 2^{-8}, ... \nWhat would experiments show for such \\tau under regularization?\n\n\n[1] Bailey et al. Finite Regret and Cycles with Fixed Step-Sizevia Alternating Gradient Descent-Ascent. COLT 2020\n[2] Farnia et. al Do GANs always have Nash equilibria? ICML 2020\n[3] Vlatakis-Gkaragkounis et al. Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games. NeurIPS 2019.\n[4] Zhang, et al. Optimality and Stability in Non-Convex-NonConcave Min-Max Optimization. arXiv e-prints, art. arXiv:2002.11875, February 2020.\n[5] Mertikopoulos et al. \"Cycles in adversarial regularized learning.\" Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2018.\n[6] Cheung et al. \"Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games.\" arXiv preprint arXiv:1905.08396 (2019).\n[7] Letcher \"On the Impossibility of Global Convergence in Multi-Loss Optimization.\" arXiv preprint arXiv:2005.12649 (2020).\n[8] Hsieh, et. al. \"The limits of min-max optimization algorithms: convergence to spurious non-critical sets.\" arXiv preprint arXiv:2006.09065 (2020).", "extra_scores": {}, "extra_text": {}}, {"review_id": "EqSzjbhJarP", "reviewer": "AnonReviewer2", "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\nThis paper studies the stable points of gradient descent ascent with different step-sizes. \nRoughly, this paper's main result is that for any fixed point for the GDA dynamics, that point is stable for GDA with a large enough timescale separation if and only if it is a local Stackelberg equilibrium.\n\nThis result is quite intuitive since a similar result has been proved by Jin et al. 2020. (the timescale had to go to infinity). Though, proving such a result for a *finite* timescale separation is a major improvement and is related to practical significant considerations. \n\n## Pros and cons\nStrengths:\nthe work is well motivated, and overall the paper is well written. Though if I think some of the technical aspects could be improved. \nThe results may interest the community.\nThe theoretical tools introduced could be used in other theoretical work. \n\nweaknesses:\nSome of the theory sections could be more developed to build intuitions on the phenomenon going on. It seems really hard for me to follow the current proof sketches since many notations are not properly introduced (or at least any intuition about what they mean is proposed). (see my section on questions/ comments)\nThe experiments are not really related to the theory. (see my section about experiments)\nI have some technical concerns and questions (I would be glad if the authors can answer them; see my section on questions)\nThe conclusion is overstating the results of the paper. \n\n## Overall review\nOverall, this paper is a good paper that should be accepted if the authors fix some statements in the conclusion section and answer my questions about the theory. Also, the experimental section could be improved (not by running more large scale experiments but by more related to the theory presented)\n\n## Questions and comments (by decreasing order of importance):\n\n### technical question\nThe most important question I have regards the guardian map you use. In the proof sketch of Theorem 1 where you state that the map $\\nu(\\tau) := det(-(J_\\tau \\oplus J_\\tau))$ is a guardian map of $\\mathcal{S}(\\mathbb{C_-^\\circ})$ but if we look at lemma C.1 the result boils down to the fact that the eigenvalues of $A \\oplus A$ are $(\\lambda_i + \\lambda_j)$ with $\\lambda_i, \\lambda_j \\in Sp(A))$.\nHowever, it means that if $A$ has a single eigenvalue in $\\mathbb{C_-^\\circ}$, then $\\nu(A)$ is non zero. Some arguments should be added (since $A$ is a real matrix, the non-real eigenvalues are complex conjugates) to justify that the only problematic case is when $A$ has $0$ as an eigenvalue. One quick fix would be to consider $\\nu(A) := det(A)det(-(A\\oplus A))$ as guardian map$. But I do not know how it would change the derivations in the proof of claim C.1. \nI am quite novel with these notions, so my questions are: Am I missing something? If yes, what? If not, would the fix work, and will it change the results of Theorem 1 and 2?\n\n### Conclusion \nIn the conclusion section, you write, “We proves gradient descent-ascent converges to a critical point for a range of finite learning rate ratios if and only if the critical point is a differential Stackelberg equilibrium. This answers a standing open question about the convergence of first-order methods to local minimax equilibria.” These two sentences may be misleading for the following reasons:\n- you only prove a *local* convergence result\n- The local distinction is important because the method can still cycle outside of these neighborhoods. (see for instance [Letcher 2020])\n- Also, the value of $\\tau$ depends on the neighborhood. So it seems that you may have an infinite number of critical points, and the value of \\tau to globally (max of the \\tau for each critical point) only has local convergence to local minimax may be infinite. Do you agree with that statement? \n\n### Experiments\nYour theory is about the nature of the stationary points found by the training dynamics  (are they theoretically meaningful), but you do not verify that training with different learning rates actually finds local minimax. Moreover, it is known that using different learning rates is necessary to get better empirical performances (see, for instance [Brock et al. 2019, Jolicoeur-Martineau et al. 2020] or most of the SOTA results on https://paperswithcode.com/paper/adversarial-score-matching-and-improved). I think that one experiment that would support your theory would be about looking at the eigenvalues of J_\\tau around the “practical equilibria” for different values of $\\tau$ and see if you only get local minimax for large enough $\\tau$.\nIn Assumption 1, you suppose that $(w,\\theta)$ is an equilibrium. But what kind of equilibrium? Nash? What do you need? That it is a stationary point of the dynamics?\n\n\n### About guardian maps\nShouldn’t you add in the definition of a guardian map that the map is continuous?\n\n### Related work\nYour examples 1 and 2 look very similar to the ones proposed by Zhang et al. 2020 in section 5.2. Can you comment on that? (I guess there is a difference, but I think this is related work that should be addressed, particularly Section 5.2)\n\n### Questions/comments on the appendix\nI think there is a typo that should be fixed on page 22: you recall that $A \\oplus B = A \\otimes B + B \\otimes A$, which is, I think, incorrect. (and it is the only place where I found a definition for $\\oplus$)\nOn page 24, you mention more elegant constructions (what are these construction?). \nYou also claim that you get the tightest bounds for $\\tau$. Can you compare these bounds? Can you prove that you are tighter?\nI do not understand the sentence \"we use $A \\boxplus A$ because of its computational advantages.\" Do you mean algebraic computations? Computational advantage usually refers to the algorithmic complexity to compute these quantities, but I guess this is not what you are talking about in the sentence. \n\n### Minor comments: \nPage 2 maybe define Schur complement\nPage 3 The notations $vec$ is not introduced. \nPage 4 The Kronecker product and sum are not defined \nProof of Lemma C.1 there is no n_1 and n_2 \n \n\nRefs:\n\nBrock, Andrew, Jeff Donahue, and Karen Simonyan. \"Large scale gan training for high fidelity natural image synthesis.\" arXiv preprint arXiv:1809.11096 (2018).\n\nZhang, Guojun, Pascal Poupart, and Yaoliang Yu. \"Optimality and Stability in Non-Convex-Non-Concave Min-Max Optimization.\" arXiv preprint arXiv:2002.11875 (2020).\n\n\nLetcher, Alistair. \"On the Impossibility of Global Convergence in Multi-Loss Optimization.\" arXiv preprint arXiv:2005.12649 (2020).\n\nJolicoeur-Martineau, Alexia, et al. \"Adversarial score matching and improved sampling for image generation.\" arXiv preprint arXiv:2009.05475 (2020).", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper treats the problem of running gradient descent-ascent (GDA) in min-max games with a different step-size for the two players. Earlier work by Jin et al. has shown that, when the ratio of the step-sizes is large enough, the stable fixed points of GDA coincide with the game's strict local min-max equilibria. The main contribution of this paper is an explicit characterization of a threshold value $\tau^*$ of this ratio as the maximum eigenvalue of a specific matrix that involves the second derivatives of the game's min-max objective at each (strict local) equilibrium.

This paper generated a fairly intense discussion, and the reviewers showed extraordinary diligence in assessing the authors' work. Specifically, the reviewers raised a fair number of concerns concerning the initial write-up of the paper, but these concerns were mostly addressed by the authors in their revision and replies. As a result, all reviewers are now in favor of acceptance.

After my own reading of both versions of the paper and the corresponding discussion, I concur with the reviewers' view and I am recommending acceptance subject to the following revisions for the final version of the paper:
1. Follow the explicit recommendations of AnonReviewer3 regarding the numerical simulations (or, failing that, remove them altogether). [The authors' phrase that "The theory we provide also does not strictly apply to using RMSprop" does not suffice in this regard]
2. Avoid vague statements like $\tau \to \infty$ in the introduction regarding the work of Jin et al. and state precisely their contributions in this context. In the current version of the paper, a version of this is done in page 4, but the introduction is painting a different picture, so this discussion should be transferred there.
3. A persisting concern is that the authors' characterization of $\tau^*$ cannot inform a practical choice of step-size scaling (because the value of $\tau^*$ derived by the authors depends on quantities that cannot be known to the optimizer). Neither the reviewers nor myself were particularly convinced by the authors' reply on this point. However, this can also be seen as an "equilibrium refinement" result, i.e., for a given value of $\tau$ only certain equilibria can be stable. I believe this can be of interest to the community, even though the authors' characterization cannot directly inform the choice of $\gamma_1$ and $\gamma_2$ (or their ratio).

Modulo the above remarks (which the authors should incorporate in their paper), I am recommending acceptance.
Decision: Accept (Poster)