The Numerics of GANs

Introduction

Generative Adversarial Networks (GANs) have been very successful in learning probability distributions. Since their first appearance, GANs have been successfully applied to a variety of tasks, including image-to-image translation , image super-resolution , image in-painting domain adaptation , probabilistic inference and many more.

While very powerful, GANs are known to be notoriously hard to train. The standard strategy for stabilizing training is to carefully design the model, either by adapting the architecture or by selecting an easy-to-optimize objective function .

In this work, we examine the general problem of finding local Nash-equilibria of smooth games. We revisit the de-facto standard algorithm for finding such equilibrium points, simultaneous gradient ascent. We theoretically show that the main factors preventing the algorithm from converging are the presence of eigenvalues of the Jacobian of the associated gradient vector field with zero real-part and eigenvalues with a large imaginary part. The presence of the latter is also one of the reasons that make saddle-point problems more difficult than local optimization problems. Utilizing these insights, we design a new algorithm that overcomes some of these problems. Experimentally, we show that our algorithm leads to stable training on many GAN architectures, including some that are known to be hard to train.

Our technique is orthogonal to strategies that try to make the GAN-game well-defined, e.g. by adding instance noise or by using the Wasserstein-divergence : while these strategies try to ensure the existence of Nash-equilibria, our paper deals with their computation and the numerical difficulties that can arise in practice.

In summary, our contributions are as follows:

We identify the main reasons why simultaneous gradient ascent often fails to find local Nash-equilibria.

By utilizing these insights, we design a new, more robust algorithm for finding Nash-equilibria of smooth two-player games.

We empirically demonstrate that our method enables stable training of GANs on a variety of architectures and divergence measures.

The proofs for the theorems in this paper can be found the supplementary material.The code for all experiments in this paper is available under https://github.com/LMescheder/TheNumericsOfGANs.

Background

In this section we first revisit the concept of Generative Adversarial Networks (GANs) from a divergence minimization point of view. We then introduce the concept of a smooth (non-convex) two-player game and define the terminology used in the rest of the paper. Finally, we describe simultaneous gradient ascent, the de-facto standard algorithm for finding Nash-equilibria of such games, and derive some of its properties.

Generative Adversarial Networks are best understood in the context of divergence minimization: assume we are given a divergence function $D$, i.e. a function that takes a pair of probability distributions as input, outputs an element from $[0,\infty]$ and satisfies $D(p,p)=0$ for all probability distributions $p$. Moreover, assume we are given some target distribution $p_{0}$ from which we can draw i.i.d. samples and a parametric family of distributions $q_{\theta}$ that also allows us to draw i.i.d. samples. In practice $q_{\theta}$ is usually implemented as a neural network that acts on a hidden code $z$ sampled from some known distribution and outputs an element from the target space. Our goal is to find $\bar{\theta}$ that minimizes the divergence $D(p_{0},q_{\theta})$, i.e. we want to solve the optimization problem

Most divergences that are used in practice can be represented in the following form :

These divergences include the Jensen-Shannon divergence , all f-divergences , the Wasserstein divergence and even the indicator divergence, which is if $p=q$ and $\infty$ otherwise.

In practice, the function class $\mathcal{F}$ in (3) is approximated with a parametric family of functions, e.g. parameterized by a neural network. Of course, when minimizing the divergence w.r.t. this approximated family, we no longer minimize the correct divergence. However, it can be verified that taking any class of functions in (3) leads to a divergence function for appropriate choices of $g_{1}$ and $g_{2}$. Therefore, some authors call these divergence functions neural network divergences .

2 Smooth Two-Player Games

A differentiable two-player game is defined by two utility functions $f(\phi,\theta)$ and $g(\phi,\theta)$ defined over a common space $(\phi,\theta)\in\Omega_{1}\times\Omega_{2}$. $\Omega_{1}$ corresponds to the possible actions of player 1, $\Omega_{2}$ corresponds to the possible actions of player 2. The goal of player 1 is to maximize $f$, whereas player 2 tries to maximize $g$. In the context of GANs, $\Omega_{1}$ is the set of possible parameter values for the generator, whereas $\Omega_{2}$ is the set of possible parameter values for the discriminator. We call a game a zero-sum game if $f=-g$. Note that the derivation of the GAN-game in Section 2.1 leads to a zero-sum game, whereas in practice people usually employ a variant of this formulation that is not a zero-sum game for better convergence .

