Last-iterate convergence rates for min-max optimization
Authors: Jacob Abernethy
Kevin A. Lai
Andre Wibisono
Venue:  (2020)
Keywords: min-max optimization
zero-sum game
saddle point
last-iterate convergence
non-asymptotic convergence
global rates
Hamiltonian
sufficiently bilinear

Abstract: While classic work in convex-concave min-max optimization relies on average-iterate 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 “sufficiently bilinear” condition. We also prove similar convergence rates for some parameter settings of the Consensus Optimization (CO) algorithm of Mescheder et al. 2017.

Under review as a conference paper at ICLR 2020
LAST-ITERATE CONVERGENCE RATES FOR MIN-MAX OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
While classic work in convex-concave min-max optimization relies average- iterate 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 challenging because many natural algorithms, such as Simultaneous Gradient Descent/Ascent provably diverge or cycle even in simple convex-coneave min-max settings, and previous work on global last-iterate convergence rates has been limited to the bilinear and convex-strongie concave settings. In this work, we show that the HAMILTONIAN GRADIENT DESCENT (HGD) algorithm achieves linear convergence in variety of more general settings, including convex-concat 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 Mescheder et (2017).
INTRODUCTION
In this paper consider methods to solve smooth unconstrained min-max optimization problems. In the most classical setting, min-max objective has the form
ming, max,, g(21, 22)
where g Rd x Rd
+ R is 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 (xi, e Rd x Rd that satisfies
g( x2) S (0 S 0(11,
for every 21 E Rdd and x2 E Rd. 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 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 is convex in #1 and concave in T2, is a classic min-max problem that has number of different applications, such solving constrained convex optimization problems. While variety of tools have been developed for this setting, very popular approach within the machine learning community has been the use of so-called no-regret algorithms Desa-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 simple computational method via repeated play: each of the inputs æı and are updated iteratively according to no-regret learning protocols, and one can prove that the average-iterates (x1, .2) converge to min-max solution.
Recently, interest min-max optimization has surged due to the enormous popularity of Generative Adversarial Networks (GANs), whose training involves solving nonconvex min-max problem where I1 and 22 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 infeasible to find "global" solution of the min-max objective. Instead, a typical goal in GAN training is to find local min-max, namely pair (xj, 2r))) that satisfies (o) all (I1,222 in some neighborhood of (g).

---

Under review as a conference paper at ICLR 2020
Second, iterate averaging lacks the theoretical guarantees present in the has motivated research on last-iterate convergence guarantees, which are appealing because they more easily carry over from convex to nonconvex settings.
setting. This
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 Ca2 for some arbitrary matrix C. SGDA provably cycles in continuous time and diverges in discrete time (see for example Daskalakis al. (2018): Mescheder et al. (2018). In fact, the full range of
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 eyclic behavior, a phenomenon commonly observed when training GANs in practice as well.
Much of the recent research on last-iterate convergence in min-max max problems has focused on asymptotic or local convergence (Mertikopoulos et al., 2019 Mescheder et al., [2017: Daskalakis & Panageas] 2018; Balduzzi et al.J 20188 Letcher et al., 2019; Mazumdar et al. 2019). While these results are certainly useful, one would ideally like to prove global non-asymplolic 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 [Teeng 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?"
Understanding global last-iterate rates in the convex-concane setting is an important stepping stone towards provable last-iterate rates in the nonconvex nonooneveee setting. Motivated by this, we prove new linear last-iterate convergence rates in the convex-concan 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. (0017); Balduzzi et al. (2018). Our results are the first to show non-asymptotic convergence of efficient algorithm in settings that not linear or strongly convex in either input. In particular, we introduce a novel "sufficienlly bilinear" condition on the second-oree -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 (PL) condition or pure bilinearity. Our analysis relies on showing
Our Contribution
such as the 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/Vk) le) in the "sufficiently bilinear" setting. On the practical side, while vanilla HGD has issues training GANs in practice, Mescheder et a (2017) show that a related algorithm known as Consensus Optimization (CO) can effectively train GANs in 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.
We begin in Dection@wiin with background material and notation, including some of our key assump- tions. In Section S we discuss Hamiltonian Gradient Descent (HGD), and we present our linear convergence rates for HGD in various set- tings. In Section 4 we present some of the key technical components used to prove our results from Section Finally, in Section we present our results for Stochastic HGD and Consensus Optimization. The details of our proofs are in Appendix H
Mariing
Figure 1: HGD converges quickly, while SGDA spirals. This vonconvex-nonconeea objective is in defined in Appendix K
2

---

Under review as a conference paper at ICLR 2020
2 BACKGROUND
2.1 PRELIMINARIES
In this section, we discuss some key definitions and notation. We will use ||-|| to denote the Fuclidean norm for vectors the operator norm for matrices tensors. For symmetric matrix A, we will use Amin ( (A) and Xmax (A) to denote the smallest and largest cigenvalues of A. For a general real matrix A, miin (A) and o max denote the smallest and largest singular values of A.
Definition 2.1. A critical point of f Rd - R is point I E R such that V ff(z) = 0.
Definition 2.2 (Convexity / Strong convexity). Let 2 0. A function f Rdd I. is p-strongly convex if for any u,v & Rd, fu) 2 f(u) + [v), differentiable, f p-strongly-comvex iff for all x Rd, V f(x) = pl. If F 0 in either of the above definitions, f is called convex.
v) + ||| vll. When f is twice-
Definition 2.3 (Monotone/ Strongly monotone). Let μ 2 0. A vector field IR Rd is p-strongly #||== yl1² p= 0, v is called monotone.
monotone if for any y R., (x y, v(z) vv)) 2
Definition 2.4 (Smoothness). A function f: RRd + R is L-smooth if f differentiable everywhere and for all u, v E Id satisfies [[V](u) - V S L ||u v||.
Notation Since g is function of ø1 Idd and D2 Rd will often consider æ1 and T2 to be components of one vector x = (2) x2). We will use superscripts to denote iterate indices. Following Balduzzi et al. 2018), we use { (V 9, Vz,g) denote the signed vector of partial derivatives. Under this notation, the Simultaneous Gradient Descent/Ascent (SGDA) update can be written as x (k+1) = (k) n (x)))))
We will use J to denote the Jacobian of i.e. J= (
22
V2 V2
-
22229) Note that unlike
ma 9
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 when writing ç, J. 9, H, and other functions. Note that J, and H are defined for a given objective clarity. We will always assume is sufficiently differentiable whenever we take derivatives. In particular, we assume second-order differentiability in Section
omit this dependence
well for notational
will also use the following non-standard definition for notational convenience:
Definition 2.5 (Higher-order Lipschitz). A function y Rd - R is (L1, La, Lg)-Lipschitz if for all x E Rd, [|[(=)] I L1 and [[VÉ(=)]] s L2. and for all x. E Rd, |[VE(z) Vε(v))l La v/l
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 global min-maxes (i.e. they satisfy (1)
In other words, we prove convergence rates to min-maxes settings where convergence to criti- cal points is necessary and sufficient for convergence min-maxes. This assumption is true for convex-concave settings, but also holds for some semconvex-noncomeet settings, as we discuss in Ap- pendix E This assumption allows to measure the convergence of our algorithms to c-approximate critical points, defined as follows:
Definition 2.7. Let 0. A point E Rd x Dd is an e-approximate critical point if]((())]] e.
Convergence to approximate critical points is a necessary condition for convergence to local or global minima, and it is natural measure of convergence since the value of 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
3

---

