Year: 2019

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.

heading: 1 INTRODUCTION
text: 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 φ(pg, pdata) = maxD hD(pg, pdata), where hD 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 pg, the outer function φ(pg, pdata) is the Jenson-Shannon (JS) distance (minus a constant); second, the outer function is convex in pg, so a gradient descent method on pg 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θ ψTAθ 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 pg. 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 CPGAN 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 CPGAN 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.

heading: 2 NEW LOSS: CP-GAN
text: 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.

heading: 2.1 GENERATIVE ADVERSARIAL NETWORKS
text: We first review the formulation of the original GAN proposed by Goodfellow et al. (2014). Given samples from a true data distribution pdata, we want to generate a new distribution pg to mimic pdata. To judge how far away the generated distribution pg is from pdata, 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 pg to fool the discriminator so that the loss value is minimized. Formally, the problem for a GAN is given by
min pg max D Ex∼pdata,y∼pg log(D(x)) + log(1−D(y)). (1)
A common choice for the discriminator is D(u) = 11+exp(−f(u)) , where f is a function. Given this choice, the formulation given in Eq. (1) becomes
min pg max f
Ex∼pdata,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 pg, where z is drawn from a given distribution pz . This yields the following program:
min G max f
Ex∼pdata,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):
max f Ex∼pdata,z∼pz log
1
1 + exp(−f(x)) + log
1
1 + exp(f(G(z))) , (3a)
min G Ex∼pdata,z∼pz log(1 + exp(−f(G(z)))). (3b)

heading: 2.2 COUPLING GAN
text: As mentioned before, the program is given in Eq. (3) has shortcomings, which we propose to address via the following formulation:
min ψ max θ Ex∼pdata,z∼pz [log
1
1 + exp(fθ(Gψ(z))− fθ(x)) ]. (4a)
Similar to the − logD trick used in the original GAN training (a.k.a. non-saturating GAN), in practice we always use the non-saturating version for training:
D problem : min θ Ex∼pdata,z∼pz [log(1 + exp(fθ(Gψ(z))− fθ(x)))], (5a)
G problem : min ψ Ex∼pdata,z∼pz [log(1 + exp(fθ(x)− fθ(Gψ(z))))]. (5b)
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 JSGAN, 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 x1 = 1 and x2 = 2, and generated data are y1 = 0.5 and y2 = 0.5, then the boundary is drawn at, say, 0.8. Then the discriminator only has the motivation to approach x2 = 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 x2 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 y1 will try to cross 0.8 to approach x1 = 1, and y2 will try to cross 1.5 to approach x2 = 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.

heading: 3 MULTI-DIRACGAN: MULTI-MODE GENERATION
text: 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 DiracGAN, 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 = (y1, . . . , yn) ∈ Rd×n and a discriminator f(x). The true data distribution is given by a n-point distribution X = (x1, . . . , xn) ∈ Rd×n, where xi’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).

heading: 4 ANALYSIS OF SOME EXISTING GANS