Our goal is to find a Nash-equilibrium of the game, i.e. a point $\bar{x}=(\bar{\phi},\bar{\theta})$ given by the two conditions

We call a point $(\bar{\phi},\bar{\theta})$ a local Nash-equilibrium, if (4) holds in a local neighborhood of $(\bar{\phi},\bar{\theta})$.

Every differentiable two-player game defines a vector field

We call $v$ the associated gradient vector field to the game defined by $f$ and $g$.

For the special case of zero-sum two-player games, we have $g=-f$ and thus

As a direct consequence, we have the following:

For zero-sum games, $v^{\prime}(x)$ is negative (semi-)definite if and only if $\nabla_{\phi}^{2}f(\phi,\theta)$ is negative (semi-)definite and $\nabla_{\theta}^{2}f(\phi,\theta)$ is positive (semi-)definite.

For zero-sum games, $v^{\prime}(\bar{x})$ is negative semi-definite for any local Nash-equilibrium $\bar{x}$. Conversely, if $\bar{x}$ is a stationary point of $v(x)$ and $v^{\prime}(\bar{x})$ is negative definite, then $\bar{x}$ is a local Nash-equilibrium.

Note that Corollary 2 is not true for general two-player games.

3 Simultaneous Gradient Ascent

The de-facto standard algorithm for finding Nash-equilibria of general smooth two-player games is Simultaneous Gradient Ascent (SimGA), which was described in several works, for example in and, more recently also in the context of GANs, in . The idea is simple and is illustrated in Algorithm 1. We iteratively update the parameters of the two players by simultaneously applying gradient ascent to the utility functions of the two players. This can also be understood as applying the Euler-method to the ordinary differential equation

where $v(x)$ is the associated gradient vector field of the two-player game.

It can be shown that simultaneous gradient ascent converges locally to a Nash-equilibrium for a zero-sum game, if the Hessian of both players is negative definite and the learning rate is small enough. Unfortunately, in the context of GANs the former condition is rarely met. We revisit the properties of simultaneous gradient ascent in Section 3 and also show a more subtle property, namely that even if the conditions for the convergence of simultaneous gradient ascent are met, it might require extremely small step sizes for convergence if the Jacobian of the associated gradient vector field has eigenvalues with large imaginary part.

Convergence Theory

In this section, we analyze the convergence properties of the most common method for training GANs, simultaneous gradient ascentA similar analysis of alternating gradient ascent, a popular alternative to simultaneous gradient ascent, can be found in the supplementary material. . We show that two major failure causes for this algorithm are eigenvalues of the Jacobian of the associated gradient vector field with zero real-part as well as eigenvalues with large imaginary part.

For our theoretical analysis, we start with the following classical theorem about the convergence of fixed-point iterations:

the absolute values of the eigenvalues of the Jacobian $F^{\prime}(\bar{x})$ are all smaller than 1.

Then there is an open neighborhood $U$ of $\bar{x}$ so that for all $x_{0}\in U$, the iterates $F^{(k)}(x_{0})$ converge to $\bar{x}$. The rate of convergence is at least linear. More precisely, the error $\|F^{(k)}(x_{0})-\bar{x}\|$ is in $\mathcal{O}(|\lambda_{max}|^{k})$ for $k\to\infty$ where $\lambda_{max}$ is the eigenvalue of $F^{\prime}(\bar{x})$ with the largest absolute value.

In numerics, we often consider functions of the form

for some $h>0$. Finding fixed points of $F$ is then equivalent to finding solutions to the nonlinear equation $G(x)=0$ for $x$. For $F$ as in $\eqref{eq:F-incremental}$, the Jacobian is given by

Note that in general neither $F^{\prime}(x)$ nor $G^{\prime}(x)$ are symmetric and can therefore have complex eigenvalues.

The following Lemma gives an easy condition, when a fixed point of $F$ as in (8) satisfies the conditions of Proposition 3.

If $v^{\prime}(\bar{x})$ only has eigenvalues with negative real-part at a stationary point $\bar{x}$, then Algorithm 1 is locally convergent to $\bar{x}$ for $h>0$ small enough.

