Title: UNDERSTANDING GANS VIA GENERALIZATION ANALYSIS FOR DISCONNECTED SUPPORT

Abstract: This paper provides theoretical analysis of generative adversarial networks (GANs) to explain its advantages over other standard methods of learning probability measures. GANs learn a probability through observations, using the objective function with a generator and a discriminator. While many empirical results indicate that GANs can generate realistic samples, the reason for such successful performance remains unelucidated. This paper focuses the situation where the target probability measure satisfies the disconnected support property, which means a separate support of a probability, and relates it with the advantage of GANs. It is theoretically shown that, unlike other popular models, GANs do not suffer from the decrease of generalization performance caused by the disconnected support property. We rigorously quantify the generalization performance of GANs of a given architecture, and compare it with the performance of the other models. Based on the theory, we also provide a guideline for selecting deep network architecture for GANs. We demonstrate some numerical examples which support our results.

1. INTRODUCTION:

Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) attract much attention as technology for learning a distribution and generating data. The purpose of GANs is to learn a probability measure from a given dataset and generate samples from the learned measure. It is often seen that samples generated by GANs can extract effectively features in the real world; it is difficult, for instance, to distinguish real images and generated images. By practical successes, a countless number of variations of GANs have been developed (Dziugaite et al., 2015; Arjovsky et al., 2017; Li et al., 2015; Nowozin et al., 2016; Gulrajani et al., 2017; Zhao et al., 2016) , and applied to a wide range of tasks (Reed et al., 2016; Zhu et al., 2017; Gauthier, 2014) .

Understanding the remarkable performance of GANs is, however, still a challenging problem. There are active discussions on the role of generators in its learning scheme (Goodfellow, 2016; Arjovsky & Bottou, 2017; Arora et al., 2018; Creswell et al., 2018) , and adversarial structures with discriminators are also a target of interest (Lotter et al., 2015; Zhang et al., 2018) . A gaming structure between generators and discriminators is also regarded as a useful factor in the mechanism of GANs (Mescheder et al., 2017; Arora et al., 2017; Heusel et al., 2017) . Generalization performance of GANs has been investigated in several studies (Liang, 2017; Liu et al., 2017; Tolstikhin et al., 2017) . In spite of these studies, it is not yet clear why GANs can generate well-extracted data better than other standard methods.

This paper introduces the disconnected support property, and explains an advantage of GANs in connection with this notion. The disconnected support property refers to a probability measures of which the support is divided into several disjoint sets, allowing non-differentiable density on the boundary. The property makes a probability measure be complex, hence it can be an obstacle for standard methods to learn the measure effectively. This property, however, is popularly seen in many real data, especially data with cluster structure, as demonstrated in Section 3.

We investigate in detail the approximation and estimation ability of GANs and some other methods, and provide novel generalization analysis of probability measures with disconnected support. Firstly, we show that the other methods suffer worse generalization performance due to complex structures of disconnected supports (Proposition 1 and Lemma 2). Secondly, our generalization analysis reveals that GANs can learn the probability measure without loss of efficiency under the the disconnected supports (Theorem 1, Corollary 1 and ??). Additionally, we derive a guideline for choosing the number of layers or connections of the generator and discriminator from the generalization analysis. Numerical results support our theoretical findings.

We remark that the disconnected support property is different from the low-dimensional supports studied in Arjovsky & Bottou (2017) , where the support of a measure generated by neural networks is disjoint to the measure of observations. In contrast, this paper considers the case in which the support of the observation measure is divided into disjoint subsets. The problem of disconnected supports is complement to the low-dimensionality, hence these two problems can be investigated separately. In this paper, to simplify the discussion, we assume that the support of a probability measure is not low-dimensional.

The contributions of this paper are summarized as follows:

1. We show that GANs perform better than other standard methods of estimating probability measures when the measure satisfies the disconnected support property. 2. We provide a new generalization error bound under a general formulation of GANs by analyzing an approximation error. The result is thus applicable to a wide range of variations of GANs. 3. Based on the generalization bound, we provide a theoretical guideline for selecting architectures of generators and discriminators.

All the proofs are given in Supplementary materials.

2. PRELIMINARIES:



2.1. NOTATION:

