Title: CPGAN: TOWARDS A BETTER GLOBAL LANDSCAPE OF

Abstract: GANs have been very popular in data generation and unsupervised learning, but our understanding of GAN training is still very limited. One major reason is that GANs are often formulated as non-convex-concave min-max optimization. As a result, most recent studies focused on the analysis in the local region around the equilibrium. In this work, we perform a global analysis of GANs from two perspectives: the global landscape of the outer-optimization problem and the global behavior of the gradient descent dynamics. We find that the original GAN has exponentially many bad strict local minima which are perceived as mode-collapse, and the training dynamics (with linear discriminators) cannot escape mode collapse. To address these issues, we propose a simple modification to the original GAN, by coupling the generated samples and the true samples. We prove that the new formulation has no bad basins, and its training dynamics (with linear discriminators) has a Lyapunov function that leads to global convergence. Our experiments on standard datasets show that this simple loss outperforms the original GAN and WGAN-GP.

1. INTRODUCTION:

Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) have been one of the most popular methods for generating data. The original GAN minimizes the loss φ(p g , p data ) = max D h D (p g , p data ), where h D is a binary classification loss that depends on the discriminator D. To justify the loss, Goodfellow et al. (2014) prove two theoretical results: first, for a given p g , the outer function φ(p g , p data ) is the Jenson-Shannon (JS) distance (minus a constant); second, the outer function is convex in p g , so a gradient descent method on p g converges to the global minimum.

In order to further understand the training behavior of GANs, there has been a surge of interest in min-max optimization or games. One major challenge is the question about which problems to analyze. The first candidates are the two-person matrix game min ψ max θ ψ T Aθ or general convex-concave problems. But the GAN formulation is not a convex-concave problem. As stated by Daskalakis & Panageas (2018) , our knowledge of min-max optimization in non convex-concave settings is "very limited." Therefore, existing results often only analyze local stability or local convergence (Daskalakis et al., 2017; Daskalakis & Panageas, 2018; Azizian et al., 2019; Gidel et al., 2018; Mazumdar et al., 2019; Yazıcı et al., 2018; Jin et al., 2019; Sanjabi et al., 2018) . Local analysis can tell us the behavior of the algorithms near the desired point, but how do we know that the algorithm will arrive there and not at some highly sub-optimal points? Answering this question requires a global landscape analysis or a study of global training dynamics.

There are some attempts on a global analysis of GANs. Mescheder et al. (2018) and Feizi et al. (2017) analyzed the simplest setting: the true data distribution is a single point and a single Gaussian distribution respectively. In these cases, the training dynamics of some GANs can converge to the globally optimal solution. Thus at least in the simplest single-mode setting, there is evidence that the global landscape of (some) GANs is compelling. However, it remains unclear whether those GANs have similarly nice properties in the multi-modal setting. Again, the difficulty here is that the practical GAN formulation is not convex-concave, even for simple discriminators/generators. These works and other related ones are reviewed in more detail in Appendix B.

Our contributions. In this work, we make a step towards understanding the global behavior of GAN training, under multi-modal settings. We focus on analyzing GANs for learning a multi-point distribution. This is a finite-sample version of the problem analyzed by Goodfellow et al. (2014) , and a multi-mode extension of the Dirac-GAN problem analyzed by Mescheder et al. (2018) . We approach the problem from two perspectives. First, we consider the min-max optimization problem and analyze the landscape of the outer problem assuming powerful discriminators. This perspective was used by Goodfellow et al. (2014) . In contrast, as optimization variables we use the samples Y instead of the probability density p g . Second, we consider the training dynamics of the game formulation assuming linear discriminators. Our contributions are summarized as follows.

• For the original GAN, we prove that the outer-minimization problem has exponentially many sub-optimal strict local minima. Each strict local minima corresponds to a modecollapse situation.

• For both the original GAN and WGAN-GP, we prove that with linear discriminators, the training dynamics cannot escape from mode-collapse.

• We propose a new GAN formulation called CP-GAN (CoupleGAN) that enjoys nice global properties. From the first perspective, we prove that the outer-minimization problem of CP-GAN has no bad strict local minima, improving upon the original GAN. From the second perspective, we prove that with linear discriminators, the training dynamics of CP-GAN can escape from mode-collapse; in addition, it has a global Lyapunov function that permits to prove global convergence.

• Our simulation results show that the new GAN performs better than WGAN-GP and the original GAN in standard datasets, in terms of FID scores. Our modification to the loss function has some similarity with the Wasserstein distance (coupling data points), but it turns out it works better than WGAN-GP on all datasets we tested. We remark that CP-GAN is orthogonal to other techniques such as spectral normalization Miyato et al. ( 2018), thus we only compare with vanilla methods such as WGAN-GP.

Finally, we remark that CP-GAN is just one example of GAN problems with nice global properties, and we hope our analysis can shed light on the design of other tractable GAN formulations.

Outline. The rest of the paper is structured as follows. We present the CP-GAN loss in Section 2, and discuss our analysis framework in Section 3. In Section 4, we analyze the outer-optimization problem of JS-GAN and the training dynamics of JS-GAN and W-GAN. In Section 5, we analyze the outer-optimization problem and the training dynamics of CP-GAN. We evaluate its performance on synthetic and standard datasets in Section 6. All proofs are in the Appendix.

2. NEW LOSS: CP-GAN:

In this section, we first review the formulation of GANs briefly. Next, we present the new formulation of CP-GAN. The theoretical advantage of the new formulation will be discussed later.

2.1. GENERATIVE ADVERSARIAL NETWORKS:

We first review the formulation of the original GAN proposed by Goodfellow et al. (2014) . Given samples from a true data distribution p data , we want to generate a new distribution p g to mimic p data . To judge how far away the generated distribution p g is from p data , a discriminator (a.k.a. critic) computes a loss value that measures their gap. This discriminator D addresses a binary classification problem, which should yield 1 for the true data point and 0 for the generated data point. The goal of the generator is to generate p g to fool the discriminator so that the loss value is minimized. Formally, the problem for a GAN is given by min pg max D E x∼p data ,y∼pg log(D(x)) + log(1 -D(y)).

(1)

A common choice for the discriminator is

D(u) = 1 1+exp(-f (u))

, where f is a function. Given this choice, the formulation given in Eq. (1) becomes min pg max f E x∼p data ,y∼pg log 1 1 + exp(-f (x))

+ log 1 1 + exp(f (y)) .

We will use a generator G θ (z) parameterized by θ to produce samples from a distribution p g , where z is drawn from a given distribution p z . This yields the following program:

min G max f E x∼p data ,z∼pz log 1 1 + exp(-f (x)) + log 1 1 + exp(f (G(z)))

.

(2)

To resolve the vanishing gradient issue, Goodfellow et al. (2014) proposed to use a game formulation (often referred to as non-saturating GAN):

EQUATION

min

EQUATION

2.2. COUPLING GAN:

As mentioned before, the program is given in Eq. ( 3) has shortcomings, which we propose to address via the following formulation: 

EQUATION

EQUATION

G problem : min

EQUATION

Here f θ is a deep net parameterized by θ, and G ψ is a generator net parameterized by ψ.

How to interpret the new loss? Our original intuition is to use "personalized criterion". In JS-GAN, the discriminator wants to solve a binary classification problem by finding a single decision boundary that separates true data and generated data. For instance, if true data are x 1 = 1 and x 2 = 2, and generated data are y 1 = 0.5 and y 2 = 0.5, then the boundary is drawn at, say, 0.8. Then the discriminator only has the motivation to approach x 2 = 1, since this would cross the bar of the current discriminator. An analogy is that if the requirement for the students is "get 60 points", then they will try to get 60 points and then rest (surely, there will be follow-up raise, but the raise cannot be too fast, since most students cannot catch). This causes x 2 to be missed by the generator, since it is "too good to learn". In contrast, in CP-GAN, the discriminator provides two boundaries at 0.8 and 1.5, and y 1 will try to cross 0.8 to approach x 1 = 1, and y 2 will try to cross 1.5 to approach x 2 = 2. Thus it can better learn the true distribution. An analogy is that if the requirements are set differently for different students, like one "60 point" and one "90 point", then they will learn to achieve the two goals. Thus CP-GAN is adopting "personalized criterion" for the generated data.

3. MULTI-DIRACGAN: MULTI-MODE GENERATION:

Mescheder (2018) quoted Rahimi: "simple experiments, simple theorems are the building blocks that help us understand more complicated systems." Then they defined a simple model called Dirac-GAN, which uses a linear discriminator and a powerful generator to recover a single-point distribution. We define a much more general model than the DiracGAN. We refer it as Multi-DiracGAN.

Definition 3.1 The Multi-DiracGAN consists of a generator distribution Y = (y 1 , . . . , y n ) ∈ R d×n and a discriminator f (x). The true data distribution is given by a n-point distribution X = (x 1 , . . . , x n ) ∈ R d×n , where x i 's are distinct.

One motivation of the Multi-DiracGAN is to consider an "empirical" version of the problem. Yet another motivation is the construction of a simple model of multi-mode distributions: for instance, when n = 2, we have a two-point distribution which is the simplest two-mode distribution. We are not aware of an existing global analysis that can be applied to this simple 2-point model. See Appendix A for more discussions.

When analyzing an optimization formulation, it is natural to proceed in the following steps: (1) Sanity check, i.e., study whether the globally optimal solutions are desired; (2) Landscape analysis, i.e., check whether there are undesirable local minima; (3) Convergence analysis, i.e., check whether the proposed algorithm converges to a local minimum or stationary point. We will first perform a sanity check and landscape analysis (for powerful discriminators), and then study the dynamics (for linear discriminators).

4. ANALYSIS OF SOME EXISTING GANS:



4.1. JS-GAN HAS EXPONENTIALLY MANY BAD BASINS:

We analyze the landscape of JS-GAN under the Multi-DiracGAN model with powerful discriminators, the formulation of which can be written as:

