GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium

Introduction

Generative adversarial networks (GANs) have achieved outstanding results in generating realistic images and producing text . GANs can learn complex generative models for which maximum likelihood or a variational approximations are infeasible. Instead of the likelihood, a discriminator network serves as objective for the generative model, that is, the generator. GAN learning is a game between the generator, which constructs synthetic data from random variables, and the discriminator, which separates synthetic data from real world data. The generator’s goal is to construct data in such a way that the discriminator cannot tell them apart from real world data. Thus, the discriminator tries to minimize the synthetic-real discrimination error while the generator tries to maximize this error. Since training GANs is a game and its solution is a Nash equilibrium, gradient descent may fail to converge . Only local Nash equilibria are found, because gradient descent is a local optimization method. If there exists a local neighborhood around a point in parameter space where neither the generator nor the discriminator can unilaterally decrease their respective losses, then we call this point a local Nash equilibrium.

To characterize the convergence properties of training general GANs is still an open challenge . For special GAN variants, convergence can be proved under certain assumptions . A prerequisit for many convergence proofs is local stability which was shown for GANs by Nagarajan and Kolter for a min-max GAN setting. However, Nagarajan and Kolter require for their proof either rather strong and unrealistic assumptions or a restriction to a linear discriminator. Recent convergence proofs for GANs hold for expectations over training samples or for the number of examples going to infinity , thus do not consider mini-batch learning which leads to a stochastic gradient .

Recently actor-critic learning has been analyzed using stochastic approximation. Prasad et al. showed that a two time-scale update rule ensures that training reaches a stationary local Nash equilibrium if the critic learns faster than the actor. Convergence was proved via an ordinary differential equation (ODE), whose stable limit points coincide with stationary local Nash equilibria. We follow the same approach. We prove that GANs converge to a local Nash equilibrium when trained by a two time-scale update rule (TTUR), i.e., when discriminator and generator have separate learning rates. This also leads to better results in experiments. The main premise is that the discriminator converges to a local minimum when the generator is fixed. If the generator changes slowly enough, then the discriminator still converges, since the generator perturbations are small. Besides ensuring convergence, the performance may also improve since the discriminator must first learn new patterns before they are transferred to the generator. In contrast, a generator which is overly fast, drives the discriminator steadily into new regions without capturing its gathered information. In recent GAN implementations, the discriminator often learned faster than the generator. A new objective slowed down the generator to prevent it from overtraining on the current discriminator . The Wasserstein GAN algorithm uses more update steps for the discriminator than for the generator . We compare TTUR and standard GAN training. Fig. 1 shows at the left panel a stochastic gradient example on CelebA for original GAN training (orig), which often leads to oscillations, and the TTUR. On the right panel an example of a 4 node network flow problem of Zhang et al. is shown. The distance between the actual parameter and its optimum for an one time-scale update rule is shown across iterates. When the upper bounds on the errors are small, the iterates return to a neighborhood of the optimal solution, while for large errors the iterates may diverge (see also Appendix Section A2.3).

Our novel contributions in this paper are:

We proof that GANs trained with TTUR converge to a stationary local Nash equilibrium,

The description of Adam as heavy ball with friction and the resulting second order differential equation,

The convergence of GANs trained with TTUR and Adam to a stationary local Nash equilibrium,

We introduce the “Fréchet Inception Distance” (FID) to evaluate GANs, which is more consistent than the Inception Score.

Two Time-Scale Update Rule for GANs

For more details on the following convergence proof and its assumptions see Appendix Section A2.1. To prove convergence of GANs learned by TTUR, we make the following assumptions (The actual assumption is ended by $\blacktriangleleft$, the following text are just comments and explanations):

The gradients $\bm{h}$ and $\bm{g}$ are Lipschitz. $\blacktriangleleft$ Consequently, networks with Lipschitz smooth activation functions like ELUs ($\alpha=1$) fulfill the assumption but not ReLU networks.

For each $\bm{\theta}$, the ODE \dot{\bm{w}}(t)=\bm{g}\big{(}\bm{\theta},\bm{w}(t)\big{)} has a local asymptotically stable attractor $\bm{\lambda}(\bm{\theta})$ within a domain of attraction $G_{\theta}$ such that $\bm{\lambda}$ is Lipschitz. The ODE \dot{\bm{\theta}}(t)=\bm{h}\big{(}\bm{\theta}(t),\bm{\lambda}(\bm{\theta}(t))\big{)} has a local asymptotically stable attractor $\bm{\theta}^{*}$ within a domain of attraction.$\blacktriangleleft$ The discriminator must converge to a minimum for fixed generator parameters and the generator, in turn, must converge to a minimum for this fixed discriminator minimum. Borkar 1997 required unique global asymptotically stable equilibria . The assumption of global attractors was relaxed to local attractors via Assumption (A6) and Theorem 2.7 in Karmakar & Bhatnagar . See for more details Assumption (A6) in the Appendix Section A2.1.3. Here, the GAN objectives may serve as Lyapunov functions. These assumptions of locally stable ODEs can be ensured by an additional weight decay term in the loss function which increases the eigenvalues of the Hessian. Therefore, problems with a region-wise constant discriminator that has zero second order derivatives are avoided. For further discussion see Appendix Section A2 (C3).

$\sup_{n}\|\bm{\theta}_{n}\|<\infty$ and $\sup_{n}\|\bm{w}_{n}\|<\infty$.$\blacktriangleleft$ Typically ensured by the objective or a weight decay term.

The next theorem has been proved in the seminal paper of Borkar 1997 .

If the assumptions are satisfied, then the updates Eq. (1) converge to $(\bm{\theta}^{*},\bm{\lambda}(\bm{\theta}^{*}))$ a.s.