Equation 10 shows that there are two major factors that determine the maximum possible step size $h$: (i) the maximum value of $\Re(\lambda)$ and (ii) the maximum value $q$ of $\left|{\Im(\lambda)}/{\Re(\lambda)}\right|$. Note that as $q$ goes to infinity, we have to choose $h$ according to $\mathcal{O}(q^{-2})$ which can quickly become extremely small. This is visualized in Figure 1: if $G^{\prime}(\bar{x})$ has an eigenvalue with small absolute real part but big imaginary part, $h$ needs to be chosen extremely small to still achieve convergence. Moreover, even if we make $h$ small enough, most eigenvalues of $F^{\prime}(\bar{x})$ will be very close to $1$, which leads by Proposition 3 to very slow convergence of the algorithm. This is in particular a problem of simultaneous gradient ascent for two-player games (in contrast to gradient ascent for local optimization), where the Jacobian $G^{\prime}(\bar{x})$ is not symmetric and can therefore have non-real eigenvalues.

Consensus Optimization

In this section, we derive the proposed method and analyze its convergence properties.

Finding stationary points of the vector field $v(x)$ is equivalent to solving the equation $v(x)=0$. In the context of two-player games this means solving the two equations

A simple strategy for finding such stationary points is to minimize $L(x)=\tfrac{1}{2}\|v(x)\|^{2}$ for $x$. Unfortunately, this can result in unstable stationary points of $v$ or other local minima of $\tfrac{1}{2}\|v(x)\|^{2}$ and in practice, we found it did not work well.

We therefore consider a modified vector field $w(x)$ that is as close as possible to the original vector field $v(x)$, but at the same time still minimizes $L(x)$ (at least locally). A sensible candidate for such a vector field is

for some $\gamma>0$. A simple calculation shows that the gradient $\nabla L(x)$ is given by

This vector field is the gradient vector field associated to the modified two-player game given by the two modified utility functions

The regularizer $L(\phi,\theta)$ encourages agreement between the two players. Therefore we call the resulting algorithm Consensus Optimization (Algorithm 2). This algorithm requires backpropagation through the squared norm of the gradient with respect to the weights of the network. This is sometimes called double backpropagation and is for example supported by the deep learning frameworks Tensorflow and PyTorch . As was pointed out by Ferenc Huzsár in one of his blog posts on www.inference.vc, naively implementing this algorithm in a mini-batch setting leads to biased estimates of $L(x)$. However, the bias goes down linearly with the batch size, which justifies the usage of consensus optimization in a mini-batch setting. Alternatively, it is possible to debias the estimate by subtracting a multiple of the sample variance of the gradients, see the supplementary material for details.

2 Convergence

For analyzing convergence, we consider a more general algorithm than in Section 4.1 which is given by iteratively applying a function $F$ of the form

for some step size $h>0$ and an invertible matrix $A(x)$ to $x$. Consensus optimization is a special case of this algorithm for A(x)=I-\gamma\,v^{\prime}(x)^{\mathchoice{\raisebox{-1.0pt}{\displaystyle\mathsf{T}}}{\raisebox{-1.0pt}{\textstyle\mathsf{T}}}{\raisebox{-1.0pt}{\scriptstyle\mathsf{T}}}{\raisebox{-1.0pt}{\scriptscriptstyle\mathsf{T}}}}. We assume that $\tfrac{1}{\gamma}$ is not an eigenvalue of v^{\prime}(x)^{\mathchoice{\raisebox{-1.0pt}{\displaystyle\mathsf{T}}}{\raisebox{-1.0pt}{\textstyle\mathsf{T}}}{\raisebox{-1.0pt}{\scriptstyle\mathsf{T}}}{\raisebox{-1.0pt}{\scriptscriptstyle\mathsf{T}}}} for any $x$, so that $A(x)$ is indeed invertible.

Assume $h>0$ and $A(x)$ invertible for all $x$. Then $\bar{x}$ is a fixed point of (15) if and only if it is a stationary point of $v$. Moreover, if $\bar{x}$ is a stationary point of $v$, we have

Let A(x)=I-\gamma v^{\prime}(x)^{\mathchoice{\raisebox{-1.0pt}{\displaystyle\mathsf{T}}}{\raisebox{-1.0pt}{\textstyle\mathsf{T}}}{\raisebox{-1.0pt}{\scriptstyle\mathsf{T}}}{\raisebox{-1.0pt}{\scriptscriptstyle\mathsf{T}}}} and assume that $v^{\prime}(\bar{x})$ is negative semi-definite and invertibleNote that $v^{\prime}(\bar{x})$ is usually not symmetric and therefore it is possible that $v^{\prime}(\bar{x})$ is negative semi-definite and invertible but not negative-definite. . Then $A(\bar{x})v^{\prime}(\bar{x})$ is negative definite.