heading: 4.1 JS-GAN HAS EXPONENTIALLY MANY BAD BASINS
text: We analyze the landscape of JS-GAN under the Multi-DiracGAN model with powerful discriminators, the formulation of which can be written as:
min Y ∈Rn φJS(Y,X) , max f
LJS(f ;Y ), (6)
where LJS(f ;Y ) = − 1n ∑n i=1 log(1 + exp(−f(xi))− 1 n ∑n i=1 log(1 + exp(f(yi))).
The range of φJS(Y,X) is [−2 log 2, 0] because LJS(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 x1 6= x2 ∈ Rd. Then
φJS(Y,X) =  −2 log 2 ≈ −1.3862, if {x1, x2} = {y1, y2} − log 2 ≈ −0.6931, if |{x1, x2} ∩ {y1, y2}| = 1, log 2− 1.5 log 3 ≈ −0.9548, if y1 = y2 ∈ {x1, x2}, 0 if |{x1, x2} ∩ {y1, y2}| = ∅.
The global minimum is −2 log 2, which is achieved iff the generated data points {y1, y2} coincide with the true data points {x1, x2}.
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 x1 6= x2 ∈ Rd. Then Ȳ = (x1, x1) 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, x1 = 0, x2 = 1. In this case, Y = (y1, y2) = (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 (y1, y2) moving from (0, 1) to (−0.1,−0.1), going through four points: (y1, y2) = (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 x1, x2, . . . , xn ∈ Rd 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., {y1, . . . , yn} = {x1, . . . , xn}. (ii) If yi ∈ {x1, . . . , xn}, i = 1, 2, . . . , n and yi = yj for some i 6= j, then Y is a sub-optimal strict local minimum. Therefore, φJS(·, X) has (nn − 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
use different objectives for D and G (the − logD 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.

heading: 4.2 TRAINING DYNAMICS OF JS-GAN
text: 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) = wTu+ b, where w ∈ Rd, b ∈ R.
min θ=(w,b)∈Rd×R LDGAN(Y ; θ) , n∑ i=1 log(1 + exp(−wTxi − b)) + log(1 + exp(wT yi + b)),
min Y=(y1,...,yn)∈Rd×n LGGAN(Y ; θ) , n∑ i=1 log(1 + exp(−wT yi − b)).
Consider the dynamics corresponding to the simultaneous gradient descent (GD) 1:
dw dt = −∂L
D GAN
∂w = n∑ i=1 xi 1 + ewT xi+b − yi 1 + e−wT yi−b , (7a)
db dt = −∂L
D GAN
∂b = n∑ i=1
1 1 + ewT xi+b − 1 1 + e−wT yi−b , (7b)
dyi dt = −∂L G GAN ∂yi =
w
1 + ewT yi+b . (7c)
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.
1Other papers, such as Mescheder (2018) analyzed both simultaneous GD and alternating GD. For simplicity, we only analyze simultaneous GD in this paper.
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 ‖yi(t)− yj(t)‖ ≤ ‖yi(0)− yj(0)‖,∀t.
This claim predicts that starting from y1(0) = y2(0) = · · · = yn(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.

heading: 4.3 DISCUSSIONS OF WGAN AND ITS VARIANTS
text: 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 analyze 2.
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 minY maxf ∑ i f(xi) − ∑ i f(yi) − λ ∑ i(‖∇uf(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 ‖yi(t)− yj(t)‖ = ‖yi(0)− yj(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.

heading: 5 ANALYSIS OF CP-GAN
text: 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.

heading: 5.1 CP-GAN HAS NO BAD BASIN
text: Following the aforementioned steps, the finite-sample version of CP-GAN reads
min Y φCP(Y,X), where φCP(Y,X) , sup f
1
n n∑ i=1 log 1 1 + exp(f(yi)− f(xi))) , (8)
resulting in a range φCP(Y,X) ∈ [− log 2, 0]. For simplicity, we define gCP(Y ) = φCP(Y,X) as the data X are fixed throughout the paper.
Proposition 2 Suppose x1, x2, . . . , xn ∈ Rd are distinct. The global minimal value of gCP(Y ) is − log 2, which is achieved iff {x1, . . . , xn} = {y1, . . . , yn}. Furthermore, for any Y , there is a continuous path from Y to a global minimum along which the value of gCP(Y ) is non-increasing.
2Mescheder (2018) analyzed W-GAN dynamics, but only consider the local region around 0, thus its analysis essentially ignores the Lipschitz constraint.
To understand this result, consider the special case n = 2 and x1 6= x2 ∈ Rd. In this case, we have
φCP(Y,X) =  − log 2 ≈ −0.6931, if {x1, x2} = {y1, y2} − 12 log 2 ≈ −0.3466, if |{i : xi = yi}| = 1 0 otherwise.
We illustrate the landscape of gCP(Y ) in Figure 1b for the special case that n = 2, d = 1, x1 = 0, x2 = 1. In this case, (y1, y2) = (0, 1) and (y1, y2) = (1, 0) are two global minima of gCP(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 (y1, y2) moving from (0, 1) to (−0.1,−0.1), going through four points: (y1, y2) = (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.

heading: 5.2 TRAINING DYNAMICS OF CP-GAN
text: 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) = wTu, where w ∈ Rd:
min θ=w∈Rd LDCP(Y ; θ) , n∑ i=1 log(1 + exp(wT (yi − xi))),
min Y=(y1,...,yn)∈Rd×n LGCP(Y ; θ) , n∑ i=1 log(1 + exp(wT (xi − yi))). (9)
Consider the dynamics corresponding to the simultaneous gradient descent for CP-GAN:
dw dt = −∂L
D CP
∂w = n∑ i=1 xi − yi 1 + ewT (xi−yi) , (10a)
dyi dt = −∂L G CP ∂yi =
w
1 + ewT (yi−xi) . (10b)
Define δi = yi − xi,∀i. Define function βij(t) = 12‖δ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 ‖xi − yi‖2.
Obviously, V = 0 iff w = 0 and xi = yi,∀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 x1 = 0. However, when we check the case x1 6= 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 xi and yi 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, limt→∞ θ(t) ∈ E, where E , {(w, y) : wT (yi − xi) = 0,∀i}. (2) When d = 1, starting from any initial point θ(0), limt→∞ θ(t) ∈M , where M = {(w, y) : w = 0, ∑ i xi = ∑ i yi}.
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 (y1, . . . , yn) = (x1, . . . , xn) 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.

heading: 6 EXPERIMENTS
text: 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.

heading: 6.1 SYNTHETIC DATASETS
text: We first demonstrate our results on 2-dimensional synthetic data. Specifically, the 2-dimensional data x = (x1, x2) is 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).

heading: 6.2 IMAGE GENERATION
text: In this section, we present results on the task of image generation. We train and evaluate CPGAN on four datasets: (1) MNIST (LeCun et al., 1998) (32×32); (2) CIFAR-10 (Krizhevsky, 2009) (32×32); (3) STL-10 (Adam Coates, 2011) (48×48); (4) CelebA (Liu et al., 2015) (64×64); and (5) LSUN Bedrooms (Yu et al., 2015) (64×64). We use three ResNet Blocks structure for MNIST generator, and the DCGAN structure for CIFAR-10, STL-10, CelebA and LSUN. The input size for the generator is 128-dimension.
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.
We use inception scores (IS) (Salimans et al., 2016) and Freché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.

heading: 7 CONCLUSION
text: 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.

heading: A EMPIRICAL VERSION: EFFECT OF MACRO-LEARNING
text: 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 pg 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 pdata, and we start from an initial two-mode distribution pg. There are two differences between pg and pdata: 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 pg to roughly overlap with the two modes of pdata which we call “macro learning”; second, adjust the distributions of each mode to match those of pdata, 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.

heading: A.1 GENERALIZATION
text: 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 pdata and the generated distribution is pg. Further, suppose we sample n points x′is from pg and sample n points from pg, 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 pdata and pg) 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 zi’s to xi’s, thus fit the empirical distribution. If we sample a new latent sample zi, then the generator will map zj to a new point xj in the underlying data distribution. Thus fitting the empirical distribution can still leads to generating new data points.

heading: B RELATED WORKS
text: 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 pdata is a single Gaussian distribution. It considers the population version, i.e., there is a continuous latent distribution of pz . 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 forD and a bi-linear function forG (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 pdata 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 pdata 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 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, CPGAN 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], P1 = U [0.2, 1] and P2 = 0.6U [0, 0.5] + 1.4U([0.5, 1]), where U [a, b] is the uniform distribution on [a, b]. Then TV (Q,P1) = TV (Q,P2), but P1 has mode collapse while P2 does not. They proposed to pack the samples, i.e., consider the distance of the product distribution Pm and Qm. The main theoretical result that “TV (Pm, Qm) is a better loss to penalize strong mode collapse than TV (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.

heading: C PROOFS IN SECTION 4.1

heading: C.1 PROOF OF CLAIM 4.1
text: We will compute values of φJS(Y,X) for all Y .
Denote D(u) = 11+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(xi)) + 1 n n∑ i=1 log 1 1 + exp(f(yi))
]
= sup D
[ 1
n n∑ i=1 log(D(xi)) + 1 n n∑ i=1 log(1−D(yi))
] .
Consider four cases.
Case 1: Both generated points overlap with the true data points, and are distinct, i.e., y1 = x1, y2 = x2 or y2 = x1, y2 = x2. Then the objective is
sup D
[ 1
2 log(D(x1)) +
1 2 log(1−D(x1)) + 1 2 log(D(x2)) + 1 2 log(1−D(x2))
] .
The optimal value is −2 log 2, which is achieved when D(x1) = D(x2) = 12 . The corresponding function values of f are f(x1) = f(x2) = 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 y1 = x1, y2 /∈ {x1, x2}. The problem becomes
sup D
[ 1
2 log(D(x1)) +
1 2 log(D(x2)) + 1 2 log(1−D(x1)) + 1 2 log(1−D(y2))
] .
The optimal value − log 2 ≈ −0.6931 is achieved when D(x1) = 1/2, D(x2) = 1 and D(y2) = 0. The corresponding function values of f are f(x1) = − log 2, f(x2) =∞ and f(y2) = −∞. Case 3: Both generated points overlap with the true data points, and are the same. Without loss of generality, check the case y1 = y2 = x1.
sup D
[ 1
2 log(D(x1)) + log(1−D(x1)) +
1 2 log(D(x2))
] .
The optimal value 12 log 1 3 + log 2 3 ≈ −0.9548 is achieved when D(x1) = 1/3 and D(x2) = 0. The corresponding function values of f are f(x1) = − log 2, f(x2) =∞. Case 4: Both generated points are different from the true data points. y1, y2 /∈ {x1, x2}. It becomes separable over the four points
sup D
[ 1
2 log(D(x1)) +
1 2 log(D(x2)) + 1 2 log(1−D(y1)) + 1 2 log(1−D(y2))
] .
Each term can achieve its maximum log 1 = 0. Thus the optimal value 0 is achieved when D(x1) = D(x2) = 1 and D(y1) = D(y2) = 0. The corresponding function values of f are f(x1) = −∞, f(x2) =∞ .

heading: C.2 PROOF OF COROLLARY 4.1
text: We re-state the corollary below.
Corollary C.1 Suppose Ȳ = (ȳ1, ȳ2) satisfies ȳ1 = ȳ2 = x1, then it is a sub-optimal strict local minimum of the problem.
Proof: Suppose is the minimal non-zero distance between two points of x1, x2, y1, y2. Consider a small perturbation of Ȳ as Y = (ȳ1 + 1, ȳ2 + 2), where | i| < . We want to verify that
φ(Ȳ , X) > φ(Y,X) ≈ −0.9548. (11)
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 y1 = ȳ1 = x1. Since the perturbation amount is small enough, we have y2 /∈ {x1, x2}. According to Case 2 above, we have
φ(Ȳ , 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 y1 /∈ {x1, x2}, y2 /∈ {x1, x2}. According to Case 4 above, we have
φ(Ȳ , X) = 0 > −0.9548.
Combining both cases, we have proved (12).

heading: Q.E.D.

heading: C.3 PROOF OF PROPOSITION 1
text: Denote D(u) = 11+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(xi)) + 1 n n∑ i=1 log 1 1 + exp(f(yi))
= sup D
1
n n∑ i=1 log(D(xi)) + 1 n n∑ i=1 log(1−D(yi)).
Denote F (D;Y ) = 1n ∑n i=1 log(D(xi)) + 1 n ∑n i=1 log(1 − D(yi)). Since D(u) ∈ (0, 1) for any u, then F (D;Y ) ≤ 0. When D(u) → 12 ,∀u, we have F (D;Y ) → −2 log 2, thus φJS(Y,X) = supD 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 Mi to be set of indices of yj such that yj equals xi, and mi to be the size of the set Mi, i.e.,
Mi = {j : yj = xi},mi = |Mi|, i = 1, 2, . . . , n. Denote Ω = {1, 2, . . . , n}\(M1 ∪M2 · · · ∪Mn). Then we have
φJS(Y,X) = 1
n sup D  n∑ i=1 [log(D(xi)) + ∑ j∈Mi log(1−D(yj))] + ∑ j /∈Ω log(1−D(yj))  = 1
n sup D  n∑ i=1 [log(D(xi)) +mi log(1−D(xi))] + ∑ j /∈Ω log(1−D(yj))  (i) = 1
n n∑ i=1 sup ti∈R [log(ti) +mi log(1− ti)] + 0
(ii) =
1
n n∑ i=1 [log 1 mi + 1 +mi log mi mi + 1 ]
= 1
n n∑ i=1 [mi logmi − (mi + 1) log(mi + 1)].
Here (i) is because D(yj), j ∈ Ω are independent of D(xi)’s and thus can be any values; in this step, the optimal D(yj) = 1,∀j ∈ Ω. (ii) is because for any positive number m, supt∈R[log(t) + m ∑n i=1 log(1− t)] = log 1 m+1 +m log m m+1 .
When mi = 1, i = 1, 2, . . . , n, i.e., yi = xi,∀i, the function φJS(Y,X) achieves value −2 log 2. Thus Y = (x1, x2, . . . , xn) is a global minimum.
Next, we show that if Y satisfies that if m1 + m2 + · · · + mn = n then Y is a strict local-min. Denote δ as the minimal distance between two points of x1, x2, . . . , xn, i.e.,
δ = min k 6=l ‖xk − xl‖.
Consider a small perturbation of Y as Ȳ = (ȳ1, ȳ2, . . . , ȳn) = (y1 + 1, y2 + 2, . . . , yn+ n), where ‖ j‖ < δ, ∀j and ∑ j ‖ j‖2 > 0. We want to verify that
φJS(Ȳ , X) > φJS(Y,X). (12)
Denote m̄i = |{j : ȳj = xi}|, i = 1, 2, . . . , n. According to the assumption m1 +m2 + · · ·+mn = n, we have yj ∈ {x1, . . . , xn},∀j. Consider an arbitrary j, and suppose yj = xi. Together with ‖ȳj − yj‖ = ‖ j‖ < δ = mink 6=l ‖xk − xl‖, we have ȳj /∈ ({x1, x2, . . . , xn}\{xi}). In other words, the only possible point in {x1, . . . , xn} that can coincide with ȳj is xi, and this happens only when j = 0. As a result, we have
m̄i ≤ mi, , 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(Ȳ , X) = 1
n n∑ i=1 [m̄i log m̄i − (m̄i + 1) log(m̄i + 1)]
≥ 1 n n∑ i=1 [mi logmi − (mi + 1) log(mi + 1)] = φJS(Y,X).
The equality is achieved iff m̄i = mi,∀i, which holds iff j = 0,∀j. Since we have assumed∑ j ‖ j‖2 > 0, the equality does not hold, thus φ(Ȳ , X) > φ(Y,X). Therefore, we have proved that Ȳ is a strict local minimum.
Finally, if Y satisfies that m1 + m2 + · · · + mn = n and mk ≥ 2 for some k, then φJS(Y,X) > −2 log 2. Thus Y is a sub-optimal strict local minimum. Q.E.D.

heading: D TECHNICAL DETAILS OF SECTION 4.2 AND 4.3

heading: D.1 PROOF OF CLAIM 4.2
text: Define a function αij(t) = 12‖yi(t)− yj(t)‖ 2,∀ i, j.
dαij(t)
dt = (yi − yj)T d(yi − yj) dt = (yi − yj)T ( dyi dt − dyj dt ) = (yi − yj)T ( w
1 + ewT yi+b − w 1 + ew T yj+b ) = (wT yi − wT yj) ( 1
1 + ewT yi+b − 1 1 + ew T yj+b ) ≤ 0.
In the last step, we used the fact that (a1 − a2) ( 1 1+ea1 − 1 1+ea2 ) ≤ 0 for any a1, a2 ∈ R. Note
that in the above computation, we skip the time index t. Therefore αij(t) is non-increasing along the trajectory, which implies ‖yi(t)− yj(t)‖ ≤ ‖yi(0)− yj(0)‖,∀t.

heading: D.2 PROOF OF CLAIM 4.3
text: WGAN-GP with linear discriminators can be expressed as
min w∈Rd LDWGAN−GP(Y ; θ) , − n∑ i=1 wTxi + n∑ i=1 wT yi + λ(‖w‖ − 1)2.
min Y=(y1,...,yn)∈Rd×n LGWGAN−GP(Y ; θ) , − n∑ i=1 wT yi.
Consider the dynamics corresponding to the simultaneous gradient descent for WGAN-GP:
dw dt = − ∂LDWGAN−GP ∂w = n∑ i=1 (xi − yi)− 2λw + 2w/‖w‖, (13a)
dyi dt = − ∂LGWGAN−GP ∂yi = −w. (13b)
Define a function αij(t) = 12‖yi(t)− yj(t)‖ 2,∀ i, j.
dαij(t)
dt = (yi − yj)T d(yi − yj) dt = (yi − yj)T ( dyi dt − dyj dt ) = (yi − yj)T (w − w) = 0.
Thus ‖yi(t)− yj(t)‖ will be a constant for all t.

heading: E TECHNICAL DETAILS OF SECTION E.5

heading: E.1 PROOF OF CLAIM 5.1
text: Define a function αij(t) = 12‖(yi(t)− xi)− (yj(t)− xj)‖ 2,∀ i, j. Denote δi(t) = yi(t)− xi.
dαij(t)
dt = (δi − δj)T d(yi − yj) dt = (δi − δj)T ( dyi dt − dyj dt ) = (δi − δj)T ( w
1 + ewT (yi−xi) − w 1 + ew T (yj−xj) ) = (wT δi − wT δj) ( 1
1 + ewT δi − 1 1 + ew T δj ) ≤ 0.
The equality holds iff wT δi = wT δj , i.e., wT (δi − δj) = 0.

heading: E.2 PROOF OF CLAIM 5.2
text: Let ui = wT (yi − xi), i = 1, . . . , n, we have
dV
dt =wT
dw dt + ∑ i (yi − xi)T dyi dt
(14a)
=wT n∑ i=1 xi − yi 1 + ewT (xi−yi) + ∑ i (yi − xi)T w 1 + ewT (yi−xi) (14b)
= n∑ i=1 wT (xi − yi) 1 + ewT (xi−yi) + n∑ i=1 wT (yi − xi) 1 + ewT (yi−xi)
(14c)
= n∑ i=1 −ui 1 + e−ui + n∑ i=1 ui 1 + eui
(14d)
= n∑ i=1 n∑ i=1 ui(1− eui) 1 + eui ≤ 0, (14e)
In the last step we used the fact that u(1 − eu) ≤ 0, ∀u ∈ R. Note that in the above computation, we skip the time index t.

heading: E.3 PROOF OF PROPOSITION 3
text: We restate the proposition below.
Proposition 4 (restate; global convergence of CPGAN dynamics) When d = 1, starting from any initial point θ(0), the trajectory defined by the CPGAN dynamics θ(t) will satisfy limt→∞ θ(t) ∈M , where M = {(w, y) : w = 0, ∑ i xi = ∑ i yi}.
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 dudt = h(u(t)), where h is a vector mapping. Assume h has continuous first partial derivatives and h(0) = 0. LetK be an invariant compact set. Suppose there is a scalar function V which has continuous first partial derivatives in K and is such that Ṽ (p) = 〈∇V (p), h(p)〉 ≤ 0,∀p ∈ K. Let E be the set of all points p ∈ K such that Ṽ (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
M = {(w, y) : w = 0, ∑ i xi = ∑ i yi}. (15)
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 Ṽ (p) = 0 is
E , {(w, y) : wT (yi − xi) = 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) ∈ R1×(n+1) : w(yi − xi) = 0,∀i}. Let E1 = {(w, y) : w = 0} and E2 = {(w, y) : yi = xi,∀i}, then E = E1 ∪ E2. The set M is still
M = {(w, y) : w = 0, ∑ i xi = ∑ i yi}.
Since θ(0) ∈ E but not in M , and E2 ⊆ M , then we have θ(0) ∈ E1 and θ(0) /∈ E2. This implies w(0) = 0 and ∑ i(xi(0)− yi(0))2 6= 0. According to the fact that Ṽ (p) = 0,∀p ∈ E and θ(t) ∈ E, we have that V (θ(t)) = V (θ(0)) =
∑ i (xi(0)− yi(0))2 + w(0)2 , δ. (16)
Since the path θ(t) ∈M ⊆ E for all t, we have θ(t) ∈ E1 orE2. Suppose J = {t ∈ R : θ(t) ∈ E2}, 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) ∈ E1 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
dw dt = −∂L
D CP
∂w = n∑ i=1 xi − yi 1 + ew(xi−yi) . (17a)
dyi dt = −∂L G CP ∂yi =
w
1 + ew(yi−xi) . (17b)
Along the path θ(t) ∈ E, we have w(t)(yi(t)− xi(t)) = 0,∀t, thus dyi(t)
dt =
0
1 + e0 = 0, ∀i,
which implies yi(t) = yi(0),∀i. This further implies dw(t)dt = ∑ i[xi(t) − yi(t)] = ∑ i[xi(0) −
yi(0)] , δ0. Since θ(0) ∈ E but not in M , thus we must have ∑ i xi(0) 6= ∑ i yi(0), implying δ0 6= 0. Thus dw(t)dt = δ0 6= 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.

heading: E.4 PROOF OF CLAIM 5.3
text: 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 (y1, . . . , yn) = (x1, . . . , xn) in the set of stationary solutions, the Jacobian has an eigenvalue with positive real part 3.
When d = 1, the dynamical system is given by
dw dt = −∂L
D CP
∂w = n∑ i=1 xi − yi 1 + ew(xi−yi) . (18a)
dyi dt = −∂L G CP ∂yi =
w
1 + ew(yi−xi) . (18b)
We can write it as θ̇ = h(θ) = (h0(θ), . . . , hn(θ)),
where hi is the right hand side of the i-th equation. The Jacobian J = ∇h satisfies the following:
J11 = ∂h0 ∂w = n∑ i=1 (xi − yi)2 1 + ew(yi−xi) ,
J1,i+1 = ∂h0 ∂yi = − 1 1 + ew(xi−yi)
+ w(xi − yi) ew(yi−xi)
(1 + ew(yi−xi))2 ,∀i = 1, . . . , n,
Ji+1,1 = ∂hi ∂w = 1 1 + ew(yi−xi) + w(yi − xi)
ew(yi−xi)
(1 + ew(yi−xi))2 ,
Ji+1,i+1 == ∂hi ∂yi
= − w 2ew(yi−xi)
(1 + ew(yi−xi))2
Jij = 0, if i, j ≥ 2 and i 6= j.
When evaluated at θ = (0, y1, . . . , yn), we have
J11 = n∑ i=1 (xi − yi)2 2 ,
J1,i+1 = − 1
2 ,∀i = 1, . . . , n,
Ji+1,1 = 1
2 ,
Ji+1,j+1 = 0, i, j ≥ 1. 3The 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.
It is easy to verify that J only has two non-zero eigenvalues
λ1,2 = 1
2 J11 ± 1√ 2
√ −1.
Therefore, when xi = yi,∀xi, the eigenvalues of the Jacobian have zero real part. When some xi 6= yi, 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 xi = ∑ i yi}, any point other than the desired solution (y1, . . . , yn) is not stable.

heading: E.5 ANALYSIS OF CP-GAN DYNAMICS FOR CONVEX CASE
text: 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 Tu) (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∈Rd LDCP(Y ; θ) , n∑ i=1 φ(wT (yi − xi)),
min Y=(y1,...,yn)∈Rd×n LGCP(Y ; θ) , n∑ i=1 φ(wT (xi − yi)).
Consider the dynamics corresponding to the simultaneous gradient descent for CP-GAN:
dw dt = −∂L
D CP
∂w = n∑ i=1 (xi − yi)φ′(wT (yi − xi)), (19a)
dyi dt = −∂L G CP ∂yi = wφ′(wT (xi − yi)) (19b)
We still consider the function
V = 1 2 ‖w‖2 + 1 2 n∑ i=1 ‖xi − yi‖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 ui = wT (yi − xi), i = 1, . . . , n, we have
dV
dt =wT
dw dt + ∑ i (yi − xi)T dyi dt
(20a)
=wT n∑ i=1 (xi − yi)φ′(wT (yi − xi)) + ∑ i (yi − xi)Twφ′(wT (xi − yi)) (20b)
= n∑ i=1 wT (xi − yi)φ′(wT (yi − xi)) + n∑ i=1 wT (yi − xi)φ′(wT (xi − yi)) (20c)
= n∑ i=1 (−ui)φ′(ui) + n∑ i=1 uiφ ′(−ui) (20d)
= n∑ i=1 ui[φ ′(−ui)− φ′(ui)] ≤ 0, (20e)
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 x1 = 0, x2 = 1. The problem becomes
gCP(Y ) = sup f∈F
1 2 log
1
1 + exp(f(0)− f(y1)) +
1 2 log
1
1 + exp(f(1)− f(y2)) ,
where F is the set of continuous functions with domain Rd. We compute all values of gCP(Y ) as follows.
Case 1: The two generated points are the same as the true data points, i.e., {x1, x2} = {y1, y2}. If y1 = 0, y2 = 1, then
gCP(Y ) = 1
2 [log 1/2 + log 1/2] = − log 2 ≈ −0.6937.

heading: If y1 = 1, y2 = 0, then
text: gCP(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 : yi = xi}| = 1. Without loss of generality, we can check the case y1 = 0, y2 6= 1. Then
gCP(Y ) ≥ sup f∈F
1 2 log
1
1 + exp(f(0)− f(0)) +
1 2 log
1
1 + exp(f(1)− f(y2))
= −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(y2)→ −∞ (or more precisely, there is a sequence of functions such that the difference f(1)− f(y2) goes to minus infinity).
Case 3: Both generated points are different from the true data points, i.e., |{i : yi = xi}| = 1. Then
gCP(Y ) ≥ sup f∈F
1 2 log
1
1 + exp(f(0)− f(y1)) +
1 2 log
1
1 + exp(f(1)− f(y2))
= sup t1∈R,t2∈R
1 2 log
1
1 + exp(t1) +
1 2 log
1
1 + exp(t2)
= 0.
The value is achieved when f(1)− f(y2)→ −∞ and f(0)− f(y2)→ −∞. According to the above results, the only global minima are {y1, y2} = {x1, x2}. 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(yi)− f(xi))) = − inf f 1 n n∑ i=1 log (1 + exp(f(yi)− f(xi)))) .
Proposition 5 (restatement of Proposition 2 ) Suppose x1, x2, . . . , xn ∈ Rd are distinct. The global minimal value of gCP(Y ) is − log 2, which is achieved iff {x1, . . . , xn} = {y1, . . . , yn}. 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′is, y ′ is and draw directed edges from xi to yi. This graph can be decomposed into cycles and trees.
(2) Each vertex in a cycle contributes − 1n 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 − 1n 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 {y1, y2, . . . , yn} = {x1, . . . , xn}, 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 yi /∈ {x1, . . . , xn}, 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.

heading: G.1 WARM-UP EXAMPLE 1: ALL GENERATED POINTS MATCH THE TRUE POINTS
text: Prove that if {y1, y2, . . . , yn} = {x1, . . . , xn}, then Y is a global minimum of g(Y ). Suppose yi = 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 k0, 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 C1, C2, . . . , CK . Each cycle Ck = (ck(1), ck(2), . . . , ck(mk)) satisfies ck(j + 1) = σ(ck(j)), j = 1, 2, . . . ,mk where ck(mk +
1) is defined as ck(1). Now we calculate the value of g(Y ).
g(Y ) = sup f
1
n n∑ i=1 log 1 1 + exp(f(yi)− f(xi)))
(i) = − inf
f
1
n K∑ k=1 ∑ i∈Ck log (1 + exp(f(yi)− f(xi))))
= − inf f
1
n K∑ k=1 mk∑ j=1 log ( 1 + exp(f(xck(j+1))− f(xck(j)))) ) (ii) = − 1
n K∑ k=1 inf f mk∑ j=1 log ( 1 + exp(f(xck(j+1))− f(xck(j)))) )
= − 1 n K∑ k=1 inf t1,t2,...,tmk∈R mk−1∑ j=1 log (1 + exp(tj+1 − tj)) + log (1 + exp(t1 − tmk))  (iii) = − 1
n K∑ k=1 mk log(1 + exp(0))
= − log 2. Here (i) is because {1, 2, . . . , n} is the combination of C1, . . . , CK and i ∈ Ck means that i = ck(j) for some j. (ii) is because Ck’s are disjoint and f can be any continuous function; more specifically, the values of f at xi’s for i in two different cycles are independent, i.e., the choice of {f(xi) : i ∈ Ck1} is independent of the choice of {f(xi) : i ∈ Ck2} if k1 6= k2, 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(tj+1 − tj)) + log (1 + exp(t1 − tm)) is a convex function of t1, t2, . . . , tm and the minimum is achieved at t1 = t2 = . . . tm = 0.

