Title: LAST-ITERATE CONVERGENCE RATES FOR MIN-MAX OPTIMIZATION

Abstract: While classic work in convex-concave min-max optimization relies on averageiterate convergence results, the emergence of nonconvex applications such as training Generative Adversarial Networks has led to renewed interest in last-iterate convergence guarantees. Proving last-iterate convergence is challenging because many natural algorithms, such as Simultaneous Gradient Descent/Ascent, provably diverge or cycle even in simple convex-concave min-max settings, and previous work on global last-iterate convergence rates has been limited to the bilinear and convex-strongly concave settings. In this work, we show that the HAMILTONIAN GRADIENT DESCENT (HGD) algorithm achieves linear convergence in a variety of more general settings, including convex-concave problems that satisfy a novel "sufficiently bilinear" condition. We also prove convergence rates for stochastic HGD and for some parameter settings of the Consensus Optimization algorithm of Mescheder et al. (2017) .

1. INTRODUCTION:

In this paper we consider methods to solve smooth unconstrained min-max optimization problems. In the most classical setting, a min-max objective has the form

min x1 max x2 g(x 1 , x 2 )

where g : R d × R d → R is a smooth objective function with two inputs. The usual goal in such problems is to find a saddle point, also known as a min-max solution, which is a pair

EQUATION

for every x 1 ∈ R d and x 2 ∈ R d . Min-max problems have a long history, going back at least as far as Neumann (1928) , which formed the basis of much of modern game theory, and including a great deal of work in the 1950s when algorithms such as fictitious play were explored (Brown, 1951; Robinson, 1951) .

The convex-concave setting, where we assume g is convex in x 1 and concave in x 2 , is a classic min-max problem that has a number of different applications, such as solving constrained convex optimization problems. While a variety of tools have been developed for this setting, a very popular approach within the machine learning community has been the use of so-called no-regret algorithms (Cesa-Bianchi & Lugosi, 2006; Hazan, 2016) . This trick, which was originally developed by Hannan (1957) and later emerged in the development of boosting (Freund & Schapire, 1999) , provides a simple computational method via repeated play: each of the inputs x 1 and x 2 are updated iteratively according to no-regret learning protocols, and one can prove that the average-iterates (x 1 , x2 ) converge to a min-max solution.

Recently, interest in min-max optimization has surged due to the enormous popularity of Generative Adversarial Networks (GANs), whose training involves solving a nonconvex min-max problem where x 1 and x 2 correspond to the parameters of two different neural nets (Goodfellow et al., 2014) . The fundamentally nonconvex nature of this problem changes two things. First, it is infeasible to find a "global" solution of the min-max objective. Instead, a typical goal in GAN training is to find a local min-max, namely a pair (x * 1 , x * 2 ) that satisfies (1) for all (x 1 , x 2 ) in some neighborhood of (x * 1 , x * 2 ).

Second, iterate averaging lacks the theoretical guarantees present in the convex-concave setting. This has motivated research on last-iterate convergence guarantees, which are appealing because they more easily carry over from convex to nonconvex settings.

Last-iterate convergence guarantees for min-max problems have been challenging to prove since standard analysis of no-regret algorithms says essentially nothing about last-iterate convergence.

Widely used no-regret algorithms, such as Simultaneous Gradient Descent/Ascent (SGDA), fail to converge even in the simple bilinear setting where g(x 1 , x 2 ) = x 1 Cx 2 for some arbitrary matrix C. SGDA provably cycles in continuous time and diverges in discrete time (see for example Daskalakis et al. (2018) ; Mescheder et al. (2018) ). In fact, the full range of Follow-The-Regularized-Leader (FTRL) algorithms provably do not converge in zero-sum games with interior equilibria (Mertikopoulos et al., 2018) . This occurs because the iterates of the FTRL algorithms exhibit cyclic behavior, a phenomenon commonly observed when training GANs in practice as well.

Much of the recent research on last-iterate convergence in min-max problems has focused on asymptotic or local convergence (Mertikopoulos et al., 2019; Mescheder et al., 2017; Daskalakis & Panageas, 2018; Balduzzi et al., 2018; Letcher et al., 2019; Mazumdar et al., 2019) . While these results are certainly useful, one would ideally like to prove global non-asymptotic last-iterate convergence rates. Provable global convergence rates allow for quantitative comparison of different algorithms and can aid in choosing learning rates and architectures to ensure fast convergence in practice. Yet despite the extensive amount of literature on convergence rates for convex optimization, very few global last-iterate convergence rates have been proved for min-max problems. Existing work on global last-iterate convergence rates has been limited to the bilinear or convex-strongly concave settings (Tseng, 1995; Liang & Stokes, 2019; Du & Hu, 2019; Mokhtari et al., 2019) . In particular, the following basic question is still open:

"What global last-iterate convergence rates are achievable for convex-concave min-max problems?"

Our Contribution Understanding global last-iterate rates in the convex-concave setting is an important stepping stone towards provable last-iterate rates in the nonconvex-nonconcave setting.

Motivated by this, we prove new linear last-iterate convergence rates in the convex-concave setting for an algorithm called HAMILTONIAN GRADIENT DESCENT (HGD) under weaker assumptions compared to previous results. HGD is gradient descent on the squared norm of the gradient, and it has been mentioned in Mescheder et al. (2017) ; Balduzzi et al. (2018) . Our results are the first to show non-asymptotic convergence of an efficient algorithm in settings that not linear or strongly convex in either input. In particular, we introduce a novel "sufficiently bilinear" condition on the second-order derivatives of the objective g and show that this condition is sufficient for HGD to achieve linear convergence in convex-concave settings. The "sufficiently bilinear" condition appears to be a new sufficient condition for linear convergence rates that is distinct from previously known conditions such as the Polyak-Łojasiewicz (PL) condition or pure bilinearity. Our analysis relies on showing that the squared norm of the gradient satisfies the PL condition in various settings. As a corollary of this result, we can leverage Karimi et al. (2016) to show that a stochastic version of HGD will have a last-iterate convergence rate of O(1/ √ k) in the "sufficiently bilinear" setting. On the practical side, while vanilla HGD has issues training GANs in practice, Mescheder et al. (2017) show that a related algorithm known as Consensus Optimization (CO) can effectively train GANs in a variety of settings, including on CIFAR-10 and celebA. We show that CO can be viewed as a perturbation of HGD, which implies that for some parameter settings, CO converges at the same rate as HGD.

Figure 1 : HGD converges quickly, while SGDA spirals. This nonconvex-nonconcave objective is in defined in Appendix K.

We begin in Section 2 with background material and notation, including some of our key assumptions. In Section 3, we discuss Hamiltonian Gradient Descent (HGD), and we present our linear convergence rates for HGD in various settings. In Section 4, we present some of the key technical components used to prove our results from Section 3. Finally, in Section 5, we present our results for Stochastic HGD and Consensus Optimization. The details of our proofs are in Appendix H.

2. BACKGROUND:



2.1. PRELIMINARIES:

In this section, we discuss some key definitions and notation. We will use ||•|| to denote the Euclidean norm for vectors or the operator norm for matrices or tensors. For a symmetric matrix A, we will use λ min (A) and λ max (A) to denote the smallest and largest eigenvalues of A. For a general real matrix A, σ min (A) and σ max (A) denote the smallest and largest singular values of A.

