Title: ON THE LIMITATIONS OF FIRST-ORDER APPROXIMATION IN GAN DYNAMICS Anonymous authors Paper under double-blind review

Abstract: Generative Adversarial Networks (GANs) have been proposed as an approach to learning generative models. While GANs have demonstrated promising performance on multiple vision tasks, their learning dynamics are not yet well understood, neither in theory nor in practice. In particular, the work in this domain has been focused so far only on understanding the properties of the stationary solutions that this dynamics might converge to, and of the behavior of that dynamics in this solutions' immediate neighborhood. To address this issue, in this work we take a first step towards a principled study of the GAN dynamics itself. To this end, we propose a model that, on one hand, exhibits several of the common problematic convergence behaviors (e.g., vanishing gradient, mode collapse, diverging or oscillatory behavior), but on the other hand, is sufficiently simple to enable rigorous convergence analysis. This methodology enables us to exhibit an interesting phenomena: a GAN with an optimal discriminator provably converges, while guiding the GAN training using only a first order approximation of the discriminator leads to unstable GAN dynamics and mode collapse. This suggests that such usage of the first order approximation of the discriminator, which is a de-facto standard in all the existing GAN dynamics, might be one of the factors that makes GAN training so challenging in practice. Additionally, our convergence result constitutes the first rigorous analysis of a dynamics of a concrete parametric GAN.

1. INTRODUCTION:

Generative modeling is a fundamental learning task of growing importance. As we apply machine learning to increasingly sophisticated problems, we often aim to learn functions with an output domain that is significantly more complex than simple class labels. Common examples include image "translation" (Isola et al., 2017) , speech synthesis (van den Oord et al., 2016) , and robot trajectory prediction (Finn et al., 2016) . Due to progress in deep learning, we now have access to powerful architectures that can represent generative models over such complex domains. However, training these generative models is a key challenge. Simpler learning problems such as classification have a clear notion of "right" and "wrong," and the approaches based on minimizing the corresponding loss functions have been tremendously successful. In contrast, training a generative model is far more nuanced because it is often unclear how "good" a sample from the model is.

Generative Adversarial Networks (GANs) have recently been proposed to address this issue (Goodfellow et al., 2014) . In a nutshell, the key idea of GANs is to learn both the generative model and the loss function at the same time. The resulting training dynamics are usually described as a game between a generator (the generative model) and a discriminator (the loss function). The goal of the generator is to produce realistic samples that fool the discriminator, while the discriminator is trained to distinguish between the true training data and samples from the generator. GANs have shown promising results on a variety of tasks, and there is now a large body of work that explores the power of this framework (Goodfellow, 2017) .

Unfortunately, reliably training GANs is a challenging problem that often hinders further research in this area. Practitioners have encountered a variety of obstacles such as vanishing gradients, mode collapse, and diverging or oscillatory behavior (Goodfellow, 2017) . At the same time, the theoretical underpinnings of GAN dynamics are not yet well understood. To date, there were no convergence proofs for GAN models, even in very simple settings. As a result, the root cause of frequent failures of GAN dynamics in practice remains unclear.

In this paper, we take a first step towards a principled understanding of GAN dynamics. Our general methodology is to propose and examine a problem setup that exhibits all common failure cases of GAN dynamics while remaining sufficiently simple to allow for a rigorous analysis. Concretely, we introduce and study the GMM-GAN: a variant of GAN dynamics that captures learning a mixture of two univariate Gaussians. We first show experimentally that standard gradient dynamics of the GMM-GAN often fail to converge due to mode collapse or oscillatory behavior. Interestingly, this also holds for techniques that were recently proposed to improve GAN training such as unrolled GANs (Metz et al., 2017) . In contrast, we then show that GAN dynamics with an optimal discriminator do converge, both experimentally and provably. To the best of our knowledge, our theoretical analysis of the GMM-GAN is the first global convergence proof for parametric and non-trivial GAN dynamics.

Our results show a clear dichotomy between the dynamics arising from applying simultaneous gradient descent and the one that is able to use an optimal discriminator. The GAN with optimal discriminator provably converges from (essentially) any starting point. On the other hand, the simultaneous gradient GAN empirically often fails to converge, even when the discriminator is allowed many more gradient steps than the generator. These findings go against the common wisdom that first order methods are sufficiently strong for all deep learning applications. By carefully inspecting our models, we are able to pinpoint some of the causes of this, and we highlight a phenomena we call discriminator collapse which often causes first order methods to fail in our setting.

2. GENERATIVE ADVERSARIAL DYNAMICS:

Generative adversarial networks are commonly described as a two player game (Goodfellow et al., 2014) . Given a true distribution P , a set of generators G = {G u , u ∈ U}, a set of discriminators (1)

D = {D v , v ∈ V},

In other words, the game is between two players called the generator and discriminator, respectively. The goal of the discriminator is to distinguish between samples from the generator and the true distribution. The goal of the generator is to fool the discriminator by generating samples that are similar to the data distribution.

By varying the choice of the measuring function and the set of discriminators, one can capture a wide variety of loss functions. Typical choices that have been previously studied include the KL divergence and the Wasserstein distance (Goodfellow et al., 2014; Arjovsky et al., 2017) . This formulation can also encode other common objectives: most notably, as we will show, the total variation distance.

To optimize the objective (1), the most common approaches are variants of simultaneous gradient descent on the generator u and the discriminator v. But despite its attractive theoretical grounding, GAN training is plagued by a variety of issues in practice. Two major problems are mode collapse and vanishing gradients. Mode collapse corresponds to situations in which the generator only learns a subset (a few modes) of the true distribution P (Goodfellow, 2017; Arora & Zhang, 2017) .

For instance, a GAN trained on an image modeling task would only produce variations of a small number of images. Vanishing gradients (Arjovsky et al., 2017; Arjovsky & Bottou, 2017; Arora et al., 2017) are, on the other hand, a failure case where the generator updates become vanishingly small, thus making the GAN dynamics not converge to a satisfying solution. Despite many proposed explanations and approaches to solve the vanishing gradient problem, it is still often observed in practice (Goodfellow, 2017) .

2.1. TOWARDS A PRINCIPLED UNDERSTANDING OF GAN DYNAMICS:

GANs provide a powerful framework for generative modeling. However, there is a large gap between the theory and practice of GANs. Specifically, to the best of the authors' knowledge, all theoretical studies of GAN dynamics for parametric models simply consider global optima and stationary points of the dynamics, and there has been no rigorous study of the actual GAN dynamics. In practice, GANs are always optimized using first order methods, and the current theory of GANs cannot tell us whether or not these methods converge to a meaningful solution. This raises a natural question, also posed as an open problem in (Goodfellow, 2017) :

Our theoretical understanding of GANs is still fairly poor. In particular, to the best of the authors' knowledge, all existing analyzes of GAN dynamics for parametric models simply consider global optima and stationary points of the dynamics. There has been no rigorous study of the actual GAN dynamics, except studying it in the immediate neighborhood of such stationary points (Nagarajan & Kolter, 2017) . This raises a natural question:

Can we understand the convergence behavior of GANs?

This question is difficult to tackle for many reasons. One of them is the non-convexity of the GAN objective/loss function, and of the generator and discriminator sets. Another one is that, in practice, GANs are always optimized using first order methods. That is, instead of following the "ideal" dynamics that has both the generator and discriminator always perform the optimal update, we just approximate such updates by a sequence of gradient steps. This is motivated by the fact that computing such optimal updates is, in general, algorithmically intractable, and adds an additional layer of complexity to the problem.