heading: G.2 WARM-UP EXAMPLE 2: NEW POINT GENERATED
text: Suppose yj ∈ {x1, . . . , xn},∀j, and there exist some xi0 that is not equal to any yj . 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 − 1n log 2. Later in the general proof, we will see that any vertex not in a cycle will reduce the objective value by exactly − 1n log 2. Consider the term log(1 + exp(f(yi0) − f(xi0))). Since xi0 does not appear in any other term in∑ i log(1 + exp(f(yi)− f(xi))), the choice of f(xi0) is free. Therefore, no matter what values of f(x1), . . . , f(xi0−1), f(xi0+1), . . . , f(xn) and f(y1), . . . , f(yn) are, we can always pick f(xi0) so that f(yi0)− f(xi0)→ −∞, making the term log(1 + exp(f(yi0)− f(xi0)))→ 0.
g(Y ) = − inf f
1
n n∑ i=1 log (1 + exp(f(yi)− f(xi))))
= − inf f
1
n ∑ i 6=i0 log (1 + exp(f(yi)− f(xi)))) + 0
≥ − 1 n ∑ i 6=i0 log(1 + 1) = −n− 1 n log 2.

heading: G.3 FORMAL PROOF OF PROPOSITION 2
text: This proof is divided into three steps. In Step 1, we compute the value of g(Y ) if all yi ∈ {x1, . . . , xn}. This is the major step of the whole proof. 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 yi ∈ {x1, . . . , xn}
Assume
yi ∈ {x1, . . . , xn},∀i. (21)
We build a directed graph G = (V,A) as follows. The set of vertices V = {1, 2, . . . , n} represents x1, x2, . . . , xn. We draw a directed edge (i, j) ∈ A if yi = xj ; in this case, there is a term log(1 + exp(f(xj) − f(xi))) 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 yi = xi. Because of the assumption (21), we can simply express
g(Y ) = − inf f
1
n n∑ i=1 log (1 + exp(f(yi)− f(xi))))
= − inf f
1
n ∑ (i,j)∈A log (1 + exp(f(xj)− f(xi)))) . (22)
Each yi correspond to a unique xj , 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 = (v0, e1, v1, e2, . . . , vm−1, em, vm) is a sequence of vertices and edges such that vi ∈ V for every i ∈ {0, 1, . . . ,m} and ei is a directed edge from vi−1 to vi 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 v0, v1, . . . , vm are distinct we call it a directed path (or path), and we say the length of the path is m. If v0, v1, . . . , vm−1 are distinct and vm = v0, 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 C1, C2, . . . , CK and subtrees T1, T2, . . . , TM 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 um is a vertex of a certain cycle Ck where 1 ≤ k ≤ K. In addition, each vertex of the graph appears in exactly one of the following sets: V (C1), . . . , V (CK), V (T1)\{u1}, . . . , V (TM )\{uM}, (c) 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
− ng(Y ) = inf f n∑ i=1 log (1 + exp(f(yi)− f(xi))))
= inf f  K∑ k=1 ∑ i∈V (Ck) log (1 + exp(f(yi)− f(xi)))) + M∑ m=1 ∑ i∈V (Tm)\{um} log (1 + exp(f(yi)− f(xi))))  ≥ inf
f  K∑ k=1 ∑ i∈V (Ck) log (1 + exp(f(yi)− f(xi))))  , gcyc. (23)
We then compute gcyc. Since Ck is a cycle, we have Xk , {xi : i ∈ Ck} = {yi : i ∈ Ck}. Since the cycles Ck’s are disjoint, we have Xk ∩Xl = ∅,∀k 6= l, meaning that the values f(xi), f(yi) for i in one cycle Ck are independent of the values corresponding to a different cycle Cl. Then the sum in the expression of gcyc can be decomposed according to different cycles.
gcyc = inf f  K∑ k=1 ∑ i∈V (Ck) log (1 + exp(f(yi)− f(xi))))  =
K∑ k=1 inf f ∑ i∈V (Ck) log (1 + exp(f(yi)− f(xi))))
Similar to Step 1, we can show that the infimum for each cycle is achieved when the values f(xi) = f(xj),∀i, j ∈ V (Ck). A more detailed proof is given as follows. Pick an arbitrary k, and suppose all the edges of Ck are (v1, v2), (v2, v3), . . . , (vr−1, vr), (vr, v1), where r = |V (Ck)| is the number
of vertices in the cycle Ck. Denote vr+1 = v1. Then
inf f ∑ i∈V (Ck) log (1 + exp(f(yi)− f(xi))))
= inf f r∑ j=1 log ( 1 + exp(f(xvj+1)− f(xvj ))) )
= inf t1,t2,...,tr∈R r−1∑ j=1 log (1 + exp(tj+1 − tj))) + log (1 + exp(t1 − tr)))  =r log 2 = |V (Ck)| log 2.
(24)
The infimum is achieved when f(xv1) = · · · = f(xvr ), or equivalently, f(xi) = f(xj),∀i, j ∈ V (Ck). Therefore,
gcyc = log 2 K∑ k=1 |V (Ck)|. (25)
According to (23) and (25), we have
− ng(Y ) ≥ K∑ k=1 |V (Ck)| log 2. (26)
Next, we prove that for any > 0, there exists a continuous function f such that
− ng(Y ) < K∑ k=1 |V (Ck)| log 2 + . (27)
Let N be a large positive number such that
n log (1 + exp(−N))) < . (28)
Pick a continuous function f as follows.
f(xi) =
{ 0, i ∈ ⋃K k=1 V (Ck),
N · depth(i), i ∈ ⋃M m=1 V (Tm).
(29)
Note that the root um of a tree Tm is also in a certain cycle Ck, thus the value f(xum) is defined twice in (29), but in both definitions its value is 0, thus the definition is valid. For any i ∈ V (Ck), suppose yi = xj , then both i, j ∈ V (Ck) which implies f(yi)−f(xi) = f(xj)−f(xi) = 0. For any i ∈ V (Tm)\{um}, suppose yi = xj , then by the definition of the graph (i, j) is a directed edge of the tree Tm, which means that depth(i) = depth(j)+1. Thus f(yi)−f(xi) = f(xj)−f(xi) = −N. In summary, for the choice of f in (29), we have
f(yi)− f(xi) =
{ 0, i ∈ ⋃K k=1 V (Ck),
−N, i ∈ ⋃M m=1 V (Tm).
(30)
For the choice of f in (29), we have
− nF (Y ; f)
= n∑ i=1 log (1 + exp(f(yi)− f(xi))))
=  K∑ k=1 ∑ i∈V (Ck) log (1 + exp(f(yi)− f(xi)))) + M∑ m=1 ∑ i∈V (Tm)\{um} log (1 + exp(f(yi)− f(xi))))  (30) =
 K∑ k=1 ∑ i∈V (Ck) log (1 + exp(0))) + M∑ m=1 ∑ i∈V (Tm)\{um} log (1 + exp(−N)))  =