The solution $(\bm{\theta}^{*},\bm{\lambda}(\bm{\theta}^{*}))$ is a stationary local Nash equilibrium , since $\bm{\theta}^{*}$ as well as $\bm{\lambda}(\bm{\theta}^{*})$ are local asymptotically stable attractors with \bm{g}\big{(}\bm{\theta}^{*},\bm{\lambda}(\bm{\theta}^{*})\big{)}=\bm{0} and \bm{h}\big{(}\bm{\theta}^{*},\bm{\lambda}(\bm{\theta}^{*})\big{)}=\bm{0}. An alternative approach to the proof of convergence using the Poisson equation for ensuring a solution to the fast update rule can be found in the Appendix Section A2.1.2. This approach assumes a linear update function in the fast update rule which, however, can be a linear approximation to a nonlinear gradient . For the rate of convergence see Appendix Section A2.2, where Section A2.2.1 focuses on linear and Section A2.2.2 on non-linear updates. For equal time-scales it can only be proven that the updates revisit an environment of the solution infinitely often, which, however, can be very large . For more details on the analysis of equal time-scales see Appendix Section A2.3. The main idea of the proof of Borkar is to use $(T,\delta)$ perturbed ODEs according to Hirsch 1989 (see also Appendix Section C of Bhatnagar, Prasad, & Prashanth 2013 ). The proof relies on the fact that there eventually is a time point when the perturbation of the slow update rule is small enough (given by $\delta$) to allow the fast update rule to converge. For experiments with TTUR, we aim at finding learning rates such that the slow update is small enough to allow the fast to converge. Typically, the slow update is the generator and the fast update the discriminator. We have to adjust the two learning rates such that the generator does not affect discriminator learning in a undesired way and perturb it too much. However, even a larger learning rate for the generator than for the discriminator may ensure that the discriminator has low perturbations. Learning rates cannot be translated directly into perturbation since the perturbation of the discriminator by the generator is different from the perturbation of the generator by the discriminator.

Adam Follows an HBF ODE and Ensures TTUR Convergence

[3,r, ,[Heavy Ball with Friction]Heavy Ball with Friction, where the ball with mass overshoots the local minimum $\bm{\theta}^{+}$ and settles at the flat minimum $\bm{\theta}^{*}$. ] In our experiments, we aim at using Adam stochastic approximation to avoid mode collapsing. GANs suffer from “mode collapsing” where large masses of probability are mapped onto a few modes that cover only small regions. While these regions represent meaningful samples, the variety of the real world data is lost and only few prototype samples are generated. Different methods have been proposed to avoid mode collapsing . We obviate mode collapsing by using Adam stochastic approximation . Adam can be described as Heavy Ball with Friction (HBF) (see below), since it averages over past gradients. This averaging corresponds to a velocity that makes the generator resistant to getting pushed into small regions. Adam as an HBF method typically overshoots small local minima that correspond to mode collapse and can find flat minima which generalize well . Fig. Adam Follows an HBF ODE and Ensures TTUR Convergence depicts the dynamics of HBF, where the ball settles at a flat minimum. Next, we analyze whether GANs trained with TTUR converge when using Adam. For more details see Appendix Section A3.

We recapitulate the Adam update rule at step $n$, with learning rate $a$, exponential averaging factors $\beta_{1}$ for the first and $\beta_{2}$ for the second moment of the gradient $\nabla f(\bm{\theta}_{n-1})$:

where following operations are meant componentwise: the product $\odot$, the square root $\sqrt{.}$, and the division $/$ in the last line. Instead of learning rate $a$, we introduce the damping coefficient $a(n)$ with $a(n)=an^{-\tau}$ for $\tau\in(0,1]$. Adam has parameters $\beta_{1}$ for averaging the gradient and $\beta_{2}$ parametrized by a positive $\alpha$ for averaging the squared gradient. These parameters can be considered as defining a memory for Adam. To characterize $\beta_{1}$ and $\beta_{2}$ in the following, we define the exponential memory $r(n)=r$ and the polynomial memory $r(n)=r/\sum_{l=1}^{n}a(l)$ for some positive constant $r$. The next theorem describes Adam by a differential equation, which in turn allows to apply the idea of $(T,\delta)$ perturbed ODEs to TTUR. Consequently, learning GANs with TTUR and Adam converges.

If Adam is used with $\beta_{1}=1-a(n+1)r(n)$, $\beta_{2}=1-\alpha a(n+1)r(n)$ and with $\nabla f$ as the full gradient of the lower bounded, continuously differentiable objective $f$, then for stationary second moments of the gradient, Adam follows the differential equation for Heavy Ball with Friction (HBF):

Adam converges for gradients $\nabla f$ that are $L$-Lipschitz.

Gadat et al. derived a discrete and stochastic version of Polyak’s Heavy Ball method , the Heavy Ball with Friction (HBF) :

According to Attouch et al. the energy, that is, a Lyapunov function, is $E(t)=1/2|\dot{\bm{\theta}}(t)|^{2}+f(\bm{\theta}(t))$ and $\dot{E}(t)=-a\ |\dot{\bm{\theta}}(t)|^{2}<0$. Since Adam can be expressed as differential equation and has a Lyapunov function, the idea of $(T,\delta)$ perturbed ODEs carries over to Adam. Therefore the convergence of Adam with TTUR can be proved via two time-scale stochastic approximation analysis like in Borkar for stationary second moments of the gradient.

In the Appendix we further discuss the convergence of two time-scale stochastic approximation algorithms with additive noise, linear update functions depending on Markov chains, nonlinear update functions, and updates depending on controlled Markov processes. Futhermore, the Appendix presents work on the rate of convergence for both linear and nonlinear update rules using similar techniques as the local stability analysis of Nagarajan and Kolter . Finally, we elaborate more on equal time-scale updates, which are investigated for saddle point problems and actor-critic learning.

Experiments