In this paper, we want to change this state of affairs and initiate the study of GAN dynamics from an algorithmic perspective. Specifically, we pursue the following question:

What is the impact of using first order approximation on the convergence of GAN dynamics?

Concretely, we focus on analyzing the difference between two GAN dynamics: a "first order" dynamics, in which both the generator and discriminator use first order updates; and an "optimal discriminator" dynamics, in which only the generator uses first order updates but the discriminator always makes an optimal update. Even the latter, simpler dynamics has proven to be challenging to understand. Even the question of whether using the optimal discriminator updates is the right approach has already received considerable attention. In particular, (Arjovsky & Bottou, 2017) present theoretical evidence that using the optimal discriminator at each step may not be desirable in certain settings (although these settings are very different to the one we consider in this paper).

We approach our goal by defining a simple GAN model whose dynamics, on one hand, captures many of the difficulties of real-world GANs but, on the other hand, is still simple enough to make analysis possible. We then rigorously study our questions in the context of this model. Our intention is to make the resulting understanding be the first step towards crystallizing a more general picture.

3. A SIMPLE MODEL FOR STUDYING GAN DYNAMICS:

Perhaps a tempting starting place for coming up with a simple but meaningful set of GAN dynamics is to consider the generators being univariate Gaussians with fixed variance. Indeed, in the supplementary material we give a short proof that simple GAN dynamics always converge for this class of generators. However, it seems that this class of distributions is insufficiently expressive to exhibit many of the phenomena such as mode collapse mentioned above. In particular, the distributions in this class are all unimodal, and it is unclear what mode collapse would even mean in this context.

Generators.:

The above considerations motivate us to make our model slightly more complicated. We assume that the true distribution and the generator distributions are all mixtures of two univariate Gaussians with unit variance, and uniform mixing weights. Formally, our generator set is G, where

EQUATION

For any µ ∈ R 2 , we let G µ (x) denote the distribution in G with means at µ 1 and µ 2 . While this is a simple change compared to a single Gaussian case, it makes a large difference in the behavior of the dynamics. In particular, many of the pathologies present in real-world GAN training begin to appear.

Loss function. While GANs are usually viewed as a generative framework, they can also be viewed as a general method for density estimation. We want to set up learning an unknown generator G µ * ∈ G as a generative adversarial dynamics. To this end, we must first define the loss function for the density estimation problem. A well-studied goal in this setting is to recover G µ * (x) in total variation (also known as L 1 or statistical) distance, where the total variation distance between two distributions P, Q is defined as

EQUATION

where the maximum is taken over all measurable events A.

Such finding the best-fit distribution in total variation distance can indeed be naturally phrased as generative adversarial dynamics. Unfortunately, for arbitrary distributions, this is algorithmically problematic, simply because the set of discriminators one would need is intractable to optimize over.

However, for distributions that are structurally simple, like mixtures of Gaussians, it turns out we can consider a much simpler set of discriminators. In Appendix B.1 in the supplementary material, motivated by connections to VC theory, we show that for two generators G µ1 , G µ2 ∈ G, we have

EQUATION

where the maxima is taken over two disjoint intervals I 1 , I 2 ⊆ R. In other words, instead of considering the difference of measure between the two generators G µ1 , G µ2 on arbitrary events, we may restrict our attention to unions of two disjoint intervals in R. This is a special case of a well-studied distance measure known as the A k -distance, for k = 2 (Devroye & Lugosi, 2012; Chan et al., 2014) . Moreover, this class of subsets has a simple parametric description.

Discriminators. Now, the above discussion motivates our definition of discriminators to be

EQUATION

In other words, the set of discriminators is taken to be the set of indicator functions of sets which can be expressed as a union of at most two disjoint intervals. With this definition, finding the best fit in total variation distance to some unknown

G µ * ∈ G is equivalent to finding µ minimizing µ = arg min µ max ,r L(µ, , r) , where L(µ, , r) = E x∼G µ * [D(x)] + E x∼Gµ [1 -D(x)] (6)

is a smooth function of all three parameters (see the supplementary material for details).

Dynamics. The objective in ( 6) is easily amenable to optimization at parameter level. A natural approach for optimizing this function would be to define G( µ) = max ,r L( µ, , r), and to perform (stochastic) gradient descent on this function. This corresponds to, at each step, finding the the optimal discriminator, and updating the current µ in that direction. We call these dynamics the optimal discriminator dynamics. Formally, given µ (0) and a stepsize η g , and a true distribution G µ * ∈ G, the optimal discriminator dynamics for G µ * , G, D starting at µ (0) are given iteratively as (t) , r (t) = arg max ,r

EQUATION

where the maximum is taken over , r which induce two disjoint intervals.

For more complicated generators and discriminators such as neural networks, these dynamics are computationally difficult to perform. Therefore, instead of the updates as in (7), one resorts to simultaneous gradient iterations on the generator and discriminator. These dynamics are called the first order dynamics. Formally, given µ (0) , (0) , r (0) and a stepsize η g , η d , and a true distribution G µ * ∈ G, the first order dynamics for G µ * , G, D starting at µ (0) are specified as t) ) .

EQUATION

(9) Even for our relatively simple setting, the first order dynamics can exhibit a variety of behaviors, depending on the starting conditions of the generators and discriminators. In particular, in Figure 1 , we see that depending on the initialization, the dynamics can either converge to optimality, exhibit a primitive form of mode collapse, where the two generators collapse into a single generator, or converge to the wrong value, because the gradients vanish. This provides empirical justification for our model, and shows that these dynamics are complicated enough to model the complex behaviors which real-world GANs exhibit. Moreover, as we show in Section 5 below, these behaviors are not just due to very specific pathological initial conditions: indeed, when given random initial conditions, the first order dynamics still more often than not fail to converge.

Parametrization We note here that there could be several potential GAN dynamics to consider here. Each one resulting from slightly different parametrization of the total variation distance. For instance, a completely equivalent way to define the total variation distance is

EQUATION

which does not change the value of the variational distance, but does change the induced dynamics.

We do not focus on these induced dynamics in this paper since they do not exactly fit within the traditional GAN framework, i.e. it is not of the form (1) (see Appendix C). Nevertheless, it is an interesting set of dynamics and it is a natural question whether similar phenomena occur in these dynamics. In Appendix C, we show the the optimal discriminator dynamics are unchanged, and the induced first order dynamics have qualitatively similar behavior to the ones we consider in this paper. This also suggests that the phenomena we exhibit might be more fundamental. In all plots the true distribution was G µ * with µ * = (-0.5, 0.5), and step size was taken to be 0.1. The solid lines represent the two coordinates of µ, and the dotted lines represent the discriminator intervals. In order: (a) first order dynamics with initial conditions that converge to the true distribution. (b) First order dynamics with initial conditions that exhibit wild oscillation before mode collapse. (c) Optimal discriminator dynamics. (d) First order dynamics that exhibit vanishing gradients and converge to the wrong distribution. Observe that the optimal discriminator dynamics converge, and then the discriminator varies wildly, because the objective function is not differentiable at optimality. Despite this it remains roughly at optimality from step to step.

4. OPTIMAL DISCRIMINATOR VS. FIRST ORDER DYNAMICS:

We now describe our results in more detail. We first consider the dynamics induced by the optimal discriminator. Our main theoretical result is1 :