As a consequence of Lemma 6 and Lemma 7, we can show local convergence of our algorithm to a local Nash equilibrium:

Let $v(x)$ be the associated gradient vector field of a two-player zero-sum game and A(x)=I-\gamma v^{\prime}(x)^{\mathchoice{\raisebox{-1.0pt}{\displaystyle\mathsf{T}}}{\raisebox{-1.0pt}{\textstyle\mathsf{T}}}{\raisebox{-1.0pt}{\scriptstyle\mathsf{T}}}{\raisebox{-1.0pt}{\scriptscriptstyle\mathsf{T}}}}. If $\bar{x}$ is a local Nash-equilibrium, then there is an open neighborhood $U$ of $\bar{x}$ so that for all $x_{0}\in U$, the iterates $F^{(k)}(x_{0})$ converge to $\bar{x}$ for $h>0$ small enough.

Our method solves the problem of eigenvalues of the Jacobian with (approximately) zero real-part. As the next Lemma shows, it also alleviates the problem of eigenvalues with a big imaginary-to-real-part-quotient:

Lemma 9 shows that the imaginary-to-real-part-quotient can be made arbitrarily small for an appropriate choice of $\gamma$. According to Proposition 3, this leads to better convergence properties near a local Nash-equilibrium.

Experiments

In our first experiment we evaluate our method on a simple $2D$-example where our goal is to learn a mixture of $8$ Gaussians with standard deviations equal to $10^{-2}$ and modes uniformly distributed around the unit circle. While simplistic, algorithms training GANs often fail to converge even on such simple examples without extensive fine-tuning of the architecture and hyper parameters .

For both the generator and critic we use fully connected neural networks with 4 hidden layers and $16$ hidden units in each layer. For all layers, we use RELU-nonlinearities. We use a $16$-dimensional Gaussian prior for the latent code $z$ and set up the game between the generator and critic using the utility functions as in . To test our method, we run both SimGA and our method with RMSProp and a learning rate of $10^{-4}$ for $20000$ steps. For our method, we use a regularization parameter of $\gamma=10$.

The results produced by SimGA and our method for , $5000$, $10000$ and $20000$ iterations are depicted in Figure 2. We see that while SimGA jumps around the modes of the distribution and fails to converge, our method converges smoothly to the target distribution (shown in red). Figure 3 shows the empirical distribution of the eigenvalues of the Jacobian of $v(x)$ and the regularized vector field $w(x)$. It can be seen that near the Nash-equilibrium most eigenvalues are indeed very close to the imaginary axis and that the proposed modification of the vector field used in consensus optimization moves the eigenvalues to the left.

CIFAR-10 and CelebA

In our second experiment, we apply our method to the cifar-10 and celebA-datasets, using a DC-GAN-like architecture without batch normalization in the generator or the discriminator. For celebA, we additionally use a constant number of filters in each layer and add additional RESNET-layers. These architectures are known to be hard to optimize using simultaneous (or alternating) gradient ascent .

Figure 4(a) and 4(b) depict samples from the model trained with our method. We see that our method successfully trains the models and we also observe that unlike when using alternating gradient ascent, the generator and discriminator losses remain almost constant during training. This is illustrated in Figure 5. For a quantitative evaluation, we also measured the inception-score over time (Figure 5(c)), showing that our method compares favorably to a DC-GAN trained with alternating gradient ascent. The improvement of consensus optimization over alternating gradient ascent is even more significant if we use $4$ instead of $3$ convolutional layers, see Figure 11 in the supplementary material for details.

Additional experimental results can be found in the supplementary material.

Discussion

While we could prove local convergence of our method in Section 4, we believe that even more insights can be gained by examining global convergence properties. In particular, our analysis from Section 4 cannot explain why the generator and discriminator losses remain almost constant during training.

Our theoretical results assume the existence of a Nash-equilibrium. When we are trying to minimize an f-divergence and the dimensionality of the generator distribution is misspecified, this might not be the case . Nonetheless, we found that our method works well in practice and we leave a closer theoretical investigation of this fact to future research.