Definition 2.1. A critical point of f : R d → R is a point x ∈ R d such that ∇f (x) = 0. Definition 2.2 (Convexity / Strong convexity). Let µ ≥ 0. A function f : R d → R is µ-strongly convex if for any u, v ∈ R d , f (u) ≥ f (v) + ∇f (v), u -v + µ 2 ||u -v||. When f is twice- differentiable, f is µ-strongly-convex iff for all x ∈ R d , ∇ 2 f (x) µI. If µ = 0 in either of the above definitions, f is called convex. Definition 2.3 (Monotone / Strongly monotone). Let µ ≥ 0. A vector field v : R d → R d is µ-strongly monotone if for any x, y ∈ R d , x -y, v(x) -v(y) ≥ µ ||x -y|| 2 . If µ = 0, v is called monotone. Definition 2.4 (Smoothness). A function f : R d → R is L-smooth if f is differentiable everywhere and for all u, v ∈ R d satisfies ||∇f (u) -∇f (v)|| ≤ L ||u -v||.

Notation Since g is a function of x 1 ∈ R d and x 2 ∈ R d , we will often consider x 1 and x 2 to be components of one vector x = (x 1 , x 2 ). We will use superscripts to denote iterate indices. Following Balduzzi et al. (2018) , we use ξ = (∇ x1 g, -∇ x2 g) to denote the signed vector of partial derivatives. Under this notation, the Simultaneous Gradient Descent/Ascent (SGDA) update can be written as k) ).

