Year: 2019

Abstract:
Generative Adversarial Networks (GANs) are powerful framework for modeling complex and high dimensional data. The training of GANs is difficult because the optimization is a min-max problem. This paper understands GANs from the perspective of duality gap and shows that the duality gap can be a 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 competitive results. Furthermore, we establish the generalization error bound of the duality gap to help design the neural network architecture and select the sample size.

heading: 1 INTRODUCTION
text: 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, 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 concentrate on the hard optimization of the measure of distribution fit such as 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 discriminator. 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 g sup f V (f, g) = E x∼pdata [φ(f(x))] + E x∼pz [φ(1− f(g(x)))], (1)
where pdata is the true data distribution and pz is the standard Gaussian distribution. Here, the goal of f is to discriminate the difference between two distributions and the goal of g 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 g such that the discriminator can not find the difference. So the GAN is just like a game between these 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 (f, g), may not be a convex function when fixing f and not a concave function when fixing g.
The first major problem of GANs is how to measure the difference between the generated distribution 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 state-of-the-art models can show similar results (Lucic et al., 2017). It is also difficult to know whether the generated distribution is close to the true distribution, and this is often observed by human eyes. Another problem is 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 difficult 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 a bad result even we 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 et al., 2017), many GAN algorithms can not converge globally (Gemp & Mahadeven, 2019),
In this paper, our main contributions are:
• We propose a new metric of GANs and prove that the metric can be an 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 as 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 5 and 6 provide the new algorithm and some experimental results. Finally, we give our conclusions and future work.

