Convergence of Gradient Methods on Bilinear Zero-Sum Games
Authors: Guojun Zhang
Yaoliang Yu
Venue:  (2020)
Keywords: GAN
gradient algorithm
convergence
min-max optimization
bilinear game

Abstract: Min-max formulations have attracted great attention in the ML community due to the rise of deep generative models and adversarial methods, while understanding the dynamics of gradient algorithms for solving such formulations has remained a grand challenge. As a first step, we restrict to bilinear zero-sum games and give a systematic analysis of popular gradient updates, for both simultaneous and alternating versions. We provide exact conditions for their convergence and find the optimal parameter setup and convergence rates. In particular, our results offer formal evidence that alternating updates converge "better" than simultaneous ones.

Published as a conference paper at ICLR 2020
CONVERGENCE OF GRADIENT METHODS ON BILIN- EAR ZERO-SUM GAMES
Guojun Zhang& & Yaoliang Yu Department of Computer Science
University of Waterloo
Vector Institute (guojun. zhang, yao lang. yu) @uwaterloo.ca
ABSTRACT
Min-max formulations have attracted great attention in the ML community due to the rise of deep generative models and adversarial methods, while understanding the dynamics of gradient algorithms for solving such formulations has remained a grand challenge. As a first step, we restrict to bilinear zero-sum games and give a systematic analysis of popular gradient updates, for both simultancous and alternating versions. We provide exact conditions for their convergence and find the optimal parameter setup and convergence rates. In particular, results offer formal evidence that alternating updates converge "better" than simultaneous ones.
INTRODUCTION
Min-max optimization has received significant attention recently due to the popularity of generative adversarial networks (GANs) (Goodfellow et al., 2014), adversarial training (Madry et al., 201 8) and reinforcement learning (Du et al., 2017; Dai et al., 2018), just to name some examples. Formally, given a bivariate function (x, y). we aim to find saddle point (x" yy) such that f(x" v) S f(x", y²) S. fx, Vx E R", Vy E IR".
(1.1)
Since the beginning of game theory, various algorithms have been proposed for finding saddle points (Arrow et al., 1958; Dem't yanov & Pevnyi, 1972: Gol' col'sstein, 1972; Korpelevich, 1976; Rockafellar, 1976; Bruck, 1977; Lions, 1978; Nemirovski & Yudin, 1983; Freund & Schapire, 1999). Due to its recent resurgence in ML, new algorithms specifically designed for training GANs were proposed (Daskalakis et al., 2018; Kingma & Ba, 2015; Gidel et al., 2019b; Mescheder et al., 2017). However, due the inherent non-convexity in deep learning formulations, our current understanding of the convergence behaviour of new and classic gradient algorithms is still quite limited, and existing games (Tseng, 1995;
analysis mostly focused on bilinear games or strongly-convex wwwoosssttoooooonoeeeeeeee Daskalakis et al., 2018; Gidel et al.. 2019b; Liang & Stokes, 2019; Mokhtari et al., 2019b). Non- zero-sum bilinear games, on the other hand, are known to be PPAD-complete (Chen et al., 2009) (for finding approximate Nash equilibria, see e.g. Deligkas et al. (2017)).
In this work, we study bilinear zero-sum games as a first step towards understanding general min-max optimization, although our results apply to some simple GAN settings (Gidel et al., 2019a) 1a). It is well-known that certain gradient algorithms converge linearly on bilinear zero-sum games (Liang & Stokes, 2019; Mokhtari al., 2019b; Rockafellar, 1976; Korpelevich, 1976). These iterative algorithms usually come with two versions: Jacobi style updates or Gauss-Seider (GS) style. In Jacobi style, update the sets of parameters (i.e., 2 and y) simultaneously whereas in GS style we update them alternatingly (i.e., one after the other). Thus, Jacobi style updates are naturally amenable parallelization while GS style updates have to be sequential, although the latter is usually found to converge faster (and more stable). In numerical linear algebra, the celebrated Stein-Rosenberg theorem (Stein & Rosenberg, 1948) formally proves that in solving certain linear systems, GS updates converge strictly faster than their Jacobi counterparts, and often with a larger set of convergent instances. However, this result does not readily apply bilinear zero-sum games.
Our main goal here is to answer the following questions about solving bilinear zero-sum games:
When exactly does a gradient-type algorithm converge?

---

Published as a conference paper at ICLR 2020
Table 1: Comparisons between Jacobi and Gauss-Seider updates. The second and third columns show when exactly an algorithm converges, with Jacobi or GS updates. The last column shows whether the convergence region of Jacobi updates contained in the GS convergence region.
Algorithm
Jacobi
Gauss-Seider Contained?
GD
diverges
limit cycle
N/A
EG
Theorem 3.2
Theorem 3.2
if B1 + 82 + a² 2//0
OGD
Theorem 3.3
Theorem 3.3
yes
momentum
does converge
Theorem 3.4
yes
Table 2: Optimal convergence rates. the second column, 3, denotes a specific parameter that depends σi and o, (see equation 4.2). In the third column, the linear rates for large The optimal parameters for both Jacobi and Gauss-Seide EG algorithms are the same. a denotes the step size (011 02 a),, and B1 and B2 hypper-parameters for EG and OGD, given in $2.
Algorithm
31
82 Rate exponent
Comment
EG
2/ + o
31
2/n²²
Jacobi and Gauss-Seidel
Jacobi OGD
2,
B.
B1 1
1/(6k²)
81 B2 oz/2
GS OGD
v2/01
/201/ (o} 1 o
0
1 - 1/n²
81 and B2 interchange
What is the optimal convergence rate by tuning the step size or other parameters?
Can we prove something similar to the Stein-Rosenberg theorem for Jacobi and GS updates?
We summarize our main results from $3 and $4 in Table and respectively, with supporting experiments given in $5. We use d and o, to denote the largest and the smallest singular values matrix E (see equation 2.1), and и: == 0//0,, denotes the condition number. The algorithms will be introduced in $2. Note that we generalize gradient-type algorithms but retain the same names. Table I shows that in most cases that we study, whenever Jacobi updates converge, the corresponding GS updates converge as well (usually with faster rate), but the converse is not true ($3). This extends the well-known Stein Rosenbeesgnberg theorem to bilinear games. Furthermore. Table tells us that by generalizing existing gradient algorithms, can obtain faster convergence rates.
Contributions
PRELIMINARIES
In the study of GAN training, bilinear games are often regarded as an important simple example for theoretically analyzing and understanding new algorithms and techniques (e.g. Daskalakis et al., 2018; Gidel et al., 2a;;;;;; Liang & Stokes, 2019). It captures the difficulty in GAN training and can represent some simple GAN formulations (Arjovsky et al., 2017: Daskalakis al., 2018: Gidel et al., 2019a; Mescheder et al., 2018). Mathematically, bilinear zero-sum games can be formulated as the following min-max problem:
min MäXyER" x Ey + + cc
(2.1)
The set of all saddle points (see definition in eq. (1.1)) is:
(xx, 5) Ey + b 0, E ==
(2.2)
Throughout, for simplicity we assume E to be invertible, whereas the seemingly general case with non-invertible E is treated in Appendix G. The linear terms are not essential in our analysis and we take b = c = 0 throughout the paper'. this case, the only saddle point is (0, O). For bilinear games, it is well-known that simultaneous gradient descent ascent does not converge (Nemirovski & Yudin, 1 1983) and other gradient-based algorithms tailored for min-max optimization have been proposed (Korpelevich, 1976; Daskalakis al., 2018; Gidel et al., 2019a; Mescheder et al., 2017). These iterative algorithms all belong to the class of general linear dynamical systems (LDS, a.k.a.
If they zero, can translate and y cancel the linear terms, see e.g. Gidel al. (2019b).
2

---