EQUATION

where

L JS (f ; Y ) = -1 n n i=1 log(1 + exp(-f (x i )) -1 n n i=1 log(1 + exp(f (y i ))). The range of φ JS (Y, X) is [-2 log 2, 0] because L JS (f ; Y ) ≤ 0 and φ JS (Y, X) ≥ L(0; Y ) = -2 log 2

, where L(0; Y ) represents the value achieved at f = 0.

To build intuition, we first present a result for the case of n = 2 points.

Claim 4.1 Suppose n = 2 and x 1 = x 2 ∈ R d . Then φ JS (Y, X) =        -2 log 2 ≈ -1.3862, if {x 1 , x 2 } = {y 1 , y 2 } -log 2 ≈ -0.6931, if |{x 1 , x 2 } ∩ {y 1 , y 2 }| = 1, log 2 -1.5 log 3 ≈ -0.9548, if y 1 = y 2 ∈ {x 1 , x 2 }, 0 if |{x 1 , x 2 } ∩ {y 1 , y 2 }| = ∅.

The global minimum is -2 log 2, which is achieved iff the generated data points {y 1 , y 2 } coincide with the true data points {x 1 , x 2 }.

As a corollary of the above claim, the outer optimization objective of the original GAN has a bad strict local-min when two points overlap (a mode-collapse).

Corollary 4.1 Suppose n = 2 and

x 1 = x 2 ∈ R d . Then Ȳ = (x 1 , x 1 ) is a sub-optimal strict local minimum of the function g(Y ) = φ JS (Y, X).

We illustrate the landscape of φ JS (Y, X) in Figure 1a for the special case that d = 1, x 1 = 0, x 2 = 1.

In this case, Y = (y 1 , y 2 ) = (0, 1) is the global minimum of φ JS (Y, X) with optimal value -2 log 2 ≈ -1.3862, and Y = (0, 0) is a strict local minimum of φ JS (Y, X) with value approximately -0.9548. An intuitive way to understand the landscape and Corollary 4.1 is given as follows. Consider a point (y 1 , y 2 ) moving from (0, 1) to (-0.1, -0.1), going through four points:

(y 1 , y 2 ) = (0, 1), (0, 0.5), (0, 0), and finally (-0.1, -0.1). The four points correspond to the four cases above, thus giving values -1.3862, -0.6931, -0.9548, 0. The four values are not monotone, indicating that there is a strict local minimum at -0.9538.

For general n, the landscape can be characterized in a similar fashion. The following result states that the original GAN objective has exponentially many strict bad local minima.

Proposition 1 Suppose x 1 , x 2 , . . . , x n ∈ R d are distinct. Consider the problem in Eq. ( 6).

(i) The global minimal value is -2 log 2, which is achieved iff the generated data points coincide with the true data points, i.e., {y 1 , . . . , y n } = {x 1 , . . . , x n }.

(ii) If y i ∈ {x 1 , . . . , x n }, i = 1, 2, . . . , n and y i = y j for some i = j, then Y is a sub-optimal strict local minimum. Therefore, φ JS (•, X) has (n n -n!) sub-optimal strict local minima.

The landscape analysis is a high-level analysis that provides some preliminary insight into the training process. But there are two gaps compared to the true training process: (1) in practice, we always (2) the landscape should be two-dimensional, but we only pick illustrative points and and illustrate them in 1D space.

use different objectives for D and G (the -log D trick) to resolve the gradient vanishing issue;

(2) the D problem is addressed via a few gradient steps only. We suspect that the major insight conveyed in the landscape analysis can still carry over to the training dynamics for the following reasons: (1) the objectives for D and G are still closely related thus the "landscape" is still similar (this can be proved rigorously by considering a bi-level optimization problem, which we skip here);

(2) inexactly optimizing D can smooth the landscape, so that the flat regions in φ JS (•, X) becomes smooth (this may be why having a discontinuous outer-function is not too big an issue of JS-GAN). However, we suspect that this smoothing effect cannot easily eliminate some deep basins, especially when there are exponentially many. A complete analysis of this effect is beyond the scope of this paper, and we will just show some evidence by analyzing the training dynamics of JS-GAN with linear discriminators.

4.2. TRAINING DYNAMICS OF JS-GAN:

We consider the non-saturating version of the formulation in Eq. ( 6), which is also the finite-sample version of Eq. (3). We assume a linear discriminator f (u) = w T u + b, where

w ∈ R d , b ∈ R. min θ=(w,b)∈R d ×R L D GAN (Y ; θ) n i=1 log(1 + exp(-w T x i -b)) + log(1 + exp(w T y i + b)), min Y =(y1,...,yn)∈R d×n L G GAN (Y ; θ) n i=1 log(1 + exp(-w T y i -b)).

Consider the dynamics corresponding to the simultaneous gradient descent (GD)1 :

EQUATION

)

EQUATION

)

EQUATION

)

The common method to deal with such complicated dynamics is local linearization. This permits to analyze the local behavior of the dynamics (see, e.g., Mescheder et al. (2018)) . A global analysis of the dynamics often requires a proper Lyapunov function that is non-increasing along the trajectories. But the design of Lyapunov functions is often challenging.

Even if one does not find such a function, one may wonder whether this is due to the lack of technical tools, or due to some intrinsic barriers. Motivated by the landscape result in Proposition 1, we wish to analyze the mode-collapse patterns, i.e., the pattern occurring when some points overlap. Interestingly, we find that collapsed modes cannot be recovered under JS-GAN dynamics, as formally stated in the following claim:

Claim 4.2 Starting from any initial point (θ(0), Y (0)), the trajectory (θ(t), Y (t)) defined in Eq. (20) satisfies y i (t) -y j (t) ≤ y i (0) -y j (0) , ∀t.

This claim predicts that starting from y 1 (0) = y 2 (0) = • • • = y n (0) (all points fall into one mode), prevents these points from separating. It is interesting to more rigorously characterize bad global behavior of JS-GAN dynamics, either for a linear or a neural-net discriminator (e.g., whether modecollapse patterns create bad attractors or limit cycles). Anyhow, the above claim makes it very hard, if not impossible, to prove the global convergence of JS-GAN dynamics for multi-mode problems.

4.3. DISCUSSIONS OF WGAN AND ITS VARIANTS:

One may wonder whether W-GAN or its variants can provide a solution to the above issues. We briefly discuss the difficulties in a global analysis of WGAN and its variants.

For W-GAN with Lipschitz constrain on f , it is not hard to prove that the outer-optimization problem has a nice landscape. However, it is hard to impose the Lipschitz condition in practice; in addition, gradient dynamics with constraints are difficult to analyze2 .

A practical solution to resolve the Lipschitz constraint issue is to add a gradient penalty, which recovers WGAN-GP Gulrajani et al. (2017) . However, the outer-optimization problem

min Y max f i f (x i ) -i f (y i ) -λ i ( ∇ u f (u) | u=yi -1)

2 may have a complicated landscape due to the extra regularization term.

We further show that the dynamics of WGAN-GP with linear discriminators have a similar issue to JS-GAN. The details are provided in Appendix.

Claim 4.3 Starting from any initial point (w(0), Y (0)), the trajectory (w(t), Y (t)) defined by WGAN-GP dynamics satisfies y i (t) -y j (t) = y i (0) -y j (0) , ∀t.

To avoid additional issues due to constraints, we remain interested in the logistic function used in the JS-GAN formulation. We hope that a small modification to the JS-GAN directly addresses its issues. We will now show that CP-GAN does achieve this goal.

5. ANALYSIS OF CP-GAN:

In this section, we analyze the proposed new CP-GAN formulation and show that it has an advantage over the original GAN framework. We highlight again a major difference of our analysis compared to earlier works: we focus on global analysis while most existing results focus on local analysis.

5.1. CP-GAN HAS NO BAD BASIN:

Following the aforementioned steps, the finite-sample version of CP-GAN reads

EQUATION

resulting in a range φ CP (Y, X) ∈ [-log 2, 0]. For simplicity, we define g CP (Y ) = φ CP (Y, X) as the data X are fixed throughout the paper.

Proposition 2 Suppose x 1 , x 2 , . . . , x n ∈ R d are distinct. The global minimal value of g CP (Y ) is -log 2, which is achieved iff {x 1 , . . . , x n } = {y 1 , . . . , y n }. Furthermore, for any Y , there is a continuous path from Y to a global minimum along which the value of g CP (Y ) is non-increasing.

To understand this result, consider the special case n = 2 and

x 1 = x 2 ∈ R d . In this case, we have φ CP (Y, X) =    -log 2 ≈ -0.6931, if {x 1 , x 2 } = {y 1 , y 2 } -1 2 log 2 ≈ -0.3466, if |{i : x i = y i }| = 1 0 otherwise.

We illustrate the landscape of g CP (Y ) in Figure 1b for the special case that n = 2, d = 1, x 1 = 0, x 2 = 1. In this case, (y 1 , y 2 ) = (0, 1) and (y 1 , y 2 ) = (1, 0) are two global minima of g CP (Y ) with optimal value -log 2 ≈ -0.6931. Similar to the previous subsection, there is an intuitive way to understand the landscape: Consider a point (y 1 , y 2 ) moving from (0, 1) to (-0.1, -0.1), going through four points: (y 1 , y 2 ) = (0, 1), then (0, 0.5), then (0, 0), and finally (-0.1, -0.1).

The four points correspond to four values -0.6931, -0.3466, -0.3466, 0. The four values are nondecreasing, indicating that there is a monotone path connecting the mode-collapsed pattern (0, 0) and a global-min (0, 1). This is different from the landscape of the JS-GAN loss, where any path between the two points has to cross some barrier.

Comparing Proposition 2 and Proposition 1, we observe the landscape of CP-GAN to be better than that of the original GAN formulation. How does that help training? Intuitively, the original GAN landscape has many basins of attraction. When starting a random initial point, a descent algorithm might fall into one of the bad basins, causing mode collapse. For CP-GAN, the only basin of attraction is the global minimum, thus the algorithm is more likely to converge to the global minimum.

