Title: DG-GAN: THE GAN WITH THE DUALITY GAP

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.

1. INTRODUCTION:

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

EQUATION

where p data is the true data distribution and p z 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.

2. RELATED WORK:

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.

3. 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.

Definition 3.1. (Game) A strategy game is a tuple < P, {S i } n i=1 , {u i } n i=1 >, where P = {p 1 , ..., p n } is the players sets, S i is the set of pure strategies for player i and u i is i's payoff real-valued function defined on the pure strategy profiles's set:

S = S 1 × ... × S n

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 < s 1 , ..., s i , ...s n >∈ S s.t. ∀ < s 1 , ..., s i , ..., s n >∈ S, we have u i (s 1 , ..., s i , ..., s n ) ≥ u i (s 1 , ..., s i , ..., s n ) 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 u

1 (s 1 , s 2 ) and u 2 (s 1 , s 2 ) s.t. u 1 (s 1 , s 2 ) + u 2 (s 1 , s 2 ) = 0 for any (s 1 , s 2 ) ∈ 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 u i (s 1 , s 2 ) = inf s1 sup s2 u i (s 1 , s 2 ) = v (2)

where the v is called the value of the zero-sum game.

The strategy (s 1 , s 2 ) ∈ 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 sup s2 u i ( s 1 , s 2 ) = v and the player 2's maximin strategy is s 2 such that inf s1 u(s 1 , s 2 ) = v. 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 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

EQUATION

The strategy

EQUATION

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 p data , and a Gaussian distribution p z , the duality gap of

EQUATION

Here the V (f, g) is the the function that GANs concentrate on:

EQUATION

3.2. DUALITY GAP AS A 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 = {f : R d → R|f ∈ F ⇔ 1 -f ∈ F}.

A convex function φ, a distribution p data , a Gaussian distribution p z and a generator g, then

EQUATION

So the F -distance can be written as

EQUATION

where V (f, g) has been defined in equation ( 4). Remark 3.1. F -distance is a distance between two distributions: p data and p g . For a special case when φ(x) = x and F = {f : R d → R|L f < ∞}, then the F -distance is Wasserstein-Distance, where L f 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 ∼ p z that is a given Gaussian distribution. Assuming {f :

EQUATION

Proof. Observe that

EQUATION

According the property of G,

EQUATION

where the second inequality comes from the property of F. Hence,

EQUATION

The theorem above shows that if the discriminator and generator have unbounded capacities, the F -distance can be a metric to discriminate the p g and p data 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 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 = {x 1 , ..., x n } where x i ∼ µ, then the empirical and the expected Rademacher Complexity are, respectively,

EQUATION

where the distribution of = ( 1 , ..., n ) satisfies that P ( i = 1) = P ( i = -1) = 1 2 .

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 DG,

EQUATION

where

EQUATION

and the x i are selected from observed data and the z i 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 B X and B Z , and the ∃L F , L G s.t. ∀f ∈ F and g ∈ G, the Lipschitz constant of f is less than L F , and the Lipschitz constant of g is less than L G . Then with probability at least 1 -3δ

EQUATION

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.,

EQUATION

where a i and b i are activation functions, M i and N i are matrices. Assume that the Lipschitz constants of a i and b i are less than 1. This is true for many popular activation functions such as ReLU.

We also assume ||M i || ≤ B i and ||N i || ≤ B i . Let d f and d g denote the widths of these two networks respectively. Lemma 4.1. For the empirical Rademacher Complexity given above,

R X (F) ≤ 4 n + 12B X H i=1 B i d 2 f Hlog(2 d f nHB X H i=1 B i ) √ n R Z (G) ≤ 4 m + 12B Z H i=1 B i d 2 g H log(2 d g mH B Z H i=1 B i ) √ m R g * (Z) (F) ≤ 4 m + 12B Z H i=1 B i d 2 f Hlog(2 d f mHB g * (Z) H i=1 B i ) √ 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 -DG|:

EQUATION

Based on ( 19), if the empirical duality gap DG(f * , g * ) ≤ , we can establish the population bound of the F -distance such that d F ,φ (p data , p g * ) ≤DG(f * , g * )

≤|DG(f * , g * ) -DG(f * , g * )| + DG(f * , g * ) ≤ 48ρ φ B Z H i=1 B i d 2 f Hlog(2 d f nHB Z H i=1 B i ) √ n + 12ρ φ L F B X log 2 δ 2n + o(n -1 2 ) + .

(20)

5. THE ALGORITHM:

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

EQUATION

)