Theorem 4.1. Fix δ > 0 sufficiently small and C > 0. Let µ * ∈ R 2 so that |µ * i | ≤ C, and |µ * 1 -µ * 2 | ≥ δ. Then, for all initial points µ (0) so that | µ (0) i | ≤ C for all i and so that | µ (0) 1 -µ (0) 2 | ≥ δ, if we let η = poly(1/δ, e -C 2 ) and T = poly(1/δ, e -C 2 ), then if µ (T ) is specified by the optimal discriminator dynamics, we have d TV (G µ * , G µ (T ) ) ≤ δ.

In other words, if the µ * are bounded by a constant, and not too close together, then in time which is polynomial in the inverse of the desired accuracy δ  and e -C 2 , where C is a bound on how far apart the µ * and µ are, the optimal discriminator dynamics converge to the ground truth in total variation distance. Note that the dependence on e -C 2 is necessary, as if the µ and µ * are initially very far apart, then the initial gradients for the µ will necessarily be of this scale as well.

On the other hand, we provide simulation results that demonstrate that first order updates, or more complicated heuristics such as unrolling, all fail to consistently converge to the true distribution, even under the same sorts of conditions as in Theorem 4.1. In Figure 1 , we gave some specific examples where the first order dynamics fail to converge. In Section 5 we show that this sort of divergence is common, even with random initializations for the discriminators. In particular, the probability of convergence is generally much lower than 1, for both the regular GAN dynamics, and unrolling. In general, we believe that this phenomena should occur for any natural first order dynamics for the generator. In particular, one barrier we observed for any such dynamics is something we call discriminator collapse, that we describe in Appendix A.

4.1. ANALYZING THE OPTIMAL DISCRIMINATOR DYNAMICS:

We provide now a high level overview of the proof of Theorem 4.1. The key element we will need in our proof is the ability to quantify the progress our updates make on converging towards the optimal solution. This is particularly challenging as our objective function is neither convex nor smooth. The following lemma is our main tool for achieving that. Roughly stated, it says that for any Lipschitz function, even if it is non-convex and non-smooth, as long as the change in its derivative is smaller in magnitude than the value of the derivative, gradient descent makes progress on the function value. Note that this condition is much weaker than typical assumptions used to analyze gradient descent.

Lemma 4.2. Let g : R k → R be a Lipschitz function that is differentiable at some fixed x ∈ R k . For some η > 0, let x = x -η∇f (x). Suppose there exists c < 1 so that almost all v ∈ L(x, x ), where L(x, y) denotes the line between x and y, g is differentiable, and moreover, we have ∇g

(x) -∇g(v) 2 ≤ c ∇g(x) 2 . Then g(x ) -g(x) ≤ -η(1 -c) ∇g(x) 2 2 .

Here, we will use the convention that µ * 1 ≤ µ * 2 , and during the analysis, we will always assume for simplicity of notation that

µ 1 ≤ µ 2 . Also, in what follows, let f ( µ) = f µ * ( µ) = d TV (G µ , G µ * ) and F ( µ, x) = G µ * (x) -G µ (x)

be the objective function and the difference of the PDFs between the true distribution and the generator, respectively.

For any δ > 0, define the sets

Rect(δ) = { µ : | µ i -µ * j | < δ for some i, j} , Opt(δ) = { µ : | µ i -µ * i | < δ for all i} .

to be the set of parameter values which have at least one parameter which is not too far from optimality, and the set of parameter values so that all parameter values are close. We also let B(C) denote the box of sidelength C around the origin, and we let Sep(γ) = {v ∈ R 2 : |v 1 -v 2 | > γ} be the set of parameter vectors which are not too close together.

Our main work lies within a set of lemmas which allow us to instantiate the bounds in Lemma 4.2. We first show a pair of lemmas which show that, explicitly excluding bad cases such as mode collapse, our dynamics satisfy the conditions of Lemma 4.2. We do so by establishing a strong (in fact, nearly constant) lower bound on the gradient when we are fairly away from optimality (Lemma 4.3). Then, we show a relatively weak bound on the smoothness of the function (Lemma 4.4), but which is sufficiently strong in combination with Lemma 4.3 to satisfy Lemma 4.2. Finally, we rule discriminator dynamics after adding an arbitrarily small amount of Gaussian noise. It is clear that by taking this noise to be sufficiently small (say exponentially small) then we avoid this pathological set with probability 1, and moreover the noise does not otherwise affect the convergence analysis at all. For simplicity, we will ignore this issue for the rest of the paper.

out the pathological cases we explicitly excluded earlier, such as mode collapse or divergent behavior (Lemmas 4.5 and 4.6). Putting all these together appropriately yields the desired statement. Our first lemma is a lower bound on the gradient value:

Lemma 4.3. Fix C ≥ 1 ≥ γ ≥ δ > 0. Suppose µ ∈ Rect(0), and suppose µ * , µ ∈ B(C) and µ * ∈ Sep(γ), µ ∈ Sep(δ). There is some K = Ω(1) • (δe -C 2 /C) O(1) so that ∇f µ * ( µ) 2 ≥ K.

The above lemma statement is slightly surprising at first glance. It says that the gradient is never 0, which would suggest there are no local optima at all. To reconcile this, one should note that the gradient is not continuous (defined) everywhere.

The second lemma states a bound on the smoothness of the function: O(1) for appropriate choices of constants on the RHS, we get

Lemma 4.4. Fix C ≥ 1 and γ ≥ δ > 0 so that δ is sufficiently small. Let µ * , µ, µ be such that L( µ, µ ) ∩ Opt(δ) = ∅, µ * ∈ Sep(γ), µ , µ ∈ Sep(δ), and µ * , µ, µ ∈ B(C). Let K = Ω(1) • (δe -C 2 /C) O(1) be the K for which Lemma 4.3 holds with those parameters. If we have µ -µ 2 ≤ Ω(1) • (δe -C 2 /C)

∇f µ * ( µ ) -∇f µ * ( µ) 2 ≤ K/2 ≤ ∇f µ * ( µ) 2 /2.

These two lemmas almost suffice to prove progress as in Lemma 4.2, however, there is a major caveat. Specifically, Lemma 4.4 needs to assume that µ and µ are sufficiently well-separated, and that they are bounded. While the µ i start out separated and bounded, it is not clear that it does not mode collapse or diverge off to infinity. However, we are able to rule these sorts of behaviors out. Formally: Lemma 4.5 (No mode collapse). Fix γ > 0, and let δ be sufficiently small. Let η ≤ δ/C for some C large. Suppose µ * ∈ Sep(γ). Then, if µ ∈ Sep(δ), and µ = µ -η∇f µ * ( µ), we have µ ∈ Sep(δ). Lemma 4.6 (No diverging to infinity). Let C > 0 be sufficiently large, and let η > 0 be sufficiently small. Suppose µ * ∈ B(C), and µ ∈ B(2C). Then, if we let µ = µ -η∇f µ * ( µ), then µ ∈ B(2C).

Together, these four lemmas together suffice to prove Theorem 4.1 by setting parameters appropriately. We refer the reader to Appendix D for more details including the proofs.

5. EXPERIMENTS:

To illustrate more conclusively that the phenomena demonstrated in Figure 1 are not particularly rare, and that first order dynamics do often fail to converge, we also conducted the following heatmap experiments. We set µ * = (-0.5, 0.5) as in Figure 1 . We then set a grid for the µ, so that each coordinate is allowed to vary from -1 to 1. For each of these grid points, we randomly chose a set of initial discriminator intervals, and ran the first order dynamics for 3000 iterations, with constant stepsize 0.3. We then repeated this 120 times for each grid point, and plotted the probability that the generator converged to the truth, where we say the generator converged to the truth if the TV distance between the generator and optimality is < 0.1. The choice of these parameters was somewhat arbitrary, however, we did not observe any qualitative difference in the results by varying these numbers, and so we only report results for these parameters. We also did the same thing for the optimal discriminator dynamics, and for unrolled discriminator dynamics with 5 unrolling steps, as described in (Metz et al., 2017) , which attempt to match the optimal discriminator dynamics.