K∑ k=1 |V (Ck)| log 2 + M∑ k=1 (|V (Tm)| − 1) log (1 + exp(−N)))
≤ K∑ k=1 |V (Ck)| log 2 + n log (1 + exp(−N)))
(28) < K∑ k=1 |V (Ck)| log 2 + .
This proves (27). Combining (26) and (27), we have −ng(Y ) = ∑K k=1 |V (Ck)| log 2, or equivalently,
g(Y ) = 1
n K∑ k=1 |V (Ck)| log 2.
G.3.2 STEP 2: COMPUTE g(Y ) FOR ANY Y
In the general case, not all yi’s lie in the set {x1, . . . , xn}. Denote the set
H = {i : yi ∈ {x1, . . . , xn}}, Hc = {j : yj /∈ {x1, . . . , xn}}.
Since yj’s in Hc may be the same, we define the set of such distinct values of yj’s as
Yout = {y ∈ Rd : y = yj , for some j ∈ Hc}.
Let nout = |Yout|, then there are total n+nout distinct values in x1, . . . , xn, y1, . . . , yn. Without loss of generality, assume y1, . . . , ynout are distinct (this is because the value of g(Y ) does not change if we re-index xi’s and yi’s as long as the subscripts of xi, yi change together), then
Yout = {y1, . . . , ynout}.
We build a directed graph G = (V,A) as follows. The set of vertices V = {1, 2, . . . , n, n + 1, . . . , n+nout} represents x1, x2, . . . , xn and y1, . . . , ynout . For i, j ≤ n, we draw a directed edge (i, j) ∈ A if yi = xj ; in this case, there is a term log(1 + exp(f(xj) − f(xi))) in the expression of g(Y ). For 1 ≤ i ≤ n and 1 ≤ j ≤ nout, we draw a directed edge (i, n + j) ∈ A if yi = yj ; in this case, there is a term log(1 + exp(f(yj) − f(xi))) 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 yi = xi.
This graph has the following property: for each 1 ≤ i ≤ n, the outdegree is exactly 1; for each n ≤ j ≤ n + nout, the outdegree of j is 0. Moreover, each vertex representing some yi has an incoming degree at least 1 (since otherwise this vertex will not be created); note that an vertex representing xi 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:
(a) There exist cycles C1, C2, . . . , CK and subtrees T1, T2, . . . , TM such that each edge v ∈ A appears either in exactly one of the cycles or in exactly one of the subtrees.
(b) Denote the root of subtree Tm as um, m = 1, . . . ,M . Then um is either a vertex of a certain cycle Ck where 1 ≤ k ≤ K, or a vertex with outdegree 0. (c) Suppose u1, . . . , uM0 are in a certain cycle, and uM0+1, . . . , uM have outdegree 0. Then each vertex of the graph appears in exactly one of the following sets: V (C1), . . . , V (CK), V (T1)\{u1}, . . . , V (TM0)\{uM0}, V (TM0+1), . . . , V (TM ).
Note that (b) is different from Lemma 2, because under the assumption of that lemma that each vertex has an outgoing edge, the root of a tree cannot have outdegree 0.
The computation of g(Y ) is quite similar to the previous case. We will highlight a few small differences. We still have
− ng(Y )
= inf f n∑ i=1 ξ(f(yi)− f(xi))
= inf f  K∑ k=1 ∑ i∈V (Ck) ξ(f(yi)− f(xi)) + M∑ m=1 ∑ i∈V (Tm)\{um} ξ(f(yi)− f(xi)  ≥ inf
f  K∑ k=1 ∑ i∈V (Ck) log (1 + exp(f(yi)− f(xi))))  ,gcyc.
(31)
Same as before, we have gcyc = ∑K k=1 |V (Ck)| log 2. Once we fix the values of f(xi) to be a
constant for i in cycles (which makes the first sum achieves the value ∑K k=1 |V (Ck)| log 2), we can always pick the values of f on the vertices j in the trees so that f(yj)− f(xj)→∞. Therefore, we have
−ng(Y ) = gcyc = K∑ k=1 |V (Ck)| log 2.