5.2. TRAINING DYNAMICS OF CP-GAN:

Next, we consider the training dynamics of CP-GAN and reveal nice global properties. Consider the game variant of the GAN formulation in Eq. ( 8), i.e., the finite-sample version of Eq. ( 5). Further, we assume the linear discriminator f (u) = w T u, where w ∈ R d :

EQUATION

Consider the dynamics corresponding to the simultaneous gradient descent for CP-GAN:

EQUATION

)

EQUATION

) Define δ i = y i -x i , ∀i. Define function β ij (t) = 1 2 δ i (t) -δ j (t) 2 , ∀ i, j. Claim 5.1

Along the trajectory defined by Eq. (10), we have

(δ i (t) -δ j (t) ≤ (δ i (0) - δ j (0) , ∀i, j.

This claim looks similar to the result for the JS-GAN dynamics given in Claim 4.2. However, there is an important difference. For the original GAN, the gaps between generated samples are shrinking, while for CP-GAN, the gaps between the errors are shrinking. Thus CP-GAN is a more natural choice from this perspective. This claim only shows the difference of the two GAN formulations, and we will show that CP-GAN has the extra benefit that it has a natural potential function. Consider the function

V = 1 2 w 2 + 1 2 n i=1 x i -y i 2 .

Obviously, V = 0 iff w = 0 and x i = y i , ∀i. According to the following result, V is non-increasing along the trajectory of CP-GAN training. Claim 5.2 Along the trajectory of the dynamics defined in Eq. (10), we have dV (t) dt ≤ 0.

Thus V is a Lyapunov function for the CP-GAN dynamics. As mentioned earlier Mescheder ( 2018) showed that V is a Lyapunov function for the JS-GAN dynamics (non-saturating version) given in Eq. ( 20) if n = 1 and x 1 = 0. However, when we check the case x 1 = 0, we found it is no longer a Lyapunov function. This means that the JS-GAN formulation is not "translation-invariant" in the sense that shifting x i and y i together leads to different dynamics. A simple fix to make it shift-invariant is to a couple Y and X together.

With the Lyapunov function, we have the global convergence to the set θ such that ∇ θ V (θ), h(θ) = 0, where h is the right-hand side of Eq. ( 10). With a bit more effort, we can show the global convergence of CP-GAN dynamics.

Proposition 3 (global convergence of CP-GAN dynamics) Starting from any initial point θ(0), consider the trajectory defined by the CP-GAN dynamics θ(t).

(1) For general d, lim t→∞ θ(t) ∈ E, where E {(w, y) : w T (y i -x i ) = 0, ∀i}.

(2) When d = 1, starting from any initial point θ(0), lim t→∞ θ(t) ∈ M , where M = {(w, y) : w = 0, i x i = i y i }.

The set of stationary points include some undesired points. The next result shows that the Jacobian at these undesired points has a positive real part, thus they are not stable. Simulations also show that small perturbation can escape these undesired points.

Claim 5.3 When d = 1, for the training dynamics given in Eq. (10), at any point other than the desired solution (y 1 , . . . , y n ) = (x 1 , . . . , x n ) in the set of stationary solutions, the Jacobian has an eigenvalue with positive real part.

Now we have a clear understanding of the global behavior of the training dynamics of CP-GAN. The most important fact is that the energy function V is a Lyapunov function. There may be other loss functions that have a Lyapunov function, at least in the simple setting, and we leave that exploration to future work.

6. EXPERIMENTS:

In this section, we present empirical results comparing different GAN loss functions. We aim to show the qualitative and quantitative improvements achieved by using the proposed loss.

6.1. SYNTHETIC DATASETS:

We first demonstrate our results on 2-dimensional synthetic data. Specifically, the 2-dimensional data In all our experiments we train the generator and discriminator in an alternating fashion. The batch size is set to 64. We trained the generator and the discriminator each 30k batch iterations on the MNIST dataset and 100k iterations on the CIFAR-10, STL-10, CelebA and LSUN datasets. We tuned the learning rate for each model to achieve their best performance. Some generated samples are shown in Appendix H.

x = (x 1 , x 2 ) is

We use inception scores (IS) (Salimans et al., 2016) and Frechét Inception distance (FID) (Heusel et al., 2017) to assess the quality of the generated images. We used 50k generated images for IS and 10k true images and 10k generated images for FID metric calculation. We provide the results in Table 1 . We observe the proposed loss to perform better than other losses in terms of Inception Score and FID, on all data sets.

7. CONCLUSION:

The analysis of the population version of GANs is difficult. In this work, we analyzed an empirical version of a few GAN formulations, i.e., assuming the true data distribution is the empirical distribution consists of n points. In this formulation, the samples are moving during the optimization process, which is what is happening in practical training. This analysis can also mimics an n-mode distribution; in fact, it captures the macro-learning part of the learning process. We show that using this perspective, the JS-GAN formulation has exponentially many bad basins, and they correspond to mode collapse. We also show that a new formulation CP-GAN does not have bad basins. Further, we analyzed the training dynamics for the log-linear discriminators, and showed that there is a global Lyapunov function for CP-GAN. Simulation on CELEBA, CIFAR10, etc. shows that the new loss improves FID scores compared to WGAN-GP. This is achieved by only changing two lines of code in Pytorch, which we think is quite remarkable. 

A EMPIRICAL VERSION: EFFECT OF MACRO-LEARNING:

The motivation of analyzing the empirical version is two-fold. First, it is a common practice in machine learning to separately analyze the population version and the empirical version. Second, as we mentioned, "the n-point distribution is an estimation of the n-mode distribution", and we elaborate below.

GANs are implicit generative models, as opposed to the explicit models like energy based models (LeCun et al. ( 2006)) and restricted boltzman machine (Salakhutdinov & Hinton (2009) ). In the implicit models, there is no explicit parameterization of the probabality density. The benefit of implicit models is that it is easier to train and sample from. During the training of GANs, when the parameters of the mapping (i.e. generator) change, it is the generated samples that are moving, not that an explicit probability density is moving. These two views are illustrated in Figure 3 .

Next, we will explain that the two views are both related and orthogonal.

First, there is a connection between the two views. As shown in Figure 4 , we can smooth the empirical distribution (blue color) which is discrete to be a continuous distribution (yellow color).

During the algorithms, the samples are actually moving, but that also corresponds to the moving of the underlying continuous probability density. Thus it is reasonable to assume p g is moving, as an approximation to the real picture that the samples are moving.

Second, we think these two views are orthogonal, and correspond to "macro-learning" and "microlearning" respectively, when learning a multi-mode distribution. Consider learning a two-mode distribution p data , and we start from an initial two-mode distribution p g . There are two differences between p g and p data : first, the locations of the two modes are different; second, the distribution within each mode is different. To learn the distribution, we want to eliminate both differences: first, move the two modes of p g to roughly overlap with the two modes of p data which we call "macro learning"; second, adjust the distributions of each mode to match those of p data , which we call "micro learning". This is illustrated in Figure 5 and Figure 6 .

Therefore, we have explained the two reasons of analyzing the empirical version (the n-point distribution). First, it is the practically used version. Second, it captures the "macro-learning" behavior of learning a multi-mode distribution.

Finally, the two types of learning are related to the two types of mode collapse mentioned in Lin et al. (2018) : "entire modes from the input data are never generated, or the generator only creates images within a subset of a particular mode." Failure of macro-learning can cause missing modes in the generated distributions, which corresponds to the first type of mode collapse. Failure of microlearning can cause a sub-mode of a mode to be missed, which also corresponds to the second type of mode collapse. See more discussions of related works on mode collapse in Appendix B.

A.1 GENERALIZATION One may wonder whether fitting the n data points can cause memorization and thus may not generalize. We explain from two perspectives: first, the existing theory on generalization of GANs; second, intuition why this does not overfit.

First, there exists generalization bounds for GANs. Suppose the true distribution is p data and the generated distribution is p g . Further, suppose we sample n points x i s from p g and sample n points from p g , and use µ and ν to represent the two empirical distributions (discrete distributions with equal probability). Arora et al. (2017) proved that for a large class of GAN problems (including JS-GAN using neural-net discriminator and generators), only polynomial samples are needed to achieve a small generalization error. As a result of the generalization bound, Arora et al. ( 2017) stated that if the GAN successfully minimized the empirical distance (i.e. the distance between µ and ν), then the population distance (the distance between the two distributions p data and p g ) is also small. Therefore, there is a generalization guarantee under suitable conditions. Of course, there is much space in improving the generalization bound of Arora et al. (2017) , and that is an orthogonal line of research. Our goal of this paper is mainly to study how to "successfully minimized the empirical distance" (i.e. fit the n-point distribution µ). Technically speaking, the form of Arora et al. (2017) does not cover CP-GAN, but the proof can be easily extended to CP-GAN.

Second, we provide some intuition why fitting the points may not cause overfitting. Consider a simple case of learning a two-mode distribution in Figure 7 . During training, we learned a generator that maps the latent samples z i 's to x i 's, thus fit the empirical distribution. If we sample a new latent sample z i , then the generator will map z j to a new point x j in the underlying data distribution. Thus fitting the empirical distribution can still leads to generating new data points. 

B RELATED WORKS:

Single-mode analysis. Two papers Feizi et al. (2017 ) Mescheder et al. (2018) provided global analysis of GANs for the single-mode case. Feizi et al. (2017) analyzed the case that the true distribution p data is a single Gaussian distribution. It considers the population version, i.e., there is a continuous latent distribution of p z . For a new formulation called quadratic GAN and using a linear generator and a quadratic discriminator, this paper proved the global convergence of alternating GDA. The min-max problem they consider is a bi-linear function for D and a bi-linear function for G (not a typical a bi-linear game which is linear in either variable, but bi-linear in either variable). They found an interesting Lyapunov function for the min-max problem, leading to the global convergence.

The major difference with our papers is that they considered the single-mode case, while we consider the multi-mode case. There are a few other differences: (a) They consider the population version, and we consider the empirical version. (b) They consider the quadratic discriminator (since to learn a Gaussian, the disciminator needs to be constrained), and we analyze both the powerful discriminator case and the linear discriminator.

To extend to the multi-mode case such as multi-Gaussian, as we discussed earlier, there is a macrolearning effect and micro-learning effect. Our work on n-point distributions captures the macrolearning effect, and Feizi et al. ( 2017) captures the micro-learning effect for Gaussian data. In the future, it would be quite interesting to combine the analysis of Feizi et al. (2017) and our analysis to the multi-Gaussian case.

Mescheder et al. ( 2018) considered the case that the true distribution p data is a single point 0. Even for this case, GDA for all min-max formulations of GANs does not converge locally. However, it proved that for the non-saturating version of JS-GAN, GDA converges to the desired solution 0. Interestingly, we found that their proof cannot be directly generalized to the case that p data is a single non-zero point. Thus even for the single non-zero point setting, it is natural to use our CP-GAN formulation to prove global convergence.

Mode collapse. Mode collapse is one of the major challenges for GANs, and received a lot of attention. Roughly speaking, it means that some "modes" of the true data distributions are not generated. The cause of mode collapse is not well understood, and there are a few high-level hypotheses, such Then T V (Q, P 1 ) = T V (Q, P 2 ), but P 1 has mode collapse while P 2 does not. They proposed to pack the samples, i.e., consider the distance of the product distribution P m and Q m . The main theoretical result that "T V (P m , Q m ) is a better loss to penalize strong mode collapse than T V (P, Q)". Based on this result, they extracted the key idea of "packing" to apply it to any GAN.

Our paper is different from Lin et al. (2018) in the following aspects. First, they did not provide theoretical analysis for a specific GAN; in contrast, we prove theoretical results of specific JS-GAN and CP-GAN formulations. Second, we provided an explanation for "why mode collapse happens", by linking mode collapse to a fundamental optimization subject "bad basin". Third, their focus is to mitigate "bad basin", and our starting point is to analyze the global landscape, and the link to mode collapse is a natural byproduct of the analysis. 

C PROOFS:

φ JS (Y, X) = sup f 1 n n i=1 log 1 1 + exp(-f (x i )) + 1 n n i=1 log 1 1 + exp(f (y i )) = sup D 1 n n i=1 log(D(x i )) + 1 n n i=1 log(1 -D(y i )) .

Consider four cases.

Case 1: Both generated points overlap with the true data points, and are distinct, i.e.,

y 1 = x 1 , y 2 = x 2 or y 2 = x 1 , y 2 = x 2 . Then the objective is sup D 1 2 log(D(x 1 )) + 1 2 log(1 -D(x 1 )) + 1 2 log(D(x 2 )) + 1 2 log(1 -D(x 2 )) .

The optimal value is -2 log 2, which is achieved when D(x 1 ) = D(x 2 ) = 1 2 . The corresponding function values of f are f (x 1 ) = f (x 2 ) = 0. The values of f on other points do not matter.

Case 2: Exactly one of the generated points overlaps with the true data points. Without loss of generality, we can check the case

y 1 = x 1 , y 2 / ∈ {x 1 , x 2 }. The problem becomes sup D 1 2 log(D(x 1 )) + 1 2 log(D(x 2 )) + 1 2 log(1 -D(x 1 )) + 1 2 log(1 -D(y 2 )) .

The optimal value -log 2 ≈ -0.6931 is achieved when D(x 1 ) = 1/2, D(x 2 ) = 1 and D(y 2 ) = 0.

The corresponding function values of f are f

(x 1 ) = -log 2, f (x 2 ) = ∞ and f (y 2 ) = -∞.

Case 3: Both generated points overlap with the true data points, and are the same. Without loss of generality, check the case

y 1 = y 2 = x 1 . sup D 1 2 log(D(x 1 )) + log(1 -D(x 1 )) + 1 2 log(D(x 2 )) .

The optimal value 1 2 log 1 3 + log 2 3 ≈ -0.9548 is achieved when D(x 1 ) = 1/3 and D(x 2 ) = 0. The corresponding function values of f are f (x 1 ) = -log 2, f (x 2 ) = ∞.

Case 4: Both generated points are different from the true data points. y 1 , y 2 / ∈ {x 1 , x 2 }. It becomes separable over the four points

sup D 1 2 log(D(x 1 )) + 1 2 log(D(x 2 )) + 1 2 log(1 -D(y 1 )) + 1 2 log(1 -D(y 2 )) .

Each term can achieve its maximum log 1 = 0. Thus the optimal value 0 is achieved when D(x 1 ) = D(x 2 ) = 1 and D(y 1 ) = D(y 2 ) = 0. The corresponding function values of f are f

(x 1 ) = -∞, f (x 2 ) = ∞ . C.2 PROOF OF COROLLARY 4.1

We re-state the corollary below.

Corollary C.1 Suppose Ȳ = (ȳ 1 , ȳ2 ) satisfies ȳ1 = ȳ2 = x 1 , then it is a sub-optimal strict local minimum of the problem.

Proof: Suppose is the minimal non-zero distance between two points of x 1 , x 2 , y 1 , y 2 . Consider a small perturbation of Ȳ as Y = ( ȳ1 + 1 , ȳ2 + 2 ), where | i | < . We want to verify that φ( Ȳ , X) > φ(Y, X) ≈ -0.9548.

There are two possibilities.

Possibility 1: 1 = 0 or 2 = 0. WLOG, assume 1 = 0, then we must have 2 > 0. Then we still have y 1 = ȳ1 = x 1 . Since the perturbation amount is small enough, we have y 2 / ∈ {x 1 , x 2 }. According to Case 2 above, we have φ( Ȳ , X) = -log 2 ≈ -0.6931 > -0.9548.

Possibility 2: 1 > 0, 2 > 0. Since the perturbation amount 1 and 2 are small enough, we have y 1 / ∈ {x 1 , x 2 }, y 2 / ∈ {x 1 , x 2 }. According to Case 4 above, we have φ( Ȳ , X) = 0 > -0.9548.

Combining both cases, we have proved (12).

Q.E.D.

C.3 PROOF OF PROPOSITION 1 Denote D(u) = 1 1+exp(-f (u)) ∈ [0, 1].

Since f can be any continuous function, D can be any continuous function with range (0, 1).

φ JS (Y, X) = sup f 1 n n i=1 log 1 1 + exp(-f (x i )) + 1 n n i=1 log 1 1 + exp(f (y i )) = sup D 1 n n i=1 log(D(x i )) + 1 n n i=1 log(1 -D(y i )). Denote F (D; Y ) = 1 n n i=1 log(D(x i )) + 1 n n i=1 log(1 -D(y i )). Since D(u) ∈ (0, 1) for any u, then F (D; Y ) ≤ 0. When D(u) → 1 2 , ∀u, we have F (D; Y ) → -2 log 2, thus φ JS (Y, X) = sup D F (D; Y ) ≥ -2 log 2. Thus the range of φ JS (•, •) is [-2 log 2, 0].

Now we compute the value of φ JS (•, X) for each Y . For any i, denote M i to be set of indices of y j such that y j equals x i , and m i to be the size of the set M i , i.e., M i = {j :

y j = x i }, m i = |M i |, i = 1, 2, . . . , n. Denote Ω = {1, 2, . . . , n}\(M 1 ∪ M 2 • • • ∪ M n ). Then we have φ JS (Y, X) = 1 n sup D   n i=1 [log(D(x i )) + j∈Mi log(1 -D(y j ))] + j / ∈Ω log(1 -D(y j ))   = 1 n sup D   n i=1 [log(D(x i )) + m i log(1 -D(x i ))] + j / ∈Ω log(1 -D(y j ))   (i) = 1 n n i=1 sup ti∈R [log(t i ) + m i log(1 -t i )] + 0 (ii) = 1 n n i=1 [log 1 m i + 1 + m i log m i m i + 1 ] = 1 n n i=1 [m i log m i -(m i + 1) log(m i + 1)].

Here (i) is because D(y j ), j ∈ Ω are independent of D(x i )'s and thus can be any values; in this step, the optimal D(y

j ) = 1, ∀j ∈ Ω. (ii) is because for any positive number m, sup t∈R [log(t) + m n i=1 log(1 -t)] = log 1 m+1 + m log m m+1 . When m i = 1, i = 1, 2, . . . , n, i.e., y i = x i , ∀i, the function φ JS (Y, X) achieves value -2 log 2. Thus Y = (x 1 , x 2 , . . . , x n ) is a global minimum. Next, we show that if Y satisfies that if m 1 + m 2 + • • • + m n = n then Y is a strict local-min.

Denote δ as the minimal distance between two points of x 1 , x 2 , . . . , x n , i.e., δ = min

k =l x k -x l .

Consider a small perturbation of Y as Ȳ = ( ȳ1 , ȳ2 , . . . , ȳn ) = (y 1 + 1 , y 2 + 2 , . . . , y n + n ), where j < δ, ∀j and j j 2 > 0. We want to verify that

EQUATION

)

