Global Convergence to the Equilibrium of GANs using Variational Inequalities

Introduction

When minimizing $f(x)$ over $x\in\mathcal{X}$, it is known that $f$ decreases fastest if $x$ moves in the direction $-\nabla f(x)$. In addition, any direction orthogonal to $-\nabla f(x)$ will leave $f(x)$ unchanged. In this work, we show that these orthogonal directions that are ignored by gradient descent can be critical in equilibrium problems, which are central to game theory. If each player $i$ in a game updates with $x^{(i)}\leftarrow x^{(i)}-\rho\nabla_{x^{(i)}}f^{(i)}(x)$, $x=[x^{(1)};x^{(2)};\ldots]^{\top}$ can follow a cyclical trajectory, similar to a person riding a merry-go-round (see Figure 1). This toy scenario actually perfectly reflects an aspect of training for a particular machine learning model mentioned below, and is depicted more technically later on in Figure 2. To arrive at the equilibrium point, a person riding the merry-go-round should walk perpendicularly to their direction of travel, taking them directly to the center.

Equilibrium problems have drawn heightened attention in machine learning due to the emergence of the Generative Adversarial Network (GAN) . GANs have served a variety of applications including generating novel images , simulating particle physics , and imitating expert policies in reinforcement learning . Despite this plethora of successes, GAN training remains heuristic.

Deep learning has benefited from an understanding of simpler, more fundamental techniques. For example, multinomial logistic regression formulates learning a multiclass classifier as minimizing the cross-entropy of a log-linear model where class probabilities are recovered via a softmax. The minimization problem is convex and is solved efficiently with guarantees using stochastic gradient descent (SGD). Unsurprisingly, the majority of deep classifiers incorporate a softmax at the final layer, minimize a cross-entropy loss, and train with a variant of SGD. This progression from logistic regression to classification with deep neural nets is not mirrored in GANs. In contrast, from their inception, GANs were architected with deep nets. Only recently has the Wasserstein Linear-Quadratic GAN (LQ-GAN) been proposed as a minimal model for understanding GANs.

In this work, we analyze the convergence of several GAN training algorithms in the LQ-GAN setting. We survey several candidate theories for understanding convergence in GANs, naturally leading us to select Variational Inequalities, an intuitive generalization of the widely relied-upon theories from Convex Optimization. According to our analyses, none of the current GAN training algorithms is globally convergent in this setting. We propose a new technique, Crossing-the-Curl, for training GANs that converges with high probability in the N-dimensional (N-d) LQ-GAN setting.

This work makes the following contributions (proofs can be found in the supplementary material):

The first global convergence analysis of several GAN training methods for the N-d LQ-GAN,

Crossing-the-Curl, the first technique with $\mathcal{O}(N/k)$ stochastic convergence for the N-d LQ-GAN,

An empirical demonstration of Crossing-the-Curl in the multivariate LQ-GAN setting as well as some common neural network driven settings in Appendix A.16.

Generative Adversarial Networks

The Generative Adversarial Network (GAN) formulates learning a generative model of data as finding a Nash equilibrium of a minimax game. The generator ($\min$ player) aims to synthesize realistic data samples by transforming vectors drawn from a fixed source distribution, e.g., $\mathcal{N}(\mathbf{0},I_{d})$. The discriminator ($\max$ player) attempts to learn a scoring function that assigns low scores to synthetic data and high scores to samples drawn from the true dataset. The generator’s transformation function, $G$, and discriminator’s scoring function, $D$, are typically chosen to be neural networks parameterized by weights $\theta$ and $\phi$ respectively. The minimax objective of the original GAN is

where $p(z)$ is the source distribution, $p(y)$ is the true data distribution, and $g(x)=-\log(1+e^{-x})$.

In practice, finding the solution to (1) consists of local updates, e.g., SGD, to $\theta$ and $\phi$. This continues until 1) $V$ has stabilized, 2) the generated data is judged qualitatively accurate, or 3) training has de-stabilized and appears irrecoverable, at which point, training is restarted. The difficulty of training GANs has spurred research that includes reformulating the minimax objective , devising training heuristics , proving the existence of equilibria , and conducting local stability analyses .

We acknowledge here that our algorithm, Crossing-the-Curl, was independently proposed in as Symplectic Gradient Adjustment (SGA). In contrast to that work, this paper specifies a non-trivial application of this algorithm to LQ-GAN which obtains global convergence with high probability.

Recent work has studied a simplified setting, the Wasserstein LQ-GAN, where $G$ is a linear function, $D$ is a quadratic function, $g(x)=x$, and $p(z)$ is Gaussian . Follow-up research has shown that, in this setting, the optimal generator distribution is a rank-$k$ Gaussian containing the top-$k$ principal components of the data . Furthermore, it is shown that if the dimensionality of $p(z)$ matches that of $p(y)$, LQ-GAN is equivalent to maximum likelihood estimation of the generator’s resulting Gaussian distribution. To our knowledge, no GAN training algorithm with guaranteed convergence is currently known for this setting. We revisit the LQ-GAN in more detail in Section 4.

Convergence of Equilibrium Dynamics

As in convex optimization, a hierarchy of monotonicity exists. For all $x\in\mathcal{X}$ and $x^{\prime}\in\mathcal{X}$, $F$ is

If, in Equation (2), “$\geq$” is replaced by “$>$”, then $F$ is strictly-monotone; if “$\geq$” is replaced by “$s||x-x^{\prime}||^{2}$”, then $F$ is $s$-strongly-monotone. If $F$ is a gradient, then replace monotone with convex.