Instead, our loss function is written as

EQUATION

)

where x = x + (1 -)x, ∼ U (0, 1), x ∼ p data , x = G(z), z ∼ p z . The details of the algorithm is given in Algorithm 1. 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 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 (Fré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 ∼ P data ; latent variable z ∼ P z ; 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 ω * = ω; 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.

4 for t = 1, ..., n critic do 5 for t = 1, ..., m do 6 x ← g θ (z) x ← x + (1 -) x L (i) ← f ω (x) -f ω (x) + λ ((||∇ xf ω (x)) || 2 -1) 2 7 end 8 ω ← Adam ∇ ω 1 m m i=1 L (i) , ω, α, β 1 , β 2 9 end 10 Sample a batch of latent variables z (i) m i=1 ∼ p z θ ← Adam ∇ θ 1 m m i=1 -f ω (g θ (z)) , θ, α, β 1 , β 2 ; 11 ω = ω * ; 12 Sample a batch of latent variables z (i) m i=1 ∼ p z θ ← Adam ∇ θ 1 m m i=1 -f ω (g θ (z)) , θ, α, β 1 , β 2 ; 13 for t = 1, ..., n critic do 14 for t = 1, ..., m do 15 L (i) ← f ω (x) -f ω (x) + λ ((||∇ xf ω (x)) || 2 -1) 2 16 end 17 ω ← Adam ∇ ω 1 m m i=1 L (i) , ω, α, β 1 , β 2 18 end 19 end

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.

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 Complexity.

proof.

EQUATION

EQUATION

Using McDiarmid's inequality, with probability at least 1 -δ

EQUATION

And use McDiarmid's inequality again, with probability at least 1 -

EQUATION

Here = ( 1 , 2 , ..., n ) and P ( i = 1) = P ( i = -1) = 0.5 So with probability at least 1 -

EQUATION

Similarly, with probability at least 1 -δ

EQUATION

So, we get the next inequality with probability at least 1 -3δ

EQUATION

A.2 THE PROOF OF LEMMA 4.1

The lemma 4.1 gives the bound of the Rademacher Complexity proof.

||f

EQUATION

Hence,

N (F, , || • || ∞ ) ≤ H i=1 N (M i , LB X H j=1,j =i B j , || • || 2 ) (32)

So, we have

EQUATION

According to the relationship between Rademacher Complexity and covering number, we get

R X (F) ≤ 4 n + 12B X H i=1 B i d 2 f Hlog(2 d f nHB X H i=1 B i ) √ n (34) Similarly, R Z (G) ≤ 4 m + 12B Z H i=1 B i d 2 g H log(2 d g mH B Z H i=1 B i ) √ m R g * (Z) (F) ≤ 4 m + 12B Z H i=1 B i d 2 f Hlog(2 d f mHB Z H i=1 B i ) √ m (35) B SUPPLEMENTARY EXPERIMENTS B.1 EXPERIMENTS ON OTHER DATASETS B.1.1 EXPERIMENTS ON MNIST

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

:



Figures and Tables:

Figure 1: Wasserstein Distance on CIFAR-10

Figure4shows the Wasserstein Distance on MNIST datasets and Figure5shows the image generated after 100K iterations by the generator on MNIST datasets.

Figure 4: Wasserstein Distance on MNIST

Figure 6: W-Distance on toy datasets

Figure 7: result on toy datasets

Figure 8: Inception score on CIFAR-10

Figure 9: results on CIFAR-10

Peer review (iclr2020):
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. The contribution of this paper is incremental due to the following reasons. 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. The proof of the upper bound is straightforward. 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. 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.