We use notations I :" r0, 1s. A j-th element of a vector b is denoted by b j , and }b} q :" p ř j b q j q 1{q is the q-norm (q P r0, 8s). vecp¨q is a vectorization operator for matrices. For z P N, rzs :" t1, 2, . . . , zu is a set of positive integers no more than z. For α P R, tαu denotes the largest integer which is not larger than α. For a domain Ω in a Euclidean space and a function f : Ω Ñ R, }f } L p :" p ş Ω |f ptq| p dtq 1{p denotes the L p norm for p P r0, 8s. For f : Ω Ñ R D with a multidimensional output, f d denotes a d-th coordinate of f pxq " pf 1 pxq, ..., f D pxqq J . Let H β pΩq be the Hölder space for β ą 0 such as a set of β-smooth functions f : Ω Ñ R, namely, f is C tβu -class and its tβu-th derivative is β ´tβu-Hölder continuous. b denotes a tensor product, and ˝a composition of functions, namely, for functions f and f 1 , f ˝f 1 " f pf 1 p¨qq. A Borel σ-algebra of Ω is denoted as σpΩq. For a measurable mapping f : Ω Ñ Ω 1 and B 1 Ă Ω 1 , a pre-image of f is defined as

f ´1pB 1 q :" tt P Ω | B 1 Q f ptqu. Let 1 Ω : x Þ Ñ

t0, 1u be an indicator function such that 1 Ω pxq " 1 if x P Ω, and 1 Ω pxq " 0 otherwise.

2.2. GENERAL FRAMEWORK OF GANS:

We provide a general formulation of a learning problem with generative adversarial networks (GANs) following Liu et al. (2017) . In this paper, we consider a probability measure P ˚on a measurable space pI D , Σq with a dimensionality D P N and Σ :" σpI D q. Here, we set D ě 3. Suppose we have a set of n observations D :" tX 1 , ..., X n u which is independently and identically generated from P ˚. Let P n :" 1 n ř iPrns δ Xi be an empirical measure where δ x is the Dirac measure at x. The goal of generative networks is to estimate P ˚from D. To this end, we construct a probability measure by generators. Let P Z be the uniform distribution on pI D , Σq. For a measurable mapping g : I D Ñ I D , we define P g as the pushforward measure: i.e., P g pBq " P Z pg ´1pBqq for B P Σ. We call g as a generator and use G for a set of generators.

GANs employ a learning scheme with a metric with discriminators (Goodfellow et al., 2014) . Let F " tf : I D Ñ Ru be a a set of discriminators. This paper considers a general metric for GANs (Liu et al., 2017) ,

EQUATION

between probability measures P and P 1 .

For the learning process, we generate m noise samples r Z 1 , ..., r Z m from P Z and obtain generated samples as r X j :" gp r Z j q with g P G for j P rms. Let P g,m :" (2)

The metric (1) covers a wide variety of GANs by selecting F. Among others, the original GAN (Goodfellow et al., 2014) is realized if F contains a logarithm of density ratio; Wasserstein-GAN (Arjovsky et al., 2017) , MMD-GAN (Dziugaite et al., 2015; Li et al., 2017) and Energy-Based GAN (Zhao et al., 2016) are given if F is the set of 1-Lipschitz functions, a reproducing kernel Hilbert space, and the bounded continuous functions, respectively. The f -GAN (Nowozin et al., 2016 ) also belongs to this class.

We assume that F is large enough to contain functions which can work as a discriminator, namely, we assume that the following holds:

d F pP, P 1 q " 0 ô P " P 1 .

(3)

A sufficient condition for (3) is investigated in Zhang et al. (2018) .

2.3. DEEP NEURAL NETWORKS FOR GENERATORS AND DISCRIMINATORS:

In the schemes of GANs, F and G are realized by deep neural networks (DNNs). For further discussion, we formulate the function class given by DNNs.

Let L P N be a number of layers in DNNs, and D 1 P N be a dimensionality of variables in an -th layer for P rL `1s. Here, we set D 1 L`1 " D for generators and D 1 L`1 " 1 for discriminators. We introduce A P R D 1 `1ˆD 1 and b P R D 1 as matrix and vector parametersof the -th layer. An architecture Θ of DNNs is defined as a set of L pairs of pA , b q as Θ :" ppA 1 , b 1 q, ..., pA L , b L qq. We define notations for Θ as follow: |Θ| :" L as the number of layers, }Θ} 0 :" ř PrLs } vecpA q} 0 `}b } 0 as the number of non-zero elements in Θ, and }Θ} 8 :" maxtmax PrLs } vecpA q} 8 , max PrLs }b } 8 u be the scale of parameters in Θ. We employ the ReLU activation function η : R D 1 Ñ R D 1 for each D 1 P N such as ηpxq " pmaxtx d , 0uq dPrD 1 s .

We define functions of DNNs with an architecture Θ as ξrΘs : R D 1 Ñ R D 2 by ξrΘspxq " x pL`1q , x p1q :" x, x p `1q :" ηpA x p q `b q, for P rLs.

The function class of DNNs is thus given by ΞpS, B, Lq :"

! ξrΘs : I D Ñ R | }Θ} 0 ď S, }Θ} 8 ď B, |Θ| ď L ) ,

where S P N, B ą 0, and L P N are hyper-parameters. Here, S bounds the number of non-zero parameters of DNNs, namely, it controls the sparseness of DNNs. B is a bound for scales of parameters.

3. DISCONNECTED SUPPORT PROPERTY:



3.1. INTRODUCTION AND EXAMPLE:

It is often observed that data in real world data the support of its probability measure may not be connected but a union of disjoint subsets. This is typical if the data has cluster structures, as seen in many data sets for classification tasks. Moreover, the density function of the probability measure may not be smooth at a boundary of the support. Figures 1 (MNIST, (LeCun et al., 1998) ) and 2 (Shelter Animal, Center) illustrate such examples in the real world. They are projected onto a 2-dimensional Euclidean space by t-SNE (Maaten & Hinton, 2008 ) so that they preserve the original distance structure among points. We can see that both of the data are concentrated on several disjoint subsets and there are a clear gap or empty regions between some of the subsets. This observation suggests that the disconnected property of probability measures should be addressed in discussing estimation of probability measures, while standard analysis does not consider this phenomenon. In fact, this paper will show that the disconnected supports property has an important role in showing an advantage of GANs over standard estimation methods.

Figure 1 : Plot of the MNIST data.

Figure 2 : Plot of the animal data.

3.2. MATHEMATICAL FORMULATION OF DISCONNECTED SUPPORTS:

Here we make a rigorous definition of disconnected supports. The property of smoothness (i.e. differentiability) is involved, which is a key factor to analyze generalization performance in the fields of the statistics (Stone, 1982; Tsybakov, 2009) ; Stone (1982) shows, for instance, that smoothness and a dimension of data are sufficient to characterize an optimal convergence of generalization errors.

We first prepare a family of subsets as a component in the disconnected supports:

S α,J :" S Ă I D | A boundary of S is J combination of α-smooth hyper surfaces ( .

The supplementary material will provide a more rigorous definition. Now, we define the disconnected support property of probability measures as well as a probability measure with global support, i.e., with no the disconnected support property. Let SupppP q be the support of P ., i.e, SupppP q :" tx P I D | P pV x q ą 0 for all open neighborhood V x of xu.

Hereafter, M ě 2 is the number of disjoint components of a support. Definition 1. (Disconnected Supports / Global Support) Let M ě 2. A probability measure P on pI D , Σq has M disconnected supports, if there exist nonempty disjoint sets S 1 , ..., S M P S α,J such that SupppP q "

ď mPrM s S m .

A probability measure P on pI D , Σq has a global support, if SupppP q " I D .

Figure 3 illustrates the disconnected support property.