Published as a conference paper at ICLR 2020
matrix iterative processes). Using state augmentation (0)) := =xx(") y0) define general k-step LDS as follows:
Ek= A, + d.
(2.3)
where the matrices A, and vector d depend the gradient algorithm (examples can be found in Appendix C.I). Define the characteristic polynomial, with Ao = -I
((A) == det A,)
(2.4)
The following well-known result decides when such a k-step LDS converges for any initialization:
Theorem 2.1 (e.g. Gohberg et al. (1982)). The LDS in eq. (2.3) converges for any initialization
(z(") ".""),..,,(.-_.) 2()-1) iff the spectral radius == max p(A) = 0} < 1, in which case (2(0) converges linearly with an (asymptotic) exponent
Therefore, understanding the bilinear game dynamics reduces to spectral analysis. The (sufficient and necessary) convergence condition reduces to that all roots of p(A) lie in the (open) unit disk, which can be conveniently analyzed through the celebrated Schur's theorem (Schur, 1917):
Theorem 2.2 (Schur (1917)). The roots of a real polynomial p()) ao\" + an An +.... On are within the (open) unit disk of the complex plane vik E (1,2....,,1) det (P.PP - Qx)) 0. where Pk. Qs are x k matrices defined as: [Pela. = aリ-11,2 [Qu]i.) = an-it)
In the theorem above, we denoted 1s as the indicator function of the event S, i.e. 1s= if holds and 1s otherwise. For nice summary of related stability tests, see Mansour (2011). We therefore define Schur stable polynomials to be those polynomials whose roots all lie within the (open) unit disk of the complex plane. Schur's 's theorem has the following corollary (proof included in Appendix B.2 for the sake of completeness):
Corollary 2.1 (e.g. Mansour (2011)), A real quadratic polynomial X² + aA + b is Schur stable if < 1, la| < 1 + b; A real cubic polynomial X3 + ax² + bλ + is Schur stable iff |c| < 1, la+c < 1 + 6, b aC < - -²2; A real quartic polynomial X + +ax + +b2 + cA+ d Schur stable d,, la < b + d + I, and (1 d) + (c - aa) c)/ 172.
if ad|
Let us formally define Jacobi and GS updates: Jacobi updates take the form
x Ti (2x (y( (1-1) x (t- (t==)),, (() (2( y (1-1) x (t- k), ((--)),,
while Gauss-Seidel updates replace a (t-() with the more recent xf (1-++1) in operator T2, where Tı, T, Rank x Rink + Rn" can be any update functions. For LDS updates in eq. (2.3) we find nice relation between the characteristic polynomials of Jacobi and GS updates in Theorem 2.3 (proof in Appendix B.1), which turns out to greatly simplify our subsequent analyses:
Theorem 2.3 (Jacobi vs. Gauss-Seidel,, Let p(). L, + U, and L; is strictly lower block triangular. Then, the characteristic polynomial of Jacobi updates p(>, 1) while that of Gauss-Setee updates is p(,, A).
det d U,)A*-i, where A,
Compared the Jacobi update, in some sense the Mhuss-Seidell update amounts to shifting the strictly lower block triangular matrices L; one step to the left, as p(A, X) can be rewritten as det. (
with L == 0. This observation will significantly simplify our comparison between Jacobi and Gauss-Seine updates.
Next, we define some popular gradient algorithms for finding saddle points in the min-max problem min max f(x. (xx.). y).
(2.5)
We present the algorithms for general (bivariate) function f although main results will specialize ff to the bilinear case in eq. (2. Note that we introduced more "step sizes" for our refined analysis, as we find that the enlarged parameter space often contains choices for faster linear convergence (see $4). We only define the Jacobi updates, while the GS counterparts can be easily inferred. We always on and 02 to define step sizes (or learning rates) which are positive.
3

---

Published as a conference paper at ICLR 2020
Gradient descent (GD) The generalized GD update has the following form:
xx(+1) x an / m (xx!) (9), ()))) y ((++1) y0) + 02 V ()l(( (0).
(2.6)
When a1 Q22, the convergence of averaged iterates (a.k.a. Cesari convergence) for convex-concave
games is analyzed in (Bruck, 1977; Nemirovski & Yudin, 1978; Nedić & Ozdaglar, 2009). Recent progress on interpreting GD with dynamical systems can be seen in, e.g., Mertikopoulos et al. (2018);
Bailey et al. (2019); Bailey Piliouras (2018).
Extra-gradient (EG) We study generalized version of EG, defined as follows:
x (++1/2) x 71 V fx ()), y ((+1/22)
(()) V v ()))
(2.7)
(111) x 01 f (1+11/2) y ((+1/2)). ( (1) 0 f 1/2), y ( (2.8)
EG was first proposed in Korpelevich (1976) with the restriction 0₁ 0g = 72, under which linear convergence was proved for bilinear games. Convergence of EG on convex-concave games was analyzed in Nemirovski (2004); Monteiro & Svaiter (2010), and Mertikopoulos et al. (2019) provides convergence guarantees for specific wwt---coee--o-cooee
problems. For bilinear games, slightly more generalized version was proposed in Liang& & Stokes (2019) where an 02, 71 = 72. with linear convergence proved. For later convenience we define 31 = 0271 and B2 = 01 7/2
Optimistic gradient descent (OGD) We study generalized version of OGD, defined as follows: x (t+1) (t) a (x)(t) () + 31 V= yy((1))
(2.9)
y (1+1) = y + a V vz (0)) - 3. V fz (x-((( (t-1) 10)-))yy(111 (1-1))
(2.10)
The original version of OGD was given in Popov (1980) with 0 = a2 2 2/3 and rediscovered in the GAN literature (Daskalakis et al., 2018). Its linear convergence for bilinear games was proved in Liang& & Stokes (2019). A slightly more generalized version with 0₁ ar and $1 3g was analyzed in Peng et al. (2019); Mokhtari et al. (2019h), again with linear convergence proved. The stochastic case was analyzed Hsieh et al. (2019).
Momentum method Generalized heavy ball method was analyzed in Gidel et al. (2019b):
x (1+1) x (x)( () + B - (111))),
(2.
y (1+1) = y + a (zx"(()) ()) + 1 y(--1)).
(2.12)
This is modification of Polyak's 's heavy ball (HB) (Polyak, 1964), which also motivated Nesterov's accelerated gradient algorithm (NAG) (Nesterov, 1983). Note that for both x-update and the y-update, we add a scale multiple of the successive difference (e.g. proxy of the momentum). For this algorithm our result below improves those obtained in Gidel et al. (2019b), as will be discussed in $3.
EG and OGD approximations of proximal point algorithm It has been observed recently in Mokhtari et al. (2019b) that for convex-concave games, EG (01 = 02 "1 = ?/2 77) and OGD (a1/2- /2/ /2 31 B2 17) can be treated approximations of the proximal point algorithm (Martinet, 1970; Rockafellar, 1976) when is small. With this result, one can show that EG and OGD converge saddle points sublinearly for smooth convex-concave games (Mokhtari et al., 2019a). We give a brief introduction of the proximal point algorithm in Appendix A (including a linear convergence result for the slightly generalized version).
The above algorithms, when specialized to bilinear fuucciion f (see eq. (2.1)), can be rewritten as a 1-step or 2-step LDS (see. eq. (2.3)). See Appendix C.I for details.
EXACT CONDITIONS
With tools from $2, we formulate necessary and sufficient conditions under which a gradient- based algorithm converges for bilinear games. We sometimes use "J" as a shorthand for Jacobi style updates and "GS" for Gauss-Seidel style updates. For each algorithm, we first write down the characteristic polynomials (see derivation in Appendix C. for both Jacobi and GS updates, and present the exact conditions for convergence. Specifically, strictly include the Jacobi convergence regions. The proofs for Theorem 3.1, 3.2, 3.3 and 3.4 can be found in Appendix C.2, C.3, C.4, and C.5, respectively.
show that in many cases the GS convergence regions
4

---

Published as a conference paper at ICLR 2020
GD The characteristic equations be computed as:
J: (A 1) 010220 = 0, GS: (A 1)- a1020 = 0.
(3.1)
Scaling symmetry From section we obtain a scaling symmetry (0),0)) - (lon, o2/l), with 1 O. With this symmetry can always fix on 02 a. This symmetry also holds for EG and momentum. For OGD, the scaling symmetry is slightly different with (1,,81, a2, 82) 7 (tan t31, a2 B2/t). but we can still use this symmetry fix a₁ =
Theorem 3.1 (GD), Jacobi GD and Gauss- Seidel GD do not converge. However, Gauss-Seidel GD can have a limit cycle while Jacobi GD always diverges.
In the constrained case, Mertikopoulos et al. (2018) and Bailey & Piliouras (2018) show that FIRL, a more generalized algorithm of GD, does not converge for polymatrix games. When aj Q2, the GD has been shown in Bailey et al. (2019).
result of
EG The characteristic equations can be computed as:
J: (A (A- ()=1)² + (81 + 82)0 1) + (a1az0² + +113200) =0, 3 1) (01020² + 31 = 0.
(3.2)
GS:
12-
(3.3)
Theorem 3.2 (EG). For generalized EG with a = a2 a and 7/2 = B2/a, Jacobi and Gauss-Seidel updates achieve linear convergence ifr for any singular value of E, we have:
J: 1:18,0² + 320 - 2 < 310 ( -20 + a2o?
(1 -1- -1-1111-77000 -20 <1,
(3.4)
GS :8: + + 2 < + -1 -1 -123007)
(1 - (1-
(3.5)
1/ + + 2/07, the convergence region of GS updates strictly include that of Jacobi updates.
OGD
The characteristic equations can be computed as:
J: - (Aa1 - 31)(Aa2 - =2)00² = 0, 1² (Aa) B:)()aaz 32) 2 0.
(3.6)
GS:
(3.7)
Theorem 3.3 (OGD). For generalized OGD with a =02 = a, Jacobi and Gauss-Seidel updates achieve linear convergence iff for any singular value a of E, we have:
4+ (a (3) 82)0² > 0, | 1, (a- 0,
J:
(3.8)
aa (8f02 + +1) +1) <
32) +2) 81,32 - -3)):
(a- 32) 0, (,) + <,
GS:
(3.9)
(a 1)(28202++1) +1) (1 32
The convergence region of GS updates strictly include that of Jacobi updates.
Momentum
The characteristic equations can be computed as:
J: 1)²(2 - 32) + 2
(3.10)
GS: - (2-1) (1)(A -2) 22
(3.11)
Theorem 3.4 (momentum). For the generalized momentum method with a2 the Jacobi updates never converge, while the GS updates converge iff for any singular value a of E. we have:
|3,321 <
0² - 32 a²o² (1 (23,) 31 32).
3, +3, 4(31 + 1)(2 + 1 > d²0²
(3.12)
This condition implies that at least one of B1, B2 is negative.
5

---

Published as a conference paper at ICLR 2020
Prior to our work, only sufficient conditions for linear convergence were given for the usual EG and OGD; see $2 above. For the momentum method, our result improves upon Gidel et al. (2019b) where they only considered specific cases of parameters. For example, they only considered 3 B2 2 -1/16 for Jacobi momentum (but with explicit rate of divergence), and 31 = -1 1/2, A2 = 0 for GS momentum (with convergence rate). Our Theorem 3.4 gives more complete picture and formally justifies the necessity of negative momentum.
In the theorems above, we used the term "convergence region" denote subset of the parameter space (with parameters a, 3 or 7) where the algorithm converges. Our result shares similarity with the celebrated Mhein-Rosenbers theorem (Stein Rosenberg. 1948), which only applies to solving linear systems with non-negative matrices (if one were to apply it to our case, the matrix S in eq. (F.1) in Appendix F needs to have non-zero diagonal entries, which is not possible). In this sense, our results extend the Rosenberg theorem to cover nontrivial bilinear games.
4 OPTIMAL EXPONENTS OF LINEAR CONVERGENCE
In this section we study the optimal convergence rates of EG and OGD. We define the exponent of linear convergence as r li 11/1 which is the same as the spectral radius. For case of presentation we fix æ1 ag a (using scaling symmetry) and we use r. denote the optimal exponent of linear convergence (achieved by tuning the parameters a, B, 7). Our results show that by generalizing gradient algorithms one can obtain better convergence rates.
Theorem 4.1 (EG optimal). Both Jacobi and GS EG achieve the optimal exponent of linear conver-
gence r. (k² (x² + 1) at a + 0 and B1 32 = 2/ + oa). As + + 1 1 2/k
Note that we defined B3 = a in Section 2. In other words, we are taking very large extra-gradient steps (% - oc) and very small gradient steps (a - 0).
Theorem 4.2 (OGD optimal). For Jacobi OGD with 31 = 32 = B. to achieve the optimal exponent of linear convergence, we must have a $ 23. For the original OGD with =28, the optimal exponent of linear convergence r. satisfies
2
4 20 V (of 250 of + (of - (90 - oz)):
(4.1)
30f (0 02)3/2 /909
0 60f0 o
8. = 2/2 2
(4.2)
01o2
If K - 00, F+ ~ 1 - 1/ (6x2). For GS OGD with B2 0, the optimal exponent of convergence is
r. / (x² 1)/ + 1), al a v2/ai and /2 (of o.) If + oo, r. 1/k2,
Remark The original OGD (Popov, 1980; Daskalakis et al., 2018) with a 2,3 may not always be optimal. For example, take one-dimensional bilinear game and a 1, and denote the spectral radius given ax 3 as ra,, B). we fix a = 1/2, by numerically solving section 3 we have
r (1/2,1/4) = 0.966, (112211/3 = 0.956,
(4.3)
ie,, a = = 1/3 is better choice than 2/3 1/2.
Numerical method We provide numerical method for finding the optimal exponent of linear convergence, by realizing that the wnit disk in Theorem 2.2 is not special. Let us call a polynomial to be r-chhur stable if all of its roots lie within an (open) disk of radius r in the complex plane. We can scale the polynomial with the following lemma:
Lemma 4.1. A polynomial p()) is S-hurr stable iff p(rX) is Schur stable.
With the lemma above, the exponent of linear convergence is at most r (r < 1). A simple binary search would allow one to find a better and better convergence region. See details in Appendix D.3.
rescale the Schur conditions and find the convergence region where

---

Published as a conference paper at ICLR 2020
0.30
Adam
0.525
w/o scaling
SGD
scaling
0.2
0.000
-15
0.2
0.915
-20
0.15
-25
0.200
-32
GS OGD
-5
Jacoal OGD
1000
1962
2002
330 450
230
820
1000
Figure 1: Left: linear convergence of optimal EG, Jacobi OGD, Claus--Seide OGD in a bilinear
game with the log distance; Middle: comparison among Adam, SGD and EG in learning the mean of a Gaussian with WGAN with the squared distance; Right: Comparison between EG with (a = 0.02,
y 2.0) and without scaling (a = 7 = 0.2). We use the squared distance.
2.00
15
177
15
0.6
1.50
A5
125
100
0.0
3.5
100
2.0
0.
8.5
10
15
2.0
0.0
0.5
15
2.0
30
15
1.0
1.0
2.0
2.0
Figure 2: Heat maps of the spectral radii of different algorithms. We take o = 1 for convenience. The horizontal axis is and the vertical axis is B. Top row: Jacobi updates: Bottom row: Gauss-Seidel updates. Columns (left to right): EG; OGD; momentum. If the spectral radius is strictly less than one, means that our algorithm converges. In each column, the Jacobi convergence region is contained in the GS convergence region (for EG we need an additional assumption, see Theorem 3.2).
EXPERIMENTS
Bilinear game
We run experiments simple bilinear game and choose the optimal parameters as suggested in Theorem 4.1 and 4.2. The results are shown in the left panel of Figure I, which confirms the predicted linear rates.
Density plots We show the density plots (heat maps) of the spectral radii in Figure 2. We make plots for EG, OGD and momentum with both Jacobi and GS updates. These plots are made when 31 = B2 3 and they agree with our theorems in $3.
Wasserstein GAN
As in Daskalakis al. (2018), we consider a WGAN (Arjovsky et al., 2017)
that learns the mean of Gaussian:
min& maxo ( 0) = Ex- (s0 x)] E2- (2+ +))]
(5.1)
where s(x) the sigmoid function. can be shown that near the saddle point (0" (0*'"") xb) = (0, v) the min-max optimization can be treated bilinear game (Appendix E. With GS updates, that Adam diverges, SGD goes around limit cycle, and EG converges, as shown in the middle panel of Figure 1. We two-dimensional Gaussian with GAN.
find
that Adam does not behave well even in this simple task of learning single
Our next experiment shows that generalized algorithms may have advantage over traditional ones. Inspired by Theorem 4.1, we compare the convergence of two EGs with the same parameter 3 = ary, and find that with scaling, EG has better convergence, shown in the right panel of Figure 1. Finally,
7

---

Published as a conference paper at ICLR 2020
0.223
Jacoal EG
Jacabi OGD
Jacobl Momentum Kamentum
0.00
6S EG
GS OGSD
0.223
000
0013
002
0003
6/00
000
0.00
0000
620
1000
Figure 3: Jacobi GS updates. y-axis: Squared distance | 2--0-/10 v112 x-axis: Number of epochs. Left:
EG with 7 = 0.2, a = 0.02; Middle: OGD with a = 0.2, 81 = 0.1, 82 = 0; Right:
Momentum with 0.08, -0.1. We plot only few epochs for Jacobi if it does not converge.
0005
0010
0.20
0.1
0.3
0.1
-2.5
0.0
2.5
-25
0.0
2,3
2.5
0.0
2,5
2-
-0.05
-0.10
0
-2
-0.20
0.1
0.3
0.1
-2.5
0.0
2.5
2.5
0.0
2.5
-25
0.0
2.5
Figure 4: Test samples from the generator network trained with stochastic GD (step size a 0.01). Top row: Jacobi updates; Bottom row: Gauss-Seide! updates. Columns: epoch 0, 10, 15, 20.
we compare Jacobi updates with GS updates. In Figure 3, we can see that GS updates converge even the corresponding Jacobi updates do not.
Mixtures of Gaussians (GMMs) Our last experiment is on learning GMMs with a vanilla GAN (Goodfellow et al., 2014) that does not directly fall into our analysis. We choose a 3-hidden layer ReLU network for both the generator and the discriminator, and each hidden layer has 256 units. We find that for GD and OGD, Jacobi style updates converge more slowly than GS updates, and whenever Jacobi updates converge, the corresponding GS updates converges as well. These comparisons can be found in Figure 4 and 5, which implies the possibility of extending
results to non- non-bilinear games. Interestingly, we observe that even Jacobi GD converges on this example. We provide additional comparison between the Jacobi and GS updates of Adam (Kingma & Ba, 2015) in Appendix F.2.
0.00
C
0.05
-0.15
0,20
0.1
0.0
0.1
2
-2
-0.10
0.15
-0.20
00
0.2
Figure 5: Test samples from the generator network trained with stochastic OGD (a = 23 = 0.02). Top row: Jacobi updates; Bottom row: Gauss- updates. Columns: epoch 10, 60, 100.
8

---

Published as a conference paper at ICLR 2020
6 CONCLUSIONS
In this work we focus on the convergence behaviour of gradient-based algorithms for solving bilinear games. By drawing connection discrete linear dynamical systems ($2) and using Schur's theorem, we provide necessary and sufficient conditions for variety of gradient algorithms,, for both simultaneous (Jacobi) and alternating (eiusl) updates. Our results show that Tauss-Seidhe updates converge more easily than Jacobi updates. Furthermore, we find the optimal exponents of linear convergence for EG and OGD, and provide numerical method for searching that exponent. We performed number of experiments to validate our theoretical findings and suggest further analysis.
There are many future directions to explore. For example, our preliminary experiments on GANs suggest that similar (local) results might be obtained for more general games. Indeed, the local convergence behaviour of min-max nonlinear optimization can studied through analyzing the spectrum of the Jacobian matrix of the update operator (see, e.g., Nagarajan & Kolter (2017); Gidel et al. (2019b)). We believe our framework that draws the connection to linear discrete dynamic systems and Schur's theorem is powerful machinery that be applied in such problems and beyond. It would be interesting to generalize our results to the constrained case (even for bilinear games), studied in Daskalakis & Panageas (2019); Carmon al. (2019). Extending our results to account for stochastic noise (as empirically tested in our experiments) is another interesting direction, with results in Gidel al. (2019a); Hsieh al. (2019).
ACKNOWLEDGEMENTS
We would like to thank Argyrios Deligkas, Sarath Pattathil and Georgios Piliouras for pointing several related references. GZ supported by David R. Cheriton Scholarship. We gratefully acknowledge funding support from NSERC and the Waterloo-Huavei Joint Innovation Lab.
REFERENCES
M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, 2017.
K. J. Arrow, I. Hurwiez, and H. Uzawa. Studies in linear and non-linear programming. Stanford University Press, 1958.
J. P. Bailey and G. Piliouras. Multiplicative weights update in zero-sum games. In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 321-332133 ACM, 2018.
J. P. Bailey, G. Gidel, and G. Piliouras. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent, arXiv preprint arXiv: 04392, 2019.
R. E. Bruck. On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space. Journal of Mathematical Analysis and Applications, 61(1):159-164, 1977.
Y. Carmon, Y. Jin, A. Sidford, and K. Tian. Variance reduction for matrix games, In Advances in Neural Information Processing Systems, pp. 11377-11388, 2019.
X. Chen, X. Deng, and S.-H. Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 56(3):14, 2009.
S. S. Cheng and S. Chiou. Exact stability regions for quartic polynomials. Bulletin of the Brazilian Mathematical Society, 38(1):21-33 1188, 2007.
B. Dai, A. Shaw. L. Li, L. Xiao, N. He, Z. Liu, J. Chen, and L. Song. Sbeed: Convergent reinforcement learning with nonlinear function approximation. In International Conference on Machine Learning, pp. 1125-1134, 2018.
C. Daskalakis and I. Panageas. Last-iterate convergence: Zero-sum games and constrained min-man max optimization. In Innovations in Theoretical Computer Science, 2019.

---

Published as a conference paper at ICLR 2020
C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng. Training GANs with optimism. In International Conference on Learning Representations, 2018.
A. Deligkas, J. Fearnley, R. Savani, and P. Spirakis, Computing approximate Nash equilibria in polymatrix games. Algorithmica, 77(2):8875514 2017.
V. F. Dem yanov and A. B. Pevnyi. Numerical methods for finding saddle points. USSR Computa- tional Mathematics and Mathematical Physics, 12(5):11-52, 1972.
S. S. Du, J. Chen, L. Li, Xiao, and D. Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, pp. 1049-1058, 2017.
Y. Freund and R. F. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-)):9--103, 1999.
G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien. A variational inequality perspec- tive generative adversarial networks. In International Conference on Learning Representations, 2019a.
G. Gidel, R. A. Hemmat, M. Pezeshki, G. Huang, R. Lepriol, S. Lacoste-Julien, and I. Mitliagkas. Negative momentum for improved game dynamics. AISTATS, 2019b.
I. Gohberg, P. Lancaster, and L. Rodman. Matrix polynomials. Academic Press, 1982.
E. G. Gol'shtein. A generalized gradient method for finding saddlepoints. Ekonomika i matematich- eskie metody, 8(4):569-577 1972.
I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, pp. 2672-2680, 2014.
Y.-G. Hsieh, F. lutzeler, J. Malick, and P. Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. In Advances Neural Information Processing Systems, pp. 1936-6946, 2019.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
T. Liang and J. Stokes. Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. In AISTATS, 2019.
L. Lions. Une méthode itérative de résolution d' une inéquation variationnelle. Israel Journal of Mathematics, 31(2):204-25) 208, 1978.
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
M. Mansour. Discrete-time and sampled-data stability tests. In Williams S. Levine (ed.), The Control Handbook: Control System Fundamentals. CRC press, 2nd edition, 2011.
B. Martinet. Régularisation d' d'inéquations variationnelles par approximations successives. ESAIM: Mathematical Modelling and Numerical Analysis: Modélisation Mathématique Analyse Numérique, 4(R33)154-155 154-188 1970.
P. Mertikopoulos, C. Papadimitriou, and G. Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2703-2717. SIA.7,...AMMMMMMM SIAM, 2018
P. Mertikopoulos. B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras. Optimistic mirror descent in saddle-poin problems: Going the extra (gradient) mile. In International Conference Learning Representations, 2019.
10