Denote mi = |{j : ȳj = x i }|, i = 1, 2, . . . , n. According to the assumption m 1 + m 2 + • • • + m n = n, we have y j ∈ {x 1 , . . . , x n }, ∀j. Consider an arbitrary j, and suppose y j = x i . Together with ȳj -y j = j < δ = min k =l x k -x l , we have ȳj / ∈ ({x 1 , x 2 , . . . , x n }\{x i }). In other words, the only possible point in {x 1 , . . . , x n } that can coincide with ȳj is x i , and this happens only when j = 0. As a result, we have mi ≤ m i , , i = 1, 2, . . . , n. Together with the fact that t log t -(t + 1) log(t + 1) is a strictly decreasing function in t ∈ [0, ∞), we have

φ JS ( Ȳ , X) = 1 n n i=1 [ mi log mi -( mi + 1) log( mi + 1)] ≥ 1 n n i=1 [m i log m i -(m i + 1) log(m i + 1)] = φ JS (Y, X).

The equality is achieved iff mi = m i , ∀i, which holds iff j = 0, ∀j. Since we have assumed j j 2 > 0, the equality does not hold, thus φ( Ȳ , X) > φ(Y, X). Therefore, we have proved that Ȳ is a strict local minimum.

Finally, if Y satisfies that m 1 + m 2 + • • • + m n = n and m k ≥ 2 for some k, then φ JS (Y, X) > -2 log 2. Thus Y is a sub-optimal strict local minimum. Q.E.D.