We next formulate a notion of smoothness for P with disconnected supports. Let β ě 1 be a parameter for a degree of smoothness of P . Definition 2. (Local Smoothness) A probability measure P with M disconnected support is locally β-smooth, if there exist M pairs p r S m , S m q P S 2β,J ˆS2β,J and β `1-smooth bijective measurable maps γ m : r S m Ñ S m as P pBq " P Z pγ ´1 m pBqq, @B P σpS m q, for m P rM s.

This definition of local smoothness says that a probability measure P with disconnected supports can be generated by sufficiently smooth mappings γ m . It is used for considering a smooth density function of P restricted on S m . Lemma 1. (Locally Smooth Density Functions) If a probability measure P with M disconnected support is locally β-smooth, then there exists a function p m : S m Ñ R `such that P pBq "

ż B p m pxqdλ, B P σpS m q,

where λ is the Lebesgue measure, and p m is β-smooth for all m P rM s.

We call p m as a local density function.

Note that, since P with disconnected supports is not absolutely continuous to the Lebesgue measure on I D z Ť mPrM s S m , an ordinary density function cannot be defined. Instead, a localized version of density functions for each S m is introduced, which is guaranteed by the local smoothness.

Figure 3 : Illustration of a probability measure P with a disconnected support. SupppP q is a union of two disjoint sets S 1 and S 2 .

Figure 4 : Illustration of a generator g. To represent discontinuous S 1 and S 2 , g should be discontinuous.

3.3. DIFFICULTY WITH DISCONNECTED SUPPORTS:

As shown in this subsection, the generalization performance of many standard estimation methods is worsened with disconnected supports. We consider popular nonparametric methods, for which the generalization performance is well-studied in the asymptotics of the observation size n. The considered methods are the kernel density estimator (KDE) (Nadaraya, 1964) , the nonparametric Bayes (NB) by the Dirichlet mixtures of normal distributions (Ferguson, 1973) , the series density estimator (SDE) (Efromovich et al., 2008; Efromovich, 2010) and the density estimator with Gaussian process (GP) (Leonard, 1978) . Bounds of the generalization errors for these methods are already known (Tsybakov, 2009; Ghosal et al., 2007; van der Vaart & van Zanten, 2008) , and they are optimal in the minimax sense. Here, their performance is evaluated with respect to a root of an expected squared loss with respect to the L 2 -norm, namely, d 2 pP, P 1 q :" Er}p ´p1 } 2 L 2 s 1{2 where p and p 1 are densities for P and P 1 .

We show the deterioration of their performance by the disconnected support property. Let p P be an estimator for P ˚by KDE, NB, SDE, or GP. If P ˚has a global support and a β-smooth density, the existing studies (Tsybakov, 2009; Ghosal et al., 2007; van der Vaart & van Zanten, 2008) show that

d 2 pP ˚, p P q " O ´n´β{p2β`Dq ¯.

These bounds are sufficiently tight, since these bounds corresponds to an optimal rate (Stone, 1982) , and the performance of the methods can be improved as the density for P ˚is smoother (larger β).

On the other hand, we consider a case in which P ˚has the disconnected support property.

Proposition 1. (Deterioration of other standard methods):

There exists P ˚of the disconnected support property and locally β-smooth such that d 2 pP ˚, p P q " O ´n´1{p2`Dq ¯.

When P ˚has disconnected supports, the errors are worse than those for the global support, independent of β. This worse generalization error can be understood by the non-smoothness or discontinuity of the density functions on the boundaries of the disconnected sets (see Figure 3 ).

We next discuss other generative models for estimating a probability measure. To the best of our knowledge, other probabilistic generative methods (Koller et al., 2009) and the variational autoencoder (Kingma & Welling, 2013), their statistical generalization property is not well investigated.

Here we provide a property of generators for probability measures with disconnected supports. Lemma 2. (Discontinuous Generators for Disconnected Supports) If P ˚has disconnected supports and P ˚" P g ˚with a generator g ˚, then g ˚is not uniformly continuous.

Lemma 2 states that a generator must be discontinuous to construct a probability measure with disconnected support sets. Intuitively, to make P g ˚pB q " 0 for B P I D with λpBq ą 0, the slope of g ˚at z P I D should be close to infinite for z P g ˚,´1 pBq, hence g ˚cannot be uniformly continuous (see Figure 4 ). Because of the discontinuity, generative models with smooth functions, such as an adversarial generative model with kernel generators (Sinn & Rawat, 2018) , cannot work well with disconnected supports.

4. GENERALIZATION BY GANS:

We provide generalization analysis for GANs for probability measures with and without disconnected supports. For the purpose, we employ a metric d F with properly selected discriminators F and evaluate the generalization error d F pP ˚, P p g q with respect to an observation size n and a sampling size m. We assume F is realized by DNNs as

F " ΞpS f , B f , L f q X r F with parameters S f , B f , L f , where r

F is a specified functional class; for an example, r F is 1-Lipschitz functions for Wasserstein-GAN. Here, we consider settings that all f P F are L 1 -Lipschitz continuous and }f } L 8 ď B F with constants L 1 , B F ą 0.Generators are also constructed by DNNs as G " ΞpS g , B g , L g q with parameters S g , B g , L g .

A standard line of discussing generalization, we should consider statistical errors and approximation errors. We define a measure of the complexity of F

Υ n pFq :" inf ηą0 4η `12n ´1{2 ż c η log N ppL 1 `1q ´1 , F, } ¨}n q 1{2 d ,

where c ą 0 is a constant depends on F and N p , r F, } ¨}q is a covering number of r F with respect to an empirical norm } ¨}. We note that Υ n pFq bounds an expectation of the Rademacher complexity as

Υ n pFq ě E » -sup f PF 1 n ˇˇˇˇˇÿ iPrns τ i f pX i q ˇˇˇˇˇfi fl ,