Under review as a conference paper at ICLR 2020
2.2 RELATED WORK
Asymptotic and local convergence Several recent papers have given asymptotic or local con- vergence results for min-max problems. Mertikopouloss et al. (2019) show that the extragradient (EG) algorithm converges asymptotically ı a broad class of problems known as coherent saddle point problems, which include quasiconvex -ounneee-uussccncvveee problems. However, they do not prove convergence rates. For more general smooth nonconvex min-max problems, number of different papers have given local stability or local asymptotic convergence results for various algorithms, which we discuss in Appendix
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 linear convergence rate for the proximal point method in the bilinear and strongly convex-strongee concave cases. Another classic result, by Tseng (1995), shows linear convergence rate for the extragradient algorithm in the bilinear case. Liang & Stokes (2019) show that number of algorithms achieve a linear convergence rate in the bilmnar case, including Optimistic Mirror Descent (OMD) and Consensus Optimization (CO). They also show that SGDA obtains linear convergence rate in the strongly convex- 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 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 full column rank linear interaction term
Non-uniform average-iterate convergence A number of recent works have studied the conver- gence 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(x1, is called HAMILTONIAN GRADIENT DESCENT (HGD). HGD consists performing gradient descent on a particular objective function H. that we refer to the Hamiltonian, following the terminology of Balduzzi et al. 2018 P If we let
0g 0g be the vector of (appropriately-sipp siigee) partial derivatives, then the Hamiltonian is:
D21
0zz
0g (x) H(x) 11((2))]12 = (1
0g D2g
(x)
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 critical point is equivalent
finding a saddle point. This motivates the HGD update procedure on (x(k) (x((a) x22 step-size >> 0:
(k) with
x ( = (k) (100))/VH((+ 1)
(2)
HGD has been mentioned in Mescheder al. (017)) Balduzzi at 2018). and it strongly resembles the Consensus Optimization (CO) approach of Mescheder et al. (2017). The HGD update requires a Hessian-vector product because VH { J, making HGD 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-vecee vvector product oracle theoretically appealing primitive, and it has been used widely in the nonconvex optimization literature. Since Hessian-vector product oracles are feasible compute for GANs, many recent algorithms for local min-max nonconvex optimization have also utilized Hessian-vecti products (Mescheder et al.) Balduzzi et al., 2018: Adolphs et al. 2019 Letcher et al. 2019 Mazumdar et al. 2019).
2017
f(x) 25 Ax; h(xz). where is smooth and convex, h is smooth and strongly convex, and A has full column rank. We make brief comparison of work to that of Du
'Specifically, they assume g(21,
Hui 2019) for the convex -ttoeyyytrongl concave setting in Appendix([)
We note that the function H is not the Hamiltonian as in the sense of classical physics, we do not use the
symplectic structure in our analysis, but rather only perform gradient descent on H.
4

---

Under review as a conference paper at ICLR 2020
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 is bilinear, (b) when is strongly strrony 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 open problem. This work is the first to show that an efficient algorithm, namely HGD, can achieve non-asymprotic convergence in settings that are not strongly convex or linear 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-par assumption:
Assumption 3.1. Let g Rd 12 R.
1. Assume critical point for g exists.
2. Assume is (L1, L2, -ap-sscchittzz and let Lx = L1L3 + L3.
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 22) be a-strongly convex in æı and a-strongly concave in 22- Then HGD with step-size d 1/L4 starting from some x0 E IR x Rd will have the following convergence rate:
[|{()())|| = (1- 0² k/2
Lx ||{(=()))]
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.7 hold and let g( be L-smooth in 21 and linear in D2, and
assume the cross derivative V V "1,229 is fill rank with all singular values at least y >> 0 for all
E Rd x Rd. Then HGD with step-size vj 1/ I/L starting from some (0) E Rd Rd will have the
following convergence rate: ||5(x(())]| - (1 (2.2412))m
k/2
||((x:())]
Finally, we show our main result, which requires smoothness in both players and a large, well- conditioned cross-derivative.
Theorem 3.4. Let Assumption
3.1 hold and let g be L-smooth in 21 and L-smooth Z2. Let μ²² a2aa ( x2)) and p² = minz,,22 (aanu((Va,,,le (2))), ))), and assume the cross derivative 42 #i is full rank with all singular values lower bounded by >> 0 and upper bounded by I for all x E Rdd Rdd. Moreover, let the following "sufficiettly bilinear" condition hold:
minz,,2 Amin (( ((V2
(n² + pT + )- 4
0.
(3)
Then HGD with step-size 11 = 1/ La starting from some x (0) IRd x Rd will satisfy
[[(()( < (1 (0² T2
k/2
||((=()))|]
(2 127 LN
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(21, =2)2 f(z1) ) 3Lx x2 h(*2), where f and are L-smooth convex functions, satisfies the assumptions of Theorem 3.4 and is not strongly convex or linear in either input. We discuss simple example that is not convex-concave in Appendix [.] We also show how our results can be applied to specific settings, such 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). p. We give some explanations for this condition in the following section. In simple experiments for HGD convex-concave and nonconvex nonconvex-nonconeee nonconcave objectives, the convergence rate speeds up when there a larger bilinear component, expected from theoretical results. We show these experiments in Appendix K
5

---

Under review as a conference paper at ICLR 2020
3.2 EXPLANATION OF "SUFFICIENTLY BILINEAR" CONDITION
Suppose our objective is g( 22) (Z1 x2) + CT1 z2 for smooth function 9. Then for sufficiently large values of e (i.e. has a large enough bilinear term), we see that satisfies (3) To see this, note that if we have y*t 4L212, then (3)dition3))holklll
In this section, we explain the "sufficiently bilinear" condition
Let and I" be lower and upper bounds on the singular values
of 2 #1 Then it suffices to have (r' + c)² > (T' + =)², which is true for 3 max T., r"
(i.e. ((L) suffices).
This condition is analogous to the case when we use SGDA on the objective g(z1, g( 22)
|||z,||² || for L-smooth convex-concave g. According to Liang & Stokes (011 SGDA will converge at a rate of roughly L log(1/e) for L-smooth and c-strongly convex- stroogyyt concave objectives 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 large (this can be thought of as a large condition number). Finally, for c (2(TT)) we get fast linear convergence, since Lte O(1). Thus, to get fast linear convergence suffices make the problem "sufficiently strongly convex-strongly concave" (or "sufficiently strongly monotone").
Theorem 3.4 and condition 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 objective (22) = 0(z), x2) +czz 22 for smooth function G. we will get linear convergence || 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.
2 و | S 8L and e 2 3(1 + +8)L, which
Another way understand condition (3) is that it is sufficient condition for the existence of unique critical point in a general class settings, as we show in the following lemma, which we prove in Appendix F
Lemma 3.5. Let g(I1, x22) f(z1) + ca. x2 h(x2)) where and h are L-smooth. Moreover, assume that 2 fx1) and (2)(12) each have a eigenvalue for some Iı and x2. (3) holds, then g has a unique critical point.
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 g(x) = 0) are global minima of H. } ||E11.. On the other hand, there is guarantee that H. is convex potential function, and a priori, one would not assume gradient descent on this potential would find a critical point. Nonetheless, we are able show that in 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 = Vg.
4.1 THE YOLYAK-L.OJSSEENT CONDITION FOR THE HAMILTONIAN
We begin by recalling the definition of the PI. condition.
Definition 4.1 (Polyak-Lojasiewin) (PL) condition Polyak (1963)
Lojasiewicz (1963)). A function f: Rdd R satisfies the PL condition with parameter 0 if for all E Rd. 2 [V
(f((x) min ER4 fxx"))
The PL condition is well-known to 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 (163)). Let S Rdd - R be
L-smooth and let x² E arg min ](x). Suppose satisfies the PL. condition with parameter Then if we gradient descent from (0) E gdd with step-size t. have; f(x(k) f(x²) --) f(x))).
"The actual rate log(1 //),, for some parameter (3 that least (I. o)2

---

Under review as a conference paper at ICLR 2020
For completeness, provide the proof of Theorem 4.2 in Appendix
All of our results use Assumption 3.1, so we are guaranteed that g has critical point. This implies that the global minimum of H. is O, which allows to prove the following key lemma:
Lemma 4.3. Assume we have twice disferentiable (12) with associated H. Let e 0. If JJJ = al for every x, then H. satisfies the PL condition with parameter a.
Proof. Consider the squared norm of the gradient of the Hamiltonian:
1IV = 1 1 E11
1 (s, (JJ )
2 [Ell =
atH
The proof is finished by noting that H(x)) [-= = O when x is critical point.
To use Theorem 4.2, we will also need to show that H. is smooth, which holds when g is (L1, L2, L3)- Lipschitz. The proof of Lemma 4.4]is in Appendix
Lemma 4.4. Consider any g(an, x2) which is (I,, L2, Ia) Ia)-Lipschitt.for constants L1, L2, L3 Then the Hamiltonian H(xx) is (L1 + L smooohh.
To use Lemma 4.3 we will need control over the cigenvalues of JJJT. which we achieve with the following linear algebraic lemmas. We provide their proofs in Appendix H
Lemma 4.5. Let H ( (-B -M2
M. eigenvalues of H we have X > e.
B and let O. If Mi el and M2 -el, then for all
Lemma 4.6. Let H (-2- )). where square and full rank. Then if X an eigenvalue of H then we must have 20 (C)
(C)+
4.2 PROOF SKETCHES FOR THEOREMS 3.2
3.3 AND 3.4
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 Rd x Rd E. suppose H. satisfies the PL condition with parameter and is Lag-smooth. Then if we use HGD starting from some (0)) E Rdd x Bd with step-size n = 1/ TTx. then we have the following:
||(()()))|| < (1-
k/2
|E(](())|
Proof. Since H. satisfies the PL condition with parameter a and H. LH-smooth, we know by Theorem 4.2 that gradient descent on H with step-size 1/Lu converges at a rate H(x(k)) (1 Lx (H)))))) Substituting in for gives the lemma.
It remains show that H satisfies the PL condition in the settings of Theorems 3.2 to 3.4 show the result for the strongly convex-strongly concave setting of Theorem 3.2
First,
Lemma 4.8 (PL for the strongly convex-strongly concave setting). Let g be c-strongly conver in #1 and c-strongly concave in Z2, Then H. satisfies the PL condition with parameter c².
Proof. We apply Lemma 4.5 with H J. Since g is e-strongly-convex in I and e-strongly concave in T2 we have Mi = V2 2, > cl and M2 = -2 # > cl. Then the magnitude of the
eigenvalues of J is at least c. Thus, JJ > eT,, so by Lemma 4.3 H satisfies the PL. condition with parameter ?
Next, we show that H. satisfies the PL condition for the noncomvex- -inear setting of Theorem 3.3 We prove this lemma in Appendix Hy using Lemma 4.6
7

---

Under review as a conference paper at ICLR 2020
Lemma 4.9 (PL for the smooth conconvex-linent setting), Let g be L-smooth in 21 and lin- ear in 222- Moreover, for all a E R R let V 121 Ø2) be full rank and square with
mmin (V2 2, (01, x2)) 2 7. Then H. satisfies the PL condition with purameter a = +4
Finally, we prove that H. satisfies the PL condition in the panconvex--oncomme setting of Theorem 3.4 The proof for Lemma is Appendix H.5 and it uses Lemma H.2 which similar to Lemma 4.6
setting). Let g be L-smooth in I and L-smooth in 22. Also, let V2 V2 q be fill rank and let all of its singular values be lower bounded by y and upper bounded by I for all x E R.d x Rdd Let p² minz1,z2 Amin ((V2 0, , and
Lemma 4.10 (PL for the smooth
4² mingg,22 Amin (V2 (21,
Assume the following condition holds:
(72 + p²) + 12) 4 0.
2 (1 -1,2772
Then H. satisfies the PL condition with parameter a
2
+
Combining Lemmas 4.8 to 4.10 with Lemma
4.7 yields Theorems 3.2
3.4
EXTENSIONS OF HGD RESULTS
Stochastic HGD
Our results above also imply rates for stochastic HGD, where the gradient V in (2) is replaced by a stochastic estimator of VH such that Fl VH. Since show that H
satisfies the PL condition with parameter in different settings, we can use Theorem in Karimi et al.
(2016) to show that stochastic HGD converges at O(1/Vk) rate in the settings of Theorems 3.2
3.4 including the "sufficiently bilinear" setting. We prove Theorem 5.1 in Appendix !|
Theorem 5.1. Let Assumption 3.1 hold and suppose H satisfies the PL condition with parameter a.
Suppose we use the update x = (*))) TT (zrk),,, where v is stochastic estimate of VH such that E[u] = W. and []] (1)
we have the [1]5 & C² for all 1kk), Then if we use 2ack
2k-1
following convergence rate: E[|(((=:(0)]] S
Lx ka -
Consensus Optimization as follows:
The Consensus Optimization (CO) algorithm of Mescheder et al. (0117)
(1+1) x 7(E(( VVH((())))
where > O. 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 variety of settings, including on CIFAR-10 and celebA. While they frame CO as SGDA with small modification, they actually set y 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 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 showing that HGD still performs well even with 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-asymplotic convergence. We prove Theorem 5.2 Appendix
which implies that we get linear convergence of
Theorem 5.2. Let Assumption 3.1 hold. Let be Lg smooth and suppose H satisfies the PL condition with parameter a. Then if we update some (U) E Bdd x Rdd using the CO update (5) with step-size
Cr L,
and 7 41.g, we get the following convergence:
||<()()))|| <
(6)
We also show that CO converges in practice some simple examples in Appendix
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Jacob Abernethy, Kevin A Lai, Kfir Y Levy, and Kun Wang. Faster rates for convex-coneave games. Conference on Learning Theory (COLT), 2018.
Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmann. Local saddle point optimization: curvature exploitation approach. In Artificial Intelligence and Statistics (AISTATS), 2019.
Naman Agarwal and Elad Hazan. Lower bounds for higher-order convex optimization. In Conference on Learning Theory (COLT), 2018.
Yossi Arjevani, Ohad Shamir, and Ron Shiff. Oracle complexity of second-order methods for smooth convex optimization. Mathematical Programming, pp. 1-34, 2017.
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The mechanics n-player differentiable games. In International Conference on Machine Learning (ICML), 2018.
George W Brown. Iterative solution of games by fictitious play. Activity analysis of production and allocation, 13(1):374-376, 1951.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems (NeurIPS), pp. 9255 9265, 2018
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In International Conference on Learning Representations (ICLR). 2018.
Simon S Du and Wei Hu. Linear convergence of the primal-dual gradient method for convex-concave saddle point problems without strong convexity. In Artificial Intelligence and Statistics (AISTATS), 2019.
Yoav Freund and Robert E. Schapire. Adaptive Game Playing Using Multiplicative Weights. Games and Economic Behavior, 29(1 (9(1-)):79-133, October 1999.
Gauthier Gidel, Hugo Berard, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial nets. International Conference on Learning Representations (ICLR), 2019.
Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville. and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2672-2680, 2014.
James Hannan. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, 3:97-139, 1957.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 23:55):57-3325, 2016.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Polyak-tojasiewiez condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 795-811. Springer, 2016.
Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen. Progressive growing of gans for improved quality, stability, and variation. International Conference on Learning Representations (ICLR), 2018
Christian Kroer. First-order methods with increasing iterate averaging for solving saddle point problems. arXiv preprint 19X03 /0646, 2019.

---

Under review as a conference paper at ICLR 2020
Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, and Shimon Whiteson. Stable op- ponent shaping in differentiable games. In International Conference on Learning Representations, 2019. URL
Tengyuan Liang and James Stokes. Interaction matters: A on non-asymptotic local convergence of generative adversarial networks. Artificial Intelligence and Statistics (AISTATS), 2019.
Lojasiewiez. A topological property of real analytic subsets (in french). Coll. du CNRS, Les équations aux dérivées partielles, pp. 87-89, 1963.
Eric V Mazumdar, Michael I Jordan, and Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. arXiv preprint arXiv: /90100080303 2019.
Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 2703-2717. SIAM, 2018.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra(- gradient) mile. In International Conference on Learning Representations (ICLR), 2019.
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of GANs. Advances in Neural Information Processing Systems (NeurIPS), pp. 1825-1835, 2017.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for gans do actually converge? In International Conference on Machine Learning (ICML), pp. 3478-3487, 2018.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. arXiv preprint arXiv:1901.08511 2019.
J Neumann. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1):295-320)) 1928.
Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1):147-160, 1994.
B. Polyak. Gradient methods for minimizing functionals (in russian). Zh. Vychisl. Mat. Mat. Fiz., pp. 643-653, 1963.
Julia Robinson. An iterative method of solving game. Annals of mathematics, pp. 296-301, 1951.
Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal control and optimization, 14(5):877-898, 1976.
Paul Tseng. On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 60(1-2):237-252 1995.
Yasin YazIeı, Chuan-Sheng Foo, Stefan Winkler, Kim-Hui Yap, Georgios Piliouras, and Vijay Chandrasekhar. The unusual effectiveness of averaging in gan training. International Conference on Learning Representations (ICLR), 2019.
10

