DG-GAN: the GAN with the duality gap
Authors: Cheng Peng
Hao Wang
Xiao Wang
Zhouwang Yang
Venue:  (2020)
Keywords: GAN
duality gap
metric
saddle point
game

Abstract: Generative Adversarial Networks (GANs) are powerful, but difficult to understand and train because  GANs is a min-max problem. This paper understand GANs with duality gap that comes from game theorem and show that duality gap can be a kind of metric to evolution the difference between the true data distribution and the distribution generated by generator with given condition. And train the networks using duality gap can get some better results. Furthermore, the paper calculates the generalization bound of duality gap to estimate the help design the neural networks and select the sample size.


Under review as a conference paper at ICLR 2020
DG-GAN: THE GAN WITH THE DUALITY GAP
Anonymous authors
Paper under double-blind review
ABSTRACT
Generative Adversarial Networks (GANs) are powerful framework for modeling complex and high dimensional data. The training of GANs is difficult because the optimization a min-max problem. This paper understands GANs from the perspective of duality gap and shows that the duality gap can be good metric to evolution the difference between the true data distribution and the distribution generated by generator. Training GANs using the duality gap can provide com- petitive results. Furthermore, we establish the generalization error bound the duality gap to help design the neural network architecture and select the sample size.
INTRODUCTION
In the past few years, Generative Adversarial Networks (GANs) (Goodfellow al., 2014) are im- pactful because it has shown lots of great results for many Al tasks, such as image generation, dialogue generation, and images inpainting (Abadi & G Andersen 2016; Goodfellow 2016 Ho & Ermon 2016). Differing from other unsupervised learning methods for model generation that con- centrate on the hard optimization of the measure of distribution fit such the maximum likelihood method, GANs, which are a kind of methods of implicit models (Mohamed & Lakshminarayanan 2017 Tran et al. 2017), can be seen as a game between two networks, the generator and the dis- criminator. Training GANs will improve the two networks' capability synchronously. Denote the discriminator as f and a generator as g. The objective of GANs is
inf sup ((J.g)
[+((+)))] E (6(1-(((=)))) a--ps
arepaata
where Pdata the true data distribution and p= is the standard Gaussian distribution. Here, the goal of f is to discriminate the difference between two distributions and the goal of is to generate a distribution with the Gaussian noise. Therefore the problem of GANs is a min-max problem. The minimization problem is to search for the optimal discriminator f that can distinguish two distributions as much as possible and the maximization problem is to find the optimal generator not find the difference. So the GAN is just like game between these
such that the discriminator two players. This is in general a challenging task to find the best solution because it may be not a concave-convex min-max optimization. This means that the objective, denoted by V(J,g) g)). may not be a convex function when fixing f and not a concave function when fixing
The first major problem of GANs is how measure the difference between the generated distribu- tion and the true data distribution. It means that there is no an unanimous metric to represent the difference between the true data distribution and the generated distribution (Borji 2018). Different metrics have achieved different performances on the different benchmark datasets, although many also difficult to know
ofate-of-the-art models can show similar results (Lucic et al.) 2017). whether the generated distribution is close to the true distribution, and this is often observed by hu- man eyes. Another problem the convergence of the training algorithm of GANs, especially the global convergence. It means that if the original generator and discriminator are random, it is diffi- cult to confirm that the generator and discriminator can converge to the ideal conclusion by training with given data. So the existed algorithms should be heuristic or it can get bad result even train the neural networks with lots of datasets. Although it can be proved that the generator and discriminator can converge to the local Nash equilibrium under some strong assumptions (Martin let al. 2017), many GAN algorithms can not converge globally (Gemp & Mahadeven 2019).
In this paper, our main contributions are:

---