Table 1 cites algorithms with convergence rates for several settings. Whereas gradient descent achieves optimal convergence rates for various convex optimization settings, extragradient achieves optimal rates for VIs. Results have been extended to the online learning setting as well .

2 The ODE Method & Hurwitz Jacobians

Recently, Nagarajan and Kolter performed a local stability analysis of the gradient dynamics of Equation (1), proving that the Jacobian of $F$ evaluated at $x^{*}$ is HurwitzOur definition of Hurwitz is equivalent to the more standard: $-J$ is Hurwitz if $\max_{i}[\text{Re}(\lambda_{i}(-J))]<0$. , i.e., the real parts of its eigenvalues are strictly positive. This means that if simultaneous gradient descent using a “square-summable, not summable” step sequence enters an $\epsilon$-ball with a low enough step size, it will converge to the equilibrium. This applies only in the deterministic setting because stochastic gradients can cause the iterates to exit this ball and diverge. Note that while the real parts of eigenvalues reveal exponential growth or decay of trajectories, the imaginary parts reflect any rotation in the systemLinearized Dynamical System: $x(t)=\sum_{i}c_{i}v_{i}e^{\lambda_{i}t}$; Euler’s formula: $e^{(a+ib)t}=e^{at}(\cos(bt)+i\sin(bt))$..

The Hurwitz and monotonicity properties are complementary (see A.8). To summarize, Hurwitz encompasses dynamics with exponentially stable trajectories and with arbitrary rotation, while monotonicity includes cycles (Jacobians with zero eigenvalues) and is similar to convex optimization.

Given the preceding discussion, we believe VIs and monotone operator theory will serve as a strong foundation for deriving fundamental convergence results for GANs; this theory is

Similar to convexity suggesting its adoption by the GAN community should be smooth,

Mature with natural mechanisms for handling constraints, subdifferentials, and online scenarios,

Rich with algorithms with finite sample convergence for a hierarchy of monotone operators.

Finally, we suggest for a lucid comparison of convex optimization, game theory, and VIs.

The Wasserstein Linear Quadratic GAN

In the Wasserstein Linear-Quadratic GAN, the generator and discriminator are restricted to be linear and quadratic respectively: $G(z)=Az+b$ and $D(y)=y^{\top}W_{2}y+w_{1}^{\top}y$. Equation (1) becomes

The map $F$ associated with this zero-sum game is constructed by concatenating the gradients of the two players’ losses ($f_{G}=V,f_{D}=-V$):

Crossing-the-Curl

In this section, we will derive our proposed technique, Crossing-the-Curl, motivated by an examination of the ($w_{1},b$)-subsystem of LQ-GAN, i.e., $(w_{2},a)$ fixed at $(0,a_{0})$ for any $a_{0}$. The results discussed here hold for the N-dimensional case as well. The map associated with this subsystem is plotted in Figure 2 and formally stated in Equation (6).

The Jacobian of $F^{w_{1},b}$ is not Hurwitz, and simultaneous gradient descent, defined in Equation (7), will diverge for this problem (see A.5). However, $F^{w_{1},b}$ is monotone $(J+J^{\top}=\mathbf{0})$ and $1-$Lipschitz in the sense that $||F^{w_{1},b}(x)-F^{w_{1},b}(x^{\prime})||^{2}\leq 1||x-x^{\prime}||^{2}$. Table 1 offers an extragradient method (see Figure 2) with $\mathcal{O}(1/k)$ convergence rate, which is optimal for worst case monotone maps.

Nevertheless, an algorithm that travels perpendicularly to the vector field will proceed directly to the equilibrium. The intuition is to travel in the direction that is perpendicular to both $F$ and the axis of rotation. For a 2-d system, the axis of rotation can be obtained by taking the curl of the vector field. To derive a direction perpendicular to both $F$ and the axis of rotation, we can take their cross product:

where $\nabla_{F}$ is Feynman notation for the gradient with respect to $F$ only and $|_{v=F}$ means evaluate the expression at $v=F$. The $\nicefrac{{-1}}{{2}}$ factor ensures the algorithm moves toward regions of “tighter cycles” and simplifies notation. It may be sensible to perform some linear combination of simultaneous gradient descent and Crossing-the-Curl, so we will refer to $(I-\eta(J-J^{\top}))F$ as $F_{\eta cc}$.

Note that the fixed point of $F_{cc}$ remains the same as the original field $F$. Furthermore, the reader may recognize $F_{cc}$ as the gradient of the function $\frac{1}{2}(w_{1}^{2}+(b-\mu)^{2})$, which is strongly convex, allowing an $\mathcal{O}(e^{-k})$ convergence rate in the deterministic setting. $F_{cc}$ is derived from intuition in 2-d, however, we discuss reasons in the next subsection for why this approach generalizes to higher dimensions.

For the ($w_{1},b$)-subsystem, Crossing-the-Curl is equivalent to two other methods: the consensus algorithm and a Taylor series approximation to extragradient .