In practice, our method can potentially make formerly instable stationary points of the gradient vector field stable if the regularization parameter is chosen to be high. This may lead to poor solutions. We also found that our method becomes less stable for deeper architectures, which we attribute to the fact that the gradients can have very different scales in such architectures, so that the simple L2-penalty from Section 4 needs to be rescaled accordingly.

Our method can be regarded as an approximation to the implicit Euler method for integrating the gradient vector field. It can be shown that the implicit Euler method has appealing stability properties that can be translated into convergence theorems for local Nash-equilibria. However, the implicit Euler method requires the solution of a nonlinear equation in each iteration. Nonetheless, we believe that further progress can be made by finding better approximations to the implicit Euler method.

An alternative interpretation is to view our method as a second order method. We hence believe that further progress can be made by revisiting second order optimization methods in the context of saddle point problems.

Related Work

Saddle point problems do not only arise in the context of training GANs. For example, the popular actor-critic models in reinforcement learning are also special cases of saddle-point problems.

Finding a stable algorithm for training GANs is a long standing problem and multiple solutions have been proposed. Unrolled GANs unroll the optimization with respect to the critic, thereby giving the generator more informative gradients. Though unrolling the optimization was shown to stabilize training, it can be cumbersome to implement and in addition it also results in a big model. As was recently shown, the stability of GAN-training can be improved by using objectives derived from the Wasserstein-1-distance (induced by the Kantorovich-Rubinstein-norm) instead of f-divergences . While Wasserstein-GANs often provide a good solution for the stable training of GANs, they require keeping the critic optimal, which can be time-consuming and can in practice only be achieved approximately, thus violating the conditions for theoretical guarantees. Moreover, some methods like Adversarial Variational Bayes explicitly prescribe the divergence measure to be used, thus making it impossible to apply Wasserstein-GANs. Other approaches that try to stabilize training, try to design an easy-to-optimize architecture or make use of additional labels .

In contrast to all the approaches described above, our work focuses on stabilizing training on a wide range of architecture and divergence functions.

Conclusion

In this work, starting from GAN objective functions we analyzed the general difficulties of finding local Nash-equilibria in smooth two-player games. We pinpointed the major numerical difficulties that arise in the current state-of-the-art algorithms and, using our insights, we presented a new algorithm for training generative adversarial networks. Our novel algorithm has favorable properties in theory and practice: from the theoretical viewpoint, we showed that it is locally convergent to a Nash-equilibrium even if the eigenvalues of the Jacobian are problematic. This is particularly interesting for games that arise in the context of GANs where such problems are common. From the practical viewpoint, our algorithm can be used in combination with any GAN-architecture whose objective can be formulated as a two-player game to stabilize the training. We demonstrated experimentally that our algorithm stabilizes the training and successfully combats training issues like mode collapse. We believe our work is a first step towards an understanding of the numerics of GAN training and more general deep learning objective functions.

Acknowledgements

This work was supported by Microsoft Research through its PhD Scholarship Programme.

References

Proofs

This section contains proofs that were omitted in the main text.

Hence, we have w^{\mathchoice{\raisebox{-1.0pt}{\displaystyle\mathsf{T}}}{\raisebox{-1.0pt}{\textstyle\mathsf{T}}}{\raisebox{-1.0pt}{\scriptstyle\mathsf{T}}}{\raisebox{-1.0pt}{\scriptscriptstyle\mathsf{T}}}}v^{\prime}(x)w<0 for all vectors $w\neq 0$ if and only if w_{1}^{\mathchoice{\raisebox{-1.0pt}{\displaystyle\mathsf{T}}}{\raisebox{-1.0pt}{\textstyle\mathsf{T}}}{\raisebox{-1.0pt}{\scriptstyle\mathsf{T}}}{\raisebox{-1.0pt}{\scriptscriptstyle\mathsf{T}}}}\nabla^{2}_{\phi}f(\phi,\theta)w_{1}<0 and w_{2}^{\mathchoice{\raisebox{-1.0pt}{\displaystyle\mathsf{T}}}{\raisebox{-1.0pt}{\textstyle\mathsf{T}}}{\raisebox{-1.0pt}{\scriptstyle\mathsf{T}}}{\raisebox{-1.0pt}{\scriptscriptstyle\mathsf{T}}}}\nabla^{2}_{\theta}f(\phi,\theta)w_{2}>0 for all vectors $w_{1},w_{2}\neq 0$.