where τ i is the i.i.d. Rademacher random variables; Prpτ i " 1q " Prpτ i " 1q " 1{2, and the expectation is about X i and τ i . Using the statistics and learning theory van der Vaart & Wellner (1996) ; Bartlett et al. (2005) , we can apply a bound for Υ n pFq as

Υ n pFq ď C F n ´1{κ ,

with some constants C F ą 0 and κ ě 2.

Regarding approximation errors, we need to consider approximation of a discontinuous function; since Lemma 2 shows that a discontinuous generator is necessary to represent disconnected supports. To approximate such generators, DNNs in GANs has an advantage. Lemma 3. (Approximation for Discontinuous g by DNNs) Suppose P ˚has M disconnected supports and locally β-smooth, and also P ˚" P g ˚holds with some g ˚. Then, for any S g , there exist G, 9 g P G, and a constant c g " c g pB g , L g q ą 0 such that

EQUATION

Furthermore, if P ˚" P g ˚has a global support and it is β-smooth, (4) holds with M " 1.

Lemma 3 shows that G for GANs can approximate g ˚for disconnected supports with the rate (´β{D) by S g , and the rate is same in the case of global support. This implies an advantage of GANs in comparison with the other standard methods (Proposition 1).

Based on Lemma 3, we obtain the main theorem for generalization analysis. Theorem 1. (Generalization of GANs) Suppose that P ˚has M disconnected supports and locally β-smooth, and we have n observations and m samplings. Then, with F, an existing G, an estimator P p g by (2), and finite constants c 1 " c 1 pL f , B f , L g , B g q, c 2 , c 3 " c 3 pL f , B f q ą 0, the following inequality holds with high probability,

d F pP ˚, P p g q ď Υ m p r Fq `c1 a S g `aS f ? m looooooooooooooomooooooooooooooon ":I `c2 M DS ´β{D g loooooomoooooon ":II `Υn p r Fq `c3 c S f n looooooooomooooooooon ":III .

(5)

Furthermore, if P ˚has a global support and it is β-smooth, (5) holds with M " 1. `2d F pP n , P 0 q loooooomoooooon ":iii .

To obtain i ď I and iii ď III, we apply an empirical process technique (van der Vaart & Wellner, 1996) , especially convergence of integral probability measures (Sriperumbudur et al., 2012) and the entropy control technique (Lemma 4 and 5 in the supplementary material). To show ii ď II, we employ recent results on approximation ability of DNNs (Yarotsky, 2017; Petersen & Voigtlaender, 2017; Imaizumi & Fukumizu, 2018) and obtain an approximation bound for d F pP g , P ˚q (Lemma 3).

Combining these results, we obtain the statement of Theorem 1.

Theorem 1 provides two trade-off relations with respect to S g and S f . The generator class G controls uncertainty by sampling and the approximation error, while S f controls uncertainty of observations and discrimination. For balancing the trade-offs, we select the number of parameters (connections of DNNs) with some constants c g , c f ą 0 as S g " c g m D{p2β`Dq , and S f " c f n pκ´2q{κ ,

for optimizing the bound (5). We then obtain the following corollary. Corollary 1. (Convergence Rate of GANs) Make the same assumptions as Theorem 1, and set S f and S g as in (6). Then, with high probability converging to 1, we obtain

EQUATION

A selection of r F determines the first term in ( 7), since κ depends on r F. For an example, when F is a set of 1-Lipschitz functions, the first term is O `n´1{p2`2Dq ˘ (Sriperumbudur et al., 2012) . Remark 1. (Heterogeneous Smoothness) Corollary 1 can be extended when P ˚has different smoothness for each m P rM s, i.e., P ˚is locally β m -smooth on a set S m . In this case, we can easily extend our analysis in Theorem 1 and Corollary 1, and obtain the following convergence rate.

d F pP ˚, P p g q " O ´n´1{κ ¯`O ´m´1{κ `m´r β{p2 r β`Dq ¯,

where r β :" min mPrM s β m .

5. DISCUSSION:

We emphasize the theoretical results show that GANs do not suffer from the effect of disconnected supports. A larger β improves performance of GANs even with disconnected supports, as shown in Theorem 1 and Corollary 1. This phenomenon is different from the result of the other methods discussed in Proposition 1. Hence, we can state that GANs have advantages over the other methods which are deteriorated by the disconnected property (Section 3.3). In other words, when data are generated from a probability measure with disconnected supports and sufficiently smooth in each of the sets, only GANs can estimate the measure effectively and the other methdos cannot. This advantage of GANs comes from the approximation power for discontinuous generators shown in Lemma 3.

The results ( 5) and ( 7) provide interpretation about performance of GANs. About convergence with n, the complexity of r F and S f control a trade-off between convergence and a power of discrimination. While smaller S f reduce the errors in terms of d F , too small S f can lose the power of discrimination to satisfy (1). Hence, setting S f as in ( 6) can keep the discrimination power and does not worsen the overall rate of convergence Opn ´1{κ q. About convergence with m, S g controls the trade-off between the bias and variance of the estimator. An optimal way to select S g is provided in (6) which depends on β and D, and it is more important when κ is small (e.g. κ " 2 as MMD-GAN). Based on the interpretation and the selection rule (6), our study can provide a guideline for a design of the architecture of DNNs.

5.1. RELATED WORKS:

Compared with studies for understanding GANs (Dziugaite et al., 2015; Liang, 2017; Liu et al., 2017; Zhang et al., 2018; Biau et al., 2018; Arora et al., 2017) , we show that GANs can avoid influences of disconnected supports, unlike the other methods, hence it is a source of the advantage of GANs. This paper is the first work to focus on the disconnected support property, while several discussions (Goodfellow, 2016; Liang, 2017; Creswell et al., 2018) focus on models and metrics of the learning scheme of GANs.

It is important to compare our result with other studies for generalization analysis. Although some existing studies (Dziugaite et al., 2015; Liang, 2017; Liu et al., 2017; Zhang et al., 2018; Biau et al., 2018; Arora et al., 2017) provide generalization analysis, they do not analyze an approximation effect, namely, they evaluate d F pP ˚, P p g q ´inf gPG pP ˚, P g q. Since we analyze the term inf gPG pP ˚, P g q, we can provide a more general bound and discuss the effect of disconnected support.

As we mentioned in the introduction, this paper is not along with studies for low-dimensional supports (Arjovsky & Bottou, 2017) . We also note that an optimization aspect and gaming aspect of GANs are out of concerns of this paper. We focus on the statistical aspects of GANs such as sample complexity.

6. NUMERICAL EXPERIMENTS:

We compare the numerical performance of GANs and the other methods with toy data with. We generate synthetic data from the following two settings: (A) Gaussian distribution restricted on a compact set (global support), and (B) a probability measure with two disconnected supports (density function is the black solid line in Figure 6 ). We generate n " 500, 1000, ..., 5000 observations and estimate the true probability measures with Wasserstein GAN, MMD-GAN, KDE (the Gaussian kernel and the Epanechnikov kernel), SDE (Fourier basis), and NB (Dirichlet process prior). Hyperparameters for these methods are selected by cross-validation. For GANs, we set m " n. We use d F to evaluate errors by GANs, and a root of the expected squared errors with the L 2 -norm for the other methods. The plots are the mean of 30 replications.

Figure 5 shows generalization errors by the methods. With the disconnected support case (B), we plot the estimated density in Figure 6 . The black line shows the true density, the dashed line is by estimated densities of the other methods, and bars are histograms by GANs. The results by Wasserstein-GAN and MMD-GAN are almost same, so we omit the result by Wasserstein-GAN.

In Figure 5 , we see that in the case of global support (A), the error of GANs and the other methods are comparable. In contrast, in the case of disconnected supports (B), the other standard methods show worse generalization and only GANs keep the high performance. From Figure 6 , we can see that GANs can reveal the disconnected supports, while some of the other methods fail to fit. KDE with the Gaussian kernel represents the disconnected support by employing a small bandwidth. However, the small bandwidth yields a too sharp density, tending to worsen the generalization performance. 

7. CONCLUSION:

We investigate a generalization performance of GANs with a situation such that a support of real probability measures is divided into several sets. We find that GANs do not suffer from the division of supports, while some of the other nonparametric methods loss their efficiency by the division. Since real data are often distributed on such divided supports, the finding in this paper is related to the question of why GANs perform well with real datasets.

Supplementary Materials for "Understanding GANs via disconnected Support Detection":

We introduce a new notation P f :" E X"P rf pXqs with a probability measure P and a function f . For a set Ω with equipped distance d, let N p , Ω, dq be a covering number which is a minimum number of -balls to cover Ω.

A SOME ADDITIONAL INFORMATION:

A Rigorous Definition of S α,J

We consider a set represented by a combination of multiple horizon functions, which has been used in Petersen & Voigtlaender (2017) . Given α-smooth function h P H α pI D´1 q with α ě 1, a horizon function Ψ h : I D Ñ t0, 1u is defined for some d P rDs as

Ψ h " Ψpx 1 , . . . , x d´1 , x d ˘hpx 1 , . . . , x d´1 , x d`1 , . . . , x D q, x d`1 , ..., x D q,

where Ψ is the Heaviside function; Ψpxq " 1 txPI D |x d ě0u . We define a set by the intersection of J horizon functions Ψ h1 , ..., Ψ h J ; namely the family of sets is defined by

S α,J :" S Ă r0, 1s D | 1 S " Ψ h1 b ¨¨¨b Ψ h J ( .

Intuitively, h is regarded as an α-smooth curved surface in I D , and Ψ h describes a set which is one side of the surface. Also, S P S α,J is a set which is a intersection of J sets by Ψ h1 , ..., Ψ h J .

A Support of Probability Measures:

Let N

x denote an open neighborhood of x P I D , and For a probability measure P , a support of P is defined as SupppP q :" " x P I D | P pN x q ą 0, @N x P Σ * .

B PROOFS B.1 PROOF OF LEMMA 1:

Fix m P rM s and a corresponding r S m , S m and g m . For any B P σpS m q, the definition of γ m yields

P X pBq " P Z pγ ´1 m pBqq " ż γ ´1 m pBq p Z pzqdz,

where p Z is a density function of a uniform measure P Z . By changing variables x " γ m pzq, we have

ż γ ´1 m pBq p Z pzqdz " ż B p Z pγ ´1 m pxqqJ γm pxqdx,

where J γm pxq " | det ∇g ´1 m pxq|. Using p Z pzq " 1 for all z P I D , we obtain the following form of P X pBq using a function p m : r S m Ñ S m as

EQUATION

and p m is β-smooth since γ m is β `1-smooth and bijective.

B.2 PROOF OF LEMMA 2:

Firstly, we show the first points. Suppose that g is a continuous mapping. By the generalized intermediate value theorem (Theorem 24.3 in Munkres (2000) ), we know that gpI D q is connected since I D is a connected set. Thus, a support of P g is connected. However, P g has a disconnected support, thus there is a contradiction.

B.3 PROOF OF LEMMA 3:

In this proof, a À b denotes that b is larger than a up to a finite constant. ab denotes that a À b and a Á b hold.

By the definition of tg m u mPrM s for the measure with local smoothness, we consider an explicit form of g m . By Stein (2016), we can extend g m : r S m Ñ S m to r g m : I D Ñ S m since boundaries of r S m are Lipschitz continuous. Then, we provide the following formulation r g m pxq " pγ m,1 pxq, ..., γ m,D pxqq J , where γ m,d P H β pI D q. Then, we obtain the form of g ˚as

g ˚" ÿ mPrM s r g m b 1 r Sm .

Also, by the definition of S 2β,J which contains r S m , we obtain the form

1 r Sm " â jPrJs ψ hm,j ,

with existing ψ hm,j . Then, we have

g ˚" ÿ mPrM s r g m â jPrJs ψ hm,j .

Preliminarily, we apply sub-neural networks from Yarotsky (2017) and Petersen & Voigtlaender (2017) . Let ζrΘ `s be a network for summation such that ζrΘ `spx 1 , ..., x D 1 q " ř dPrD 1 s x d , and ζrΘ ˆs be a network for approximate multiplication such as |ζrΘ ˆspx 1 , ..., x D 1 q ´śdPrD 1 s x d | ă with some ą 0 for all x, x 1 P I (Proposition 3 in Yarotsky (2017) and Lemma 1 in Imaizumi & Fukumizu (2018) ).

We consider approximation ř mPrM s γ m,d Â jPrJs ψ hm,j for each d P rDs. Let ζrΘ γ,d,m s and ζrΘ h,m,j s for d P rDs, m P rM s and j P rJs, and we will specify the networks later. Also, let ζrΘ S,m s " ζrΘ ˆspζ rΘ h,m,1 sp¨q, ..., ζrΘ h,m,1 sp¨qq.

We consider a neural network ζrΘ d s " ζrΘ `spζ rΘ ˆspζ rΘ γ,d,1 sp¨q, ζrΘ S,1 sp¨qq, ..., ζrΘ ˆspζ rΘ γ,d,M sp¨q, ζrΘ S,M sp¨qqq. Then, an approximation error is evaluated as .

› › › › › › ÿ mPrM s γ m,d â jPrJs ψ hm,j ´ζrΘ d s › › › › › › L 2 ď ÿ mPrM s › › › › › γ m,d â jPrJs ψ hm,j ´ζrΘ ˆspζ rΘ γ,d,m sp¨q, ζrΘ S,m sp¨qq › › › › › L 2 ď ÿ mPrM s › › › › › γ m,d â jPrJs ψ hm,j ´ζrΘ γ,d,m s b ζrΘ S,m s › › › › › L 2 `ÿ mPrM s › › › › ζrΘ γ,d,m s b ζrΘ S,m s ´ζrΘ ˆspζ rΘ γ,d,m sp¨q, ζrΘ S,m sp¨qq › › › › L 2 ď ÿ mPrM s › › ›γm,d b 1 r Sm ´ζrΘ γ,d,m s b ζrΘ S,m s › › › L 2 `M ď ÿ mPrM s › › ›γm,d b p1

For T 2,m , we specify ζrΘ h,m,j s as Theorem 3.1 in Petersen & Voigtlaender (2017) . Then, we evaluate the following as

}γ m,d ´ζrΘ γ,d,m s} L 2 ď › › › › › â jPrJs ψ hm,j ´ζrΘ ˆspζ rΘ h,m,1 sp¨q, ..., ζrΘ h,m,1 sp¨qq › › › › › L 2 ď › › › › › â jPrJs ψ hm,j ´â jPrJs ζrΘ h,m,j s › › › › › L 2 `› › › › › â jPrJs ψ hm,j ´ζrΘ ˆspζ rΘ h,m,1 sp¨q, ..., ζrΘ h,m,1 sp¨qq › › › › › L 2 À ÿ jPrJs ź j 1 PrJsztju ´› › ›ψh m,j 1 › › › L 2 _ }ζrΘ h,m,j 1 } L 2 ¯› › ψ hm,j ´ζrΘ h,m,j s › › L 2 ` ď ÿ jPrJs › › ψ hm,j ´ζrΘ h,m,j s › › L 2 ` ˆ.

Here, the last inequality follows the boundedness of ψ h m,j 1 and ζrΘ h,m,j s by Theorem 3.1 in Petersen & Voigtlaender (2017) . Also, Theorem 3.1 in Petersen & Voigtlaender (2017) provides an existence of rΘ h,m,j such that }ψ hm,j ´ζrΘ h,m,j s} L 2 ď }Θ h,m,j } ´β{pD´1q 1

.

We apply the boundedness of ζrΘ h,m,j s, we have

T 2,m À ÿ jPrJs }Θ h,m,j } ´β{pD´1q 1 ` ˆ.

Combining the bounds for T 1,m and T 2,m , we bound

› › › › › › ÿ mPrM s γ m,d â jPrJs ψ hm,j ´ζrΘ d s › › › › › › L 2 ď ÿ mPrM s }Θ γ,d,m } ´pβ`1q{D 1 `ÿ mPrM s ÿ jPrJs }Θ h,m,j } ´β{pD´1q 1 `pM `1q ˆ.

Here, we consider a parameter S " Yarotsky (2017) and Petersen & Voigtlaender (2017) , a proper selection of L " |Θ ˆ| and B " }Θ ˆ}8 provides ˆÀ }Θ ˆ}´β{D 0 . Then, we have

ř dPrDs }Θ d } 1 such that S -}Θ γ,d,m } 1 -}Θ h,m,j } 1 -}Θ ˆ}1 . Also, following