These equivalences occur because the Jacobian is skew-symmetric ($J^{\top}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>=</mo></mrow><annotation encoding="application/x-tex">=</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.3669em;"></span><span class="mrel">=</span></span></span></span></span>-J$) for the ($w_{1},b$)-subsystem. In the more general case, where $J$ is not necessarily skew-symmetric, Crossing-the-Curl represents a combination of the two techniques. Extragradient (EG) is key to solving VIs and the consensus algorithm has delivered impressive results for GANs, so this is promising for $F_{cc}$. To our knowledge, $F_{eg}$ is novel and has not appeared in the Variational Inequality literature.

Crossing-the-Curl stands out in many ways though. Observe that in higher dimensions, the subspace orthogonal to $F$ is $(n-1)$ dimensional, which means $(J^{\top}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>−</mo></mrow><annotation encoding="application/x-tex">-</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6667em;vertical-align:-0.0833em;"></span><span class="mord">−</span></span></span></span></span>J)F$ is no longer the unique direction orthogonal to $F$. However, every matrix can be decomposed into a symmetric part with real eigenvalues, $\nicefrac{{1}}{{2}}(J+J^{\top})$, and a skew-symmetric part with purely imaginary eigenvalues, $\nicefrac{{1}}{{2}}(J-J^{\top})$. Notice that for an optimization problem, $J<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>−</mo></mrow><annotation encoding="application/x-tex">-</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6667em;vertical-align:-0.0833em;"></span><span class="mord">−</span></span></span></span></span>J^{\top}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>=</mo></mrow><annotation encoding="application/x-tex">=</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.3669em;"></span><span class="mrel">=</span></span></span></span></span>H<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>−</mo></mrow><annotation encoding="application/x-tex">-</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6667em;vertical-align:-0.0833em;"></span><span class="mord">−</span></span></span></span></span>H^{\top}$$=$ where $H$ is the Hessian.Assuming the objective function has continuous second partial derivatives—see Schwarz’s theorem. It is the imaginary eigenvalues, i.e., rotation, that set equilibrium problems apart from optimization and necessitate the development of new algorithms like extragradient. It is reassuring that this matrix appears explicitly in $F_{cc}$. In addition, $F_{cc}$ reduces to gradient descent when applied to an optimization problem making the map agnostic to the type of problem at hand: optimization or equilibration.

Consider the perspective of $F_{cc}$ as preconditioning $F$ by a skew-symmetric matrix. Preconditioning with a positive definite matrix dates back to Newton’s method and has reappeared in machine learning with natural gradient . Dafermos considered asymmetric positive definite preconditioning matrices for VIs. Thomas extended the analysis of natural gradient to PSD matrices. We are not aware of any work using skew-symmetric matrices for preconditioning. The scalar $x^{\top}Ax\equiv 0$ for any skew-symmetric matrix $A$, so calling $(J^{\top}-J)$ a PSD matrix is not adequately descriptive.

Note that Crossing-the-Curl does not always improve convergence; this technique can transform a strongly-monotone field into a saddle and an unstable fixed point (non-monotone) into a strongly-monotone field (see A.9 for examples), so this technique should generally be used with caution.

Lastly, Crossing-the-Curl is inexpensive to compute. The Jacobian-vector product, $JF$, can be approximated accurately and efficiently with finite differences. Likewise, $J^{\top}F$ can be computed efficiently with double backprop by taking the gradient of $\nicefrac{{1}}{{2}}||F||^{2}$. In total, three backprops are required, one for $F(x_{k})$, one for $F(\hat{x}_{k+1})$, and one for $\nicefrac{{1}}{{2}}||F(x_{k})||^{2}$.

In our analysis, we also consider the gradient regularization proposed in , $F_{reg}$, the Unrolled GAN proposed in , $F_{unr}$, alternating gradient descent, $F_{alt}$, as well as any linear combination of $F$, $JF$, and $J^{\top}F$, deemed $F_{lin}$, which forms a family of maps that includes $F_{eg}$, $F_{con}$, and $F_{cc}$:

Keep in mind that we are proposing $F_{lin}$ as a generalization of Crossing-the-Curl. We state our main results here for the $(w_{1},b)$-subsystem.

For any $\alpha$, $F^{w_{1},b}_{lin}$ with at least one of $\beta$ and $\gamma$ positive and both non-negative is strongly monotone. Also, its Jacobian is Hurwitz. See Proposition 13.

$F^{w_{1},b}_{cc}$, $F^{w_{1},b}_{\eta cc}$, $F^{w_{1},b}_{eg}$, and $F^{w_{1},b}_{con}$ with $\eta>0$ are strongly-monotone with Hurwitz Jacobians. See Proposition 1.

$F^{w_{1},b}_{alt}$, $F^{w_{1},b}_{unr}$, $F^{w_{1},b}$, and $F^{w_{1},b}_{reg}$ with any $\eta$ are monotone, but not strictly monotone. Of these maps, only $F^{w_{1},b}_{reg}$’s Jacobian is Hurwitz. See Propositions 12 and 13.

Analysis of the Full System

Here, we analyze the maps for each of the algorithms discussed above, testing for quasimonotonicity (the weakest monotone property) and whether the Jacobian is Hurwitz for the full LQ-GAN system.

Proving quasiconvexity of 4th degree polynomials has been proven strongly NP-Hard . This implies that proving monotonicity of 3rd degree maps is strongly NP-Hard. The original $F$ contains quadratic terms suggesting it may welcome a quasimonotone analysis, however, the remaining maps all contain 3rd degree terms. Unsurprisingly, analyzing quasimonotonicity for $F_{lin}$ represents the most involved of our proofs given in Appendix A.11.

The definition stated in (3) suggests checking the truth of an expression depending on four separate variables: $x$, $x^{\prime}$, $y$, $y^{\prime}$. While we used this definition for certain cases, the following alternate requirements proposed in made the complete analysis of the system tractable. We restate simplified versions of the requirements we leveraged for convenience.

For all $x\in\mathcal{X}$ and $x^{*}\in\mathcal{X}$ such that $F(x^{*})=0$, we have that $F(x)^{\top}(x-x^{*})\geq 0$.

$F$ is quasimonotone on $\mathcal{X}$ only if (A) holds, i.e. (A) is necessary but not sufficient.

$F$ is pseudomonotone on $\mathcal{X}$ if (A) and (B) hold, i.e. (A) and (B) are sufficient but not necessary.

Condition (A) says that for a map to be quasimonotone, the map must be monotone along directions orthogonal to the vector field. In addition to this, condition (B) says that for a map to be pseudomonotone, the dynamics, $-F$, must not be leading away from the equilibrium anywhere.

Equipped with these definitions, we can conclude the following:

None of the maps, including $F_{lin}$ with any setting of coefficients, is quasimonotone for the full LQ-GAN. See Corollary 5 and Propositions 15 through 17.

None of the maps, including $F_{lin}$ with any setting of coefficients, has a Hurwitz Jacobian for the full LQ-GAN. See Propositions 27 and 15 through 17.

Results from the previous section suggest that we cannot solve the full LQ-GAN, but given that we can solve the ($w_{1},b$)-subsystem, we shift focus to the ($w_{2},a$)-subsystem assuming the mean has already been learned exactly, i.e., $b=\mu$. We will revisit this assumption later.

We can conclude the following for the ($w_{2},a$)-subsystem:

$F^{w_{2},a}$, $F^{w_{2},a}_{reg}$, $F^{w_{2},a}_{unr}$, $F^{w_{2},a}_{alt}$, and $F^{w_{2},a}_{con}$ are not quasimonotone. Also, their Jacobians are not Hurwitz. See Propositions 14 through 19.

$F^{w_{2},a}_{eg}$ and $F^{w_{2},a}_{cc}$ are pseudomonotone which implies an $\mathcal{O}(1/\sqrt{k})$ stochastic convergence rate. See Propositions 21 and 24. Their Jacobians are not Hurwitz. See Proposition 27.

No monotone $F^{w_{2},a}_{lin}$ exists. See Proposition 26.

These results are not purely theoretical. Figure 4 displays trajectories resulting from each of the maps.

We can further improve upon $F^{w_{2},a}_{eg}$ and $F^{w_{2},a}_{cc}$ by rescaling with $\nicefrac{{1}}{{4a^{2}}}$: (12)$\rightarrow$(13) and (14)$\rightarrow$(15) respectively. This results in strongly-monotone and strongly-convex systems respectively, improving the stochastic convergence rate to $\mathcal{O}(1/k)$. In deriving these results, we assumed the mean was given. We can relax this assumption and analyze the ($w_{2},a$)-subsystem under the assumption that the mean is “close enough”. Using a Hoeffding bound, we find that k>\big{(}\frac{y_{hi}-y_{low}}{-|\mu|+\sqrt{\mu^{2}+d\sigma^{2}}}\big{)}^{2}\log[\frac{\sqrt{2}}{\delta^{1/2}}] iterations of $F^{w_{1},b}_{cc}$ are required to achieve a $1-\delta$ probability of the mean being accurate enough to ensure the ($w_{2},a$)-subsystem is strongly-monotone. Note that this approach of first learning the mean, then the variance retains the overall $\mathcal{O}(1/k)$ stochastic rate. We summarize the main points here.

A nonlinear scaling of $F^{w_{2},a}_{eg}$ and $F^{w_{2},a}_{cc}$ results in strictly monotone and $\nicefrac{{1}}{{2}}$-strongly monotone subsystems respectively. See Proposition 29.

If the mean is first well approximated, i.e., $b^{2}\leq\mu^{2}+\sigma^{2}$, then $F^{w_{2},a}_{cc^{\prime}}$ remains 1) $\nicefrac{{1}}{{2}}$-strongly-monotone if the ($w_{1},b$)-subsystem is “shut off” or 2) strictly-monotone if the $(w_{1},b)$-subsystem is re-weighted with a high coefficient. See Propositions 30 and 31.

