Last-iterate convergence rates for min-max optimization

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

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 [CBL06, Haz16]. This trick, which was originally developed by [Han57] and later emerged in the development of boosting [FS99], 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 $(\bar{x}_{1},\bar{x}_{2})$ 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 [GPAM+14]. 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 eq. 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}^{\top}Cx_{2}$ for some arbitrary matrix $C$. SGDA provably cycles in continuous time and diverges in discrete time (see for example [DISZ18, MGN18]). In fact, the full range of Follow-The-Regularized-Leader (FTRL) algorithms provably do not converge in zero-sum games with interior equilibria [MPP18]. 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 [MLZ+19, MNG17, DP18, BRM+18, LFB+19, MJS19]. 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 [Tse95, LS19, DH19, MOP19]. 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-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 [MNG17, BRM+18]. 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 [KNS16] to show that a stochastic version of HGD will have a last-iterate convergence rate of $O(1/\sqrt{k})$ in the “sufficiently bilinear” setting. On the practical side, while vanilla HGD has issues training GANs in practice, [MNG17] 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.

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.

Background

In this section, we discuss some key definitions and notation. We will use $\left|\left|\cdot\right|\right|$ to denote the Euclidean norm for vectors or the operator norm for matrices or tensors. For a symmetric matrix $A$, we will use $\lambda_{\min}(A)$ and $\lambda_{\max}(A)$ to denote the smallest and largest eigenvalues of $A$. For a general real matrix $A$, $\sigma_{\min}(A)$ and $\sigma_{\max}(A)$ denote the smallest and largest singular values of $A$.