Under review as a conference paper at ICLR 2020
We propose new metric of GANs and prove that the metric can be upper bound of the traditional metrics.
We establish a generalization error bound under the new metric and show that the empirical metric can be viewed the loss function for GANs.
We propose an new algorithm with the new metric which demonstrates better results than state-of-the art algorithms.
The remainder of this paper is organized as follows. In Section 2 some related work are reviewed. Section 3 gives the new metric named duality gap that can be seen as an upper bound of traditional metrics. In Section 4 we establish a generalization error bound under the new metric and show that the empirical duality gap can be viewed as the loss function for GANs. Section [3] and provide the new algorithm and some experimental results. Finally, we give our conclusions and future work.
RELATED WORK
The problem of the GANs' metric and convergence has been extensively explored over the past few decades, and substantial amount of work has been proposed in the categories of convergence and new metric. The duality gap has ever been suggested by [Grnarvva al. (2018). However, they only take the original GAN (Goodfellow et al. 2014) into consideration. Theis et al. (2015) has showed that even though the log-likelihood generative model and thus can be seen metric of GANs, it has severe limitations because it may generate some low quality models with a high likelihood. [Tolstikhin et al. (2017) proposed to use the probability mass of the real data "covered" by the model distribution as metrie. They used a kernel density estimation method to approximate the density of generated models' distribution and this metric is more interpretable than the likelihood, making it easier assess the difference in performance of the algorithms. One of the most famous metric of GANs is the inception score (IS) (Salimans al., 2016). which uses a pre- treitranned neural network (the Inception Net (Szegedy al., 2016) trained on the ImageNet (Deng et al.] 2009)) to capture the desirable properties of generated samples. It can measure the quality of the generated models and discriminability. There are some modifications of IS such as (Martin et al. 2017 Gurumurthy et al. 2017) and so on. Furthermore, Martin et al. (017) proposed Frechet Inception Distance(HiI) between two Gaussian distribution for evaluating the quality of these models. However, even though these kinds of metrics can get some good enough results on some samples, the Gaussian assumption is not always right and the FID can not work well with the non-labeled datasets.
the data can be seen as a loss function to train a
There are some other research concentrating on the metric to estimate the generated distribution. Such as Maximum Mean Diserepancy (MMD) (Gretton et al. 2012). which measures the dissim- ilarity between two probability distributions using samples drawn independently from each other. However, the MMD) method's computation complexity is the quadratic in the sample size, which is difficult to train. AAooa & Zhang (2017) proposed to use the birthday paradox test to evaluate GANs, this test approximates the support size of discrete distribution and can also be used to detect mode collapse in GANs. Generative Adversarial Metric(GAM) is proposed by Jiwoong Im et al. (0016), which means exchanging discriminators or generators of two GANs and then comparing the two GANs by engaging them in a battle against each other. Image Retrieval Performance (Wang et al., 2016) evaluates GANs with an image retrieval measure, the main idea of which is to examine the badly modeled images. There are some research that view the GANs as zero-sum game Grnarova et al. (2018) proposed the duality gap, but the paper only takes the log-likelihoon into consideration. Balduzzi et al. (018)) introduced the Hamiltonian mechanics in the games and designed an algo- rithm that can converge to the Nash Equilibrium faster, and this method has showed some desirable results if applying in GANs. Oliehook et al. (2017) studied GANs from the view of game theory and suggested an algorithm of training GANS to the Nash equilibrium. Grnarova et al. (2017) considered the Nash equilibrium for semi-shallow GAN architectures and other more complex architectures.
THE DUALITY GAP
In the section, we give the definition of the duality gap. Because the duality gap comes from game theory, we give some knowledge of game theory at first.
2

---