x (k+1) = x (k) -ηξ(x (

We will use J to denote the Jacobian of ξ, i.e.

J ≡ ∇ξ = ∇ 2 x1x1 g ∇ 2 x1x2 g -∇ 2 x2x1 g -∇ 2 x2x2 g

. Note that unlike the Hessian in standard optimization, J is not symmetric, due to the negative sign in ξ. When clear from the context, we often omit dependence on x when writing ξ, J, g, H, and other functions. Note that ξ, J, and H are defined for a given objective g -we omit this dependence as well for notational clarity. We will always assume g is sufficiently differentiable whenever we take derivatives. In particular, we assume second-order differentiability in Section 3.

We will also use the following non-standard definition for notational convenience:

Definition 2.5 (Higher-order Lipschitz). A function g :

R d → R is (L 1 , L 2 , L 3 )-Lipschitz if for all x ∈ R d , ||ξ(x)|| ≤ L 1 and ||∇ξ(x)|| ≤ L 2 , and for all x, y ∈ R d , ||∇ξ(x) -∇ξ(y)|| ≤ L 3 ||x -y||.

Notions of convergence in min-max problems The convergence rates in this paper will apply to min-max problems where g satisfies the following assumption:

Assumption 2.6. All critical points of the objective g are global min-maxes (i.e. they satisfy (1)).

In other words, we prove convergence rates to min-maxes in settings where convergence to critical points is necessary and sufficient for convergence to min-maxes. This assumption is true for convex-concave settings, but also holds for some nonconvex-nonconcave settings, as we discuss in Appendix E. This assumption allows us to measure the convergence of our algorithms to -approximate critical points, defined as follows:

Definition 2.7. Let ≥ 0. A point x ∈ R d × R d is an -approximate critical point if ||ξ(x)|| ≤ .

Convergence to approximate critical points is a necessary condition for convergence to local or global minima, and it is a natural measure of convergence since the value of g at a given point gives no information about how close we are to a min-max. Our main convergence rate results focus on this first-order notion of convergence, which is sufficient given Assumption 2.6. We discuss notions of second-order convergence and ways to adapt our results to the general nonconvex setting in Appendix A.

2.2. RELATED WORK:

Asymptotic and local convergence Several recent papers have given asymptotic or local convergence results for min-max problems. Mertikopoulos et al. (2019) show that the extragradient (EG) algorithm converges asymptotically in a broad class of problems known as coherent saddle point problems, which include quasiconvex-quasiconcave problems. However, they do not prove convergence rates. For more general smooth nonconvex min-max problems, a number of different papers have given local stability or local asymptotic convergence results for various algorithms, which we discuss in Appendix A.

Non-asymptotic convergence rates Work on global non-asymptotic last-iterate convergence rates has been limited to very restrictive settings. A classic result by Rockafellar (1976) shows a linear convergence rate for the proximal point method in the bilinear and strongly convex-strongly concave cases. Another classic result, by Tseng (1995) , shows a linear convergence rate for the extragradient algorithm in the bilinear case. Liang & Stokes (2019) show that a number of algorithms achieve a linear convergence rate in the bilinear case, including Optimistic Mirror Descent (OMD) and Consensus Optimization (CO). They also show that SGDA obtains a linear convergence rate in the strongly convex-strongly concave case. Mokhtari et al. (2019) show that OMD and EG obtain a linear rate for the strongly convex-strongly concave case, in addition to proving similar results for generalized versions of both algorithms. Finally, Du & Hu (2019) show that SGDA achieves a linear convergence rate for a convex-strongly concave setting with a full column rank linear interaction term.1 

Non-uniform average-iterate convergence A number of recent works have studied the convergence of non-uniform averages of iterates, which can be viewed as an interpolation between the standard uniform average-iterate and last-iterate. We discuss these works further in Appendix B.

3. HAMILTONIAN GRADIENT DESCENT:

Our main algorithm for finding saddle points of g(x 1 , x 2 ) is called HAMILTONIAN GRADIENT DESCENT (HGD). HGD consists of performing gradient descent on a particular objective function H that we refer to as the Hamiltonian, following the terminology of Balduzzi et al. (2018) . 2 If we let ξ := ∂g ∂x1 , -∂g ∂x2 be the vector of (appropriately-signed) partial derivatives, then the Hamiltonian is:

H(x) := 1 2 ξ(x) 2 = 1 2 ∂g ∂x1 (x) 2 + ∂g ∂x2 (x) 2 .

Since a critical point occurs when ξ(x) = 0, we can find a (approximate) critical point by finding a (approximate) minimizer of H. Moreover, under Assumption 2.6, finding a critical point is equivalent to finding a saddle point. This motivates the HGD update procedure on x (k) = (x

EQUATION

2 ) with step-size η > 0:

x

EQUATION

HGD has been mentioned in Mescheder et al. (2017) ; Balduzzi et al. (2018) , and it strongly resembles the Consensus Optimization (CO) approach of Mescheder et al. (2017) . The HGD update requires a Hessian-vector product because ∇H = ξ J, making HGD a second-order iterative scheme. However, Hessian-vector products are cheap to compute when the objective is defined by a neural net, taking only two gradient oracle calls (Pearlmutter, 1994) . This makes the Hessian-vector product oracle a theoretically appealing primitive, and it has been used widely in the nonconvex optimization literature. Since Hessian-vector product oracles are feasible to compute for GANs, many recent algorithms for local min-max nonconvex optimization have also utilized Hessian-vector products (Mescheder et al., 2017; Balduzzi et al., 2018; Adolphs et al., 2019; Letcher et al., 2019; Mazumdar et al., 2019) .

To the best of our knowledge, previous work on last-iterate convergence rates has only focused on how algorithms perform in three particular cases: (a) when the objective g is bilinear, (b) when g is strongly convex-strongly concave, and (c) when g is convex-strongly concave (Tseng, 1995; Liang & Stokes, 2019; Du & Hu, 2019; Mokhtari et al., 2019) . The existence of methods with provable finite-time guarantees for settings beyond the aforementioned has remained an open problem. This work is the first to show that an efficient algorithm, namely HGD, can achieve non-asymptotic convergence in settings that are not strongly convex or linear in either player.

3.1. CONVERGENCE RATES FOR HGD:

We now state our main theorems for this paper, which show convergence to critical points. When Assumption 2.6 holds, we get convergence to min-maxes. All of our main results will use the following multi-part assumption:

Assumption 3.1. Let g : R d × R d → R.

1. Assume a critical point for g exists.

2. Assume g is (L 1 , L 2 , L 3 )-Lipschitz and let L H = L 1 L 3 + L 2 2 .

Our first theorem shows that HGD converges for the strongly convex-strongly concave case. Although simple, this result will help us demonstrate our analysis techniques. Theorem 3.2. Let Assumption 3.1 hold and let g(x 1 , x 2 ) be α-strongly convex in x 1 and α-strongly concave in x 2 . Then HGD with step-size η = 1/L H starting from some

x (0) ∈ R d × R d will have the following convergence rate: ξ(x (k) ) ≤ 1 -α 2 L H k/2 ξ(x (0) ) .

Next, we show that HGD converges when g is linear in one of its arguments and the cross-derivative is full rank. This setting allows a slightly tighter analysis compared to Theorem 3.4. Theorem 3.3. Let Assumption 3.1 hold and let g(x 1 , x 2 ) be L-smooth in x 1 and linear in x 2 , and assume the cross derivative ∇ 2 x1,x2 g is full rank with all singular values at least γ > 0 for all x ∈ R d × R d . Then HGD with step-size η = 1/L H starting from some

x (0) ∈ R d × R d will have the following convergence rate: ξ(x (k) ) ≤ 1 - γ 4 (2γ 2 +L 2 )L H k/2 ξ(x (0) ) .

Finally, we show our main result, which requires smoothness in both players and a large, wellconditioned cross-derivative. Theorem 3.4. Let Assumption 3.1 hold and let g be L-smooth in x 1 and L-smooth

in x 2 . Let µ 2 = min x1,x2 λ min ((∇ 2 x2x2 g(x 1 , x 2 )) 2 ) and ρ 2 = min x1,x2 λ min ((∇ 2 x1x1 g(x 1 , x 2 ))

2 ), and assume the cross derivative ∇ 2 x1x2 g is full rank with all singular values lower bounded by γ > 0 and upper bounded by Γ for all x ∈ R d × R d . Moreover, let the following "sufficiently bilinear" condition hold:

EQUATION

Then HGD with step-size η = 1/L H starting from some

EQUATION

As discussed above, Theorem 3.4 provides the first last-iterate convergence rate for min-max problems that does not require strong convexity or linearity in either input. For example, the objective

g(x 1 , x 2 ) = f (x 1 ) + 3Lx 1 x 2 -h(x 2 )

, where f and h are L-smooth convex functions, satisfies the assumptions of Theorem 3.4 and is not strongly convex or linear in either input. We discuss a simple example that is not convex-concave in Appendix E. We also show how our results can be applied to specific settings, such as the Dirac-GAN, in Appendix G.

The "sufficiently bilinear" condition (3) is in some sense necessary for our linear convergence rate since linear convergence is impossible in general for convex-concave settings, due to lower bounds on convex optimization (Agarwal & Hazan, 2018; Arjevani et al., 2017) . We give some explanations for this condition in the following section. In simple experiments for HGD on convex-concave and nonconvex-nonconcave objectives, the convergence rate speeds up when there is a larger bilinear component, as expected from our theoretical results. We show these experiments in Appendix K.

3.2. EXPLANATION OF "SUFFICIENTLY BILINEAR" CONDITION:

In this section, we explain the "sufficiently bilinear" condition (3). Suppose our objective is g(x 1 , x 2 ) = ĝ(x 1 , x 2 ) + cx 1 x 2 for a smooth function ĝ. Then for sufficiently large values of c (i.e. g has a large enough bilinear term), we see that g satisfies (3). To see this, note that if we have γ 4 > 4L 2 Γ 2 , then condition (3) holds. Let γ and Γ be lower and upper bounds on the singular values of ∇ 2 x1x2 ĝ. Then it suffices to have

(γ + c) 4 > 4L 2 (Γ + c) 2 , which is true for c = 3 max{L, Γ } (i.e. c = O(L) suffices).

This condition is analogous to the case when we use SGDA on the objective g(

x 1 , x 2 ) = ĝ(x 1 , x 2 ) + c ||x 1 || 2 -c ||x 2 || 2 for L-smooth convex-concave ĝ. According to Liang & Stokes (2019), SGDA

will converge at a rate of roughly L2 c 2 log(1/ ) for L-smooth and c-strongly convex-strongly concave objectives. 3 For c = 0, SGDA will diverge in the worst case. For c = o(L), we get linear convergence, but it will be slow because L+c c is large (this can be thought of as a large condition number). Finally, for c = Ω(L), we get fast linear convergence, since L+c c = O(1). Thus, to get fast linear convergence it suffices to make the problem "sufficiently strongly convex-strongly concave" (or "sufficiently strongly monotone").

Theorem 3.4 and condition (3) show that there exists another class of settings where we can achieve linear rates in the min-max setting. In our case, if we have an objective g(x 1 , x 2 ) = ĝ(x 1 , x 2 )+cx 1 x 2 for a smooth function ĝ, we will get linear convergence if ∇ 2 x1x2 ĝ ≤ δL and c ≥ 3(1 + δ)L, which ensures that the problem is "sufficiently bilinear." Intuitively, it makes sense that the "sufficiently bilinear" setting allows a linear rate because the pure bilinear setting allows a linear rate.

Another way to understand condition (3) is that it is a sufficient condition for the existence of a unique critical point in a general class of settings, as we show in the following lemma, which we prove in Appendix F.

Lemma 3.5. Let g(x 1 , x 2 ) = f (x 1 ) + cx 1 x 2 -h(x 2 )

where f and h are L-smooth. Moreover, assume that ∇ 2 f (x 1 ) and ∇ 2 h(x 2 ) each have a 0 eigenvalue for some x 1 and x 2 . If (3) holds, then g has a unique critical point.

4. PROOF SKETCHES FOR HGD CONVERGENCE RATE RESULTS:

In this section, we go over the key components of the proofs for our convergence rates from Section 3.1. Recall that the intuition behind HGD was that critical points (where ξ(x) = 0) are global minima of H = 1 2 ||ξ|| 2 . On the other hand, there is no guarantee that H is a convex potential function, and a priori, one would not assume gradient descent on this potential would find a critical point. Nonetheless, we are able to show that in a variety of settings, H satisfies the PL condition, which allows HGD to have linear convergence. Proving this requires proving properties about the singular values of J ≡ ∇ξ.

4.1. THE POLYAK-ŁOJASIEWICZ CONDITION FOR THE HAMILTONIAN:

We begin by recalling the definition of the PL condition. Definition 4.1 (Polyak-Łojasiewicz (PL) condition Polyak (1963) ; Lojasiewicz (1963) 

). A function f : R d → R satisfies the PL condition with parameter α > 0 if for all x ∈ R d , 1 2 ||∇f (x)|| 2 ≥ α(f (x) -min x * ∈R d f (x * )).

The PL condition is well-known to be the weakest condition necessary to obtain linear convergence rate for gradient methods; see for example Karimi et al. (2016) . We will show that H satisfies the PL condition, which allows us to use the following classic theorem. Theorem 4.2 (Linear rate under PL Polyak (1963) ; Lojasiewicz (1963) ). Let f : R d → R be L-smooth and let x * ∈ arg min x∈R d f (x). Suppose f satisfies the PL condition with parameter α. Then if we run gradient descent from x (0) ∈ R d with step-size 1 L , we have:

f (x (k) ) -f (x * ) ≤ (1 -α L ) k (f (x (0) ) -f (x * )).

For completeness, we provide the proof of Theorem 4.2 in Appendix C.

All of our results use Assumption 3.1, so we are guaranteed that g has a critical point. This implies that the global minimum of H is 0, which allows us to prove the following key lemma: Lemma 4.3. Assume we have a twice differentiable g(x 1 , x 2 ) with associated ξ, H, J. Let c > 0. If JJ αI for every x, then H satisfies the PL condition with parameter α.

Proof. Consider the squared norm of the gradient of the Hamiltonian:

1 2 ∇H 2 = 1 2 J ξ 2 = 1 2 ξ, (JJ )ξ ≥ α 2 ||ξ|| 2 = αH.

The proof is finished by noting that H(x) = 0 when x is a critical point.

To use Theorem 4.2, we will also need to show that H is smooth, which holds when g is

(L 1 , L 2 , L 3 )- Lipschitz. The proof of Lemma 4.4 is in Appendix H. Lemma 4.4. Consider any g(x 1 , x 2 ) which is (L 1 , L 2 , L 3 )-Lipschitz for constants L 1 , L 2 , L 3 > 0. Then the Hamiltonian H(x) is (L 1 L 3 + L 2 2 )-smooth.

To use Lemma 4.3, we will need control over the eigenvalues of JJ , which we achieve with the following linear algebraic lemmas. We provide their proofs in Appendix H. We now proceed to sketch the proofs of our main theorems using the techniques we have described.

The following lemma shows it suffices to prove the PL condition for H for the various settings of our theorems: Lemma 4.7. Given g : R d × R d → R, suppose H satisfies the PL condition with parameter α and is L H -smooth. Then if we use HGD starting from some x (0) ∈ R d × R d with step-size η = 1/L H , then we have the following:

ξ(x (k) ) ≤ 1 -α L H k/2 ξ(x (0) ) .

Proof. Since H satisfies the PL condition with parameter α and H is L H -smooth, we know by Theorem 4.2 that gradient descent on H with step-size 1/L H converges at a rate of ) ). Substituting in for H gives the lemma.

