Min-max formulations have attracted great attention in the ML community due to the rise of deep generative models and adversarial methods, and understanding the dynamics of (stochastic) gradient algorithms for solving such formulations has been 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. Min-max optimization has received significant attention recently due to the popularity of generative adversarial networks (GANs) (Goodfellow et al., 2014) and adversarial training (Madry et al., 2018) , just to name some examples. Formally, given a bivariate function f (x, y), we aim to find a saddle point (x * , y * ) such that f (x * , y) ≤ f (x * , y * ) ≤ f (x, y * ), ∀x ∈ R n , ∀y ∈ R n . (1.1) Since the beginning of game theory, various algorithms have been proposed for finding saddle points (Arrow et al., 1958; Dem'yanov & Pevnyi, 1972; Gol'shtein, 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 to 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 analysis mostly focused on bilinear games or strongly-convex-strongly-concave games (Tseng, 1995; Daskalakis et al., 2018; Gidel et al., 2019b; Liang & Stokes, 2019; Mokhtari et al., 2019b) . Nonzero-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) . It is well-known that certain gradient algorithms converge linearly on bilinear zero-sum games (Liang & Stokes, 2019; Mokhtari et al., 2019b; Rockafellar, 1976; Korpelevich, 1976) . These iterative algorithms usually come with two versions: Jacobi style updates or Gauss-Seidel (GS) style. In a Jacobi style, we update the two sets of parameters (i.e., x and y) simultaneously whereas in a GS style we update them alternatingly (i.e., one after the other). Thus, Jacobi style updates are naturally amenable to 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 to 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? • 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? Table 2 : Optimal convergence rates. In the second column, β * denotes a specific parameter that depends on σ 1 and σ n (see equation 4.2). In the third column, the linear rates are for large κ. The optimal parameters for both Jacobi and Gauss-Seidel EG algorithms are the same. α denotes the step size (α 1 = α 2 = α), and β 1 and β 2 are hyper-parameters for EG and OGD, as given in §2. Algorithm α β 1 β 2 rate exponent Comment Jacobi and Gauss-Seidel Jacobi OGD 2β 1 β * β 1 ∼ 1 − 1/(6κ 2 ) β 1 = β 2 = α/2 GS OGD √ 2/σ 1 √ 2σ 1 /(σ Contributions We summarize our main results from §3 and §4 in Table 1 and 2 respectively, with supporting experiments given in §5. We use σ 1 and σ n to denote the largest and the smallest singular values of matrix E (see equation 2.1), and κ := σ 1 /σ n denotes the condition number. The algorithms will be introduced in §2. Note that we generalize gradient-type algorithms but retain the same names. Table 1 shows that in most cases that we study, whenever Jacobi updates converge, the corresponding GS updates converge as well (usually with a faster rate), but the converse is not true ( §3). This extends the well-known Stein-Rosenberg theorem to bilinear games. Furthermore, Table 2 tells us that by generalizing existing gradient algorithms, we can obtain faster convergence rates. In this work we focus on the convergence behaviour of gradient-based algorithms for solving bilinear games. By drawing a connection to discrete linear dynamical systems ( §2) and using Schur's theorem, we provide necessary and sufficient conditions for a variety of gradient algorithms, for both simultaneous (Jacobi) and alternating (Gauss-Seidel) updates. Our results show that Gauss-Seidel updates converge more easily than Jacobi updates. Furthermore, we find the optimal exponents of linear convergence for EG and OGD, and provide a numerical method for searching that exponent. We performed a 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 be 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 a powerful machinery that can be applied in such problems and beyond. It would be interesting to generalize our results to the constrained case (even for bilinear games), initiated in the recent work of Daskalakis & Panageas (2019) . Extending our results to account for stochastic noise (as empirically tested in our experiments) is another interesting direction, with some initial results in Gidel et al. (2019a A PROXIMAL POINT (PP) ALGORITHM PP was originally proposed by Martinet (1970) with α 1 = α 2 and then carefully studied by Rockafellar (1976) . The linear convergence for bilinear games was also proved in the same reference. Note that we do not consider Gauss-Seidel PP since we do not get a meaningful solution after a shift of steps 2 . where x (t+1) and y (t+1) are given implicitly by solving the equations above. For bilinear games, one can derive that: We can compute the exact form of the inverse matrix, but perhaps an easier way is just to compute the spectrum of the original matrix (the same as Jacobi GD except that we flip the signs of α i ) and perform λ → 1/λ. Using the fact that the eigenvalues of a matrix are reciprocals of the eigenvalues of its inverse, the characteristic equation is: With the scaling symmetry (α 1 , α 2 ) → (tα 1 , α 2 /t), we can take α 1 = α 2 = α > 0. With the notations in Corollary 2.1, we have a = −2/(1 + α 2 σ 2 ) and b = 1/(1 + α 2 σ 2 ), and it is easy to check |a| < 1 + b and b < 1 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 is rarely used in practice since it is an implicit method, i.e., one needs to solve (x (t+1) , y In this section we apply Theorem 2.1 to prove Theorem 2.3, an interesting connection between Jacobi and Gauss-Seidel updates: and L i is strictly lower block triangular. Then, the characteristic polynomial of Jacobi updates is p(λ, 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., all blocks are updated simultaneously): . . . . . . where A i,j is the j-th column block of A i . For each matrix A i , we decompose it into the sum where L i is the strictly lower block triangular part and U i is the upper (including diagonal) block triangular part. Theorem 2.1 indicates that the convergence behaviour of equation B.1 is governed by the largest modulus of the roots of the characteristic polynomial: Alternatively, we can also consider the updates in the sense of Gauss-Seidel (i.e., blocks are updated sequentially): We can rewrite the Gauss-Seidel update elegantly 3 as: i.e., where L k+1 := 0. Applying Theorem 2.1 again we know the convergence behaviour of the GaussSeidel update is governed by the largest modulus of roots of the characteristic polynomial: Note that A 0 = −I and the factor det(I − L 1 ) −1 can be discarded since multiplying a characteristic polynomial by a non-zero constant factor does not change its roots. B.2 PROOF OF COROLLARY 2.1 Corollary 2.1 (e.g. Mansour (2011)) . A real quadratic polynomial λ 2 + aλ + b is Schur stable iff b < 1, |a| < 1 + b; A real cubic polynomial λ 3 + aλ 2 + bλ + c is Schur stable iff |c| < 1, Proof. It suffices to prove the result for quartic polynomials. We write down the matrices: We require det( 2 and thus |c − ad| < 1 − d 2 due to the first condition. δ 4 > 0 simplifies to: 14) which yields |a + c| < |b + d + 1|. Finally, δ 3 > 0 reduces to: Denote p(λ) := λ 4 + aλ 3 + bλ 2 + cλ + d, we must have p(1) > 0 and p(−1) > 0, as otherwise there is a real root λ 0 with |λ 0 | ≥ 1. Hence we obtain b + d + 1 > |a + c| > 0. Also, from |c − ad| < 1 − d 2 , we know that: So, the second factor in B.15 is negative and the positivity of the first factor reduces to: To obtain the Schur condition for cubic polynomials, we take d = 0, and the quartic Schur condition becomes: To obtain the Schur condition for quadratic polynomials, we take c = 0 in the above and write: The proof is now complete.
We systematically analyze the convergence behaviour of popular gradient algorithms for solving bilinear games, with both simultaneous and alternating updates.
{"src": "scitldr-AIC_train", "paper_id": "SJlVY04FwH"}