CP-GAN: Towards a Better Global Landscape of GANs
Authors: Ruoyu Sun
Tiantian Fang
Alex Schwing
Venue:  (2020)
Keywords: GAN
global landscape
non-convex optimization
min-max optimization
dynamics

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. 

Under review as a conference paper at ICLR 2020
CPGAN: TOWARDS A BETTER GLOBAL LANDSCAPE OF GANS
A Anonymous authors Paper under double-blind review
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 per- spectives: the global landscape of the outer-optimization problem and the global behavior the gradient descent dynamics. We find that the original GAN has ex- ponentially many bad strict local minima which are perceived as mode-collapse, and the training dynamics (with linear discriminators) cannot escape mode col- lapse. To address these issues, we propose 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 ex- periments on standard datasets show that this simple loss outperforms the original GAN and WGAN-GP.
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 pPp: Pdata) max, (P Pdara), where hn is a binary classification loss that depends on the discriminator D. To justify the loss, Gooofelole et al. (2014) prove two theoretical results: first, for given Pg. the outer function o(Pg.Pdata)) is the Jenson-Shannon (JS) distance (minus a constant); second, the outer function is convex in Pg. SO 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 ming max, 167 AO 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 local
vergence (Daskalakis et al. 2017 Daskalaks & Panageas 2018 Azizian et al. 2019 Gidel et al.) 2018 Mazumdar et 2019 YazIcı al. 20188 Jin al. 2019 Sanjabi al. 2018). Local analysis
can tell us the behavior of the algorithms near the desired point, but how do we know that the algo-
rithm will arrive there and not at some highly sub-optimal points? Answering this question requires global landscape analysis or study of global training dynamics.
There are some attempts on a global analysis of GANs. Mescheder al. (0018) and Feizi et al. (017) analyzed the simplest setting: the true data distribution is 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 Ieast 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-modaa setting. Again, the difficulty here is that the practical GAN formulation is not works and other related ones are reviewed in more detail in Appendix B
even for simple tissrriminattos/eeeraatosss These
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 multi-point

---