This shows that $v^{\prime}(x)$ is negative definite if and only if $\nabla^{2}_{\phi}f(\phi,\theta)$ is negative definite and $\nabla^{2}_{\theta}f(\phi,\theta)$ is positive definite.

A similar proof shows that $v^{\prime}(x)$ is negative semi-definite if and only if $\nabla^{2}_{\phi}f(\phi,\theta)$ is negative semi-definite and $\nabla^{2}_{\theta}f(\phi,\theta)$ is positive semi-definite. ∎

If $\bar{x}$ is a local Nash-equilibrium, $\nabla^{2}_{\phi}f(\bar{\phi},\bar{\theta})$ is negative semi-definite and $\nabla^{2}_{\theta}f(\bar{\phi},\bar{\theta})$ is positive semi-definite, so $v^{\prime}(\bar{x})$ is negative definite by Lemma 1.

Conversely, if $v^{\prime}(\bar{x})$ is negative definite, $\nabla^{2}_{\phi}f(\bar{\phi},\bar{\theta})$ is negative definite and $\nabla^{2}_{\theta}f(\bar{\phi},\bar{\theta})$ positive definite by Lemma 1. This implies that $\bar{x}$ is a local Nash-equilibrium of the two-player game defined by $f$. ∎

Convergence theory

For $h>0$, this is smaller than $1$ if and only if

This is a direct consequence of Proposition 3 and Lemma 4. ∎

If $v(\bar{x})=0$, then $F(\bar{x})=\bar{x}$, so $\bar{x}$ is a fixed point of $F$. Conversely, if $\bar{x}$ satisfies $F(\bar{x})=\bar{x}$, we have $A(\bar{x})\,v(\bar{x})=0$. Because we assume $A(\bar{x})$ to be invertible, this shows $v(\bar{x})=0$.

Now, the $i^{th}$ partial derivative of $F(x)$ is given by

where $b_{i}$ denotes the $i^{th}$ unit basis vector. For a fixed point $\bar{x}$ we have by the first part of the proof $v(\bar{x})=0$ and therefore

as $v^{\prime}(\bar{x})w\neq 0$ for $w\neq 0$. ∎

This is a direct consequence of Proposition 3, Lemma 6 and Lemma 7. ∎

This implies, because $A$ is negative semi-definite, that

Because $\|Av\|^{2}\geq\rho\|v\|^{2}=\rho$ this implies the assertion. ∎

Additional Theoretical Results

This section contains some additional theoretical results. On the one hand, we demonstrate how the convergence of gradient ascent and common modifications like momentum and gradient rescaling can be analyzed naturally using Proposition 3. On the other hand, we analyze alternating gradient ascent for two-player games and show that for small step sizes $h>0$ it is locally convergent towards a Nash-equilibrium if all the eigenvalues of the Jacobian of the associated gradient vector field have negative real-part. We also discuss the bias of consensus optimization in a mini-batch setting and present a possible way to debias it.

Then $v^{\prime}(x)=\nabla^{2}f(x)$ is the Hessian-matrix of $f$ at $x$. Let

Any fixed point of (34) is a stationary point of the gradient vector field $v(x)$. Moreover, if $\nabla^{2}f(x)$ is negative definite, the fixed point iteration defined by $F$ is locally convergent towards $\bar{x}$ for small $h>0$.

This follows directly from Proposition 3. ∎

Momentum

Let $v(x)$ be a vector field. Using momentum, the operator $F$ can be written as

with $G(x,m)=(m,v(x)-\gamma\,m)$. The Jacobian of $G$ is given by

$\lambda$ is an eigenvalue of $G^{\prime}(x,m)$ if and only if $\lambda(\lambda+\gamma)$ is an eigenvalue of $v^{\prime}(x)$.

Let $(w_{1},w_{2})$ be an eigenvector of $G^{\prime}(x,m)$ as in (36) with associated eigenvalue $\lambda$. Then

showing that $\lambda(\lambda+\gamma)w_{1}=v^{\prime}(\bar{x})w_{1}$. As $w_{1}=0$ implies $w_{2}=0$, this shows that $w_{1}$ is an eigenvector of $v^{\prime}(\bar{x})$ with associated eigenvalue $\lambda(\lambda+\gamma)$.

Conversely, let $\lambda(\lambda+\gamma)$ be an eigenvalue of $v^{\prime}(x)$ to the eigenvector $w$. We have