D TECHNICAL DETAILS OF SECTION 4.2 AND 4.3

D.1 PROOF OF CLAIM 4.2 Define a function α ij (t) = 1 2 y i (t) -y j (t) 2 , ∀ i, j. dα ij (t) dt = (y i -y j ) T d(y i -y j ) dt = (y i -y j ) T dy i dt - dy j dt = (y i -y j ) T w 1 + e w T yi+b - w 1 + e w T yj +b = (w T y i -w T y j ) 1 1 + e w T yi+b - 1 1 + e w T yj +b ≤ 0.

In the last step, we used the fact that (a 1 -a 2 )

1 1+e a 1 -1 1+e a 2

≤ 0 for any a 1 , a 2 ∈ R. Note that in the above computation, we skip the time index t. Therefore α ij (t) is non-increasing along the trajectory, which implies y i (t) -y j (t) ≤ y i (0) -y j (0) , ∀t.

D.2 PROOF OF CLAIM 4.3 WGAN-GP with linear discriminators can be expressed as:

min w∈R d L D WGAN-GP (Y ; θ) - n i=1 w T x i + n i=1 w T y i + λ( w -1) 2 . min Y =(y1,...,yn)∈R d×n L G WGAN-GP (Y ; θ) - n i=1

w T y i .

Consider the dynamics corresponding to the simultaneous gradient descent for WGAN-GP:

EQUATION

)

EQUATION

)

We will use Lasalle's invariance principle (see, e.g. (Haddad & Chellaboina, 2011, Theorem 3.3) or (Cohen & Rouhling, 2017 , Theorem 1)) to prove this result.

Definition (invariance set).:

A set A is said to be invariant with respect to a differential equation du dt = h(u(t)) if every solution to this equation starting in A remains in A.

Lemma 1 (Lasalle's invariance principle) Consider a dynamical system defined by du dt = h(u(t)), where h is a vector mapping. Assume h has continuous first partial derivatives and h(0) = 0. Let K be an invariant compact set. Suppose there is a scalar function V which has continuous first partial derivatives in K and is such that Ṽ (p) = ∇V (p), h(p) ≤ 0, ∀p ∈ K. Let E be the set of all points p ∈ K such that Ṽ (p) = 0. Let M be the largest invariant set in E. Then for every solution t starting in K, u(t) → M as t → ∞.

Our goal is to show that starting from any initial point θ(0) = (w(0), y(0)), the dynamics defined by ( 10), denoted as θ(t) = (w(t), y(t)) will converge to the set

EQUATION

) Define K = {θ : θ 2 ≤ θ(0) 2 } Since V ≤ 0, we have θ(t) 2 ≤ θ(0) 2 , thus θ(t) ∈ K, ∀t. Thus K is an invariant compact set.

According to Claim 5.2, the set of points p such that Ṽ (p) = 0 is

E {(w, y) : w T (y i -x i ) = 0, ∀i}.

According to the LaSalle's invariance principle, the algorithm will converge to the largest invariance subset of E.Without knowing which set it is, we can already obtain the result that the algorithm converges to the set E. This proves the first part of the result. The analysis so far works for any d.

Next, we will use the condition d = 1. We show that when M defined in ( 15) is the largest invariant set in E. Assume the contrary, that there is a set M M ⊆ E such that M is an invariant set. Then starting from any point θ(0) ∈ E\M , we have θ(t) ∈ M .

Since d = 1, then set E becomes E = {(w, y) ∈ R 1×(n+1) : w(y i -x i ) = 0, ∀i}. Let E 1 = {(w, y) : w = 0} and E 2 = {(w, y) : y i = x i , ∀i}, then E = E 1 ∪ E 2 . The set M is still M = {(w, y) : w = 0, i x i = i y i }.

Since θ(0) ∈ E but not in M , and E 2 ⊆ M , then we have θ(0) ∈ E 1 and θ(0) / ∈ E 2 . This implies w(0) = 0 and i (x i (0) -y i (0)) 2 = 0. According to the fact that Ṽ (p) = 0, ∀p ∈ E and θ(t) ∈ E, we have that

EQUATION

)

Since the path θ(t) ∈ M ⊆ E for all t, we have

θ(t) ∈ E 1 or E 2 . Suppose J = {t ∈ R : θ(t) ∈ E 2 }, then for s ∈ J we have V (θ(s)) = w(s) 2 + 0 = w(s) 2

. By ( 16), we have w(s) 2 = δ, ∀s.

For t / ∈ J, we have θ(t) ∈ E 1 and thus w(t) = 0. Thus w(t) = 0, ∀t / ∈ J and w(t) = δ, ∀s ∈ J. As w(t) is continuous for t and w(0) = 0, we must have J = ∅. This means w(t) = 0 for all t.

Recall the dynamics defined by 10 for the case d = 1 is

EQUATION

)

EQUATION

Along the path θ(t) ∈ E, we have w(t)(y i (t) -x i (t)) = 0, ∀t, thus

dy i (t) dt = 0 1 + e 0 = 0, ∀i, which implies y i (t) = y i (0), ∀i. This further implies dw(t) dt = i [x i (t) -y i (t)] = i [x i (0) - y i (0)]

δ 0 . Since θ(0) ∈ E but not in M , thus we must have i x i (0) = i y i (0), implying δ 0 = 0. Thus dw(t) dt = δ 0 = 0, which contradicts w(t) = 0, ∀t. This contradiction implies that the original assumption that there is a set M

M ⊆ E such that M is an invariant set does not hold. Thus the largest invariant subset of E must be a subset of M .

Finally, if θ(0) ∈ M , then the gradients are zero, thus θ(t) ∈ M, ∀t, which implies that M itself is a invariant set. Thus M is indeed the largest invariant set of E.

E.4 PROOF OF CLAIM 5.3:

We restate the claim below.

Claim E.1 When d = 1, for the training dynamics of (10), at any point other than the desired solution (y 1 , . . . , y n ) = (x 1 , . . . , x n ) in the set of stationary solutions, the Jacobian has an eigenvalue with positive real part3 .

When d = 1, the dynamical system is given by

EQUATION

)

EQUATION

We can write it as θ = h(θ) = (h 0 (θ), . . . , h n (θ)),

where h i is the right hand side of the i-th equation. The Jacobian J = ∇h satisfies the following:

J 11 = ∂h 0 ∂w = n i=1 (x i -y i ) 2 1 + e w(yi-xi) , J 1,i+1 = ∂h 0 ∂y i = - 1 1 + e w(xi-yi) + w(x i -y i ) e w(yi-xi) (1 + e w(yi-xi) ) 2 , ∀i = 1, . . . , n, J i+1,1 = ∂h i ∂w = 1 1 + e w(yi-xi) + w(y i -x i ) e w(yi-xi) (1 + e w(yi-xi) ) 2 , J i+1,i+1 == ∂h i ∂y i = - w 2 e w(yi-xi) (1 + e w(yi-xi) ) 2 J ij = 0, if i, j ≥ 2 and i = j.

When evaluated at θ = (0, y 1 , . . . , y n ), we have It is easy to verify that J only has two non-zero eigenvalues

J 11 = n i=1 (x i -y i ) 2 2 , J 1,i+1 = - 1 2 , ∀i = 1, . . . , n, J i+1,1 = 1 2 , J i+1,j+1 = 0, i, j ≥ 1.

λ 1,2 = 1 2 J 11 ± 1 √ 2 √ -1.

Therefore, when x i = y i , ∀x i , the eigenvalues of the Jacobian have zero real part. When some x i = y i , then the two eigenvalues of the Jacobian have a positive real part, meaning that this stationary point is not stable. This proves the result: in the set of stationary solutions M = {(w, y) : w = 0, i x i = i y i }, any point other than the desired solution (y 1 , . . . , y n ) is not stable.

E.5 ANALYSIS OF CP-GAN DYNAMICS FOR CONVEX CASE:

Next, we consider the training dynamics of a generalized CP-GAN for a convex discriminator.

In (9), we used a log-linear discriminator D(u) = log(1 + e -w T u ) (although we called it a "linear discriminator" previously for simplicity). In this subsection, we show that the same analysis can be extended to a "convex-linear" discriminator. The empirical version with the convex-linear discriminator is presented below; it is an extension of (9).

min θ=w∈R d L D CP (Y ; θ) n i=1 φ(w T (y i -x i )), min Y =(y1,...,yn)∈R d×n L G CP (Y ; θ) n i=1 φ(w T (x i -y i )).

Consider the dynamics corresponding to the simultaneous gradient descent for CP-GAN:

EQUATION

EQUATION

We still consider the function

V = 1 2 w 2 + 1 2 n i=1 x i -y i 2 .

According to the following result, V is non-increasing along the trajectory of CP-GAN training with convex discriminators, thus it is still a global Lyapunov function for the dynamics (19).

Claim E.2 Suppose φ is a convex function. Along the trajectory of the dynamics defined in Eq. ( 19), we have dV (t) dt ≤ 0.

Proof of Claim E.2: Let u i = w T (y i -x i ), i = 1, . . . , n, we have