Under review as a conference paper at ICLR 2020
distribution. This is finite-sample version of the problem analyzed by Goodfellow et al. (2014) and a multi-mode extension of the Dirac-GAN problem analyzed by [Msccheer 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 al.] (2014). In contrast, 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 mode- collapse 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 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, prove that with linear discriminators, the training dynamics of CP-GAN can escape from mode-collapse; in addition, 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 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 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 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 formula- tion 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 Pdatas want to generate new distribution Ps. to mimic Pdata- To judge how far away the generated distribution Py is from Pdata. a discriminator (a.k.a. critic) computes 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 generate Pg to fool the discriminator so that the loss value is minimized, Formally, the problem for a GAN is given by
min max E Epppesss Po (z)) + log(1 D(y)). Ps
1
A common choice for the discriminator is D(n) = I+exp(- where f is a function. Given this choice, the formulation given in Eq. becomes
1
min max E pan. log
+ -log I exp(
P4
I exp(-f(x))
2

---

Under review as a conference paper at ICLR 2020
We will use a generator (2(2) parameterized by 0 to produce samples from distribution Pg. where 2 is drawn from given distribution pz. This yields the following program:
min max Prp log + exp(-f(z)) + log 1 exp(f(G(2)))
(2)
G
To resolve the vanishing gradient issue, Goodfellow et al. 2014) proposed to use a game formulation (often referred to non-saturating GAN);
max maxa log exp(-f(2)) + log exxp([(((())
(3a)
min E. - parMan log(1 + exp((f((((2)))
(3b)
2.2 COUPLING GAN
As mentioned before, the program is given in Eq. 33 has shortcomings, which we propose to address via the following formulation:
min max E Be-Paatt [log 1 ex) fo()))
(4a)
Similar to the - log D trick used the original GAN training (a.k.a. non-saturating GAN), in prac- tice we always use the non-saturating version for training:
D problem min E Erppaaa [log(1 - exp(fo(G(())) - -
(5a)
G problem min E Pa [log(1 (1 - exp(fa(z) fo(GG
(5b)
Here fo a deep net parameterized by 0, and Gy is a generator net parameterized by th
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 21 1 and I2 = 2, and generated data are 1/1 = 0.5 and = 0.5, then the boundary is drawn at, say, 0.8. Then the discriminator only has the motivation to approach 22 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 22 to be missed by the generator, since is "too good to learn".
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 J2 2. Thus can better learn the true distribution. An analogy 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.
1, and 3/2 will try to cross 1.5 to approach
MUL.I-DIRACGAN, MULTI-MODS GENERATION
Mescheder 2018 quoted Rahimi: "simple experiments, simple theorems are the building blocks that help us understand more complicated systems." Then they defined simple model called Dirac- GAN, which uses a linear discriminator and powerful generator to recover a single-point distribu- tion. We define much more general model than the DiracGAN. We refer it as Multi-DiracGAN,
Definition 3.1 The Multi-DiracGAN consists of generator distribution Y = (yi,..., ..)) E RRxx and discriminator f(x). The true data distribution given by a n-point distribution (I1....,Za) E pdxn, where x, 's distinct.
One motivation of the Multi-DiraCGAN is to consider "empirical" version of the problem. Yet another motivation is the construction of a simple model of multi-mode distributions: for instance, when 2, have two-point distribution which is the simplest two-mode distribution. We are not aware an existing global analysis that can be applied to this simple 2 2-point model. See Appendix A for more discussions.
3

---

Under review as a conference paper at ICLR 2020
When analyzing 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, Le., check whether there are undesirable local minima; (3) Convergence analysis, ie., 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 IS-GAN under the tors, the formulation of which can be written as:
model with powerful discrimina-
min das (Y, X) - max 1, (J:Y), YERT
(6)
where (f:Y) = - E log(1 +
1/ Ei= log(1 exp(f(xx))
The range of ØJs (Y. is log
2, 0) because I I (f: s 0 and X) 2 L(0:Y)
=
log where L(0; Y) represents the value achieved
To build intuition, we first present result for the case of n 2 points.
Claim 4.1 Suppose n = 2 and 21 # I2 E Rd Then
2 2 = 1.3862,
if [21, x22 = {11, V2
log 2 R 006931,
if (211 0 {41 y2 } 1,
(Y,
log 1.5 = 0.9548,
y1 = y/2 E {21, 52).
if [2) n (11, 82) = 0.
The global minimumm is -2 log 2, which is achieved iff the generated data points {y1, y23 coincide with the true data points {x1, x2
As 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 21 o x2 IR.d. Then Y (11, 21) ) is sub-optimal strict local minimum of the function gY) (Y,
We illustrate the landscape Φus (Y, ) in Figure for the special case that d d 1, 1,:2100,20
= 02
In this case, Y (21, y2) (0, 1) is the global minimum of ΦJs (Y,X) with optimal value -2 log 2 x - 1.38622 and Y = (0, 0) is a strict local minimum of dJs(Y, X) with value approx- imately 00.9548. An intuitive way to understand the landscape and Corollary 4.1 is given fol- lows. Consider a point (V1.32) 32) moving from 10 to (-0.1, -0.1), going through four points: (y) 3/2 = (0, 1). (0, 0.5).. (0,0), and finally (-0.1, 1..)). The four points correspond to the four cases above, thus giving values - 1 1.3862, -0.6931, 0.9548, O. The four values are not monotone, indicating that there is striet local minimum at -0.9538.
For general the landscape can be characterized in similar fashion. The following result states that the original GAN objective has exponentially many strict bad local minima.
Proposition 1 Suppose 31, 32, 22, In E Rdd 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., {yI..... Vn = {ø1..... 2n).
(ii) If yi E (II,..., In,) i 1.2.... ...., ...... and y; Yi for some + j. then Y is sub-optimal strict local minimum. Therefore, dus( X) has (n - n!) sub-optimal strict local minima.
The landscape analysis is high-level analysis that provides some preliminary insight into the train- ing process. But there are gaps compared to the true training process: (1) in practice, we always
4

---

Under review as a conference paper at ICLR 2020
(YA)
Vor (Y20)
(0.0)
(R+)
(0.1)
Y
(-c-d)
-0.9931
-0.3466
0.0540
(a) original GAN
(b) CP-GAN
Figure 1: Graphical illustration of the landscape GAN outer optimization problem miny o(Y, X). is a rigorous figure for two reasons: (1) there are only four possible function values, thus the function is piece-wise linear function, but we use smooth curves to connect them to make the figure easier understand. (2) the landscape should be two-dimensional, but only pick illustrative points and and illustrate them in ID space.
use different objectives for and G (the - log D trick) to resolve the gradient vanishing issue; (2) the D problem is addressed via 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 & 88 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. 66 which is also the Umite-sample version of Eq. (3). We assume linear discriminator ((u) w² where Rd b E R.
min (=( XR
LO (Y; A
log(1 exp(-wo b)) log(1 + exp(w"
u yE b)),
min W.
LG GAN (Y; A
log(1 -xxepxp= ys b)).
Consider the dynamics corresponding to the simultaneous gradient descent (GD)
dw
aL.8AN
Vi
(7a)
dt Ow
+ e t
1 + e w g
db
aL Øb
Σ
(7b)
dl
+ T zetb
+ 1+e-wTg--6
dy:
OLGAN
W
(7c)
dt
Dy:
1 + e 4
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.
'Other papers, such as Mescheder 2018) analyzed both simultaneous GD and alternating GD. For simplic- ity, only analyze simultaneous GlD in this paper.
5

---

Under review as a conference paper at ICLR 2020
Even if one does not find such function, one may wonder whether this is due to the lack of tech- nical tools, or due to some intrinsic barriers. Motivated by the landscape result in Proposition]] []] we wish analyze the mode-collapse patterns, i... the pattern occurring when some points overlap. In- terestingly, 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(0), (()),, the trajectory (())) defined in Eq. (2 satisfies (tv:(t) - y3 (t)ll & (0) yy (0)], Vt.
This claim predicts that starting from y1 (0) (2 prevents these points from separating. It is interesting to more rigorously characterize bad global behavior of JS-GAN dynamics, either for a linear or neural-net discriminator (e.g., whether mode- collapse 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.
yn (0) (all points fall into mode),
4.3 DISCUSSIONS OF WGAN AND ITS VARIANTS
One may wonder whether W-GAN or its variants can provide 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 S. it is not hard to prove that the outer-optimization problem has nice landscape. However, it hard to impose the Lipschitz condition practice; in addition, gradient dynamics with constraints are difficult to analyze
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 maxy Σ, (x;) - E, f(y)) (IV. lu=y. 1)² may have complicated land- scape 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 (O))) the trajectory (t)) defined by WGAN-GP dynamics satisfies [[y:(t) yソ (t) (0) (D)l,,, Vt.
To avoid additional issues due to constraints, we remain interested in the logistic function used in the JS-GAN formulation. We hope that 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 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
1 log 1 + exp(f(())) f(x:)))
min Φcr (0, X); where (Y, x) sup f
(8)
Y
resulting in a range dcr (Y, X) E l- 2, 0]. For simplicity, we define PP = Φcr X) as the data X are fixed throughout the paper.
Proposition 2 Suppose I1, F2,,I....,, E Rdd are distinct. The global minimal value of PY is - -oo 2, which is achieved iff {21...., _n} = {yi...., }n Furthermore, for any Y, there continuous path from Y to global minimum along which the value of g CY is non-increasing.
Mescheder (0188) analyzed W-GAN dynamics, but only consider the local region around 0, thus its anal- ysis essentially ignores the Lipschitz constraint.

---

Under review as a conference paper at ICLR 2020
To understand this result, consider the special 2 and 21 + 22 E R In this case, have
- log2 2 = -06931,, log 00.3466, if If I. y =
if #2) = 323
Φcp (Y,
otherwise.
We illustrate the landscape of g CP (Y) in Figure [ for the special case that n. 2, 1,21 0,32 = 1. In this case, (1), 1/2) (0, 1) and (V1. 32) = (1, 0) are two global minima of g (Y) with optimal value - log 2 -0.6931. Similar the previous subsection, there an intuitive way to understand the landscape: Consider point (/)) moving from (0, to (-0.1, going through four points: (31,3/2 (0, 1), then (0, 0.5). then (0, 0), and finally (-0.1,
The four points correspond to four values -0 -0.6931, 00.3466, -0.3466, O. The four values are non- decreasing, indicating that there a monotone path connecting the mole-ccllapsed pattern (0, 0) and 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 harrier.
Comparing Proposition 2 and Proposition T. 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 random initial point, 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 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-sampee version of Eq. (5) Further,
we assume the linear discriminator f(u) = w" u, where w E Rd:
min @=wER
log(1 + exp(w" (y/s xx))),
(9)
L (Y: &
log(1 (1 + exp(w" (z; v:))).
Y= dx
Consider the dynamics corresponding to the simultaneous gradient descent for CP-GAN:
dw aL
(10a)
dt Ow
eu (1)-
f=1
dy.
aLge
(10b)
dl Oy:
1 wwn (1i =x,)
Define 6, Vi F,, Vi. Define function Biy(t) = (l( - 8,(t)l2,
Claim 5.1 Along the trajectory defined by Eq. (0)],, Vi
10 we have (1) 8,(1) < ((()((0)
This claim looks similar to the result for the IS-GAN dynamics given in Claim 4.2 However, there 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
|
2
yill2
2
Obviously, = 0 iff w = and x; = yi, Vi. According to the following result, V is non-increasing along the trajectory of CP-GAN training.
7

---

Under review as a conference paper at ICLR 2020
Model
MNIST
CIFARIO
STL10
CelebA
LSUUN
FID
IS
FID
FID
IS
FID
IS
FID
NSGAN
1.98:1.001
7.73
5.6210.09
53.42
0.06
82.81
2.4610.01
21.68
2.77
41.15
WGAN-GP
2.00:10001
7.05
6.52::0.08
40.31
7.3410.11
65.23
0.05
17.18
2.80
34.02
CPGAN
2.05+0002
5.08
6.72:10.06
36.66
7.56=0.21
57.07
2.73+0.02
15.45
2.82+0002
30.41
Table 1: Inception score (IS) (higher is better) and Frechét Inception distance (FID) (lower is better) for non-saturatie non-saturating GAN, WGAN-GP and our proposed CPGAN on MNIST, CIFARIO, STL10, CelebA and LSUN.
Claim 5.2 Along the trajectory of the dynamics defined in Eq. 10 have dV()) S 0.
Thus V is Lyapunov function for the CP-GAN dynamics. As mentioned earlier Mescheder (2018) showed that V is a Lyapunov function for the JS-GAN dynamics inon-saturating version) given Eq. (20) if n
and x = However, when we check the case Ii + 0, we found it is no longer Lyapunov function. This means that the JS-GAN formulation is not "translation-invaria" in the sense that shifting z; and y: together leads to different dynamics. simple fix to make shift-invariant is couple Y and X together.
With the Lyapunov function, we have the global convergence to the set 0 such that (V),(0), h()) = where h is the right-hand side of Eq. (TO). With bit more effort, we show the global convergence of CP-GAN dynamics.
(global convergence of CP-GAN dynamics) Starting from any initial point 0(0), con- sider the trajectory defined by the CP-GAN dynamics 0(t).
Proposition 3
(1) For general d, lim; 0(t) E E, where E _ {(w, y) w" (y: -x;) = 0, 0.Vi].
(2) When d = 1, starting from any initial point (()), lom 0(1) E M, where M = [w,, y)
0, Σ, I. y.
The set of stationary points include some undesired points. The next result shows that the Jacobian these undesired points has positive real part, thus they are not stable. Simulations also show that small perturbation can escape these undesired points.
When d = 1, for the training dynamics given in Eq. (TO). at any point other than the desired solution (y1...., yn) = (II,,..., Ra)) in the set of stationary solutions, the Jacobian has an eigenvalue with positive real part.
Claim 5.3
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 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 (x), v22 is drawn from a mixture of 5 or 25 equally weighted Gaussians each with variance 0.002, the means of which are spaced equally on the unit circle. See the blue points in columns (a) and (d) of fig an illustration. Our generated samples 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 shown in (b), (c), (e) and (f).
8

---

Under review as a conference paper at ICLR 2020
(d)
(e)
Figure 2: (a) True(blue) and generated(red) Samples (b) loss for the generator (c) loss for the dis- criminator 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.
6.2 IMAGE GENERATION
In this section, we present results on the task of image generation. We train and evaluate CPGAN
on four datasets: (1) MNIST (LeCun al. 1998) (32x32); (2) CIFAR-10 (Krizhevsky) 2009)
(32x32); (3) STL-10 (Adam Coates 2011) (48 x88); (4) CelebA (Liu et al.) 2015) (64x64); and (5) LSUN Bedrooms (Yu et al. 2015) (64x64). 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 generator is 128-dimension.
In all our experiments we train the generator and discriminator in an alternating fashion. The batch size set 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 shown in Appendix H
We use inception scores (IS) (Salimans et al. 2016) and Frechét Inception distance (FID) (Heusel eet 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 T We observe the proposed loss 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. this work, we analyzed an empirical version of few GAN formulations, i.e., assuming the true data distribution is the empirical dis- tribution consists of n points. In this formulation, the samples are moving during the optimization process, which what happening in practical training. This analysis can also mimics an n-mode distribution; in fact, it captures the macro-lcarning 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 new formulation CP-GAN does not have bad basins. Fur- ther, we analyzed the training dynamics for the log-linear discriminators, and showed that there is global Lyapunov function for CP-GAN. Simulation CELEBA, CIFAR10 10, 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.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Andrew Y. Ng Adam Coates, Honglak Lee. An analysis of single layer networks in unsupervised feature learning. AISTATS, 2011.
Martin Arjovsky and Léon Bottou. Towards principled methods for training generative adversarial networks. In NIPS 2016 Workshop on Adversarial Training. In review for ICLR, volume 2016, 2017.
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (GANs). In Proceedings of the 34th International Conference on Machine Learning, pp. 224-232, 2017.
Waiss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. A tight and uni- fied analysis of extragradient for a whole spectrum of differentiable games. arXiv preprint arXiv:1906.05945, 2019.
Cyril Cohen and Damien Rouhling. formal proof in coq of lasalle's invariance principle. In International Conference Interactive Theorem Proving, pp- 148- 163. Springer, 2017.
Constantinos Daskalakis and Toannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems, pp. 9236-9246, 2018.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint arXiv:1711.00141, 2017.
Soheil Feizi, Farzan Farnia, Tony Ginart, and David Tse. Understanding gans: the log setting, arXiv preprint arXiv: :tt.::/710.10999 10793, 2017.
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Remi Lepriol, Gabriel Huang, Si- mon Lacoste-Julien and Ioannis Mitliagkas. Negative momentum for improved game dynamics. arXiv preprint arXiv: 1807.04740, 2018.
Ian Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 2672-2680, 2014.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Im- proved training of wasserstein gans. arXiv preprint arXiv:/704.00033 2017.
Wassim M Haddad and VijaySekhar Chellaboina. Nonlinear dynamical systems and control: Lyapunov-based approcch. Princeton university press, 2011.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge local nash equilibrium. In Advances in Neural Information Processing Systems, pp. 6629 6640, 2017.
Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Minmax optimization: Stable limit points of gradient descent ascent are locally optimal. arXiv preprint arXiv: 902.00618. 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Corinna Cortes, and Christopher JC Burges. The mnist database of handwritten digits, 1998.
Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, and F Huang. A tutorial energy-based learning. Predicting structured data, 1(0), 2006.
Jerry Li, Aleksander Madry, John Peebles, and Ludwig Schmidt. Towards understanding the dy- namics of generative adversarial networks. arXiv preprint arXiv:1706.0988 2017.
Zinan Lin, Ashish Khetan, Giulia Fanti, and Sewoong Oh. Pacgan: The power of two samples in generative adversarial networks. In Advances in Neural Information Processing Systems, pp. 1498-1507, 2018.
10

---

Under review as a conference paper at ICLR 2020
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 Jordan, and Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. arXiv preprint 1001:0900.000... 2019.
Lars Mescheder. On the convergence properties of gan training. arXiv preprint arXiv:1801.0444 1:16, 2018.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for gans do actually converge? arXiv preprint wrXh::/801.04406 2018.
Luke Metz, Ben Poole, David Pfau, and Jascha Sohl-Dickstein. Unrolled generative adversarial networks. arXiv preprint 161.0666,, 2016.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprint 1r02iv/802.05000 2018.
Ruslan Salakbutdinov and Geoffrey Hinton. Deep boltzmann machines. In Artificial intelligence and statistcc, pp. 448-455, 2009.
Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, Xi Chen, and Xi Chen. Improved techniques for training gans. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp- 2234 2242. Curran Associates, Inc., 2016. URL http::/ nips cc/paper/ 6125- - $125-improved mmppoovdd-eehhiggeeee wwweeehhnnissoor-eeeeeeeeeeeeeee
Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn, and Jason D Lee, On the convergence and ro- bustness of training gans with regularized optimal transport. In Advances in Neural Information Processing Systems, pp. 7091-7101, 2018.
Yasin Yazıeı, Chuan-Sheng Sheng Foo, Stefan Winkler, Kim-Hui Yap, Georgios Piliouras, and Vi- jay Chandrasekhar. The unusual effectiveness of averaging in gan training. arXiv preprint arXiv:1806.0448 2018.
Fisher Yu, Ari Seff, Yinda Zhang, Shuran Song, Thomas Funkhouser, and Jianxiong Xiao. Lsun: Construction of large-scale image dataset using deep learning with humans in the loop. arXiv preprint 1rx.v31506.0336,, 2015.
A EMPIRICAL VERSION: EFFECT OF MACRO-LEARNING
The motivation of analyzing the empirical version is two-fold. First, it is 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 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 explicit probability density is moving. These two views are illustrated in Figure
Next, we will explain that the two views are both related and orthogonal.
First, there is connection between the two views. As shown in Figure 4 we can smooth the empirical distribution (blue color) which discrete to a continuous distribution (yellow color). During the algorithms, the samples actually moving, but that also corresponds to the moving of the underlying continuous probability density. Thus it is reasonable to assume 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 "micro- learning" respectively, when learning multi-mode distribution. Consider learning two-mode

---

Under review as a conference paper at ICLR 2020
Y1
Y2
Y3
Pg
(a) Population version: probability density changes
(b) Empirical version: samples move
Figure 3: Population version and empirical version. Population version: the probability densities
changing. Empirical version: the samples 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.
distribution Pdata. and we start from an initial two-mode distribution Pg. There are two differences between Py and Pdaza: first, the locations of the two modes 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 roughly overlap with the modes of Pdata which call "macro learning"; second, adjust the distributions of each mode to match those of Pdata. which we call "micro learning". This illustrated in Figure Figure
Therefore, we have explained the two reasons of analyzing the empirical version (the n-point distri- bution). First, is the practically used version. Second, captures the "macro-learning" behavior of learning a multi-mode mode distribution.
Finally, the two types of learning are related the two types of mode collapse mentioned Lin et al. (2018): "entire modes from the input data are never generated, the generator only creates images within a subset of 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 micro- learning can cause a sub-mode mode to be missed, which also corresponds to the second type of mode collapse. See more discussions of related works mode collapse in Appendix B
A.1 GENERALIZATION
One may wonder whether fitting the data points can cause memorization and thus may not gen- eralize. 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 Py- Further, suppose sample points z/s from Pş and sample points from Pg. and use f and z/ to represent the two empirical distributions (discrete distributions with equal probability). Arora et al. (2017) proved that for large class of GAN problems (including JS-GAN using neural-net discriminaor and generators), only polynomial samples are needed to achieve small generalization error. As result of the generalization bound, Arora al. (2017)
12

---

Under review as a conference paper at ICLR 2020
Figure 5: Illustration of the process of learning multi-mode distribution. Will decompose this process into two parts in the next figure.
X1
Y1
Y/2
X2
(a) Macro-learning
(b) Micro-leamingg
Figure 6: Illustration of learning a mudti-mode distribution. We decompose the process as the macro- learning and the micro-learning. The macro-learning refers 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 mode collapse. Note that even for the single-mode, the learning process can be decomposed into the macro learning and the micro learning.
stated that if the GAN successfully minimized the empirical distance (i.e. the distance between j and v), then the population distance (the distance between the two distributions Pdsta and Pg) is also small. Therefore, there 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 this paper mainly to study how to "successfully minimized the empirical distance" (i.e. fit the n-point distribution μ)). Technically speaking, the form of Arora ct al. (017)) 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 simple case learning two-mode distribution Figure During training, we learned generator that maps the latent samples 's to v, 's, thus fit the empirical distribution. If we sample new latent sample 2; then the generator will map 2y to a new point zj in the underlying data distribution. Thus fitting the empirical distribution still leads to generating new data points.
X
Figure 7: Learning two-mode distribution. During training, we learned generator that maps the latent samples 2 2; 'ss thus fit the data. we sample new 2;, then it will be mapped new point in the underlying data distribution.
13

---

Under review as a conference paper at ICLR 2020
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 ct al. (2117) analyzed the case that the true distribution Pdata is a single Gaussian distribution. It considers the population version, i.e., there is continuous latent distribution of pz. For a new formulation called quadratic GAN and using a linear generator and 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 bi-linear game which 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 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 macro- learning effect and micro- miiro-llarning effect. Our work on n-point distributions captures the macro- learning 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
case.
Mescheder et al. (2018) considered the case that the true distribution Pdata is a single point O. 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,
found that their proof cannot be directly generalized the case that Pasta is a single non-zero point. Thus even for the single non-zero point setting, it is natural to use our CP-GAN formulation prove global convergence.
Mode collapse. Mode collapse is one of the major challenges for GANs, and received a lot of atten- tion. 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 few high-level hypotheses, such as improper loss function AArjovsyy& & Bottou| (2017); Arora et al. (2017) and weak discriminators Metz et al. (2016); Salimans et al. (2016): Arora et al. (2017): [i 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 al. (0166) and minibatch discrimination Salimans et al. (2016). A recent work [in et al. (2018) proposed theoretically motivated method PacGAN, which 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 UO0 11, PA U/0.2, 1] and P2 = 0.6U 0. 0.5) + [[.5, IJ). where U(a,b) is the uniform distribution on [a, b). Then TV(Q, Pi) TV(Q, P2), but Pi has mode collapse while P2 does not. They proposed pack the samples, i... consider the distance of the product distribution pm and Q" The main theoretical result that "TV( QT)) is a better loss penalize strong mode collapse than (V, 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. (018)) in the following aspects. First, they did not provide theoretical analysis for specific GAN; in contrast, we prove theoretical results of specific JS- JSN and CP-GAN formulations. Second, we provided an explanation for "why mode collapse happens", by linking mode collapse to 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 natural byproduct of the analysis.
C PROOFS IN SECTION 4.1
C.1 PROOF OF CLAIM 4.1
We will compute values of @i,(Y, X) for all Y.
14

---

Under review as a conference paper at ICLR 2020
Denote ((u) ((w) E 1]. Since can be any continuous function, D can be any continuous function with range (0, 1).
n log
(X, = sup
log
f
71
+ exp(-f(z:))
i=1 1 + exx((((ui))
i=1
sup
(zx:)))))) +
Σ log(1 D(vil))
72
Consider four cases.
Case 1: Both generated points overlap with the true data points, and are distinct, i.e., y1 I1, Y2 I2 or 1/2 = æ1, 1/2 = ø2. Then the objective is
sup
log (og(D((z))
log(1 D(a1)) + log(D(xz)) log(1 - D(x2))
The optimal value is 2 log 2, which is achieved when D(x,) - D(22) 2. The corresponding function values of f are f(z1) = f(²2) = 0. The values on other points do not matter.
Case 2: Exactly generality, we can check the case y1 = I1, y2 & {2). The problem becomes
of the generated points overlaps with the true data points. Without loss of
1 (og(D(z))) + log (D(())))) + log(1 - (xx )) log(1 D(v2)) sup 1
The optimal value - log = -0.6931 is achieved when ( ) = 1/2, D(x²) ) = 1 and D(y2) = 0. The corresponding function values are f(z)) log 2. f(x2)
and f = -0.
Case 3: Both generated points overlap with the true data points, and are the same. Without loss of generality, check the case f11 1/2 T1-
log(D((>))) + log(1 D(x1)) + log 1og(D(z2))
1
sup
2
2
The optimal value log + log 2 = - 0.9548 is achieved when D(x1) = 1/3 and D(x2) = 0. The corresponding function values of are (x1) = log 2, f xc.
Case 4: Both generated points are different from the true data points. y1,82 & (21, It becomes separable over the four points
log(D()))) + log log(D(zz)) + log(1 D(v1)) log(1 D(va)) sup 2
Each term can achieve its maximum log 1 = 0. Thus the optimal value is achieved when D(x1) = D(r2) and (3))) D(y2) 0. The corresponding function values of are f(x1) -00 f(x2) = 00
C.2 PROOF OF COROLLARY 4.1
We re-state the corollary below.
Corollary C.1 Suppose Y = (#1, F2) satisfies σ1 = T2 = F1, then a sub-optimal strict local minimum of the problem.
Proof: Suppose is the minimal non-zero distance between two points of æ 22 V1, y2- Consider a small perturbation of Y as Y ( c1, T2 + c2), where |cs| < c. We want verify that
(( X)) > @ X) 0..548..
(11)
There are two possibilities.
Possibility 1: é1 0 62 O. WLOG, assume e 0, then must have e2 > 0. Then still have = Ø1 I1. Since the perturbation amount is small enough, we have 32 &f {x1,22). According to Case 2 above, we have
(( x) log -0.6931 -0.9548.
15

---

Under review as a conference paper at ICLR 2020
Possibility 2: 61 0, 0. Since the perturbation amount é and éz small enough, have y1 $ [21, 8/2 $ {2). According to Case above, we have
o(Y, X) - 0 0.9548..
Combining both cases, we have proved (22
Q.E.D.
C.3 PROOF OF PROPOSITION
Denote (()) T-exp(- (wa)
[0,1]. 1]. Since f can be any continuous function, can be any continuous function with range 1).
(Y, = sup
log
log 1 + (xx(((()
f 71
+
i=1
sup
1
+ log(D(z;))
n Σ
1
log(1 D(y))).
D
11
Denote F(D:Y) = E log(D(z)) + Ei= log(1 - D(v)). Since D(u) E (0, for any u, then F(D;Y) < 0. When Duu) 2, Vu, we have F(D;Y) Y) -2 log 2, thus oIs(Y, supp (D;Y) log Thus the range of é )) is log 2,0g 0j.
Now compute the value of ΦJs(; X) for each Y. For any i, denote Mi to be set of indices of yj such that yy equals vy and m, to be the size of the set M,, i.e.,
Mf i : B = 3 m, MM .,. n
Denote 5 =1.22
.......n)mncc (M M2 ... Mn). Then we have
oJs(Y, = sup n
1
log(D (D(x)))
Σ
log(1 D(s)))]++ Σ
log(1 D(U;))
JEM,
jgf
1 sup
[log( ((zz)) m. log(1 D(x;))l + Σ log(1 D(y)))
n
1
sup [log(4) + m, log(1 4:)] + ER
(18)
m
log
+ m. log
n
m4 +
1
mm log m4 (m; + 1) log(m; 1)].
Here (i) is because D Dyy)). E are independent of D(x;)'s 's and thus can be any values; in this step. the optimal ( 1, Vj Ω. (ii) is because for any positive number m, sup,eR (lo.e)) +
m Em log(1 1)] log m++ m log m-T
When m. 1, 1,2,.... ... n, i.e., y/1 xz, Vi, the function dus X) achieves value -2 log Thus Y = 7 02, Fn) is a global minimum.
Next, show that if Y satisfies that if mi ma + + m, then y is strict local-min. Denote ó as the minimal distance between two points of x T2,,,,, In. i.c.
= min | - mill-
kll
Consider small perturbation of Y as Y = (Vi ......, Fn) (v1 + + 82 ......, ||s,]| 6, Vj and E, ||,, O. We want verify that
.e....,,h .n + tc), where
dis (Y, X) > dus (Y, X).
(12)
16

---

Under review as a conference paper at ICLR 2020
Denote
m; = Kij:: =, 1,2.... .., n..
According to the assumption my + m2 +... my = n, we have yj E {- f Vj. Consider
an arbitrary and suppose yj 24. Together with || - ツ/y
|Eil < ming || - æı||,
we have Øj & (121, 22...,, In J {) In other words, the only possible point in f.1,,..,,8 Znn that can coincide with Jj is 24, and this happens only when Ej O. As result, we have
m, S mi, , 1,2,..... 72
Together with the fact that t logt - + 1) log(t + 1) is strictly decreasing function in E [0, oo), have
ØJS (os(Y,X) =
m, log m, (m, + 1) log(m; + 1)]
1=1
me log my
(m, + 1) log(m; + +1] das (Y, X).
The equality is achieved iff m, m,, Vi, which holds iff Ej Vj.. Since we have assumed E, ||cl|l O, the equality does not hold, thus o(Y X) o X). Therefore, have proved that Y a strict local minimum.
Finally, if Y satisfies that + m2 + +... + M. = and mg 2 2 for some k, then oY,(Y, > -2 log 2. Thus is sub-optimal striet local minimum. Q.E.D.
D TECHNICAL DETAILS OF SECTION 4.2 AND
D.1 PROOF OF CLAIM
4.2
Define function City (t) = 1 (1l):(t) - yソ (,)+), i.j.
dai (t) (y:= y₂ d(vi Uj)
dy.
dyj
(B/ vz)²²
dt
dt
dt
dt
(y: v¹) (
w
w
1 cwt ew mitb
e 4B
(w" - w w²'Ui) (1 1 ewo vi
= Ms
< 0.
S 0 for any a1, a1,02 E R. Note that the above computation, we skip the time index t. Therefore (ty(() is non-increasing along the trajectory, which implies [[v:(t) y₁ (f) < (1),(0) yo (0)],, Vt.
In the last step, we used the fact that (a: a2)
D.2 PROOF OF CLAIM 4.3
WGAN-GP with linear discriminators can be expressed as
min (PGAN-GP(Y;0) wERd
Σ
w Dr
" yi
X([w]| 1)2.
G (Y
min (= - d
w
ye
1=1
Consider the dynamies corresponding to the simultaneous gradient descent for WGAN-GP:
dw
OLD OLAGNN-GP dt dw
(at y/) 2Aw + 2w ||]]]
(13a)
1=1
dy:
O OLWGAN-GP W.
(13b)
dt Oys
17

---

Under review as a conference paper at ICLR 2020
Define function any (t) 21lba(t) y ( V.j.
doig (1)
(yi y5)² d(ii Uj)
(dy,
dyy
dys
(vi 0z)²
dt
dt
dt
dt
(yi yn) ST (w w.
O.
Thus (t):(t) (t(t)] will be a constant for all
E
TECHNICAL DETAILS OF SECTION E.S
E.
PROOF CLAIM 5.
Define function ony (t) 2 (1((vit) - v:)) (1)(1) x;)]1? i.j. Denote 6,(t) (t( Iz-
da:g(t)
(ò: 6,)² d(vi Uj)
dys
dyj
(d: 0,)²
dl
dl
di
dl
1 eue (w)) (6. 6,)²
w
w
1 + "00 (115 (35)
1 1+ cwo (w"' 0, wF
1
1
+ E
S 0.
The equality holds iff w = w 8j. i.e. w²'(0; 6,) = O.
E.2 PROOF CLAIM 5.2
Let u, w"( x;), ,,..., n, have
dV
r dw
dy dt
=
Σ(u (t xx))
(14a)
dt
dt
n
T
Σ (3): xx,)²
(14b)
1 + nn (z1-91)
1 1 e (y n.))
W (x) -11)
w" (3/s xii)
+
(14c)
el0 (xi-1))
+ e "":(v:- (z:)
1=1
Us
+
Σ
(14d)
1 4-
1 6
[=1
1=1
a
-
S
(14e)
1+ E
In the last step we used the fact that u(1 - e") 0, Vu E R. Note that in the above computation, we skip the time index t.
E.3 PROOF PROPOSITION
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 lim,- 8(t) e M, where M { (w, v)
0. E. xz
V.
18

---

Under review as a conference paper at ICLR 2020
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 differential equation du h(((()) if every solution to this equation starting in remains in A.
de
Lemma (Lasalle's 's invariance principle) Consider dynamical system defined by du h(u(t)), de where h a vector mapping. Assume h has continuous first partial derivatives and h(0) = 0. Let K Suppose there is scalar function V which has continuous first partial
be an invariant compact derivatives in K and is such that (p)) (VV(p), h(p)) 0, Vp K. Let E be the set of all Let M be the largest invariant set in E. Then for every solution I starting in K, u(I) + M as L - 20.
points p E K such that (p))
Our goal is to show that starting from any initial point 8(0) = (w(0), v(0)), the dynamics defined by (10), denoted as ((t) (w(t), v(t) will converge to the set
M {(w, v)
0, Σ
v1.
(15)
Define
K K= 1=101111 [0(0)]1²)
Since V < 0, we have |10(1)]2 < [0(0)] thus O(1) E K, vl. Thus K is an invariant compact set.
According to Claim 5.2 the set of points such that (p) 0
E A (w, y) : w (ye xx) = 0, ViJ.
According to the LaSalle's invariance principle, the algorithm will converge to the largest invariance subset of F. 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 = We show that when M defined in (15) is the largest invariant set in E. Assume the contrary, that there is set M & M C E such that M is an invariant set. Then starting from any point ((0) E\M we have 0(1) E M.
Since d = 1, then set E. becomes
E = (w,y) R1x(n+11, -w(J x;) 0, Vi].
Let E1 ((w,)) : w 0} and Esg [[w, y) y/: Ii, Vi). then E' Ei Es. The set M still
M = { (w. v) : w = 0, Σ Σ v1).
Since ((0) E E but not in M, and Fg S M, then we have 0(0) E Fg and ((0) & Eg. This implies w(O) = 0 and >, (z: (0))² + 0. According to the fact that (p)) 0, Vp E E and 0(t) E E, we have that
V(((t)) v(e(0)) Σ (z:(0) y. (0)) w0)² & 8.
(16)
Since the path 0(t) E M C E for all we have 0(t) E E₁ or E. Suppose J = { E :: 0(t) E Ez}. then for s E J have ((((s)) = wss)² + ws)) By (66. we have
wss)² =6 6, Vs.
Fort t & J. we have O(t) E Ej and thus w(t) = 0. Thus w(t) 0, Vt & J and w(t) 8, vs E J. As
w(t) is continuous for and w = 0, we must have = 0. This means w(t) = 0 for all t.
Recall the dynamics defined by 10 for the case d = 1 is
dw
OLD
y/ (m v4)
(17a)
dt
Ow
1=1
dy:
aLg
(17b)
dt
Oy:
+ c
-
19

---

Under review as a conference paper at ICLR 2020
Along the path (tt) E, we have (t)((tttt) zx(t)) 0, Vt, thus
dyc(!) dt + e0 = -, Ví,
which implies (t) = (0), Vi. This further implies dur(t) (t( - y1(ti] = E.)
dt
ye: (o)
80- Since ((0) E but not in M, thus must have x,) + >, (0),,, implying 60 + O. Thus dwr(t) 60 * O, which contradicts w(t) = 0, vt. This contradiction implies that the original assumption that there is a set M & . S E such that M an invariant set does not hold. Thus the largest invariant subset of E must be subset of M.
dt
Finally, if (() E M. then the gradients are zero, thus 0(t) E .,, Vt, which implies that M itself is invariant set. Thus M is indeed the largest invariant set of E.
E.4 PROOF OF CLAIM 53
We restate the claim below.
Claim E.1 When d 1, for the training dynamics of (10). at any point other than the desired solu- tion (y1...., with positive real part
(x) ,a) in the set of stationary solutions, the Jacobian has an eigenvalue
When d = 1. the dynamical system is given by
dw 0L
12
F2 yi
(18a)
dt
dw
dy:
a
w
(18b)
dt
By:
+ em((:=zz
We can write it as
0 h(0) (ho ... hn (0))
where hy is the right hand side of the i-th equation. The Jacobian J
4 satisfies the following:
Oho
(z. 32
Ju
Ow
+ [2,)
aho
c xx)
J1,5-1
+ w(x; Mi) (1 (w =2:) Vi I,...,7, n,,
ay:
Oh;
(
J141,1 dw
+ w(yt xz) + e" - mz =z
+ ("((y=-z:) x;)
Oh, w² w((-))))
J4115-1 =
Oy: (1 (
Jo 0, if j.j j and # j.
When evaluated at 0 = (0, ...., ynd. we have
(I: y1)²
J11
2
1=1
J1,++1
Vi = 1,...,n.
2'
1
J441,1 z' O,
J-1jt11
1
'The stability of typical equilibria of smooth ODEs is determined by the sign of real part of cigenvalues of the Jacobian matrix. It is unstahle if at least one eigenvalue has positive real part. See, e.g., Mexcheder (2018 for the discussions.
20

---

Under review as a conference paper at ICLR 2020
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.
It is easy to verify that J only has two non-zero eigenvalues
1 JI1 +
1 V-1.
112
2
V2
Therefore, when z; Y/, Vz,, the eigenvalues of the Jacobian have zero real part. When some * ys. then the two eigenvalues the Jacobian have a positive real part, meaning that this stationary point is not stable. This proves the result: in the of stationary solutions M {(w,y) 0, > I; = >; | any point other than the desired solution (U)...., Un) is not stable.
E.5 ANALYSIS OF CP-GAN DYNAMICS FOR CONVEX CASE
Next, we consider the training dynamics generalized CP-GAN for a convex discriminator.
In 9 we used a log-linear discriminator D(u) = log(1 + e (although we called it a "lin- ear discriminator" previously for simplicity). In this subsection, we show that the same analysis can be extended to a "coovex-linear" discriminator. The empirical version with the convex convex-linear discriminator presented below; it an extension of (
min L8P A
olw (y: -x;)),
@=wE
min == Uu jR
(Y;0) & o(w" (z+ y:)).
Consider the dynamies corresponding the simultaneous gradient descent for CP-GAN:
dw aLD Σ (z. - --:oo'' (u, zz)),
(19a)
dt dw
1=1
dy:
aLg wo' (w (w=((x: 1 v1))
(19b)
dt
dy:
We still consider the function
1 n
V
|
2
Σ i=1
|0 yill2.
According to the following result, is non-increasing along the trajectory of CP-GAN training with convex discriminators, thus is still global Lyapunov function for the dynamics 19)
Claim E.2 Suppose & is convex function.. Along the trajectory of the dynamics defined in Eq. 19
have (V 5 O.
21

---

Under review as a conference paper at ICLR 2020
Proof of Claim
E.2
Let u;
wy(y== =x), I...., have
dV
=
w
dw
Σ (yt xz)²
dyi
(20a)
di
dl
di
w
( - v: (w" (yi - -x,)) + Σ (ys - -x,) "'w'(w" (w" - yz))
(20b)
7
w² "((x: y²) (w" wu-((x xx:)) + Σ w² w"(pi xz)Ø (x; v.))
(20c)
uu) (u:) + ug (-us)
(20d)
1=1
Σ us|o'( (-w:) - d'(ui)] 50
(20e)
In the last step we used the fact that u(d' d'(w)) S 0, Vu E IR 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. It is not hard to extend the convergence results this case, and we skip the details.
F PROOF OF PROPOSITION 2 FOR n =
Without loss of generality, we can consider two points σ 0, The problem becomes
(Y) sup log 1+ exp(((((0) f()) log SEF2 2
1 exp(f(l) f(v2))
where F is the set of continuous functions with domain Rd. We compute all values of g CD (Y) as follows.
Case 1: The two generated points are the same as the true data points, i.e., {x1, = {81, {2).
y1 0, 1/2 = 1, then
CP (Y) =
[log 1/2 + log 1/2] = - log 2 x 0.6997.
2
y1 = 1, = 0, then
1
1
1
g (Y) sup
log
+ + log exp(f(1)
+ exp(f(() - f(1)
fef
1
sup EER
log
1 exp(t) + log + exp(-t)
2
log 2.
Case 2: Exactly one of the generated points coincides with the corresponding true data point, i.c.,
Hi: : y4 x.H. = 1. Without loss of generality, we can check the case yı = 0, y2 * 1. Then
9 CP( 2 sup log 1 + exp(((()) f(0)) 1
2 log 1 exx((((1 f(2))
sef 2
log2 + sup log
2
IER 2
I+ exp(t)
log 2 -..3466
The value is achieved when f()))f(y2) + - oo (or more precisely, there is a sequence functions such that the difference f(1) f(y2) goes minus infinity).
22

---

Under review as a conference paper at ICLR 2020
Case 3: Both generated points are different from the true data points, ie., Ift y: 2z 1. Then
1
1
1
1
9 PP) 2 sup log /EF 2
log
1+ exp(f(0) - f(vi))
2
exp(f(I) - f(u2))
1
1
1
sup &ER
log
1+
log
+ exp((2)
0.
The value is achieved when f(1) f(22) - 0o and f(0) f(122 + -00.
According to the above results, the only global minima are (y1, (2), addition, from
any Y, it is easy to verify that there is non-decreasing path from Y to global minimum.
G PROOF OF PROPOSITION 2 FOR GENERAL
Recall the function
1 log exp(f(v) - f(x))) - n
yYY sup f n
log (1 + exp(f(v:) - (x:)))).
Proposition 5 (restatement of Proposition Suppose 21, 22. In E R are distinct. The global minimal value of 9 CP (Y) is 1og which achieved iff {Ii,.... FnJ = (y1..... .n Further- more, the function gYY) has no sub-optimal basin.
The key of the proof is to compute the values of gYY for any Y. Roughly speaking, the value g(Y) can be computed by the following process:
(1) We can build graph with vertices representing distinct values in xis, s/8 and draw directed edges from v; to ye- This graph can decomposed into cycles and trees.
(2) Each vertex in a cycle contributes log 2 to the value g(Y).
(3) Each vertex in a tree contributes 0 to the value gYY).
Putting these ideas together, the value g(Y) equals 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 (yr, 1/,........ yn) (.i,...,,r, J. then Y is global minimum of g(Y). the second subsection, as another warm-up example, global minimum. In the third subsection, we prove Proposition 2 technical lemmas will be provided in the remaining subsections.
prove that if there exists some y/ & {xI,.... Jn then it is not
in three steps. The proofs some
G. WARM-UP EXAMPLE 1: ALL GENERATED POINTS MATCH THE TRUE POINTS
Prove that if {81. .e....,,... | = {z1.... }, then Y is a global minimum of g
Suppose Y4 Ta(t), then (0(1), o (2)) .)...................... (n)) is permutation of (1, (1.2...., nn.. We view as mapping from 21, ...,,.... n to 21, .......... m). Pick an arbitrary then in the infinite sequence (i), (i)),, (3) (1), ... there exists least numbers that are the same. Suppose ((ho) (Ko+ (T)+)) (i) for some ko, T, then since is one-to-one mapping have (i) Then obtain a cycle C (i, o (i) ... (T-)) (T))
We can divide
n} into the collection of finitely many cycles C₁, Cz,..., Cx. Each cycle C (cx(1), (2),..., .., c* (mz)) satisfies (j + 1) (cx())) 1,2, ...,. my where es (m +
23

---

Under review as a conference paper at ICLR 2020
1) is defined (1). Now calculate the value of g(Y).
n
g(Y)
sup
log
72
exp(f(u)) f(x,)))
K
inf
log (1+ cxp(f((s)) - f(x)))))
k=1iECs
K
me
inf
Σ
log (1 exp(f f
f 71
j=1
1
K
me
inf
log (1 exp(f( - f(Foa
R=
K
m&A -1
inf fom
log (1 + exp(ts+1 t,)) + log (1 + exp((1 tmx)))
ER
k=1
K
(11)
m& log(1 + exp(0))
1=1
log 2.
Here (i) is because 21, n1 is the combination of Ci...., and i E Cs means that cı (i) for some j. (ii) because C are disjoint and f can be any continuous function; more specifically, the values of f at x;'s 'ss for i in two different cycles CR J is independent of the choice of (fx i E Ckay if K # 22, thus we can take the infimum over each cycle (i.e. put "inf" inside the sum over k). (iii) is because mh log(1 + exp(15+1
independent, i.e., the choice of {f(z)) i
()) log (1 + exp(t1 - (m)) is convex function of &,, .,,,,,,,,,.. im and the minimum is achieved at f1 = t2 = ... tm 0.
G.2 WARM-UP EXAMPLE 2: NEW POINT GENERATED
Suppose yj (I1,...,,y Vj, and there exist some Zig that is not equal to any yj- this part, we compute the value g(Y) and show that is not a global minimum. The computation for this example will illustrate how a "free" variable reduces the objective value g by at least log 2. Later in the general proof, we will see that any vertex not in cycle will reduce the objective value by exactly - 2.
Consider the term log(1 + exp( ((r.))) Since Tio does not appear in any other term in E, log(1 exp(f();) (xx)))) the choice of fa is free. Therefore, no matter what values of f(x1)... (xio--)), fx f(x,) and f() ((,, are, we can always pick f f( ) so that (21.) f(x:o) + -0, making the term log(1 + exx((( f(r:,))) + O.
1
o(Y) = inf
log (1 cxp(f(v)) f(x)))))
f
i=1
1
inf
Σ
log + exp(f(())) - fxx)))) +0
f n1
i
2 n
log(1 + 1)
in
N2
log 2.
G.3 FORMAL PROOF OF PROPOSITION
This proof is divided into three steps. In Step 1, we compute the value of g(Y) if all y e (#). (Z1...., Fn). This is the major step of the whole proof. In Step compute the value of gYY)
24

---

Under review as a conference paper at ICLR 2020
for any Y. In Step 3. show that if Y is not global minimum, then there is a non-decreasing continuous path from Y to a global minimum.
G.3.1 STEP I: COMPUTE g(Y) THAT ALL yi (I1,..., Assume
yi ( , Vi.
(21)
We build directed graph G (V, A) as follows. The set of vertices V 21, represents I1, T2..... 2p. We draw a directed edge (i.j) E A y = Ty; in this case, there is a term log + exp(f(#,) f(x:))) in the expression of g Note that in this directed graph, it is possible to
have a self-loop (i, i), which corresponds to the case y; J;- Because of the assumption (2T). we simply express
9(V) = - inf
log (1 + exp(S(m)) - f(x))))
f n
1=1
(22)
-niff 1
Σ
log (1 + - f(x)))))
f n (iJ))A
Each Y/ correspond unique 2j,, thus the outdegree of denoted outdegree must be exactly 1; in other words, for each é there is exactly one directed edge going out from i. The indegree of each i, denoted as indegree can be any number in {0, n....
To proceed, we need 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 = (vo, 31, v1, e2...... 1m,1,, Em: Um) is sequence of vertices and edges such that E V for every i E {0, I...., ma and 64 is a directed edge from 1/-1 to G2 for every E {I...., m).. The set of vertices in W is denoted as (W),, and the set of edged in W is denoted as A(W). If vo U1...., Um are distinct we call it a directed path (or path), and we say the length of the path is m. If to, U1,..., 1m distinct and Um Uo, we call it directed cycle (or cycle).
.....,um
Note that we always say has path to itself u (with length 0), no matter whether there is an edge between v to itself or not. This because the degenerate walk W (()) 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 E V, the root, such that there exactly one path from to for each node v E V and there is no edge from the root to itself. The depth of 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 is a subgraph of G = (V, A) which is directed tree. The set of vertices in T is denoted as V(T), and the set of edged in denoted as A(T).
We prove 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 Suppose G = AV, is a directed graph and outdegree(1) = 1, Ve E V. Then we have the following:
.2.....Tyy TM such that each edge v E A appears either in exactly one of the cycles in exactly of the subtrees.
(a) There exist cycles C₁ C2...., .a....,Cs Cx and subtrees T2,.2....
(b) The root of each subtree um is a vertex of a certain cycle Ct where < k <
K. In addition, each vertex of the graph appears in exactly one of the following sets: (TT))uu)) ( (TTM) {ums)
(c) There is at least one cycle in the graph;
25

---

Under review as a conference paper at ICLR 2020
15
13
12
11
Yo
Example I for Lemma 2
(b) Example 2 for Lemma with self-loop
Example for Lemma 3
Figure 9: The first figure a connected component a graph. contains 10 vertices and 10 directed
edges. It can be decomposed into 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), 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 self-loop, and two trees attached to The third figure is example of Lemma
There is one vertice 9 with outdegree 0, which corresponds to ye and y7 since both 6 and 7 are connected to it. The fact that the two edges have the same head implies that ye V7-
With this lemma, ready to compute the value gYY). According Lemma 2 have
-ng(Y) inf
log (1 + (x)( f(x)))))
inf
log (1 + exp(((((()) -(x:))
Σ Σ
log (1 exp(fx(((()) f(xi))))
k= (EV(Ck)
m=1 (TV(TT))(Mn)
2 inf
Σ
(1 + (xxp(f((())) -f())(
A Jeye.
k=1iEV(Cw)
(23)
We then compute Jeye- Since Cg is cycle, have X₁ {.; : {yr Cz). Since the cycles C₁ s are disjoint, we have X X = 0, vk & meaning that the values ( [y: for i one cycle Cg are independent of the values corresponding to a different cycle C₁. Then the sum in the expression of Jeye can be decomposed according to different cycles.
K Σ k= (EV(CL)
Jeye = inf
log (1 + exp(s(v)) ((x))))))
inf (EV(C.)
log (1 exp( ((x))))
Similar to Step 1, show that the infimum for each cycle is achieved when the values f(x;) f(z,), Vi.j E V(C)). A more detailed proof is given as follows. Pick an arbitrary k. and suppose all the edges of Cs (u1, v2). (12, vz),-... (Ur-1, ur), (v,, v1), where [V(Ck)] is the number
26

---

Under review as a conference paper at ICLR 2020
of vertices in the cycle Ck. Denote Ur41 D1. Then
inf Σ
log (1 + exp((())))
(EV(CL)
inf
Σ
log
f(z,,
j=1
(24)
inf 4.
log (1 + exp(1 4))) + log (1 + exp((1 - 4)))
=r log 2 = [V(Ck) 2.
The infimum is achieved when ((x)) = =...= [(x,)) equivalently, f(x)) [(z)),
V(C)). Therefore,
Jeye = log 2 V(C+))
(25)
According to 23 and 25 have
ng(() 2 Σ logg)
(26)
Next, we prove that for any c > 0, there exists continuous function f such that
nY(()=
Σ
log2 +
(27)
Let N be a large positive number such that
n log (1 +xxp(-N)) <e.
(28)
Pick a continuous function f as follows.
0, f(x)) 1 N depth(i),
i UK V(Ck), i E U V(Tm).
(29)
Note that the root of tree Tm, is also in certain cycle C₁. thus the value f( ) is defined twice (9)). but in both definitions its value is O, thus the definition is valid. For any V (C²). ((zy)={(z))
suppose y; -y, then both i,j E VV(A)) which implies ([zx))((a)) i E V (T }. suppose = 2y. then by the definition the graph (i.j) is a directed edge of the tree Tm. which means that depth (i) depth(j)+ Thus f(y) (f,))f((z)) = f(x)))((x.) = NN
O. For any
In summary, for the choice of f in 29
we have
0,
EEU k V(Ck),
f(:)) - f(x;)
(30)
-N, ie UmE1 V(Tn).
27

---

Under review as a conference paper at ICLR 2020
For the choice of f in 29 we have
:f)(
log (1 exp(f())) -(;))
M
log (1 exp(f(y)) ff f(x)))))
Σ
log (1 + exp(f(u)) --((()))))))
(CV(
ieV (Tm Hum3
log (1 + exp(0)))
Σ
log (1 exp(-NN))
(CL
(TM)
K
log)) Σ ((V(mm)) log (1 +ex((-N1)
K
[V(C)) 2 in log (1 + exp(-NN))
log2
This proves 27
Combining 26 and 27 we have -ng(Y) = Ek=n [V(Ck) log equivalently,
K
1
g(Y)
V(C+)) log
n
G.3.2 STEP 2: COMPUTE gYY) FOR ANY Y
In the general case, not all yı 's lie in the set {I1....,
Denote the set
H {i y E {कt (o1....,,..) J.)) = ( Mj ,n.)) Since yj 's in He may be the same, we define the set of such distinct values of yj as
You (u Rd y Mj, for some j E HT)..
Let Puu Youil: then there are total + Nout distinct values in I1.... Tn, .1...... Yn- Without loss of generality, assume y1,..., -ng.u are distinct (this because the value of (Y) does not change we re-index I; is and yı is as long the subscripts of xi, Vi change together), then
You! {y),- Mnontt }.
We build directed graph G AV, as follows. The of vertices V {1, ... n, + 1,..., n Nout) represents T1, I2,..., and 91.... Unout For i, j < n, we draw directed edge (i,j) E if y; = .y; this case, there a term log(1 + cxp(f (x,f - (x:))) of gYY). For 1 < i < n and < I noutt we draw a directed edge (i, n j] E A if y, = yy; in this case, there term log(1 + exp(f(y;) -(()))) the expression of gY)). Note that this directed graph, it is possible to have self-loop (6, i), which corresponds to the case = 24.
(1.
the expression
This graph has the following property: for each i S n, the outdegree exactly 1; for each j S Aouts the outdegree of is O. Moreover, each vertex representing some has an incoming degree at least 1 (since otherwise this vertex will not be created); note that an vertex representing I; may have incoming degree O. We present lemma which is extension of the Lemma The proof is given in Appendix G.5
Lemma Suppose G = (V, is a directed graph and outdegree(v) & Vo E V. Then we have the following:
28

---

Under review as a conference paper at ICLR 2020
(a) There exist cycles C1, C2...., CK and subtrees Ti....... appears either in exactly one of the cycles or in exactly one of the subtrees.
"22...,TTr, TM such that each edge A
(b) Denote the root of subtree I'm Ums m L.. Then um is either vertex of certain cycle Cg where 1 S k S K, or a vertex with outdegree 0.
(c) Suppose u1....; MMo
in a certain cycle, and UMo+l..... uM have outdegree Then each vertex of the graph appears in exactly one of the following sets: ((C.),...,V(CCAA
V(TMo+1):.... (TTw).
Note that (b) is different from Lemma because under the assumption of that lemma that each vertex has an outgoing edge, the root of a tree cannot have outdegree O.
The computation of g(Y) is quite similar the previous case. We will highlight few small differ- ences. We still have
nY(()
inf
- ((())))((x;))
M
inf
E(S(W:) - f(x;)) +
Σ Σ
E(f(Us) f(x;)
(31)
k= (CL)
m=1 i (en((T))Veun
2 inf
log (1 exp(f(vs) s(x)))))
k= iEV(Ct)
Jeyo.
Same as before, we have Joye Ek [V(C))] log Once fix the values of f(z;) to be constant for i in cycles (which makes the first sum achieves the value ΣK V(Cx)) log 2), we can k=
always pick the values of on the vertices j in the trees so that f (x,) + co. Therefore, have
ng Peye
V(C+))
G.3.3 STEP 3: FINDING A NON-DECREASING PATH A GLOBAL MINIMUM
Finally, we prove that for any Y, there a non-decreasing continuous path from Y to one global minimum Y*. In other words, there is continuous function ý 0, Rdxn such that 17(0) Y, Y17(1) = Y and g(n(t)) is non-decreasing function with respect to E [0, 1]. In this proof, we will just describe the path in words, and skip the rigorous definition of the continuous function 7), since it should be clear from the context how to define 17.
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 Ý and a non- decreasing continuous path from Y to y such that g(V) - =(V) 2 1 n log 2.
For any Y that is not global minimum, we apply Claim G. 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 non-decreasing continuous path from Y to Y*. This finishes the proof of Proposition
G.4 PROOF OF LEMMA 2
We first prove a few observations. We will slightly extend the definition of "walk" to allow a walk with infinite length.
29

---

Under review as a conference paper at ICLR 2020
Observation 1: Suppose in directed graph G (V, A), any vertex has outdegree exactly 1. Starting from any vertex vn E V(G). there is a unique walk with infinite length
(wo) _ (No, e1, 11, 62, 02 Us C2 Us+1, Ci+1,...),
where e; an edge in A(G) with tail 8/-1 and head U/-
Proof of Observation 1: At each vertex Us. there is unique outgoing edge e; (v, 1(41) which uniquely defines the next vertex 2/+1- Continue the process, we have proved Observation 1.
Suppose in directed graph G (V, any vertex has outdegree exactly 1. Suppose the unique walk starting from vo is ((n)) _ (Vn, Et, U1, C2, 02...., U/, Ci Bet1, e1+1....), then the walk can be decomposed into two parts
Observation 2:
W1 (vo) = (Vo, 61, 01, C2 22,.... - 1, Cig vio);
(vn = (Vigs Cio+1, t1o+1, +2 + +2
where Wi(w)) a directed path from uo to Ui (i.e. the vertices Up, 01,...; Vig are distinct), and (20))) is the repetition of certain cycle (i.e. there exists T such that U+4T 0ú for any i 2 in). This decomposition is unique.
Proof of Observation 2: Since there only finitely many vertices in the graph, then some vertices must appear at least twice in (wo). Among all such vertices, suppose u is the one that appears the earliest in the walk W (vo), and the first two appearances are Vie u and 8/2 Denote T' = i io. Since there is a unique edge going out from any vertex, thus U must be the same as U+++1 Thus starting from = Vio. the walk (2(v)) will be repetitions of the cycle consisting of vertices Vig +ig+1. U1 -1, and we denote this cycle C.o.
and ig i1.
+1+, Continue the process, we have v; U14T for any > in-
If the vertices before V/ are not distinct, then there are at least two vertices ey where 0 S < l S in- This contradicts the definition of ig. Therefore, Wi (vo) a directed path from ti to thg
In Observation 2, for any uo E V. the "transition point" Vig in the infinite walk W(r)) is unique. We define the "firsttoouch-vertex" of og to Vig. The first-touch- vertex u = 0% has the following Ck for some k; (ii) there exists path from to (iii) any paths from e to any vertex in the cycle C₁ other than u must pass u. In other words, an ant starts from vo and crawls along the edges, the first vertex in a cycle that it touches is Since any to corresponds to unique W(o),, its first-touch- vertex must exist and unique. Note that if u is in some cycle, then its first-touch- point is u itself.
properties: (i)
As a corollary of Observation 2, there is at least one cycle in the graph. Suppose all cycles G C1, Cz..... Ck- Because the outdegree of each vertex is 1, these cycles must be disjoint, i.e., V(C,) (C,)) = and A(C,) n A(C,) = 0, for any i +
Define R to be the set of vertices of C Ci...., Cm with indegree at least two, i.e.,
R 2 {u: U Cj for some k and indegree(v) 2 2}.
Suppose the elements of R are ui...,, uM. We denote the set of vertices in the cycles
K
V. = U JVIC)u....vCC.
(32)
1=1
We describe the intuition behind the partitioning of G. Based on Observation 2, starting from any vertex outside of V. there is a unique path that reaches V.. Combining all vertices that reach the cycles at um. (denoted as V..), and the paths from these vertices to um. we obtain a directed subgraph Tm, which is connected with V. only via the vertex um- The subgraphs Tm are disjoint from each other since they connected with V. via different vertices. In addition, each vertex outside of V. 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 Ti,..., TM.
30

---

Under review as a conference paper at ICLR 2020
Next, we provide more formal definitions and proofs. For any m f1,2...., define
Vm {u E V(G): Um is the first-touch-vereex of v),
(33a)
Vm Vm Mumm)
(33b)
Am {e A(G) the tail of is in Vn
(33c)
Tm (Vm; Am) a subgraph of G.
(33d)
We first show that V1, V.,,.,, ,,,, VM and v(CI)...., V(Ck) form a partition of the edge of G,
i.e.
K V(G) = ( (
M
(34a)
m==
Vm ni== = 0, Vm, 8,,
(34b)
Vn M (VC)) 0, Vm, k.
(34c)
V(CL) D. vk
(34d)
For any vertex v & (U v(CK)). its first-touch-vertex w must be different from (otherwise would be in a certain cycle). Since is in a cycle, denoted as Cku there is directed edge with head wr in addition, since a first-oouch-vertex of v & Ck then there must be another edge with head w. Thus the indegree of w is at least 2, which means E R. Thus w um for some which must belong to Vn for some m, we have proved
implies v E Vn. Since any v & V(Ck)) 34a).
Since each vertex v has a unique firs-touch--vertex, thus a vertex cannot lie in two different sets Vm and V., which proves (34b). Assume (34ch does not hold, i.e., there exists some V(Ck) Vn for some k, m. Since the first-touch-vertex of v is itself, according to (33a) we have v uni but according to (33b) v Um & Vm, a contradiction. Thus (34c) holds. (34d) obvious.
Next, we show that the edge sets of Ti.... Tm and CI...., CK form partition of the edge set of G, i.c.
K A(G) U A(Cx))
U U ACCT.)
(35a)
k=1
A(Tm) AAT,)) 0, Vm,,, s,.
(35b)
A(Tm) n A(C)) = U. Vmn k.
(35c)
A(Cc) ACC)) = 0. VK +
(35d)
These relation be proved easily by and the definitions E A(G)) (U A(Ca)). we want to show that en lies in at least one Tm Suppose where vo. Vi E VG).. Since ei is not in a cycle, vp & Va. thus by (34)) we have vo E Vn for certain m. which further implies e E Am A(Tm by the the definitions (33c) and (33d). Thus we proved (35a). Any edge in A(Tm) has a tail u E VTTm). thus according to (34b) we know
33c and 33d
For any edge
(Vo, v1)
& V,, Vs & m. By the definition 33cb. we have e & Am A(Tm). which proves (35b). Similarly,
any edge e in A(C²) has a tail u (CC)). thus according to (34c) we know u E V Vm, 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 E 21, M). Tm is a subtree of with the root um- For any vertex vo in the subgraph Tm. consider the walk W(v)). Any path starting from to must be part of (wo). Starting from vo there is only one path from vo to um which is W1 (vo). according to Observation 2. Therefore, by the definition of directed tree, Tm is directed tree with the root Umm
G.5 PROOF OF LEMMA 3
We utilize the result of Lemma 2 to prove Lemma More specifically, we will reduce to the case of Lemma
31

---

Under review as a conference paper at ICLR 2020
We build new graph as follows. Denote the set of vertices in G that have outdegree Oa Do. For any vertice in Do. we add an edge from Do to itself (a self-loop), and obtain a new graph G (V, Now each vertice in G has outdegree exactly 1.
Each self-loop is a length-1 cycle, thus by adding edges to vertices in Do we have created |Dol length-1 cycles, denoted as CK+I...... ...........+tpp. CDo) Suppose all other cycles are C₁ C2...., Cx.
According to Lemma 1, there exist cycles C1, C2,..... CK. CK+I,-.., CK+IPal and subtrees A appears either in exactly one of the cycles in exactly one of the subtrees. (b) The root of each subtree um is a vertex of a certain cycle Cs where 1 1 k < K Doll In addition, each vertex of the graph appears in exactly one of the following VCC),, ((T)))uu),,... V(TM)) (war),
T1, T2.T2..... ................................ Tas such that: (a) Each edge
sets:
Now remove the edges added vertices in Do and restore the original graph. Then have removed the cycles I.+I...., Cx+ Dol and do not change other cycles and subtrees. We do change the relations between the trees and the eycles: previously, the root of each tree is vertex in certain cycle; now, since some cycles are removed, the roots of some trees will be a vertex with outdegree 0. Suppose these trees are Mo++1 T TMs.
After removing the edges added to vertices in Do. C₁, C2...., and subtrees Ti, T2...... T'M sat- isty the following: (a) Each edge
appears either in exactly one of the cycles or exactly one of the subtrees. (b) Denote the root of subtree Tm as Um- m = -...., ,M. Then um is either a vertex of a certain cycle C2 where 1 k S K, or a vertex with outdegree (c) Each vertex of the graph ap- pears in exactly one of the following sets: V (TMo+t1)...., MTTM).
V(Tar.) (umo)
G.6 PROOF OF CLAIM G.1
We first prove the case for d 2 2. Suppose the corresponding graph for Y is G. and G decomposed into the union of cycles Ci...., Cx and trees Ti,.... Tm. We perform the following operation: pick an arbitrary tree T. with the root un- We claim that there must be an edge e with the head umm If Mm > (i.e. Umm represents some yi), then there must be an incoming edge to umm thus the claim holds. um I n (i.e. um represents some I;), 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 tree Tm, must because um is a head of an edge.
Suppose is the tail of the edge Now remove the edge edge e' = V). The new edge corresponds to ye = Ty. The old edge (v, um)) corresponds to Yo Zum (and a term {(f(xum) term E(f(Uu..)) Vo Fun (if um n) or yv Vum-n (if um n) to U. = x.. Let ÿJ y for any *
(u, um) and create new
((x))) if um S yo Dum -n {.1,..., vn) (and fIx))) ) if um > n. This change corresponds to the change of yo: we change
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 = (u,e',v) v). In this new graph, the number of vertices in cycles increases by 1, thus the value of g increases by n log 2, i.e., g(Y) - -YY 1 n log 2.
Since d 2 2, we can find path in Rd from point to another point without passing any of the points in {#1,... ). In the continuous process of moving ye to f.. the function values will not change except at the end that V. x.. Thus there is non-increasing path from Y to Y, in the sense that along this path the function values of does not decrease.
The illustration of this proof is given as below.
32

---

Under review as a conference paper at ICLR 2020
Y6 Y/
(a) Original graph
(b) Modified graph, with improved function value
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 ys = 1/7. We change y/ to ØT = to obtain the figure on the right. Since one more cycle created, the function value increases by n log
For the case d = 1, the above proof does not work. The reason is that the path from to B. may touch other points in (.1...., Fn and thus may change the value of g. We only need to make small modification: we move Ve in IR until it touches a certain that corresponds to vertex in the tree T. at which point a cycle created, and the function value increases by at least 1 log 2. This path is 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.
33

---

Under review as a conference paper at ICLR 2020
6
4
7
7
4
0
2
8
9
4
6
5
(a)
(b)
(c)
(d)
(c)
Figure 11: Generated (a)MNIST (b) CIFAR-10 (c) CelebA (d) LSUN samples by CPGAN.
34


Reviews:
[{"review_id": "rygZ-NwDKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI recommend the paper be accepted because it provides a new formulation for training GANs that both demonstrates improved empirical performance while also allowing theoretically favorable properties (on spurious local minima and avoidance of mode collapse) that specifically do not hold for a standard GAN.\n\nThe primary question I am left with after reading the paper is: is there a probabilistic interpretation of the new loss function (equation 4a).  The authors justify this formulation because it allows analysis via Lyapunov functions, but it would be very useful to know if it itself is the maximum likelihood estimate under an alternate data model.  Such an explanation would improve the understandability of this method.\n\nMinor comment: \n\nThe fourth bullet point under the contributions section should specific the sense in which the new GAN \"performs better\"\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "SygX86JaYS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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:\nThe 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.\nIn 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?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJleOiRaFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors propose a  modification to the original GAN formulation, by coupling the generated samples and the true samples to avoid mode collapse.\n\nI have some concerns about the analysis and the experiments of the paper: Most of the analysis is tailored for a very simple linear discriminator case which for the WGAN means just matching the first moments. Even in this simple setup, they consider d=1 (the scalar case). I am not sure how one can generalize this analysis to a more realistic case. Also the experimental gains seem incremental which makes me worried about such generalization. Finally, there are a few works in the literature about understanding the optimization landscape of GANs. For a sample, see https://arxiv.org/abs/1706.04156 and https://arxiv.org/abs/1710.10793. The later uses a Lyp function to analysis the global convergence of a GAN.  Also there is a few papers about the mode collapse issue in GANs. See for example https://arxiv.org/abs/1712.04086\n ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is proposed a rejection based on majority reviews.
Decision: Reject