$F^{W_{2},A}_{eg}$ and $F^{W_{2},A}_{cc}$ are not quasimonotone for the 2-d LQ-GAN system (with and without $(AA^{\top})^{-1}$ scaling). See Proposition 32.

Several takeaways emerge. One is that the stability of the system is highly dependent on the mean first being learned. In other words, batch norm is required for the monotonicity of LQ-GAN, so it is not surprising that GANs typically fail without these specialized layers.

Second is that stability is achieved by first learning a simple subsystem, ($w_{1},b$), then learning the more complex, ($w_{2},a$)-subsystem. This theoretically confirms the intuition behind progressive training of GANs , which have generated the highest quality images to date.

Thirdly, because $J^{cc^{\prime}}_{w_{2},a}$ is symmetric (and $\succ 0$), we can integrate $F^{cc^{\prime}}_{w_{2},a}$ to discover the convex function it is implicitly descending via gradient descent: $f^{cc^{\prime}}_{w_{2},a}=1/2[(a^{2}-\sigma^{2})-\sigma^{2}\log(\nicefrac{{a^{2}}}{{\sigma^{2}}})]$. Compare this to KL-divergence: $KL(\sigma||a)=1/2[(\sigma^{2}/a^{2})+\log(\nicefrac{{a^{2}}}{{\sigma^{2}}})-1]$. In contrast to $KL$, $f^{cc^{\prime}}_{w_{2},a}$ is convex in $a$ and may be a desirable alternative due to less extreme gradients near $a=0$.