heading: 2 RELATED WORK
text: The problem of the GANs’ metric and convergence has been extensively explored over the past few decades, and a substantial amount of work has been proposed in the categories of convergence and new metric. The duality gap has ever been suggested by Grnarova et 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 of the data can be seen as a loss function to train a generative model and thus can be seen as a 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 a metric. 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 to assess the difference in performance of the algorithms. One of the most famous metric of GANs is the inception score (IS) (Salimans et al., 2016), which uses a pre-trained neural network (the Inception Net (Szegedy et 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. (2017) proposed Frechet Inception Distance(FID) 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.
There are some other research concentrating on the metric to estimate the generated distribution. Such as Maximum Mean Discrepancy (MMD) (Gretton et al., 2012), which measures the dissimilarity 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. Arora & Zhang (2017) proposed to use the birthday paradox test to evaluate GANs, this test approximates the support size of a discrete distribution and can also be used to detect mode collapse in GANs. Generative Adversarial Metric(GAM) is proposed by Jiwoong Im et al. (2016), 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 a zero-sum game.Grnarova et al. (2018) proposed the duality gap, but the paper only takes the log-likelihood into consideration. Balduzzi et al. (2018) introduced the Hamiltonian mechanics in the games and designed an algorithm that can converge to the Nash Equilibrium faster, and this method has showed some desirable results if applying in GANs. Oliehoek 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.

heading: 3 THE DUALITY GAP
text: 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.
Definition 3.1. (Game) A strategy game is a tuple < P, {Si}ni=1, {ui}ni=1 >, where P = {p1, ..., pn} is the players sets, Si is the set of pure strategies for player i and ui is i’s payoff real-valued function defined on the pure strategy profiles’s set: S = S1 × ...× 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 a strategy profile< s1, ..., si, ...sn >∈ S s.t. ∀ < s1, ..., s′i, ..., sn >∈ S, we have ui(s1, ..., si, ..., sn) ≥ ui(s1, ..., s′i, ..., sn) for any player i.
In this paper, we only discuss GANs with only two players, the game mentioned below are twoplayers’ game.
Definition 3.3. (Zero-sum game)A zero-sum game is a game with the two payoff functions u1(s1, s2) and u2(s1, s2) s.t. u1(s1, s2) + u2(s1, s2) = 0 for any (s1, s2) ∈ S
For a two-players’ zero-sum game, its equilibria also is called saddle point, which has some important properties and has attracted lots of attentions. Because the saddle point is difficult to research, this leads the difficulty of the GANs’ research. About the equilibria, we have the following theorem:
Theorem 3.1. In a zero-sum game, we have
sup s2 inf s1 ui(s1, s2) = inf s1 sup s2 ui(s1, s2) = v (2)
where the v is called the value of the zero-sum game.
The strategy (s1, s2) ∈ S is called the maximin strategy. For these two players, they have different maximin strategies. The player 1’s maximin strategy is ŝ1 such that sups2 ui(ŝ1, s2) = v and the player 2’s maximin strategy is ŝ2 such that infs1 u(s1, ŝ2) = v. Furthermore, if we combine the two maximin strategies of these two players, we can achieve an equilibrium.

heading: 3.1 THE DUALITY GAP OF GANS
text: The traditional machine learning problem can be seen as an optimization problem. The objective to be minimized is denoted by a loss function. However, because the GAN objective is a minmax problem, it can be seen as 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 − distance when the generator’s and discriminator’s capacity are unbounded. A zero-sum game comes from game theory, consisting of 2 players D(Discriminator) and G(Generator) with their strategy-fields F and G. A function V : F × G → R is the utilities of the 2 players. By selecting (f, g) ∈ F × 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 f∈F inf g∈G V (f, g) & inf g∈G sup f∈F V (f, g). (3)
The strategy (f∗, g∗) ∈ F × G is called (Pure) Equilibrium if it satisfies that
sup f∈F V (f, g∗) = inf g∈G V (f∗, g). (4)
According to the above discussion, the GANs’ duality gap metric of the pure strategy can be defined.
Definition 3.4. (Duality Gap of GANs) Given 2 strategy fields F and G, strategy (f∗, g∗) ∈ F ×G, a convex function φ, a true data distribution pdata, and a Gaussian distribution pz , the duality gap of (f∗, g∗) is
DG(f∗, g∗) := sup f∈F V (f, g∗)− inf g∈G V (f∗, g) (5)
Here the V (f, g) is the the function that GANs concentrate on:
V (f, g) = E x∼pdata [φ(f(x))] + E x∼pz
[φ(1− f(g(x)))] (6)

heading: 3.2 DUALITY GAP AS A METRIC
text: 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 = {f : Rd → R|f ∈ F ⇔ 1− f ∈ F}. A convex function φ, a distribution pdata, a Gaussian distribution pz and a generator g, then
dF,φ(pdata, pg) = sup f∈F E x∼pdata [φ(f(x))] + E x∼pg [φ(1− f(x))]− 2φ(1 2 ). (7)
So the F − distance can be written as dF,φ(pdata, pg) = sup
f∈F V (f, g), (8)
where V (f, g) has been defined in equation (4). Remark 3.1. F−distance is a distance between two distributions: pdata and pg . For a special case when φ(x) = x and F = {f : Rd → R|Lf <∞}, then the F − distance is Wasserstein-Distance, where Lf 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. If for any distribution p, ∃g ∈ G, s.t. g(z) ∼ p where z ∼ pz that is a given Gaussian distribution. Assuming {f : Rd → R|Lf <∞} ⊂ F , then
sup f∈F V (f, g∗)− inf g∈G V (f∗, g) ≥ sup f∈F V (f, g∗)− 2φ(1 2 ) ≥ 0 (9)
Proof. Observe that
sup f∈F V (f, g∗)− inf g∈G V (f∗, g) ≥ sup f∈F V (f, g∗)− 2φ(1 2 )⇔ inf g∈G V (f∗, g) ≤ 2φ(1 2 ). (10)
According the property of G,
inf g∈G V (f∗, g) ≤ V (f∗, g)|pg=pdata = E x∼pdata [φ(f∗(x)) + φ(1− f∗(x))] ≤ 2φ(1 2 ), (11)
where the second inequality comes from the property of F . Hence,
sup f∈F V (f, g∗)− 2φ(1 2 ) ≥ V (f, g∗)|f= 12 − 2φ( 1 2 ) = 0. (12)
The theorem above shows that if the discriminator and generator have unbounded capacities, the F −distance can be a metric to discriminate the pg and pdata and the duality gap is an upper bound of the F − distance.

heading: 4 THE GENERALIZATION ERROR BOUND ON THE DUALITY GAP
text: 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 error. In general, the gap can be replaced by the empirical error 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 et al., 2019).
The generalization error bound of the unsupervised learning is always related to the complexity of the function space. We use Rademacher complexity to characterize the capacity of the function space. Because GANs have two function spaces F and G and the duality gap is related to these two spaces, the complexities of F and G are the keys to establish the duality gap’s generalization bound.
Definition 4.1. (Rademacher Complexity) Given a function space F and a random sample X = {x1, ..., xn} where xi ∼ µ, then the empirical and the expected Rademacher Complexity are, respectively,
R̂X(F) = E [sup f∈F
1
n n∑ i=1 if(xi)], R̂n,µ(F) = E X∼µn [R̂X(F)], (13)
where the distribution of = ( 1, ..., n) satisfies that P ( i = 1) = P ( i = −1) = 12 .
The generalization error bound of the duality gap concentrates on the gap between the population duality gap denoted by DG and the empirical duality gap denoted by D̂G,
D̂G(f∗, g∗) = sup f∈F V̂ (f, g∗)− inf g∈G V̂ (f∗, g), (14)
where
V̂ (f, g) = E x∼p̂data [φ(f(x))]+ E z∼p̂z [φ(1−f(g(z)))] = n∑ i=1 φ(f(xi)) n + m∑ i=1 φ(1− f(g(zi))) m , (15)
and the xi are selected from observed data and the zi are sampled from a standard Gaussian distribution.
Theorem 4.1. If the true data sample X and the Gaussian-distribution sample Z are bounded and the bound is denoted by BX and BZ , and the ∃LF , LG s.t. ∀f ∈ F and g ∈ G, the Lipschitz constant of f is less than LF , and the Lipschitz constant of g is less than LG . Then with probability at least 1− 3δ
|DG− D̂G| ≤4ρφR̂X(F) + 2ρφLGR̂g∗(Z)(F) + 2ρφLFR̂Z(G)
+12ρφLFBX √ log 2δ 2n + 12ρφLFLGBZ √ log 2δ 2m . (16)
For GANs, the two players generator and discriminator are approximated by deep neural networks, so the Rademacher Complexity is a function of the two neural networks’ parameter. Supposing f ∈ F and g ∈ G, then the f and g can be written as the form of a composition of a sequence of function, i.e.,
f = aH(MH(aH−1(MH−1(...a1(M1(·))...)))), g = bH′(NH′(bH′−1(NH′−1(...b1(N1(·))...)))),
(17)
where ai and bi are activation functions, Mi and Ni are matrices. Assume that the Lipschitz constants of ai and bi are less than 1. This is true for many popular activation functions such as ReLU. We also assume ||Mi|| ≤ Bi and ||Ni|| ≤ B′i . Let df and dg denote the widths of these two networks respectively.
Lemma 4.1. For the empirical Rademacher Complexity given above,
R̂X(F) ≤ 4
n +
12BX ∏H i=1Bi √ d2fHlog(2 √ dfnHBX ∏H i=1Bi)√
n
R̂Z(G) ≤ 4
m +
12BZ ∏H′ i=1B ′ i √ d2gH ′log(2 √ dgmH ′BZ ∏H′ i=1B
′ i)√
m
R̂g∗(Z)(F) ≤ 4
m +
12BZ ∏H i=1Bi √ d2fHlog(2 √ dfmHBg∗(Z) ∏H i=1Bi)√
m
(18)
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, we generate a noise for every iteration, so we can claim that m n. Combining these two theorems, we obtain
Theorem 4.2.
|DG− D̂G| ≤ 48ρφBZ
∏H i=1Bi √ d2fHlog(2 √ dfnHBZ ∏H i=1Bi)√
n +12ρφLFBX √ log 2δ 2n + o(n− 1 2 ).
(19)
Based on (19), if the empirical duality gap D̂G(f∗, g∗) ≤ , we can establish the population bound of the F − distance such that
dF,φ(pdata, pg∗) ≤DG(f∗, g∗)
≤|DG(f∗, g∗)− D̂G(f∗, g∗)|+ D̂G(f∗, g∗)
≤ 48ρφBZ
∏H i=1Bi √ d2fHlog(2 √ dfnHBZ ∏H i=1Bi)√
n
+ 12ρφLFBX √ log 2δ 2n + o(n− 1 2 ) + .
(20)

heading: 5 THE ALGORITHM
text: According to the Sections 3 and 4, 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 as a loss function for training GANs. Note that many classical algorithms use F-distance as the loss function. We develop a new algorithm using duality gap as the loss function. We focus on WGAN-GP, the loss function of which is
dF,φ (pdata, pg∗) + λ E x̂∼Px̂
[ (||∇x̂f (x̂) ||2 − 1)2 ] . (21)
Instead, our loss function is written as
DG (f∗, g∗) + λ E x̂∼Px̂
[ (||∇x̂f (x̂) ||2 − 1)2 ] (22)
where x̂ = x+ (1− )x̃, ∼ U(0, 1), x ∼ pdata, x̃ = G(z), z ∼ pz . The details of the algorithm is given in Algorithm 1. We call our method DG-GAN, the GAN with the duality gap.

heading: 6 NUMERICAL EXPERIMENTS
text: In order to test our method, We conduct experiments using the duality gap on some datasets such as a toy dataset, MNIST, CIFAR-10, qnd so on. Then we compare our method DG-GAN with classic GAN models such as WGAN and WGAN-GP. The experiment results show that there are significant practical benefits to using our method over the traditional methods. There are two main benefits: (1) DG-GAN provides a good metric suggesting the generator‘s convergence and sample’s quality. (2) Our method using duality gap as loss function has faster rate of convergence.
We train DG-GANs on CIFAR-10, and compare our method with WGANs. Specifically, we adopt a 4-layer CNN as 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. Figure 1 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 3 shows the image generated after 20K iterations by the generator on CIFAR-10.
In addition to the inception scores of the two methods, we also calculate the FID (Fréchet Inception Distance) of them. For WGAN-GP, after 20K iteration’s training, the FID between generated distribution and true distribution is 54.4, however for DG-GAN, it is 45.6. These observations, based on IS and FID, show that DG-GAN can provide a better quality of generated samples.
Algorithm 1: Learning parameters for BPR input :
sample real data x ∼ Pdata; latent variable z ∼ Pz; a random number ∼ U [0, 1];
output: Generator parameter θ;
1 initialize the generator parameter θ and the discriminator parameter ω and Adam parameterα = 0.0001,β1 = 0,β2 = 0.9; 2 while θ not convergence do 3 ω∗ = ω; 4 for t = 1, ..., ncritic do 5 for t = 1, ...,m do 6 x̃← gθ (z) x̂← x+ (1− ) x̃ L(i) ← fω (x̃)− fω (x) + λ ((||∇x̂fω (x̂)) ||2 − 1)2 7 end 8 ω ← Adam ( ∇ω 1m ∑m i=1 L (i), ω, α, β1, β2 )
9 end 10 Sample a batch of latent variables { z(i) }m i=1 ∼ pz
θ ← Adam ( ∇θ 1m ∑m i=1−fω (gθ (z)) , θ, α, β1, β2 ) ;
11 ω = ω∗; 12 Sample a batch of latent variables { z(i) }m i=1 ∼ pz
θ ← Adam ( ∇θ 1m ∑m i=1−fω (gθ (z)) , θ, α, β1, β2 ) ;
13 for t = 1, ..., ncritic do 14 for t = 1, ...,m do 15 L(i) ← fω (x̃)− fω (x) + λ ((||∇x̂fω (x̂)) ||2 − 1)2 16 end 17 ω ← Adam ( ∇ω 1m ∑m i=1 L (i), ω, α, β1, β2 )

heading: 18 end
text: 19 end

heading: 7 CONCLUSION
text: In this paper, we introduce a 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 an 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.

heading: A THE PROOF OF THEOREMS

heading: A.1 THE PROOF OF THEOREM 4.1
text: The theorem 4.1 gives the generalization error bound of the duality gap with the Rademacher Complexity.
proof. | sup f∈F V (f, g∗)− inf g∈G V (f∗, g)− (sup f∈F V̂ (f, g∗)− inf g∈G V̂ (f∗, g))|
≤| sup f∈F V (f, g∗)− sup f∈F V̂ (f, g∗)|+ | inf g∈G V̂ (f∗, g)− inf g∈G V (f∗, g)|
≤2(sup f∈F E x∼pdata [φ(f(x))]− E x∼p̂data [φ(f(x))])
+(sup f∈F E x∼pz [φ(1− f(g∗(x)))]− E x∼p̂z [φ(1− f(g∗(x)))])
+(sup g∈G E x∼pz [φ(1− f∗(g(x)))]− E x∼p̂z [φ(1− f∗((x)))])
(23)
Let X = {x1, x2, ..., xi, ..., xn}, X ′ = {x1, x2, ..., x′i, ...xn} and ρφ = ||φ||Lip
| sup f∈F E x∼pdata [φ(f(x))]− E x∼p̂data [φ(f(x))]−
− sup f∈F E x∼pdata [φ(f(x))]− E x∼p̂′data [φ(f(x))]|
≤ 1 n sup f∈F |φ(f(xi))− φ(f(x′i))| ≤ 2 ρφ n LFBX
(24)
Using McDiarmid’s inequality, with probability at least 1− δ2 sup f∈F E x∼pdata [φ(f(x))]− E x∼p̂data [φ(f(x))]
≤ E p̂data [sup f∈F E x∼pdata [φ(f(x))]− E x∼p̂data [φ(f(x))]] + 2ρφLFBX √ log 2δ 2n
(25)
And use McDiarmid’s inequality again, with probability at least 1− δ2
E[sup f∈F E x∼pdata [φ(f(x))]− E x∼p̂data [φ(f(x))]]
≤2 E xi∼pdata,
[ 1
n sup f∈F n∑ i=1 iφ(f(xi))]
≤2E [ 1
n sup f∈F n∑ i=1 iφ(f(xi))] + 2ρφ sup f,xi,x′i |f(xi)− f(x′i)| √ log 2δ 2n
≤2ρφE [ 1
n sup f∈F n∑ i=1 if(xi)] + 2ρφ sup f,xi,x′i |f(xi)− f(x′i)| √ log 2δ 2n
=2ρφR̂X(F) + 4ρφLFBX √ log 2δ 2n
(26)
Here = ( 1, 2, ..., n) and P ( i = 1) = P ( i = −1) = 0.5 So with probability at least 1− δ
sup f∈F E x∼pdata [φ(f(x))]− E x∼p̂data [φ(f(x))]
≤2ρφR̂X(F) + 6ρφLFBX √ log 2δ 2n
(27)
Similarly, with probability at least 1− δ
sup g∈G E x∼pz [φ(1− f∗(g(x)))]− E x∼p̂z [φ(1− f∗(g(x)))]
≤2ρφ · LFR̂Z(G) + 6ρφ · LFLGBZ √ log 2δ 2m
sup f∈F E x∼pz [φ(1− f(g∗(x)))]− E x∼p̂z [φ(1− f(g∗(x)))]
≤2ρφ · LGR̂Z(F) + 6ρφLFLGBZ √ log 2δ 2m
(28)
So, we get the next inequality with probability at least 1− 3δ
|DG− D̂G| ≤ 4ρφR̂X(F) + 2ρφ · LGR̂Z(F) + 2ρφ · LFR̂Z(G)
+12ρφ · LFBX √ log 2δ 2n + 12ρφ · LF · LGBZ √ log 2δ 2m
(29)

heading: A.2 THE PROOF OF LEMMA 4.1
text: The lemma 4.1 gives the bound of the Rademacher Complexity
proof.
||f(x)− f ′(x)||∞ ≤||aH(MH(aH−1(MH−1(...a1(M1(x))...))))− aH(M ′H(aH−1(M ′H−1(...a1(M ′1(x))...))))||2 ≤||aH(MH(aH−1(MH−1(...a1(M1(x))...))))− aL(M ′H(aH−1(MH−1(...a1(M1(x))...))))||2 +||aH(M ′H(aH−1(MH−1(...a1(M1(x))...))))− aH(M ′H(aH−1(M ′H−1(...a1(M ′1(x))...))))||2
≤||MH −M ′H ||2BX H−1∏ i=1 ||Mi||2 + ||M ′H ||2||aH−1(...a1(M1(x))...)− aL−1(...a1(M ′1(x))...)||2
≤ · · · ≤ H∑ i=1 BX H∏ j=1,j 6=i ||Mj ||2||Mi −M ′i ||2 ≤ H∑ i=1 BX · H∏ j=1,j 6=i Bi||Mi −M ′i ||2
(30) ForM = {M ∈ Rm×n : ||M ||2 ≤ Bi}, its’ covering number N (M, , || · ||2) satisfy
N (M, , || · ||2) ≤ (1 + min(
√ m, √ n)Bi
)mn (31)
Hence,
N (F , , || · ||∞) ≤ H∏ i=1 N (Mi, LBX ∏H j=1,j 6=iBj , || · ||2) (32)
So, we have
N (F , , || · ||∞) ≤ (1 + √ dfHBX ∏H i=1Bi )d 2 fH (33)
According to the relationship between Rademacher Complexity and covering number, we get
R̂X(F) ≤ 4
n +
12BX ∏H i=1Bi √ d2fHlog(2 √ dfnHBX ∏H i=1Bi)√
n (34)

heading: Similarly,
text: R̂Z(G) ≤ 4
m +
12BZ ∏H′ i=1B ′ i √ d2gH ′log(2 √ dgmH ′BZ ∏H′ i=1B
′ i)√
m
R̂g∗(Z)(F) ≤ 4
m +
12BZ ∏H i=1Bi √ d2fHlog(2 √ dfmHBZ ∏H i=1Bi)√
m
(35)

heading: B SUPPLEMENTARY EXPERIMENTS

heading: B.1 EXPERIMENTS ON OTHER DATASETS

heading: B.1.1 EXPERIMENTS ON MNIST
text: We train the GANs using duality gap corresponding to 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, λ is 10. Number of discriminator iterators per generator iterators is 5. We take 100K iterations in all the experiments on MNIST datasets.
Figure 4 shows the Wasserstein Distance on MNIST datasets and Figure 5 shows the image generated after 100K iterations by the generator on MNIST datasets.

heading: B.1.2 EXPERIMENTS ON TOY DATASETS
text: We train the the GANs using duality gap corresponding to WGAN-GP on three toy datasets with increasing difficulty: (1) RING: a mixture of 8 Gaussians, (2) GRID: a mixture of 25 Gaussians, (3)Swissroll. And compare our method with the traditional methods WGAN. Specifically, we adopt a 4-layers ReLU- with 512 hidden units as the generator and a 4-layer ReLU- with 512 hidden units as the discriminator. In the subsection, λ is 0.1. Number of discriminator iterators per generator iterators is 5. 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.

heading: B.2 TRAINING GANS USING DG CORRESPONDING TO OTHER GANS
text: Because for every traditional GANs which train GANs by minimizing F-distance, we can find a duality gap corresponding to it. Thus, except the experiments in section 5, where the loss function is the duality gap corresponding to WGAN-GP, we also take WGAN, in consideration. For WGAN, we adopt a 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 on CIFAR-10 and compare their inception scores and generated models. Figure 8 shows the inception score of WGAN and our method and Figure 9 shows their generated models:

Review summaries:
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.