heading: G.3.3 STEP 3: FINDING A NON-DECREASING PATH TO A GLOBAL MINIMUM
text: Finally, we prove that for any Y , there is a non-decreasing continuous path from Y to one global minimum Y ∗. In other words, there is a continuous function η : [0, 1] → Rd×n such that η(0) = Ȳ , η(1) = Y ∗ and g(η(t)) is a non-decreasing function with respect to t ∈ [0, 1]. In this proof, we will just describe the path in words, and skip the rigorous definition of the continuous function η, since it should be clear from the context how to define η.
The following claim shows that we can increase the value of Y incrementally; see the proof in Appendix G.6
Claim G.1 For an arbitrary Y that is not a global minimum, there exists another Ŷ and a nondecreasing continuous path from Y to Ŷ such that g(Ŷ )− g(Y ) ≥ 1n log 2.
For any Y that is not a global minimum, we apply Claim G.1 for finitely many times (no more than n times), then we will arrive at one global minimum Y ∗. We connect all non-decreasing continuous paths, and get a non-decreasing continuous path from Y to Y ∗. This finishes the proof of Proposition 2.

heading: G.4 PROOF OF LEMMA 2
text: We first prove a few observations. We will slightly extend the definition of “walk” to allow a walk with infinite length.
Observation 1: Suppose in a directed graph G = (V,A), any vertex has outdegree exactly 1. Starting from any vertex v0 ∈ V (G), there is a unique walk with infinite length
W (v0) , (v0, e1, v1, e2, v2, . . . , vi, ei, vi+1, ei+1, . . . ),
where ei is an edge in A(G) with tail vi−1 and head vi.
Proof of Observation 1: At each vertex vi, there is a unique outgoing edge ei = (vi, vi+1) which uniquely defines the next vertex vi+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 v0 isW (v0) , (v0, e1, v1, e2, v2, . . . , vi, ei, vi+1, ei+1, . . . ), then the walk can be decomposed into two parts
W1(v0) = (v0, e1, v1, e2, v2, . . . , vi0−1, ei1 , vi0),
W2(v0) = (vi0 , ei0+1, vi0+1, ei0+2, vi0+2, . . . ),
where W1(v0) is a directed path from v0 to vi0 (i.e. the vertices v0, v1, . . . , vi0 are distinct), and W2(v0) is the repetition of a certain cycle (i.e. there exists T such that vi+T = vi, for any i ≥ i0). 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 (v0). Among all such vertices, suppose u is the one that appears the earliest in the walk W (v0), and the first two appearances are vi0 = u and vi1 = u and i0 < i1. Denote T = i1 − i0. Since there is a unique edge going out from any vertex, thus vi0+1 must be the same as vi1+1 = vi0+1+T . Continue the process, we have vi = vi+T for any i ≥ i0. Thus starting from u = vi0 , the walk W2(v0) will be repetitions of the cycle consisting of vertices vi0 , vi0+1, . . . , vi1−1, and we denote this cycle as Ck0 .
If the vertices before vi1 are not distinct, then there are at least two vertices vj = vl where 0 ≤ j < l ≤ i0. This contradicts the definition of i0. Therefore, W1(v0) is a directed path from v0 to vi0 . 2 In Observation 2, for any v0 ∈ V , the “transition point” vi0 in the infinite walk W (v0) is unique. We define the “first-touch-vertex” of v0 to be vi0 . The first-touch-vertex u = vi0 has the following properties: (i) u ∈ Ck for some k; (ii) there exists a path from v to u; (iii) any paths from v to any vertex in the cycle Ck other than u must pass u. In other words, if an ant starts from v0 and crawls along the edges, the first vertex in a cycle that it touches is u. Since any v0 corresponds to a unique W (v0), 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 C1, C2, . . . , CK . Because the outdegree of each vertex is 1, these cycles must be disjoint, i.e., V (Ci) ∩ V (Cj) = ∅ and A(Ci) ∩A(Cj) = ∅, for any i 6= j. Define R to be the set of vertices of C1, . . . , Cm with indegree at least two, i.e.,
R , {v : v ∈ Ck for some k, and indegree(v) ≥ 2}.
Suppose the elements of R are u1, . . . , uM . We denote the set of vertices in the cycles as
Vc = K⋃ k=1 V (C1) ∪ · · · ∪ V (CK). (32)
We describe the intuition behind the partitioning of G. Based on Observation 2, starting from any vertex outside of Vc there is a unique path that reaches Vc. Combining all vertices that reach the cycles at um (denoted as Vm), and the paths from these vertices to um, we obtain a directed subgraph Tm, which is connected with Vc only via the vertex um. The subgraphs Tm’s are disjoint from each other since they are connected with Vc via different vertices. In addition, each vertex outside of Vc lies in exactly one of the subgraph Tm. Thus, we can partition the whole graph into the union of the cycles C1, . . . , CK and the subgraphs T1, . . . , TM .
Next, we provide more formal definitions and proofs. For any m ∈ {1, 2, . . . ,M}, define V̄m = {v ∈ V (G) : um is the first-touch-vertex of v}, (33a) Vm = V̄m\{um}, (33b) Am = {e ∈ A(G) : the tail of e is in Vm}, (33c) Tm = (V̄m, Am) is a subgraph of G. (33d)
We first show that V1, V2, . . . , VM and V (C1), . . . , V (CK) form a partition of the edge set of G, i.e.,
V (G) = ( K⋃ k=1 V (Ck) )⋃( M⋃ m=1 Vm ) , (34a)
Vm ∩ Vc = ∅, ∀m, s, . (34b) Vm ∩ V (Ck) = ∅, ∀m, k. (34c)
V (Ck) ∩ V (Cl) = ∅, ∀k 6= l, (34d)
For any vertex v /∈ (⋃K k=1 V (Ck) )
, its first-touch-vertex w must be different from v (otherwise v would be in a certain cycle). Since w is in a cycle, denoted as Ck0 , there is a directed edge with head w; in addition, since w is a first-touch-vertex of v /∈ Ck0 , then there must be another edge with head w. Thus the indegree of w is at least 2, which means w ∈ R. Thus w = um for some m, which implies v ∈ Vm. Since any v /∈ (⋃K k=1 V (Ck) ) must belong to Vm for some m, we have proved (34a).
Since each vertex v has a unique first-touch-vertex, thus a vertex cannot lie in two different sets Vm and Vs, which proves (34b). Assume (34c) does not hold, i.e., there exists some v ∈ V (Ck) ∩ Vm for some k,m. Since the first-touch-vertex of v is v itself, according to (33a) we have v = um; but according to (33b) v = um /∈ Vm, a contradiction. Thus (34c) holds. (34d) is obvious. Next, we show that the edge sets of T1, . . . , Tm and C1, . . . , CK form a partition of the edge set of G, i.e.,
A(G) = ( K⋃ k=1 A(Ck) )⋃( M⋃ m=1 A(Tm) ) , (35a)
A(Tm) ∩A(Ts) = ∅, ∀m, s, . (35b) A(Tm) ∩A(Ck) = ∅, ∀m, k. (35c) A(Ck) ∩A(Cl) = ∅, ∀k 6= l, (35d)
These relation can be proved easily by (34) and the definitions (33c) and (33d). For any edge e1 ∈ A(G)\ (⋃K k=1A(Ck) ) , we want to show that e1 lies in at least one Tm. Suppose e1 = (v0, v1) where v0, v1 ∈ V (G). Since e1 is not in a cycle, v0 /∈ Vc, thus by (34a) we have v0 ∈ Vm for a certain m, which further implies e1 ∈ Am = A(Tm) by the the definitions (33c) and (33d). Thus we proved (35a). Any edge e in A(Tm) has a tail u ∈ V (Tm), thus according to (34b) we know u /∈ Vs,∀s 6= m. By the definition (33c), we have e /∈ Am = A(Tm), which proves (35b). Similarly, any edge e in A(Ck) has a tail u ∈ V (Ck), thus according to (34c) we know u /∈ Vm,∀m, thus we have e /∈ Am = A(Tm), which proves (35c). The last one (35d) holds because the cycles are disjoint.
Finally, we prove that for any m ∈ {1, 2, . . . ,M}, Tm is a subtree of G with the root um. For any vertex v0 in the subgraph Tm, consider the walk W (v0). Any path starting from v0 must be part of W (v0). Starting from v0 there is only one path from v0 to um which is W1(v0), according to Observation 2. Therefore, by the definition of directed tree, Tm is a directed tree with the root um.