› › › › › › ÿ mPrM s γ m,d â jPrJs ψ hm,j ´ζrΘ d s › › › › › › L 2 À M JS ´β{D .

Since J is finite, we obtain the result.

B.4 PROOF OF THEOREM 1:

By the definition of p g in ( 2), the following inequality holds

EQUATION

for arbitrary g P G.

We consider a bound for d F pP ˚, P p g q as d F pP ˚, P

p g q " sup f PF pP ˚f ´Pp g f q " sup f PF pP ˚f ´Pn f `Pn f ´Pp g,m f `Pp g,m f ´Pp g f q ď sup f PF pP ˚f ´Pn f `Pp g,m f ´Pp g f q `sup f PF pP n f ´P 9 g,m f q,

where the inequality follows ( 9) with an existing 9 g P G. We will provide a detailed construction of g ˚. We continue the bound as

d F pP ˚, P p g q ď sup f PF pP ˚f ´Pn f `Pp g,m f ´Pp g f q `sup f PF pP n f ´P ˚f `P ˚f ´P 9 g f `P 9 g f ´P 9 g,m f q ď 2 sup gPG sup f PF |P g,m f ´Pg f | `sup f PF pP ˚f ´P 9 g f q `2 sup f PF |P n f ´P ˚f | ": i `ii `iii.

Here, i denotes an effect from m samplings, ii denotes an approximation error, and iii denotes an uncertainty with the n observations.

To evaluate i and iii, we provide the following lemma. This result follows a standard technique of the empirical process theory and we provide its outline for a sake of completeness. Lemma 4. Let H be a some set of measurable functions and X 1 , ..., X n " P be i.i.d. n observations. Suppose that E P rh 2 pXqs ď σ 2 and }h} L 8 ă C h hold with finite parameters σ 2 ą 0 and C h ą 0.

Then, there exists a constant C θ and we obtain

sup hPH ˇˇˇˇˇ1 n ÿ iPrns hpX i q ´EP rhpXqs ˇˇˇˇď inf ηą0 # 4η `12 ż C h η c log N p , H, } ¨}L 8 q n d `c 2τ σ 2 `4C θ n `τ C h n ˆ2 3 `Cθ

˙+ with probability at least 1 ´2 expp´τ q for all τ ą 0.

Proof. At the beginning, we bound an expectation of the empirical process (Steinwart & Christmann, 2008; Bartlett et al., 2005; Massart, 2000; Sriperumbudur et al., 2012) . Afterward, we evaluate a concentration of the empirical process around the expectation.

By applying the symmetrization and concentration techniques (Proposition 7.10 in Steinwart & Christmann ( 2008)), we obtain

E P bn » -sup hPH ˇˇˇˇˇ1 n ÿ iPrns hpX i q ´ErhpXqs ˇˇˇˇˇfi fl ď 2E P bn bν bn » -sup hPH ˇˇˇˇˇ1 n ÿ iPrns u i hpX i q ˇˇˇˇˇfi fl ,

where u i " ν is the Rademacher variable which takes 0 or 1 with probability 0.5. Combining this bound with the Taralgand's inequality (Theorem A.9.1 in Steinwart & Christmann (2008) ), we obtain the following inequality

EQUATION

with probability at least 1 ´expp´τ q for all τ ą 0 and θ ą 0.

About the term with the Rademacher variable, we also apply a similar strategy (Lemma A.4 in Bartlett et al. ( 2005)), then obtain

EQUATION

with probability at least 1 ´expp´τ 1 q for all τ 1 ą 0 and θ 1 ą 0.

Let } ¨}n be an empirical norm as }f } 2 n " n ´1 ř iPrns f pX i q 2 . About the term E ν bn " sup hPH ˇˇ1 n ř iPrns u i hpX i q ˇˇı, we apply the chaining technique and obtain