The results of the experiment are given in Figure 2 . We see that all three methods fail when we initialize the two generator means to be the same. This makes sense, since in that regime, the generator starts out mode collapsed and it is impossible for it to un-"mode collapse", so it cannot fit the true distribution well. Ignoring this pathology, we see that the optimal discriminator otherwise always converges to the ground truth, as our theory predicts. On the other hand, both regular first order dynamics and unrolled dynamics often times fail, although unrolled dynamics do succeed more often than regular first order dynamics. This suggests that the pathologies in Figure 1 are not so rare, and that these first order methods are quite often unable to emulate optimal discriminator dynamics.

6. RELATED WORK:

GANs have received a tremendous amount of attention over the past two years (Goodfellow, 2017) . Hence we only compare our results to the most closely related papers here. The recent paper (Arora et al., 2017) studies generalization aspects of GANs and the existence of equilibria in the two-player game. In contrast, our paper focuses on the dynamics of GAN training.

We provide the first rigorous proof of global convergence and show that a GAN with an optimal discriminator always converges to an approximate equilibrium.

One recently proposed method for improving the convergence of GAN dynamics is the unrolled GAN (Metz et al., 2017) . The paper proposes to "unroll" multiple discriminator gradient steps in the generator loss function. The authors argue that this improves the GAN dynamics by bringing the discriminator closer to an optimal discriminator response. Our experiments show that this is not a perfect approximation: the unrolled GAN still fails to converge in multiple initial configurations (however, it does converge more often than a "vanilla" one-step discriminator).

The authors of (Arjovsky & Bottou, 2017 ) also take a theoretical view on GANs. They identify two important properties of GAN dynamics: (i) Absolute continuity of the population distribution, and (ii) overlapping support between the population and generator distribution. If these conditions do not hold, they show that the GAN dynamics fail to converge in some settings. However, they do not prove that the GAN dynamics do converge under such assumptions. We take a complementary view: we give a convergence proof for a concrete GAN dynamics. Moreover, our model shows that absolute continuity and support overlap are not the only important aspects in GAN dynamics: although our distributions clearly satisfy both of their conditions, the first-order dynamics still fail to converge.

The paper (Nagarajan & Kolter, 2017) studies the stability of equilibria in GAN training. In contrast to our work, the results focus on local stability while we establish global convergence results. Moreover, their theorems rely on fairly strong assumptions. While the authors give a concrete model for which these assumptions are satisfied (the linear quadratic Gaussian GAN), the corresponding target and generator distributions are unimodal. Hence this model cannot exhibit mode collapse. We propose the GMM-GAN specifically because it is rich enough to exhibit mode collapse.

The recent work (Grnarova et al., 2017) views GAN training through the lens of online learning. The paper gives results for the game-theoretic minimax formulation based on results from online learning.

The authors give results that go beyond the convex-concave setting, but do not address generalization questions. Moreover, their algorithm is not based on gradient descent (in contrast to essentially all practical GAN training) and relies on an oracle for minimizing the highly non-convex generator loss. This viewpoint is complementary to our approach. We establish results for learning the unknown distribution and analyze the commonly used gradient descent approach for learning GANs.

7. CONCLUSIONS:

We haven taken a step towards a principled understanding of GAN dynamics. We define a simple yet rich model of GAN training and prove convergence of the corresponding dynamics. To the best of our knowledge, our work is the first to establish global convergence guarantees for a parametric GAN. We find an interesting dichotomy: If we take optimal discriminator steps, the training dynamics provably converge. In contrast, we show experimentally that the dynamics often fail if we take first order discriminator steps. We believe that our results provide new insights into GAN training and point towards a rich algorithmic landscape to be explored in order to further understand GAN dynamics. 

A DISCRIMINATOR COLLAPSE: A BARRIER FOR FIRST ORDER METHODS:

As discussed above, our simple GAN dynamics are able to capture the same undesired behaviors that more sophisticated GANs exhibit. In addition to these behaviors, our dynamics enables us to discern another degenerate behavior which does not seem to have previously been observed in the literature. We call this behavior discriminator collapse.

We first explain this phenomenon using language specific to our GMM-GAN dynamics. In our dynamics, discriminator collapse occurs when a discriminator interval which originally had finite width is forced by the dynamics to have its width converge to 0. This happens whenever this interval lies entirely in a region where the generator PDF is much larger than the discriminator PDF. We will shortly argue why this is undesirable.

In Figure 3 , we show an example of discriminator collapse in our dynamics. Each plot in the figure shows the true PDF minus the PDF of the generators, where the regions covered by the discriminator are shaded. Plot (a) shows the initial configuration of our example. Notice that the leftmost discriminator interval lies entirely in a region for which the true PDF minus the generators' PDF is negative. Since the discriminator is incentivized to only have mass on regions where the difference is positive, the first order dynamics will cause the discriminator interval to collapse to have length zero if it is in a negative region. We see in Plot (c) that this discriminator collapses if we run many discriminator steps for this fixed generator. In particular, these steps do not converge to the globally optimal discriminator shown in Plot (b).

This collapse also occurs when we run the dynamics. In Plots (d) and (e), we see that after running the first order dynamics -or even unrolled dynamics -for many iterations, eventually both discriminators collapse. When a discriminator interval has length zero, it can never uncollapse, and moreover, its contribution to the gradient of the generator is zero. Thus these dynamics will never converge to the ground truth.

For general GANs, we view discriminator collapse as a situation when the local optimization landscape around the current discriminator encourages it to make updates which decrease its representational power. For instance, this could happen because the first order updates are unable to wholly follow the evolution of the optimal discriminator due to attraction of local maxima, and thus only capture part of the optimal discriminator's structure. We view understanding the exact nature of discriminator collapse in more general settings and interesting research problem to explore further.

B OMITTED DETAILS FROM SECTION 2 B.1 TWO INTERVALS SUFFICE FOR G:

Here we formally prove (4). In fact, we will prove a slight generalization of this fact which will be useful later on.

We require the following theorem from Hummel and Gidas: Hummel & Gidas, 1984) ). Let f be any analytic function with at most n zeros. Then f • N (0, σ 2 ) has at most n zeros.