---

Published as a conference paper at ICLR 2020
L. Mescheder, S. Nowozin, and A. Geiger. The numerics of GANs. In Advances in Neural Information Processing Systems, pp. 1825-1835, 2017.
L. Mescheder, A. Geiger, and S. Nowozin. Which training methods for GANs do actually converge?
In International Conference on Machine Learning, 2018.
A. Mokhtari, Ozdaglar, and Pattathil. Proximal point approximations achieving a convergence rate of (1) for smooth convex-concave saddle point problems: Optimistic gradient and extra- gradient methods. arXiv preprint arXiv:/906.0/ 15, 2019a.
A. Mokhtari, A. Ozdaglar, and Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. arXiv preprint 1oXiv:990108555 2019b.
R. D. C. Monteiro and B. F. Svaiter. On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean. SIAM Journal on Optimization, 20(6):2755-2787, 2010.
Nagarajan and Kolter. Gradient descent GAN optimization locally stable. Advances in Neural Information Processing Systems, pp. 5585-5595, 2017.
A. Nedié and A. Ozdaglar. Subgradient methods for saddle-point problems. Journal of optimization theory and applications, 142(1):205-2255 2009.
A. Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 25())222-, 2004.
A. S. Nemirovski and D. B. Yudin. Cesàro convergence of the gradient method of approximating saddle points of convex-concave functions. Doklady Akademii Nauk, 239: 1056-1059, 1978.
A. Nemirovski and D. B. Yudin. Problem complexity and method efficiency in optimization. Wiley, 1983.
Y. Nesterov. A method for unconstrained convex minimization problem with the rate of convergence O(1/k?). Doklady Akademii Nauk, 269:543-547, 1983.
W. Peng, Y. Dai, H. Zhang, and L. Cheng. Training GANs with centripetal acceleration. arXiv preprint arXiv: (002:.999200000 08949, 2019.
B. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computa- tional Mathematics and Mathematical Physics, 4(5):1-17, 1964.
I. D. Popov. A modification of the Arrow-Hurwizz method for search of saddle points. Mathematical Notes, 28(5):845-848, 1980.
R. T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization, 14(5):877-898, 1976.
Y. Saad. Iterative methods for sparse linear systems. SIAM, 2nd edition, 2003.
I. Schur. Über Potenzreihen, die im Innern des Einheitskreises beschränkt sind. Journal für die reine und angewandte Mathematik, 147:205-22 2322, 1917.
Stein and R. L. Rosenberg. On the solution of linear simultancous equations by iteration. Journal of the London Mathematical Society, 1(2):111-118, 1948.
P. Tseng. On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 60(1 203-222237,2 1995.
11

---

Published as a conference paper at ICLR 2020
A PROXIMAL POINT (PP) ALGORITHM
PP was originally proposed by Martinet (1970) with 01 = Q2 and then carefully studied by Rockafel- lar (1976). The linear convergence for bilinear games also proved in the same reference. Note that we do not consider Gauss-Seidel PP since we do not get meaningful solution after shift of steps".
a (1+1) (1) on Va (ax , (((+t)),, y (
y + az V (x) ((
(A.1)
where x (++1) and y 1+++) are given implicitly by solving the equations above. For bilinear games, one can derive that:
2 (++1)
I 0.
E
z (()
(A.2)
We can compute the exact form of the inverse matrix, but perhaps an easier way just to compute the spectrum of the original matrix (the same Jacobi GD except that we flip the signs of a;) and perform + 1/A. Using the fact that the eigenvalues of a matrix are reciprocals the eigenvalues of its inverse, the characteristic equation is:
(1/A - 1)2 + 0r102202 = 0.
(A.3)
With the scaling symmetry (a), - ( a2/t), we can take a a2 = 2>>
> 0. With the notations in Corollary 2.1, we have = 2/((1 a²o²) and = 1/(1 + a²o²), and is easy check |al < 1 + b and b < are always satisfied, which means linear convergence is always guaranteed. Hence, we have the following theorem:
Theorem A.1. For bilinear games, the proximal point algorithm always converges linearly.
Although the proximal point algorithm behaves well, it rarely used in practice since it is an implicit method, i.e., needs to solve (x((++),, y (1++1) from equation A.1.
B PROOFS IN SECTION
B.1 PROOF OF THEOREM 2.3
In this section we apply Theorem 2.1 to prove Theorem 2.3, an interesting connection between Jacobi and Gauss- Seidel updates:
Theorem 2.3 (Jacobi vs. Gauss-Seidel), Let p(A,
U.)**) where A,
Li + U; and L; is strictly lower block triangular. Then, the characteristic polynomial of Jacobi updates is p(A, 1) while that of Gauss-Seidel updates is p(>,\)
Let us first consider the block linear iterative process in the sense of Jacobi (i.e., blocks are updated simultaneonsly):
(t)
((-i)
(+)
A
(1-8) 1) + Σ Aigz
(1-1)
+ d,
(B.1)
(t-))
j=l
where Ai, is the j-th column block of A, For each matrix A,, we decompose it into the sum
A, = U.
(B.2)
where L, is the strictly lower block triangular part and U; is the upper (including diagonal) block triangular part. Theorem 2.1 indicates that the convergence behaviour of equation B. is governed by the largest modulus of the roots of the characteristic polynomial:
det
- x
Σ
A = det
A
L + U.JA
(B.3)
IIf inverse operators this is in principle doable.
12

---

Published as a conference paper at ICLR 2020
Alternatieely, can also consider the updates in the sense of Gauss Seidel (i.e., blocks updated sequentially):
Azjzj (t- ++1)
Σ
A (t-i)
+ di, 1= I,...,b.
(B.4)
can rewrite the Gauss-Seidel update elegantly² as:
(I L1)2(t)
[1+1 + U.)2(1-1) d.
(B.5)
i.e.
(1) = Σ I L,) (L +1))
dd)
(B.6)
where Lx+1 = O. Applying Theorem 2.1 again we know the convergence behaviour the Gauss-
Seidel update is governed by the largest modulus of roots of the characteristic polynomial:
-X E(- L,) (I,+1 U.)A
det
(B.7)
- (-x- (I (I-1,)-1
ELA -.))--))
det
+
(B.8)
h Σ 1=0
= =det(I - -I) del
(AL + U,MA
(B.9)
Note that Ag = - and the factor det(T - -1) can be discarded since multiplying a characteristic
polynomial by non-zero constant factor does not change its roots.
B.2 PROOF OF COROLLARY
Corollary 2.1 (c.g. Mansour (2011)). A real quadratic polynomial X² + aA + is Schur stable if < 1, la < 1 + b; A real cubic polynomial X + ax² + bλ + e is Schur stable iff [c| < 1, la+c] 1+ b, b ac
e²; real quartic polynomial X + ax bx +
cA d Schur stable
iff ad] < - d², la cl < bb+ d 1, and < (1 + d) + (c ad) c)
Proof. It suffices to prove the result for quartic polynomials. We write down the matrices:
P
[1].
Q
[d].
(B.
1 0
d
c]
P
Q2 =
(B.11)
a
1
0
d
1
0
0
d
b7
P3
Q3
(B.12)
a
1
d
0 1
0 0
07
d
c
b
a
0
0
d
b
P
Q4
(B.13)
b
a
1
0
d
C
b
0
0
0
0
d
We require dct(P,PP. Q =: 8 0, for 1,2,3, If l:
have d
namely, [d] < 1. 69 0 reduces to (c ad)²
< (1 - d2)2 and thus |c ad
< 1 - d2 due to the
first condition.. > simplifies to:
-(aa + c)2 - (b+d+ 1) d - l) - 1)2 - (a c) ad)) 0,
(B.14)
"This well-known when see c.g. Saad (2003).
13