EQUATION

It remains to show that H satisfies the PL condition in the settings of Theorems 3.2 to 3.4. First, we show the result for the strongly convex-strongly concave setting of Theorem 3.2. Lemma 4.8 (PL for the strongly convex-strongly concave setting). Let g be c-strongly convex in x 1 and c-strongly concave in x 2 . Then H satisfies the PL condition with parameter α = c 2 .

Proof. We apply Lemma 4.5 with H = J. Since g is c-strongly-convex in x 1 and c-strongly concave in x 2 we have M 1 = ∇ 2 x1x1 g cI and M 2 = -∇ 2 x2x2 g cI. Then the magnitude of the eigenvalues of J is at least c. Thus, JJ c 2 I, so by Lemma 4.3, H satisfies the PL condition with parameter c 2 .

Next, we show that H satisfies the PL condition for the nonconvex-linear setting of Theorem 3.3. We prove this lemma in Appendix H.4 by using Lemma 4.6. Lemma 4.9 (PL for the smooth nonconvex-linear setting). Let g be L-smooth in x 1 and linear in x 2 . Moreover, for all x ∈ R d × R d , let ∇ 2 x1x2 g(x 1 , x 2 ) be full rank and square with σ min (∇ 2 x1x2 g(x 1 , x 2 )) ≥ γ. Then H satisfies the PL condition with parameter α = γ 4 2γ 2 +L 2 .

Finally, we prove that H satisfies the PL condition in the nonconvex-nonconvex setting of Theorem 3.4. The proof for Lemma 4.10 is in Appendix H.5, and it uses Lemma H.2, which is similar to Lemma 4.6.

Lemma 4.10 (PL for the smooth nonconvex-nonconvex setting). Let g be L-smooth in x 1 and L-smooth in x 2 . Also, let ∇ 2 x1x2 g be full rank and let all of its singular values be lower bounded by γ and upper bounded by

Γ for all x ∈ R d × R d . Let ρ 2 = min x1,x2 λ min ((∇ 2 x1x1 g(x 1 , x 2 )) 2 ) and µ 2 = min x1,x2 λ min ((∇ 2 x2x2 g(x 1 , x 2 )) 2

). Assume the following condition holds:

(γ 2 + ρ 2 )(γ 2 + µ 2 ) -4L 2 Γ 2 > 0.

Then H satisfies the PL condition with parameter α

= (γ 2 +ρ 2 )(γ 2 +µ 2 )-4L 2 Γ 2 2γ 2 +ρ 2 +µ 2 .

Combining Lemmas 4.8 to 4.10 with Lemma 4.7 yields Theorems 3.2 to 3.4.

5. EXTENSIONS OF HGD RESULTS:

Stochastic HGD Our results above also imply rates for stochastic HGD, where the gradient ∇H in (2), is replaced by a stochastic estimator v of ∇H such that E[v] = ∇H. Since we show that H satisfies the PL condition with parameter α in different settings, we can use Theorem 4 in Karimi et al. (2016) to show that stochastic HGD converges at a O(1/ √ k) rate in the settings of Theorems 3.2 to 3.4, including the "sufficiently bilinear" setting. We prove Theorem 5.1 in Appendix I.

Theorem 5.1. Let Assumption 3.1 hold and suppose H satisfies the PL condition with parameter α. Suppose we use the update k) . Then if we use η k = 2k+1 2α(k+1) 2 , we have the following convergence rate:

x (k+1) = x (k) -η k v(x (k) ), where v is a stochastic estimate of ∇H such that E[v] = ∇H and E[ v(x (k) ) 2 ] ≤ C 2 for all x (

E[ ξ(x (k) ) ] ≤ L H C 2 kα 2 .

Consensus Optimization The Consensus Optimization (CO) algorithm of Mescheder et al. (2017) is as follows:

EQUATION

where γ > 0. This is essentially a weighted combination of SGDA and HGD. Mescheder et al. (2017) remark that while HGD has poor performance on nonconvex problems in practice, CO can effectively train GANs in a variety of settings, including on CIFAR-10 and celebA. While they frame CO as SGDA with a small modification, they actually set γ = 10 for several of their experiments, which suggests that one can also view CO as a modified form of HGD.

Using this perspective, we prove Theorem 5.2, which implies that we get linear convergence of CO in the same settings as Theorems 3.2 to 3.4 provided that γ is sufficiently large (i.e. the HGD update is large compared to the SGDA update). The key technical component is showing that HGD still performs well even with a certain kind of small arbitrary perturbation. Previously, Liang & Stokes (2019) proved that CO achieves linear convergence in the bilinear setting, so our result greatly expands the settings where CO has provable non-asymptotic convergence. We prove Theorem 5.2 in Appendix J.

Theorem 5.2. Let Assumption 3.1 hold. Let g be L g smooth and suppose H satisfies the PL condition with parameter α. Then if we update some x (0) ∈ R d × R d using the CO update (5) with step-size η = α 4L H Lg and γ = 4Lg α , we get the following convergence:

EQUATION

We also show that CO converges in practice on some simple examples in Appendix K.

A GENERAL NONCONVEX MIN-MAX OPTIMIZATION:

In standard nonconvex optimization, a common goal is to find second-order local minima, which are approximate critical points where ∇ 2 f is approximately positive definite. Likewise, a common goal in nonconvex min-max optimization is to find approximate critical points where an analogous secondorder condition holds, namely that ∇ 2 x1x1 g(x) is approximately positive definite and ∇ 2 x2x2 g(x) is approximately negative definite. Critical points where this second-order condition holds are called local min-maxes. When Assumption 2.6 holds, all critical points are global min-maxes, but in more general settings, we may encounter critical points that do not satisfy these conditions. Critical points may be local min-mins or max-mins or indefinite points. A number of recent papers have proposed dynamics for nonconvex min-max optimization, showing local stability or local asymptotic convergence results (Mescheder et al., 2017; Daskalakis & Panageas, 2018; Balduzzi et al., 2018; Letcher et al., 2019; Mazumdar et al., 2019) . The key guarantee that these papers generally give is that their algorithms will be stable at local min-maxes and unstable at some set of undesirable critical points (such as local max-mins). This essentially amounts to a guarantee that in the convex-concave setting, their algorithms will converge asymptotically and in the strictly concave-strictly convex setting (i.e. where there is only an undesirable max-min), their algorithms will diverge asymptotically. This type of local stability is essentially the best one can ask for in the general nonconvex setting, and we show how to give similar guarantees for our algorithm in Section A.1.

A.1 NONCONVEX EXTENSIONS FOR HGD:

While the naive version of HGD will try to converge to all critical points, we can modify HGD slightly to achieve second-order stability guarantees as in various related work such as Balduzzi et al. (2018) ; Letcher et al. (2019) . In particular, we consider modifying HGD so that there is some scalar α in front of the ∇H term as follows:

EQUATION

We now present two ways to choose α. Our first method is inspired by the Simplectic Gradient Adjustment algorithm of Balduzzi et al. (2018) , which is as follows:

EQUATION

)