EQUATION

where the last inequality follows a bound for an empirical norm and the boundedness of H.

Combining ( 10), ( 11) and ( 12) and changing variables, we obtain the result.

To bound I with r X 1 , ..., r X m " P g , we consider the following value where we define H " th " f ˝g | f P F, g P Gu. To apply Lemma 4, we investigate a covering number N p , H, } ¨}L 8 q. Lemma 5. Assume that f P F is L 1 -Lipschitz continuous. We obtain log N p , H, } ¨}L 8 q ď log N pp1 `L1 q ´1 , G, } ¨}L 8 q `log N pp1 `L1 q ´1 , F, } ¨}L 8 q Proof. Fix ą 0. Let G Ă G and F Ă F be covering sets as a set of centers of -balls for the covering G and F. Obviously, |G| " N p , G, } ¨}L 8 q and |F | " N p , F, } ¨}L 8 q. We define a subset For any h P H, there exist g P G and f P F, then f " f ˝g holds. Also, by the definition of covering sets, there exist f 1 P F and g 1 P G such that }f ´f 1 } L 8 ď and }g ´g1 } L 8 ď . Let h 1 " f 1 ˝g1 , and we measure the distance }h ´h1 } L 8 ď }f ˝g ´f 1 ˝g1 } L 8

" }f ˝g ´f ˝g1 `f ˝g1 ´f 1 ˝g1 } L 8 ď }f ˝g ´f ˝g1 } L 8 `}f ˝g1 ´f 1 ˝g1 } L 8