Before presenting the experiments, we introduce a quality measure for models learned by GANs. The objective of generative learning is that the model produces data which matches the observed data. Therefore, each distance between the probability of observing real world data $p_{w}(.)$ and the probability of generating model data $p(.)$ can serve as performance measure for generative models. However, defining appropriate performance measures for generative models is difficult . The best known measure is the likelihood, which can be estimated by annealed importance sampling . However, the likelihood heavily depends on the noise assumptions for the real data and can be dominated by single samples . Other approaches like density estimates have drawbacks, too . A well-performing approach to measure the performance of GANs is the “Inception Score” which correlates with human judgment . Generated samples are fed into an inception model that was trained on ImageNet. Images with meaningful objects are supposed to have low label (output) entropy, that is, they belong to few object classes. On the other hand, the entropy across images should be high, that is, the variance over the images should be large. Drawback of the Inception Score is that the statistics of real world samples are not used and compared to the statistics of synthetic samples. Next, we improve the Inception Score. The equality $p(.)=p_{w}(.)$ holds except for a non-measurable set if and only if $\int p(.)f(x)dx=\int p_{w}(.)f(x)dx$ for a basis $f(.)$ spanning the function space in which $p(.)$ and $p_{w}(.)$ live. These equalities of expectations are used to describe distributions by moments or cumulants, where $f(x)$ are polynomials of the data $x$. We generalize these polynomials by replacing $x$ by the coding layer of an inception model in order to obtain vision-relevant features. For practical reasons we only consider the first two polynomials, that is, the first two moments: mean and covariance. The Gaussian is the maximum entropy distribution for given mean and covariance, therefore we assume the coding units to follow a multidimensional Gaussian. The difference of two Gaussians (synthetic and real-world images) is measured by the Fréchet distance also known as Wasserstein-2 distance . We call the Fréchet distance $d(.,.)$ between the Gaussian with mean $(\bm{m},\bm{C})$ obtained from $p(.)$ and the Gaussian with mean $(\bm{m}_{w},\bm{C}_{w})$ obtained from $p_{w}(.)$ the “Fréchet Inception Distance” (FID), which is given by :

Next we show that the FID is consistent with increasing disturbances and human judgment. Fig. 2 evaluates the FID for Gaussian noise, Gaussian blur, implanted black rectangles, swirled images, salt and pepper noise, and CelebA dataset contaminated by ImageNet images. The FID captures the disturbance level very well. In the experiments we used the FID to evaluate the performance of GANs. For more details and a comparison between FID and Inception Score see Appendix Section A1, where we show that FID is more consistent with the noise level than the Inception Score.

We compare the two time-scale update rule (TTUR) for GANs with the original GAN training to see whether TTUR improves the convergence speed and performance of GANs. We have selected Adam stochastic optimization to reduce the risk of mode collapsing. The advantage of Adam has been confirmed by MNIST experiments, where Adam indeed considerably reduced the cases for which we observed mode collapsing. Although TTUR ensures that the discriminator converges during learning, practicable learning rates must be found for each experiment. We face a trade-off since the learning rates should be small enough (e.g. for the generator) to ensure convergence but at the same time should be large enough to allow fast learning. For each of the experiments, the learning rates have been optimized to be large while still ensuring stable training which is indicated by a decreasing FID or Jensen-Shannon-divergence (JSD). We further fixed the time point for stopping training to the update step when the FID or Jensen-Shannon-divergence of the best models was no longer decreasing. For some models, we observed that the FID diverges or starts to increase at a certain time point. An example of this behaviour is shown in Fig. 4. The performance of generative models is evaluated via the Fréchet Inception Distance (FID) introduced above. For the One Billion Word experiment, the normalized JSD served as performance measure. For computing the FID, we propagated all images from the training dataset through the pretrained Inception-v3 model following the computation of the Inception Score , however, we use the last pooling layer as coding layer. For this coding layer, we calculated the mean $\bm{m}_{w}$ and the covariance matrix $\bm{C}_{w}$. Thus, we approximate the first and second central moment of the function given by the Inception coding layer under the real world distribution. To approximate these moments for the model distribution, we generate 50,000 images, propagate them through the Inception-v3 model, and then compute the mean $\bm{m}$ and the covariance matrix $\bm{C}$. For computational efficiency, we evaluate the FID every 1,000 DCGAN mini-batch updates, every 5,000 WGAN-GP outer iterations for the image experiments, and every 100 outer iterations for the WGAN-GP language model. For the one time-scale updates a WGAN-GP outer iteration for the image model consists of five discriminator mini-batches and ten discriminator mini-batches for the language model, where we follow the original implementation. For TTUR however, the discriminator is updated only once per iteration. We repeat the training for each single time-scale (orig) and TTUR learning rate eight times for the image datasets and ten times for the language benchmark. Additionally to the mean FID training progress we show the minimum and maximum FID over all runs at each evaluation time-step. For more details, implementations and further results see Appendix Section A4 and A6.

We first want to demonstrate the difference between a single time-scale update rule and TTUR on a simple toy min/max problem where a saddle point should be found. The objective $f(x,y)=(1+x^{2})(100-y^{2})$ in Fig. 3 (left) has a saddle point at $(x,y)=(0,0)$ and fulfills assumption A4. The norm $\|(x,y)\|$ measures the distance of the parameter vector $(x,y)$ to the saddle point. We update $(x,y)$ by gradient descent in $x$ and gradient ascent in $y$ using additive Gaussian noise in order to simulate a stochastic update. The updates should converge to the saddle point $(x,y)=(0,0)$ with objective value $f(0,0)=100$ and the norm . In Fig. 3 (right), the first two rows show one time-scale update rules. The large learning rate in the first row diverges and has large fluctuations. The smaller learning rate in the second row converges but slower than the TTUR in the third row which has slow $x$-updates. TTUR with slow $y$-updates in the fourth row also converges but slower.

We test TTUR for the deep convolutional GAN (DCGAN) at the CelebA, CIFAR-10, SVHN and LSUN Bedrooms dataset. Fig. 4 shows the FID during learning with the original learning method (orig) and with TTUR. The original training method is faster at the beginning, but TTUR eventually achieves better performance. DCGAN trained TTUR reaches constantly a lower FID than the original method and for CelebA and LSUN Bedrooms all one time-scale runs diverge. For DCGAN the learning rate of the generator is larger then that of the discriminator, which, however, does not contradict the TTUR theory (see the Appendix Section A5). In Table 1 we report the best FID with TTUR and one time-scale training for optimized number of updates and learning rates. TTUR constantly outperforms standard training and is more stable.

We used the WGAN-GP image model to test TTUR with the CIFAR-10 and LSUN Bedrooms datasets. In contrast to the original code where the discriminator is trained five times for each generator update, TTUR updates the discriminator only once, therefore we align the training progress with wall-clock time. The learning rate for the original training was optimized to be large but leads to stable learning. TTUR can use a higher learning rate for the discriminator since TTUR stabilizes learning. Fig. 5 shows the FID during learning with the original learning method and with TTUR. Table 1 shows the best FID with TTUR and one time-scale training for optimized number of iterations and learning rates. Again TTUR reaches lower FIDs than one time-scale training.

