Title: A UNIFORM GENERALIZATION BOUND FOR GENERA-TIVE ADVERSARIAL NETWORKS

Abstract: This paper focuses on the theoretical investigation of unsupervised generalization theory of generative adversarial networks (GANs). We first formulate a more reasonable definition of general error and generalization bounds for GANs. On top of that, we establish a bound for generalization error with a fixed generator in a general weight normalization context. Then, we obtain a width-independent bound by applying p,q and spectral norm weight normalization. To better understand the unsupervised model, GANs, we establish the generalization bound, which uniformly holds with respect to the choice of generators. Hence, we can explain how the complexity of discriminators and generators contribute to generalization error. For p,q and spectral weight normalization, we provide explicit guidance on how to design parameters to train robust generators. Our numerical simulations also verify that our generalization bound is reasonable.

1. INTRODUCTION:

The generative adversarial network (GAN) (Goodfellow et al., 2014) is one of most powerful generative models for modeling complex high-dimensional tasks, such as image generation, dialogue generation, and image impainting. Many variants of GANs (Ho & Ermon, 2016; Abadi & Andersen, 2016; Goodfellow et al., 2014; Li et al., 2017; Yu et al., 2018) have also been introduced to reinforce the stability of training processes to obtain more realistic models.

A GAN consists of two neural networks: a discriminator and a generator. Literally, the generator generates simulated data, while the discriminator tries to discriminate between simulated data and real data. The training process of GANs is tantamount to a two-player game between a generator and a discriminator. The main goal is to obtain a good generator, which is able to successfully approximate the distribution of real data. We denote the distribution of real data and the generatorinduced distribution by D real and D g , respectively. Our goal is to find a generator such that D real = D g . We revise the goal as d(D real , D g ) = 0, with a distribution distance d(•, •). The Jensen-Shannon (JS) divergence is implicitly used in Vanillar GANs (Goodfellow et al., 2014) , and the 1-Wasserstein distance is employed in WGANs (Arjovsky et al., 2017) . Empirical experiments suggest that the Wasserstein distance is a more sensible measure for differentiating probability measures supported in low-dimensional manifolds.

The generalization properties of GANs are less explored in the literature, and some exceptions are these works (Jiang et al., 2019; Arora et al., 2017; Bartlett et al., 2017; Zhang et al., 2017) . Motivated by the supervised learning context, where we say training to be generalized if the gap between the training loss and the test loss is small, we can define the generalization for GANs in a similar way. Concretely, generalization for GANs means that, the population distance between D real and D g is closed to the empirical distance between the empirical distributions of D real and D g . Hence, we define the gap between the population and empirical distance as the generalization error. Though our ultimate goal is to minimize the former distance, the latter one is what we minimize in practice. Given that our training process provides a small distance between empirical distributions, a small generalization error indicates that the population distance is also small. In other words, a small generalization error guarantees that the generated distribution is close to the real data distribution.

In fact, the training process of GANs is sample-dependent. In other words, the generator depends on the training data sets, which are random samples from D real . The training process minimizes d( Dreal , D g ), where Dreal denotes the empirical distribution over samples. The deviation between Dreal and D real leads to the generalization error, i.e., the gap between d(D real , D g ) and d( Dreal , D g ). This motivates us to establish a bound for generalization error, that is, the generalization bound. A tight generalization bound guarantees that the generalization error is small. The highlights and main contributions of this article are summarized as follows:

• We formulate new definitions for both generalization error and generalization bound, which are more reasonable than the definitions in previous work (Arora et al., 2017; Jiang et al., 2019) . • We establish the generalization error bound in a general version, with a fixed generator. By applying p,q weight normalization, we obtain a tighter bound. • We establish the generalization error bound, which uniformly holds over any choice of generator. Hence, we can explain how the complexity of the generator class and discriminator class contribute to the generalization error.

• Numerical experiments on Gaussian Mixture models verify that the theory of generalization error bound is consistent with the numerical performance.

1.1 RELATED WORK Some previous works provide theoretical investigations of the generalization of GANs. Arora et al. (2017) introduces a new metric for distributions called F-distance, and defines the generalization for GANs based on this distance. On top of that, the paper shows that generalization does happen with a moderate number of training examples (i.e., when the generator wins, the two distributions must be close in F-distance). However, they analyze the generalization with a fixed generator. Hence, the result is not guaranteed to hold uniformly across all generators. In this paper, we establish generalization error bounds for both scenarios. When a generator is fixed, we provide a tighter bound for generalization error than that in Arora et al. (2017) . k/m) with 1/p * 1, d 1 d, which is tighter than those from previous works. Moreover, we provide a more general version of the bound for generalization error with a fixed generator, and the result in Jiang et al. (2019) is a special case under the spectral weight normalization. To the best of our knowledge, we are the first to establish a generalization bound for GANs that holds uniformly across all generators.

2. PRELIMINARIES:

We first introduce the formulation of the generalization bound for GANs. We use D real for the real data distribution over R d0 , and N d (0, I) for a d-dimensional standard Gaussian distribution. We define the sample set as S {x i } m i=1 , where {x i } m i=1 are i.i.d samples from D real and denote z ∼ N l0 (0, I) as Gaussian noise. We denote the p,q -norm of a matrix A as A p,q ( j ( i A p i,j ) q p ) 1 q and the spectral norm as A 2 . We denote the conjugate of p as p * , with 1/p * + 1/p = 1. For an arbitrary distribution µ, μ denotes the empirical distribution over a random sample of size m from µ.

We let F = {f | f : R d0 → [-1, 1]} denote the function class of discriminators, and G = {g | g : R l0 → R d0 } denote the function class of generators. Every generator g ∈ G induces a distribution D g : by applying g to a random sample z ∼ N l0 (0, I), then we generate a sample g(z) from D g . In the context of GANs, both F and G are neural network function classes. Specifically,

