While Generative Adversarial Networks (GANs) have empirically produced impressive results on learning complex real-world distributions, recent works have shown that they suffer from lack of diversity or mode collapse. The theoretical work of Arora et al. (2017a) suggests a dilemma about GANs’ statistical properties: powerful discriminators cause overfitting, whereas weak discriminators cannot detect mode collapse.
 By contrast, we show in this paper that GANs can in principle learn distributions in Wasserstein distance (or KL-divergence in many cases) with polynomial sample complexity, if the discriminator class has strong distinguishing power against the particular generator class (instead of against all possible generators). For various generator classes such as mixture of Gaussians, exponential families, and invertible and injective neural networks generators, we design corresponding discriminators (which are often neural nets of specific architectures) such that the Integral Probability Metric (IPM) induced by the discriminators can provably approximate the Wasserstein distance and/or KL-divergence. This implies that if the training is successful, then the learned distribution is close to the true distribution in Wasserstein distance or KL divergence, and thus cannot drop modes. Our preliminary experiments show that on synthetic datasets the test IPM is well correlated with KL divergence or the Wasserstein distance, indicating that the lack of diversity in GANs may be caused by the sub-optimality in optimization instead of statistical inefficiency. In the past few years, we have witnessed great empirical success of Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) in generating high-quality samples in many domains. Various ideas have been proposed to further improve the quality of the learned distributions and the stability of the training. (See e.g., BID0 Odena et al., 2016; Huang et al., 2017; Radford et al., 2016; Tolstikhin et al., 2017; Salimans et al., 2016; Jiwoong Im et al., 2016; Durugkar et al., 2016; Xu et al., 2017) and the reference therein. ) However, understanding of GANs is still in its infancy. Do GANs actually learn the target distribution? Recent work (Arora et al., 2017a; b; Dumoulin et al., 2016) has both theoretically and empirically brought the concern to light that distributions learned by GANs suffer from mode collapse or lack of diversity -the learned distribution tends to miss a significant amount of modes of the target distribution (elaborated in Section 1.1). The main message of this paper is that the mode collapse can be in principle alleviated by designing proper discriminators with strong distinguishing power against specific families of generators such as special subclasses of neural network generators (see Section 1.2 and 1.3 for a detailed introduction.) We present the first polynomial-in-dimension sample complexity bounds for learning various distributions (such as Gaussians, exponential families, invertible neural networks generators) using GANs with convergence guarantees in Wasserstein distance (for distributions with low-dimensional supports) or KL divergence. The analysis technique proceeds via designing discriminators with restricted approximability -a class of discriminators tailored to the generator class in consideration which have good generalization and mode collapse avoidance properties.We hope our techniques can be in future extended to other families of distributions with tighter sample complexity bounds. This would entail designing discriminators that have better restricted approximability bounds, and generally exploring and generalizing approximation theory results in the context of GANs. We hope such explorations will prove as rich and satisfying as they have been in the vanilla functional approximation settings. DISPLAYFORM0 Taking expectation overp n on the above bound yields DISPLAYFORM1 So it suffices to bound Epn [W F (p,p n )] by 2R n (F, G) and the same bound will hold for q. Let X i be the samples inp n . By symmetrization, we have DISPLAYFORM2 Adding up this bound and the same bound for q gives the desired result.B PROOFS FOR SECTION 3 B.1 PROOF OF THEOREM 3.1Recall that our discriminator family is DISPLAYFORM3 Restricted approximability The upper bound W F (p 1 , p 2 ) ≤ W 1 (p 1 , p 2 ) follows directly from the fact that functions in F are 1-Lipschitz.We now establish the lower bound. First, we recover the mean distance, in which we use the following simple fact: a linear discriminator is the sum of two ReLU discriminators, or mathematically t = σ(t) − σ(−t). Taking v = µ1−µ2 µ1−µ2 2, we have DISPLAYFORM4 Therefore at least one of the above two terms is greater than µ 1 − µ 2 2 /2, which shows that DISPLAYFORM5 For the covariance distance, we need to actually compute DISPLAYFORM6 (Defining R(a ) = E[max {W + a, 0}] for W ∼ N(0, 1).) Therefore, the neuron distance between the two Gaussians is DISPLAYFORM7 As a → max {a + w, 0} is strictly increasing for all w, the function R is strictly increasing. It is also a basic fact that R(0) = 1/ √ 2π.Consider any fixed v. By flipping the sign of v, we can let v µ 1 ≥ v µ 2 without changing Σ DISPLAYFORM8 As R is strictly increasing, for this choice of (v, b) we have DISPLAYFORM9 Ranging over v 2 ≤ 1 we then have DISPLAYFORM10 The quantity in the supremum can be further bounded as DISPLAYFORM11 . DISPLAYFORM12 Now, using the perturbation bound (cf. (Schmitt, 1992 , Lemma 2.2)), we get DISPLAYFORM13 DISPLAYFORM14 Combining the above bound with the bound in the mean difference, we get DISPLAYFORM15 The last equality following directly from the closed-form expression of the W 2 distance between two Gaussians (Masarotto et al., 2018, Proposition 3) . Thus the claimed lower bound holds with c = 1/(2 √ 2π).
GANs can in principle learn distributions sample-efficiently, if the discriminator class is compact and has strong distinguishing power against the particular generator class. Proposes the notion of restricted approximability, and provides a sample complexity bound, polynomial in the dimension, which is useful in investigating lack of diversity in GANs. Analyzes that the Integral Probability Metric can be a good approximation of Wasserstein distance under some mild assumptions.