Finally the One Billion Word Benchmark serves to evaluate TTUR on WGAN-GP. The character-level generative language model is a 1D convolutional neural network (CNN) which maps a latent vector to a sequence of one-hot character vectors of dimension 32 given by the maximum of a softmax output. The discriminator is also a 1D CNN applied to sequences of one-hot vectors of 32 characters. Since the FID criterium only works for images, we measured the performance by the Jensen-Shannon-divergence (JSD) between the model and the real world distribution as has been done previously . In contrast to the original code where the critic is trained ten times for each generator update, TTUR updates the discriminator only once, therefore we align the training progress with wall-clock time. The learning rate for the original training was optimized to be large but leads to stable learning. TTUR can use a higher learning rate for the discriminator since TTUR stabilizes learning. We report for the 4 and 6-gram word evaluation the normalized mean JSD for ten runs for original training and TTUR training in Fig. 6. In Table 1 we report the best JSD at an optimal time-step where TTUR outperforms the standard training for both measures. The improvement of TTUR on the 6-gram statistics over original training shows that TTUR enables to learn to generate more subtle pseudo-words which better resembles real words.

Conclusion

For learning GANs, we have introduced the two time-scale update rule (TTUR), which we have proved to converge to a stationary local Nash equilibrium. Then we described Adam stochastic optimization as a heavy ball with friction (HBF) dynamics, which shows that Adam converges and that Adam tends to find flat minima while avoiding small local minima. A second order differential equation describes the learning dynamics of Adam as an HBF system. Via this differential equation, the convergence of GANs trained with TTUR to a stationary local Nash equilibrium can be extended to Adam. Finally, to evaluate GANs, we introduced the ‘Fréchet Inception Distance” (FID) which captures the similarity of generated images to real ones better than the Inception Score. In experiments we have compared GANs trained with TTUR to conventional GAN training with a one time-scale update rule on CelebA, CIFAR-10, SVHN, LSUN Bedrooms, and the One Billion Word Benchmark. TTUR outperforms conventional GAN training consistently in all experiments.

Acknowledgment

This work was supported by NVIDIA Corporation, Bayer AG with Research Agreement 09/2017, Zalando SE with Research Agreement 01/2016, Audi.JKU Deep Learning Center, Audi Electronic Venture GmbH, IWT research grant IWT150865 (Exaptation), H2020 project grant 671555 (ExCAPE) and FWF grant P 28660-N31.

References

The references are provided after Section References.

Appendix

A1 Fréchet Inception Distance (FID)

We improve the Inception score for comparing the results of GANs . The Inception score has the disadvantage that it does not use the statistics of real world samples and compare it to the statistics of synthetic samples. Let $p(.)$ be the distribution of model samples and $p_{w}(.)$ the distribution of the samples from real world. The equality $p(.)=p_{w}(.)$ holds except for a non-measurable set if and only if $\int p(.)f(x)dx=\int p_{w}(.)f(x)dx$ for a basis $f(.)$ spanning the function space in which $p(.)$ and $p_{w}(.)$ live. These equalities of expectations are used to describe distributions by moments or cumulants, where $f(x)$ are polynomials of the data $x$. We replacing $x$ by the coding layer of an Inception model in order to obtain vision-relevant features and consider polynomials of the coding unit functions. For practical reasons we only consider the first two polynomials, that is, the first two moments: mean and covariance. The Gaussian is the maximum entropy distribution for given mean and covariance, therefore we assume the coding units to follow a multidimensional Gaussian. The difference of two Gaussians is measured by the Fréchet distance also known as Wasserstein-2 distance . The Fréchet distance $d(.,.)$ between the Gaussian with mean and covariance $(\bm{m},\bm{C})$ obtained from $p(.)$ and the Gaussian $(\bm{m}_{w},\bm{C}_{w})$ obtained from $p_{w}(.)$ is called the “Fréchet Inception Distance” (FID), which is given by :

Next we show that the FID is consistent with increasing disturbances and human judgment on the CelebA dataset. We computed the $(\bm{m}_{w},\bm{C}_{w})$ on all CelebA images, while for computing $(\bm{m},\bm{C})$ we used 50,000 randomly selected samples. We considered following disturbances of the image $\bm{X}$:

Gaussian noise: We constructed a matrix $\bm{N}$ with Gaussian noise scaled to $$. The noisy image is computed as$(1-\alpha)\bm{X}+\alpha\bm{N}$for$\alpha\in\{0,0.25,0.5,0.75\}$. The larger$\alpha$ is, the larger is the noise added to the image, the larger is the disturbance of the image.

Gaussian blur: The image is convolved with a Gaussian kernel with standard deviation $\alpha\in\{0,1,2,4\}$. The larger $\alpha$ is, the larger is the disturbance of the image, that is, the more the image is smoothed.

Black rectangles: To an image five black rectangles are are added at randomly chosen locations. The rectangles cover parts of the image. The size of the rectangles is $\alpha\text{imagesize}$ with $\alpha\in\{0,0.25,0.5,0.75\}$. The larger $\alpha$ is, the larger is the disturbance of the image, that is, the more of the image is covered by black rectangles.

Salt and pepper noise: Some pixels of the image are set to black or white, where black is chosen with 50% probability (same for white). Pixels are randomly chosen for being flipped to white or black, where the ratio of pixel flipped to white or black is given by the noise level $\alpha\in\{0,0.1,0.2,0.3\}$. The larger $\alpha$ is, the larger is the noise added to the image via flipping pixels to white or black, the larger is the disturbance level.

ImageNet contamination: From each of the 1,000 ImageNet classes, 5 images are randomly chosen, which gives 5,000 ImageNet images. The images are ensured to be RGB and to have a minimal size of 256x256. A percentage of $\alpha\in\{0,0.25,0.5,0.75\}$ of the CelebA images has been replaced by ImageNet images. $\alpha=0$ means all images are from CelebA, $\alpha=0.25$ means that 75% of the images are from CelebA and 25% from ImageNet etc. The larger $\alpha$ is, the larger is the disturbance of the CelebA dataset by contaminating it by ImageNet images. The larger the disturbance level is, the more the dataset deviates from the reference real world dataset.