EQUATION

In the last step we used the fact that u(φ (-u) -φ (u)) ≤ 0, ∀u ∈ R due to the convexity of φ.

Note that in the above computation, we skip the time index t.

Thus V is a Lyapunov function for the CP-GAN dynamics with convex discriminators. 2

It is not hard to extend the convergence results to this case, and we skip the details.

F PROOF OF PROPOSITION 2 FOR n = 2

Without loss of generality, we can consider two points

x 1 = 0, x 2 = 1. The problem becomes g CP (Y ) = sup f ∈F 1 2 log 1 1 + exp(f (0) -f (y 1 )) + 1 2 log 1 1 + exp(f (1) -f (y 2 ))

,

where F is the set of continuous functions with domain R d . We compute all values of g CP (Y ) as follows.

Case 1: The two generated points are the same as the true data points, i.e., {x 1 , x 2 } = {y 1 , y 2 }. If

y 1 = 0, y 2 = 1, then g CP (Y ) = 1 2 [log 1/2 + log 1/2] = -log 2 ≈ -0.6937. If y 1 = 1, y 2 = 0, then g CP (Y ) = sup f ∈F 1 2 log 1 1 + exp(f (0) -f (1)) + 1 2 log 1 1 + exp(f (1) -f (0)) = sup t∈R 1 2 log 1 1 + exp(t) + 1 2 log 1 1 + exp(-t) = -log 2.

Case 2: Exactly one of the generated points coincides with the corresponding true data point, i.e., |{i : y i = x i }| = 1. Without loss of generality, we can check the case y 1 = 0, y 2 = 1. Then

g CP (Y ) ≥ sup f ∈F 1 2 log 1 1 + exp(f (0) -f (0)) + 1 2 log 1 1 + exp(f (1) -f (y 2 )) = - 1 2 log 2 + sup t∈R 1 2 log 1 1 + exp(t) = - 1 2 log 2 ≈ -0.3466.

The value is achieved when f (1)-f (y 2 ) → -∞ (or more precisely, there is a sequence of functions such that the difference f (1) -f (y 2 ) goes to minus infinity).

Case 3: Both generated points are different from the true data points, i.e., |{i :

y i = x i }| = 1. Then g CP (Y ) ≥ sup f ∈F 1 2 log 1 1 + exp(f (0) -f (y 1 )) + 1 2 log 1 1 + exp(f (1) -f (y 2 )) = sup t1∈R,t2∈R 1 2 log 1 1 + exp(t 1 ) + 1 2 log 1 1 + exp(t 2 ) = 0.

The value is achieved when f (1) -f (y 2 ) → -∞ and f (0) -f (y 2 ) → -∞.

According to the above results, the only global minima are {y 1 , y 2 } = {x 1 , x 2 }. In addition, from any Y , it is easy to verify that there is a non-decreasing path from Y to a global minimum.

G PROOF OF PROPOSITION 2 FOR GENERAL n:

Recall the function

g(Y ) = sup f 1 n n i=1 log 1 1 + exp(f (y i ) -f (x i ))) = -inf f 1 n n i=1 log (1 + exp(f (y i ) -f (x i )))) .

Proposition 5 (restatement of Proposition 2 ) Suppose x 1 , x 2 , . . . , x n ∈ R d are distinct. The global minimal value of g CP (Y ) is -log 2, which is achieved iff {x 1 , . . . , x n } = {y 1 , . . . , y n }. Furthermore, the function g(Y ) has no sub-optimal basin.

The key of the proof is to compute the values of g(Y ) for any Y . Roughly speaking, the value g(Y ) can be computed by the following process:

(1) We can build a graph with vertices representing distinct values in x i s, y i s and draw directed edges from x i to y i . This graph can be decomposed into cycles and trees.

(2) Each vertex in a cycle contributes -1 n log 2 to the value g(Y ).

(3) Each vertex in a tree contributes 0 to the value g(Y ).

Putting these ideas together, the value g(Y ) equals -1 n log 2 times the number of vertices in the cycles.

The outline of this section is as follows. In the first subsection, as a warm-up example, we prove that if {y 1 , y 2 , . . . , y n } = {x 1 , . . . , x n }, then Y is a global minimum of g(Y ). In the second subsection, as another warm-up example, we prove that if there exists some y i / ∈ {x 1 , . . . , x n }, then it is not a global minimum. In the third subsection, we prove Proposition 2, in three steps. The proofs of some technical lemmas will be provided in the remaining subsections.

G.1 WARM-UP EXAMPLE 1: ALL GENERATED POINTS MATCH THE TRUE POINTS:

Prove that if {y 1 , y 2 , . . . , y n } = {x 1 , . . . , x n }, then Y is a global minimum of g(Y ).

Suppose y i = x σ(i) , then (σ(1), σ(2), . . . , σ(n)) is a permutation of (1, 2, . . . , n). We view σ as a mapping from {1, 2, . . . , n} to {1, 2, . . . , n}. Pick an arbitrary i, then in the infinite sequence i, σ(i), σ(σ(i)), σ (3) (i), . . . there exists at least two numbers that are the same. Suppose σ (k0) (i) = σ (k0+T ) (i) for some k 0 , T , then since σ is a one-to-one mapping we have i = σ (T ) (i). Then we obtain a cycle C = (i, σ(i), σ (2) (i), . . . , σ (T -1) (i)).

We can divide {1, 2, . . . , n} into the collection of finitely many cycles C 1 , C 2 , . . . , C K . Each cycle C k = (c k (1), c k (2), . . . , c k (m k )) satisfies c k (j + 1) = σ(c k (j)), j = 1, 2, . . . , m k where c k (m k + 1) is defined as c k (1). Now we calculate the value of g(Y ).

g(Y ) = sup f 1 n n i=1 log 1 1 + exp(f (y i ) -f (x i ))) (i) = -inf f 1 n K k=1 i∈C k log (1 + exp(f (y i ) -f (x i )))) = -inf f 1 n K k=1 m k j=1 log 1 + exp(f (x c k (j+1) ) -f (x c k (j) ))) (ii) = - 1 n K k=1 inf f m k j=1 log 1 + exp(f (x c k (j+1) ) -f (x c k (j) ))) = - 1 n K k=1 inf t1,t2,...,tm k ∈R   m k -1 j=1 log (1 + exp(t j+1 -t j )) + log (1 + exp(t 1 -t m k ))   (iii) = - 1 n K k=1 m k log(1 + exp(0)) = -log 2.

Here (i) is because {1, 2, . . . , n} is the combination of C 1 , . . . , C K and i ∈ C k means that i = c k (j) for some j. (ii) is because C k 's are disjoint and f can be any continuous function; more specifically, the values of f at x i 's for i in two different cycles are independent, i.e., the choice of {f

(x i ) : i ∈ C k1 } is independent of the choice of {f (x i ) : i ∈ C k2 } if k 1 = k 2 ,

thus we can take the infimum over each cycle (i.e. put "inf" inside the sum over k).

(iii) is because m-1 j=1 log(1 + exp(t j+1 - t j )) + log (1 + exp(t 1 -t m )

) is a convex function of t 1 , t 2 , . . . , t m and the minimum is achieved at t 1 = t 2 = . . . t m = 0.

G.2 WARM-UP EXAMPLE 2: NEW POINT GENERATED Suppose y j ∈ {x 1 , . . . , x n }, ∀j, and there exist some x i0 that is not equal to any y j . In this part, we compute the value g(Y ) and show that Y is not a global minimum. The computation for this example will illustrate how a "free" variable reduces the objective value g(Y ) by at least -1 n log 2. Later in the general proof, we will see that any vertex not in a cycle will reduce the objective value by exactly -1 n log 2. Consider the term log(1 + exp(f (y i0 ) -f (x i0 ))). Since x i0 does not appear in any other term in i log(1 + exp(f (y i ) -f (x i ))), the choice of f (x i0 ) is free. Therefore, no matter what values of f (x 1 ), . . . , f (x i0-1 ), f (x i0+1 ), . . . , f (x n ) and f (y 1 ), . . . , f (y n ) are, we can always pick f

(x i0 ) so that f (y i0 ) -f (x i0 ) → -∞, making the term log(1 + exp(f (y i0 ) -f (x i0 ))) → 0. g(Y ) = -inf f 1 n n i=1 log (1 + exp(f (y i ) -f (x i )))) = -inf f 1 n i =i0 log (1 + exp(f (y i ) -f (x i )))) + 0 ≥ - 1 n i =i0 log(1 + 1) = - n -1 n log 2.

G.3 FORMAL PROOF OF PROPOSITION 2:

This proof is divided into three steps. In Step 1, we compute the value of g(Y ) if all y i ∈ {x 1 , . . . , x n }. This is the major step of the whole proof. 

We build a directed graph G = (V, A) as follows. The set of vertices V = {1, 2, . . . , n} represents x 1 , x 2 , . . . , x n . We draw a directed edge (i, j) ∈ A if y i = x j ; in this case, there is a term log(1 + exp(f (x j ) -f (x i ))) in the expression of g(Y ). Note that in this directed graph, it is possible to have a self-loop (i, i), which corresponds to the case y i = x i . Because of the assumption (21), we can simply express

EQUATION

Each y i correspond to a unique x j , thus the outdegree of i, denoted as outdegree(i), must be exactly 1; in other words, for each i there is exactly one directed edge going out from i. The indegree of each i, denoted as indegree(i), can be any number in {0, 1, . . . , n}.

To proceed, we need a few definitions from standard graph theory.

Definition G.1 (walk, path and cycle) In a directed graph G, a directed walk (or more simply, walk) W = (v 0 , e 1 , v 1 , e 2 , . . . , v m-1 , e m , v m ) is a sequence of vertices and edges such that v i ∈ V for every i ∈ {0, 1, . . . , m} and e i is a directed edge from v i-1 to v i for every i ∈ {1, . . . , m}.