Theorem B.1 ((

This allows us to prove::

Theorem B.2. Any linear combination F (x) of the probability density functions of k Gaussians with the same variance has at most k -1 zeros, provided at least two of the Gaussians have different means. In particular, for any µ = ν, the function F (x) = D µ (x) -D ν (x) has at most 3 zeroes.

Proof. If we have more than 1 Gaussian with the same mean, we can replace all Gaussians having that mean with an appropriate factor times a single Gaussian with that mean. Thus, we assume without loss of generality that all Gaussians have distinct means. We may also assume without loss of generality that all Gaussians have a nonzero coefficient in the definition of F .

Suppose the minimum distance between the means of any of the Gaussians is δ. We first prove the statement when δ is sufficiently large compared to everything else. Consider any pair of Gaussians with consecutive means ν, µ. WLOG assume that µ > ν = 0. Suppose our pair of Gaussians has the same sign in the definition of F . In particular they are both strictly positive. For sufficiently large δ, we can make the contribution of the other Gaussians to F an arbitrarily small fraction of the whichever Gaussian in our pair is largest for all points on [ν, µ]. Thus, for δ sufficiently large, that there are no zeros on this interval. Now suppose our pair of Gaussians have different signs in the definition of F . Without loss of generality, assume the sign of the Gaussian with mean ν is positive and the sign of the Gaussian with mean µ is negative. Then the PDF of the first Gaussian is strictly decreasing on (ν, µ] and the PDF of the negation of the second Gaussian is decreasing on [ν, µ). Thus, their sum is strictly decreasing on this interval. Similarly to before, by making δ sufficiently large, the magnitude of the contributions of the other Gaussians to the derivative in this region can be made an arbitrarily small fraction of the magnitude of whichever Gaussian in our pair contributes the most at each point in the interval. Thus, in this case, there is exactly one zero in the intervale [µ, ν].

Also, note that there can be no zeros of F outside of the convex hull of their means. This follows by essentially the same argument as the two positive Gaussians case above.

The general case (without assuming δ sufficiently large) follows by considering sufficiently skinny (nonzero variance) Gaussians with the same means as the Gaussians in the definition of F , rescaling the domain so that they are sufficiently far apart, applying this argument to this new function, unscaling the domain (which doesn't change the number of zeros), then convolving the function with an appropriate (very fat) Gaussian to obtain the real F , and invoking Theorem B.1 to say that the number of zeros does not increase from this convolution.

B.2 THE FUNCTION L:

In this section, we derive the form of L. By definition, we have

EQUATION

)

It is not to hard to see from the Fundamental theorem of calculus that L is indeed a smooth function of all parameters.

C ALTERNATIVE INDUCED DYNAMICS:

Our focus in this paper is on the dynamics induced by, since it arises naturally from the form of the total variation distance (3) and follows the canonical form of GAN dynamics (1). However, one could consider other equivalent definitions of total variation distance too. And these definitions could, in principle, induce qualitatively different behavior of the first order dynamics.

As mentioned in Section 3, an alternative dynamics could be induced by the definition of total variation distance given in (10). The corresponding loss function would be

EQUATION

i.e. the same as in ( 6) but with absolute values on the outside of the expression. Observe that this loss function does not actually fit the form of the general GAN dynamics presented in (1). However, it still constitutes a valid and fairly natural dynamics. Thus one could wonder whether similar behavior to the one we observe for the dynamics we actually study occurs also in this case.

To answer this question, we first observe that by the chain rule, the (sub)-gradient of L with respect to µ, , r are given by

∇ µ L (µ, , r) = sgn (L(µ, , r)) ∇ µ L(µ, , r) ∇ L (µ, , r) = sgn (L(µ, , r)) ∇ L(µ, , r) ∇ r L (µ, , r) = sgn (L(µ, , r)) ∇ r L(µ, , r) ,

that is, they are the same as for L except modulated by the sign of L.

We now show that the optimal discriminator dynamics is identical to the one that we analyze in the paper (7), and hence still provably converge. This requires some thought; indeed a priori it is not even clear that the optimal discriminator dynamics are well-defined, since the optimal discriminator is no longer unique. This is because for any µ * , µ, the sets

EQUATION

)

However, we show that the optimal discriminator dynamics are still well-formed. WLOG assume that A1 G µ (x) -G µ * (x)dx ≥ 0, so that A 1 is also the optimal discriminator for the dynamics we consider in the paper. If we let (i) , r (i) be the left and right endpoints of the intervals in A i for i = 1, 2, we have that the update to µ induced by ( (1) , r (1) ) is given by 1) , r (1) ) , so the update induced by ( (1) , r (1) ) is the same as the one induced by the optimal discriminator dynamics in the paper. Moreover, the update to µ induced by ( (2) , r (2) ) is given by

EQUATION

∇ µ L (µ, (2) , r (2) ) = sgn L(µ, (2) , r (2) ) ∇ µ L(µ, (2) , r (2) ) (a) = -∇ µ (-L(µ, (1) , r (1) )) = ∇ µ L(µ, (1) , r (1) ) ,

where (a) follows from the assumption that A1 G µ (x) -G µ * (x)dx ≥ 0 and from ( 13), so it is also equal to the the one induced by the optimal discriminator dynamics in the paper. Hence the optimal discriminator dynamics are well-formed and unchanged from the optimal discriminator dynamics described in the paper.

Thus the question is whether the first order approximation of this dynamics and/or the unrolled first order dynamics exhibit the same qualitative behavior too. To evaluate the effectiveness, we performed for these dynamics experiments analogous to the ones summarized in Figure 2 in the case of the dynamics we actually analyzed. The results of these experiments are presented in Figure 4 . Although the probability of success for these dynamics is higher, they still often do not converge. We can thus see that a similar dichotomy occurs here as in the context of the dynamics we actually study. In particular, we still observe the discriminator collapse phenomena in these first order dynamics. It might be somewhat surprising that even with absolute values discriminator collapse occurs. Originally the discriminator collapse occurred because if an interval was stuck in a negative region, it always subtracts from the value of the loss function, and so the discriminator is incentivized to make it disappear. Now, since the value of the loss is always nonnegative, it is not so clear that this still happens.

Despite this, we still observe discriminator collapse with these dynamics. Here we describe one simple scenario in which discriminator collapse still occurs. Suppose the discriminator intervals have left and right endpoints , r and L(µ, , r) > 0. Then, if it is the case that

ri i G µ * (x)-G µ (x)dx < 0 for some i = 1, 2.

that is, on one of the discriminator intervals the value of the loss is negative, then the discriminator is still incentivized locally to reduce this interval to zero, as doing so increases both L(µ, , r) and hence L (µ, , r). Symmetrically if L(µ, , r) < 0 and there is a discriminator interval on which the loss is positive, the discriminator is incentivized locally to reduce this interval to zero, since that increases L (µ, , r). This causes the discriminator collapse and subsequently causes the training to fail to converge.

D OMITTED PROOFS FROM SECTION 4.1:

This appendix is dedicated to a proof of Theorem 4.1. We start with some remarks on the proof techniques for these main lemmas. At a high level, Lemmas 4.3, 4.5, 4.6 all follow from involved case analyses. Specifically, we are able to deduce structure about the possible discriminator intervals by reasoning about the structure of the current mean estimate µ and the true means. From there we are able to derive bounds on how these discriminator intervals affect the derivatives and hence the update functions.

To prove Lemma 4.4, we carefully study the evolution of the optimal discriminator as we make small changes to the generator. The key idea is to show that when the generator means are far from the true means, then the zero crossings of F ( µ, x) cannot evolve too unpredictably as we change µ. We do so by showing that locally, in this setting F can be approximated by a low degree polynomial step where µ ∈ Opt(δ ), we end the step outside of this set but still in Opt(2δ ). By Lemma D.2, for a sufficiently small choice of constant in the definition of δ , the TV-distance at the end of such a step will be at most δ.