After learning both the mean and variance of each dimension, the covariance of separate dimensions can be learned. Proposition 35 in the Appendix states that the subsystem relevant to learning each row of $A$ is strictly monotone when all other rows are held fixed. In fact, the maps for these subsystems are affine and skew-symmetric just like the ($w_{1},b$)-subsystem. This implies that Crossing-the-Curl applied successively to each row of $A$ can solve for $A^{*}$; pseudocode is presented in Algorithm 1 in Appendix A.15. Note that this procedure is reminiscent of the Cholesky–Banachiewicz algorithm which computes $A$ row by row, beginning with the first row. The resulting algorithm is $\mathcal{O}(N/k)$.

Experiments

The second and third rows of the table reveal that convergence slows considerably for higher dimensions. However, the stagewise procedure discussed in Subsection 6.2 is guaranteed to converge given the mean has been learned to a given accuracy. This procedure solves the 4-d deterministic LQ-GAN in $\mathbf{20549}$ iterations with a $\mathbf{0.88}$ success rate. For the 4-d stochastic LQ-GAN using two-sample minibatch estimates, this procedure achieves $||x_{k}-x^{*}||/||x_{0}-x^{*}||<0.1$ in 100,000 iterations with a 0.75 success rate.

Conclusion

In this work, we performed the first global convergence analysis for a variety of GAN training algorithms. According to Variational Inequality theory, none of the current GAN training algorithms is globally convergent for the LQ-GAN. We proposed an intuitive technique, Crossing-the-Curl, with the first global convergence guarantees for any generative adversarial network. As a by-product of our analysis, we extract high-level explanations for why the use of batch norm and progressive training schedules for GANs are critical to training. In experiments with the multivariate LQ-GAN, Crossing-the-Curl achieves performance superior to any existing GAN training algorithm.

For future work, we will investigate alternate parameterizations of the discriminator such as $D(y)=w_{2}(y-w_{1})^{2}$. We will also work on devising heuristics for setting the coefficients of $F_{lin}$.

Acknowledgments

Crossing-the-Curl was independently proposed in called Symplectic Gradient Adjustment (SGA). Like Crossing-the-Curl, this algorithm is motivated by attacking the challenges of rotation in differentiable games, however, it is derived by performing gradient descent on the Hamiltonian as opposed to generalizing a particular perpendicular direction selected from intuition in 2-d. Given the equivalence between SGA and Crossing-the-Curl, our work can also be viewed as proving that a non-trivial application of this algorithm can be used to solve the LQ-GAN. On the other hand, we have also proven in Proposition 7 that a naive application of this algorithm is insufficient for solving LQ-GAN suggesting more research is required to understand and more efficiently solve this complex problem.

References

Appendix A Appendix

Algorithmic Game Theory (AGT) offers results on convergence to equilibria when a game, possibly online, is convex , socially-convex , or smooth . A convex game is one in which all player losses are convex in their respective variables, i.e. $f_{i}(x_{i},x_{-i})$ is convex in $x_{i}$. A socially-convex game adds the additional requirements that 1) there exists a strict convex combination of the player losses that is convex and 2) each player’s loss is concave in the variables of each of the other players. In other words, the players as a whole are cooperative, yet individually competitive. Lastly, smoothness ensures that “the externality imposed on any one player by the actions of the others is bounded” . In a zero-sum game such as (1), one player’s gain is exactly the other player’s loss making smoothness an unlikely fit for studying GANs. See for examples where the three properties above overlap with monotonicity in VIs.

A.1.2 Differential Games

Differential games consider more general dynamics such as $\ddot{x}=-F(x)$, not just first order ODEs, however, the focus is on systems that separate control, $u$, and state $x$, i.e. $\dot{x}=-F(x(t),u(t),t)$. More specific to our interests, Differential Nash Games can be expressed as Differential VIs, a specific class of infinite dimensional VIs with explicit state dynamics and explicit controls; these, in turn, can be framed as infinite dimensional VIs without an explicit state.

A.2 Nash Equilibrium vs VI Solution

Repeated from . Let $(\mathbf{C},K)$ be a cost minimization game with player cost functions $C_{i}$ and feasible set $K$. Let $x^{*}$ be a Nash equilibrium. Let $F=[\frac{\partial C_{1}}{\partial x_{1}},\ldots,\frac{\partial C_{N}}{\partial x_{N}}]$. Then

where $\mathbf{I}_{K}(x^{*})$ is the internal cone at $x^{*}$. When $C_{i}(\mathbf{x}_{i},\mathbf{x}_{-i})$ is pseudoconvex in $\mathbf{x}_{i}$ for all $i$, this condition is also sufficient. Note that this is implied if $F$ is pseudomonotone, i.e. pseudomonotonicity of $F$ is a stronger condition.

A.3 Table of Maps Considered in Analysis

All maps corresponding to the ($w_{1},b$)-subsystem in Table 4 maintain the desired unique fixed point, $F(x^{*})=0$, where $x^{*}=(w_{1}^{*},b^{*})=(0,\mu)$.

For the ($w_{2},a$)-subsystem, all maps except $F_{lin}$ with certain settings of ($\alpha,\beta,\gamma$) and $F_{con}$ maintain the desired unique fixed point, $x^{*}=(w_{2}^{*},a^{*})=(0,\sigma)$. $F_{con}$ introduces an additional spurious fixed point at