showing that $\lambda$ is an eigenvalue of $G^{\prime}(x,m)$ to the eigenvector $(w,\lambda w)$. ∎

Any fixed point $(\bar{x},\bar{m})$ of (35) satisfies $\bar{m}=0$ and $v(\bar{x})=0$. Moreover, assume that $\gamma>0$ and that $v^{\prime}(\bar{x})$ only has real negative eigenvalues. Then the fixed point iteration defined by (35) is locally convergent towards $(\bar{x},\bar{m})$ for small $h>0$.

It is easy to see that any fixed point of (35) must satisfy $\bar{m}=0$ and $v(\bar{x})=0$. If all eigenvalues $\mu$ of $v^{\prime}(\bar{x})$ are real and non-positive, then all solutions to $\lambda(\lambda+\gamma)=\mu$ have negative real part, showing local convergence by Proposition 3. ∎

Note that the proof of Corollary 12 breaks down if $v^{\prime}(\bar{x})$ has complex eigenvalues, as it is often the case for the associated gradient vector field of two-player games.

Gradient Rescaling

In this section we investigate the effect of gradient rescaling as used in ADAM and RMSProp on local convergence. In particular, let

for some $\alpha>0$. The Jacobian of (40) is then given by

Any fixed point $(\bar{x},\bar{\beta})$ of (40) satisfies $\bar{\beta}=0$ and $v(\bar{x})=0$. Moreover, assume that $\alpha\in(0,1)$ and that all eigenvalues of $I+\frac{h}{\sqrt{\epsilon}}v^{\prime}(\bar{x})$ lie in the unit ball. Then the fixed point iteration defined by (40) is locally convergent towards $(\bar{x},\bar{\beta})$.

It is easy to see that any fixed point $(\bar{x},\bar{\beta})$ of (40) must satisfy $\bar{\beta}=0$ and $v(\bar{x})=0$. We therefore have

The eigenvalues of (42) are just the eigenvalues of $I+\frac{h}{\sqrt{\epsilon}}v^{\prime}(x)$ and $1-\alpha$ which all lie in the unit ball by assumption. ∎

Alternating Gradient Ascent

Alternating Gradient Ascent (AltGA) applies gradient ascent-updates for the two players in an alternating fashion, see Algorithm 3. For a theoretical analysis, we more generally regard fixed-point methods that iteratively apply a function of the form

to $x$. By the chain rule, the Jacobian of $F$ at $x$ is given by

Assume now that $F_{1}(x)=x+hG_{1}(x)$ and $F_{2}(x)=x+hG_{2}(x)$. Then, if $\bar{x}$ is a fixed point of both $F_{1}$ and $F_{2}$, we have

As a consequence, we the following analogue of Corollary 5:

If the Jacobian $v^{\prime}(\bar{x})$ of the gradient vector field $v(x)$ at a fixed point $\bar{x}$ only has eigenvalues with negative real part, Algorithm 3 is locally convergent to $\bar{x}$ for $h>0$ small enough.

This follows directly from the derivation above and Proposition 3. ∎

The bias in consensus optimization

To calculate $\nabla L(x)$ in consensus optimization, we need estimates of $L(x)$, which is defined as

In a mini-batch setting, we can obtain unbiased estimates of $v(x)$ by averaging all gradients $v_{i}(x)$ for the examples in the mini-batch:

However, when we substitute this estimate for $v(x)$ in the definition of $L(x)$, we obtain a biased estimator of $L(x)$ as the next lemma shows. The lemma also gives an explicit expression for the bias.

Assume that $v_{i}(x)$, $i=1,\dots,B$, are independent and identically distributed unbiased estimates of $v(x)$, i.e. $\operatorname{E}[v_{i}(x)]=v(x)$ for all $i$. Let

Then $L_{B}(x)$ is a biased estimator of $L(x)$ with

Note that the bias is going down linearly with the batch size. In practice, we found that a batch size of $64$ is usually sufficient to make consensus optimization work.

Alternatively, as was also noted by Ferenc Huszár in a blog post on www.inference.vc, it is possible to obtain unbiased estimates of $L(x)$ by subtracting $1/{(2B-2)}$ times the sample variance of the $v_{i}(x)$ from $L_{B}(x)$.

We leave a closer investigation of the benefits and disadvantages of this variant of consensus optimization to future research.

Additional Experimental Results

Effect of Hyperparameters