∀ f ∈ F, x ∈ R d0 , f (x) = T f,k1+1 •σ •T f,k1 •• • ••σ •T f,1 •x, where ∀ 1 ≤ i ≤ k 1 +1, T f,i (u) W f,i u+b f,i , and σ(•) is a ρ-Lipschitz active function. Note that, b f,i ∈ R di×1 , W f,i ∈ R di-1×di

, where d i is the width of the ith layer of f , and k 1 + 1 is the depth of f . For convenience, we introduce

M f,i (b f,i , W f,i ) . Similarly, we define the generator class as G {g | g = T g,k2+1 • σ • T g,k2 • • • • • σ • T g,1 • z, z ∈ R l0 }. Here, T g,i (u) W g,i u + b g,i , 1 ≤ i ≤ k 2 + 1. Note that, b g,i ∈ R li×1 , W g,i ∈ R li-1×li

, where l i is the width of the ith layer of f , and k 2 + 1 is the depth of g. For neural network functions f ∈ F and g ∈ G, we parameterize them as f w , g v , respectively, where w, v are the weight parameters. We denote W and V as the parameter space of F, G, respectively. We denote the Lipshchitz constant (with respect to the input x ∈ R d0 ) of f as L.

Weight normalization. Weight normalization is an efficient regularization method for training robust models. We introduce the p,q and spectral weight normalizations, and establish the generalization theory for such weight normalized neural networks.

Assume that, F is a neural network function class, which is parameterized as F = {f w |w = (M f,k1+1 , . . . , M f,1 ), w ∈ W}. We define F with p,q weight normalization as M f,i p,q c F ,i , i = 1, . . . , k 1 + 1. In this context, we define the parameter norm as ww p,q

k1+1 i=1 M f,i -M f,i p,q /c F ,i .

For spectral weight normalization, we repeat the definition in Jiang et al. (2019) 's work. Assume that, F is a neural network function class without bias terms. It is parameterized as F = {f w |w = (W f,k1+1 , . . . , W f,1 ), w ∈ W}. We define F with spectral weight normalization as W f,i 2 B F ,i , i = 1, . . . , k 1 + 1. In this context, we define the parameter norm as ww 2

k1+1 i=1 W f,i -W f,i 2 /B F ,i .

For F and G, the parameter norm • induces the metric parameter space (W, • ) and (V, • ), respectively. Hence, we define the Lipschitz constants of f ∈ F and g ∈ G (with respect to • ) as L f and L G , respectively.

GANs. According to the training process of GANs, we formulate the objective functions as:

min g∈G max f ∈F E x∼D real [φ(f (x)] -E x∼Dg [φ(f (x))],

where φ(•) : [-1, 1] → R is a monotone L φ -Lipschitz continuous function. The objective function shows that, the discriminator f should give high values to x ∼ D real and low values to x ∼ D g . When D real , D g are the same, f is expected to output 0.

The training process for GAN is tantamount to minimizing a specific distance, between D g and D real . To measure the distance between distributions, we consider a general distance. Let µ, ν be two distributions supported on R d1 :

d F (µ, ν) sup f ∈F E x∼µ [φ(f (x))] -E x∼ν [φ(f (x))].

The objective function is equivalent to min g∈G d F (D real , D g ). Without a loss of generality, we take φ(x)

x in our work. Therefore, our distribution distance can be revised as

d F (µ, ν) = sup f ∈F E x∼µ [f (x)] -E x∼ν [f (x)].

Though the distribution distance is similar to Wasserstein Distance (Arjovsky et al., 2017) , our discriminator function class F is not forced to be an 1-Lipschitz function class. According to Arora et al. (2017) 's work, if we constrain the range of f to [0, 1] and utilize the F-distance (Arora et al., 2017) , the representation can be reduced to the original GAN and WGAN by specific φ(•). Thus, it can unify the JS divergence and the Wasserstein distance. Since our generalization theory also holds in these cases, we omit repetitive discussions of F-distance.

Rademacher Complexity. The complexity or capacity of a network function class has a direct effect on the generalization properties of a network. Since a GAN model consists of two network structures, the complexities of F and G are the keys to further investigation of the generalization properties of GANs. The definition of the Rademacher complexity is given as follows. If we assume that F is a class of real value functions, and i is the Rademacher Random Variable, then the empirical and expected Rademacher complexities are defined accordingly,

RS (F) E sup f ∈N 1 n n i=1 i f (z i ) , R n,D (F) E S∼D n RS (F) ,

where 1 , . . . , n are independent Rademacher random variables, i.e., P( i = 1) = P( i = -1) = 1/2.

We first introduce the definition of generalization error for GANs. In supervised learning, generalization error refers to the gap between the training error and the test error. However, in the context of GANs, neither the training error nor the test error is well defined. This is because the discriminator f , which is the counterpart of the loss function, varies throughout the training process. In the following, we provide a reasonable measure for the counterparts of the training error and the test error for GANs using the distribution distance d F (•, •). For a GAN model with the discriminator f ∈ F and the generator g ∈ G, we define the training error as d F ( Dreal , D g ) and the real error as d F (D real , D g ), where Dreal is the empirical distribution over the sample set S. The generalization error bound for GANs is defined as the difference between these two errors.

We compare our definition of the generalization error with that in Arora et al. ( 2017 2017) is slightly different from our intuition. In these works, ḡ is defined as the generator, which is obtained by the training process, and g * is defined as the optimal generator for inf g∈G d F (D real , D g ). Then, they define the generalization bound as

d F (D real , D ḡ ) -d F (D real , D g * ).

However, in practise, exact values for g * and D real are not accessible. Thus, the first term fails to represent the training error, and the second term fails to represent the testing error.

It is more reasonable to assume that D g is a known distribution for a fixed g. The process of generating new noise samples in every epoch, is an empirical approximation of D g , rather than a simple "training noise" data collection process. From this perspective, our definition provides a more reasonable theoretical measure of the generalization error for GANs. Definition 3.1. For a GAN model with the discriminator f ∈ F and the generator g ∈ G, the generalization error is defined as

|d F (D real , D g ) -d F ( Dreal , D g )|.

We say is a generalization error bound if the following holds:

sup g∈G |d F (D real , D g ) -d F ( Dreal , D g )| ,

where only relies on the parameter settings of F and G.

Intuitively, a low generalization error bound guarantees that the generalization error is low. Hence, the discriminator successfully discriminates between real data and unseen data. In these cases, the generator generates a distribution close to D real . An explicit generalization error bound provides us with guidance to design a GAN for designing a GAN to adequately fit real data. The following theorem provides an upper bound for the generalization error, with a fixed g. Theorem 3.2. For any fixed g ∈ G, with a probability of at least 1 -δ over the choice of samples S:

EQUATION

Though the result of Theorem Corollary 3.3. Assume x p * 1, ∀x ∈ S. For any fixed g ∈ G, with a probability of at least 1 -δ over the choice of samples S, with p,q weight normalization:

dF (D real , Dg) -dF ( Dreal , Dg) 2 s k 1 +1 (2k1 + 4) log 2 m + k 1 +1 i=1 cF,iρd [ 1 p * -1 q ] + i d 1 p * 0 C(p) m + log(1/δ) m ,

where

s k+1 k 1 +1 i=1 ( k 1 +1 l=i c F ,l ρd [ 1 p * -1 q ] + l ) + d 1 p * 0 k 1 +1 l=1 c F ,l ρd [ 1 p * -1 q ] + l and C(p) 2 log(2d0) p ∈ {1} ∪ (2, ∞), min(p * -1, 2 log(2d0)) p ∈ (1, 2] .

By utilizing the big O notation, Theorem 3.2 provides a bound of order O(d

1 p * 0 k 1 /m)

, where 1/p * 1 usually holds. Notice that, some previous works (Bartlett et al., 2017; Jiang et al., 2019) provide bounds of order O( d 3 k 1 /m) and O(d k 1 /m), where d = max{d i } k1 i=1 . Hence, our bound is tighter than previous works. Remark 3.4. A fair comparison between our bound and the bound in Arora et al. (2017) shows our bound is tighter. We denote P F as the number of parameters of f ∈ F, and L F as the Lipschitz constant with respect to the parameters of f ∈ F. We assess the two results under our definition of generalization bound in Section 3. According to Arora et al. (2017) 

, if m 3P F log(L F P F / )/ 2 , we have a probability of at least 1 -exp(-P F ) over the choice of S, |d F (D real , D g ) -d F ( Dreal , D g )|

/2. This holds because the formula (6) in the Theorem B.2 of Arora et al. (2017) no longer contributes to the generalization bound. We convert our result into a similar fashion by utilizing 1/m 2 /(3P F log(L F P F / )) and δ = exp(-P F ). We obtain

|dF (D real , Dg) -dF ( Dreal , Dg)| 2(s k 1 +1 (2k1 + 4) log 2 + k 1 +1 i=1 cF,iρd [ 1 p * -1 q ] + i d 1 p * 0 C(p)) + √ PF • 3PF log(LF PF / ) .

Since {c F ,i } k1 i=1 can be constrained to small values by applying weight normalization, we can force the following holds:

2(s k 1 +1 (2k1 + 4) log 2 + k 1 +1 i=1 cF,iρd [ 1 p * -1 q ] + i d 1 p * 0 C(p)) √ PF • 1 2 3 log( k 1 +1 i=1 ρ k 1 +1-i l j=i d [ 1 p * -1 q ] + l cF,jPF / ) -1 . log(L F P F / ) ≈ log(P F √ m

) and P F are large numbers, which only depend on the structure of F. Hence, there exits {c F ,i } k1 i=1 that is small enough to satisfy the inequality above. In these cases, our bound is tighter than Arora et al. ( 2017)'s bound. In fact, the weight normalization contracts the range of network parameters, so the complexity of F is reduced, thereby leading to a tighter generalization error bound.

Inspired by the probabilistic inequality in corollary 3.3, we formulate a hypothesis testing process to judge whether a generator produces data with the same distribution as that of the real data. The appendix contains the theory and experiments related to this novel hypothesis test on a toy dataset.

If we adopt ReLU (a homogeneous function) as an active function and apply the p,q weight normalization, the bound for the generalization error can be further reduced to become width-independent. Corollary 3.5. Under the same settings as Corollary 3.3, if 1/p + 1/q 1, we adopt the ReLU function as active function. Then, for any fixed g ∈ G, with a probability of at least 1 -δ over the choice of samples S:

dF (D real , Dg) -dF ( Dreal , Dg) 2 (1 + d 1 p * 0 ) k 1 +1 l=1 c F ,l (2k1 + 4) log 2 m + k 1 +1 i=1 cF,id 1 p * 0 C(p) m + log(1/δ) m .

We can easily extend our results to cases with spectral weight normalization (Jiang et al., 2019) .

Corollary 3.6. Let d = max{d i } k1+1 i=1 . Under the same settings as Corollary 3.3, for any fixed g ∈ G, with a probability of at least 1 -δ over the choice of samples S with spectral weight normalization:

dF (D real , Dg) -dF ( Dreal , Dg) 24( k 1 +1 i=1 BF,i)d k1 log(2 √ dmk1 k 1 +1 i=1 BF,i) √ m + 8 √ m + log(1/δ) m .

Corollary 3.6 shows the advantage of applying spectral weight normalization. We constrain k1+1 i=1 B F ,i such that it is small enough to force the first term to be small. If we set Miyato et al. (2018) also show that, spectral weight normalization render the discriminator more powerful for distinguishing between generated data and real data. Hence, we can suffer less from model collapse. Since d depends on the largest width of the network, the bound in spectral normalization is not actually width-independent. For this reason, we prefer to utilize the p,q weight normalization to obtain a width-independent bound.

k1+1 i=1 B F ,i = 1, the conclusion is reduced to O{ d 2 k 1 /m}. Experiments in

4. UNIFORM GENERALIZATION ERROR BOUND:

We have established the generalization error upper bound with a fixed generator g, that is, g is independent of the training process and the choice of sample set S. However, such a bound is not a uniform bound for ∀ g ∈ G. For any fixed g, let S(g) denote the set of samples where the inequality (1) in Theorem 3.2 holds, i.e., S(g

EQUATION

holds with S}. We emphasize the dependence of S(g) on g because this set varies as g changes. In other words, different S(g) values lead to different probability levels, at which the bound holds. Hence, the probability that (1) holds with S ∈ ∩ g∈G S(g) is not guaranteed to be greater than 1 -δ. An upper bound for the generalization error with a fixed g is tantamount to the generalization error bound for neural networks in supervised learning. To further understand GANs, it is necessary for us to establish a uniform bound for generalization error with varying g. The following theorem provides a generalization bound for GANs. Theorem 4.1. With a probability of at least 1 -2|X | • exp(-m 2 /4) over the choice of samples S:

sup g∈G |dF (D real , Dg) -dF ( Dreal , Dg)| 2Rm,D real (F) + ,

where X is a 2LL G -net of V, and V is the parameter space of G.

Theorem 4.1 depicts the error that is contributed by G. Note that, if G is complicated, then |X | can be a large number. In other words, if we reduce the complexity of G by applying weight normalization, the generalization error bound will consequentially decrease. In fact, weight normalization is an approach for reducing the complexity of a function class and provides generalization error bound control. For the p,q weight normalization, the next theorem provides an explicit expression of the generalization error bound. Corollary 4.2. With a probability of at least 1 -δ over the choice of samples S:

sup g∈G |dF (D real , Dg) -dF ( Dreal , Dg)| 2 s k 1 +1 (2k1 + 4) log 2 m + k 1 +1 i=1 cF,iρd [ 1 p * -1 q ] + i d 1 p * 0 C(p) m + c δ 2PG m log(6k2LLG),

where c δ satisfies

log(1/δ) ( c 2 δ 2 -1)P G log(6k 2 LL G ) + P G log(c δ 2P G m log(6k 2 LL G ),

s k1+1 and C(p) are given in theorem 3.3, and P G denotes the number of parameters in g ∈ G.

Notice that with the p,q weight normalization, we obtain an upper bound for L, L G , in a p,q norm version:

L k1+1 i=1 c F ,i ρd [ 1 p * -1 q ]+ i , L G k2+1 i=1 ρ k2+1-i k2+1 j=i l [ 1 p * -1 q ]+ j c G,j .

Hence, for an arbitrary weight normalized GAN, we calculate the generalization bound with P G , c F ,i and c G,j . For every δ, we calculate the right hand side of the constraint and pick a feasible and small c δ . According to theorem 4.2, the choice of g contributes to the second term. Since the bounds {c F ,i } k1 i=1 for weight normalization can be artificially constrained to a small range, the first two terms can be constrained to a small value. Since P G is determined by the network structure of g ∈ G and is usually much larger than k 2 2 , the third term is dominate. Similarly, we obtain a width-independent generalization bound by adopting ReLU functions and applying specific p,q weight normalization, with 1/p + 1/q 1 . Our result can be extended to cases with spectral weight normalization. Corollary 4.3. Assume x 2 1 for x ∈ S. With a probability of at least 1 -δ over the choice of samples S with spectral weight normalization:

sup g∈G |dF (D real , Dg) -dF ( Dreal , Dg)| 24 k 1 +1 i=1 BF,id k1 m log(2 √ dmk1 k 1 +1 i=1 BF,i) + 8 √ m + c δ PG m log(6k2 k 1 +1 i=1 BF,i k 2 +1 j=i BG,j),

where c δ satisfies

log(1/δ) ( c 2 δ 2 -1)P G log(6k 2 k1+1 i=1 B F ,i k2+1 j=i B G,j ) + P G log(c δ 2P G m log(6k 2 k1+1 i=1 B F ,i k2+1 j=i B G,j )).

5. NUMERICAL EXPERIMENTS.:

In this section, we illustrate some numerical experiments to verify that our generalization error bound is consistent with numerical studies. We train Wasserstein generative adversarial networks (WGANs) to learn a three-Gaussian Mixture distribution. The structure of the discriminator is a three-layer In order to compute the generalization error with an empirical approach, we generate two data sets, S train and S test , while the sample size of S test is much larger than that of S train . We regard the empirical distribution over S test as an approximation of D real . The noise is generated from z ∼ N 2 (0, I), in the training process.

We compare the generalization error and generalization bound of the WGAN model. We adopt an empirical approach to calculate d F (D real , D g ) and d F ( Dreal , D g ). Since theorem 4.2 provides a computable generalization bound with 2,2 weight normalization, for a trained WGAN, we can calculate the generalization error and generalization bound. For each d ∈ {50, 70, 90, 110, 130}, we repeat the following process 50 times to compute the generalization error and the average generalization error. At the same time, we calculate the generalization error bound for each d and the average value. S test , S train (denoted as Dtest , Dtrain ), respectively. The detailed process is included in the appendix.

According to figure 2 , there is a positive correlation between the generalization error and generalization bound. As the number of parameters in the generator increases, the generalization bound increases. In other words, the experiment verifies that, our bound provides generalization error control. A low generalization bound guarantees that the generalization error is low, whereas a generator with a large number of parameters introduces more error.

In fact, by applying p,q weight normalization to f, g with small c F ,i , c G,j , we control the generalization bound so that it remains a small value. The number of parameters in the generator should not be extremely large. So far, the experiment and our theory have explained how p,q weight normalization and the parameter settings of f, g affect the generalization of GANs. Our generalization bound provides explicit guidance on parameters designing to train GANs with small generalization error. Thus, we can obtain robust generators.

6. CONCLUSION:

In this paper, we establish the generalization theory for GANs and provide a more reasonable definition of generalization error. We first establish a general bound for generalization error, with a fixed generator. To further understand GANs, we establish the generalization error bound, which uniformly holds over any choice of generators. Our numerical experiments on Gaussian Mixture models verify that, our theory is consistent with the numerical studies. In the Appendix, we also formulate a novel hypothesis testing procedure to judge whether the generated distribution equals the distrbution of observed data. Notice that, in these high dimension cases, the ordinary statistical approaches do not work well. Our hypothesis test is capable of discriminating between good and bad generators. One interesting future research topic is to develop generalization error bounds for autoencoder GANs with an additional encoder network. 

A PROOF DETAILS FOR MAIN RESULTS:

PROOF OF THEOREM 3.2

Proof.

sup

f ∈F E x∼D f (x) -E z∼N f • g(z) -sup f ∈F E x∼ D f (x) -E z∼N f • g(z) sup f ∈F E x∼D f (x) -E z∼N f • g(z) -E x∼ D f (x) -E z∼N f • g(z) = sup f ∈F E x∼D f (x) -E x∼ D f (x)

Using the well-known estimation method for the generalization bound in supervised learning Mohri et al. (2018) , with a probability of at least 1 -δ over the choice of samples, we have

sup f ∈F E x∼D f (x) -E x∼ D f (x) 2R m,D real (F) + log(1/δ) m PROOF OF COROLLARY 3.3

We adopt Chen et al. ( 2019) to obtain a tighter and more general bound of the Rademacher Complexity:

R m (F)

s k1+1 (2k 1 + 4) log 2 m + k1+1 i=1 c F ,i ρd [ 1 p * -1 q ]+ i d 1 p * 0 C(p) m Where s k1+1 k1+1 i=1 ( k1+1 l=i c F ,l ρd [ 1 p * -1 q ]+ l ) + d 1 p * 0 k1+1 l=1 c F ,l ρd [ 1 p * -1 q ]+ l C(p) 2 log(2d 0 ) p = 1 , min(p * -1, 2 log(2d 0 )) p > 1 . PROOF OF THEOREM 4.1 Lemma A.1. ∀ x p * 1, f ∈ F, we have f (x) c F ,k1+1 k1 i=1 ρ k1+1-i k1 j=i d [ 1 p * -1 q ]+ j c F ,j .

Where ρ is the Lipschitz constant of the active function.

Proof. Define a series of variables {Z 0 , Z 1 , ..., Z k1 } as

Z 0 = x p * and Z l+1 = f l+1 (x) p * , l = 0, 1, ..., k 1 ,

where f l is the combination of the first l layers. Then, we prove by induction that for l = 1, ..., k 1 ,

Z l l i=1 ρ l+1-i l j=i d [ 1 p * -1 q ]+ j c F ,j . When l = 0, we have Z 0 = x p * 1. For l = 1, 2, ..., k 1 , Z l = f l (x) p * = σ(W f,l (x) + b f,l ) p * ρd [ 1 p * -1 q ]+ l ( W f,l p,q f l-1 (x) p * + b f,l p * ) ρd [ 1 p * -1 q ]+ l (c F ,l Z l-1 + c F ,l ) l i=1 ρ l+1-i l j=i d [ 1 p * -1 q ]+ j c F ,j

Finally, we have

f (x) = W f,k1+1 f k1 (x) p * W f,k1+1 p * f k1 (x) p * c F ,k1+1 k1 i=1 ρ k1+1-i k1 j=i d [ 1 p * -1 q ]+ j c F ,j

Lemma A.2. For generator class G, which is parameterized as the previous discussions, there is a /L G -net X for parameter space V, with respect to the p,q parameter norm, such that

log |X | P G log(3k 2 L G / ), where L G = c G,k2+1 k2 i=1 ρ k2+1-i k2 j=i l [ 1 p * -1 q ]+ j c G,j . Proof. For two generators g v , g v ∈ G, v = (M g,k2+1 , . . . , M g,1 ), v = (M g,k2+1 , . . . , M g,1 ) ∈ V, we have |g v (x) -g v (x)| |g {M g,k 2 +1 ,...,Mg,1} -g {M g,k 2 +1 ,M g,k 2 ...,Mg,1} | + • • • + |g {M g,k 2 +1 ,...,M g,2,Mg,1 } -g {M g,k 2 +1 ,...,M g,1} | L G (∆M g,k2+1 ) p,q c G,k2+1 + • • • + L G (∆M g,1 ) p,q c G,1 =L G k2+1 i=1 (∆b g,i , ∆W g,i ) p,q c G,i ,

Notice that, we derive the second inequality by applying lemma A.1 on g. Then, we focus on the

c G,i k2L G -nets of set {x ∈ R li-1×li | x p,q c G,i }. According to lemma 1.3 of Berthet, there exists a c G,i k2L G -net X i that satisfyies log |X i | l i-1 (l i +1) log(3k 2 L G / ). We construct a /L G -net X of V, by taking X {v = (M g,k2+1 , . . . , M g,1 ) ∈ V | M g,i ∈ X i , i = 1, ..., k 2 +1}. Hence, we have log |X | P G log(3k 2 L G / ). Lemma A.3. For any generator g ∈ G, d F (D real , D g ) -E S [d F ( Dreal , D g )] 2R m,D real (F) Proof. d F (D real , D g ) -E S [d F ( Dreal , D g )] = sup f ∈F E x∼D real f (x) -E z∼N f • g(z) -E S sup f ∈F E x∼ Dreal f (x) -E z∼N f • g(z) E S sup f ∈F E x∼D real f (x) -E z∼N f • g(z) -sup f ∈F E x∼ Dreal f (x) -E z∼N f • g(z) E S sup f ∈F E x∼D real f (x) -E z∼N f • g(z) - E x∼ Dreal f (x) -E z∼N f • g(z) 2R m,D real (F),

where we denote the noise distribution N l0 (0, I) as N for short.

Lemma A.4. With F, G fixed, the following holds with a probability of at least 1 -2δ over the choice of samples S:

sup g∈G E S sup f ∈F E x∼ Dreal f (x) -E z∼N f • g(z) -sup f ∈F E x∼ Dreal f (x) -E z∼N f • g(z) c δ 2PG log(3k2LLG) √ m ,

where c δ satisfies

log(1/δ) ( c 2 δ 2 -1)PG log(3k2LLG) + PG log(c δ 2PG log(3k2LLG)/m).

Proof. Let S 1 and S 1 be two sample sets from real data, with #S 1 = #S 1 = m. They differ by exactly one element, which is denoted as x i ∈ S 1 and x i ∈ S 1 , respectively. For a fixed g, we have

sup f ∈F E x∼ D f (x) -E z∼N f • g(z) -sup f ∈F E x∼ D f (x) -E z∼N f • g(z) sup f ∈F E x∼ D f (x) -E z∼N f • g(z) -E x∼ D f (x) -E z∼N f • g(z) = sup f ∈F E x∼ D f (x) -E x∼ D f (x) = sup f ∈F 1 m f (x i ) -f (x i ) 2 m ,

where D, D stands for the uniform distribution over S 1 , S 1 . According to McDiarmid's inequality, it holds that:

P S E S sup f ∈F E x∼ D f (x) -E z∼N f • g(z) -sup f ∈F E x∼ D f (x) -E z∼N f • g(z) 2 2 exp(- 2 /2 2/m ),

where D stands for the uniform distribution over S. By following Lemma A.2, we let X be a 2LL Gnet of V that satisfies log |X | P G log(6k 2 LL G / ). Then, by a union bound over all g, whose parameter belongs to X , we have:

P S sup g∈X E S sup f ∈F E x∼ D f (x) -E z∼N f • g(z) -sup f ∈F E x∼ D f (x) -E z∼N f • g(z) 2 2 exp(P G log(6k 2 LL G / )) exp(- 2 /2 2/m ). Take = c δ √ 2P G log(6k2LL G ) √ m

, then the proof is finished. 

) i = E x∼ Dreal [f train (x)] -E x∼Dg [f train (x)].

In each iterations, we generate an m-size noise sample set from N l0 (0, I), to feed the second term. Then, let d F ( Dreal , D g ) = 50 i=1 d F ( Dreal , D g ) i /50. 3. We set ĉf,i as M ftrain,i p,q . For a given confidential level 1 -α, by plugging {ĉ f,i } k1 i=1 into the right hand side of corollary 3.5, we obtain T .

4.. If d:

F ( Dreal , D g ) > T , we reject H 0 at a 1 -α level.

The hypothesis testing for H 0 is an application of corollary 3.5. Instead of providing a statistic with an explicit distribution, our hypothesis testing is based on a probabilistic bound for generalization error with a fixed generator.

Notice that, there are some distribution-free methods to compare two distributions in a purely statistical way, such as the Kolmogorov-Smirnov test, Shapiro-Wilk test, Mann-Whitney U Test and Bootstrap Methods. However, most of these methods are heavily based on some strong assumptions (i.e., normality, the conditions for central limit theorem and low dimension). Hence, these methods do not work with some unusual and high dimensional distributions. In high dimensional cases, corollary 3.5 guarantees that, our novel hypothesis testing has the capacity to discriminate between high dimensional distributions. Our numerical experiments show that, this hypothesis testing is commensurate with our observations.

D MORE EXPERIMENTAL RESULTS FOR OUR HYPOTHESIS TEST:

The following experiment illustrates the hypothesis testing process in section 3.1.1. For a specific generator, we convey the hypothesis process on 100 sample sets {S i } 100 i=1 , where ∀S i is derived from the same distribution of S train . If a generator is visually bad, the hypothesis process is expected to reject H 0 almost 100 times, at a 0.95 confidential level. In these cases, it is highly probable that the generated distribution is not close to the real distribution. Notice that, even if the hypothesis process embraces H 0 , the generator is not guaranteed to fit the real distribution well. Instead, we should say, the sample data is not rich enough to provide significant evidence to reject H 0 at a high confidential level. In fact, for a visually good generator, the hypothesis process fails to reject H 0 , even with a rich sample data set. In our experiments, an extremely small and negative value of gap d F ( Dreal , D g ) -T implies that the generator fits the real data very well and vice versa. For the previous bad generator in figure 3 , the gap is positive but small. This implies that, though the generator fails to fit the real data, it does not violate the real data grossly.

We display some representative results for hypothesis test in section 4. The experimental settings are the same as in previous discussions.

D.1 DISCRIMINATION:

To verify that our hypothesis test shows discrimination in choice of good generators, we conduct hypothesis test on 79 generators with the same training set S train and d = 50.

In figure 6 and 7, we juxtapose the hypothesis test conclusion and the corresponding generator.

Recall that, for a given g, we reject H 0 : D real = D g if d F ( Dreal , D g ) > T . Numerical experiments show that, our hypothesis is capable to detect the visually bad generators, at a 0.95 confidential level.

Our hypothesis test is based on a probabilistic inequality, which depends on the artificially designed sample set S train and confidential level 1 -α. Thus, for visually bad generators, there may be some rare acceptances of H 0 . In these cases, instead of stating 'the hypothesis test provided an incorrect conclusion', we should say 'the sample set S train is not rich enough to provide evidence to reject H 0 , at a 1 -α confidential level'. Such an example is included in 7.

D.2 DISTRIBUTION DEVIATION SENSITIVITY:

The numerical experiments also imply that, the hypothesis test can detect how D g violates D real .

We provide an example in figure 5 .

According to figure 5 , the hypothesis test provides stable rejection of H 0 with S i , i = 1, . . . , 100. Moreover, there is an evident gap between the training loss and T. Recall that the gap between the training loss and T of the bad generator in figure 3 is small and unstable. Obviously, the generator in figure 5 is much worse than the previous ones. The result suggests that, our hypothesis test is sensitive to the deviation between D g , D real .

Concretely, for generators that fit the data very well (or very badly), the hypothesis test provides a training loss which is much larger (or lower) than T ; for generators that perform modestly, the hypothesis test provides a training loss that is close to T to show its hesitation. In latter cases, to obtain an unambiguous conclusion, we can choose a richer sample set or set a larger confidential level. Figure 7 : Though our hypothesis test fails to detect the 24 th generator, it shows that train loss is extremely closed to T for the 24 th generator. This unusual acceptance is caused by randomness. In this case, the sample set Strain is not rich enough to reject H0, at a 0.95 confidential level.

:



Figures and Tables:

Jiang et al. (2019) also established a bound for generalization error using spectral normalization of GANs with a fixed generator. They show the advantages of spectrum control for generalization by constraining discriminator class. By adopting the Rademacher Complexity, Bartlett et al. (2017) yielded a bound of order O( d 3 k/m), where d, k, m stand for the largest discriminator width, the discriminator depth, and the training data size, respectively. Jiang et al. (2019) derived a bound of order O( d 2 k/m). In our work, we establish a bound of order O(d 1 p * 1

); Jiang et al. (2019); Zhang et al. (2017). Arora et al. (2017) defined the training error as d F ( Dreal , Dg ), which is related to the empirical distribution of D g . In other words, noise samples are regarded as a training set for GANs, while D g is regarded as an unknown distribution. However, such a consideration is not commensurate with the experiment process. Instead of being reinput in every iteration like the training set S, a new noise sample set of size m is generated in every epoch. Thus, noise sample sets are not equivalent to the training set S, since every noise sample sets is utilized only once. The definition of the generalization bound in Jiang et al. (2019); Zhang et al. (

3.2 seems similar to the Theorem 3.1 inZhang et al. (2017), our definition of generalization error is different. Theorem 3.2 shows that, for a fixed g ∈ G, the bound for the generalization error mainly depends on the complexity of F. Although the discriminator class should be complex enough to discriminate between D real and D g , a grossly complicated discriminator class generates extra generalization errors. Theorem 3.2 also shows the relationship between R m,D real (F) and the generalization error bound. For some specific neural network function classes, such as the class of p,q weight normalized neural networks, we can compute the Rademacher complexity to obtain an explicit upper bound for the generalization error. There are some previous works of Rademacher Complexity bounds, includingGolowich et al. (2018);Neyshabur et al. (2015); Chen et al. (2019). We adopt Chen et al. (2019) to obtain a tighter and more general bound.

(2 × 50 FC)-ReLU-(50 × 50 FC)-ReLU-(50 × 50 FC)-ReLU-(50 × 1 FC) network, where FC denotes a fully connected layer. The generator is a three-layer (2 × d FC)-ReLU-(d × 50 FC)-ReLU-(50 × 50 FC)-ReLU-(50 × 2 FC) network, where d takes value in {50, 70, 90, 110, 130}. After the training process, we calculate the generalization error and generalization error bound. The details of the experimental settings are included in the appendix.

Figure 1 displays two visualizations of the simulated results. The left panel shows a visibly good generator and the right panel shows a visibly bad generator. According to the previous discussions, generalization error is defined as |d F (D real , D g )d F ( Dreal , D g )|. To compute d F (D real , D g ), d F ( Dreal , D g ), we approximate the distribution distance d F (D real , D g ), d F ( Dreal , D g ) by substituting D real , Dreal with the uniform distribution over

(a) A visibly good generator. (b) A visibly bad generator.

Figure 1: The blue point cloud represents S train , a sample from a Gaussian Mixture distribution. The red points are {g(zi)} m train i=1 , while {zi} m train i=1

Figure 2: Each dot on the graph represents the average generalization error and the generalization bound of WGAN with d ∈ {50, 70, 90, 110, 130}.

.0.1 HYPOTHESIS TESTING FOR H 0 : D real = D g . (a) For the previous visually good generator. (b) For the previous visually bad generator.

Figure 4: A representative result of the hypothesis test with the generators in figure 3. In every experiment, we reject H0 if the training loss is larger than T.We show a representative result in figure4. Recall that, the hypothesis testing process reject H 0 if d F ( Dreal , D g ) > T , where we refer to d F ( Dreal , D g ) as the training loss and T as the test statistic for H 0 . Figure4suggests that, the hypothesis testing process embraces H 0 with a visually good generator, while it reject H 0 with a visually bad one, at a 0.95 confidential level. In fact, our experiments show that the conclusions from the hypothesis testing are commensurate with our observation. In our toy model, H 0 is rejected when the generated data forms a single clique (what we call Model Collapse) or it obviously disjoints with the real data. Hence, our hypothesis test is capable of discriminating between good and bad generators, with sufficient sample data.

(a) An extremely bad generator, which is even worse than figure 3. Model collapse also occurs. (b) We convey the hypothesis test with Si, i = 1, . . . , 100. All the experiments reject H0 at a 0.95 confidential level.

Figure 5: In such a extreme case, the values of training loss and T are stable.

Figure 6: In every figure, the blue points cloud represents S train , a sample from a Gaussian Mixture distribution. The red points are {g(zi)} m train i=1 , while {zi} m train i=1

(a) The hypothesis test result. For a fixed g, we reject H0 if the training loss is larger than T. According to the figure, we reject H0 with the 9, 26 th generators. (b) 40 generator examples in order. Notice that generator 9, 24 and 26 are visually bad (or even occur model collapse).

Jiahui Yu, Zhe Lin, Jimei Yang, Xiaohui Shen, Xin Lu, and Thomas S. Huang. Generative image inpainting with contextual attention. CoRR, abs/1801.07892, 2018. URL http://arxiv. org/abs/1801.07892. Pengchuan Zhang, Qiang Liu, Dengyong Zhou, Tao Xu, and Xiaodong He. On the discriminationgeneralization tradeoff in gans. CoRR, abs/1711.02771, 2017. URL http://arxiv.org/ abs/1711.02771.

Table content: <table/>

1. Train a WGAN over S train and save the parameters of the optimal ḡ. 2. Train a discriminator f to maximize E x∼ Dtrain [f (x)] -E x∼Dḡ[f (x)] to obtain ftrain .3. Train a discriminatorf to maximize E x∼ Dtest [f (x)] -E x∼Dḡ [f (x)] to obtain ftest .4. We calculate d F ( Dtrain , D g ) by following section 3.1.1. We obtain d F (D real , D g ) by substituting 'train' with 'test'.C A NOVEL HYPOTHESIS TEST FOR H 0 : D real = D g .For a given generator g ∈ G, we are insterested in whether this generator generates real data. To answer this question, we formulate a hypothesis test.Since our goal is to provide a hypothesis-testing process to figure out whether D g = D real holds, at a confidential level 1 -α, we state the null hypothesis as H 0 : D g = D real and the alternative hypothesis as H 1 : D g = D real . With the distribution distance, we revise the null hypothesis as:H 0 : d F (D real , D g ) = 0.Intuitively, in the context of image-generating GANs, a visually bad generator should give evidence to reject the null hypothesis and embrace the alternative hypothesis.Assume that H 0 holds, we haved F ( Dreal , D g ) |d F ( Dreal , D g ) -d F (D real , D g )|.According to corollary 3.5, for a given g ∈ G, with probability at least 1 -α over the choice of S, it holds that: d F ( Dreal , D g ) T , where T denotes the right hand side of corollary 3.5. Hence, d F ( Dreal , D g ) > T provides significant evidence to reject H 0 at a 1 -α confidential level. In other words, for a given g ∈ G, if d F ( Dreal , D g ) > T holds. This means that the artificial data is discriminable and g fails to adequately fit the real data. Hence, to make a hypothesis testing conclusion, we compare the values of d F ( Dreal , D g ) and T .C.0.1 HYPOTHESIS TESTING PROCESS.1. For a given g ∈ G, we train a discriminator f to maximizeE x∼ Dreal [f (x)] -E x∼Dg [f (x)].Notice that, training such a discriminator is equivalent to training a WGAN with g fixed. Hence, we obtain f train .2. For i ∈ {1, ..., 50}, we have d F ( Dreal , D g

Table content: <table/>

Peer review (iclr2020):
The authors give new generalization bounds for GANs. The argue for a new definition of generalization for GANs, which isolates the effect of sampling error arising from sampling from the real distribution. (Their argument, which I find convincing, may be paraphrased as saying that sampling from the generator should be viewed more as a computational cost than a data-gathering cost, since a procedure may sample from a generator as many times as it wants.) They give a bound that is uniform both over discriminators and generators. In my opinion, the mathematical writing is not up to the standard for publication in ICLR. There are many cases where the paper is unclear, and, in many other cases, I have to guess what they mean, and I have limited confidence in my guess. Since the theorems of the paper are quite technical, it is very difficult to be confident what their exact statements are. One example is where they write *We define F with weight normalization as ...*. The fact that the c in this definition has a subscript of f led me to think that the bound can depend on f, but this does not make sense. I assume that the bound is independent of f. Later, when they write *we define the Lipschitz constant of f*, since they write that this Lipschitz constant is with respect to a norm on parameterizations, I take it that they are defining the Lipschitz constant of a mapping from parameters to functions (and not a Lipschitz constant of f). But they don*t indicate what metric is used to define the distance between functions. When the compare their bound with previous work, they treat quantities as constants which can be large. For example, they treat the product of the operator norms of the layers as a constant. It also is not clear how they get the bound that they attribute to Bartlett, et al from the bound in that paper. Most of the technical heavy lifting appears to have been borrowed from the Chen, et al paper. A more detailed account of how they get their covering bound for their (p,q) norm from the Dumer paper is needed. Since the authors assume that phi is the identity, it seems unnecessary to keep subscript d with it. On the other hand, subscripting d with calF would make the theorems easier to interpret at a glance. (Edit on 11/14/19: I have read the response and checked the revision. Some of the above criticisms have been addressed by the revision. I have increased my rating.)