$F_{con}$ is a special case of $F_{lin}$ where $\alpha=1$, $\beta=1$, and $\gamma=0$.

A.4 Minimax Solution to Constrained Multivariate LQ-GAN is Unique

Taking derivatives and setting equal to zero, we find that the fixed point at the interior is unique.

The last implication in Equation (30) follows because $A$ is constrained to be of Cholesky form, i.e., lower triangular with positive diagonal, and every symmetric positive definite matrix has a unique Cholesky decomposition.

The second to last implication of Equation (32) follows because $A=\Sigma^{1/2}$ is necessarily full rank. Note this implies $A^{\top}$ is also full rank. The null space of a full rank matrix is the zeros vector, which implies $W_{2}+W_{2}^{\top}=0$. $W_{2}$ is symmetric, so this implies $W_{2}=0$. ∎

Consider the case where the mean of $p(z)$ is zero:

We will show that simultaneous gradient descent always produces an iterate that is farther away from the equilibrium than the previous iterate, i.e. $||x_{k+1}-x^{*}||^{2}/||x_{k}-x^{*}||^{2}>1$.

Therefore, simultaneous gradient descent diverges from the equilibrium of the ($w_{1},b$)-subsystem for any step size scheme, $\rho_{k}$.

A.6 Derivation of Crossing-the-Curl

Here, we derive our proposed technique in 3-d, however, the result of the derivation can be computed in arbitrary dimensions:

A.7 Monotonicity: Definitions and Requirements

For all $x\in\mathcal{X}$ and $x^{\prime}\in\mathcal{X}$,

While we used these definitions in our analysis for certain cases, the following alternate requirements proposed in made the complete analysis of the system tractable. We restate them here for convenience. Note that we what we refer to as condition (B) in the main body of the paper is actually a stronger version of condition (C) below with $v=(x^{*}-x)/t$.

$F$ is quasimonotone on $\mathcal{X}$ if and only if (A) and (B’) hold.

$F$ is pseudomonotone on $\mathcal{X}$ if and only if (A) and (C’) hold.

A.8 A Comparison of Monotonicity and Hurwitz

The monotonicity and Hurwitz properties are complementary.

Let $F(x)=Jx$, $J=\begin{bmatrix}1&4\\ -1&1\end{bmatrix}$, $S=\begin{bmatrix}0&1\\ -1&0\end{bmatrix}$, and $v=SJx=[-x_{1}+x_{2},-x_{1}-4x_{2}]^{\top}$. Then $\lambda_{1,2}(J)=1\pm 2i$ so $J$ is Hurwitz, and

which, by condition (A), implies $F$ is not quasimonotone.

A.8.2 Monotonicity Does Not Imply Hurwitz

Let $F(x)=Jx$ and $J=\begin{bmatrix}0&1\\ -1&0\end{bmatrix}$. Then $\lambda_{1,2}(J)=\pm i$ so $J$ is not Hurwitz, but

A.8.3 Monotonicity and Hurwitz Can Overlap

Let $F(x)=Jx$ and $J=\begin{bmatrix}1&0\\ 0&1\end{bmatrix}$. Then $\lambda_{1,2}(J)=1$ so $J$ is Hurwitz and

If $F$ is (strictly,strongly)-monotone, then the Jacobian of $F$ is a real, square, (positive definite,strongly-positive definite) matrix, therefore, it matches the above assumptions. Hence, the conclusion follows. ∎

A.9 Crossing-the-Curl Can Make Monotone Fields, Non-Monotone

Here, we provide examples of negative results for Crossing-the-Curl. This is to emphasize that our proposed technique can cause problems if not used with caution. The headings below describe the before and afters when applying our proposed technique to the map $F(x)=Jx$.

Increase in condition number: $\kappa=\nicefrac{{11}}{{5}}\rightarrow 4$.

$F^{w_{2},a}_{eg^{\prime}}$ becomes non-monotone.

Crossing-the-Curl forces monotonicity for normal, affine fields.

Let $F=Jx+b$ and assume $J$ is normal, i.e., $JJ^{\top}=J^{\top}J$. Then

Unrolled GANs and Alternating Updates are Monotone for the ($w_{1},b$)-subsystem.

In Unrolled GANs, the generator computes the gradient of $V$ assuming the discriminator has already made several updates. Define the discriminator’s update as

and denote the composition of $U$, $\Delta k$-times as

where $\Delta k$ is some positive integer. Then the update for Unrolled GANs is

In the case of the ($w_{1},b$)-subsystem, we can write these unrolled updates out explicitly. Remember $F=[b-\mu,-w_{1}]^{\top}$, so

where the corresponding map is $F^{unr}=[b_{k}-\mu,\rho\Delta k(b_{k}-\mu)-w_{1,k}]$. Taking a look at the Jacobian, we find

Here, we considered updating $b$ first, but the ($w_{1},b$)-subsystem is perfectly symmetric, so the analysis holds either way. If $w_{1}$ is updated first, this is equivalent to Unrolled GAN with $\Delta k=1$ (see Equation 104). The Jacobian is

The Jacobian’s for Unrolled GAN and alternating descent are both positive semidefinite, therefore, their maps are monotone (but not strictly-monotone). Note that these results imply neither is Hurwitz either because both Jacobians exhibit a zero eigenvalue. ∎