---

Published as a conference paper at ICLR 2020
which yields la + c| |b d 1/. Finally, d3 0 reduces to:
(b-dd-)(d-
(a- c) (dd) - +
(c- ad) + c)) > 0. (B.15)
Denote p(A) A + aa + by² + cA + d. we must have p(1) > and p(-1) 1) > 0, otherwise
there is a real root Au with Aol 2 1. Hence we obtain b b+ + > + c
> 0. Also, from
Ic ad < 1 d, know that:
Cc - adI
la + c)
< |b d 1| d8) (b d 10(1-)((1))))))) d²).
(B.16)
So, the second factor in B.15 is negative and the positivity of the first factor reduces to:
b < (1+ (c- ad) (d - 1)
(B.17)
To obtain the Schur condition for cubic polynomials, we take d = 0, and the quartic Schur condition becomes:
|d| < 1, la + < <b+1,b ac - c².
(B.18)
To obtain the Schur condition for quadratic polynomials, we take 0 in the above and write:
<< 1, |a| <1+6
(B.19)
The proof is now complete.
C PROOFS IN SECTION
Some of the following proofs in Appendix C.4 and C.5 rely on Mathematica code (mostly with the built-in function Reduce) but in principle the code can be verified manually using cylindrical algebraic decomposition."
C.I DERIVATION CHARACTERISTIE POLYNOMIALS
In this appendix, derive the exact forms of LDSs (eq. (2.3)) and the characteristic polynomials for all gradient-based methods introduced in $2, with eq. (2.4). The following lemma is well-known and easy verify using Schur's complement:
Lemma C.1. Given M g2ax2n A E paax and
A B C
M
(C.1)
D
If C' and D commute, then det M det( AD BC).
Gradient descent From equation 2.6 the update equation of Jacobi GD can be derived as:
(++1)
01
E (1)
(C.2)
a2E
and with Lemma C. we compute the characteristic polynomial as in eq. (2.4):
(2 1)I
F
det
(A (A-1)4 det((A - 1 + +aaa2E
(C.3)
-22E
With spectral decomposition we obtain equation 3.1. Taking 022 + Aaz and with Theorem 2.3 we obtain the corresponding GS updates. Therefore, the characteristic polynomials for GD are:
J: (A - 1)2 + 010202 = 0, GS: (A 1)2 + a1020 = 0.
(C.4)
*See the online Mathematica documentation.
14

---

Published as a conference paper at ICLR 2020
Extra-gradient
From eq. (2.7) and eq. (2.8), the update of Jacobi EG is:
# (1+1)
I E
-01 E
20)
(C.5)
azE
I- 1-3, 3, E
the characteristic polynomial is:
(A + BEEE -02
0₁E (A- 1)I 31 E
det
(C.6)
Since we assumed 0: > 0, we can left multiply the second row by E/ az and add it the first Hence, we obtain:
row.
(A 1)I -
01 16)-2/13/ +,3,E E E/a2
det
(C.7)
B +
With Lemma C.1 the equation above becomes:
det[(A 1 + (31 + 8 E(X- E+ B132E E
EE E),,
(C.8)
which simplifies to equation 3.2 with spectral decomposition. Note that to obtain the GS polynomial, we simply take a2 - λa in the Jacobi polynomial as shown in Theorem 2.3. For the case of reading copy the characteristic equations for generalized EG:
J: (A 1)2 + (81 (2) 1) + (a1a20² + 31320=) = 0, GS: (A 1)² + (0102 + B1 + 32)0 2A 1) + (a1020 + +1
(C.9)
0. (C.10)
Optimistic gradient descent
We can compute the LDS for OGD with eq. (2.9) and eq. (2.10);
(1+2)
I
-' (1+1) +
0
B E
2(0)
(C.11)
E2E
I
B
With eq. (2.4), the characteristic polynomial for Jacobi OGD is
(A² A)T
(Aan 81 E (22
det
(C.12)
(->02 + E
-
Taking the determinant and with Lemma C.I we obtain equation 3.6. The characteristic polynomial for GS updates equation 3.7 can be subsequently derived with Theorem 2.3, by taking (az, 82) + (Aa2, AB2). For the ease of reading we copy the characteristic polynomials from the main text as:
J: 1 1)² + (Aar B:) 32)0²² 0,
(C.13)
GS: 2² 1)2² + (Aa1 B1) 32) 0.
(C.14)
Momentum method
With eq. (2.11) and eq. (2.12), the LDS for the momentum method is: [1+ 8 -a1 E (1+33)1
[ 3,1
z (++2)
z (++1)
-B21 (())
(C.15)
0
From eq. (2.4), the characteristic polynomial for Jacobi momentum is
det [22 X(1 31) + B1)
Aay E (22 32) 32)
(C.16)
-'
Taking the determinant and with Lemma C. we obtain equation 3.10, while equation 3. 1 can be derived with Theorem 2.3, by taking a2 + daz. For the ease of reading we copy the characteristic polynomials from the main text
J: (A 1)²(2 31) 32) a1ag0222 0,
(C.17)
GS: (A - 1)3(A-8)( - B2) + 01020222 = 0.
(C.18)
C.2 PROOF OF THEOREM 3.1: SCHUR CONDITIONS OF GD
Theorem 3.1 (GD), Jacobi GD and Gauss-Seider GD do not converge. However, Gauss-Seidel GD can have limit cycle while Jacobi GD always diverges.
Proof. With the notations in Corollary 2.1, for Jacobi GD, b = 1 + a²o² > 1. For Gauss-Seida GD, b = 1. The Schur conditions violated.
[]
15

---

Published as a conference paper at ICLR 2020
C.3 PROOF OF THEOREM 3.2: SCHUR CONDITIONS OF EG
Theorem 3.2 (EG). For generalized EG with a - 02 a and 7/6 = 3:/0 Jacobi and Gauss-Seidel updales achieve linear convergence for any singular value of E, we have;
J:1310² + 820 - 1+ (1 010²) 320 a2
(1 (1- 320 a²0 <1,
(3.4)
GS ( + +2 - < + - --00) -320²)
(1 -1- (1- 320 <1.
(3.5)
1f + +3++82+ < 2/0 the convergence region of GS updates strictly include that of Jacobi updates.
Both characteristic polynomials can be written as quadratic polynomial X² + aa + b, where:
a = (31 + 32 - 2, b - (1 810 - 320 + a²o²,
(C.19)
GS: a = (31 + 32 + x²)0²² - 2, 6 (1 -1 -1-
(C.20)
Compared to Jacobi EG, the only difference between Gauss-Seided and Jacobi updates that the a²o² in b is now in a, which agrees with Theorem 2.3. Using Corollary 2.1, we can derive the Schur conditions equation 3.4 and equation 3.5.
More can be said if $1 + 32 is small. For instance, if 31 + + a 2/ then equation 3.4 implies equation 3.5. In this case, the first conditions equation 3.4 and equation 3.5 are equivalent, while the second condition of equation 3.4 strictly implies that of equation 3.5. Hence, the Schur region of Gauss-Seidel updates includes that of Jacobi updates. The same holds true if 3 + B2 377
More precisely, to show that the GS convergence region strictly contains that of the Jacobi convergence region, simply take 31 = 32 = B. The Schur condition for Jacobi EG and Gauss-Seide EG are separately:
J: a²=²" + (Bo² 11) < 1, GS: 0 30 < and |oo| 2 3
1)²
(C.21)
(C.22)
It can be shown that if B a² 3 and 0, equation C.21 is always violated whereas equation C.22 is always satisfied.
Conversely, give example when Jacobi EG converges while GS EG does not. Let Bi0²
3202 = 3 then Jacobi EG converges iff o² < whiie GS EG converges iff a²0² 1
2
4-
C.4 PROOF OF THEOREM 3.3: SCHUR CONDITIONS OF OGD
In this subsection, we fill in the details of the proof of Theorem 3.3, by first deriving the Schur conditions of OGD, and then studying the relation between Jacobi OGD and GS OGD.
Theorem 3.3 (OGD). For generalized OGD with a₁ Q2 = a, Jacobi and Gauss Causs-Seidel updates achieve linear convergence for any singular value a of E, we have:
3202 11, (a- 1-) 32) > 0, + (a (1) 32)02 > 0, J: a2 (8i02 +) (320 < (0) - 82) + B1 (1,3(31,320' -3))
(3.8)
(2)
02)0² <4,
GS:
(3.9)
(a.3,0² + (ola8820++13 (1 31.200
The convergence region of GS updates strictly include that of Jacobi updates.
The Jacobi characteristic polynomial now quartic in the form X + ax3 + bx² cA + d, with 2, a²0"² 1, aa(3, 02)0² d 31
(C.23)
Comparably, the GS polynomial equation 3.7 can reduced to cubic one A ax² Pb + c with
a = 2 + 000²,
((1 + 32)0² + 1, c 31320²
(C.24)
First we derive the Schur conditions equation 3.8 and equation 3.9. Note that other than Corollary 2.1. 1, equivalent Schur condition can be read from Cheng & Chiou (2007, Theorem 1) as:
16

---

Published as a conference paper at ICLR 2020
Theorem C.1 (Cheng & Chiou (2007)). A real quartic polynomial X + ax + bx? + cc d is Schur stable iff:
||| < 1, |a| d la <
(1 d) b+ d² - a(1 + d)c (1+ d)2 add
(C.25)
With equation C.23 and Theorem C.1, is straightforward to derive equation 3.8. With equation C.24 and Corollary 2.1, we can derive equation 3.9 without much effort.
Now, let us study the relation between the convergence region of Jacobi OGD and GS OGD, as given in equation 3.8 and equation 3.9. Namely, we want to prove the last sentence of Theorem 3.3. The outline of our proof is as follows. We first show that each region of (a, 31, ,32) described in equation 3.8 (the Jacobi region) is contained in the region described in equation 3.9 (the GS region). only studying
singular value, slightly abuse the notations and rewrite B, as 3, (i 1, 2) and ao as a. From equation 3.6 and equation 3.7, 31 and 32 can switch. WLOG, we assume B1 2 f2. There four cases consider:
Since
B1 2 82 0. The third Jacobi condition in equation 3.8 now is redundant, and we have
a > 31 or a < B2 for both methods. Solving the quadratic feasibility condition for a gives:
32 + V 4+ 5,3
B1 B<aa< u + Vu² + to
0 < B2
1,
B2
B1
(C.26)
2(1 + 35
t= (B) + () + 1). where (3 + 13 + 32), v = (1 B2 1)(118 10. 3)
On the other hand, assume a > B1, the first and third GS conditions are automatic, Solving the second gives:
<< 32 32 23 - -3 + 1
8 83
31 3<ac <<a<- (8.+ - V(: - 32) 16.
(C.27)
Define f(32) : -32 + v B2/2 and ((32) = (32 54+53))/2(( + B5)), and show that
f(32) 2 g(32).
(C.28)
Furthermore, can also be shown that given 0 < B2 < and B2 S 31 < <B(2),, we have
(u + v + 40)/t -8, + / + (1/2) (Bi 3²) 16.
(C.29)
B1 2 B2 = 0. The Schur condition for Jacobi and
updates reduces to:
2,
Jacobi: 0 < 31 < 1, B1 <a<
(C.30)
1 87
- + / 16 + 34
GS: 0 B1 22, 31 a
(C.31)
One can show that given 31 E (0, 1). we have 2 + BP) < (-81 + /I6 //2
31 2 0 > 32. Reducing the first, second and fourth conditions of equation 3.8 yields:
32 + + 532
B <a<as + Vu2 + to
32 < 0, <
(C.32)
2(1 + 32)
This region contains the Jacobi region. It can be similarly proved that even within this larger region, GS Schur condition equation 3.9 is always satisfied.
32 < 31 < O. We have < 0, to < O and thus a < (u + Vu + twwttt < 0. This contradicts our assumption that a > 0.
Combining the four cases above, know that the Jacobi region is contained in the GS region.
To show the strict inclusion, take 31 = B2 = a/5 and a + 0. One can show that as long as a is small enough, all the Jacobi regions do not contain this point, each of which described with
17

---

Published as a conference paper at ICLR 2020
singular value in equation 3.8. However, all the GS regions described in equation 3.9 contain this point.
The proof above is still missing equation C.29 and equation C.32 in the sub-sub-sections below, with the help of Mathematica, although can also verify these claims manually. Moreover, line proof of the inclusion can be given with Mathematica code, as shown in Section C.4.5.
details. We provide the proofs of equation C.26, equation C.28,
C.4.1 PROOF OF EQUATION C.26
The fourth condition of equation 3.8 can be rewritten as:
a 2ua < 0,
(C.33)
where u = (3132 + (3 + 1 3; + 1 -), ( 1)(3
1)( +1++ 1). The
discriminant is 4(u²2 tv) (1- ( 83 B833 3132) 2 0. Since if
31 < O,
+ -
0
If 31 2. 0,
07 32 + 83
31132
+ 82 (1
+ 31 2 0,
where we used |8182] < in both cases. So, equation C.33 becomes:
Vu= t <a<
V +
(C.34)
Combining with 31 or B2 obtained from the second condition, we have:
vu + to
u t
< < 82 or B1 <
(C.35)
t
The first case is not possible, with the following code:
u (bl b2 1) (bl + b2); v bl b2 (b1 12 + 1)
(b1 b2
3)
t (b1*2 1) (b2*2
1);
Reduce [b2 t > u - Sqrt [u*2 + v] & b1 >= b2 > 0
& Abs [bl b2] 11,
and we have:
False.
Therefore, the only possible case is <a< (u+ Vur - to)/t. Where the feasibility region be solved with:
Reduce [b1 u + (qr2( vj&<b1>>b2>0000b [b1 b2] 1]
What we get is:
0<b2<1 &
b2<=b1<b2/ (2 (1+b2*2)) Cgrt[(4+5 b2*2) (1+b222)) ~21
Therefore, we have proved equation C.26.
C.4.2 PROOF OF EQUATION C.28
With
Reduce [- (b2/2) + Sqrt [8 b2/2]/2 (b2 + Sqrt [4 5 b2*2]) / (2 (1 + b2*2))
& 0 < b2 < 1].
we can remove the first constraint and get:
0 < b2 1.
18

---

Published as a conference paper at ICLR 2020
C.4.3 PROOF EQUATION C.29
Given
Reduce [-1/2 (b1 + b2) + 1/2 Sqrt[(b1 b2) + 16]
(u + Sqrt [ + t vl) /t &
0 < b2 < &
b2 <= bl < (b2
Sqrt [4 b2^2]) (2 (1 62(2)), (b2, b1}],
can remove the first constraint and get:
0 < b2 < &
b2 <= bl < b2/ (2 (1 + 22)2))
1/2 Sqrt I (4 b2-2) (1 02^2)^2]-
C.4.4 PROOF OF EQUATION C.32
The second Jacobi condition simplifies to > A1 and the fourth simplifies to equation C.34. Combining with the first Jacobi condition:
Reduce [Abs [b1 b2] < 1
a > b1 & (u Sqrt [u^2 t v)) < a (u + Sqrt [u'2 t v] /t
& b1
b2 < (b2, bl, a} // Simplify,
we have:
b2 < 0 & b1 > 0 &
b2/ + b2*2) (q + / + b2(2) 22] > 2 bl &
b1 < a < (b1 b2 + b1*2 b2 bl 62*2) ( + b1*2) (1 b2*2)) +
(qrt[((-1 bl b2) (b1*2 b2*2 + bl 62 (-1 + b2*2)
b1*3 (b2 + b2 ((1 b1*2) ^ (1 (2-2)22)1
This can be further simplified achieve equation C.32.
C.4.5 ONE LINE PROOF
In fact, there another very simple proof:
Reduce [FrrAll[(bl, b2, a), (a - b1) (a
b2) > 0
& (a + b1)
(a + b2) -4 & Abs [bl b2]
1 &
a^2 (b1*2 1) (b2*2
1) (bl b2 1)
(2 (b1 + b2)
bl b2 (b1 b2 3)),
(a b1) (a - b2)
&
(a + b1) (a b2) <
& (a b1 1) (a b2 + 1) > (1 + b1 b2) (b2, b1, a]l
True.
However, this proof does not tell us much information about the range of our variables.
C.5 PROOF OF THEOREM 3.4: SCHUR CONDITIONS OF MOMENTUM
Theorem 3.4 (momentum). For the generalized momentum method with an = Q.2 = a. the Jacobi updates never converge, while the GS updates converge for any singular value of E, have:
|3,321 < - a² x² + 3 B2 + 81 3, 4(3 + 1)(2 + a²o?
a²0² < (23
32 B1 -3))
(3.12)
This condition implies that at least one of 31, 82 is negative.
C.5.1
SCHUR CONDITIONS OF JACOBI AND GS UPDATES
Jacobi condition We first rename and 81, as b1, b2. With Theorem C.I:
19

---

Published as a conference paper at ICLR 2020
(Abs [d] < 1, [bs[a] < d 3,
a + b + c + d 1> 0, - + b - d
0, (1 d) b - (c
d) (a c) (1 d) (1 2)
0) / (a -> -> - bl - b2, -> al*2 + +1 (b1 + b2) + bl b2,
-> bb b2 - bl b2, d b1 b2) // /ullsiimpliy
We obtain:
(Abs [bl b2] 1, Abs [2 b1 b2 < bl b2, al*2 0,
al*2 + 4 (1 b1) (1 + b2) > 0, al*2 (-1 b1 b2) ' < 0).
The last condition never satisfied and thus Jacobi momentum never converges.
Gauss-Seidel condition
With Theorem C.I, we compute:
(Abs [d] < 1, Abs [a] < d + 3, + b + c + + 1> 0, - b
+ d 1
0, (1 - 2) b + c02 a (1 + d) c (1 + d) (1 d) + a²2 d <
0) / (a -> 2 bl b2, b ->
-> 1 + (b1 + b2) b1 b2,
c -> -bl - b2 - -2-22h bl b2, d -> bl b2) // PullSimplify.
The result is:
(Abs [bl b2] < 1, Abs [2 - al^2 + b1 + b2] < 3 + b1 b2, al^2 > 0,
(1 + b1) (1 b2) al^2,
a1^2 (b1 + b2 + (-2 + a2^2 b1) b1 b2 + b1 (-1 + 2 b1) 62*2) < 0),
which can be further simplified equation 3.12.
C.5.2 NEGATIVE MOMENTUM
With Theorem 3.4, we can actually show that in general at least one of B1 and (32 must be negative. There are three cases to consider, and in each case we simplify equation 3.12:
1. 8,33 O. WLOG, let 32 = 0, and we obtain
-1 < B1 and a²0² 41)+
(C.36)
2. 8,33 O. We have
-1 <1< 0, -1 < < 00,00 000000 4(1 + B1)(1 B2)
(C.37)
3. 8,33 < 0. WLOG, assume 81 2 82. We obtain:
1
8
- < B2 < 0, 0 < 81 min
(C.38)
3,2
1 28
The constraints for a are a > 0 and:
max (1 31 (23 B2 B1
32)
] <
0
<
220
< 4(11 + 31)(1 + 32).
(C.39)
3132
These conditions can be further simplified by analyzing all singular values. They only depend on and on, the largest and the smallest singular values. Now, let us derive equation C.37, equation C.38 and equation C.39 more carefully. Note that we use for cc.
C.5.3 PROOF OF EQUATION C.37
Reduce [Abs
b2] < 1 & Abs [ 2 + b1 + b2 + 21 < b1 b2 + 3 &
(bl + 1) (b2 1) 2^2 &
a^2 bl b2 < (1 bl b2) (2 bl b2 - bl - b2) & bl 62 > 0 &
a > 0, (b2, bl, a]]
-1 < b2 &8 -1
< b1
< 0 & 0 a Sq + 4 b1 4 b2 + 4 b1 62]
20

---

Published as a conference paper at ICLR 2020
C.5.4 PROOF EQUATIONS C.38 AND C.39
Reduce [Abs [b1 b2] < & Abs [-a^2 + b1 b2 + 2] < b1 b2 + 3 &
4 (b1 + 1) (b2 - 1) > 2 &
a b1 62 < (1 b1 b2) (2 b1 b2 -b1 b2) & b1 62 < 0 &
b1 >= b2 & > 0, (b2, bl, a}l
(-1 < b2
(1/3) 6a (10 bl <= b2/ (-1 2 62) &
0 < a < Sq + 4 b1 4 b2 + 4 b1 b2]) 11 (b2/ (-1 + 2 b2) <
b1 < < b2))
sqrt[(-bl -
+
b2 + bin2 62 b1 62n2 - 2 b1 b2*2)
b1 b2)] < Sqrtlq <q< b1 4 b2 b1 b21))) 11 (113) <
b2 < 0 & ((0 < <= b2/ b2/
62) &
<
0 < a < 4 + b2
b1 b2])
11 (62/ (-1 2 b2) <
b1 < (
&&
Sqrt[(-b] - - 62 + b1 b2 + b1^2 62
b1 62 - 2 b1*2 62 /
b1 b2)] a Sq 4 b1 + 4 b2
4 b1 b2])))
Some further simplication yields equation C.38 and equation C.39.
D PROOFS IN SECTION 4
For bilinear games and gradient-based methods, a Schur condition defines the region of convergence in the parameter space, as we have seen in Section 3. However, is unknown which setting of parameters has the best convergence rate in Schur stable region. We explore this problem now. Due to Theorem 3.1, we do not need to study GD. The remaining cases are EG, OGD and GS momentum (Jacobi momentum does not converge due to Theorem 3.4). Analytically (Section D.1 and D.2), we study the optimal linear rates for EG and special cases of generalized OGD (Jacobi OGD with 3 = B2 and Gauss-Seidel OGD with 32 0). The special cases include the original form of OGD, We also provide details for the numerical method described at the end of Section 4.
The optimal spectral radius is obtained by solving another min-max optimization problem:
min max r(0,a). (ES((B)
(D.1)
where 0 denotes the collection of all hyper-parameters, and r(0, a) is defined as the spectral radius function that relies on the choice of parameters and the singular value a. We also use Sv Sv(E) to denote the set of singular values of E.
In general, the function r(0, a) is non-convex and thus difficult analyze. However, in the special case of quadratic characteristic polynomials, it is possible to solve equation D.1. This is how we will analyze EG and special cases of OGD, as r(0.0 .)) can be expressed using root functions of quadratic polynomials. For cubic and quartic polynomials, it is in principle also doable as we have analytic formulas for the roots. However, these formulas are extremely complicated and difficult to optimize and we leave it for future work. For EG and OGD, we will show that the optimal linear rates depend only on the conditional number K. == /
For simplicity, we always fix a1 = 02 = a > O using the scaling symmetry studied in Section 3.
D.1 PROOF OF THEOREM 4.1: OPTIMAL CONVERGENCE RATE OF EG
Theorem 4.1 (EG optimal). Both Jacobi and GS EG achieve the optimal exponent of linear conver-
gence r. = (k² 1)/(1²2 1) at a + 0 and 31 = $2 = =2/(of + ).). As K + co, r. + 1 2/
D.1.1 JACOBI EG
For Jacobi updates, if B1 === =8, by solving the roots of equation 3.2, the min-max problem is:
min max
Va'o² + (1 302)2
(D.2)
0 (ESv(E)
21

---

Published as a conference paper at ICLR 2020
01 o o, can simply take and B 1/o²² to obtain super-linear convergence rate. Otherwise, let us assume 01 > On. We obtain a lower bound by taking a + 0 and equation D.2 reduces to:
min max |1 - 330% B oESv(E)
(D.3)
The optimal solution given at 1 - 3o = ßa - 1, yielding 3 == 2/ + o.)). The optimal radius is thus (oî (o} + o since the lower bound equation D.3 can be achieved by taking - 0.
From general BI, 3g. it can be verified that the optimal radius is achieved at 31 = 32 and the problem reduces to the previous case. The optimization problem is:
min max r(a, BI, 3), a,81,52 (EV
(D.4)
where
/V [|1 (31 + 32)0² + (3 32)20 - 4020
310 -1-0-1)0)(111 320 a²o²
4a (8) B2) 4a² - (31 - 32)
r(a, (2,
In the first case, a lower bound is obtained at a² = (31 - =2)200//4 and thus the objective only depends on 31 + B2. In the second case, the lower bound is obtained a - 0 and 31 + $2. Therefore, the function is optimized at 31 = 32 and a + 0.
Our analysis above does not choice. For example, when 01 = on = 1, we can take B1 = + a and 33 = - a to obtain super-linear convergence rate.
that a and 3n 32 2/(oî o is the only optimal
D.1.2 GAUSS-SEIDEL EG
For Gauss-Seidel updates and 31 82 = 3, we do the following optimization:
min max a.3 oESv(F)
(D.5)
where by solving equation 3.3:
30²
a²0² 4(1 B002)
r(a, 3,0) = - (1- + (01-@oo224(188)1111
a²0² 2 4(1 - B00).
((a,8,00) is quasi-convex o², so we just need to minimize over a, 3 at both end points. Hence, equation D.5 reduces to: min max (1)) a,
< 4/0 we find that the minimum (x² - 1x/(k² 1) can be achieved at a + 0 and B = 2/ + +.)), the same as Jacobi EG. This is because a + 0 decouples x and y and it does not matter whether the update Jacobi or GS.
By arguing over three cases: a 43 4/0 a² 43 4/0 and 4/0 < a² + 1.4354/0
For general 31. 82 it can be verified that the optimal radius is achieved 3, 32. We do the following transformation: B, + - a2/2, so that the characteristic polynomial becomes:
(A 1)a + (51 (2 +)+ + (51 - a² 22/2((E2 - a² 2/22=* = 0.
(D.6)
Denote ε1 + Φ. and (51 a² /2)(2 a²/2) v, have:
x² - (2- )2 + 1 02 + oz + 0² = 0.
(D.7)
The discriminant is A = ( (0 (0² 4v) 2 We discuss two cases:
1. 8² 4v < 0. We minimizing:
min
1 (a² (a2 2 o)o + tofu V1+ (a² 6)0² t..
0,00,0
with a V b == maxfa, b} a shorthand. A minimizer is at a + and v - 0²/4 /4 (since d² 4v), where 31 = =9 2/(a? oR) and - 0.
22

---

Published as a conference paper at ICLR 2020
2. 6² 4v 2 0. A lower bound is: min [1 / /0
which is obtained iff 4a² ~ (d) 4u)l for all o². This only possible if a + and 6² + 4v, which yields 81 = $2 2/ oo))
which can be achieved 31 = 32 = 2/ + o and a + 0. Again, this might not be the only choice. For instance, take
From what has been discussed, the optimal radius is 10/-11/(a² +
σ1 0 1, from equation 3.3, super-linear convergence rate can be achieved at B1 1 and
82 = 1 a²
D.2 PROOF OF THEOREM 4.2: OPTIMAL CONVERGENCE RATE OF OGD
Theorem 4.2 (OGD optimal). For Jacobi OGD with B1 = 32 3, to achieve the optimal linear
rate, we must have I 23. For the original OGD with = 23, the optimal linear rate T, satisfies
1
(of (5o o v (?) -o?)),
(D.8)
4v207
at
3of (oî o2/3/2 /90 o + 6070 of
8. 2
(D.9)
0/02
If k - 00, ~ 1- 1/6" For Gauss-Seides OGD with B2 = 0, the optimal linear rate is To / 1), at v2/01 and $1 /2/l///////// (o} o.. If 0o, T. 1 1/k2.
For OGD, the characteristic polynomials equation 3.6 and equation 3.7 are quartic and cubic separately, and thus optimizing the spectral radii for generalized OGD is difficult. However, we can study two special cases: for Jacobi OGD, we take 31 = 82; for Seauss OGD, we take B3 In both cases, the spectral radius functions can be obtained by solving quadratic polynomials.
D.2.1 JACOBI OGD
We assume 31 = B2 = 3 this subsection. The characteristic polynomial for Jacobi OGD equation 3.6 can be written as:
22 1)2 (Aa - 000-- 0.
(D.10)
Factorizing it gives two equations which are conjugate to each other:
X(A 1) + i(Aa 8)o 0.
(D.11)
The roots of one equation are the conjugates the other equation. WLOG, we solve A(A - 1) +
i(Xa B) = 0 which gives (1/2) + r)), where
iao, U v V1-a"o2 a²0²
2i(a 23)a.
(D.12)
Denote A = 1 0²0 and A, = 2(a 2330. If 2 23, v can be expressed as:
0 22 V (VVAR Ai + A A i V A + A3 1/
V2 (a
(a ((i),))
(D.13)
therefore, the spectral radius r(a, 0) satisfies:
r(a, ((0,3
1 I (11 + a/v2/2 (ax b\V2)²) 1 + a20² 2
2202
A A + V2 + a)),
(D.14)
and the minimum is achieved at -28. From now on, we assume a S 23, and thus + ib. We write:
r(a, 0, m)x
/ 2 (as
b/V2)2) (11 a11 (ao + b/ b/v2)2)
= ( 01+0200 + A7 + 43 + V2 - al).
[1(1+a200 / A +
V2(boa - a)) 0 < 00 < 1, + + V2(bor - a)) a0 > 1.
(D.15)
23

---

Published as a conference paper at ICLR 2020
This is non-convex and non-differentiable function, which is extremely difficult to optimize.
At 23, in this case, /1- oign 4.8 and b /4 - 1sign(43 1). The sign function sign(z) is defined to if x > quasi-convex function:
and 0 otherwise. The function we are optimizing
r( (1+ (I++V1- 3o
48 S 1,
(D.16)
- V 4, 4,200 > 1.
We are maximizing over a and minimizing over 3. There are three cases:
43ao S 1. At 43 = 1, the optimal radius is:
- = 1 1+ 1
43 2 1. A1 the optimal radius satisfies:
n²
+ n2
2
43 < 1 and of 1. The optimal is achieved at:
1 / 48 2, B0 / 08 11
The solution is unique since the left is decreasing and the right increasing. The optimal is:
90 3o1 - (oî o2)33/ /90 - a 6ofa2 of
B.
(D.17)
4
0f
The optimal radius satisfies:
(0 -
2
(o)-o2)(50} - o + ( - o9) -2)))
(50
(D.18)
4v207
This is the optimal solution among the three cases. If o is small enough we have 2 ~ 1 1/3x33).
D.2.2 GAUSS-SEIDEL OGD
In this subsection, we study Gauss-Seidel OGD and fix B2 = 0. The characteristic polynomial equation 3.7 now reduces quadratic polynomial:
X + (a2o² 2) + a3,0²
For convenience, we reparametrize B1 - +//a.. So, the quadratic polynomial becomes:
X + (a=oa2 - 2) + 30²= 0.
We are doing min-max optimization min max, r(a, B,o), where r(a, B) is:
V 30²
00 4(a² - (3)
r(a, B,
(D.19)
1
20202 2| + 2 B)o
00 > 4(a² - B).
7
There are three cases to consider:
a oo 4(a² -3). We are minimizing - 3o over a and B. Optimizing over 3, gives 3 a=a² --a--a' -=a-aaoo/4 Then we minimize over and obtain a² 2/of. The optimal 1/0
and the optimal radius is /1- 1/K2.
24

---

Published as a conference paper at ICLR 2020
a ato 4(a² - B). Fixing a, the optimal 3 a² - a /4, and we solving
[212299 - + - Vo - o 100 -1
min max
We need discuss three cases: a² > >, oî < and 2/0 a² <//0 In the first case, the optimal radius is
- 1x
In the second case, a² - 2/07 and the optimal radius is / 11111/10 1/R2. In the third case, the optimal radius also /1 - 1/k² minimized at a² + 2/07.
of > 4(a² - 3) and ato² < 4(aa² - -). In this case, we have a² < 4. Otherwise, ((a,3,0)) 1. We are minimizing
1
0 2| 2V a0 V 10000-4a"01 48o2).
max 3
2
The minimum over ar achieved at o² and B = 2/(0f + 022) this gives a v2/01 and 31 = / o.)). The optimal radius r, v(k² 1)/(x²² II.
Out the three cases, the optimal radius is obtained in the third case, where r 1/x². This better than Jacobi OGD, but still worse than the optimal EG.
D.3 NUMERICAL METHOD
We first prove Lemma 4.1:
Lemma 4.1. A polynomial p(A) is r-Schur stable iff p(rA) is Schur stable.
Proof. Denote p(A) II:- (A A²). We have (() II - >r/r), and:
Vi E [m], Avl < < vi [n]. |A/rl <1
(D.20)
With Lemma 4.1 and Corollary 2.1, we have the following corollary:
Corollary D.1. A real quadratic polynomial X² aA + b r-Schur stable iff b < y² [:|a <r|rrb/rr; A real cubic polynomial X + ax² + bλ + r-Schur stable iff lc| 73, lar² + < br.
b acr² < r c²; A real quartic polynomial X ax3 bx + cd + d is r-Schur stable iff < 8 d², lar? + cl < br + d/r + and
lor adr
(cr² ad) (ar2 cc
b< 12 + dr
-4)2
Proof. In Corollary 2.1, rescale the coefficients according to Lemma 4.1.
We can use the corollaries above find the regions where r-Schur stability is possible, i.e., linear rate of exponent r. A simple algorithm might be to start from recursively take r++1 = sr; and find the Schur stable region S.+1 inside S, the region empty then stop the search and return S. can be taken to be, say, 0.99. Formally, this algorithm can be described as follows in Algorithm
1, find the region Sp. Then
To = 1, 0, 0.99: Find the Schur region Su: while S, not empty do
F++1 srr;
Find the re+1 -Schrr region St+1; t= 1=t+ 1;
end
Algorithm 1: Numerical method for finding the optimal convergence rate
In this algorithm, Corollary D.1 can be applied to obtain any r-Schur region.
25

---

Published as a conference paper at ICLR 2020
0.00
0005
-1
-0.1
-0.15
-3
0.0
0.2
-5
-2.5
0.0
2.5
-2.5
0.0
0.5
3.5
0.00
3.0
1.2
-0.55
2.5
1.5
-0.0
1.0
2.0
-0.15
2.5
1.0
Figure 6: Test samples generated from the generator network trained with stochastic Adam. Top row: Jacobi updates; Bottom row: Gause-Seidel updates. Columns (left to right): epoch 5, 10, 20.
E SUPPLEMENTARY MATERIAL FOR SECTIONS 5 AND
We provide supplementary material for Sections 5 and 6. We first prove that when learning the mean Gaussian, WGAN is locally a bilinear game Appendix E.1. For mixtures of Gaussians, provide supplementary experiments about Adam in Appendix F.2. This result implies that in some cases, Jacobi updates are better than GS updates. We further verify this claim Appendix E.3 by showing an example of OGD on bilinear games. Optimizing the spectral radius given a certain singular value is possible numerically, as in Appendix E.4.
E. WASSERSTEIN GAN
Inspired by Daskalakis et al. (2018), we consider the following WGAN (Arjovsky et al., 2017):
f( 0) min max E Ee [s x)] (s (2+ Φ))},
(E.1)
with s(x) == 1/(1+ the sigmoid function. We study the local behavior near the saddle point
O), which depends on the Hessian:
V
V2
- Es 0)
EO 2 0² + s'000=00 2) Eg 1 x x) Es 2)z2
(V2 (00)
B
00
with F., shorthand for (e and E.g for Eg-N( At the saddle point, the Hessian is simplified as:
s())T
0
-I/4
-())
I/4
B
00
Therefore, this WGAN is locally bilinear game.
E.2 MIXTURES OF GAUSSIANS WITH ADAM
Given the same parameter settings in Section 5, train the vanilla GAN using Adam, with the step size a = 0.0002, and 3 = 0.9, 82 = 0.999. As shown in Figure 6, Jacobi updates converge faster than the corresponding GS updates.
26

---

Published as a conference paper at ICLR 2020
1.0
0.8
0.6
Bo
0.4
0.2
0.0
0.0
0.5
1.0
1.5
2.0
ad
Figure 7: Contour plot of spectral radius equal to 0.8. The red curve for the Jacobi polynomial and the blue curve is for the GS polynomial. The GS region is larger but for some parameter settings, Jacobi OGD achieves a faster convergence rate.
E.3 JACOBI UPDATES MAY CONVERGE FASTER TIIAN GS UPDATES
Take 0.9625, 8 0.790283 and 0.816572 (by solving equation 3.6 and equation 3.7), which means that Jacobi OGI) has better performance for this setting of parameters. A more intuitive picture is given Figure where we take 31 32 = B.
0.5722, and 1, the Jacobi and GS OGD radii separately
E.4 SINGLE SINGULAR VALUE
We minimize r(0, σr) for a given singular value numerically. WLOG, we take 1, since we can rescale parameters to obtain other values a. implement grid search for all the parameters within the range [- 2] and step size 0.05. For the step size a, take it to be positive. We use {a, b, $} as a shorthand for {a, a + 8, a b).
We first numerically solve the characteristic polynomial for Jacobi OGD equation 3.6, fixing a with scaling symmetry. With E {0, 2, 0.05). 9 E {-2, 2, 0.05). the best parameter setting is a 0.7, 31 0.1 and 0.6. 31 and 83 can be switched. The optimal radius is 0.6.
We also numerically solve the characteristic polynomial for Gauss-Seide OGD equation 3.7, fixing a 02 = a with scaling symmetry. With a E {0, 2, 0.05), ), B E (-2, 2, 0.05]. the best parameter setting is a 1.4, B1 0.7 and B3 0. A1 and Bg can be switched. The optimal rate is 1/(5v2). This rate can be further improved to be zero where v2, = 1/V2 and B2 0.
Finally, we numerically solve the polynomial for Causs-Seides momentum equation 3.11, with the same grid. The optimal parameter choice is a 1.8. 31 -0.1 and 3n -0.05. 31 and 32 can be switched. The optimal rate is 0.5.
F SPLITTING METHOD
In this appendix, we interpret the gradient-based algorithms (except PP) we have studied in this paper splitting methods (Saad, 2003), for both Jacobi and Gauss Seidel updates. By doing this, one can understand our algorithms better the context numerical linear algebra and compare our results in Section 3 with the Stein-Rosenberg theorem.
27

---

Published as a conference paper at ICLR 2020
F.1
JACOBI UPDATES
From equation 2.2, finding saddle point is equivalent to solving:
0
E
b
Sz
d.
(F.I)
E
y
Now, we try to understand the Jacobi algorithms using splitting method. For GD and EG, the method splits S into M N and solve
2++1
Nz: + M
(F.2)
For GD, we can obtain that:
01
0j
E 012
M
N
(F33
02
1
1-1
I
For EG, we need to compute an inverse:
01
31 E
M
N M
S.
(R.4)
E
02
Given det(a1az2 -,3,EET) * the inverse always exists.
The splitting method can also work for second-step methods, such as OGD and momentum. We split M N P and solve:
2++1
M
Nz + M Pz M M d.
(F.5)
For OGD, we have:
E
0
a1 a1-91
01-31
0
B.
M
01
N
P
(R6)
88
02
02
9g
E
P2
0
a2
02-BB B2
02- 82
For the momentum method, we can write:
M
01
0
I
022
N
1+ I
a1 E
1+:2 02
- E
P
01
81
0
1
&
0
(F.7)
F.2 CEUSS-SEIDEL UPDATES
Now, we try to understand the GS algorithms using splitting method. For GD and EG, the method splits S into M N and solve
2++1
M
Nz.
M
(F88
For GD, we can obtain that:
M
a
N
aj
I
E 022
(F99)
E
02
11
I
For EG, we need to compute an inverse:
a
E E
M (B2 + a102) E
N M S.
(F.10)
02 (I
31 E E)
The splitting method can also work for second-step methods, such as OGD and momentum. We split S = M- N and solve:
Z++1
M M N
M 1 P
(F.11)
For OGD, we obtain:
E
81
a1-Bi
M
NN
P
(F.12)
E
T
0
02 - 82
022
0g 80--3 3g
02 - 82
For the momentum method, we can write:
I
0
1+:1 I
E
M =
E
02
N
=
1- I
P =
0
03
(F.13)
28

---

Published as a conference paper at ICLR 2020
G SINGULAR BILINEAR GAMES
In this paper we considered the bilinear game when is a non-singular square matrix for simplicity. Now let us study the general case where Ruxx, As stated in Section saddle points exist iff
b E RER) CER(EE)
(G.1)
Assume b Eb', E c'. One shift the origin of and y: x b. y + d, such that the linear terms cancel out. Therefore, the min-max optimization problem becomes:
min max x² Ey. #ER" yER"
(G.2)
The set of saddle points is:
(<x yyly E (N a EN(E )}-
(G.3)
For all the first-order algorithms we study in this paper, x+)) E x +R()) and ( E ( Since for any matrix X E I R(X) @ N(X R if the algorithm converges saddle point, then this saddle point is uniquely defined by the initialization:
x²
PE (0) y y
(G.4)
where
I
(G.5)
the orthogonal projection operator onto the null space of X, and X denotes the Moore-Penross, pscudoinverse. Therefore, the convergence to the saddle point is described by the distances of (t) and ( to the null spaces (EET) and (E). We consider the following measure:
A = E Ey 12 + EE 11,
(G.6)
the Euclidean distance of z (t) (z( y (*) the space of saddle points N(ET) (E).
Consider the singular value decomposition E:
Σ, U
E
(G.7)
0
with Σ, E Rrxr diagonal and non-singular. Define:
(+) V
r U (1)
(G.8)
and equation G.6 becomes:
A 1| + || 112
(G.9)
with e, denoting the sub-ves vector with the first r elements of Hence, the convergence of the bilinear game with singular matrix E reduces to the convergence of the bilinear game with non-singular matrix E,, and all our previous analysis still holds.
29


Reviews:
[{"review_id": "SJepczfJ5r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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 convergence of multiple methods (Gradient, extragradient, optimistic and momentum) on a bilinear minmax game. More precisely, this paper uses spectral condition to study the difference between simultaneous (Jacobi) and alternating (Gau\\ss-Seidel) updates. The analysis is based on Schur theorem and give necessary and sufficient condition for convergence. \n \n*Decision*\nThis paper tries to study a phenomenon that has known a recent surge of interest due to the numerous practical minmax application: the impact of alternating updates in minmax optimization. This problem is challenging because most of the theoretical analysis techniques have been developed to analyse simultaneous updates. \nI think that this paper has treated well the related work and underlines well its contributions. \nEven if the main contribution are theoretical the authors of this paper provide some experiments to confirm that the theory provides some meaningful insights.\nHowever, I have the concern that the study is still limited to bilinear example and thus it is not clear how to apply it to non-bilinear objective (even locally because since the Jacobian has pure imaginary eigenvalues, even locally the Jacobian may have eigenvalues with negative real part).\nMoreover this work do not provides significantly better (factor 8 improvement in the constants) convergence rate that the one provided on the literature (Tseng 1995, Mokthari et al 2019, Gidel et al. 2019) to solve bilinear games. The contributions is more about proving new (interesting) analysis tools and showing a better robustness of GS updates with respect to hyperparameter tunning. \nTo me, it is an accept.\n\n*Questions*\n- In Theorem 4.1 and 4.2 you use the word ‘optimal exponent’. In what sense these algorithms are optimal ? Usually the sense of optimal is when you achieve the lower bound of convergence. Is it the case here ?\n- Right after theorem 2.3 you claim that GS updates simply leads to a shift of index for $L_i$ setting $L_{k+1}=0$ but it seems to me that then $\\lambda L_1$ is missing in the sum. Is it just an unfortunate oversight? Does it affect the proofs of you main theorems ? These results only marginally (improve by a factor 8) improve upon Moktari et al. (2019).\n \n*Remarks*\n- To me the J and GS conditions in Theorem 3.2, 3.3 and 3.4 are more Lemmas than Theorems: They are condition that are hard to interpret and they have small interest if one cannot conclude on simple conditions (such as the ones you actually provide in the Theorem). My point is that providing such complicated conditions without condition is only half solve the problem of convergence.  In that sense, in the discussion of Theorem 3.4, you are a bit unfair with Gidel et al (2019) since unlike them you do not provide any convergence rate. On one side theorem 3.4 gives an interesting characterization for the convergence (that leads to the fact that at least one of the beat has to be negative) but if it does not lead to any rate it is a less interesting result. \n- In Table 1 and 2, $\\alpha,\\beta_1$ and $\\beta_2$ have not been introduced. It is thus hard to get the most of them.\n- Theorem 3.1 has been stated in previous works (like for instance Gidel et al 2019). You should not claim it as a contribution.\n\n=== After rebuttal === \nI've read the authors's response.\nI agree with the concerns raised by Reviewer 2 regarding the experimental part and whether or not such theoretical study (far from the practical aspect) are of interest to the ICLR community.\nI think that that paper would be more suited for a theoretical venue such as AISTATS (or ICML) but I also think that this work remains of interest to the ICLR community.  \nI am not convinced by the fact that this analysis could be generalized beyond bilinear game with a local analysis  because even an arbitrarily small perturbation can transform a bilinear example into a non-stable equilibrium (with no hope of local convergence), take for instance \n$$ \\min_x \\max_y -\\epsilon \\|x\\|^2 +  x^\\top A y + \\epsilon \\|y\\|^2$$\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1gglldXqB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "1) Summary\nThe manuscript presents a theoretical convergence analysis of gradient-based saddle point algorithms to solve min-max problems with a bilinear objective function. In particular, the analysis covers block updates and joint updates.\n\n2) Quality\nThe paper -- being a theoretical analysis rather than a new algorithm -- seems mathematically rigorous but lacks motivation and also explanation.\n\n3) Clarity\nThe notation is pretty clear and the results seem convincing but the mathematical formulation in eq. 2.1 and related assumptions (E being invertible, b and c being) need to be better justified in order to make the paper accessible to a broader audience. \n\n4) Reproducibility\nThe data is mainly synthetic and the codes for the update schemes are available. This should render the results reproducible.\n\n5) Evaluation\nThe evaluation is on synthetic settings and the results on the convergence seem convincing but a subtantial optimization problem remains for future work.\n\n6) Questions/Issues\n  A) Not sure about the implications, isn't the set of saddle points in eq (2.2) equivalent to x=y=0? If this is intended, there needs to be some explanation.\n  B) It is not clear how well the results of the bilinear setting are applicable to the general case of bivariate functions. E.g. below eq (2.5) and below eq (5.1). There needs to be more justification.\n  C) The start of Section 2 kicks off a little rough i.e. the formal setting could be better motivated.\n\n7) Details\n  a) Section 2, below eq 2.2: \"biliner games\" -> \"bilinear games\"\n  b) Capitalization in references: Nash, GAN, Potenzreihen, Einheitskres\n  c) References: \"méthode iterative de résolution d'une équation variationelle\"", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "B1lJvI1CKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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:\nThe paper presents exact conditions for the convergence of several gradient based methods for solving bilinear games. In particular, the methods under study are Gradient Descent(GD), Extragradient (EG), Optimizatic Gradient descent (OGD) and Momentum methods. For these methods, the authors provide convergence rates (with optimal parameter setup) for both alternating (Gauss-Seidel) and simultaneous (Jacobi) updates.   \n\nComments:\nThe paper is well written and the main contributions are clear. \nI find the theoretical results of the paper interesting and promising, however i believe that the proposed analysis will be difficult to extend beyond bilinear games to more practical scenarios as the authors claim.  In particular, the proposed analysis is based on understanding the bilinear game dynamics using spectral analysis. This approach is not novel. It is well known for bilinear games (see for example [1] and the references therein) and is not easy to extent to general games.\n\nThe authors provide necessary and sufficient conditions under witch all previously mentioned algorithms (GD, EG, OGD,Momentum) converge for bilinear games. The convergence analysis  (Theorems 3.1 -3.4) is easy to follow and seems correct. \n\nMain issue: The authors mentioned in their abstract that \"... and understanding the dynamics of (stochastic ) gradient algorithms for solving ...\". In addition in their figures 4 and 5 they compare stochastic methods. However there is no convergence analysis on stochastic variants of the proposed methods. Note that in [2], it was shown that stochastic variants can prevent the convergence of standard game optimization methods, while their deterministic version converges. \nIf the goal of the last experiment is to show that the proposed methods and analysis can be extended to more interesting general settings then the algorithms analyzed in the paper should be used in the numerical evaluation and not their stochastic variants. The authors should be more clear (from the abstract) on what algorithms they study. The paper clearly focuses on deterministic (full gradient) methods. \n\nTo conclude I liked the paper and the theoretical analysis seems correct however i am not convinced that the results could be of interest for the ICLR community. It focuses only on simple bilinear zero-sum games and on deterministic methods for solving them. \n\nMinor Comments:\npage 2, bellow eq 2.2 biliner---> bilinear\npage 3 bellow eq. 2.6: Cesari---> Cesaro\nIn caption of figure 2: replace the x-axis and y-axis with horizontal axis and vertical axis respectively.\n\nReferences:\n[1] Gidel, Gauthier, Reyhane Askari Hemmat, Mohammad Pezeshki, Remi Lepriol, Gabriel Huang, Simon Lacoste-Julien, and Ioannis Mitliagkas. \"Negative momentum for improved game dynamics.\" arXiv preprint arXiv:1807.04740 (2018).\n\n[2] Chavdarova, Tatjana, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien. \"Reducing noise in gan training with variance reduced extragradient.\" arXiv preprint arXiv:1904.08598 (2019).\n\n========= after rebuttal =============\n   I would like to thank the authors for the reply. After reading their response and the comments of the other reviewers I  decide to update my score to \"weak accept\".\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers found the work interesting but worried about the extension to non-bilinear games. This is a point the authors should explicitly address in their work before publication.
Decision: Accept (Poster)