where A is the antisymmetric part of J and λ = sgn ξ, J A ξ, J . Balduzzi et al. (2018) show that λ is positive when in a strictly convex-strictly concave region and negative in a strictly concave-strictly convex region. Thus, if we choose α = λ = sgn ξ, J A ξ, J , we can ensure that the modified HGD will exhibit local stability around strict min-maxes and local instability around strict max-mins. This follows simply because we will do gradient descent on H in the first case and gradient ascent on H in the second case.

Another way to choose α involves using an approximate eigenvalue computation on ∇ 2 x1x1 g and ∇ 2

x2x2 g to detect whether ∇ 2 x1x1 g is positive semidefinite and ∇ 2 x2x2 g is negative semidefinite (which would mean we are in a convex-concave region). We set α = 1 if we are in a convex-concave region and -1 otherwise, which will guarantee local stability around min-maxes and local instability around other critical points. This approximate eigenvector computation can be done using a logarithmic number of Hessian-vector products.

B BACKGROUND ON NON-UNIFORM AVERAGE ITERATES:

A number of recent works have focused on the performance of a non-uniform average of an algorithm's iterates. Iterate averaging can lend stability to an algorithm or improve performance if the algorithm cycles around the solution. On the other hand, uniform averages can suffer from worse performance in nonconvex settings if early iterates are far from optimal. Non-uniform averaging is a way to achieve the stability benefits of iterate averaging while potentially speeding up convergence compared to uniform averaging. In this way, one can view non-uniform averaging as an interpolation between average-iterate and last-iterate algorithms.

One popular non-uniform averaging scheme is the exponential moving average (EMA). For an algorithm with iterates z (0) , ..., z (T ) , the EMA at iterate t is defined recursively as

z (t) EM A = βz (t-1) EM A + (1 -β)z (t-1) EM A

where z (0) EM A = z (0) and β < 1. A typical value for β is 0.999. Yazıcı et al. (2019) and Gidel et al. (2019) show that uniform and EMA schemes can improve GAN performance on a variety of datasets. Mescheder et al. (2018) and Karras et al. (2018) use EMA to evaluate the GAN models they train, showing the effectiveness of EMA in practice.

In terms of theoretical results, Kroer (2019) studies saddle point problems of the form min x1 max x2 f (x 1 ) + g(x 1 ) + Kx 1 , x 2 -h * (x 2 ), where f is a smooth convex function, g and h are convex functions with easily computable prox-mappings, and K is some linear operator. They show that for certain algorithms, linear averaging and quadratic averaging schemes are provably at least as good as the uniform average scheme in terms of iterate complexity. Abernethy et al. (2018) show how linear and exponential averaging schemes can be used to achieve faster convergence rates in some specific convex-concave games.

Overall, while non-uniform averaging is appealing for a variety of reasons, there is currently no theoretical explanation for why it outperforms uniform averages or why it would converge at all in many settings. In fact, one natural way to show convergence for an EMA scheme would be to show last-iterate convergence.

C PROOF OF LINEAR CONVERGENCE RATE UNDER PL CONDITION:

Here we present a classic proof of Theorem 4.2.

Proof of Theorem 4.2.

EQUATION

where the first line comes from smoothness and the update rule for gradient descent, the second inequality comes from the PL condition. Applying the last line recursively gives the result.

D COMPARISON OF THEOREM 3.4 TO DU & HU (2019) In this section, we compare our results in Theorem 3.4 to those of Du & Hu (2019) . Du & Hu (2019) prove a rate for SGDA when g is L-smooth and convex in x 1 and L-smooth and µ-strongly concave in x 2 and ∇ 2 x1x2 g is some fixed matrix A. The specific setting they consider is to find the unconstrained min-max for a function g :

R d1 × R d2 → R defined as g(x 1 , x 2 ) = f (x 1 ) + x 2 Ax 1 -h(x 2 )

where f is convex and smooth, h is strongly-convex and smooth, and A ∈ R d2×d1 has rank d 1 (i.e. A has full column rank).

Their rate uses the potential function P t = λa t + b t , where we have:

λ = 2LΓ(L + Γ 2 µ ) µγ 2

(12)

a k = x (k) 1 -x * 1 (13) b k = x (k) 2 -x * 2 (14)

where (x * 1 , x * 2 ) is the min-max for the objective. Their rate (Theorem 3.1 in Du & Hu ( 2019)) is

P k+1 ≤ 1 -c µ 2 γ 4 L 3 Γ 2 (L + Γ 2 µ ) k P k (15)

for some constant c > 0. To translate this rate into bounds on ||ξ||, we can use the smoothness of g in both of its arguments to note that ∂g

∂x1 (x 1 , x 2 ) = ∂g ∂x1 (x 1 , x 2 ) -∂g ∂x1 (x * 1 , x * 2 ) ≤ L x (k) 1 -x * 1

and likewise for x 2 . So the rate on P k translates into a rate on ||ξ|| with some additional factor in front.

Their rate and our rate are incomparable -neither is strictly better. For instance when γ = Γ is much larger than all other quantities, their rates simplify to 1 -O µ 3 L 3 k , while ours go to

1 -O γ 2 L H k/2

. While our convergence rate requires the sufficiently bilinear condition (3) to hold, we do not require convexity in x 1 or concavity in x 2 . Moreover, we allow ∇ 2 x1x2 g to change as long as the bounds on the singular values hold whereas Du & Hu (2019) require ∇ 2 x1x2 g to be a fixed matrix.

E NONCONVEX-NONCONCAVE SETTING WHERE ASSUMPTION 2.6 AND THE CONDITIONS FOR THEOREM 3.4 HOLD:

In this section we give a concrete example of a nonconvex-nonconcave setting where Assumption 2.6 and the conditions for Theorem 3.4 hold. We choose this example for simplicity, but one can easily come up with other more complicated examples.

For our example, we define the following function:

EQUATION

The first and second derivatives of F are as follows:

EQUATION

From Figure 2 , we can see that this function is neither convex nor concave.

Our objective will be g

(x 1 , g 2 ) = F (x 1 ) + 4x 1 x 2 -F (x 2 ). Note that L = 3 because F (x) ≤ 3 for all x. Also, γ = Γ = 4 since ∇ 2 x1x2 g = 4I.