heading: G.5 PROOF OF LEMMA 3
text: We utilize the result of Lemma 2 to prove Lemma 3. More specifically, we will reduce to the case of Lemma 2.
We build a new graph as follows. Denote the set of vertices inG that have outdegree 0 asD0. For any vertice in D0, we add an edge from D0 to itself (a self-loop), and obtain a new graph G̃ = (V, Ã). Now each vertice in G̃ has outdegree exactly 1.
Each self-loop is a length-1 cycle, thus by adding edges to vertices in D0 we have created |D0| length-1 cycles, denoted as CK+1, . . . , CK+|D0|. Suppose all other cycles are C1, C2, . . . , CK .
According to Lemma 1, there exist cycles C1, C2, . . . , CK , CK+1, . . . , CK+|D0| and subtrees T1, T2, . . . , TM such that: (a) 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 um is a vertex of a certain cycle Ck where 1 ≤ k ≤ K + |D0|. In addition, each vertex of the graph appears in exactly one of the following sets: V (C1), . . . , V (CK), V (T1)\{u1}, . . . , V (TM )\{uM}, Now we remove the edges added to vertices in D0 and restore the original graph. Then we have removed the cyclesCK+1, . . . , CK+|D0| and do not change other cycles and subtrees. We do change the relations between the trees and the cycles: previously, the root of each tree is a vertex in a certain cycle; now, since some cycles are removed, the roots of some trees will be a vertex with outdegree 0. Suppose these trees are TM0+1, TM0+2, . . . , TM .
After removing the edges added to vertices inD0, C1, C2, . . . , CK and subtrees T1, T2, . . . , TM satisfy the following: (a) Each edge v ∈ A appears either in exactly one of the cycles or in exactly one of the subtrees. (b) Denote the root of subtree Tm as um, m = 1, . . . ,M . Then um is either a vertex of a certain cycleCk where 1 ≤ k ≤ K, or a vertex with outdegree 0. (c) Each vertex of the graph appears in exactly one of the following sets: V (C1), . . . , V (CK), V (T1)\{u1}, . . . , V (TM0)\{uM0}, V (TM0+1), . . . , V (TM ).