Under review as a conference paper at ICLR 2020
Definition 3.1. (Game) A strategy game is tuple P. P.(Si] {ui]i= >, where P (PI.....PP) } is the players sets, S: is the set of pure strategies for player and un is i's payoff real-valued function defined on the pure strategy profiles's set: == x.. Sn
The key of the game theory is the Nash Equilibrium, which is a strategy profile such that no player can change his payoff unilaterally.
Definition 3.2. (Nash Equilibrium) A Nash Equilibrium is strategy profile < $1, St...., S. DE S s.t. V < 81, 81,...,,,, 8.,,.. 8n >E S, we have u.(81,..., Si,..., 8n) ) 2 U, (81 (s1...... .1.,.... S,,,..,,,, 8n) for any player
In this paper, we only discuss GANs with only two players, the game mentioned below are two- players' game.
Definition 3.3. (Zero-sum game)A zero-sum game a game with the two payoff u1 ($1, $2)
and (2 52) s.f. i1 (81, + (2 52) for any ($1, 82)
For two-players' zero-sum game, its equilibria also is called saddle point, which has some impor- tant properties and has attracted lots attentions. Because the saddle point difficult to research, this leads the difficulty of the GANs' research. About the equilibria, we have the following theorem:
Theorem 3.1. In zero-sum game, we huve
supinf (3, 82) = inf su = 52
(2)
81 82
where the is called the value of the zero-sum game.
The strategy (81, 82) E S' is called the maximin strategy. For these two players, they have different maximin strategies. The player I's maximin strategy š1 such that sup,2 (s()),52) 52) v and the player 2's maximin strategy is 52 such that inf,, u(s1, 62) = u. Furthermore, if we combine the two maximin strategies of these two players, we can achieve an equilibrium.
3.1 THE DUALITY GAP OF GANS
The traditional machine learning problem be
optimization problem. The objective to be minimized is denoted by a loss function. However, because the GAN objective is a min- max problem, can be seen the zero-sum game, with the 2 players being the generator and the discriminator. We will introduce the duality gap metric, which can be used to estimate the ability of the generators and the discriminators, and the relationship of duality gap and the classical metric- F - dislance when the generator's s and discriminator's capacity are unbounded.
zero-sum game comes from game theory, consisting of players D(Discriminator and ((Generator) with their strategy-fields F and G. A function V F x g + R is the utilities of the 2 players. By selecting (f,g) F x G. the D's utility is +V and the G's utility is -V. The goal of the 2 players is to maximize the worst case utility, which is
sup in & inf sup V(f.). feF SEg
(3)
gEg fer
The strategy (f" F G is called (Pure) Equilibrium if it satisfies that
sup
V(,gg")) in (V(", jEF
(4)
gEg
According to the above discussion, the GANs' duality gap metric the pure strategy can be defined.
Definition 3.4. (Duality Gap of GANs) Given 2 strategy fields and G, strategy (J", (f*,g") E G, convex function o, true data distribution Pdatos and Gaussian distribution Ps. the duality gap of (f* .g'))))))))))))) is
DGG (""".")) = suup V in V gEg
(5)
feF
Here the V(f.9 () is the the function that GANs concentrate on:
V(f.g)
E [o(f())) + E [ f((())))
(6)
zmppaca
goops
3

---

Under review as a conference paper at ICLR 2020
3.2 DUALITY GAP AS METRIC
The traditional metric used in GANS is a kind of distance between two distribution, denoted by F distance.
Definition 3.5. (F distance) Given a function space F= R RIf E F FF). F). A convex,uucttonn Φ, distribution Pdata- a Gaussian distribution p= and generator 9. then
E [ - ([(1=f(x))) - 261 1 ()
d d Pa)
sup E
[o({()))]+
FEF Paata
So the distance can be written as
dpatta Pg)
sup (f.gg, fEF
where V(J.g) has been defined in equation (4).
Remark 3.1. F-distancs is distance between two distributions: Pdata and Pa. For special case when ((x) and F {S Rd R R < oo), then the JF dislance is Wasserstein--isttmeee. where L is the Lipschitz constant of f.
The next theorem shows that the duality gap can be an upper bound of F distance with the given condition.
Theorem 3.2. ffr any distribution p. 3g E G. s.t. g(z) ~ p where z ~ Pa that is a given Gaussian distribution. Assuming {f Rd + R < 20) C F. then
sup - fEF
V in
2
sup V(f.g") - -2x( - 2
(9)
gEG
JEF
Proof. Observe that
sup V(f.g") in Vf"", :9) V(f.g) -25( 1 + in V( ,g) $20(
(10)
fEF According the property of g,
feF
9Eg
inf .) V(f", ppppot
E (x)) + 6(1 s $201
(11)
g6g
where the second inequality comes from the property of F. Hence,
V(f.g") 201 V(f.g")rr= -2Ø( 1 = 0.
sup
(12)
fEF
The theorem above shows that if the diseriminator and generator have unbounded capacities, the F - distance can be a metric to discriminate the Py and pdata and the duality gap is an upper bound of the F distance.
4 THE GENERALIZATION ERROR BOUND ON THE DUALITY GAP
Considering the training of GANs with the new metric, we first establish the generalization error bound of the duality gap. The generalization error bound is the gap between the training error and the test еттоr. In general, the gap can be replaced by the empirical eтrоr and the population error when assuming the test datasets are infinite. The generalization error bound in general depends the sample size and the complexities of the function spaces of the discriminators and generators. So establishing the generalization error bound can guide the design of these two neural networks and select the sample size. The generalization error bound for vanilla GANs has been studied in the literature. For example, spectral weight normalization (Miyato et al. 2018) is used to establish a tight bound for GANs by (Jiang al. 2019).
The generalization error bound of the unsupervised learning is always related to the complexity of the function space. We use Rademacher complexity characterize the capacity of the function space. Because GANs have two function spaces and & and the duality gap is related to these two spaces, the complexities of F and are the keys establish the duality gap's generalization bound.
4

---

Under review as a conference paper at ICLR 2020
Definition 4.1. (Rademacher Complexity) Given function space F and random sample X (21,...,pp) where 24 ~ Hs then the empirical and the expected Rademacher Complexity are, re- spectively,
Rx El sup fEP
Σ (x(i),
Rn,(F)==
E (2 X~ya
(13)
where the distribution of (ci..., en) satisfies that P(+ = P(G, = =- -1
The generalization error bound of the duality gap concentrates the gap between the population duality gap denoted by DG and the empirical duality gap denoted by DG,
DG(F", sup Vffgg) - inf V .9), fEF
(14)
969
where
Σ +((())))
d01 f(g(z;))) (15)
V(s9)=
E [+((()))]+ E (011)((())) ProPa
znpps
n
and the 2; are selected from observed data and the 2, are sampled from a standard Gaussian distri- bution.
Theorem 4.1. If the true data sample X and the the bound is denoted by Bx and Bz, and the BLy, Lg s.t. of E F and E G. the Lipschitz constant is less than T.y, and the Lipschitz constant of g is less than Lng. Then with probability at least 36
sample Z are bounded and
DG - DDI <x + 2p Lo gx + 2p
log 2n
log 2
(16)
+12pgL=BX
12p0LFLoB21
2m
For GANs, the two players generator and discriminator approximated by deep neural networks, so the Rademacher Complexity is a function the two neural networks' parameter. Supposing f F and g E G. then the f and g can be written the form of composition of sequence of function, i.e.,
f = a (Ma (MM
(17)
g = by (NH (ox--(Nrrr((..b((M))))
where and by are activation functions, M, and N; are matrices. Assume that the Lipschitz con- stants of a; and b; less than This is true for many popular activation functions such ReLU. We also assume ||M, || < B, and ||N,|| I B Let d, and dy denote the widths of these two networks respectively.
Lemma 4.1. For the empirical Rademacher Complexity given above,
12Bx I Bi de
I B.)
Rx(F) <
H' 12Bz I Bly ds (2 dym Bz I1 B
4 R2(9)
(18)
m
m
12B₂ II Buy de Hl ddmHH II B.)
RS (2) 4 m
Vm
This above theorem shows that the empirical Rademacher Complexity's bound depends on these two neural networks' architectures, especially the width and the depth. When training GANs, generate a noise for every iteration, so we can claim that m > n. Combining these two theorems, obtain
5

---

Under review as a conference paper at ICLR 2020
Theorem 4.2.
Bx II. B.y H2 1 B,) DDG DDGDGG v
log 2n
+ +12p B
+ onnn -n
(19)
Based on (19), if the empirical duality gap DG S we can establish the population bound of the FF distancc such that
dr ((Pttta Pa-) <DG(S",")
DDGG(f - DG DG
48p Bz I1 Biy dz H2 dy II B:)
(20)
vn
log 2n
+ 12poLxBx|
+ o(n o(n
te.
5 THE ALGORITHM
According to the Sections and we know that the population duality gap is an upper bound of F-distance and the gap between population duality gap and empirical duality gap can be arbitrarily small. Our theories imply that the empirical duality gap can be used loss function for training GANs. Note that many classical algorithms use F-distance the loss function. We develop new algorithm using duality gap as the loss function. We focus on WGAN-GP, the loss function which is
dr (Pdata: pg-) + A
E 2NPS
(l -
(21)
Instead, our loss function is written as
DG (f" gg)
E AnP:
(1IV (f) 1)²]
(22)
where à = ex + (1 E) e (0, 1), x ~ Paatos 7 = G(z), ~ Ps. The details of the algorithm is given in Algorithm We call our method DG-GAN, the GAN with the duality gap.
6 NUMERICAL EXPERIMENTS
In order to test our method, We conduct experiments using the duality gap on some datasets such as toy dataset, MNIST, CIFAR-10, qnd GAN models such as WGAN and WGAN-GP. The experiment results show that there are significant practical benefits using our method over the traditional methods. There
Then compare method DG-GAN with classic
main benefits: (1)
DG-GAN provides good metric suggesting the generator's 's convergence and sample's e quality. (2) Our method using duality gap as loss function has faster rate of convergence.
We train DG-GANs on CIFAR-IO, and compare our method with WGANs. Specifically, we adopt 4-layer CNN the generator and a 3-layer CNN as the discriminator. In the following, À is 10. Number of discriminator iterators per generator iterators is 5. We run 20K iterations in all the experiments on CIFAR-10. 10. Figure [ shows the Wasserstein Distance on CIFAR-10 datasets training with algorithm [1 And for quantitative assessment of our generated examples, we use the inception score (Salimans et al.) (2016)). Figure 2 shows the Inception score on CIFAR-10 datasets and Figure shows the image generated after 20K iterations by the generator CIFAR-IO.
In addition to the inception scores of the two methods, we also calculate the FID (Fréchet Inception Distance) of them. For WGAN-GP, after 20K iteration's training, the FID between generated distri- bution and true distribution 54.4, however for DG-GAN, it is 45.6. These observations, based on IS and FID, show that DG-GAN can provide better quality of generated samples.

---

Under review as a conference paper at ICLR 2020
Algorithm 1: Learning parameters for BPR input:
sample real data æ Pdatai latent variable Pz; a random number e ~ U10, 1];
output:
Generator parameter 0:
initialize the generator parameter 0 and the discriminator parameter w and Adam
parametero 0.0001, 1, 0,8² 0.9;
while not convergence do
W" W: for / 1, Meritic do
for l.... m do
④ + (2) 2 + er + (1-
L0 fm (ī) - fw (I) ((IVV (f)) ll2 1)²
end
Adam (V Σ - [ w. a, B1, (2)
end
Sample batch of latent variables {0(1) mm
10
i=1 ~ Pz
0 - Adam (Ve 1 tM Em - (g0 (,),,,,a,31,,8) 32):
11
www;;
Sample batch of latent variables {=(0)) 1 ~ ~2
- Adam (Vo 1 m Din fw (go (z)), 31, 32): for / 1,.., Meritic do
13
for 1 1= 1. ...., m do
I for (x) fo (x) + ((IVV (8)) 1l2 1)²
16
end
+- Adam (Va E TW,,,, ar, 31,
18
end
19
end

---

Under review as a conference paper at ICLR 2020
Figure 1: Wasserstein Distance on CIFAR-I 10
Figure 2: Inception Score on CIFAR-10
(a) step 10000
(b) step 20000
Figure 3: result on CIFAR-10
7 CONCLUSION
In this paper, we introduce new metric for GANs, which can bound the traditional metric under several assumptions. We establish the generalization error bound of the new metric to help design the neural networks and select the sample size. We call this new framework DG-GAN, We compare the performance between DG-GANs and other classical GANs on benchmark datasets and DG-GAN has demonstrated competitive performance.
There are several future research directions. The first is to extend DG-GANs to autoencoder GANs, where we have addition encoder network to learn the meaningful encoding. The second is to develop a formal hypothesis testing procedure to test whether the generated sample and the observed sample have the same distribution.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martín Abadi and David G Andersen. Learning to protect communications with adversarial neural cryptography. arXiv preprint arXiv:1610.069/8 2016.
Sanjeev Arora and Yi Zhang. Do gans actually learn the distribution? an empirical study. arXiv preprint arXiv: /706: 0777706082244 2017.
David Balduzzi, Sébastien Racaniére, James Maetens, Karl Jakob, Foerster Tuyls, and Graepel Thore. The mechanics of n-player differentiable games. arXiv preprint arXiv:1802.05644 2018.
Ali Borji. Pros and cons of gan evaluation measures. arXiv preprint arXiv:1802.0344, 2018.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale
hierarchical image database. CVPR, pp. 248-255, 2009.
Feizi, C Suh, Xia, and D Tes. Understanding gans: the lqg setting, 2018.
Ian Gemp and Sridhar Mahadeven. Global convergence to the cquilibrium of gans using variational inequalities. arXiv preprint arXiv:1808.00 01531,, 2019.
lan Goodfellow. Generative adversarial networks. arXiv preprint arXiv: 2016.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirzal, Bing Xu, David Warde-Farley, Shejil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances neural infor- mation processing systems, pp. 2672-2680, 2014.
Arthur Gretton, Karsten M Borgwardt, Malte Rasch. Berhhard Scholköpf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, pp. 723-773, (13)Mar 2012.
P Grnarova, K Y Levy, A Lucchi, T Hofmann, and A Krause. An online learning approach to generative adversarial networks. CoRR, Vol abs/1706.03269, 2017.
Paulina Grnarova, Kfir Y Levy, Aurelien Lucchi, Nathanael Perradudin, Thomas Hofmann, and Andreas Krause. Evaluating gans via duality gap. arXiv preprint 1811.v8811.0555 2018.
Swaminathan Gurumurthy, Ravi Kiran Sarvadevabhatla, and R Venkatesh Babu. Deligan: Genera- tive adversarial networks for diverse and limited data. CVPR, pp. 4941 4949, 2017.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in Neural Information Processing Systems, pp. 4565-4573, 2016.
Haoming Jiang, Zhehui Chen, Minshuo Chen, and Tuo Zhao. On computation and genralization of generative adversarial networks under spectral control. International Conference on Learning Representation, 2019.
Daniel Jiwoong Im, Chris Dongjoo Kim, Hui Jiang, and Roland Memisevic. Generating images with recurrent adversarial networks. arXiv preprint 1602v:1602.05/1 10, 2016.
Mario Lucic, Karol Kurach, Marcin Michalski, Sylvain Gelly, and Olivier Bousquet. Are gans created equal? a large-scale study. arXiv preprint arXiv:1711.10337 2017.
Heusel Martin, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Hochreiter. Gans trained by two time-scale update rule converge to local nash equilibrium. In Advances in Neural Information Processing Systems, pp. 6626-6637, 2017.
Taker Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral nornalization for generative adversarial networks. arXiv preprint arXiv:1802.05957, 2018.
Shakir Mohamed and Balaji Lakshminarayanan. Learning in implicit generative models. NIPS Workshop on Adversarial Training. 2017.
Olichock, R Savani, Gallego, van der Pol, and R Gross. Beyond local nash equilibria for adversarial networks. ArXiv e-prints, 2018

---

Under review as a conference paper at ICLR 2020
F A Olichock, R Savani, Gallego-Posada E Van der Pol, D De Jong, and R Gros. Gangs: Generative adversarial network games. arXiv preprint arXiv:1712.00679.,222 2017.
Tim Salimans, Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. In Advances in Neural Information Processing Systems, pp. 2234-2224422 2016.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zhigniew Wojna. Rethink- ing the inception architecture for computer vision. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2818-2826, 2016.
Lucas Theis, Aäron van den Oord, and Matthias Bethge. note on the evaluation of generative models. arXiv preprint 1rXiv:1511.01880 2015., 2015.
Ilya O Tolstikhin, Sylvain Gelly, Olivier Bousquet, Carl-Johann Simon-Gabriel, and Bernhard Scholköpf. Adagan: Boosting generative models. In Advances in Neural Information Processing Systems, pp. 5430-5439, 2017.
Dustin Tran, Rajesh Ranganath, and David M Blei. Deep and hierarchical implicit model. arXiv preprint 1wt.::102..8888088 2017.
Yaxing Wang, Lichao Zhang, and Joost de Weijer. Ensembles of generative adversarial net- works. arXiv preprint 112.9916 2016.
A
THE PROOF OF THEOREMS
A.1 THE PROOF OF THEOREM 4.1
The theorem 4.1 gives the generalization error bound of the duality gap with the Rademacher Com- plexity.
proof.
sup JEF
V(Jg") Vn -9)
(sup V(Jg") 1 in Mnf ,9)) JEF
DEG
DEG
< sup V(f.g") sup fer
(ffgg)) + in (f .9)
V(f gEG
FEF
gEG
(spp
[p({(x)))
()(()))))
(23)
|EF expata
+( E [Ø - (x))) 2ep
E [Ø(1 - f(g*(x)))))
xnp;
+(sup F. 1Ø(1 f f'((())))
E 10(1 f* ((z)))))
gEg x>pp
supe
Let X {21, 22 Nnh, X' =
In] and Ps |
sup E [o([()))
E [
/eFarpietu
arndaat
sup E [o(f(x)))
E [o(f()))]
JeF prepaate
zmp datn
(24)
1 <= sup (o({(z))) ((((==))))(((()))) < Pá L Bx n1
n feF
Using McDiarmid's inequality, with probability at least
sup F. [o(f(x))]
E.
[o(f(x))
JEF prppaaoo
z~PPata
(25)
log
< E sup [o((()))
[o(f()))]] x
Pdata JeF prepaate
2n
10

---

Under review as a conference paper at ICLR 2020
And use McDiarmid's inequality again, with probability at least
E(sup E PaFaaaaaaa
[o([())]] [+(f())]]
araaata
E sup
(O(((()))
Ni FEF
log %
22 El sup
Σ
(x(((())) 2ps sup 1f(x)) - m(x))| V
11 fET
f
2n
(26)
10g 2
2pp E sup 1I /EF
cx())))) + +2p sup If(xz) f(x/))) f
2n
log
Rx + 4p [Bx
2n
Here = (e1, c,,... ..., Gn) and P(e, = P(g: -1) = 0.5
So with probability at least 1 5
sup E [o(f()))] J
[o(f()))
(27)
10g3
+
2n
Similarly, with probability at least 1
sup E [0 (((())) xmpp
E [Ø(1 (*(()))
SE9 a~p:
log
22p LzRx(9) + 6ps LILgBr
2m
(28)
sup E. [0(1 f(gg (z)))
F.
10 f(gg(())) (z)))
xeps
x~p:
log 2
S2pp Lg (F) + 6p Bz
2m
So, we get the next inequality with probability at least 1 - -6
DDG DGI S xxx + 2ps LoR + 2ps L=
logg 2n
log3
(29)
+12ps LyBx\
+ 12ps Ls Lg Bz
2m
A.2 THE PROOF OF LEMMA
The lemma 4.1 gives the bound of the Rademacher Complexity
11

---

Under review as a conference paper at ICLR 2020
proof.
11f())-
<
<|
II
(M (z))...) |Mill2 (1.
-l- (M (z)) )..)1
...
>> Bx II
|M
Milk s Σ Bx
II !=
B.IMM Milla
j=1,f
(30)
For M {M E mmxn || S B.}. its' covering number N(M, ll 112) satisfy
N(M, 112) = (1+ min( (m, vn)B, mm
(31)
Hence,
NFF (1. S II N
LBx I[ Bj -111112)
(32)
So, we have
N(F,e, ,1 (1++ Hd II B₁ Big
(33)
According to the relationship between Rademacher Complexity and covering number, we get
12Bx II, B & (2 II B.)
Rx) -
(34)
Similarly,
12Bz II B. de d (2 / dm Bz II B))
4
R₂ <
+
m
mm
(35)
12Bz II Bu de de
(2 2 d II B:)
4 +
(2)
m
B SUPPLEMENTARY EXPERIMENTS
B.1 EXPERIMENTS OTHER DATASETS
B.1.1 EXPERIMENTS ON MNIST
We train the GANs using duality gap corresponding WGAN-GP on MNIST. And compare our method with the traditional methods WGAN-GP. Specifically, we adopt a 3-layers CNN as the generator and a 3-layer CNN as the discriminator.In the subsection, À 10. Number of discriminator iterators per generator iterators is 5. We take 100K iterations in all the experiments on MNIST datasets.
Figure shows the Wasserstein Distance on MNIST datasets and Figure 5 shows the image generated after 100K iterations by the generator MNIST datasets.
12

---

Under review as a conference paper at ICLR 2020
22-
20000
40000
00000
80000
10000G
leaois
Figure 4: Wasserstein Distance on MNIST
4
5
3
3
4
9
7 7
0
3
3
0
6
4
0
9
5
6
3
6
3
5
0
5
5
6
1 7
4
4
5
0
4
3
9
2
0
9
0
9
8
0
6
5
4
4
3
4
7
5
4
7
5 8
3
6
3
5
7
5
6
50
0
4
7
2
53
5
9
4
4
9
33030
9
7
5
4
9
2
4
2 9
3 7 2
77
4
4
7
1
(
7
4
/ 3
5
8
7
03
2 4 7
0
(a) step 20000
(b) step 40000
step 60000
5
8
8
7
2
0
2
7
4 2
4
2 0
2
6
2
8
/
5
9
5
9
7
9
6
7
0 /
4
7
4
O
3
89
8
2
6
2
0
/
9
I
7
8
5
3
H 7 5 0 4 3
$
7
8
$50
6
6 2 6
3
4
3
8
4
8
7 5
6 8
0
8
6
4
0
6
0
5
4
2
0 7
3
(d) step 80000
(e) step 100000
Figure 5: result MNIST datasets
B.1.2 EXPERIMENTS ON TOY DATASETS
We train the the GANs using duality gap corresponding to WGAN-GP on three toy datasets with increasing difficulty: (I) RING: mixture of Gaussians, (2) GRID: mixture of 25 Gaussians, (3)Swissroll. And compare our method with the traditional methods WGAN. Specifically, we adopt a 4-yarsrs ReLU- with 512 hidden units the generator and 4- ReLU- with 512 hidden units as the discriminator. In the subsection, À is 0.1. Number of discriminator iterators per generator iterators is We take 100K iterations in all the experiments on RING, 200K iterations on GRID and 200K iterations on Swissroll.
Figure 6 shows the Wasserstein Distance on the above three toy datasets and Figure 7 shows the image generated by the generator on the above three toy datasets. In the three figures, the yellow points represents the true data and the green points represent the generated data.
13

---

Under review as a conference paper at ICLR 2020
2000 J00ONLOOO
0000 DOOOOOOOOOO
(a) W-Distance on RING
(b) W-Distance on GRID
(c) W-Distance on Swissroll
Figure 6: W-Distance toy datasets
(a) result on ring
(b) result on grid
(c) result on swissroll
Figure 7: result on toy datasets
B.2 TRAINING GANS USING DG CORRESPONDING TO OTHER GANS
Because for every traditional GANs which train GANs by minimizing F-distance, we can find duality gap corresponding to it. Thus, except the experiments section 5 where the loss function is the duality gap corresponding WGAN-GP, we also take WGAN, in consideration. For WGAN, we adopt 4-layers CNN as the generator and a 3-layer CNN as the discriminator and the dataset is CIFAR-10.
We take 10K iterations in the experiments CIFAR-10 and compare their inception scores and generated models. Figure & shows the inception score of WGAN and our method and Figure 9 shows their generated models:
14

---

Under review as a conference paper at ICLR 2020
weceoon Sooee
Figure 8: Inception score on CIFAR-10
WGAN's generated images
(b) DG-GAN's generated images
Figure 9: results CIFAR-10
15


Reviews:
[{"review_id": "Hyx014dhFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "I vote to reject the paper at this stage, mainly because of the following three points:\n\n1) The motivation is unclear and overall structure of the paper is confusing. It should be better motivated why one should use the duality gap as an upper bound for the \"F-distance\". Minimizing the F-distance as is usually done seems like the more direct and simple approach. Since the results are far from state of the art, a clean and neat presentation of the theoretical advantages and contributions is crucial. \n\n2) The presentation is not professional, hard to follow and the submission overall looks very rushed:\n- In equations, please use \\inf, \\sup, and \\text{...} for text such as distance, data, ... \n- I have trouble understanding the overall idea behind Algorithm 1 and Eq. (22). What is the definition of f^* and g^* in Eq. (22)? Some explanatory text would be valuable.\n- The set F in Definition 3.5 looks odd, as it appears to be recursive and might not be unique.  \n- The writing looks very rushed, and should be improved. For example, I have trouble understanding the sentence \"So the existed algorithms should be heuristic or it can get a bad result even we train the neural networks with lots of datasets.\" in the introduction. \n- The aspect ratio in Fig. 5 should be fixed.\n\n3) The experiments are completely preliminary and not reasonable:\n- The WGAN-GP baseline is very weak, i.e. does not show any reasonable generated images (Fig. 9). There are countless open pytorch implementations on GitHub which out-of-the-box produce much better results. \n- The shown inception scores are far from state-of-the-art. It is unclear, why one should use the proposed duality gap GAN.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or 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": "HygHUcfK_r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "This paper has problems with clarity/polish and experimental design that are sufficiently severe\nto merit rejection by themselves.\n\nRegarding clarity/polish:\nI am generally not super picky about these things, but there does have to be some standard.\nThis paper looks very hastily put together, especially pages 7 and 8.\nThere are many typos and unclear statements.\nJust a few examples:\n\n> Generative Adversarial Networks (GANs) are powerful framework for (in the abstract)\n> be a good metric to evolution the difference (in the abstract)\n> In the past few years, Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) are impactful because it has shown lots of great results for many AI tasks, (first sentence)\n\n> It means that there is no an unanimous metric to represent the difference between the true data distribution and the generated distribution\nWhat does this mean? People have mostly settled on using FID for this.\n \n> It is also difficult to know whether the generated distribution is close to the true distribution, and this is often observed by human eyes.\nIsn't this just restating the point made in the first sentence?\nRegardless, nobody really uses human evaluation anymore - so this is just not correct.\n\n>  It means that if the original generator and discriminator are random, it is difficult to confirm that the generator and discriminator can converge to the ideal conclusion by training with given data.\nBut this paper doesn't propose a way to solve that problem, so it's strange to mention this here in this way.\n\n\nThese issues would maybe be excusable if not for the totally inadequate experimental validation.\nA non-exhaustive list of methodological problems with the (single) experiment:\n\n1. The experiment uses a single run each of the baseline and DG-GAN, when it's well-known that GAN training runs\nhave inter-run variance larger than the difference in score reported in Fig 1 and 2.\n\n2. The models have not been trained for long enough.\n\n3. The architecture of the neural networks used for the Generator and Discriminator is very non-standard, which\nprobably leads to:\n\n4. The scores achieved by the baseline are very far from state of the art, making the comparison mostly useless,\nand rendering the third claim from the introduction (\"We propose an new algorithm with the new metric which demonstrates better results than state-of-the-art algorithms.\") completely untrue.\n\nIn light of these other issues, I haven't checked the proofs.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or 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": "Bye3SqyGcH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "This paper proposed to use the duality gap sup_f V(f, g*) – inf_g V(f*, g) as a metric for GAN training. It proves that this metric is an upper bound of F-distance. It also proves a generalization bound for this metric. Simulation resultson MNIST, CIFAR10, etc. are reported.\n\n  The contribution of this paper is incremental due to the following reasons.\n\n 1) The duality gap is only an upper bound of the F-distance. This means that if the duality gap is zero then the learned distribution is the true distribution. However, the converse is not necessarily true: even if the algorithm starts with the true distribution, the duality gap may not be zero. Thus the metric is not a proper metric.\n  The proof of the upper bound is straightforward.\n\n  2) Another issue is the gap between the min-max formulation and the real training algorithm. As for GAN, due to the inexact update, it is not really solving the min-max problem. For the proposed metric, it is also impossible to solve sup_f V(f, g*) and inf_g V(f*, g) to reasonable accuracy. Thus what the algorithm is really doing, perhaps, is to optimizing a new loss which is the sum of the original loss and and an extra term. Viewing it as a “duality gap” seems to be far from the practical training. This discrepancy exists for GANs, but it is a bigger issue for the duality gap interpretation. \n\n  3) The simulation is not convincing. The reported FID for CIFAR10 using WGAN-GP is 54.4, which seems to be a bit high. I’m not sure whether it is due to parameter choice or due to weak D/G networks used in the simulation. If the paper cannot compare various architecture, it is more convincing to at least use some standard architecture, like DCGAN. Or at least report the parameter tuning effort made for getting the results. ", "extra_scores": {"experience_assessment": "I have published one or two 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": {}}]

Author rebuttal:

Meta-review: This paper proposes looking at the duality gap to measure performance. However, the metric is just an upperbound on the true metric of interest, and therefore its value can be ambiguous. 

The reviewers found the paper to be in an unacceptable form and was clearly hastily prepared. They were also skeptical about the novelty of the result as well as the comprehensiveness of the experiments.

This paper would require extensive revisions before any potential acceptance. Reject   
Decision: Reject