First, we show that g satisfies Assumption 3.1. We see that g has a critical point at (0, 0). Moreover, g is (L 1 , L 2 , L 3 )-Lipschitz for any finite-sized region of R 2 . Thus, if we assume our algorithm stays within a ball of some radius R, the (L 1 , L 2 , L 3 )-Lipschitz assumption will be satisfied. Since our algorithm does not diverge and indeed converges at a linear rate to the min-max, this assumption is fairly mild.

Next, we show that g satisfies condition (3). Condition (3) requires γ 4 > 4L 2 Γ 2 for g. We see that this holds because γ 4 = 4 4 = 256 and 4LΓ 2 = 4 * 3 * 4 2 = 192.

Therefore, the assumptions of Theorem 3.4 are satisfied.

We can also show that this objective satisfies Assumption 2.6, so we get convergence to the min-max of g. We will show that g has only one critical point (at (0, 0)) and that this critical point is a min-max. We first give a "proof by picture" below, showing a plot of g in Figure 3 , along with plots of g(•, 0) and g(0, •) showing that (0, 0) is indeed a min-max.

We can also formally show that (0, 0) is the unique critical point of g and that it is a min-max. We prove this for completeness, although the calculations more or less amount to a simple case analysis. 

3: Plot of nonconvex-nonconcave g(x 1 , x 2 ) = F (x 1 ) + 4x 1 x 2 -F (x 2 )

These equations imply the following:

EQUATION

That is, for all critical points of g, x 1 must be a fixed point of h 1 (x) = 3 4 sin -3 4 sin x and x 2 must be a fixed point of h 2 (x) = -3 4 sin 3 4 sin x . Since |h 1 (x)| < 1 and |h 2 (x)| < 1 always, h 1 and h 2 are contractive maps, so they have only one fixed point each. Thus, g will only have one critical point, namely the point (x 1 , x 2 ) such that x 1 is the unique fixed point of h 1 and x 2 is the unique fixed point of h 2 .

Finally, we can observe that (0, 0) is a critical point of g, so it must be the unique critical point of g. One can also see that this is a min-max by looking at the second derivatives of F in (18).

F PROOF OF LEMMA 3.5:

To prove Lemma 3.5, we will use the following lemma: Figure 4 : Plot of g(•, 0). We can see that there is only one min and it occurs at x 1 = 0.

Figure 5 : Plot of g(0, x 2 ). We can see that there is only one max and it occurs at x 2 = 0.

Lemma F.1. Let g(x 1 , x 2 ) = f (x 1 ) + cx 1 x 2 -h(x 2 )

where f and h are L-smooth. Then if c > L, g has a unique critical point.

Proof of Lemma 3.5. Condition (3) is as follows:

(γ 2 + ρ 2 )(µ 2 + γ 2 ) -4L 2 Γ 2 > 0.

(27) Note that in our setting, γ = Γ = c. Next, observe that if ∇ 2 f (x 1 ) and ∇ 2 h(x 2 ) each have a 0 eigenvalue for some x 1 and x 2 , condition (3) reduces to: c > 2L.

(28) Then by Lemma F.1, we see that g must have a unique critical point.

Next, we prove Lemma F.1.

Proof of Lemma F.1. Suppose our objective is g(x 1 , x 2 ) = f (x 1 ) + cx 1 x 2 -h(x 2 ) where f and h are both L-smooth convex functions. Critical points of g must satisfy the following:

∇f

EQUATION

In other words, x 2 must be a fixed point of

F (z) = -1 c ∇f ( 1 c ∇h(z)).

The function F will have a unique fixed point if it is a contractive map. We now show that for c > L, this is the case.

EQUATION

EQUATION

EQUATION

where the inequalities follow from smoothness of f and h. An analogous property can be shown by solving for x 1 instead. Thus, if c > L, then g will have a unique fixed point.

Condition (3) is thus a sufficient condition for the existence of a unique critical point for the class of objectives above.

G APPLICATIONS:

In this section, we discuss how our results can be applied to various settings. One simple setting is the Dirac-GAN from Mescheder et al. (2018) , where g(

x 1 , x 2 ) = min x1 max x2 f (x 1 x 2 ) -f (0)

for some function f whose derivative is always non-zero. When f (t) = t, the Dirac-GAN is just a bilinear game, so HGD will converge globally to the Nash Equilibrium (NE) of this Dirac-GAN, as shown in Balduzzi et al. (2018) . Our results prove global convergence rates for HGD on the Dirac-GAN even when a small smooth convex regularizer is added for the discriminator or subtracted for the generator. Moreover, Lemma 2.2 of Mescheder et al. (2018) shows that the diagonal blocks of the Jacobian are 0 at the NE for arbitrary f with non-zero derivative. As such, HGD will achieve the convergence rates in this paper in a region around the NE for the Dirac-GAN for arbitrary f with non-zero derivative even when a small smooth convex regularizer is added for either player.

Du & Hu (2019) list several applications where the min-max formulation is relevant, such as in ERM problems with a linear classifier. Given a data matrix A, the ERM problem involves solving min x (Ax) + f (x) for some smooth, convex loss and smooth, convex regularizer f . This problem has the saddle point formulation min x max y y Ax - * (y) + f (x). According to Du & Hu (2019) , this formulation can be advantageous when it allows a finite-sum structure, reduces communication complexity in a distributed setting, or allows some sparsity structure to be exploited. Our results show that linear rates are possible for this problem if A is square, well-conditioned, and sufficiently large compared to and f . λ σ 2 min -λ

EQUATION

We will show that if λ < δ, where δ = σ 2 min (C)

+ ||A|| 2 2 -(σ 2 min + ||A|| 2

2 ) 2 -σ 4 min , then λ min (T ) > 0, which is a contradiction. It suffices to show the following inequality:

EQUATION

(57) has zeros at the following values:

EQUATION

Since ( 57) is a convex parabola, if λ is less than both zeros, we will have proved (57). This is clearly true if λ < δ.

As a last step, we can give a slightly nicer form of δ, using Lemma H. Lemma H.1. For x ∈ (0, 1) and c ∈ (0, x 2 ), we have:

EQUATION

Proof.

x -

x 2 -c = x -x 1 - c x 2 > x -x 1 - c 2x 2 = c 2x H.4 PROOF OF LEMMA 4.9 Proof. Let C(x 1 , x 2 ) = ∇ 2 x1x2 g(x 1 , x 2 ). For all x ∈ R d × R d , C(x 1 , x 2

) is square and full rank by assumption, so we can apply Lemma 4.6 with 

H = J at each point x ∈ R d × R d , which gives λ(JJ ) ≥ σ 4 min (C(x1,x2)) 2σ 2 min (C(x1,x2))+||∇ 2 x 1 x 1 g(x1,x2)|| 2 . We have ∇ 2 x1x1 g(x 1 , x 2 ) ≤ L since g is smooth in x 1 . Also, σ 2 min (C(x 1 , x 2 )) ≥ γ.

(C) + λ min (A 2 ))(λ min (B 2 ) + σ 2 min (C)) -σ 2 max (C)(||A|| + ||B||) 2 and assume c > 0. Then if λ is an eigenvalue of HH = A 2 + CC -AC -CB -C A -BC B 2 + C C , we must have λ ≥ (σ 2 min (C) + λ min (A 2 ))(λ min (B 2 ) + σ 2 min (C)) -σ 2 max (C)(||A|| + ||B||) 2 (2σ 2 min (C) + λ min (A 2 ) + λ min (B 2 )) 2

.