ď L 1 }g ´g1 } L 8 `}f ´f 1 } L 8 ď pL 1 `1q .

Here, the third inequality follows the Lipschitz property of f P F. Here, we know that H is covered by pL 1 `1q -balls with the center H. Since |H| " |G| ˆ|F |, the result holds. Now, we have the following entropy bound log N p , H, } ¨}L 8 q ď log N pp1 `L1 q ´1 , G, } ¨}L 8 q `log N pp1 `L1 q ´1 , F, } ¨}L 8 q ď pS g `1q logp2pL 1 `1q ´1pL g `1qD g B g q `min " pS f `1q logp2pL 1 `1q ´1pL f `1qD f B f q, C κ p1 `L1 q ´κ* with D g :" ś PrLg`1s pD `1q and D f :" ś PrL f `1s pD `1q. Let Γ f :" 2pL f `1qD f B f , and N p r Fq :" log N p , r F, } ¨}n q for brevity. Here, we apply Lemma 8 in Schmidt-Hieber (2017) for the entropy bound for G and F. Using the entropy bound and Lemma 4, we obtain

EQUATION

with some η ą 0, A 1 " 12 log 1{2 Γ f , A 2 " C r F log 1{2 C r F `p2τ σ 2 `Cθ q 1{2 , and A 3 " τ C h p2{3 Cθ q. Also, we set Υ n p r

Fq " 4η `12