We compare the Inception Score with the FID. The Inception Score with $m$ samples and $K$ classes is

The FID is a distance, while the Inception Score is a score. To compare FID and Inception Score, we transform the Inception Score to a distance, which we call “Inception Distance” (IND). This transformation to a distance is possible since the Inception Score has a maximal value. For zero probability $p(y_{k}\mid\bm{X}_{i})=0$, we set the value $p(y_{k}\mid\bm{X}_{i})\log\frac{p(y_{k}\mid\bm{X}_{i})}{p(y_{k})}=0$. We can bound the $\log$-term by

Using this bound, we obtain an upper bound on the Inception Score:

The upper bound is tight and achieved if $m\leqslant K$ and every sample is from a different class and the sample is classified correctly with probability 1. The IND is computed “IND = $m$ - Inception Score”, therefore the IND is zero for a perfect subset of the ImageNet with $m<K$ samples, where each sample stems from a different class. Therefore both distances should increase with increasing disturbance level. In Figure A7 we present the evaluation for each kind of disturbance. The larger the disturbance level is, the larger the FID and IND should be. In Figure A8, A9, A10, and A10 we show examples of images generated with DCGAN trained on CelebA with FIDs 500, 300, 133, 100, 45, 13, and FID 3 achieved with WGAN-GP on CelebA.

A2 Two Time-Scale Stochastic Approximation Algorithms

Stochastic approximation algorithms are iterative procedures to find a root or a stationary point (minimum, maximum, saddle point) of a function when only noisy observations of its values or its derivatives are provided. Two time-scale stochastic approximation algorithms are two coupled iterations with different step sizes. For proving convergence of these interwoven iterates it is assumed that one step size is considerably smaller than the other. The slower iterate (the one with smaller step size) is assumed to be slow enough to allow the fast iterate converge while being perturbed by the the slower. The perturbations of the slow should be small enough to ensure convergence of the faster.

$a(n)$: step size for the slow iterate Eq. (13),

$b(n)$: step size for the fast iterate Eq. (14),

$\bm{M}^{(\theta)}_{n}$: additive random Markov process for the slow iterate Eq. (13),

$\bm{M}^{(w)}_{n}$: additive random Markov process for the fast iterate Eq. (14),

$\bm{Z}^{(\theta)}_{n}$: random Markov process for the slow iterate Eq. (13),

$\bm{Z}^{(w)}_{n}$: random Markov process for the fast iterate Eq. (14).

The first result is from Borkar 1997 which was generalized in Konda and Borkar 1999 . Borkar considered the iterates:

Assumptions on the noise: For the increasing $\sigma$-field

the sequences of random variables $(\bm{M}^{(\theta)}_{n},\mathcal{F}_{n})$ and $(\bm{M}^{(w)}_{n},\mathcal{F}_{n})$ satisfy

Assumption on the existence of a solution of the slow iterate: The ODE

has a unique global asymptotically stable equilibrium $\bm{\theta}^{*}$.

If the assumptions are satisfied, then the iterates Eq. (15) and Eq. (16) converge to $(\bm{\theta}^{*},\bm{\lambda}(\bm{\theta}^{*}))$ a.s.

According to Lemma 2 in Assumption (A3) is fulfilled if $\{\bm{M}^{(\theta)}_{n}\}$ is a martingale difference sequence w.r.t $\mathcal{F}_{n}$ with

and $\{\bm{M}^{(w)}_{n}\}$ is a martingale difference sequence w.r.t $\mathcal{F}_{n}$ with

where $B_{1}$ and $B_{2}$ are positive deterministic constants.

We address assumption (A4) with weight decay in two ways: (I) Weight decay avoids problems with a discriminator that is region-wise constant and, therefore, does not have a locally stable generator. If the generator is perfect, then the discriminator is 0.5 everywhere. For generator with mode collapse, (i) the discriminator is 1 in regions without generator examples, (ii) 0 in regions with generator examples only, (iii) is equal to the local ratio of real world examples for regions with generator and real world examples. Since the discriminator is locally constant, the generator has gradient zero and cannot improve. Also the discriminator cannot improve, since it has minimal error given the current generator. However, without weight decay the Nash Equilibrium is not stable since the second order derivatives are zero, too. (II) Weight decay avoids that the generator is driven to infinity with unbounded weights. For example a linear discriminator can supply a gradient for the generator outside each bounded region.

The main result used in the proof of the theorem relies on work on perturbations of ODEs according to Hirsch 1989 .

Konda and Borkar 1999 generalized the convergence proof to distributed asynchronous update rules.

Tadić relaxed the assumptions for showing convergence . In particular the noise assumptions (Assumptions A2 in ) do not have to be martingale difference sequences and are more general than in . In another result the assumption of bounded iterates is not necessary if other assumptions are ensured . Finally, Tadić considers the case of non-additive noise . Tadić does not provide proofs for his results. We were not able to find such proofs even in other publications of Tadić.

A2.1.2 Linear Update, Additive Noise, and Markov Chain

In contrast to the previous subsection, we assume that an additional Markov chain influences the iterates . The Markov chain allows applications in reinforcement learning, in particular in actor-critic setting where the Markov chain is used to model the environment. The slow iterate is the actor update while the fast iterate is the critic update. For reinforcement learning both the actor and the critic observe the environment which is driven by the actor actions. The environment observations are assumed to be a Markov chain. The Markov chain can include eligibility traces which are modeled as explicit states in order to keep the Markov assumption.

The Markov chain is the sequence of observations of the environment which progresses via transition probabilities. The transitions are not affected by the critic but by the actor.

We define for every measurable function $f$

Assumptions on the noise: The sequence $\bm{M}^{(w)}_{n}$ is a $k\times k$-matrix valued $\mathcal{F}_{n}$-martingale difference with bounded moments:

We assume slowly changing $\bm{\theta}$, therefore the random process $\bm{H}_{n}$ satisfies

Assumptions on the update functions and solutions to the Poisson equation:

Boundedness of solutions: For some constant $C$ and for all $\bm{\theta}$:

Boundedness in expectation: All moments are bounded. For any $d>0$, there exists $C_{d}>0$ such that

Function $C(.)$ gives the Lipschitz constant for every $\bm{z}$:

We report Theorem 3.2 (see also Theorem 7 in ) and Theorem 3.13 from :

If the assumptions are satisfied, then for the iterates Eq. (26) and Eq. (27) holds:

The proofs only use the boundedness of the moments of $\bm{H}_{n}$ , therefore $\bm{H}_{n}$ may depend on $\bm{w}_{n}$. In his PhD thesis , Vijaymohan Konda used this framework for the actor-critic learning, where $\bm{H}_{n}$ drives the updates of the actor parameters $\bm{\theta}_{n}$. However, the actor updates are based on the current parameters $\bm{w}_{n}$ of the critic.

The random process $\bm{Z}^{(w)}_{n}$ can affect $\bm{H}_{n}$ as long as boundedness is ensured.

Nonlinear update rule. \bm{g}\big{(}\bm{Z}^{(w)}_{n};\bm{\theta}_{n}\big{)}\ +\ \bm{G}\big{(}\bm{Z}^{(w)}_{n};\bm{\theta}_{n}\big{)}\bm{w}_{n} can be viewed as a linear approximation of a nonlinear update rule. The nonlinear case has been considered in where additional approximation errors due to linearization were addressed. These errors are treated in the given framework .

A2.1.3 Additive Noise and Controlled Markov Processes

The most general iterates use nonlinear update functions $\bm{g}$ and $\bm{h}$, have additive noise, and have controlled Markov processes .

is guaranteed to have at least one solution that is absolutely continuous. If $\bm{\Theta}$ is an absolutely continuous map satisfying Eq. (52) then we say that $\bm{\Theta}\in\bm{\Sigma}$.

Assumptions on the controlled Markov processes: The controlled Markov process $\{\bm{Z}^{(w)}_{n}\}$ takes values in a compact metric space $S^{(w)}$. The controlled Markov process $\{\bm{Z}^{(\theta)}_{n}\}$ takes values in a compact metric space $S^{(\theta)}$. Both processes are controlled by the iterate sequences $\{\bm{\theta}_{n}\}$ and $\{\bm{w}_{n}\}$. Furthermore $\{\bm{Z}^{(w)}_{n}\}$ is additionally controlled by a random process $\{\bm{A}^{(w)}_{n}\}$ taking values in a compact metric space $U^{(w)}$ and $\{\bm{Z}^{(\theta)}_{n}\}$ is additionally controlled by a random process $\{\bm{A}^{(\theta)}_{n}\}$ taking values in a compact metric space $U^{(\theta)}$. The $\{\bm{Z}^{(\theta)}_{n}\}$ dynamics is

for $B^{(\theta)}$ Borel in $S^{(\theta)}$. The $\{\bm{Z}^{(w)}_{n}\}$ dynamics is

Note that the Lipschitz constant $L^{(\theta)}$ does not depend on $\bm{z}^{(\theta)}$.

Note that the Lipschitz constant $L^{(w)}$ does not depend on $\bm{z}^{(w)}$.

Assumptions on the additive noise: $\{\bm{M}^{(\theta)}_{n}\}$ and $\{\bm{M}^{(w)}_{n}\}$ are martingale difference sequence with second moments bounded by $K(1+\|\bm{\theta}_{n}\|^{2}+\|\bm{w}_{n}\|^{2})$. More precisely, $\{\bm{M}^{(\theta)}_{n}\}$ is a martingale difference sequence w.r.t. increasing $\sigma$-fields

for $n\geqslant 0$ and a given constant $K>0$.

$\{\bm{M}^{(w)}_{n}\}$ is a martingale difference sequence w.r.t. increasing $\sigma$-fields

for $n\geqslant 0$ and a given constant $K>0$.

Furthermore, $a(n),b(n),n\geqslant 0$ are non-increasing.

Assumptions on the controlled Markov processes, that is, the transition kernels: The state-action map

Assumptions on the existence of a solution:

We consider occupation measures which give for the controlled Markov process the probability or density to observe a particular state-action pair from $S\times U$ for given $\bm{\theta}$ and a given control policy $\pi$. We denote by $D^{(w)}(\bm{\theta},\bm{w})$ the set of all ergodic occupation measures for the prescribed $\bm{\theta}$ and $\bm{w}$ on state-action space $S^{(w)}\times U^{(\theta)}$ for the controlled Markov process $\bm{Z}^{(w)}$ with policy $\pi^{(w)}$. Analogously we denote, by $D^{(\theta)}(\bm{\theta},\bm{w})$ the set of all ergodic occupation measures for the prescribed $\bm{\theta}$ and $\bm{w}$ on state-action space $S^{(\theta)}\times U^{(\theta)}$ for the controlled Markov process $\bm{Z}^{(\theta)}$ with policy $\pi^{(\theta)}$. Define

for $\bm{\nu}$ a measure on $S^{(w)}\times U^{(w)}$ and the Marchaud map

We assume that the set $D^{(w)}(\bm{\theta},\bm{w})$ is singleton, that is, $\hat{\bm{g}}(\bm{\theta},\bm{w})$ contains a single function and we use the same notation for the set and its single element. If the set is not a singleton, the assumption of a solution can be expressed by the differential inclusion $\dot{\bm{w}}(t)\in\hat{\bm{g}}(\bm{\theta},\bm{w}(t))$ .

The following theorem is from Karmakar & Bhatnagar :

where $A_{0}=\cap_{t\geqslant 0}\overline{\{\bar{\bm{\theta}}(s):s\geqslant t\}}$ which is almost everywhere an internally chain transitive set of the differential inclusion

This framework allows to show convergence for gradient descent methods beyond stochastic gradient like for the ADAM procedure where current learning parameters are memorized and updated. The random processes $\bm{Z}^{(w)}$ and $\bm{Z}^{(\theta)}$ may track the current learning status for the fast and slow iterate, respectively.

Stochastic regularization like dropout is covered via the random processes $A^{(w)}$ and $A^{(\theta)}$.

A2.2 Rate of Convergence of Two Time-Scale Stochastic Approximation Algorithms

First we consider linear iterates according to the PhD thesis of Konda and Konda & Tsitsiklis .

The learning rates are deterministic, positive, nondecreasing and satisfy with $\epsilon\leqslant 0$:

A matrix is Hurwitz if the real part of each eigenvalue is strictly negative. We assume that the matrices $-\bm{A}_{22}$ and $-\bm{\Delta}$ are Hurwitz.

There exists a constant $\bar{a}\leqslant 0$ such that

The next theorem is taken from Konda and Konda & Tsitsiklis .

Under above assumptions and when the constant $\epsilon$ is sufficiently small, the limit matrices

is the unique solution to the following system of equations

The next theorems shows that the asymptotic covariance matrix of $a(n)^{-1/2}\bm{\theta}_{n}$ is the same as that of $a(n)^{-1/2}\bar{\bm{\theta}}_{n}$, where $\bar{\bm{\theta}}_{n}$ evolves according to the single time-scale stochastic iteration:

The next theorem combines Theorem 2.8 of Konda & Tsitsiklis and Theorem 4.1 of Konda & Tsitsiklis:

If the assumptions hold with $\epsilon=0$, then $a(n)^{-1/2}\hat{\bm{\theta}}_{n}$ converges in distribution to $\mathcal{N}(\bm{0},\bm{\Sigma}_{11}^{(0)})$.

In his PhD thesis Konda extended the analysis to the nonlinear case. Konda makes a linearization of the nonlinear function $\bm{h}$ and $\bm{g}$ with

There are additional errors due to linearization which have to be considered. However, only a sketch of a proof is provided but not a complete proof.

Theorem 4.1 of Konda & Tsitsiklis is important to generalize to the nonlinear case.

The convergence rate is governed by $\bm{A}_{22}$ for the fast and $\bm{\Delta}$ for the slow iterate. $\bm{\Delta}$ in turn is affected by the interaction effects captured by $\bm{A}_{21}$ and $\bm{A}_{12}$ together with the inverse of $\bm{A}_{22}$.

A2.2.2 Nonlinear Update Rules

The rate of convergence for nonlinear update rules according to Mokkadem & Pelletier is considered .

The terms $\bm{Z}^{(\theta)}_{n}$ and $\bm{Z}^{(w)}_{n}$ can be used to address the error through linearization, that is, the difference of the nonlinear functions to their linear approximation.

There exists a neighborhood $\mathcal{U}$ of $(\bm{\theta}^{*},\bm{w}^{*})$ such that, for all $(\bm{\theta},\bm{w})\in\mathcal{U}$

A matrix is Hurwitz if the real part of each eigenvalue is strictly negative. We assume that the matrices $\bm{A}_{22}$ and $\bm{\Delta}$ are Hurwitz.

We report a theorem and a proposition from Mokkadem & Pelletier . However, first we have to define the covariance matrices $\bm{\Sigma}_{\theta}$ and $\bm{\Sigma}_{w}$ which govern the rate of convergence.

We now define the asymptotic covariance matrices $\bm{\Sigma}_{\theta}$ and $\bm{\Sigma}_{w}$:

$\bm{\Sigma}_{\theta}$ and $\bm{\Sigma}_{w}$ are solutions of the Lyapunov equations:

Besides the learning steps $a(n)$ and $b(n)$, the convergence rate is governed by $\bm{A}_{22}$ for the fast and $\bm{\Delta}$ for the slow iterate. $\bm{\Delta}$ in turn is affected by interaction effects which are captured by $\bm{A}_{21}$ and $\bm{A}_{12}$ together with the inverse of $\bm{A}_{22}$.

A2.3 Equal Time-Scale Stochastic Approximation Algorithms

In this subsection we consider the case when the learning rates have equal time-scale.

If equal time-scales assumed then the iterates revisit infinite often an environment of the solution . In Zhang 2007, the functions of the iterates are the derivatives of a Lagrangian with respect to the dual and primal variables . The iterates are

The terms $\bm{Z}^{(\theta)}_{n}$ and $\bm{Z}^{(w)}_{n}$ subsum biased estimation errors.

Assumptions on update function: $\bm{h}$ and $\bm{g}$ are continuous, differentiable, and bounded. The Jacobians

are Hurwitz. A matrix is Hurwitz if the real part of each eigenvalue is strictly negative. This assumptions corresponds to the assumption in that the Lagrangian is concave in $\bm{w}$ and convex in $\bm{\theta}$.

$\{\bm{M}^{(\theta)}_{n}\}$ and $\{\bm{M}^{(w)}_{n}\}$ are a martingale difference sequences w.r.t. the increasing $\sigma$-fields $\mathcal{F}_{n}$. Furthermore they are mutually independent.

Define the “contraction region” $A_{\eta}$ as follows:

Under above assumptions the iterates return to $A_{\eta}$ infinitely often with probability one (a.s.).

The proof of the theorem in does not use the saddle point condition and not the fact that the functions of the iterates are derivatives of the same function.

For the unbiased case, Zhang showed in Theorem 3.1 of that the iterates converge. However, he used the saddle point condition of the Lagrangian. He considered iterates with functions that are the derivatives of a Lagrangian with respect to the dual and primal variables .

A2.3.2 Equal Time Step for Actor-Critic Method

If equal time-scales assumed then the iterates revisit infinite often an environment of the solution of DiCastro & Meir . The iterates of DiCastro & Meir are derived for actor-critic learning.

The average reward per stage is for the recurrent state $\bm{x}^{*}$:

For TD($\lambda$) we have an eligibility trace:

We define the approximation error with optimal parameter $\bm{w}^{*}(\bm{\theta})$:

where $\pi(\bm{\theta})$ is an projection operator into the span of $\bm{\Phi}\bm{w}$. We bound this error by

The rewards $\{r(\bm{x})\}_{\bm{x}\in\mathcal{X}}$ are uniformly bounded by a finite constant $B_{r}$.

Each Markov chain for each $\bm{\theta}$ is aperiodic, recurrent, and irreducible.

Assumption on the likelihood ratio derivative:

where $\|.\|_{2}$ is the Euclidean $L_{2}$ norm.

Assumptions on the approximation space given by $\bm{\Phi}$:

The columns of the matrix $\bm{\Phi}$ are independent, that is, the form a basis of dimension $k$. The norms of the columns vectors of the matrix $\bm{\Phi}$ are bounded above by $1$, that is, $\|\bm{\phi}_{l}\|_{2}\leqslant 1$ for $1\leqslant l\leqslant k$.