Proof of Lemma H.2. This proof resembles that of Lemma 4.6. Let v = v 1 v 2 be an eigenvector of HH with eigenvalue λ. Expanding HH v = λv, we have:

EQUATION

)

where M is invertible because C C is positive definite and WLOG, we may assume that λ < λ min (C C) = σ 2 min (C). We will show that if the assumptions in the statement of the lemma hold, then we get a contradiction if λ is below some positive threshold. In particular, we show that the following inequality holds for small enough λ (this inequality contradicts (62)):

σ 2 min (C) -λ + λ min (A 2 ) > σ 2 max (C)(||A|| + ||B||) 2 M -1 ⇐ σ 2 min (C) -λ + λ min (A 2 ) > σ 2 max (C) λ min (B 2 ) + σ 2 min (C) -λ (||A|| + ||B||) 2 ⇐⇒ λ 2 -(2σ 2 min (C) + λ min (A 2 ) + λ min (B 2 ))λ+ (σ 2 min (C) + λ min (A 2 ))(λ min (B 2 ) + σ 2 min (C))-σ 2 max (C)(||A|| + ||B||) 2 > 0 Letting b = 2σ 2 min (C) + λ min (A 2 ) + λ min (B 2

), we can solve for the zeros of the above equation:

EQUATION

Note that we have c > 0 by assumption, so this equation has only positive roots. Note also that b 2 > 4c, so the roots will not be imaginary. Then we see that if

EQUATION

, we get a contradiction. Using Lemma H.1, we see that δ > c b . So we've proven that λ < c b gives a contradiction, so we must have λ ≥ c b , i.e.

λ ≥ (σ 2 min (C) + λ min (A 2 ))(λ min (B 2 ) + σ 2 min (C)) -σ 2 max (C)(||A|| + ||B||) 2 2σ 2 min (C) + λ min (A 2 ) + λ min (B 2 )

.

Proof of Lemma 4.10. The proof is very similar to that of Lemma 4.9.

Let C(x 1 , x 2 ) = ∇ 2 x1x2 g(x 1 , x 2 ). For all x ∈ R d × R d , C(x 1 , x 2

) is square and full rank with bounds on its singular values by assumption. Moreover, (3) holds, so we can apply Lemma H.2 with H = J at each point x ∈ R d × R d . Using the fact that g is smooth in x 1 and x 2 , this gives

λ(JJ ) ≥ (σ 2 min (C(x 1 , x 2 )) + λ min (A 2 ))(σ 2 min (C(x 1 , x 2 )) + µ 2 ) -4L 2 σ 2 max (C(x 1 , x 2 )) 2σ 2 min (C(x 1 , x 2 )) + λ min (A 2 ) + µ 2 .

Using the bounds on the singular values of C(x 1 , x 2 ), we have that JJ

(γ 2 +λmin(A 2 ))(γ 2 +µ 2 )-4L 2 Γ 2 2γ 2 +λmin(A 2 )+µ 2

I, so by Lemma 4.3, H satisfies the PL condition with parameter

(γ 2 +λmin(A 2 ))(γ 2 +µ 2 )-4L 2 Γ 2 2γ 2 +λmin(A 2 )+µ 2 .

I PROOF OF THEOREM 5.1

In this section, we prove Theorem 5.1. The proof leverages the following theorem from Karimi et al. (2016) . 4Theorem I.1 (Karimi et al. (2016) ). Assume that f is L-smooth, has a non-empty solution set X * , and satisfies the PL condition with parameter α. Let v be a stochastic estimate of ∇f such that k) and some C. If we use the SGD update k) ) with η k = 2k+1 2α(k+1) 2 , then, we get a convergence rate of

E[v] = ∇f . Assume E[ v(x (k) ) 2 ] ≤ C 2 for all x (

EQUATION

EQUATION

If instead we use a constant η k = η < 1 2α , then we obtain a linear convergence rate up to a solution level that is proportional to η,

EQUATION

Now we can prove Theorem 5.1.

Proof of Theorem 5.1. If H satisfies the PL condition with parameter α, then we can apply Theorem I.1 to the stochastic variant of HGD. since H * = 0, we get

EQUATION

The theorem follows from Jensen's inequality, which implies that E ξ(x (k) ) ≤ E ξ(x (k) ) 2 .

J PROOF OF THEOREM 5.2

In this section, we prove our main result about Consensus Optimization, namely Theorem 5.2.

The key technical component is showing that HGD still performs well even with small arbitrary perturbations, as we show in the following theorem: k) where v (k) is some arbitrary vector such that v (k) = ξ(x (k) ) . Let g be L g -smooth and suppose H satisfies the PL condition with parameter α. Let η = 1 L H and let η v = α 4L H Lg . Then we get the following convergence:

Theorem J.1. Let x (k+1) = x (k) -η∇H(x (k) ) + η v v (

EQUATION

From Theorem J.1, it is simple to prove Theorem 5.2

Proof of Theorem 5.2. Note that the CO update (5) with γ = 4Lg α is exactly the update in Theorem J.1 with v (k) = -ξ(x (k) ), so we get the desired convergence rate.

Our result treats SGDA as an adversarial perturbation even though this is not the case, which suggests that this analysis may be improved. It would be nice if one could directly apply the PL-based analysis that we used for HGD, but this does not seem to work for CO since CO is not gradient descent on some objective. Now we prove Theorem J.1.

Proof of Theorem:

EQUATION

Next, note that the triangle inequality and smoothness of g imply:

EQUATION

≤ ξ(x (k+1/2) ) + L g x (k+1) -x (k+1/2) (70)

EQUATION

Using the above result and v (k) = ξ(x (k) ) , we get:

EQUATION

Setting η v = α 4L H Lg gives the result.

Note that for this result, we assume g is L g smooth in x 1 and x 2 jointly, whereas in other parts of the paper we assume g is smooth in x 1 or x 2 separately. If g is L-smooth in x 1 and L-smooth in x 2 and ∇ 2 x1x2 g(x 1 , x 2 ) ≤ L c for all x 1 , x 2 , then g will be L + L c smooth.

K EXPERIMENTS:

In this section, we present some experimental results showing how SGDA, HGD, and CO perform on a convex-concave objective and a nonconvex-nonconcave objective. For our CO plots, γ refers to the γ parameter in the CO algorithm. All of our experiments are initialized at (5, 5). The stepsize η for HGD and SGDA is always 0.01, while the step-size η for CO with γ = {0.1, 1, 10} is {0.1, 0.01, 0.001} respectively to account for the fact that increasing γ increases the effective step-size, so the η parameter needs to be decreased accordingly. The experiments were all run on a standard 2017 Macbook Pro.

The main takeaways from the experiments are that CO with low γ will not converge if there is a large bilinear term, while CO with high γ and HGD all converge for small and large bilinear terms. When the bilinear term is large, CO with high γ and HGD both will converge in fewer iterations (for the same step-size). We did not optimize for step-size, so it is possible this effect may change if the optimal step-size is chosen for each setting.

K.1 CONVEX-CONCAVE OBJECTIVE:

The convex-concave objective we use is g(x 1 , x 2 ) = f (x 1 ) + cx 1 x 2 -f (x 2 ) where f (x) = log(1 + e x ). We show a plot of f in Figure 6 . These plots show g when c = 10, so SGDA diverges, as does CO with γ = 0.1. Note that in this case, CO with γ ≥ 1 and HGD both require very few iterations (typically about 2) to reach the min-max. In this section, we look at the convergence of HGD for the same objective as discussed in the previous section, namely g(x 1 , x 2 ) = F (x 1 ) + cx 1 x 2 -F (x 2 ) where F is defined as in ( 16) in Appendix E. In this case, we will vary c to show that HGD converges faster for higher c and will not converge for sufficiently low c. 

:

Specifically, they assume g(x1, x2) = f (x1) + x T

, where f is smooth and convex, h is smooth and strongly convex, and A has full column rank. We make a brief comparison of our work to that ofDu & Hu (2019) for the convex-strongly concave setting in Appendix D.2 We note that the function H is not the Hamiltonian as in the sense of classical physics, as we do not use the symplectic structure in our analysis, but rather we only perform gradient descent on H.

c log(1/ ), for some parameter β that is at least (L + c) 2 .

The actual theorem inKarimi et al. (2016) is stated in a slightly different way, but it is equivalent to our presentation.

Figures and Tables:

and let ≥ 0. If M 1 I and M 2 ≺ -I, then for all eigenvalues λ of HH , we have λ > 2 .Lemma 4.6.Let H = A C-C 0 , where C is square and full rank. Then if λ is an eigenvalue of HH , then we must have λ ≥ SKETCHES FOR THEOREMS 3.2, 3.3, AND 3.4

Figure 3: Plot of nonconvex-nonconcave g(x 1 , x 2 ) = F (x 1 ) + 4x 1 x 2 -F (x 2 )

1. Letting x = σ 2 min (C) + ||A|| 2 2 and c = σ 4 min (C), we have δ > σ 4 min (C) 2σ 2 min (C)+||A|| 2 . So to reiterate, if λ < σ 4 min (C) 2σ 2 min (C)+||A|| 2 < δ, then(57) holds, so T 0, which contradicts (52).

Figure 6: Plot of f (x) = log(1 + e x ) with its first and second derivatives. This is a convex, smooth function When c = 3, SGDA converges, and when c = 10, SGDA diverges. We note that HGD and CO (for large enough γ) tend to converge faster when c is larger. K.1.1 SGDA CONVERGES (c = 3)These plots show g when c = 3, so SGDA converges, as does CO with γ = 0.1.

Figure7: SGDA vs. HGD for 300 iterations for g(x 1 , x 2 ) = f (x 1 ) + cx 1 x 2 -f (x 2 ) where f (x) = log(1 + e x ) and c = 3. SGDA slowly circles towards the min-max, and HGD goes directly to the min-max.

Figure 8: CO for 100 iterations with different values of γ for g(x 1 , x 2 ) = f (x 1 ) + cx 1 x 2 -f (x 2 )where f (x) = log(1 + e x ) and c = 3. The γ = 0.1 curve slowly circles towards the min-max, while the other curves go directly to the min-max.

Figure 9: HGD vs. CO for 100 iterations for g(x 1 , x 2 ) = f (x 1 ) + cx 1 x 2 -f (x 2 ) where f (x) = log(1 + e x ) and c = 3 with different values of γ.

Figure10: SGDA vs. HGD for 150 iterations for g(x 1 , x 2 ) = f (x 1 ) + cx 1 x 2 -f (x 2 ) where f (x) = log(1 + e x ) and c = 10. SGDA slowly circles away from the min-max, while HGD goes directly to the min-max.

Figure14: SGDA vs. HGD for 300 iterations for g(x 1 , x 2 ) = F (x 1 ) + cx 1 x 2 -F (x 2 ) where F (x) is defined in (73) and c = 3. SGDA slowly circles towards the min-max, and HGD goes more directly to the min-max.

Figure 15: CO for 100 iterations with different values of γ for g(x 1 , x 2 ) = F (x 1 ) + cx 1 x 2 -F (x 2 )where F (x) is defined in (73) and c = 3. The γ = 0.1 curve slowly circles towards the min-max, while the other curves go more directly to the min-max.

Figure 16: HGD vs. CO for 100 iterations for g(x 1 , x 2 ) = F (x 1 ) + cx 1 x 2 -F (x 2 ) where F (x) is defined in (73) and c = 3 with different values of γ.

Figure 18: CO for 15 iterations with different values of γ for g(x 1 , x 2 ) = F (x 1 ) + cx 1 x 2 -F (x 2 )where F (x) is defined in (73) and c = 10. The γ = 0.1 curve makes an erratic cycle around the min-max, slowly diverging, while the other curves go directly to the min-max.



Figure 20: Distance to minmax for HGD iterates for different values of c in the objective g(x 1 , x 2 ) = F (x 1 ) + cx 1 x 2 -F (x 2 ) where F (x) is defined in (73).

Then we have that JJ

Table content: <table><tr><td/><td/><td/><td>γ 4 2γ 2 +L 2 I, so by Lemma 4.3, H</td></tr><tr><td colspan="4">satisfies the PL condition with parameter γ 4 2γ 2 +L 2 .</td></tr><tr><td colspan="2">H.5 PROOF OF LEMMA 4.10</td><td/><td/></tr><tr><td colspan="4">To prove Lemma 4.10, we use the following lemma:</td></tr><tr><td>Lemma H.2. Let H =</td><td>A -C</td><td>C -B</td><td>, where C is square and full rank. Moreover, let c =</td></tr><tr><td>(σ 2 min</td><td/><td/><td/></tr></table>

Peer review (iclr2020):
*Summary* This paper study the convergence of Hamiltonian gradient descent (HGD) on minmax games. The paper show that under some assumption on the cost function of the min max that are (in some sense) weaker than strong convex-concavity. More precisely, they use the ‘bilinearity’ of the objective (due to the interaction between the players) to prove that the squared norm of the vector field of the game follows some Polyak Lojasiewicz condition. Thus the proof is concluded by the linear (resp. sublinear) convergence of gradient descent (resp. stochastic GD) under PL assumption. *Decision* I think that is work is clearly very interesting. The fact to prove linear convergence rate without strong-convex-concavity is quite surprising. And this paper brings nice tools to analyse HGD. Also the result on Stochastic HGD is very interesting. However, I am wondering whether this paper is perfectly suited to ICLR conference due to the lack of experiment, practical implication given by the theory, or theory in the non-convex setting (I know that the latter is a huge open question and I am not criticizing the absence of theory in the non-convex-concave setting). One way to improve to work would be to provide practical takeaways from the theory or to provide experiments in the main paper. Regarding the practical limitation of this work: - the sufficient bilinearity condition are hard to meet in practice. (even for convex-concave problems) - In a non-convex-concave setting, Hamiltonian gradient descent is attracted the any stationary point, even “local maxima” (or the equivalent in the minmax setting). Making this algorithm not very practical. (However, CO is) However, I really think that the community is currently lacking of understanding on minmax optimization and that we need better training method in many practical emergent frameworks that are minmax (such as GANs or multi agent learning). That is why, I would vote for a weak accept. *Questions* - What are the practical implication of your work ? for instance does it say anything on how to tune for CO ? *Remarks* - It is claimed that Theorem 3.4 gives the first linear convergence rate for minmax that does not require strong-convex or linearity. Note that, recently [1] seem to propose a result on extragradient in the same vein (i.e. without strong convexity or linearity). - (Minor) not alway have the same unit: Thm 3.2 it is proportional to a strong convexity and in Lemma 4.7 it is proportional to a strong convexity squared (actually the PL of the squared norm of the gradient). For clarity it might be interesting to use the notation in Lemma 4.7. The same way for unit consistency I would use instead of [1] Azizian, Waïss, et al. *A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games.* arXiv preprint arXiv:1906.05945 (2019). === After rebuttal === I*ve read the authors*s response. The concern raised by reviewer 3 is very important. The descent lemma used by the author is not valid for the stochastic result. The authors should address that in their revision. I however maintain my grade.