n 1{2 ş C Ă F

η N pL1`1q ´1 p r Fq 1{2 d . Then, we have

EQUATION

)

About I, we define Γ g :" 2pL f `1qD g B g and obtain a similar bound as

i ď Υ m p r Fq `1 m 1{2 ´pS g `1q 1{2 A 1 1 `A1 2 ¯`A 1 3 m ,

where A 1 1 " 12plog 1{2 Γ f `log 1{2 Γ g q, A 2 " C r F log 1{2 C r F `CG log 1{2 C G `2p2τ σ 2 `Cθ q 1{2 , and A 3 " 2τ C h p2{3 `Cθ q.

About ii, we evaluate the error from approximation by constructing a specific deep neural network for generators. We apply Lemma 3 and let 9 g " p 9 g 1 , ..., 9 g D q be a generator specified in Lemma 3.

ii 

:



Figures and Tables:

Figure 5: Generalization errors.

Figure 6: Estimated density functions with the case (B).

˝g | g P G, h P F * Ă H, and we known |H| " |G| ˆ|F |.

Each of the terms I, II and III has the following role: I bounds an error by the m samplings, II bounds an error from approximation by G, and III bounds an error by n observations.

Table content: <table><tr><td colspan="4">Proof Outline: By the definition of P g in (2) and standard calculation, we obtain the inequality p</td></tr><tr><td>d F pP ˚, P g q ď 2 sup p</td><td>sup</td><td>ˇľoooooooooooooooooooooooomoooooooooooooooooooooooon ˇˇE Pg,m rf pXqs ´EPg rf pXqs</td><td>`inf</td></tr><tr><td>gPG</td><td>f PF</td><td/><td/></tr><tr><td/><td/><td>":i</td><td/></tr></table>

Sm ´ζrΘ S,m sq `pγ m,d ´ζrΘ γ,d,m sq b ζrΘ S,m s `}γ m,d ´ζrΘ γ,d,m s} L 2 }ζrΘ S,m s} L 8 `M ":where the last inequality follows the Hölder's inequality.About T 1,m , there exists a corresponding ζrΘ γ,d,m s such that }γ m,d ´ζrΘ γ,d,m s} L 2 À }Θ γ,d,m }

Table content: <table><tr><td/><td/><td/><td>´pβ`1q{D 1</td><td>,</td></tr><tr><td colspan="4">by following Theorem A.8 in Petersen &amp; Voigtlaender (2017). Also, since γ m,d is bounded by its</td></tr><tr><td colspan="4">smoothness and compact support, we have }γ m,d } L 8 ă 8 hence</td></tr><tr><td/><td/><td colspan="2">´pβ`1q{D T 1,m À }Θ γ,d,m } 1</td></tr><tr><td/><td/><td/><td>›</td></tr><tr><td/><td/><td/><td>› › L 2 `M ď</td></tr><tr><td>ÿ</td><td/><td>›</td><td>›</td></tr><tr><td>mPrM s</td><td>}γ m,d } L 8</td><td colspan="2">› ›1 Sm ´ζrΘ S,m s r › › L 2</td></tr><tr><td>ÿ</td><td/><td/></tr><tr><td/><td colspan="2">T 1,m `T2,m `M ˆ,</td></tr><tr><td colspan="2">mPrM s</td><td/></tr></table>

" P g ˚f ´P 9 g f

Table content: <table><tr><td>ż</td><td/><td/><td/><td/></tr><tr><td>"</td><td colspan="4">pf ˝g˚´f ˝9 gqdP Z</td></tr><tr><td/><td/><td>ż</td><td/><td/></tr><tr><td colspan="2">ď L 1</td><td colspan="3">}g ˚´9 g} 2 dP Z</td></tr><tr><td colspan="2">ď L 1</td><td>¨ÿ dPrDs</td><td>ż</td><td>|g d pxq ´9 g d pxq| 2 dP Z pxq</td><td>‚1{2</td></tr><tr><td colspan="2">" L 1</td><td>¨ÿ dPrDs</td><td colspan="2">}g d ´9 g d } 2 L 2</td></tr></table>

Peer review (iclr2019):
 The paper provides some bounds on the generalization performance of GANs for approximating distributions with discontinuous support. This work relies heavily on the results shown in [1] and [2] on the approximation power of Deep networks for non-smooth functions. The paper is globally well written and the proof seems sound. However, the experiments could be more convincing and the relevance of the result is questionable: - By choosing the function class F to the be L_1-lipschitz, the resulting error bound loses it’s dependence on the smoothness beta and becomes slightly worse than the classical methods (equation 7 with kappa = 2+2D). Is this an artifact of the proof? if that is the case, it would be good to have a tighter bound: [3] might be a good starting point. - Neural networks used in practice are continuous usually, but it seems that all the analysis is all based on the fact that distributions with disjoint support require discontinuous networks. Can similar results be obtained in the more realistic case of continuous networks? Also what network architecture was used in the experiments? - Although the bound in eq (5) clearly shows a tradeoff for S_g it only says that S_f should be as small as possible. Of course, if S_f =0 there is no discriminative power, but it’s unclear to me how the expression for S_f in eq (6) can be obtained from (5) and why it would keep the discriminative power (in what sense?). Again, this tradeoff was discussed in prior work [3], so it might be worth looking into that direction. - The discussion right after lemma 1 doesn*t seem to be true: a distribution might have disjoint support and still have a density (i.e.: absolutely continuous with respect to the Lebesgue measure). It can even have a smooth density. - The experiment doesn’t use the same metric to compare GANs method with other methods, so it is unclear how these methods compare. Moreover, figure 6 seems to show that other methods are also able to get the support right (Kernel E). Based on what could we claim that one method is better than the other? Revision: Thank you for your response. > In fact, our estimator in the theoretical and experimental analysis employs a continuous (ReLU) network. Though discontinuous networks are necessary for our setting (Lemma 2), we show that (continuous) ReLU networks can approximate the discontinuous network effectively (Lemma 3), hence the effectiveness of GANs is proved (Theorem 1). -That clarifies things, however I find that the discussion after lemma 2 rather missleading, if in the end the result ends up using continuous generator: "Because of the discontinuity, generative models with smooth functions, such as an adversarial generative model with kernel generators (Sinn & Rawat, 2018), cannot work well with disconnected supports." - It is still unclear to me how the optimal value of S_f is obtained from eq (5). The author points out the work by Zhang+ (2018), but this should be clarified in the current version of the paper: What result in Zhang+(2018) do you use to get this value? - I find the experiments not very convincing. I understand that the point is not to show that GANs are better than other methods but it is important to be make meaningful compairisons (use comparable scores) otherwise there is little scientific value in figure 5 especially. - As reviewer 1 mentions, lemma 3 is supposed to be one of the main theoretical contributions of the paper, however, the proof seems very similar to the one in ([2], appendix B.1). Although the authors mention lemma 1 of [2] in the proof of lemma 3, it seems like the whole section in ([2] appendix B.1) is dedicated to show the very same result. For all these reasons I still wouldn*t recommend accepting this paper. [1]: Yarotsky. Error bounds for approximation with deep relu networks. [2]: Massaki Imaizumi, Kenji Fukumizu. Deep neural networks learn non-smooth functions effectively. [3]: P. Zhang, Q. Liu, D. Zhou, T. Xu, and X. He. On the Discrimination-Generalization Tradeoff in GANs.