The set of vertices in W is denoted as V (W ), and the set of edged in W is denoted as A(W ). If v 0 , v 1 , . . . , v m are distinct we call it a directed path (or path), and we say the length of the path is m. If v 0 , v 1 , . . . , v m-1 are distinct and v m = v 0 , we call it a directed cycle (or cycle).

Note that we always say v has a path to itself v (with length 0), no matter whether there is an edge between v to itself or not. This is because the degenerate walk W = (v) satisfies the conditions of the above definition.

Definition G.2 (tree) A directed tree is a directed graph T = (V, A) with a designated node r ∈ V , the root, such that there is exactly one path from v to r for each node v ∈ V and there is no edge from the root r to itself. The depth of a node in a tree is the length of the path from the node to the root (define the depth of the root to be 0). A subtree of a directed graph G is a subgraph T of G = (V, A) which is a directed tree. The set of vertices in T is denoted as V (T ), and the set of edged in T is denoted as A(T ).

We prove a lemma that states that the graph can be decomposed into the union of cycles and trees. A graphical illustration is given in Figure 10 .

Lemma 2 Suppose G = (V, A) is a directed graph and outdegree(v) = 1, ∀v ∈ V . Then we have the following:

(a) There exist cycles C 1 , C 2 , . . . , C K and subtrees T 1 , T 2 , . . . , T M such that each edge v ∈ A appears either in exactly one of the cycles or in exactly one of the subtrees.

(b) The root of each subtree u m is a vertex of a certain cycle C k where 1 ≤ k ≤ K. In addition, each vertex of the graph appears in exactly one of the following sets:

EQUATION

) There is at least one cycle in the graph; With this lemma, we are ready to compute the value g(Y ). According to Lemma 2, we have

EQUATION

We then compute

g cyc . Since C k is a cycle, we have X k {x i : i ∈ C k } = {y i : i ∈ C k }. Since the cycles C k 's are disjoint, we have X k ∩ X l = ∅, ∀k = l, meaning that the values f (x i ), f (y i ) for i in one cycle C k are independent of the values corresponding to a different cycle C l .

Then the sum in the expression of g cyc can be decomposed according to different cycles.

g cyc = inf f   K k=1 i∈V (C k ) log (1 + exp(f (y i ) -f (x i ))))   = K k=1 inf f i∈V (C k ) log (1 + exp(f (y i ) -f (x i ))))

Similar to:

Step 1, we can show that the infimum for each cycle is achieved when the values f (

x i ) = f (x j ), ∀i, j ∈ V (C k ).

A more detailed proof is given as follows. Pick an arbitrary k, and suppose all the edges of

EQUATION

)

The infimum is achieved when f

EQUATION

According to ( 23) and ( 25), we have

EQUATION

Next, we prove that for any > 0, there exists a continuous function f such that

EQUATION

Let N be a large positive number such that

EQUATION

Pick a continuous function f as follows.

f

EQUATION

Note that the root u m of a tree T m is also in a certain cycle C k , thus the value f (x um ) is defined twice in (29), but in both definitions its value is 0, thus the definition is valid. For any i ∈

V (C k ), suppose y i = x j , then both i, j ∈ V (C k ) which implies f (y i )-f (x i ) = f (x j )-f (x i ) = 0. For any i ∈ V (T m )\{u m }, suppose y i = x j ,

then by the definition of the graph (i, j) is a directed edge of the tree T m , which means that depth(i) = depth(j)+1. Thus f (y

i )-f (x i ) = f (x j )-f (x i ) = -N.

In summary, for the choice of f in (29), we have

f (y i ) -f (x i ) = 0, i ∈ K k=1 V (C k ), -N, i ∈ M m=1 V (T m ). (30)

For the choice of f in (29), we have

-nF (Y ; f ) = n i=1 log (1 + exp(f (y i ) -f (x i )))) =   K k=1 i∈V (C k ) log (1 + exp(f (y i ) -f (x i )))) + M m=1 i∈V (Tm)\{um} log (1 + exp(f (y i ) -f (x i ))))   (30) =   K k=1 i∈V (C k ) log (1 + exp(0))) + M m=1 i∈V (Tm)\{um} log (1 + exp(-N )))   = K k=1 |V (C k )| log 2 + M k=1 (|V (T m )| -1) log (1 + exp(-N ))) ≤ K k=1 |V (C k )| log 2 + n log (1 + exp(-N ))) (28) < K k=1 |V (C k )| log 2 + .

This proves (27).:

Combining ( 26) and ( 27

), we have -ng(Y ) = K k=1 |V (C k )| log 2, or equivalently, g(Y ) = 1 n K k=1 |V (C k )| log 2. G.3.2 STEP 2: COMPUTE g(Y ) FOR ANY Y

In the general case, not all y i 's lie in the set {x 1 , . . . , x n }. Denote the set H = {i : y i ∈ {x 1 , . . . , x n }}, H c = {j : y j / ∈ {x 1 , . . . , x n }}.

Since y j 's in H c may be the same, we define the set of such distinct values of y j 's as Y out = {y ∈ R d : y = y j , for some j ∈ H c }.

Let n out = |Y out |, then there are total n + n out distinct values in x 1 , . . . , x n , y 1 , . . . , y n . Without loss of generality, assume y 1 , . . . , y nout are distinct (this is because the value of g(Y ) does not change if we re-index x i 's and y i 's as long as the subscripts of x i , y i change together), then Y out = {y 1 , . . . , y nout }.

We build a directed graph G = (V, A) as follows. The set of vertices V = {1, 2, . . . , n, n + 1, . . . , n + n out } represents x 1 , x 2 , . . . , x n and y 1 , . . . , y nout . For i, j ≤ n, we draw a directed edge (i, j) ∈ A if y i = x j ; in this case, there is a term log(1 + exp(f (x j ) -f (x i ))) in the expression of g(Y ). For 1 ≤ i ≤ n and 1 ≤ j ≤ n out , we draw a directed edge (i, n + j) ∈ A if y i = y j ; in this case, there is a term log(1 + exp(f (y j ) -f (x i ))) in the expression of g(Y ). Note that in this directed graph, it is possible to have a self-loop (i, i), which corresponds to the case y i = x i .

This graph has the following property: for each 1 ≤ i ≤ n, the outdegree is exactly 1; for each n ≤ j ≤ n + n out , the outdegree of j is 0. Moreover, each vertex representing some y i has an incoming degree at least 1 (since otherwise this vertex will not be created); note that an vertex representing x i may have incoming degree 0. We present a lemma which is an extension of the Lemma 2. The proof is given in Appendix G.5.

Lemma 3 Suppose G = (V, A) is a directed graph and outdegree(v) ≤ 1, ∀v ∈ V . Then we have the following:

Observation 1: Suppose in a directed graph G = (V, A), any vertex has outdegree exactly 1.

Starting from any vertex v 0 ∈ V (G), there is a unique walk with infinite length W (v 0 ) (v 0 , e 1 , v 1 , e 2 , v 2 , . . . , v i , e i , v i+1 , e i+1 , . . . ),

where e i is an edge in A(G) with tail v i-1 and head v i .

Proof of Observation 1: At each vertex v i , there is a unique outgoing edge e i = (v i , v i+1 ) which uniquely defines the next vertex v i+1 . Continue the process, we have proved Observation 1. 2

Observation 2: Suppose in a directed graph G = (V, A), any vertex has outdegree exactly 1. Suppose the unique walk starting from v 0 is W (v 0 ) (v 0 , e 1 , v 1 , e 2 , v 2 , . . . , v i , e i , v i+1 , e i+1 , . . . ), then the walk can be decomposed into two parts W 1 (v 0 ) = (v 0 , e 1 , v 1 , e 2 , v 2 , . . . , v i0-1 , e i1 , v i0 ), W 2 (v 0 ) = (v i0 , e i0+1 , v i0+1 , e i0+2 , v i0+2 , . . . ),

where W 1 (v 0 ) is a directed path from v 0 to v i0 (i.e. the vertices v 0 , v 1 , . . . , v i0 are distinct), and W 2 (v 0 ) is the repetition of a certain cycle (i.e. there exists T such that v i+T = v i , for any i ≥ i 0 ). This decomposition is unique.

Proof of Observation 2: Since there are only finitely many vertices in the graph, then some vertices must appear at least twice in W (v 0 ). Among all such vertices, suppose u is the one that appears the earliest in the walk W (v 0 ), and the first two appearances are v i0 = u and v i1 = u and i 0 < i 1 . Denote T = i 1 -i 0 . Since there is a unique edge going out from any vertex, thus v i0+1 must be the same as v i1+1 = v i0+1+T . Continue the process, we have v i = v i+T for any i ≥ i 0 . Thus starting from u = v i0 , the walk W 2 (v 0 ) will be repetitions of the cycle consisting of vertices v i0 , v i0+1 , . . . , v i1-1 , and we denote this cycle as C k0 .

If the vertices before v i1 are not distinct, then there are at least two vertices v j = v l where 0 ≤ j < l ≤ i 0 . This contradicts the definition of i 0 . Therefore, W 1 (v 0 ) is a directed path from v 0 to v i0 . 2

In Observation 2, for any v 0 ∈ V , the "transition point" v i0 in the infinite walk W (v 0 ) is unique. We define the "first-touch-vertex" of v 0 to be v i0 . The first-touch-vertex u = v i0 has the following properties: (i) u ∈ C k for some k; (ii) there exists a path from v to u; (iii) any paths from v to any vertex in the cycle C k other than u must pass u. In other words, if an ant starts from v 0 and crawls along the edges, the first vertex in a cycle that it touches is u. Since any v 0 corresponds to a unique W (v 0 ), its first-touch-vertex must exist and unique. Note that if u is in some cycle, then its first-touch-point is u itself.