Contrapositively, in any step where the TV-distance at the start is more than δ, we will have at the start that µ ∈ Opt(δ ). Then, it suffices to prove that the step decreases the total variation distance additively by at least 1/ poly(C, e C 2 , 1/δ) in this case. For appropriate choices of constants in expression for the step size (sufficiently small multiplicative and sufficiently large in the exponent), this is immediately implied by Lemma 4.4 and Lemma 4.2 provided that µ * , µ, µ ∈ B(2C) and | µ 1 -µ 2 | ≥ δ at the beginning of each step. The condition that we always are within B(2C) at the start of each step is proven in Lemma 4.6 and the condition that the means are separated (ie., that we don't have mode collapse) is proven in Lemma 4.5.

It is interesting that a critical component of the above proof involves proving explicitly that mode collapse does not occur. This suggests the possibility that understanding mode collapse may be helpful in understanding convergence of Generative Adversarial Models and Networks.

D.4 PROOF OF LEMMA 4.3:

In this section we prove Lemma 4.3. We first require the following fact:

Fact D.5 ((Markov, 1892)). Let p(x) = d i=0 c j x j be a degree d polynomial so that |p(x)| ≤ 1 for all x ∈ [-1, 1]. Then max 0≤j≤d |c j | ≤ ( √ 2 + 1) d . More generally, if |p(x)| ≤ α for all x ∈ [-ρ, ρ], then max 0≤j≤d |c j ρ j | ≤ O(α).

We also have the following, elementary lemma:

Lemma D.6. Suppose µ 2 > µ *

i for all i. Then there is some x > µ 2 so that F µ * ( µ, x) < 0.

We are now ready to prove Lemma 4.3

Proof of Lemma 4.3. We proceed by case analysis on the arrangement of the µ and µ * .

Case 1: µ * 1 < µ 1 and µ * 2 < µ 2 In this case we have F µ * ( µ, x) ≤ 0 for all x ≥ µ 2 . Hence the optimal discriminators are both to the left of µ 2 . Moreover, by a symmetric logic we have F µ * ( µ, x) ≥ 0 for all x ≤ µ * 1 , so the optimal discriminator has an interval of the form

I 1 = [-∞, r 1 ] and possibly I 2 = [l 2 , r 2 ] where r 1 < l 2 < r 2 < µ 2 . Then it is easy to see that ∂f ∂ µ2 ( µ 2 ) ≥ 1 √ 2π e -( µ2-r2) 2 /2 ≥ 1 √ 2π e -2C 2 .

Case 2: µ 1 < µ * 1 and µ 2 < µ * 2 This case is symmetric to Case (1).

Case 3: µ 1 < µ * 1 < µ * 2 < µ 2 By Lemma D.6, we know that F µ * ( µ, x) < 0 for some x ≥ µ 2 , and similarly

F µ * ( µ, x) < 0 for some x ≤ µ 1 . Since clearly F (µ * )( µ, x) > 0 for x ∈ [µ * 1 , µ * 2 ]

, by Theorem B.2 and continuity, the optimal discriminator has one interval. Denote it by I = [ , r], so that we have

≤ µ * 1 and r ≥ µ * 2 . Suppose ≥ µ 1 . Then ∂f ∂ µ 1 ( µ 1 ) = 1 √ 2π e -( µ1-) 2 /2 -e -( µ1-r) 2 /2 = 1 √ 2π e -( µ1-) 2 /2 1 -e -( µ1-)(r-) e -(r-) 2 /2 ≥ 1 √ 2π e -2C 2 1 -e -δ 2 /2 .

We get the symmetric bound on

∂f µ * ∂ µ2 ( µ 2 ) if r ≤ µ 2 . The final case is if < µ 1 < µ 2 < r.

Consider the auxiliary function:

H(µ) = e -( -µ) 2 /2 -e -(r-µ) 2 /2 .

On the domain [ , r], this function is monotone decreasing. Moreover, for any µ ∈ [ , r], we have

H (µ) = ( -µ)e -( -µ) 2 /2 -(r -µ)e -(r-µ) 2 /2 ≤ - r - 2 e -(r-) 2 /8 ≤ - γ 2 e -γ 2 /8 .

In particular, this implies that H( µ 1 ) < H( µ 2 ) -γ 2 e -γ 2 /8 /2, so at least one of H( µ 2 ) or H( µ 1 ) must be γ 2 e -γ 2 /8 /4 in absolute value. Since

∂f µ * ∂ µi ( µ i ) = H( µ i )

, this completes the proof in this case.

Case 4: µ * 1 < µ 1 < µ 2 < µ * 2 By a symmetric argument to Case 3, we know that the optimal discriminator intervals are of the form (-∞, r] and [ , ∞) for some r < µ 1 < µ 2 < . The form of the derivative is then exactly the same as in the last sub-case in Case 3 with signs reversed, so the same bound holds here. D.5 PROOF OF LEMMA 4.4

We now seek to prove Lemma 4.4. Before we do so, we need to get lower bounds on derivatives of finite sums of Gaussians with the same variance. particular, we first show: Lemma D.7. Fix γ ≥ δ > 0 and C ≥ 1. Suppose we have µ * , µ ∈ B(C), µ * , µ ∈ Sep(γ), with µ ∈ Rect(δ), where all these vectors have constant length k. Then, for any x ∈ [-C, C], we have that 1) e -C 2 /2 for some i = 0, . . . , 2k -1.

| d i dx i F µ * ( µ, x)| ≥ Ω(1) • (δ/C) O(

Proof. Observe that the value of the ith derivative of F µ * ( µ, x) for any x is given by

d i dx i F µ * ( µ, x) = 1 √ 2π 2k j=1 w j (-1) i H i (z j )e -z 2 j /2 ,

where w j ∈ {-1/k, 1/k}, the z j is either x -µ * j or x -µ j , and H i (z) is the ith (probabilist's) Hermite polynomial. Note that the (-1) i H i are orthogonal with respect to the Gaussian measure over R, and are orthonormal after some finite scaling that depends only on i and is therefore constant. Hence, if we form the matrix M ij = (-1) i H i (x -z j ), if we define u i = d i dx i F µ * ( µ, x) for i = 0, . . . , 2k -1, we have that M v = u, where v j = 1 √ 2π w j e -(x-zj ) 2 /2 . By assumption, we have

v 2 ≥ Ω( √ k • e -C 2 /2 ) = Ω(e -C 2 /2

). Thus, to show that some u i cannot be too small, it suffices to show a lower bound on the smallest singular value of M . To do so, we leverage the following fact, implicit in the arguments of (Gautschi, 1990) : Gautschi, 1990) ). Let p r (z) be family of orthonormal polynomials with respect to a positive measure dσ on the real line for r = 1, 2, . . . , t and let z 1 , . . . , z t be arbitrary real numbers with z i = z j for i = j. Define the matrix V given by V ij = p i (z j ). Then, the smallest singular value of V , denoted σ t (V ), is at least