$F_{lin}$, $F_{cc}$, $F_{eg}$, and $F_{con}$ are strongly-monotone for the ($w_{1},b$)-subsystem (includes multivariate case). $F$ and $F_{reg}$ are monotone, but not strictly monotone. Moreover, $F_{lin}$, $F_{cc}$, $F_{eg}$, $F_{con}$, and $F_{reg}$ are Hurwitz for the ($w_{1},b$)-subsystem (includes multivariate case). $F$ is not Hurwitz.

We start with the original map, $F^{w_{1},b}$, and its Jacobian.

The symmetrized Jacobian is positive semidefinite, therefore this system is monotone. Also, the real parts of the eigenvalues of its Jacobian are zero, therefore, $J$ is not Hurwitz.

Now we analyze $F^{w_{1},b}_{cc}$, $F^{w_{1},b}_{eg}$, and $F^{w_{1},b}_{con}$, which as discussed in the main body, are equivalent.

The symmetrized Jacobian is positive definite with a minimum eigenvalue of $1$, therefore this system is $1$-strongly-monotone. By Proposition 10, the Jacobians of these maps are Hurwitz for the $(w_{1},b)$-subsystem.

Now we analyze the generalization $F^{w_{1},b}_{lin}=(\alpha I-\beta J^{\top}-\gamma J)F^{w_{1},b}$.

The symmetrized Jacobian is positive definite with a minimum eigenvalue of $(\beta+\gamma)$, therefore this system is $(\beta+\gamma)$-strongly-monotone. By Proposition 10, $J^{w_{1},b}_{lin}$ is Hurwitz for the $(w_{1},b)$-subsystem.

Now we analyze the regularized-gradient algorithm, $F^{w_{1},b}_{reg}$.

Therefore, this map is monotone (but not strictly or strongly-monotone). Also, the real parts of the eigenvalues of its Jacobian are strictly positive, therefore, $J^{w_{1},b}_{reg}$ is Hurwitz.

Note that for $F_{cc}$, $F_{eg}$, $F_{con}$, and $F_{lin}$, $J$ is symmetric, therefore, $F$ is the gradient of some function, $f(w_{1},b)=\frac{1}{2}(w_{1}^{2}+(b-\mu)^{2})$. Also, note that the standard algorithm with step size $\rho_{k}=\frac{1}{k+1}$ is equivalent to the standard running estimate of the mean: $\mu_{k+1}=\frac{k}{k+1}\mu_{k}+\frac{1}{k+1}x_{k}$ where $x_{k}$ is the $k$-th sample.

Specifically, we first consider the sign of $\beta+\gamma$. Lemma 1 rules out negative values. Lemma 2 rules out positive values when $\sigma^{2}\leq\nicefrac{{1}}{{2}}$, and Lemma 3 rules out positive values when $\sigma^{2}>\nicefrac{{1}}{{2}}$. Corollary 2 concludes that $\beta+\gamma=0$.

Next, given $\beta+\gamma=0$, we consider the sign of $\alpha$. Lemmas 4 and 5 rule out positive values of $\alpha$ when $\beta$ is greater than or less than or equal to zero respectively, i.e., $\alpha$ cannot be positive. Similarly, Lemmas 6 and 7 rule out negative values of $\alpha$ when $\beta$ is less than or greater than or equal to zero respectively, i.e., $\alpha$ cannot be negative. Corollary 3 concludes that $\alpha=0$.

Lastly, given that $\beta+\gamma=\alpha=0$, Lemmas 8 and 9 prove that $\beta$ cannot be greater than or less than or equal to zero respectively. Corollary 4 concludes that $\beta=\gamma=0$. Therefore, the only quasimonotone linear combination is the trivial one resulting in $F=0$, which completes the proof.

For $F_{lin}$ to be quasimonotone, $\beta+\gamma$ must not be strictly less than zero, i.e. $\beta+\gamma\cancel{<}0$.

If $(\beta+\gamma)<0$, then this system is not quasimonotone. Therefore, assume $(\beta+\gamma)\geq 0$ from now on. ∎

If $\sigma^{2}\leq\frac{1}{2}$, for $F_{lin}$ to be quasimonotone, $\beta+\gamma$ must not be strictly greater than zero, i.e. $\beta+\gamma\cancel{>}0$.

We will use a different parameterization of $F_{lin}$ for this part of the proof.

In order for a system to be quasimonotone, we require condition (A) (among other properties). We will now show that this property is not satisfied for $F_{lin}$ with $\hat{\beta}>0$ by considering two different cases.

Case 1: Consider the $(w_{2},a)$-subsystem. Let

Above, we premultiply $F_{lin}$ by a skew symmetric matrix, which ensures $v^{\top}F_{lin}=F_{lin}^{\top}A_{skew}F_{lin}=0$.

The relevant portion of the Jacobian of $F_{lin}$ is

Consider $x=[0,0,c\sigma,0]$ and both $\hat{\beta}$ and $\alpha$ fixed.

This implies either $\alpha=0$ or $\hat{\beta}\leq 0$ for the system to be quasimonotone.

Case 2: Consider the $(a,b)$-subsystem. Let

The relevant portion of the Jacobian of $F_{lin}$ is

Consider $\alpha=0$ and $x=[0,0,\frac{\sigma}{10},\frac{\sigma}{2}]$. Then

Then $\alpha=0\Rightarrow\hat{\beta}\leq 0$. In either case, $\hat{\beta}$ must be nonpositive. Therefore, $\hat{\beta}=\beta+\gamma\cancel{>}0$. ∎