Note that unlike the Hessian in standard optimization, $J$ is not symmetric, due to the negative sign in $\xi$. When clear from the context, we often omit dependence on $x$ when writing $\xi,J,g,\mathcal{H},$ and other functions. Note that $\xi,J$, and $\mathcal{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:

2 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:

All critical points of the objective $g$ are global min-maxes (i.e. they satisfy eq. 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 $\epsilon$-approximate critical points, defined as follows:

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 2.6. We discuss notions of second-order convergence and ways to adapt our results to the general nonconvex setting in Appendix A.

3 Related work

Several recent papers have given asymptotic or local convergence results for min-max problems. [MLZ+19] 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.

Compared to the work on asymptotic convergence, the work on global non-asymptotic last-iterate convergence rates has been limited to much more restrictive settings. A classic result by [Roc76] shows a linear convergence rate for the proximal point method in the bilinear and strongly convex-strongly concave cases. Another classic result, by [Tse95], shows a linear convergence rate for the extragradient algorithm in the bilinear case. [LS19] 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. [MOP19] 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, [DH19] show that SGDA achieves a linear convergence rate for a convex-strongly concave setting with a full column rank linear interaction term.Specifically, they assume $g(x_{1},x_{2})=f(x_{1})+x_{2}^{T}Ax_{1}-h(x_{2})$, 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 of [DH19] for the convex-strongly concave setting in Appendix D.

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.

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 $\mathcal{H}$ that we refer to as the Hamiltonian, following the terminology of [BRM+18].We note that the function $\mathcal{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 $\mathcal{H}$. If we let \xi:=\big{(}\frac{\partial g}{\partial x_{1}},-\frac{\partial g}{\partial x_{2}}\big{)} be the vector of (appropriately-signed) partial derivatives, then the Hamiltonian is:

Since a critical point occurs when $\xi(x)=0$, we can find a (approximate) critical point by finding a (approximate) minimizer of $\mathcal{H}$. Moreover, under 2.6, finding a critical point is equivalent to finding a saddle point. This motivates the HGD update procedure on $x^{(k)}=(x_{1}^{(k)},x_{2}^{(k)})$ with step-size $\eta>0$:

HGD has been mentioned in [MNG17, BRM+18], and it strongly resembles the Consensus Optimization (CO) approach of [MNG17].

The HGD update requires a Hessian-vector product because $\nabla\mathcal{H}=\xi^{\top}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 [Pea94]. 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 [MNG17, BRM+18, ADLH19, LFB+19, MJS19].

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 [Tse95, LS19, DH19, MOP19]. 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.

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

Assume $g$ is $(L_{1},L_{2},L_{3})$-Lipschitz and let $L_{\mathcal{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.

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.

Finally, we show our main result, which requires smoothness in both players and a large, well-conditioned cross-derivative.

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}^{\top}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 eq. 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 [AH18, ASS17]. 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.

2 Explanation of “sufficiently bilinear” condition

In this section, we explain the “sufficiently bilinear” condition eq. 3. Suppose our objective is $g(x_{1},x_{2})=\hat{g}(x_{1},x_{2})+cx_{1}^{\top}x_{2}$ for a smooth function $\hat{g}$. Then for sufficiently large values of $c$ (i.e. $g$ has a large enough bilinear term), we see that $g$ satisfies eq. 3. To see this, note that if we have $\gamma^{4}>4L^{2}\Gamma^{2}$, then condition eq. 3 holds. Let $\gamma^{\prime}$ and $\Gamma^{\prime}$ be lower and upper bounds on the singular values of $\nabla^{2}_{x_{1}x_{2}}\hat{g}$. Then it suffices to have $(\gamma^{\prime}+c)^{4}>4L^{2}(\Gamma^{\prime}+c)^{2}$, which is true for $c=3\max\{L,\Gamma^{\prime}\}$ (i.e. $c=O(L)$ suffices).

Theorem 3.4 and condition eq. 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})=\hat{g}(x_{1},x_{2})+cx_{1}^{\top}x_{2}$ for a smooth function $\hat{g}$, we will get linear convergence if $\|\nabla^{2}_{x_{1}x_{2}}\hat{g}\|\leq\delta L$ and $c\geq 3(1+\delta)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 eq. 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.

Let $g(x_{1},x_{2})=f(x_{1})+cx_{1}^{\top}x_{2}-h(x_{2})$ where $f$ and $h$ are $L$-smooth. Moreover, assume that $\nabla^{2}f(x_{1})$ and $\nabla^{2}h(x_{2})$ each have a 0 eigenvalue for some $x_{1}$ and $x_{2}$. If eq. 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 $\xi(x)=0$) are global minima of $\mathcal{H}=\frac{1}{2}\left|\left|\xi\right|\right|^{2}$. On the other hand, there is no guarantee that $\mathcal{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, $\mathcal{H}$ satisfies the PL condition, which allows HGD to have linear convergence. Proving this requires proving properties about the singular values of $J\equiv\nabla\xi$.

We begin by recalling the definition of the PL condition.

The PL condition is well-known to be the weakest condition necessary to obtain linear convergence rate for gradient methods; see for example [KNS16]. We will show that $\mathcal{H}$ satisfies the PL condition, which allows us to use the following classic theorem.

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

All of our results use 3.1, so we are guaranteed that $g$ has a critical point. This implies that the global minimum of $\mathcal{H}$ is 0, which allows us to prove the following key lemma:

Assume we have a twice differentiable $g(x_{1},x_{2})$ with associated $\xi,\mathcal{H},J$. Let $\alpha>0$. If $JJ^{\top}\succeq\alpha I$ for every $x$, then $\mathcal{H}$ satisfies the PL condition with parameter $\alpha$.

Consider the squared norm of the gradient of the Hamiltonian:

The proof is finished by noting that $\mathcal{H}(x)=0$ when $x$ is a critical point. ∎

To use Theorem 4.2, we will also need to show that $\mathcal{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.

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 $\mathcal{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^{\top}$, which we achieve with the following linear algebra lemmas. We provide their proofs in Appendix H.

Let $\textstyle H=\begin{pmatrix}M_{1}&B\\ -B^{\top}&-M_{2}\end{pmatrix}$ and let $\epsilon\geq 0$. If $M_{1}\succ\epsilon I$ and $M_{2}\prec-\epsilon I$, then for all eigenvalues $\lambda$ of $HH^{\top}$, we have $\lambda>\epsilon^{2}$.

Let $H=\begin{pmatrix}A&C\\ -C^{\top}&0\end{pmatrix}$, where C is square and full rank. Then if $\lambda$ is an eigenvalue of $HH^{\top}$, then we must have $\lambda\geq\frac{\sigma_{\min}^{4}(C)}{2\sigma^{2}_{\min}(C)+\left|\left|A\right|\right|^{2}}$.

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 $\mathcal{H}$ for the various settings of our theorems:

Since $\mathcal{H}$ satisfies the PL condition with parameter $\alpha$ and $\mathcal{H}$ is $L_{\mathcal{H}}$-smooth, we know by Theorem 4.2 that gradient descent on $\mathcal{H}$ with step-size $1/L_{\mathcal{H}}$ converges at a rate of $\mathcal{H}(x^{(k)})\leq(1-\frac{\alpha}{L_{\mathcal{H}}})^{k}\mathcal{H}(x^{(0)})$. Substituting in for $\mathcal{H}$ gives the lemma. ∎

It remains to show that $\mathcal{H}$ satisfies the PL condition in the settings of Theorems 3.2, 3.3 and 3.4. First, we show the result for the strongly convex-strongly concave setting of Theorem 3.2.

Let $g$ be $c$-strongly convex in $x_{1}$ and $c$-strongly concave in $x_{2}$. Then $\mathcal{H}$ satisfies the PL condition with parameter $\alpha=c^{2}$.

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}=\nabla_{x_{1}x_{1}}^{2}g\succ cI$ and $M_{2}=-\nabla_{x_{2}x_{2}}^{2}g\succ cI$. Then the magnitude of the eigenvalues of $J$ is at least $c$. Thus, $JJ^{\top}\succeq c^{2}I$, so by Lemma 4.3, $\mathcal{H}$ satisfies the PL condition with parameter $c^{2}$. ∎

Next, we show that $\mathcal{H}$ satisfies the PL condition for the nonconvex-linear setting of Theorem 3.3. We prove this lemma in Section H.4 by using Lemma 4.6.

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

Then $\mathcal{H}$ satisfies the PL condition with parameter $\alpha=\frac{(\gamma^{2}+\rho^{2})(\gamma^{2}+\mu^{2})-4L^{2}\Gamma^{2}}{2\gamma^{2}+\rho^{2}+\mu^{2}}$.

Combining Lemmas 4.8, 4.9 and 4.10 with Lemma 4.7 yields Theorems 3.2, 3.3 and 3.4.

Extensions of HGD results

Our results above also imply rates for stochastic HGD, where the gradient $\nabla\mathcal{H}$ in eq. 2, is replaced by a stochastic estimator $v$ of $\nabla\mathcal{H}$ such that $\operatorname{E}\left[v\right]=\nabla\mathcal{H}$. Since we show that $\mathcal{H}$ satisfies the PL condition with parameter $\alpha$ in different settings, we can use Theorem 4 in [KNS16] to show that stochastic HGD converges at a $O(1/\sqrt{k})$ rate in the settings of Theorems 3.2, 3.3 and 3.4, including the “sufficiently bilinear” setting. We prove Theorem 5.1 in Appendix I.

Let 3.1 hold and suppose $\mathcal{H}$ satisfies the PL condition with parameter $\alpha$. Suppose we use the update $x^{(k+1)}=x^{(k)}-\eta_{k}v(x^{(k)})$, where $v$ is a stochastic estimate of $\nabla\mathcal{H}$ such that $\textup{E}[v]=\nabla\mathcal{H}$ and $\textup{E}[\|v(x^{(k)})\|^{2}]\leq C^{2}$ for all $x^{(k)}$. Then if we use $\eta_{k}=\frac{2k+1}{2\alpha(k+1)^{2}}$, we have the following convergence rate: $\textup{E}[\|\xi(x^{(k)})\|]\leq\sqrt{\frac{L_{\mathcal{H}}C^{2}}{k\alpha^{2}}}$.

The Consensus Optimization (CO) algorithm of [MNG17] is as follows:

where $\gamma>0$. This is essentially a weighted combination of SGDA and HGD. [MNG17] 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 $\gamma=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, 3.3 and 3.4 provided that $\gamma$ 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, [LS19] 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.

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

References

Appendix 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 $\nabla^{2}f$ is approximately positive definite. Likewise, a common goal in nonconvex min-max optimization is to find approximate critical points where an analogous second-order condition holds, namely that $\nabla_{x_{1}x_{1}}^{2}g(x)$ is approximately positive definite and $\nabla_{x_{2}x_{2}}^{2}g(x)$ is approximately negative definite. Critical points where this second-order condition holds are called local min-maxes. When 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 [MNG17, DP18, BRM+18, LFB+19, MJS19]. 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.

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 [BRM+18, LFB+19]. In particular, we consider modifying HGD so that there is some scalar $\alpha$ in front of the $\nabla\mathcal{H}$ term as follows:

We now present two ways to choose $\alpha$. Our first method is inspired by the Simplectic Gradient Adjustment algorithm of [BRM+18], which is as follows:

where $A$ is the antisymmetric part of $J$ and $\lambda=\textup{sgn}\left(\left\langle\xi,J\right\rangle\left\langle A^{\top}\xi,J\right\rangle\right)$. [BRM+18] show that $\lambda$ is positive when in a strictly convex-strictly concave region and negative in a strictly concave-strictly convex region. Thus, if we choose $\alpha=\lambda=\textup{sgn}\left(\left\langle\xi,J\right\rangle\left\langle A^{\top}\xi,J\right\rangle\right)$, 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 $\mathcal{H}$ in the first case and gradient ascent on $\mathcal{H}$ in the second case.

Another way to choose $\alpha$ involves using an approximate eigenvalue computation on $\nabla^{2}_{x_{1}x_{1}}g$ and $\nabla^{2}_{x_{2}x_{2}}g$ to detect whether $\nabla^{2}_{x_{1}x_{1}}g$ is positive semidefinite and $\nabla^{2}_{x_{2}x_{2}}g$ is negative semidefinite (which would mean we are in a convex-concave region). We set $\alpha=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.

Appendix 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

where $z_{EMA}^{(0)}=z^{(0)}$ and $\beta<1$. A typical value for $\beta$ is $0.999$. [YFW+19] and [GBVLJ19] show that uniform and EMA schemes can improve GAN performance on a variety of datasets. [MGN18] and [KALL18] use EMA to evaluate the GAN models they train, showing the effectiveness of EMA in practice.

In terms of theoretical results, [Kro19] studies saddle point problems of the form $\min_{x_{1}}\max_{x_{2}}f(x_{1})+g(x_{1})+\langle Kx_{1},x_{2}\rangle-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. [ALLW18] 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.

Appendix C Proof of linear convergence rate under PL condition

Here we present a classic proof of Theorem 4.2.

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. ∎

Appendix D Comparison of Theorem 3.4 to [DH19]

Their rate uses the potential function $P_{t}=\lambda a_{t}+b_{t}$, where we have:

where $(x_{1}^{*},x_{2}^{*})$ is the min-max for the objective. Their rate (Theorem 3.1 in [DH19]) is

for some constant $c>0$. To translate this rate into bounds on $\left|\left|\xi\right|\right|$, we can use the smoothness of $g$ in both of its arguments to note that $\left|\left|\frac{\partial g}{\partial x_{1}}(x_{1},x_{2})\right|\right|=\left|\left|\frac{\partial g}{\partial x_{1}}(x_{1},x_{2})-\frac{\partial g}{\partial x_{1}}(x^{*}_{1},x^{*}_{2})\right|\right|\leq L\left|\left|x_{1}^{(k)}-x_{1}^{*}\right|\right|$ and likewise for $x_{2}$. So the rate on $P_{k}$ translates into a rate on $\left|\left|\xi\right|\right|$ with some additional factor in front.

Their rate and our rate are incomparable – neither is strictly better. For instance when $\gamma=\Gamma$ is much larger than all other quantities, their rates simplify to $\left(1-O\left(\frac{\mu^{3}}{L^{3}}\right)\right)^{k}$, while ours go to $\left(1-O\left(\frac{\gamma^{2}}{L_{\mathcal{H}}}\right)\right)^{k/2}$. While our convergence rate requires the sufficiently bilinear condition eq. 3 to hold, we do not require convexity in $x_{1}$ or concavity in $x_{2}$. Moreover, we allow $\nabla_{x_{1}x_{2}}^{2}g$ to change as long as the bounds on the singular values hold whereas [DH19] require $\nabla_{x_{1}x_{2}}^{2}g$ to be a fixed matrix.

Appendix E Nonconvex-nonconcave setting where 2.6 and the conditions for Theorem 3.4 hold

In this section we give a concrete example of a nonconvex-nonconcave setting where 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:

The first and second derivatives of $F$ are as follows:

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}^{\top}x_{2}-F(x_{2})$. Note that $L=3$ because $F^{\prime\prime}(x)\leq 3$ for all $x$. Also, $\gamma=\Gamma=4$ since $\nabla^{2}_{x_{1}x_{2}}g=4I$.

Next, we show that $g$ satisfies condition eq. 3. Condition eq. 3 requires $\gamma^{4}>4L^{2}\Gamma^{2}$ for $g$. We see that this holds because $\gamma^{4}=4^{4}=256$ and $4L\Gamma^{2}=4*3*4^{2}=192$.

Therefore, the assumptions of Theorem 3.4 are satisfied.

We can also show that this objective satisfies 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(\cdot,0)$ and $g(0,\cdot)$ 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. Let us look at the derivatives of $g$ with respect to $x_{1}$ and $x_{2}$:

Observe that if $x_{1}\in[-\frac{\pi}{2},\frac{\pi}{2}]$ then critical points of $g$ must satisfy $3\sin x_{1}+4x_{2}=0$, which implies that $x_{2}\in[-\frac{3}{4},\frac{3}{4}]$. Likewise, if $x_{2}\in[-\frac{\pi}{2},\frac{\pi}{2}]$, then critical points of $g$ must have $x_{1}\in[-\frac{3}{4},\frac{3}{4}]$. We show that this implies that $g$ only has critical points where $x_{1}$ and $x_{2}$ are both in the range $[-\frac{\pi}{2},\frac{\pi}{2}]$.

Suppose $g$ had a critical point such that $x_{1}\leq-\frac{\pi}{2}$. Then this critical point must satisfy $x_{2}=\frac{3}{4}$. But from our observation above, if a critical point has $x_{2}=\frac{3}{4}$, then $x_{1}$ must lie in $[-\frac{3}{4},\frac{3}{4}]$, which contradicts $x_{1}\leq-\frac{\pi}{2}$.

Next, suppose $g$ had a critical point such that $x_{1}>\frac{\pi}{2}$. Then this critical point must satisfy $x_{2}=-\frac{1}{4}(\sin x_{1}+2)$, which implies that $x_{2}\in[-\frac{3}{4},\frac{3}{4}]$. But then by the observation above, $x_{1}$ must lie in $[-\frac{3}{4},\frac{3}{4}]$, which contradicts $x_{1}>\frac{\pi}{2}$.

From this we see that any critical point of $g$ must have $x_{1}\in[-\frac{\pi}{2},\frac{\pi}{2}]$. We can make analogous arguments to show that any critical point of $g$ must have $x_{2}\in[-\frac{\pi}{2},\frac{\pi}{2}]$.

From this, we can conclude that all critical points of $g$ must satisfy the following:

That is, for all critical points of $g$, $x_{1}$ must be a fixed point of $h_{1}(x)=\frac{3}{4}\sin\left(-\frac{3}{4}\sin x\right)$ and $x_{2}$ must be a fixed point of $h_{2}(x)=-\frac{3}{4}\sin\left(\frac{3}{4}\sin x\right)$. Since $|h_{1}^{\prime}(x)|<1$ and $|h_{2}^{\prime}(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).

Appendix F Proof of Lemma 3.5

To prove Lemma 3.5, we will use the following lemma:

Let $g(x_{1},x_{2})=f(x_{1})+cx_{1}^{\top}x_{2}-h(x_{2})$ where $f$ and $h$ are $L$-smooth. Then if $c>L$, $g$ has a unique critical point.

Note that in our setting, $\gamma=\Gamma=c$. Next, observe that if $\nabla^{2}f(x_{1})$ and $\nabla^{2}h(x_{2})$ each have a 0 eigenvalue for some $x_{1}$ and $x_{2}$, condition eq. 3 reduces to:

Then by Lemma F.1, we see that $g$ must have a unique critical point. ∎

Suppose our objective is $g(x_{1},x_{2})=f(x_{1})+cx_{1}^{\top}x_{2}-h(x_{2})$ where $f$ and $h$ are both $L$-smooth convex functions. Critical points of $g$ must satisfy the following:

In other words, $x_{2}$ must be a fixed point of $F(z)=-\frac{1}{c}\nabla f(\frac{1}{c}\nabla 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.

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 eq. 3 is thus a sufficient condition for the existence of a unique critical point for the class of objectives above. ∎

Appendix G Applications

In this section, we discuss how our results can be applied to various settings. One simple setting is the Dirac-GAN from [MGN18], where $g(x_{1},x_{2})=\min_{x_{1}}\max_{x_{2}}f(x_{1}^{\top}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 [BRM+18]. 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 [MGN18] 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.

Appendix 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.2 Proof of Lemma 4.5

Note that $HH^{\top}=\begin{pmatrix}M_{1}^{2}+BB^{T}&-M_{1}B-BM_{2}\\ -(M_{1}B+BM_{2})^{T}&M_{2}^{2}+B^{T}B\end{pmatrix}=\begin{pmatrix}M_{1}&-B\\ -B^{T}&M_{2}\end{pmatrix}^{2}$.

Now let $Z=\begin{pmatrix}M_{1}&-B\\ -B^{T}&M_{2}\end{pmatrix}$. It suffices to show that for any eigenvalue $\delta$ of $Z$, $|\delta|\leq\epsilon$. For the sake of contradiction, let $v$ be an eigenvalue of $Z$ with eigenvalue $\delta$ such that $\left|\delta\right|\leq\epsilon$. Let $v=\begin{pmatrix}v_{1}\\ v_{2}\end{pmatrix}$. Since $Zv=\delta v$ for $\left|\delta\right|\leq\epsilon$ and $M_{1}\succ\epsilon I$ and $M_{2}\prec-\epsilon I$, we must have $v_{1}\neq 0$ and $v_{2}\neq 0$. Then we have:

Let $\hat{M}_{1}=M_{1}-\delta I$ and let $\hat{M}_{2}=M_{2}-\delta I$. Note that $\hat{M}_{1}\succ 0$ and $\hat{M}_{2}\prec 0$. Then we can write $v_{1}=\hat{M}_{1}^{-1}Bv_{2}$. Further, we can substitute into eq. 38 to get

In other words, $v_{2}$ is an eigenvector of $-\hat{M}_{2}^{-1}B^{\top}\hat{M}_{1}^{-1}B$ with eigenvalue $-1$. Let $A=-\hat{M}_{2}^{-1}$ and $T=B^{\top}\hat{M}_{1}^{-1}B$. Note that $A$ is positive definite and $T$ is PSD. Then we have:

Since $A^{1/2}TA^{1/2}$ is PSD, and $AT$ is similar to $A^{1/2}TA^{1/2}$, we must have that all of the eigenvalues of $AT$ are nonnegative. This contradicts that $v_{2}$ is an eigenvector of $AT$ with eigenvalue $-1$.

Thus, all eigenvalues of $Z$ must have magnitude greater than $\epsilon$. ∎

H.3 Proof of Lemma 4.6

Suppose $\lambda$ is an eigenvalue of $HH^{\top}$ with eigenvector $v=\begin{pmatrix}v_{1}\\ v_{2}\end{pmatrix}$. WLOG, suppose $\lambda<\sigma_{\min}^{2}(C)$. Since $v$ is an eigenvector, we have:

Since $\lambda<\sigma_{\min}^{2}(C)$, we have that $C^{\top}C-\lambda I$ is invertible, so we can write $v_{2}=(C^{\top}C-\lambda I)^{-1}C^{\top}Av_{1}$ from the eq. 44. Plugging this into eq. 43 gives:

Write the SVD of $C$ as $C=U\Sigma V^{\top}$. Then we have:

where the second line follows because $VV^{\top}=I$ when $C$ is full rank and where $D$ is a diagonal matrix such that $D_{ii}=\frac{\sigma_{i}^{2}(C)}{\sigma_{i}^{2}(C)-\lambda}$.

Let $M=I-D$, so $M$ is diagonal with $M_{ii}=\frac{-\lambda}{\sigma_{i}^{2}(C)-\lambda}$. Then eq. 46 becomes:

This means $T=AMA+CC^{\top}-\lambda I$ has a 0 eigenvalue. A simple lower bound for the eigenvalues of $T$ is

We will show that if $\lambda<\delta$, where $\delta=\sigma^{2}_{\min}(C)+\frac{\left|\left|A\right|\right|^{2}}{2}-\sqrt{(\sigma^{2}_{\min}+\frac{\left|\left|A\right|\right|^{2}}{2})^{2}-\sigma^{4}_{\min}}$, then $\lambda_{\min}(T)>0$, which is a contradiction. It suffices to show the following inequality:

eq. 57 has zeros at the following values:

Since eq. 57 is a convex parabola, if $\lambda$ is less than both zeros, we will have proved eq. 57. This is clearly true if $\lambda<\delta$.

As a last step, we can give a slightly nicer form of $\delta$, using Lemma H.1. Letting $x=\sigma_{\min}^{2}(C)+\frac{\left|\left|A\right|\right|^{2}}{2}$ and $c=\sigma_{\min}^{4}(C)$, we have $\delta>\frac{\sigma_{\min}^{4}(C)}{2\sigma^{2}_{\min}(C)+\left|\left|A\right|\right|^{2}}$. So to reiterate, if $\lambda<\frac{\sigma_{\min}^{4}(C)}{2\sigma^{2}_{\min}(C)+\left|\left|A\right|\right|^{2}}<\delta$, then eq. 57 holds, so $T\succ 0$, which contradicts eq. 52. ∎

For $x\in(0,1)$ and $c\in(0,x^{2})$, we have:

H.4 Proof of Lemma 4.9

H.5 Proof of Lemma 4.10

To prove Lemma 4.10, we use the following lemma:

Let $H=\begin{pmatrix}A&C\\ -C^{\top}&-B\end{pmatrix}$, where $C$ is square and full rank. Moreover, let $c=(\sigma_{\min}^{2}(C)+\lambda_{\min}(A^{2}))(\lambda_{\min}(B^{2})+\sigma_{\min}^{2}(C))-\sigma_{\max}^{2}(C)(\left|\left|A\right|\right|+\left|\left|B\right|\right|)^{2}$ and assume $c>0$. Then if $\lambda$ is an eigenvalue of $HH^{\top}=\begin{pmatrix}A^{2}+CC^{\top}&-AC-CB\\ -C^{\top}A-BC^{\top}&B^{2}+C^{\top}C\end{pmatrix}$, we must have

This proof resembles that of Lemma 4.6. Let $v=\begin{pmatrix}v_{1}\\ v_{2}\end{pmatrix}$ be an eigenvector of $HH^{\top}$ with eigenvalue $\lambda$. Expanding $HH^{\top}v=\lambda v$, we have:

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

Letting $b=2\sigma_{\min}^{2}(C)+\lambda_{\min}(A^{2})+\lambda_{\min}(B^{2})$, we can solve for the zeros of the above 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 $\lambda<\delta=\frac{b-\sqrt{b^{2}-4c}}{2}$, we get a contradiction. Using Lemma H.1, we see that $\delta>\frac{c}{b}$. So we’ve proven that $\lambda<\frac{c}{b}$ gives a contradiction, so we must have $\lambda\geq\frac{c}{b}$, i.e.

Using the bounds on the singular values of $C(x_{1},x_{2})$, we have that $JJ^{\top}\succeq\frac{(\gamma^{2}+\lambda_{\min}(A^{2}))(\gamma^{2}+\mu^{2})-4L^{2}\Gamma^{2}}{2\gamma^{2}+\lambda_{\min}(A^{2})+\mu^{2}}I$, so by Lemma 4.3, $\mathcal{H}$ satisfies the PL condition with parameter $\frac{(\gamma^{2}+\lambda_{\min}(A^{2}))(\gamma^{2}+\mu^{2})-4L^{2}\Gamma^{2}}{2\gamma^{2}+\lambda_{\min}(A^{2})+\mu^{2}}$. ∎

Appendix I Proof of Theorem 5.1

In this section, we prove Theorem 5.1. The proof leverages the following theorem from [KNS16].The actual theorem in [KNS16] is stated in a slightly different way, but it is equivalent to our presentation.

Assume that $f$ is $L$-smooth, has a non-empty solution set $\mathcal{X}^{*}$, and satisfies the PL condition with parameter $\alpha$. Let $v$ be a stochastic estimate of $\nabla f$ such that $E[v]=\nabla f$. Assume $E[\|v(x^{(k)})\|^{2}]\leq C^{2}$ for all $x^{(k)}$ and some $C$. If we use the SGD update $x^{(k+1)}=x^{(k)}-\eta_{k}v(x^{(k)})$ with $\eta_{k}=\frac{2k+1}{2\alpha(k+1)^{2}}$, then, we get a convergence rate of

If instead we use a constant $\eta_{k}=\eta<\frac{1}{2\alpha}$, then we obtain a linear convergence rate up to a solution level that is proportional to $\eta$,

If $\mathcal{H}$ satisfies the PL condition with parameter $\alpha$, then we can apply Theorem I.1 to the stochastic variant of HGD. since $\mathcal{H}^{*}=0$, we get

The theorem follows from Jensen’s inequality, which implies that $\textup{E}\left[\|\xi(x^{(k)})\|\right]\leq\sqrt{\textup{E}\left[\|\xi(x^{(k)})\|^{2}\right]}$. ∎

Appendix 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:

Let $x^{(k+1)}=x^{(k)}-\eta\nabla\mathcal{H}(x^{(k)})+\eta_{v}v^{(k)}$ where $v^{(k)}$ is some arbitrary vector such that $\left|\left|v^{(k)}\right|\right|=\left|\left|\xi(x^{(k)})\right|\right|$. Let $g$ be $L_{g}$-smooth and suppose $\mathcal{H}$ satisfies the PL condition with parameter $\alpha$. Let $\eta=\frac{1}{L_{\mathcal{H}}}$ and let $\eta_{v}=\frac{\alpha}{4L_{\mathcal{H}}L_{g}}$. Then we get the following convergence:

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

Note that the CO update eq. 5 with $\gamma=\frac{4L_{g}}{\alpha}$ is exactly the update in Theorem J.1 with $v^{(k)}=-\xi(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.

Let $x^{(k+1/2)}=x^{(k)}-\eta\nabla\mathcal{H}(x^{(k)})$, so $x^{(k+1)}=x^{(k+1/2)}+\eta_{v}v^{(k)}$. From eq. 11 in the proof of Theorem 4.2 with $\eta=\frac{1}{L_{\mathcal{H}}}$, we get

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

Using the above result and $\left|\left|v^{(k)}\right|\right|=\left|\left|\xi(x^{(k)})\right|\right|$, we get:

Setting $\eta_{v}=\frac{\alpha}{4L_{\mathcal{H}}L_{g}}$ 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 $\left|\left|\nabla^{2}_{x_{1}x_{2}}g(x_{1},x_{2})\right|\right|\leq L_{c}$ for all $x_{1},x_{2}$, then $g$ will be $L+L_{c}$ smooth.

Appendix 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, $\gamma$ refers to the $\gamma$ parameter in the CO algorithm. All of our experiments are initialized at $(5,5)$. The step-size $\eta$ for HGD and SGDA is always $0.01$, while the step-size $\eta$ for CO with $\gamma=\{0.1,1,10\}$ is $\{0.1,0.01,0.001\}$ respectively to account for the fact that increasing $\gamma$ increases the effective step-size, so the $\eta$ 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 $\gamma$ will not converge if there is a large bilinear term, while CO with high $\gamma$ and HGD all converge for small and large bilinear terms. When the bilinear term is large, CO with high $\gamma$ 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.

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.

When $c=3$, SGDA converges, and when $c=10$, SGDA diverges. We note that HGD and CO (for large enough $\gamma$) tend to converge faster when $c$ is larger.

These plots show $g$ when $c=3$, so SGDA converges, as does CO with $\gamma=0.1$.

K.1.2 SGDA diverges (c=10𝑐10c=10)

These plots show $g$ when $c=10$, so SGDA diverges, as does CO with $\gamma=0.1$. Note that in this case, CO with $\gamma\geq 1$ and HGD both require very few iterations (typically about 2) to reach the min-max.

K.2 Nonconvex-nonconcave objective

The nonconvex-nonconcave objective we use is $g(x_{1},x_{2})=F(x_{1})+cx_{1}x_{2}-F(x_{2})$ where $F$ is defined as in eq. 16 in Appendix E.

As in the convex-concave case, when $c=3$, SGDA converges, and when $c=10$, SGDA diverges. Again, HGD and CO (for large enough $\gamma$) tend to converge faster when $c$ is larger.

These plots show $g$ when $c=3$, so SGDA converges, as does CO with $\gamma=0.1$.

K.2.2 SGDA diverges (c=10𝑐10c=10)

These plots show $g$ when $c=10$, so SGDA diverges, as does CO with $\gamma=0.1$. Note that in this case, CO with $\gamma\geq 1$ and HGD both require very few iterations (typically about 2) to reach the min-max.

K.3 Convergence of HGD for nonconvex-nonconvex objective with different-sized bilinear terms

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 eq. 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$.