As a corollary of Observation 2, there is at least one cycle in the graph. Suppose all cycles of G are C 1 , C 2 , . . . , C K . Because the outdegree of each vertex is 1, these cycles must be disjoint, i.e., V (C i ) ∩ V (C j ) = ∅ and A(C i ) ∩ A(C j ) = ∅, for any i = j.

Define R to be the set of vertices of C 1 , . . . , C m with indegree at least two, i.e., R {v : v ∈ C k for some k, and indegree(v) ≥ 2}.

Suppose the elements of R are u 1 , . . . , u M . We denote the set of vertices in the cycles as

EQUATION

We describe the intuition behind the partitioning of G. Based on Observation 2, starting from any vertex outside of V c there is a unique path that reaches V c . Combining all vertices that reach the cycles at u m (denoted as V m ), and the paths from these vertices to u m , we obtain a directed subgraph T m , which is connected with V c only via the vertex u m . The subgraphs T m 's are disjoint from each other since they are connected with V c via different vertices. In addition, each vertex outside of V c lies in exactly one of the subgraph T m . Thus, we can partition the whole graph into the union of the cycles C 1 , . . . , C K and the subgraphs T 1 , . . . , T M . For the case d = 1, the above proof does not work. The reason is that the path from y v to ŷv may touch other points in {x 1 , . . . , x n } and thus may change the value of g. We only need to make a small modification: we move y v in R until it touches a certain x i that corresponds to a vertex in the tree T m , at which point a cycle is created, and the function value increases by at least 1 n log 2. This path is a non-decreasing path, thus the claim is also proved.

H GENERATED SAMPLES IN SIMULATION:

Here we show some samples of generated data in the appendix. 

:

Other papers, such as Mescheder (2018) analyzed both simultaneous GD and alternating GD. For simplicity, we only analyze simultaneous GD in this paper.

Mescheder (2018) analyzed W-GAN dynamics, but only consider the local region around 0, thus its analysis essentially ignores the Lipschitz constraint.

The stability of typical equilibria of smooth ODEs is determined by the sign of real part of eigenvalues of the Jacobian matrix. It is unstable if at least one eigenvalue has positive real part.See, e.g., Mescheder (2018) for the discussions.

Figures and Tables:

) Similar to the -log D trick used in the original GAN training (a.k.a. non-saturating GAN), in practice we always use the non-saturating version for training:

Figure 1: Graphical illustration of the landscape of GAN outer optimization problem min Y φ(Y, X). It is not a rigorous figure for two reasons: (1) there are only four possible function values, thus the function is a piece-wise linear function, but we use smooth curves to connect them to make the figure easier to understand. (2) the landscape should be two-dimensional, but we only pick illustrative points and and illustrate them in 1D space.

drawn from a mixture of 5 or 25 equally weighted Gaussians each with a variance of 0.002, the means of which are spaced equally on the unit circle. See the blue points in columns (a) and (d) of figure 2 for an illustration. Our generated samples are shown as the red points in (a) and (c) in figure 2 and we can see our generators can catch every mode. The generator and the discriminator loss are shown in (b), (c), (e) and (f).

Figure 2: (a) True(blue) and generated(red) Samples (b) loss for the generator (c) loss for the discriminator from 5-Gaussian synthetic data. (d) True(blue) and generated(red) Samples (e) loss for the generator (f) loss for the discriminator from 25-Gaussian synthetic data.

Figure 3: Population version and empirical version. Population version: the probability densities are changing. Empirical version: the samples are moving.

Figure 4: Illustration of the learning process of the single mode. The generated samples are moving, which correspond to the adjustment of the probability densities. They represent two views on the learning process.

Figure 5: Illustration of the process of learning a multi-mode distribution. Will decompose this process into two parts in the next figure.

Figure6: Illustration of learning a multi-mode distribution. We decompose the process as the macrolearning and the micro-learning. The macro-learning refers to the moving of the whole mode towards the underlying mode. The micro-learning refers to the adjustment of the distribution within each mode. If macro-learning fails, then an entire mode is missed in the generated distributions, which corresponds to mode collapse. Note that even for the single-mode, the learning process can be decomposed into the macro learning and the micro learning.

Figure 7: Learning a two-mode distribution. During training, we learned a generator that maps the latent samples z i 's to x i 's, thus fit the data. If we sample a new z i , then it will be mapped to a new point in the underlying data distribution.

as improper loss function Arjovsky & Bottou (2017); Arora et al. (2017) and weak discriminators Metz et al. (2016); Salimans et al. (2016); Arora et al. (2017); Li et al. (2017). Interestingly, CP-GAN both changes the loss function and improves the discriminator. A number of empirical solutions have been proposed, including unrolled GAN Metz et al. (2016) and minibatch discrimination Salimans et al. (2016). A recent work Lin et al. (2018) proposed a theoretically motivated method PacGAN, which we elaborate below. The key observation is the following: two pairs of distributions with the same total variation distance do not exhibit the same degree of mode collapse. For instance, consider Q = U [0, 1], P 1 = U [0.2, 1] and P 2 = 0.6U [0, 0.5] + 1.4U ([0.5, 1]), where U [a, b] is the uniform distribution on [a, b].

IN SECTION 4.1 C.1 PROOF OF CLAIM 4.1 We will compute values of φ JS (Y, X) for all Y . Denote D(u) = 1 1+exp(-f (u)) ∈ [0, 1]. Since f can be any continuous function, D can be any continuous function with range (0, 1).

Figure 8: Graphical illustration of LaSalle's invariance principle. Figure from Cohen & Rouhling (2017). Starting from K, the dynamics will finally converge to the set M .

Figure 9: The first figure is a connected component of a graph. It contains 10 vertices and 10 directed edges. It can be decomposed into a cycle and two subtrees. The cycle consists of vertices 1, 2, 3, 4.The first subtree consists of edge (10, 4) and vertices 10, 4, and the second subtree consists of edges (8, 7), (9, 7), (7, 5), (6, 5), (5, 1). The second figure is another connected component of the same graph as the first figure. It has one cycle being a self-loop, and two trees attached to it. The third figure is an example of Lemma 3. There is one vertice 9 with outdegree 0, which corresponds to y 6 and y 7 since both 6 and 7 are connected to it. The fact that the two edges have the same head 9 implies that y 6 = y 7 .

Figure 10: Illustration of the proof of Claim G.1. For the figure on the left, we pick an arbitrary tree with the head being vertex 9, which corresponds to y 6 = y 7 . We change y 7 to ŷ7 = x 7 to obtain the figure on the right. Since one more cycle is created, the function value increases by -1 n log 2.

Figure 11: Generated (a)MNIST (b) CIFAR-10 (c) CelebA (d) LSUN samples by CPGAN.

98±0.01 7.73 5.62±0.09 53.42 5.88±0.06 82.81 2.46±0.01 21.68 2.77±0.03 41.15 WGAN-GP 2.00±0.01 7.05 6.52±0.08 40.31 7.34±0.11 65.23 2.65±0.01 17.18 2.80±0.01 34.02 CPGAN 2.05±0.02 5.08 6.72±0.06 36.66 7.56±0.21 57.07 2.73±0.02 15.45 2.82±0.02 30.41 Inception score (IS) (higher is better) and Frechét Inception distance (FID) (lower is better) for non-saturating GAN, WGAN-GP and our proposed CPGAN on MNIST, CIFAR10, STL10, CelebA and LSUN.

Table content: <table><tr><td>Model</td><td>MNIST</td><td/><td colspan="2">CIFAR10</td><td>STL10</td><td/><td>CelebA</td><td/><td>LSUN</td></tr><tr><td/><td>IS</td><td>FID</td><td>IS</td><td>FID</td><td>IS</td><td>FID</td><td>IS</td><td>FID</td><td>IS</td><td>FID</td></tr><tr><td>NSGAN</td><td>1.</td><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild.In Proceedings of International Conference on Computer Vision (ICCV), 2015.Eric V Mazumdar, Michael I Jordan, and S Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. arXiv preprint arXiv:1901.00838, 2019.

Table content: <table><tr><td>Lars Mescheder. On the convergence properties of gan training. arXiv preprint arXiv:1801.04406,</td></tr><tr><td>1:16, 2018.</td></tr><tr><td>Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for gans do</td></tr><tr><td>actually converge? arXiv preprint arXiv:1801.04406, 2018.</td></tr><tr><td>Luke Metz, Ben Poole, David Pfau, and Jascha Sohl-Dickstein. Unrolled generative adversarial</td></tr><tr><td>networks. arXiv preprint arXiv:1611.02163, 2016.</td></tr><tr><td>Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization</td></tr><tr><td>for generative adversarial networks. arXiv preprint arXiv:1802.05957, 2018.</td></tr><tr><td>Ruslan Salakhutdinov and Geoffrey Hinton. Deep boltzmann machines. In Artificial intelligence</td></tr><tr><td>and statistics, pp. 448-455, 2009.</td></tr></table>

In Step 2, we compute the value of g(Y )for any Y . In Step 3, we show that if Y is not a global minimum, then there is a non-decreasing continuous path from Y to a global minimum. G.3.1 STEP 1: COMPUTE g(Y ) THAT ALL y i ∈ {x 1 , . . . , x n } Assume y i ∈ {x 1 , . . . , x n }, ∀i.

Table content: <table/>

Peer review (iclr2020):
The paper attempts to perform global analysis of GAN on the issue of sub-optimal strict local minima and mode collapse, and proposes a new GAN formulation (CoupleGAN) that enjoys nice global properties. The paper is overall well written and conveys an interesting new formulation of GANs. However, the reviewer is concerned with the following questions: The paper is mainly on analyzing the case when the true data has n points instead of on a continuous support. It would be more interesting to see theoretical guarantee on even Gaussian mixture model. Also since GANs are mostly known for generalizing what is seen to generate new data, whether converging only to the n points are good or not still worth debating. In claim 4.2 and 4.3, what if the initialization of y is completely random? Then the claim cannot say anything on mode collapse. So is the formulation in the paper the real characterization of mode collapse?