---

Under review as a conference paper at ICLR 2020
A GENERAL NONCONVEX MIN-MAX OPTIMIZATION
In standard nonconvex optimization, common goal is find second-order local minima, which approximate critical points where V is approximately positive definite. Likewise, common goal in nonconvex min-max optimization is to find approximate critical points where an analogous second- order condition holds, namely that V 2112 (ar) is approximately positive definite and V z2z2 ((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 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 al. 2017: Daskalakis & Panageas 2018 [alluzzi 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 local min-maxes and unstable at some set of undesirable critical points (such as local max-mins). This essentially amounts to guarantee that in the convex-come 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.
A.1 NONCONVEX EXTENSIONS FOR HGD
While the naive version of HGD will try to converge all critical points, we modify HGD slightly to achieve second-ordes stability guarantees as in various related work such as Balduzzi et al. (2018): [etcheer al. (201)). In particular, we consider modifying HGD that there is some scalar a in front of the VH term as follows:
(k+1) xx) (R) nja (x))))
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:
(++1) 1) (k) - T)(((x - -AT ((a)))
(8)
where A is the antisymmetric part of J and A = sgn ((S, (AT ()). Balduzzi et al. (2018) show that À is positive when in a strictly convex-strictly concave region and negative in a strictly concave-strictlyy convex region. Thus, if we choose that the modified HGD will exhibit local stability around strict min maxes and local instability around strict max-mins. This follows simply because will do gradient descent on H. in the first case and gradient ascent on H. in the second case.
À sgn ((E (AT J))), we can ensure
Another way to choose a involves using approximate eigenvalue computation on V2 22 9 and v detect whether V2 is positive semidefinite and V #2 negative semidefinite (which would mean we are in a convex-concave region). We set a = 1 if we are in a convex-concad 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 logarithmic number of Hessian-vector products.
B BACKGROUND ON NON-UNIFORM AVERAGE ATERATES
A number of recent works have focused on the performance of a non-uniform average of an algorithm's 's iterates. Iterate averaging can lend stability to an algorithm or improve performance 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 non-uniform averaging as an interpolation between average-iterate and last-iterate algorithms.
11

---

Under review as a conference paper at ICLR 2020
One popular non-uniform averaging scheme is the exponential moving average (EMA). For algorithm with iterates 20)) syy 2(²), the EMA at iterate is defined recursively
(e) EMMA
BZEMA + (1 3)
where 2 EEMA = (0) and 3 1. A typical value for 3 is 0.999. YAZIeı et al. 2019) and Gidel et al.
(0)
(2019) show that uniform and EMA schemes improve GAN performance 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 mitly, maxas (x1 g(x)) + (K (2) (x2). where f is smooth convex function, 9 and 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 least 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 achieve faster convergence rates in some specific convex-coneat games.
Overall, while non-uniform averaging is appealing for variety reasons, there is currently no theoretical explanation for why it outperforms uniform averages or why it would converge at all in many settings. fact, one natural way 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
((((h11)) f(²)) f(x f(x²)
2L V V
(9)
$ f(x -f(x²) L
(f(x)()) - f(x²))
(10)
-1- 2) (f(xx()) f(x"))
(11)
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 (019)
In this section, compare results in Theorem 3.4 to those Du & Hu (2019) Du & Hu 2019 prove a rate for SGDA when is L-smooth and convex in æi and L-smooth and j--strogly concave in 22 and 2 2 9 some fixed matrix A. The specific setting they consider is find the unconstrained min-max for function g Rdd x R IR defined as g( x22 = f(r)) an Az h(x2) where is convex and smooth, is strongly-conver and smooth, and A E Rd2xd, has rank d1 (i.e. A has full column rank).
Their rate uses the potential function P. = Xax- b. where we have:
2T +
(12)
un2
x
(13)
by
82
(K)
(14)
where xz) the min-max for the objective. Their rate (Theorem 3.1 in Du & Hu 2019
12241
Po+1 <
1 1-c
Ps
(15)
TT
+
1
12

---

Under review as a conference paper at ICLR 2020
for some constant 0. To translate this rate into bounds on ness of in both of its arguments to note that
||l||.
the smooth-
ae (x1,
8g
0z (2),
8q
8g az (2f. =3) -
L 2 -zi and likewise for ø2. So the rate on Pk translates into rate on |Elll with some additional factor in front.
Their rate and our rate are incomparable neither is strictly better. For instance when y 1 much larger than all other quantities, their rates simplify to (1 (1-0 (1))
K while ours go to
(1-0 ) k/2 While our convergence rate requires the sufficiently bilinear condition (3) to hold, we do not require convexity in ø1 or concavity in Ø2. Moreover, we allow V 2 9 to change as long as the bounds on the singular values hold whereas Du Hu (2019) require V matrix.
mi 2 to be a fixed
E
SETTING WHERE ASSUMPTION 2.6 AND THE CONDITIONS FOR THEOREM 3.4 HOLD
In this section we give a concrete example of a einoonvc-nnoconcawe setting where Assumption 2.6 and the conditions for Theorem 3.4hold. We choose this example for simplicity, but can easily come up with other more complicated examples.
For our example, we define the following function:
3(x + 7)
for x < -2
F(x)
cos
for
(16)
COS x + 2x
for x >
The first and second derivatives of F are follows:
-3
for < -
F'(x)
3sin x
for
_ < x S
(17)
2
sin + 2
for x > I
0
for <
F" (x)
3 cos x
for 7
(18)
cos x
for x > n
From Figure 2 we can see that this function is neither convex nor concave.
Our objective will be g( 92) F(x1) + F(x2). Note that L 3 because Fx) S for all x. Also,
r = since V 41.
First, we show that y satisfies Assumption 3.1 We see that g has a critical point (0,0). Moreover, g is (T,, T,2 Tap-Liischhitz for any finite-sized region of R2. Thus, if we assume our algorithm stays within a ball of some radius R, the (L1, L2. L3) Liisschit assumption will be satisfied. Since our algorithm does not diverge and indeed converges at linear rate to the min-max, this assumption is fairly mild.
Next, show that g satisfies condition 3 this holds because 7² = 256 and 4LT
Condition
3 requires y > 4 for g. We that 192.
4
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 critical point (at (0, 0)) and that this critical point is min-max. We first give a "proof by picture" below, showing a plot of g in Figure 3 along with plots g(: and g0. showing that (0, 0) is indeed min-max.
We can also formally show that (0, 0) is the unique critical point of and that is a min max. We prove this for completeness, although the calculations more less amount to simple case analysis.
13

---

Under review as a conference paper at ICLR 2020
f(x)
f(x)
('()
10
Figure 2: Plot of nonconvex function F(x) defined in (16) well as its first and second derivatives
Let us look at the derivatives of with respect to x and nz
(-3 + 4r²
for 01 S --
0g (21,
2
3 æ1 + 4.²
for 5
< x1 S
(19)
0x
sin 21 + 2 + 4x2
for I1 >
3 + 4x 3sin 22 + 4x
for 22 S -
0g (x), 22)
for 3/2 82 S
(20)
Ox²
sin x2 + + 4x
for T2
g 2
Observe that if di E E 3: ]] then critical points of g must satisfy s #1 + 4x² which implies that Ø2 E [- (31 Likewise, x2 1- 3.. then critical points of must have x2 [- 3/4 3. We show that this implies that g only has critical points where 21 and x2 are both in the range 2 21.
Suppose g had critical point such that 21 < 2 Then this critical point must satisfy 222 3 But from our observation above, if critical point has x2 then 21 must lie in [- 2 21. which contradicts æ < 2.
Next, suppose g had a critical point such that #1 5. Then this critical point must satisfy T2
(sin + 2), which implies that x2 E [-3 4 3.. But then by the observation above, æ1 must in [- 3 31 4: 4 which contradicts 21 >
that any critical point of must have arguments to show that any critical point of g must have x2 E |- r
From this
[- T 3. We make analogous
2121 -
From this, conclude that all critical points of g must satisfy the following:
s 0i + 4x 0 3in
(21)
D2 4x 0
(22)
14

---

Under review as a conference paper at ICLR 2020
200
100
9
0
100
200
8
4
2
8
0
4
-2
2
X2
4
X1
6
8
8
Figure 3: Plot of nonconvex nonconcaveenccccveeeeeee g(21, F((1)) 4x F(x2)
These equations imply the following:
3
sin.F2
(23)
sin T1
(24)
4
3
3
sin
sin T2
(25)
4
4
3
3
32
sin
sin T2
(26)
4
4
That is, for all critical points g. 21 must be a fixed point of (x(2) = sin (- sin 2r) and 2g must be a fixed point of (2()) = 3 sin (3 sin.). Since 1h (x)] < 1 and 1hg (x) < always, h and h2 are contractive maps, so they have only one fixed point each. Thus, y will only have one critical point, namely the point (æ1, .22) such that 2ú is the unique fixed point of hı and is the unique fixed point of hzz.
(3
Finally, can observe that (0, 0) is critical point of g. so it must be the unique critical point of One can also see that this is min-max by looking at the second derivatives of F (1)).
F PROOF OF LEMMA 3.5
To prove Lemma 3.5
will the following lemma:
15

---

Under review as a conference paper at ICLR 2020
25
20
15
g(,
10
5
0
-10.0
-7.5
-5.0
-2.5
0.0
2.5
5.0
7.5
10.0
Xi
Figure 4: Plot of g(. 0). We can see that there only one min and occurs at æ1 = 0.
-5
-10
-15
-20
-25
10.0
-7.5
-5.0
-2.5
0.0
2.5
5.0
7.5
10.0
Xa
Figure 5: Plot of g(0, x2). We can see that there is only one max and it occurs at
0.
16

---

Under review as a conference paper at ICLR 2020
Lemma F.1. Let g(2),
f(1) + caf x2 h(22) where and h are L-smooth. Then if c L,
9 has a unique critical point.
Proof of Lemma 3.5
Condition
(3) is as follows:
(7 + p² + +
41,272 O.
(27)
Note that in setting, 7 r c. Next, observe that if V (2)(x) and (2)(222) each have a eigenvalue for some 2i and 22, condition (3) reduces to:
2L.
(28)
Then by Lemma F.1 we see that g must have a unique critical point.
Next, we prove Lemma
Proof of Lemma F.7 Suppose our objective g(r,, x2) = f(x)) cx. x2 M(x2)) where f and
are both L-smooth convex functions. Critical points of g must satisfy the following:
Vf(z)) cr2
(29)
Vh((2) + = 0
(30)
+ 21 (h((22)
(31)
+ 22 = v Vh(x2)
(32)
In other words, 22 must be fixed point of F(2) = VVS Vh))). The function F will have unique fixed point if it is contractive map. We now show that for > L, this is the case.
Vh(uw)
v ( VV((w)
[(()) F(V)lI
V
(33)
c
L
Vh(u))
[V((o))
(34)
L2
1|u w/l <
||u rll
(35)
where the inequalities follow from smoothness of f and h. An analogous property can be shown by solving for æı instead. Thus, if > L. then will have a unique fixed point.
Condition (3) is thus sufficient condition for the existence of unique critical point for the class of objectives above.
G APPLICATIONS
In this section, discuss how results be applied to various settings. One simple setting the Dirac-GAN from Mescheder et al. (018)), where g( x22 = min,, max fa x2) - f() for some function f whose derivative is always non-zero. When f(t) = the Dirac-GAN is just a bilinear game, so HGD will converge globally to the Nash Equilibrium (NE) of this Dirac-GAN, shown in Balduzzi 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 Mescheder al. (2018) shows that the diagonal blocks of the Jacobian are 0 at the NE for arbitrary 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 small smooth convex regularizer is added for either player.
Du & Hu (2019) list several applications where the min-max formulation relevant, such as in ERM problems with linear classifier. Given data matrix A, the ERM problem involves solving min, ((Ax) + fxx for some smooth, convex loss & and smooth, convex regularizer f. This problem has the saddle point formulation min,, max, y Ax 8 (y) + (zx. According to Du & Hu 2019)) this formulation can be advantageous when it allows finite-sum structure, reduces communication complexity in distributed setting, 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 l and f.
17

---

Under review as a conference paper at ICLR 2020
H PROOFS FOR SECTION 4
In this section, we prove our main results about the convergence of HGD, starting with some key technical lemmas.
H.1 PROOF OF LEMMA 4.4
Proof. We have VH. < U Rd x Rd. Then we have:
IVH((u) VH(x)]I =
( (()((u)J(u) _ (o)J(w)]
||5 (u) - (u)J(o)+ (w))))
-
(u)
- [w)[o)] -
< (15(n))1- J(v)ll [[(()) E(vIl (10)))11100)
< (L1 L2) zll
H.2 PROOF OF LEMMA 4.5
Mf + BB"
-M BM2 M3 + B
-(1i -T M2
M1 - B
Proof. Note that HHT
(M, + BM2)"
M1 -B
Now let Z = (BBT M2
It suffices to show that for any eigenvalue á of Z, [8| S
For the
sake of contradiction, let be an eigenvalue of Z with eigenvalue 8 such that |6| - Let v
V1
U/
Since Zu = 5u for |6] S and M1 > eT and M2 < -ET, we must have i1 # 0 and 12 * 0. Then have:
M2 13 TT v1 )
Mi Bvz
U11 1/2
8
(36)
This implies
(M1 - 81)01 = Buz
(37)
(M₂ 81)022 = BTvy
(38)
Let M1 M1 51 and let M2 M2 51. Note that M, > 0 and M2 - 0. Then we can write
11 = M Buy. Further, we can substitute into (38) to get
M262 BT BM Bu2
(39)
- MM 2 Bvz U2
(40)
In other words, 12 is an eigenvector of B M, B with eigenvalue 1. Let A - MM and
T= BT 2 B. Note that A is positive definite and T is PSD. Then we have:
AT 1/2 ( 1/2 /2 122
(41)
Since 41/2TA1/2 PSD, and A7 similar to /1/2TA1/2 we must have that all of the eigenvalues of AT are nonnegative. This contradicts that is an eigenvector of AT with eigenvalue -1. Thus, all eigenvalues of Z must have magnitude greater than c.
H.3 PROOF OF LEMMA 4.6
Proof. Suppose À is an eigenvalue of H with eigenvector e
D1j
WLOG, suppose
<
122
22 (C) Since is an eigenvector, we have:
AA2 +C+CCT
ACC CTC
(v)
V1
(42)
-OTA A
02
18

---

Under review as a conference paper at ICLR 2020
Thus, have:
(A2 + AT)n AC
(43)
Av1 + C-A)e =
(44)
Since À < o min (C), we have that CTC - AI is invertible, so we can write 2/2 = (CTC
C Au from the (44) Plugging this into (43) gives:
(A² CC AI ACCC C --) 1 A)81 =0
(45)
(A(I - - )A CCT - =0
(46)
Write the SVD of C as C = U.VT. Then we have:
=UVV UVV VEUT
(47)
-UEV -M)
(48)
(S-- -M)='"
(49)
(50)
UDU
(51)
where the second line follows because VVT I when C is full rank and where D is diagonal
(C)
matrix such that Di: (C))-
Let M = - D, so M is diagonal with M = - Then (46)
becomes:
(AMA + CC - xf)11
(52)
This means T = AMA + CC - XT has a 0 eigenvalue. A simple lower bound for the eigenvalues of T is
Amin (T) 2 - -1A|1
to Luin (C) - A
(53)
min X
We will show that if A 8, where min (C) + HAI Amin (T) > 0, which is contradiction. It suffices to show the following inequality:
(o _
0
min then
A
||A|1
Jn (C) - 0>>0
(54)
min
o (C) - X > ||| 2
(55)
o min
(o 2min (C)) x)2 > ||A|| X
(56)
X2 - (20 min (C) + || + miin (C) > 0
(57)
(77) has zeros the following values:
||A|12 2
||
min (C) + /
V(
02
odt Juin (C)
(58)
min
Since (57) convex parabola, if À is less than both zeros, will have proved (57) true if À 5.
This is clearly
As a last step, we can give slightly nicer form of 8, using Lemma H.1 Letting x = 2 (C)+ + ||A|| of (C)
2
and c = o (C',, we have 8 >
min ( [C|= So to reiterate, if < o
min (C)+IAA|| < 8, then
(57) holds, T > which contradicts (52)
Lemma H.1. For (0,1) and (0, 22).
). we have:
x
c>
2r
19

---

Under review as a conference paper at ICLR 2020
Proof.
1-Vr"
2
1
c
(1-
x²
2x 2x
H.4 PROOF OF LEMMA
Proof. Let C( x2)
V
21 (TI, For all E R2d x Rd, C(x1, is square and full rank
by assumption, miin (aa))
can apply Lemma 4.6 with H J at each point Rd x Rd,, which gives
)(JJT) 2 mon (C(m) ma + V2 21 ((m1 We have || V2 a ( x2) S L since g is smooth
in Ø1. Also, o min (C( x2)) 2 7. Then we have that JJ t 2 I, so by Lemma 4.3 H
satisfies the PL condition with parameter 25-41
H.5 PROOF OF LEMMA 1.10
To prove Lemma 4.10 use the following lemma:
(-C
A
C )) where C is square and full rank. Moreover, let
Lemma H.2. Let H-
-B)
(omin (C) + Amin )min(A?)) (A?)) (B?)
o min (C))
- (C)(II) [[B1)) and assume e >> 0. Then
A² + CCT
-AC - AC-CB
if A is an eigenvalue of H1 = -CT A BCT
B² CC
we must have
(o 2 (C) + Amin (A²)) (Amin((B))) + on (C)) 0 max )
A
(20 min (C) + Amin (A?) Amin \mi)(B2))
U11
Proof of Lemma H.2 This proof resembles that of Lemma 4.6 Let
be eigenvector of
HH. with eigenvalue A. Expanding HHH T de, we have:
(A² + +CC AT)n
+ +C++CB)
(59)
-(CT A BCT wn (B² + CC XT) 12
(60)
M
12 = = M (CT A BC )e1
(61)
(-(AC + CBBM A BCBC A2 +CC Af)e1 =
(62.)
where M is invertible because CTC is positive definite and WLOG, we may assume that Amin (C C* 2 (C). We will show that if the assumptions in the statement of the lemma hold, then we get contradiction if À is below some positive threshold. In particular, we show that the following inequality holds for small enough \ (this inequality contradicts (62))
2 (C) À + Amin (A3)
o e (C)(IAI1 + [|B1)) ||
02 2max (C)
002 min (C) - A Amin (A2)
Amin (B2) + 2 (C) - (|| + |[BI))
X2 -20 (C) + Amin (A2) + )minnB3)) min
(0 (C') + (A2)
(A²)) ( (B²) + on (C))-o- 2
[C)(IA]|+ (
0
Letting b = 20 (C) + Amiu (A2) + Amin B we can solve for the zeros of the above equation:
A b + Vb 4e
(63)
Note that we have > 0 by assumption, so this equation has only positive roots. Note also that 122 > 4c, the roots will not be imaginary. Then that if X 8 b-
get
20

---

Under review as a conference paper at ICLR 2020
contradiction. Using Lemma H.l that 8 > 8. So we've proven that À gives contradiction, so we must have À b. i.e.
(o min (C) + Amin (Ain((A)) (A2)) (B2) + min (C)) o max (C)[ +1B112
20 minn( (C) + Amin (A2) Amin (
Proof of Lemma 4.10 The proof is very similar to that of Lemma 4.9
Let C(z1, x2)
V2 12 (21. (2). For E R x R. C(z1, 22) 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 Rd Rd. Using the fact that g is smooth in 11 and T2, this gives
X(JJ)2 (o (C(),, Amin (A22) (C (C(11, x2)) p²) o (
2 min (C(z1, x2)) + Amin ( + 112
Using the bounds on the singular values of C(11, we have that JJ (7 thmin (A") (1? + - I, so by Lemma 4.3 H. satisfies the PL condition with parameter 27 Amin (42)+
(y3 +mmit (A () -
27 Amin (A2)+
I PROOF OF THEOREM 5.1
In this section, prove Theorem 5.1 (016
The proof leverages the following theorem from Karimi et al.
Theorem 1.1 (Karimi et al. (0166). Assume that f is L-smooth, has a non-empty solution set X",, and satisfies the PL condition with parameter Let be stochastic estimate of f such that Elu] = Vf. Assume ((])((=(())]1{]] S C² for all ((k) and some C. If we use the SGD update 2k+1
I(h+1) (k) ()((x(K) with Aik 2a(k+1]2, then, we get convergence rate of
LCC
B[f(xx) - fr 2ka
(64)
instead we constant T7s 1) 2n then obtain linear convergence rate up solution level that is proportional to
LC
(x)(x(()) f*1 I (1 - -an)2amn) 2an)" (f(x ff1+
(65)
4a
Now we can prove Theorem
Proof of Theorem 5.7 If H satisfies the PL condition with parameter a, then can apply Theo-
rem 1.1 to the stochastic variant of HGD. since H" = 0, we get
L2
E
(66)
2k
The theorem follows from Jensen's 's inequality, which implies that (+))]] s V (x({()))))
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 showing that HGD still performs well even with small arbitrary perturbations, as we show in the following theorem:
'The actual theorem in Karimi al. 2016) is stated in slightly different way, but it is equivalent presentation.
21

---

Under review as a conference paper at ICLR 2020
Theorem J.1. Let x((++)) x(()) ,)VH(x(()) + noulh) where e(h) is some arbitrary vector such that || = ||{()()))]| Let g be Lg smooth and suppose H. satisfies the PL condition with + and let tlu ILuLo' Then we get the following convergence:
parameter a. Let 17 In
||{()(()|| - (1- 1ixxxx) )
||((=(0)]|-
(67)
From Theorem it simple to prove Theorem 5.2
Proof of Theorem 5.2 Note that the CO update (5) with 4h is exactly the update in Theorem J.1
with v(h)
[((x
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
Proof of Theorem J.1
+noul From Let æ (k+1/22 = (k) v)HH(x())) so x0(11) x((+1/2)
(11) in the proof Theorem 4.2 with T.7 we get
[|((((+11)) < (1 (1- E
1/2
||(()()))|| S S zime ( [|E(co(61)11
(68)
Next, note that the triangle inequality and smoothness of imply:
(()(())))| - 5( (0+1/22))
+ ((((kt)) - ((x(02122))
-
(69)
< ((z
+ Lg [2(tt11) (x+1/22
(70)
[(z)
5
+ Ly Tl
(71)
Using the above result and | || ||5(x((1))1 we get:
[(n(ktti) - (1-
2Ln Lgglo [[c((
(72)
Setting T) aLx b, gives the result.
Note that for this result, we assume g 4g smooth in 11 and 22 jointly, whereas in other parts the paper we assume g is smooth in 22 separately. If g is L-smooth in 2 and L-smooth in 22 and [ (21, < Le for all 21, 22, then g will be L. L. smooth.
K EXPERIMENTS
In this section, we present some experimental results showing how SGDA, HGD, and CO perform on convex-concane objective and nonconvex nonooooccee objective. For our CO plots, 7 refers the Y parameter in the CO algorithm. All of our experiments are initialized at (5.5). The step- size for HGD and SGDA is always 0.01, while the step-size for CO with 7 (0.1. 10) (0.1, 0.01, 0.001} respectively to account for the fact that increasing ? increases the effective step-size, so the 7) parameter needs to be decreased accordingly. The experiments were all run standard 2017 Macbook Pro.
The main takeaways from the experiments are that CO with low 7 will not converge if there is 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 the optimal step-size is chosen for each setting.
22

---

Under review as a conference paper at ICLR 2020
K.1 CONVEX-CONCAVE OBJECTIVE
The convex-concave objective we use is g(1,,)) v2) f(xi) + co122 f(x2) where f(x)
log(1 e.). We show plot of in Figure
f(x)
f(x)
('(x
Figure 6: Plot of f(x) log(1 + e²) with its first and second derivatives. This is convex, smooth function
When SGDA converges, and when c 10, SGDA diverges. We note that HGD and CO (for large enough 7) tend to converge faster when c is larger.
K. SGDA CONVERGES (c =3) 3)
These plots show when c = 3, so SGDA converges, as does CO with 7 = 0.1.
23

---

Under review as a conference paper at ICLR 2020
Sinjgitaneous Gradient Descent/Ascent Hamiltonian Gradient Descent
SGDA
HGD
Sta Starting point
Min-max
5
X2
-5
-10
15
-10
-5
10
15
X1
(a)
SGDA
HGD
Starting point
Min-max
400
200
200
400
600
15
10
-15
-10
X2
-5
-5
5
-10
10
15-15
(b)
Figure SGDA vs. HGD for 300 iterations for g(21, 22) f(x1) + cz - f(22) where f(z) = log(1 + e*) and to the min-max.
3. SGDA slowly circles towards the min-max, and HGD goes directly
24

---

Under review as a conference paper at ICLR 2020
Consensus Optimization for different values of gamma
10.0
5.0
2.5
0.0
-5.0
CD with gamma 0.1
gamma 1
gemma
-7.5
Starting point
Min-max
-10.0
10.0
-75
-25
10.0
X1
(a)
.... CO with gamma 0.1
with gamma
CO with gamma 10
Starting point
Min-max
300
200
100
g
0
100
200
300
10.0
7.5
5.0
-10.0
-15.07.5-5.011
-2.
-2.5
X2
0.0
X1
2.5
5.0
-7.5
7.5
10:010.0
(b)
Figure 8: CO for 100 iterations with different values of for ((x1, f(x1) + criv2 f
where (x) = log(1 + e²) and c 3. The = 0.1 curve slowly circles towards the min-max, while the other curves go directly the min-max.
25

---

Under review as a conference paper at ICLR 2020
Consensus Optimization vs. Hamiltonian Gradient Descent
10.0
HGD
gamma
7.5
gamma
Starting point
Min-max
2.5
0.0
-2.
-75
-10.0
-1.5
-5.0
10.0
(a)
HGD
CO with gamma 1
CO with gamma = 10
Starting point
Min-max
150
100
50
100
150
200
0
-2
-2
X2
0
2
X1
-6
6
8
-8
(b)
Figure 9: HGD vs. CO for 100 iterations for g( 22) = f(a)) + CT1 f(12) where f(x)
log(1 e²) and e with different values of 7.
26

---

Under review as a conference paper at ICLR 2020
K.1.2 SGDA DIVERGES (c 10)
These plots show g when 10, so SGDA diverges, does CO with 7 0.1. Note that in this case, CO with 7 2 1 and HGD both require very few iterations (typically about 2) to reach the min-max.
Simyltaneous Gradient Descent/Ascent vs. Hamiltonian Gradient Descent
10:
X2
SEDA
Starting
n-max
-15
10
-5
5
10
15
(a)
SGDA
HGD
Starting point
Min-max
2000
000
1000
2000
15
10
-10
X2
-5
X1
5
10
10
15-15
(b)
Figure 10: SGDA vs. HGD for 150 iterations for ((x,,x2) f(x))+++++ cri - f(22) where f(x) = log(1 + et) and e 10. SGDA slowly circles away from the min-max, while HGD goes directly to the min-max.
27

---

Under review as a conference paper at ICLR 2020
Consensus Optimization for different values of gamma
10.0
5.0
2.5
with gamma
CO with garbma
0.0
CD with gariina = 10
Starting point
Min-max
-5.0
-7.
-10.0
10.0
-15
-5.0
-2.5
10.0
X1
(a)
.... CO with gamma 0.1
with gamma
CO with gamma 10
Starting point
Min-max
1000
750
500
250
g
250
500
750
1000
10.0
7.5
5.0
-10.0
-15.07.5-5.001
-2.
-2.5
X2
0.0
X1
2.5
5.0
-7.5
7.5
10.010.0
(b)
Figure 11: CO for 15 iterations with different values of r for (2)) f(x1) + cri02 ((2)
where f()) = log(1 + e²) and = 10. The 7 = 0.1 curve makes a cyclic pattern around the min-max, while the other curves go directly the min-max.
28

---

Under review as a conference paper at ICLR 2020
Consensus Optimization vs. Hamiltonian Gradient Descent
10.0
HGD
gamma
7.5
gamma
Starting point
Min-max
2.5
0.0
-25
-75
-10.0
-1.5
-5.0
10.0
(a)
HGD
CO with gamma
CO with gamma 10
Starting point
Min-max
600
400
200
400
600
0
-2
-2
X2
0
2
X1
-6
6
8
-8
(b)
Figure 12: HGD vs. CO for 15 iterations with different values of for g(x1, = f(x1) cr102
(#22 where f(x) = log(1 + e²) and
29

---

Under review as a conference paper at ICLR 2020
K.2
NONCONVEX NONCONEEX-AONCONGAE OBJECTIVE
The nonconvex-noneonccae objective we use is x2),, = F(I1) + C2 F(22) where F is defined as (16) in Appendix
3(x + 2)
for x 5 m
2
F(x)
30s x
for
2 < x S 2 for x >
(73)
008 x + 2x
We show plot of F in Figure 13
f(x)
f(x)
('()
10
Figure 13: Plot of nonconvex function (z) defined in (16) as well as its first and second derivatives
As in the convex-concave case, when c 3. SGDA converges, and when 10, SGDA diverges. Again, HGD and CO (for large enough ?) tend to converge faster when c is larger.
K.2.1
SGDA CONVERGES (c = 3)
These plots show when 3, so SGDA converges, as does CO with 7 = 0.1.
30

---

Under review as a conference paper at ICLR 2020
Siyyttnnouus Gradient Descent/Ascent Hamiltonian Gradient Descent
SGDA
HGD
7.5
Starting point
Min-max
5.0
0.0
-25
-5.0
-7.5
110.0
-1.5
-5.0
-2.5
0.0
2.5
5.0
7.5
10.0
X1
SGDA
HGD
Starting point
Min-max
300
200
100
200
300
10.0
7.5
5.0
2.5
-10.0
0.0
-500
-25
-2.5
X2
0.0
5,0
2.5
5.0
-7.5
7.5
10.010.0
(b)
Figure 14: SGDA vs. HGD for 300 iterations for g(01, x2) = F(z1) + cri - where F F(x)
is defined in (73) and 3. SGDA slowly circles towards the min-max, and HGD goes more directly to the min-max.
31

---

Under review as a conference paper at ICLR 2020
Consensus Optimization for different values of gamma
10.0
5.0
2.5
0.0
-5.0
CD with gamma = 0.1
gamma 1
gamma
-7.5
Starting point
Min-max
-10.0
10.0
-75
-25
10.0
X1
(a)
.... CO with gamma 0.1
with gamma
CO with gamma 10
Starting point
Min-max
300
200
100
g
100
200
300
10.0
7.5
5.0
-10.0
-15.0
-25
-2.5
X2
0.0
X1
2.5
5.0
-7.5
7.5
10:010.0
(b)
Figure 15: CO for 100 iterations with different values of for g( x2) F(m) cr F(22)
where F(x) is defined in (73) and e = 3. The ? = 0.1 curve slowly circles towards the min-max, while the other curves go more directly to the min-max.
32

---

Under review as a conference paper at ICLR 2020
Consensus Optimization vs. Hamiltonian Gradlent Descent
10.0
HGD
with gamma 1
gamma
Starting point
5.0
Min-max
2.5
0.0
-7.5
-10.0
-1.5
-5.0
10.0
X1
(a)
HGD
CO with gamma
CO with gamma = 10
Starting point
Min-max
200
100
50
50
100
150
0
-2
X2
0
2
X1
-6
6
8
-8
(b)
Figure 16: HGD vs. CO for 100 iterations for g( x2) F(a1) + Cr1 F(x2) where F(x) is
defined in (73) and 3 with different values 7.
33

---

Under review as a conference paper at ICLR 2020
K.2.2 SGDA DIVERGES (c 10)
These plots show g when so SGDA diverges, does CO with 7 0.1. Note that in this case, CO with 7 2 1 and HGD both require very few iterations (typically about 2) to reach the min-max.
nipyttanc Gradient Descent/Ascent vs. Hamiltonian Gradient Descent
HGD
7.2
Starting poin:
Min max
5.0
-7.5
-10.0
-5.0
2.5
(a)
SGDA
HGD
Starting point
Min-max
1000
750
500
250
250
500
750
10.0
7.5
5.0
2.5
-10.0
0.0
-5.0
-2.5 X2
-2.5
0.0
-500
X1
2.5
5.0
-7.5
7.5
10:010.0
(b)
Figure 17: SGDA vs. HGD for 150 iterations for g x2) F(m)) + c2122 F(x2) where F(x) defined in (73) and 10. SGDA slowly circles away from the min-max, while HGD goes directly to the min-max.
34

---

Under review as a conference paper at ICLR 2020
Consensus Optimization for different values of gamma
10.0
5.0
2.5
0.0
-5.0
CO with gemma 0.1
with gamma 1
with gemma
-75
Starting point
Min
-10.0
10.0
-15
-5.0
-2.
10.0
X1
(a)
.... CO with gamma 0.1
with gamma
CO with gamma 10
Starting point
Min-max
1000
750
500
250
g
250
500
- 750
1000
10.0
7.5
5.0
-10.0
-10.07.555.00
-2.
-2.5
X2
0.0
X1
2.5
5.0
-7.5
7.5
10.010.0
(b)
Figure 18: CO for 15 iterations with different values of 7 for g( .2) F(x1) crı F(22) where F(x) is defined in (73) and e = 10. The y = 0.1 curve makes an erratic cycle around the min-max. slowly diverging, while the other curves go directly to the min-max.
35

---

Under review as a conference paper at ICLR 2020
Consensus Optimization vs. Hamiltonian Gradient Descent
10.0
HGD
gamma
7.5
gamma
Starting point
Min-max
2.5
0.0
-2.
-75
-10.0
-1.5
-5.0
2.5
10.0
(a)
HGD
CO with gamma
CO with gamma 10 Starting point
Min-max
600
400
200
600
0
-2
X2
0
2
X1
-6
6
8
-8
(b)
Figure 19: HGD vs. CO for 15 iterations with different values of y for g(11, = F(x1) +c
F(12) where F(x)) is defined in (73) and
10.
36

---

Under review as a conference paper at ICLR 2020
K.3 CONVERGENCE OF HGD FOR NONCONVEX-NONCONTE OBJECTIVE WITH DIFFERENT SIZED BILINEAR TERMS
In this section, look the convergence of HGD for the objective as discussed in the previous section, namely g(11, = F(x1) + CC1 - F(22) where F is defined as in (16) in Appendix B
3(x 2)
for v
F(x)
cos x
for
S T
(74)
COS x + 2x π for x > g
In this case, we will vary c to show that HGD converges faster for higher c and will not converge for sufficiently low
c 0
c= 0.5
c 1
2
= 3
5
5.
Norm of X-x*
10
2
10
15
Number of iterations
Figure 20: Distance minmax for HGD iterates for different values of in the objective g(x1, 42)
F F(I1) + CT1 F(22) where F(x) is defined in (73)
37

---

Under review as a conference paper at ICLR 2020
70
=
c 0.5
c 1
Norm of gradient of g
60
c 2
c
c 5
50
c 10
40
30
10
0
10
15
20
Number of iterations
Figure 21: Gradient norm for HGD iterates for different values of the objective g( = F(I1) C21 F(22) where F(x) is defined in (73) Since all runs initialized at (5, 5), when is increased, the initial gradient norm also increases. Nonetheless, HGD still converges faster for the with higher
38


Reviews:
[{"review_id": "HkljIvR3tr", "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": "This paper shows that Hamiltonian gradient descent (HGD), which is gradient descent on the norm of the squared norm of the vector field, achieves linear convergence for a broader range of problems than bilinear and convex-strongly concave formulations. In particular, the authors show the result for convex-concave problems satisfying a “sufficiently bilinear” condition that is related to the PL conditions. Finally, the authors argue that consensus optimization (CO) can be viewed as a perturbation of HGD when the parameter choice is big enough. From this viewpoint they derive convergence rates for CO on the broader set of problems. This provides some further theoretical justification of the success of CO on large scale GAN problems.\n\nThe paper is presented in a clear manner, with the objectives and analysis techniques delineated in the main paper. This was helpful to get a sense of the main points before going through the appendix. The objective of the paper is to extend the problem settings for which there is last iterate min-max convergence rates, which now exist for bilinear, strongly convex-strongly concave, and convex-strongly concave problems. The authors achieve this by analyzing HGD and giving convergence rates for when a “sufficiently bilinear condition is satisfied”. The primary idea behind the proof techniques is to show that the objective (Hamiltonian) satisfies the PL condition. I found this to be an interesting approach.\n\nAs a result, the main question in evaluating this paper is on the significance of the result and the generality of the “sufficiently bilinear” condition. I tend to lean toward the result carrying some significance since it does extend the class of problems for which the convergence rates exists. However, the weakness is that the condition is opaque and it is not entirely clear how broad of class of problems this condition would apply to. I do acknowledge that the authors did a reasonable job of trying to clear this up in section 3.2 and section G of the appendix. It did still leave me wanting more with respect to the practical significance though. \n\nFinally, I found the connection to CO valuable. In particular, since this paper does not show large-scale experiments, the connection serves to provide some more theoretical evidence for they CO performs well in practice.\n\nPost Author Response: Thanks for the response. I agree with your perspective and think this paper should be accepted.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of 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 assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1evEoR6YH", "reviewer": "AnonReviewer3", "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": "\nSummary:\nThe paper, considers methods for solving smooth unconstrained min-max optimization problems.  In particular, the authors prove that the Hamiltonian Gradient Descent (HGD) algorithm converges with linear convergence rate to the min-max solution. One of the main contributions of this work is that the proposed analysis is focusing on last iterate convergence guarantees for the HGD. This result, as the authors claim can be particularly useful in the future for analyzing more general settings (nonconvex-nonconcave min-max problems).\nIn addition, two preliminary convergence theorems were provided for two extensions of HGD: (i) a stochastic variant of HGD and (ii)  Consensus Optimization Algorithm (CO) (by establishing connections of CO and HGD).\n\nMain Comments:\nThe paper is well written and the main contributions are clear. I believe that the idea of the paper is interesting and the convergence analysis seems correct, however i have some concerns regarding  the presentation and the combination of different assumptions used in the theory. \n\n1) I think definition 2.5 of Higher order Lipschitz is very strong assumption to have. What exactly means? Essentially the authors upper bounded any difficult term appear in the theorems. Is it possible to avoid having something so strong? Please elaborate.\n\n2) In assumption 3.1 is not clear what $L_H$ is. This quantity never mentioned before. Reading the Lemmas of Section 4 (Lemma 4.4) you can see that it is the smoothness parameter of function $H$. Thus, is not necessary to have it there (not important for the definition).\n\n3) What is the main difference on the combination of assumptions on Theorems 3.2, 3.2 and 3.4. Which one is stronger. Is there a reason for the existence of Theorem 3.3?\n\n4) All the results heavily depend on the PL condition. I think having this in mind, showing the convergence of Theorems 3.2-3.4 is somehow trivial. In particular, one can propose several combinations of assumptions in order for the function H to satisfy the PL condition. Can we avoid having the PL condition? The authors need to elaborate more on this.\n\n5) In Theorem 5.2, the term 1/sqrt(2) is missing from the final bound.\n\nMinor Suggestions:\nIn first paragraph of page 5 where the authors divide the existing literature into the three particular cases, I am suggesting to add the refereed papers inside each one of this cases (which papers assumed function g bilinear , which papers strongly convex-concave etc.)\n\nI understand that the main contribution of the work is the theoretical analysis of the proposed method but would like to see some numerical evaluation in the main paper. There are some preliminary results in the appendix but it will be useful for the reader if there are are some plots showing the benefit of the method in comparison with existing methods that guarantee convergence (which method is faster?). In the current experiments there is a comparison only with CO algorithm and SGDA.\n\nIn general i find the paper interesting, with nice ideas and I believe that will be appreciated from researchers that are interested on smooth games and their connections to machine learning applications. \n\nI suggest weak accept but I am open to reconsider in case that my above concerns are answered.\n\n**********after rebuttal********\nI would like to thank the authors for their reply and for the further clarification. \nI will keep my score the same but I highly encourage the authors to add some clarification related to my last comment on the globally bounded gradient. \nIn their response they mentioned that the analysis only requires that  H is smooth and that $\\|\\xi(x^{(0)})\\|$ is sufficient bound. This needs to be clear in the paper (add clear arguments and related references). \nIn addition, in their response they highlight the non-increasing nature of function H over the course of the algorithm which is important for their argument. Having this in mind note that the theoretical results on stochastic variant presented in the paper are wrong. In SGD,  function H does not necessarily decrease over the course of the algorithm. The authors either need to remove these results or restate them in a different way in order to satisfy the assumed conditions.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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 carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BkgIGYrAKS", "reviewer": "AnonReviewer1", "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* \n\nThis 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.\n\n*Decision*\n\nI 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.\n\nHowever, 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).\nOne way to improve to work would be to provide practical takeaways from the theory or to provide experiments in the main paper. \n\nRegarding the practical limitation of this work: \n- the sufficient bilinearity condition are hard to meet in practice. (even for convex-concave problems)\n- 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)\n\nHowever, 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.  \n\n*Questions* \n- What are the practical implication of your work ? for instance does it say anything on how to tune $\\gamma$ for CO ?\n\n*Remarks*\n- 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).\n- (Minor) $\\alpha$ 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 $\\alpha^2$ in Lemma 4.7. The same way for unit consistency I would use $L_H^2$ instead of $L_H$\n\n[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).  \n\n\n=== After rebuttal === \nI've read the authors's response. \nThe 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.  \nI however maintain my grade. \n\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 carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This provides a simple analysis of an existing algorithm for min-max optimization under some favorable assumptions.  The paper is clean and nice, though unfortunately lands just below borderline.

I urge the authors to continue their interesting work, and amongst other things address the reviewer comments, for example those on stochastic gradient descent. 
Decision: Reject