heading: G.6 PROOF OF CLAIM G.1
text: We first prove the case for d ≥ 2. Suppose the corresponding graph for Y isG, andG is decomposed into the union of cyclesC1, . . . , CK and trees T1, . . . , Tm. We perform the following operation: pick an arbitrary tree Tm with the root um. We claim that there must be an edge e with the head um. If um > n (i.e. um represents some yi), then there must be an incoming edge to um, thus the claim holds. If um ≤ n (i.e. um represents some xi), then um must have an outgoing edge, and this edge must be in a cycle (otherwise um cannot be the root). Thus um is chosen to be in a tree Tm must because um is a head of an edge.
Suppose v is the tail of the edge e. Now we remove the edge e = (v, um) and create a new edge e′ = (v, v). The new edge corresponds to yv = xv . The old edge (v, um) corresponds to yv = xum (and a term ξ(f(xum) − f(xv))) if um ≤ n or yv = yum−n /∈ {x1, . . . , xn} (and a term ξ(f(yum−n) − f(xv))) if um > n. This change corresponds to the change of yv: we change yv = xum (if um ≤ n) or yv = yum−n (if um > n) to ŷv = xv . Let ŷi = yi for any i 6= v. Previously v is in a tree Tm, now v is the head of a new tree, and also part of the new cycle CK+1 = (v, e′, v). In this new graph, the number of vertices in cycles increases by 1, thus the value of g increases by − 1n log 2, i.e., g(Ŷ )− g(Y ) = 1 n log 2.
Since d ≥ 2, we can find a path in Rd from a point to another point without passing any of the points in {x1, . . . , xn}. In the continuous process of moving yv to ŷv , the function values will not change except at the end that yv = xv . Thus there is a non-increasing path from Y to Ŷ , in the sense that along this path the function values of g does not decrease.
The illustration of this proof is given as below.
For the case d = 1, the above proof does not work. The reason is that the path from yv to ŷv may touch other points in {x1, . . . , xn} and thus may change the value of g. We only need to make a small modification: we move yv in R until it touches a certain xi that corresponds to a vertex in the tree Tm, at which point a cycle is created, and the function value increases by at least 1n log 2. This path is a non-decreasing path, thus the claim is also proved.

heading: H GENERATED SAMPLES IN SIMULATION
text: Here we show some samples of generated data in the appendix.

Review summaries:
In this paper, the authors introduce a new training loss for GANs.  This loss allows the outer optimization problem to have no spurious local minima, under an appropriate finite sample analysis.  In contrast, the authors establish that there are exponentially many spurious local minima under the conventional GAN training loss.  Under a linear discriminator model, the authors show that a standard GAN can not escape from collapsed modes in a finite sample analysis, whereas the new trining loss allows for such an escape (due to the presence of a Lyapunov functional with favorable properties).  The authors use this new training loss to train GANS on MNIST, CIFAR10, CelebA, and LSUN datasets, and observe mild improvements in Inception Scores and Frechet Inception Distances of the resulting generated images.