Theorem D.8 ((

σ min (V ) ≥ R t r=1 r (y) 2 dσ(y) -1/2

, where r (y) = s =r y-zs zr-zs is the Langrange interpolating polynomial for the z r .

Set p r = H r-1 t = 2k, and σ as the Gaussian measure; then apply the theorem. Observe that for any i, j, we have |z i -z j | ≥ min(δ, γ) ≥ δ and |z i | ≤ C. Hence the largest coefficient of any Lagrange interpolating polynomial through the z i is at most ( C δ ) 2k-1 with degree 2k -1. So, the square of any such polynomial has degree at most 2(2k -1) and max coefficient at most 2k( C δ ) 2(2k-1) This implies that

R 2k r=1 r (y) 2 dσ(y) = 2k r=1 R r (y) 2 dσ(y) ≤ 2k r=1 2(2k -1) • 2k C δ 2(2k-1) max s∈[2(2k-1)] R y s dσ(y) ≤ O(1) • C δ 4k max s∈[4k] ∞ -∞ y s e -y 2 /2 dy ≤ O(1) • C δ O(1)

.

Hence by Theorem D.8 we have that σ min (V ) ≥ Ω(1) • δ

Let Z ± denote the set of all x ∈ A for which F ( µ , x) and F ( µ, x) have different nonzero signs. Let Z + denote the subset of Z ± where F ( µ , x) > 0 > F ( µ, x) and Z -denote the subset where F ( µ , x) < 0 < µ, x). Then Z ± = Z + ∪ Z -and Z + , Z -are disjoint and Lebesgue-measurable. If vol(Z + ) ≤ vol(Z -), switch µ and µ so that vol(Z + ) ≥ vol(Z -).

Note that Z + can be obtained by making cuts in the real line at the zeros of F ( µ , x), F ( µ, x), and F ( µ , x) -F ( µ, x), then taking the union of some subset of the open intervals induced by these cuts. By Theorem B.2, the total number of such intervals is O(1). Thus, Z + is the union of a constant number of open intervals. By similar arguments, Z -is also the union of a constant number of open intervals.

We now prove that vol(Z + ), 1) . Note also that by Lemma D.2, each of these intervals has mass under 1) . Since there are at most a constant number of such intervals, this is also a bound on vol(Z + ) (and vol(Z -)).