The next theorem from DiCastro & Meir implies that the trajectory visits a neighborhood of a local maximum infinitely often. Although it may leave the local vicinity of the maximum, it is guaranteed to return to it infinitely often.

where $B_{\Delta td1}$, $B_{\Delta td2}$, and $B_{\Delta td3}$ are finite constants depending on the Markov decision process and the agent parameters.

The trajectory visits a neighborhood of a local maximum infinitely often.

The larger the critic learning rates $\Gamma_{w}$ and $\Gamma_{\eta}$ are, the smaller is the region around the local maximum.

The results are in agreement with those of Zhang 2007 .

Even if the results are derived for a special actor-critic setting, they carry over to a more general setting of the iterates.

A3 ADAM Optimization as Stochastic Heavy Ball with Friction

The Nesterov Accelerated Gradient Descent (NAGD) has raised considerable interest due to its numerical simplicity and its low complexity. Previous to NAGD and its derived methods there was Polyak’s Heavy Ball method . The idea of the Heavy Ball is a ball that evolves over the graph of a function $f$ with damping (due to friction) and acceleration. Therefore, this second-order dynamical system can be described by the ODE for the Heavy Ball with Friction (HBF) :

where $a(n)$ is the damping coefficient with $a(n)=\frac{a}{n^{\beta}}$ for $\beta\in(0,1]$. This ODE is equivalent to the integro-differential equation

where $k$ and $h$ are two memory functions related to $a(t)$. For polynomially memoried HBF we have $k(t)=t^{\alpha+1}$ and $h(t)=(\alpha+1)t^{\alpha}$ for some positive $\alpha$, and for exponentially memoried HBF we have $k(t)=\lambda\exp(\lambda\ t)$ and $h(t)=\exp(\lambda\ t)$. For the sum of the learning rates, we obtain

where $\gamma=0.5772156649$ is the Euler-Mascheroni constant.

Gadat et al. derived a discrete and stochastic version of the HBF :

The recursion Eq. (166) is the first moment update of ADAM .

For the term $r(n)a(n)$ we obtain for the polynomial memory the approximations

Gadat et al. showed that the recursion Eq. (164) converges for functions with at most quadratic grow . The authors mention that convergence can be proofed for functions $f$ that are $L$-smooth, that is, the gradient is $L$-Lipschitz.

Kingma et al. state in Theorem 4.1 convergence of ADAM while assuming that $\beta_{1}$, the first moment running average coefficient, decays exponentially. Furthermore they assume that $\frac{\beta_{1}^{2}}{\sqrt{\beta_{2}}}<1$ and the learning rate $\alpha_{t}$ decays with $\alpha_{t}=\frac{\alpha}{\sqrt{t}}$.

ADAM divides $\bm{m}_{n}$ of the recursion Eq. (166) by the bias-corrected second raw moment estimate. Since the bias-corrected second raw moment estimate changes slowly, we consider it as an error.

We are interested in the difference of actual stochastic $v_{n}$ to the true stationary $v$:

A4 Experiments: Additional Information

A4.2 WGAN-GP on the One Billion Word Benchmark.

A4.3 BEGAN

The Boundary Equilibrium GAN (BEGAN) maintains an equilibrium between the discriminator and generator loss (cf. Section 3.3 in )

which, in turn, also leads to a fixed relation between the two gradients, therefore, a two time-scale update is not ensured by solely adjusting the learning rates. Indeed, for stable learning rates, we see no differences in the learning progress between orig and TTUR as depicted in Figure A12.

A5 Discriminator vs. Generator Learning Rate

The convergence proof for learning GANs with TTUR assumes that the generator learning rate will eventually become small enough to ensure convergence of the discriminator learning. At some time point, the perturbations of the discriminator updates by updates of the generator parameters are sufficient small to assure that the discriminator converges. Crucial for discriminator convergence is the magnitude of the perturbations which the generator induces into the discriminator updates. These perturbations are not only determined by the generator learning rate but also by its loss function, current value of the loss function, optimization method, size of the error signals that reach the generator (vanishing or exploding gradient), complexity of generator’s learning task, architecture of the generator, regularization, and others. Consequently, the size of generator learning rate does not solely determine how large the perturbations of the discriminator updates are but serve to modulate them. Thus, the generator learning rate may be much larger than the discriminator learning rate without inducing large perturbation into the discriminator learning.

Even the learning dynamics of the generator is different from the learning dynamics of the discriminator, though they both have the same learning rate. Figure A13 shows the loss of the generator and the discriminator for an experiment with DCGAN on CelebA, where the learning rate was 0.0005 for both the discriminator and the generator. However, the discriminator loss is decreasing while the generator loss is increasing. This example shows that the learning rate neither determines the perturbations nor the progress in learning for two coupled update rules. The choice of the learning rate for the generator should be independent from choice for the discriminator. Also the search ranges of discriminator and generator learning rates should be independent from each other, but adjusted to the corresponding architecture, task, etc.

A6 Used Software, Datasets, Pretrained Models, and Implementations

We used the following datasets to evaluate GANs: The Large-scale CelebFaces Attributes (CelebA) dataset, aligned and cropped , the training dataset of the bedrooms category of the large scale image database (LSUN) , the CIFAR-10 training dataset , the Street View House Numbers training dataset (SVHN) , and the One Billion Word Benchmark .

All experiments rely on the respective reference implementations for the corresponding GAN model. The software framework for our experiments was Tensorflow 1.3 and Python 3.6. We used following software, datasets and pretrained models:

BEGAN in Tensorflow, https://github.com/carpedm20/BEGAN-tensorflow, Fixed random seeds removed. Accessed: 2017-05-30

DCGAN in Tensorflow, https://github.com/carpedm20/DCGAN-tensorflow, Fixed random seeds removed. Accessed: 2017-04-03

Improved Training of Wasserstein GANs, image model, https://github.com/igul222/improved_wgan_training/blob/master/gan_64x64.py, Accessed: 2017-06-12

Improved Training of Wasserstein GANs, language model, https://github.com/igul222/improved_wgan_training/blob/master/gan_language.py, Accessed: 2017-06-12

Inception-v3 pretrained, http://download.tensorflow.org/models/image/imagenet/inception-2015-12-05.tgz, Accessed: 2017-05-02

References