Part of the proof in Lemma 2 looks at the limit in which $a$ approaches 0. One might presume a simple fix is to constrain $a$ to be larger than some small value, e.g., 1e-10, and use a large $\hat{\beta}$ value. Here, we show that even using $a=\frac{\sigma}{100}$ breaks quasimonotonicity. The variance of the data distribution is assumed to be unknown, which would make it very difficult to select a proper lower bound for $a$ that maintains quasimonotonicity within the feasible region.

Consider $x=[0,-1,\frac{\sigma}{100},\frac{\sigma}{2}]$ and the $(a,b)$-subsystem as in 2. Then

If $\hat{\beta}>0$, then this is a concave quadratic form in $\alpha$. To find where this function is positive, we need to find its roots.

The $\alpha$ root with smaller magnitude provides an upper bound for $\hat{\beta}^{2}$.

Now consider again $x=[0,0,\frac{\sigma}{100},0]$ and equation 141 with $c=\frac{1}{100}$.

This provides a lower bound for $\hat{\beta}^{2}$.

The upper bound we require for $\hat{\beta}$ is greater than the lower bound, therefore, no $\hat{\beta}$ will satisfy quasimonotonicity. ∎

If $\sigma^{2}>\frac{1}{2}$, for $F_{lin}$ to be quasimonotone, $\beta+\gamma$ must not be strictly greater than zero, i.e. $\beta+\gamma\cancel{>}0$.

For this proof, we make use of the traditional definition of quasimonotonicity. Consider

If $(\beta+\gamma)>0$, then this system is not quasimonotone. In either case, $(\beta+\gamma)\cancel{>}0$. ∎

𝛽𝛾0\beta+\gamma=0 for quasimonotonicity.). Together, Lemmas 1, 2 and 3 imply that $(\beta+\gamma)$ must be to satisfy quasimonotonicity.

If $(\beta+\gamma)=0$ and $\alpha>0$, for $F_{lin}$ to be quasimonotone, $\beta$ must not be strictly greater than zero, i.e. $\beta\cancel{>}0$.

For this proof, we make use of the traditional definition of quasimonotonicity. Consider

If $(\beta+\gamma)=0$ and $\alpha>0$, then $\beta\leq 0$ for the system to be quasimonotone. ∎

If $(\beta+\gamma)=0$, for $F_{lin}$ to be quasimonotone, $\alpha$ must not be strictly greater than zero, i.e. $\alpha\cancel{>}0$.

We will assume $\alpha>0$, which by Lemma 4 implies $\beta\leq 0$. This will lead to a contradiction. Consider

If $(\beta+\gamma)=0$ and $\alpha>0$ (implies $\beta\leq 0$), then $\langle F(y),x-y\rangle>0$ and $\langle F(x),x-y\rangle<0$, which breaks quasimonotonicity. Therefore, $\alpha\cancel{>}0$. ∎

If $(\beta+\gamma)=0$ and $\alpha<0$, for $F_{lin}$ to be quasimonotone, $\beta$ must not be strictly less than zero, i.e. $\beta\cancel{<}0$.

If $\alpha<0$, then $\beta\geq 0$ to maintain quasimonotonicity. ∎

If $(\beta+\gamma)=0$, for $F_{lin}$ to be quasimonotone, $\alpha$ must not be strictly less than zero, i.e. $\alpha\cancel{<}0$.

We will assume $\alpha<0$, which by 6 implies $\beta\geq 0$. This will lead to a contradiction.

If $(\beta+\gamma)=0$ and $\alpha<0$ (implies $\beta\geq 0$), then $\langle F(y),x-y\rangle>0$ and $\langle F(x),x-y\rangle<0$, which breaks quasimonotonicity. Therefore, $\alpha\geq 0$. ∎

Together, Corollary 2 and Lemmas 4-7 imply that $\alpha$ must equal zero for $F_{lin}$ to be quasimonotone.

If $(\beta+\gamma)=0$ and $\alpha=0$, for $F_{lin}$ to be quasimonotone, $\beta$ must not be strictly greater than zero, i.e. $\beta\cancel{>}0$.

If $\beta>0$, then this system is not quasimonotone. Therefore, $\beta\leq 0$. ∎

If $(\beta+\gamma)=0$ and $\alpha=0$, for $F_{lin}$ to be quasimonotone, $\beta$ must not be strictly less than zero, i.e. $\beta\cancel{<}0$.

If $\beta<0$, then this system is not quasimonotone. Therefore, $\beta\geq 0$. ∎

𝛽𝛾0𝛼0⇒𝛽𝛾0(\beta+\gamma)=0,\alpha=0\Rightarrow\beta=\gamma=0). Together, Lemmas 8 and 9 imply that $\beta=0$, which, along with Corollary 2, imply that $\gamma=0$ as well.

[$\alpha=\beta=\gamma=0$] Together, Corollaries 2 and 3, and 4 imply that there is no non-trivial linear combination that induces a quasimonotone LQ-GAN system.

$F_{cc}$, $F_{eg}$, $F_{con}$, and $F$ are not quasimonotone for the LQ-GAN system.

These maps are all linear combinations of $F$, $JF$ and $J^{\top}F$, therefore, by Corollary 5, they are not quasimonotone for the LQ-GAN system. ∎

Note that if a map is not quasimonotone for the $(w_{2},a)$-subsystem, then it is not quasimonotone for the full system. This is because an analysis of the $(w_{2},a)$-subsystem is equivalent to an analysis of a subspace of the full system with $w_{1}=b=0$.