Z -1 ≤ O(1) • µ -µ Θ(1) 1 • (δe -C 2 /C) -O(1) . Since vol(Z + ) ≥ vol(Z -), it suffices to prove vol(Z + ) ≤ O(1) • µ -µ Θ(1) 1 • (δe -C 2 /C) -O(

F ( µ , x) at most R |F ( µ , x) -F ( µ, x)|dx ≤ O(1) • µ -µ 1 . By Lemma D.11 and Lemma 4.3, each of these intervals has length at most O(1) • µ -µ Θ(1) 1 • (δe -C 2 /C) -O(

Let Y denote the set of x ∈ A on which both F ( µ, x) and F ( µ , x) are nonnegative. Let X, X denote the x ∈ A for which F ( µ, x) and F ( µ , x) are respectively positive. Let W, W denote, respectively, the sets of endpoints of the union of the optimal discriminators for µ, µ . Then the union of the optimal discriminators for µ, µ are respectively Y ∪ Z -∪ X ∪ W and Y ∪ Z + ∪ X ∪ W . Furthermore, each of these two unions is given by some constant number of closed intervals and more specifically, that X, X each contain at most two intervals by Lemma B.2. Thus, we have for any i that

∂ ∂ µ i TV(µ * , µ) µ µ = Y ∪Z + ∪W ∪X d dx e (x-µ i ) 2 /2 dx - Y ∪Z -∪W ∪X d dx e (x-µi) 2 /2 dx ≤ Y ∪Z + ∪W ∪X d dx e (x-µi) 2 /2 dx - Y ∪Z -∪W ∪X d dx e (x-µi) 2 /2 dx + O(1) • | µ i -µ i | ,

by Lipschitzness, and so

∂ ∂ µ i TV(µ * , µ) µ µ = Z + ∪X d dx e (x-µi) 2 /2 dx - Z -∪X d dx e (x-µi) 2 /2 dx + O(1) • | µ i -µ i | ≤ Z + d dx e (x-µi) 2 /2 dx ± 4 100 • K - Z - d dx e (x-µi) 2 /2 dx ± 4 100 • K + O(1) • | µ i -µ i | ≤ Z + d dx e (x-µi) 2 /2 dx + Z - d dx e (x-µi) 2 /2 dx + 8 100 • K + O(1) • | µ i -µ i | ≤ 2vol(Z + ) sup x∈R d dx e (x-µi) 2 /2 + 8 100 • K + O(1) • | µ i -µ i | ≤ O(1) • µ -µ Θ(1) 2 • (δe -C 2 /C) -O(1) + 8 100 • K .

This bound also upper bounds ∇f µ * ( µ ) -∇f µ * ( µ) 2 up to a constant factor. Thus, if we choose our step to have magnitude µ - 1) with appropriate choices of constants, we get

µ 2 ≤ Ω(1) • (δe -C 2 /C) O(

∇f µ * ( µ ) -∇f µ * ( µ) 2 ≤ K/2 ≤ ∇f µ * ( µ) 2 /2 ,

as claimed D.6 PROOF OF LEMMA 4.5

We now prove Lemma 3.4, which forbids mode collapse.

Proof of Lemma 4.5.

Since η ≤ δ, if | µ 1 -µ 2 | > 2δ then clearly µ ∈ Sep(δ), since the gradient is at most a constant since the function is Lipschitz. Thus assume WLOG that | µ 1 -µ 2 | ≤ 2δ ≤ γ/50.

There are now six cases:

Case 1: µ 1 ≤ µ * 1 ≤ µ * 2 ≤ µ 2 This case cannot happen since we assume | µ 1 -µ 2 | ≤ 2δ ≤ γ/50. Case 2: µ * 1 ≤ µ 1 ≤ µ 2 ≤ µ * 2

In this case, by Lemma D.6, we know F is negative at -∞ and at +∞.

Since clearly F ≥ 0 when x ∈ [µ * 1 , µ * 2 ]

, by Theorem B.2 and continuity, the discriminator intervals must be of the form (-∞, r], [ , ∞) for some r ≤ µ 1 ≤ µ 2 ≤ . Thus, the update to µ i is (up to a constant factor of √ 2π) given by e -( -µi) 2 /2 -e -(r-µi) 2 /2 . The function Q(x) = e -( -x) 2 /2 -e -(r-x) 2 /2 is monotone on x ∈ [r, ], and thus µ i must actually move away from each other in this scenario.

Case 3: µ * 1 ≤ µ 1 ≤ µ * 2 ≤ µ 2 In this case we must have |µ * 2 -µ 1 | ≤ 2δ and similarly |µ * 2 -µ 2 | ≤ 2δ.

We claim that in this case, the discriminator must be an infinitely long interval (-∞, m] for some m ≤ µ 1 . This is equivalent to showing that the function F ( µ, x) has only one zero, and this zero occurs at some m ≤ µ 1 . This implies the lemma in this case since then the update to µ 1 and µ 2 are then in the same direction, and moreover, the magnitude of the update to µ 1 is larger, by inspection.

Thus, altogether we have:

√ 2π ∂F ∂x ( µ, x) ≤ -2re -α 2 /2 + O δH 2 (δ)e -(r-10δ) 2 /2

< 0 by our choice of δ, and since r = γ/2 > δ/25.

Case 4:

µ 1 ≤ µ * 1 ≤ µ 2 ≤ µ * 2

This case is symmetric to Case 3, and so we omit it. Case 5:

µ * 1 ≤ µ * 2 ≤ µ 1 ≤ µ 2

In this case, we proceed as in the proof of Theorem B.2. If the Gaussians were sufficiently skinny, then by the same logic as in the proof of Theorem B.2, there is exactly one zero crossing. The lemma then follows in this case by Theorem B.1.

Case 6: µ 1 ≤ µ 2 ≤ µ * 1 ≤ µ * 2 This case is symmetric to Case 5.

This completes the proof. D.7 PROOF OF LEMMA 4.6

We also show that no terribly divergent behavior can occur. Formally, we show that if the true means are within some bounded box, then the generators will never leave a slightly larger box.

Proof of Lemma 4.6. If µ ∈ B(C), then since f is Lipschitz and η is sufficiently small, clearly µ ∈ B(C). Thus, assume that there is an i = 1, 2 so that | µ i | > C, and let µ 1 be the largest such i in magnitude. WLOG take µ 2 > 0. In particular, this implies that µ 2 > µ * i for all i = 1, 2. There are now 3 cases, depending on the position of µ 1 .

Case 1: µ 1 ≥ µ * 2 : Here, as in Case 2 in Lemma 4.5, the optimal discriminator is of the form (-∞, r] for some r ≤ µ 1 , µ 2 . In particular, the update step will be µ i = µ i -ηe -(r-µi) 2 /2 < µ i .

Thus, in this case our update moves us in the negative direction. By our choice of η, this implies that 0 ≤ µ 2 < µ 2 . Moreover, since µ 1 ≥ µ * 2 , this implies that | µ 1 | ≤ C, and thus | µ 1 | ≤ 2C. Therefore in this case we stay within the box.

Case 2: µ * 1 ≤ µ 1 ≤ µ * 2 : As in Case 1, we know that µ 1 cannot leave the box after a single update, as | µ 1 | ≤ C. Thus it suffices to show that µ 2 moves in the negative direction. By Lemma D.6, we know there is a discriminator interval at -∞, and there is no discriminator interval at ∞. Moreover, in this case, we know that F ( µ, x) ≥ 0 for all x ≥ µ 2 . Thus, all discriminators must be to the left of µ 2 . Therefore, the update to µ 2 is given by

µ 2 = µ 2

-η e -(r2-µ2) 2 /2 -e -( 2 -µ2) 2 /2 + e -(r1-µ2) 2 /2 , for some r 1 ≤ 2 ≤ r 2 ≤ µ 2 . Clearly this update has the property that 0 ≤ µ 2 < µ 2 , and so the new iterate stays within the box.

Case 3: µ 1 ≤ µ * 2 In this case we must prove that neither µ 1 nor µ 2 leave the box. The two arguments are symmetric, so we will focus on µ 2 . Since η is small, we may assume that µ 2 > 3C/2, as otherwise µ 2 cannot leave the box. As in Case 1, it suffices to show that the endpoints of the discriminator intervals are all less than µ 2 . But in this case, we have that for all x ≥ µ 2 , the value of the true distribution at x is at most 2e -(x-C) 2 /2 , and the value of the discriminator is at e -(x-µ 2 ) 2 /2 ≥ e -(x-1.5C) 2 /2 . By direct calculation, this is satisfied for any choice of C satisfying 2e 5C 2 /8 < e 3C 2 /4 , which is satisfied for C ≥ 3.

E SINGLE GAUSSIAN:

Although our proof of the two Gaussian case implies the single Gaussian case, it is possible to prove the single Gaussian case in a somewhat simpler fashion, while still illustrating several of the high-level components of the overall proof structure. Therefore, we sketch how to do so, in hopes that it provides additional intuition for the proof for a mixture of two Gaussians.

In order to prove convergence, we can use the following.

1. The fact that the gradient is only discontinuous on a measure 0 set of points.

2. An absolute lower bound on the magnitude of the gradient from below over all points that are not close to the optimal solution that we might encounter over the course of the algorithm

3. An upper bound on how much the gradient can change if we move a certain distance.

Then, as long as we take steps that are small enough to guarantee that the gradient never changes by more than half the absolute lower bound, we will get by Lemma 4.2 that we always make progress towards the optimum solution in function value unless we are already close to the optimal solution.

The proof of these facts is substantially simplified in the single Gaussian case. Suppose we have a true univariate Gaussian distribution with unit variance and mean µ * , along with a generator distribution with unit variance and mean µ. Then the optimal discriminator for this pair of distributions starts at the midpoint between their means and goes in the direction of the true distribution off to ∞ or -∞. Therefore, unless the generator mean is within one step length of the true mean, it cannot move away from the true mean. One can also argue that the gradient of µ with respect to the optimal discriminator (ie., the gradient of total variation distance) is only discontinuous when µ = µ * , and has magnitude roughly e ( µ-( µ+µ * )/2) 2 /2 for µ = µ * . This implies the first two items. For the last item, note that the midpoint e z 2 /2 , which implies the gradient is Lipschitz as long as we are not at the optimal solution, which gives bounds on how much the gradient can change if we move a certain distance.

The preceding discussion implies convergence for an appropriately chosen step size, and all this can be made fully quantitative if one works out the quantitative versions of the statements in the preceding argument.

This analysis is simpler the the two Gaussians analysis in several respects. In particular, the proofs of the second two items are substantially more involved and require many separate steps. For example, in the two Gaussian case, the gradient can be 0 if mode collapse happens, so we have to directly prove both that mode collapse does not happen and that the gradient is large if mode collapse doesn't happen and we aren't too close to the optimal solution, which is a substantially more involved condition to prove. Additionally, the gradient in the two Guassian case does not seem to be Lipschitz away from the optimum like it is in the single Gaussian case. Instead, we will have to use a weaker condition which is considerably more difficult to reason about. This is further complicated by the fact that the optimal discriminators can move in a discontinuous fashion when we vary the generator means.

:

We actually analyze a minor variation on the optimal discriminator dynamics. In particular, we do not rule out the existence of a measure zero set on which the dynamics are ill-behaved. Thus, we will analyze the optimal

Figures and Tables:

and a monotone measuring function m : R → R, the objective of GAN training is to find a generator u in arg min u∈U max v∈V E x∼P [m(D v (x))] + E x∼Gu [m(1 -D v (x))] .

Figure1: A selection of different GAN behaviors. In all plots the true distribution was G µ * with µ * = (-0.5, 0.5), and step size was taken to be 0.1. The solid lines represent the two coordinates of µ, and the dotted lines represent the discriminator intervals. In order: (a) first order dynamics with initial conditions that converge to the true distribution. (b) First order dynamics with initial conditions that exhibit wild oscillation before mode collapse. (c) Optimal discriminator dynamics. (d) First order dynamics that exhibit vanishing gradients and converge to the wrong distribution. Observe that the optimal discriminator dynamics converge, and then the discriminator varies wildly, because the objective function is not differentiable at optimality. Despite this it remains roughly at optimality from step to step.

Figure 2: Heatmap of success probability for random discriminator initialization for regular GAN training, unrolled GAN training, and optimal discriminator dynamics.

Figure 3: Example of Discriminator Collapse. The initial configuration has µ * = {-2, 2}, µ = {-1, 2.5}, left discriminator [-1, 0.2], and right discriminator [-1, 2.5]. The (multiplicative) step size used to generate (c), (d), and (e) was 0.3.

Figure 4: Heatmap of success probability for random discriminator initialization for regular GAN training, unrolled GAN training with dynamics induced by 12

Peer review (iclr2018):
 Although GAN recently has attracted so many attentions, the theory of GAN is very poor. This paper tried to make a new insight of GAN from theories and I think their approach is a good first step to build theories for GAN. However, I believe this paper is not enough to be accepted. The main reason is that the main theorem (Theorem 4.1) is too restrictive. 1. There is no theoretical result for failed conditions. 2. To obtain the theorem, they assume the optimal discriminator. However, most of failed scenarios come from the discriminator dynamics as in Figure 2. 3. The authors could make more interesting results using the current ingredients. For instance, I would like to check the conditions on eta and T to guarantee d_TV(G_mu*, G_hat{mu})<= delta_1 when |mu*_1 – mu*_2| >= delta_2 and |hat{mu}_1 – hat{mu}_2| >= delta_3. In Theorem 4.1, the authors use the same delta for delta_1, delta_2, delta_3. So, it is not clear which initial condition or target performance makes the eta and T.