Year: 2021

Abstract:
Arguably the most fundamental question in the theory of generative adversarial networks (GANs) is to understand when GANs can actually learn the underlying distribution. Theoretical and empirical evidence (see e.g. (Arora et al., 2018)) suggests local optimality of the empirical training objective is insufficient. Yet, it does not rule out the possibility that achieving a true population minimax optimal solution might imply distribution learning. In this paper, we show that standard cryptographic assumptions imply that this stronger condition is still insufficient. Namely, we show that if local pseudorandom generators (PRGs) exist, then for a large family of natural target distributions, there are ReLU network generators of constant depth and poly size which take Gaussian random seeds so that (i) the output is far in Wasserstein distance from the target distribution, but (ii) no polynomially large Lipschitz discriminator ReLU network can detect this. This implies that even achieving a population minimax optimal solution to the Wasserstein GAN objective is likely insufficient for distribution learning in the usual statistical sense. Our techniques reveal a deep connection between GANs and PRGs, which we believe will lead to further insights into the computational landscape of GANs.

heading: 1 INTRODUCTION
text: When will a generative adversarial network (GAN) trained with samples from a distribution D actually output samples from a distribution that is close to D? This question is one of the most foundational questions in GAN theory—indeed, it was raised since the original paper introducing GANs. However, despite significant interest, this question still remains to be fully understood for general classes of generators and discriminators.
A significant literature has developed discussing the role of the training dynamics (Liu et al., 2017; Li et al., 2018; Arora et al., 2018; Berard et al., 2019; Wiatrak et al., 2019; Thanh-Tung & Tran, 2020; Allen-Zhu & Li, 2021), as well as the generalization error of the GAN objective (Zhang et al., 2017; Arora et al., 2017; Thanh-Tung et al., 2019). In most cases, researchers have demonstrated that given sufficient training data, GANs are able to learn some specific form of distributions after successful training. Underlying these works appears to be a tacit belief that if we are able to achieve the minimax optimal solution to the population-level GAN objective, then the GAN should be able to learn the target distribution. In this work, we take a closer look at this assumption.
What does it mean to learn the target distribution? As a starting point, we must first formally define what we mean by learning a distribution; more concretely, what do we mean when we say that two distributions are close? The original paper of (Goodfellow et al., 2020) proposed to measure closeness with KL divergence. However, learning the target distribution in KL divergence is quite unlikely to be satisfied for real-world distributions. This is because learning distributions in KL divergence also requires us to exactly recover the support of the target distribution, which we cannot really hope to do if the distribution lies in an unknown (complicated) low-dimensional manifold. To rectify this, one may instead consider learning in Wasserstein distance, as introduced in the context of GANs by (Arjovsky et al., 2017), which has no such “trivial” barriers. Recall that the Wasserstein distance between two distributions D1,D2 over Rd is given by
W1(D1,D2) = sup Lip(f)1 ED1 [f ] ED2 [f ] ,
where for any f : Rd ! R, we let Lip(f) denote the Lipschitz constant of f . That is, two densities are close in Wasserstein distance if no Lipschitz function can distinguish between them. In this work we will focus on Wasserstein distance as it is the most standard notion of distance between probability distributions considered in the context of GANs.
Note that if the class of discriminators contains sufficiently large neural networks, then minimax optimality of the GAN objective does imply learning in Wasserstein distance. This is because we can approximate any Lipschitz function arbitrarily well, with an exponentially large network with one hidden layer (see e.g. (Poggio et al., 2017)). Thus, in this case, minimizing the population GAN objective is actually equivalent to learning in Wasserstein distance. Of course in practice, however, we are limited to polynomially large networks for both the generator and the discriminator. This raises the natural question:
Does achieving small error against all poly-size neural network discriminators imply that the
poly-size generator has learned the distribution in Wasserstein distance?
One might conjecture that this claim is true, since the generator is only of poly-size. Thus, using a (larger) poly-size discriminator (as opposite to the class of all 1-Lipschitz functions) might still be sufficient to minimize the actual Wasserstein distance. In this paper, however, we provide strong evidence to the contrary. We demonstrate that widely accepted cryptographic assumptions imply that this is false, even if the generator is of constant depth: Theorem 1.1 (Informal, see Theorem 3.1). For any n 2 N, let n be the standard Gaussian measure over Rn. Assuming local pseudorandom generators exist, the following holds for any sufficiently large m 2 Z, d, r  poly(m), and any diverse1 target distribution D⇤ over [0, 1]d given by the pushforward of the uniform distribution Ir on [0, 1]r by a constant depth ReLU network of polynomial size/Lipschitzness: 2
There exist generators G : Rm ! Rd computed by (deterministic) ReLU networks of constant depth and polynomial size for which no ReLU network of polynomial depth/size/Lipschitzness can tell apart the distributions G( m) and D⇤, yet G( m) and D⇤ are ⌦(1)-far in Wasserstein distance.
While Theorem 1.1 pertains to the practically relevant setting of continuous seed and output distributions, we also give guarantees for the discrete setting. In fact, if we replace D⇤ and m by the uniform distributions over {±1}d and {±1}m, we show this holds for generators whose output coordinates are given by constant-size networks (see Theorem 3.2).
We defer the formal definition of local pseudorandom generators (PRGs) to Section 2.2. We pause to make a number of remarks about this theorem.
First, our theorem talks about the population loss of the GAN objective; namely, it says that the true population GAN objective is small for this generator G, meaning that for every ReLU network discriminator f of polynomial depth/size/Lipschitzness, we have that
|E[f(D⇤)] E[f(G( m))]|  1
d!(1) .
In other words, our theorem states that even optimizing the true population minimax objective is insufficient for distribution learning. In fact, we show this even when the target distribution can be represented perfectly by some other generative model.
Second, notice that our generator is extremely simple: notably, it is only constant depth. On the other hand, the discriminator is allowed to be much more complex, namely any ReLU network of polynomial complexity. This discriminator class thus constitutes the most powerful family of functions we could hope to use in practice. Despite this, we show that the discriminators are still not powerful enough to distinguish the output of the (much simpler) generator from the target distribution.
Third, our conclusions hold both for d m and d  m, so long as the input and output dimensions are related by polynomial factors.
1See Definition 6. In the discussion proceeding this definition, we give a number of examples making clear that this is a mild and practically relevant assumption to make.
2When we say “polynomial,” we are implicitly referring to the dependence on the parameter m, though because d, r are bounded by poly(m), “polynomial” could equivalently refer to the dependence on those parameters if they exceeded m.
Finally, we formally define the class of “diverse” target distributions for which our conclusions hold in Section 2.3. We note that this class is quite general: for instance, it includes pushforwards of the uniform distribution under random leaky ReLU networks (see Lemma 2.3).
Empirical results. To complement these theoretical results, we also perform some empirical validations of our findings (see Section 4). Our theorem is constructive; that is, given a local PRG, we give an explicit generator which satisfies the theorem. We instantiate this construction with Goldreich’s PRG with the “Tri-Sum-And” (TSA) predicate (Goldreich, 2011), which is an explicit function which is believed to satisfy the local PRG property. We then demonstrate that a neural network discriminator trained via standard methods empirically cannot distinguish between the output of this generator and the uniform distribution. While of course we cannot guarantee that we achieve the truly optimal discriminator using these methods, this still demonstrates that our construction leads to a function which does appear to be hard to distinguish in practice.
GANs, PRGs, and circuit lower bounds. At a high level, our results and techniques demonstrate surprising and deep connections between GANs and more “classical” problems in cryptography and complexity theory. Theorem 1.1 already shows that cryptographic assumptions may pose a fundamental barrier to the most basic question in GAN theory. In addition to this, we also show a connection between this question and circuit lower bounds. In the supplementary material, we show that if we are able to unconditionally exhibit generators which can fool polynomially large ReLU network discriminators, then we would obtain breakthrough circuit lower bounds against TC0 (see Theorem C.2 and Remark C.3). This complements Theorem 1.1, as it says that if we can unconditionally construct generators which fool realistic discriminators, then we make progress on long-standing questions in circuit complexity. We believe that exploring these connections may be crucial to achieving a deeper understanding of what GANs can and cannot learn.

heading: 1.1 RELATED WORK
text: GANs and Distribution Learning The literature on GAN theory is vast and we cannot hope to do it full justice here. For a more extensive review, see e.g. (Gui et al., 2020). Besides the previously mentioned work on understanding GAN dynamics and generalization, we only mention the most relevant papers here. One closely related line of work derives concrete bounds on when minimax optimality of the GAN objective implies distribution learning (Bai et al., 2018; Liang, 2018; Singh et al., 2018; Uppal et al., 2019; Chen et al., 2020a; Schreuder et al., 2021). However, the rates they achieve scale poorly with the dimensionality of the data, and/or require strong assumptions on the class of generators and discriminators, such as invertability. Another line of work has demonstrated that first order methods can learn very simple GAN architectures in polynomial time (Feizi et al., 2017; Daskalakis et al., 2017; Gidel et al., 2019; Lei et al., 2020). However, these results do not cover many of the generators used in practice, such as ReLU networks with > 1 hidden layers.
Local PRGs and Learning PRGs have had a rich history of study in cryptography and complexity theory (see e.g. (Vadhan, 2012)). From this literature, the object most relevant to the present work is the notion of a local PRG. These are part of a broader research program of building constant parallel-time cryptography (Applebaum et al., 2006). One popular local PRG candidate was suggested in (Goldreich, 2011). By now there is compelling evidence that this candidate is a valid PRG, as a rich family of algorithms including sum-of-squares (ODonnell & Witmer, 2014) and statistical query algorithms (Feldman et al., 2018) provably cannot break it.
Finally, we remark that Goldreich’s PRG and, more generally, hardness of refuting random CSPs have been used in a number of works showing hardness for various supervised learning problems (Daniely & Vardi, 2021; Daniely et al., 2014; Daniely, 2016; Daniely & Shalev-Shwartz, 2016; Applebaum et al., 2006; Applebaum & Raykov, 2016). We consider a very different setting, and our techniques are very different from the aforementioned papers.

heading: 2 TECHNICAL PRELIMINARIES
text: Notation Denote by Un the uniform distribution over {±1}n, by n the standard n-dimensional Gaussian measure, and by In the uniform measure on [0, 1]n. Given distribution D over Rm and measurable function G : Rm ! Rd, let G(D) denote the distribution over Rd given by the push-
forward of D under G—to sample from the pushforward G(D), sample x from D and output G(x). Given : R ! R and vector v 2 Rd, denote by (v) 2 Rd the result of applying entrywise to v. To avoid dealing with issues of real-valued computation, let R⌧ ⇢ R be the set of multiples of 2 ⌧ bounded in magnitude by 2⌧ .

heading: 2.1 GANS AND PSEUDORANDOM GENERATORS
text: In this section we review basic notions about generative models and PRGs. Definition 1 (ReLU Networks). Let CL,S,d denote the family of ReLU networks F : Rd ! R of depth L and size S. Formally, F 2 CL,S,d if there exist weight matrices W1 2 Rk1⇥d,W2 2 Rk2⇥k1 , . . . ,WL 2 R1⇥kL 1 and biases b1 2 Rk1 , b2 2 Rk2 . . . , bL 2 R such that
F (x) , WL (WL 1 (· · · (W1x+ b1) · · · ) + bL 1) + bL,
and PL 1
i=1 ki = S, where (z) , max(0, z) is the ReLU activation. Additionally, we let C ⌧,⇤ L,S,d
be the subset of such networks which are additionally ⇤-Lipschitz and whose weight matrices and biases have entries in R⌧– we will refer to ⌧ as the bit complexity of the network.
The following allows us to control the complexity of compositions of ReLU networks: Lemma 2.1. Let J : Rs ! Rr be a function each of whose output coordinates is computed by some network in C⌧1,⇤1L1,S1,s, and let f 2 C ⌧2,⇤2 L2,S2,r . Then f J 2 C⌧,⇤L,S,s for ⌧ = max(⌧1, ⌧2), ⇤ = ⇤1⇤2 p r, L = L1 +L2, and S = (S1 + 1)r+ S2. Furthermore, for the network in C⌧,⇤L,S,s realizing f J , the bias and weight vector entries in the output layer lie in R⌧2 .
Next, we formalize the probability metric we will work with. Definition 2 (IPM). Given a family F of functions, define the F-integral probability metric between two distributions p, q by WF (p, q) = supf2F |Ey⇠p[f(y)] Ey⇠q[f(y)]|. When F consists of the family of 1-Lipschitz functions, this is the standard Wasserstein-1 metric, which we denote by W1.
In the context of GANs, we will focus on discriminators given by ReLU networks of polynomial size, depth, Lipschitzness, and bit complexity: Definition 3 (Discriminators). F⇤ denotes the set of all sequences of discriminators fd : Rd ! R, indexed by d 2 N, whose size, depth, Lipschitzness, bit complexity grow at most polynomially in d.
We now formalize the definition of GANs, which closely parallels the definition of PRGs. Definition 4 (GANs/PRGs). Let ✏ : N ! [0, 1] be an arbitrary function, and let {d(m)}m2N be some sequence of positive integers. Given a sequence of seed distributions {Dm}m over Rm, a sequence of target distributions {D⇤d(m)} over Rd(m), a family F of discriminators f : Rd(m) ! R, and a sequence of generators Gm : Rm ! Rd(m), we say that {Gm} ✏-fools F relative to {D⇤d(m)} with seed {Dm} if for all sufficiently large m,
E[f(Gm(Dm))] E[f(D⇤d(m))]  ✏(m) 8f 2 F , f : Rd(m) ! R. (1)
Note that in the notation of Definition 2, (1) is equivalent to WF (Gm(Dm),D⇤d(m))  ✏(m).3
In this definition, if the discriminators and generators were instead Boolean functions, we would refer to {Gm} as pseudorandom generators. Remark 2.2. It will often be cumbersome to refer to sequences of target/seed distributions and discriminators/generators as in Definitions 3 and 4, so occasionally we will refer to a single choice of m and d even though we implicitly mean that m and d are parameters that increase towards infinity. In this vein, we will often say that a single network f is in F⇤, though we really mean that f belongs to a sequence of networks which lies in F⇤. And for distributions p, q which implicitly belong to sequences {pd}, {qd}, when we refer to bounds on WF⇤(p, q) we really mean that for any sequence of discriminators fd 2 F⇤, |E[fd(pd)] E[fd(qd)]| is bounded.
3Here we are slightly abusing notation as F contains functions which have domain not equal to Rd(m), and we ignore these functions in the supremum.

heading: 2.2 LOCAL PSEUDORANDOM GENERATORS
text: In complexity theory, the role of neural network discriminators is played by Boolean circuits, which one can roughly think of as networks which take in Boolean strings as input and whose activations are logical operations (e.g. AND/OR/NOT) rather than ReLUs (see Section A.2 in the supplement).
It is widely believed that there exist so-called local PRGs capable of fooling all polynomial-sized Boolean circuits and all of whose output coordinates are functions of a constant number of input coordinates (Applebaum et al., 2006). One prominent candidate is Goldreich’s PRG: Definition 5 ((Goldreich, 2011)). Let H be a collection of d subsets S1, . . . , Sd of {1, . . . ,m}, each of size k and each sampled independently from the uniform distribution over subsets of {1, . . . ,m} of size k. Let P : {±1}k ! {±1} be a Boolean function; P is often referred to as a predicate. Let GP,H : {±1}m ! {±1}d denote the Boolean function whose `-th output coordinate is computed by evaluating P on the coordinates of the input indexed by subset S` in H .
The following is a standard assumption in cryptography (see (Applebaum, 2016)), namely that the incredibly simple functions in Definition 5 fool all Boolean circuits of polynomial size: Assumption 1. For any c > 1, there exists k 2 N and P : {±1}k ! {±1} such that for m sufficiently large, with probability 1 om(1) over the randomness of H in Definition 5, the function G = GP,H negl(m)-fools all polynomial-size Boolean circuits relative to Umc with seed Um for some negligible function negl : N ! [0, 1].4

heading: 2.3 DIVERSE DISTRIBUTIONS
text: Recall that the main result of this paper is to construct generators that look indistinguishable from natural target distributions D⇤ according to any poly-sized neural network, but which are far from D⇤ in Wasserstein. In this section we describe in greater detail the properties that these D⇤ satisfy. Definition 6. A distribution µ over Rd is (N, )-diverse if for any discrete distribution ⌫ on Rd supported on at most N points, W1(µ, ⌫) .
The main fact we use about (N, )-diverse distributions is that they cannot be approximated by pushforwards of Ulog2 N (see Lemma A.12 in the supplement for a formal statement).
Note that Definition 6 is a very mild assumption that simply requires that the distribution not be tightly concentrated around a few points. Distributions that satisfy Definition 6 are both practically relevant and highly expressive. For starters, any reasonable real-world image distribution will be diverse as it will not be concentrated around a few unique images. One can also show that distributions like uniform distributions over well-separated discrete point sets and over [0, 1]d are diverse (Lemma A.13 and Lemma A.15 in supplement). Definition 6 also captures random expansive neural networks with leaky ReLU activations: Lemma 2.3 (Random expansive leaky ReLU networks). For k0, . . . , kL 2 N satisfying ki 1.1ki 1 for all i 2 [L], let W1 2 Rk1⇥k0 ,W2 2 Rk2⇥k1 , . . . ,WL 2 RkL⇥kL 1 be random weight matrices, where every entry of Wi is an independent draw from N (0, 1/ki). For the function F : Rk0 ! RkL given by F (x) , WL (WL 1 (· · · (W1x) · · · )), where (z) = (z) = z/2 + (1/2 )|z| is the leaky ReLU activation, F (Ik0) is (2m, )-diverse for m = (k0/2) log(k0/2) kL/1.1 1 and = ⇥( )L with probability at least 1 exp( ⌦(d)).
For example, if , L = ⇥(1), then F (Ik0) is (2 ⌦(k0 log k0),⌦(1))-diverse for k0 sufficiently large.
It is easy to see that the networks in Lemma 2.3 can be implemented as ReLU networks, so our main theorem applies to target distributions given by pushing the uniform distribution over the continuous cube through a random expansive leaky ReLU network of constant depth.

heading: 3 FOOLING RELU NETWORK DISCRIMINATORS DOES NOT SUFFICE
text: In this section we will show that even though a generative model looks indistinguishable from some target distribution D⇤ according to any ReLU network in F⇤, it can be quite far from D⇤ in Wasser-
4g : N ! R 0 is negligible if for every polynomial p, g(n) < |1/p(n)| for all sufficiently large n.
stein. We begin by describing a simple version of this result over discrete domains in Section 3.1. In Section 3.2 we extend this to target distributions over continuous domains, but where the generator still takes in a discrete-valued seed. Finally, in Section 3.3 we give a simple reduction that extends these results to give generators that take in a continuous-valued random (Gaussian) seed, culminating in the following main result: Theorem 3.1. Let {Hm}m be a sequence of generators Hm : Rr(m) ! Rd(m) for r(m), d(m)  poly(m) whose output coordinates are computable by networks in C⌧
0(m),⇤0(m) L0(m),S0(m),r(m)
for ⌧ 0(m),⇤0(m)  poly(m). Suppose that Hm(Ir(m)) is (2m,⌦(1))-diverse.
Fix any ✏ : N ! [0, 1] satisfying ✏(m) max(negl(m), exp( O(m)). Under Assumption 1, there is a sequence of generators Gm : Rm ! Rd(m) such that for all m sufficiently large:
1. Every output coordinate of Gm is computable by a network in C⌧,⇤L,S,m for
⌧ = max(O(log(⇤0(m) ·m ·d(m)/✏(m))), ⌧ 0(m), O(1)), ⇤ = O(⇤0(m)2poly(m)/✏(m)),
L = L0(m) +O(1), S = O(r(m) log(1/✏(m))) + 3m+ S0(m).
2. WF⇤(Gm( m), Hm(Ir(m)))  ✏(m)·poly(m), 3. W1(Gm( m), Hm(Ir(m))) ⌦(1).
Note that a natural choice of parameters for Hm would be
⌧ 0(m)  O(logm), ⇤0(m), S0(m), 1/✏(m)  poly(m), L0(m)  O(1).
(In fact, the poly(m) factor in bullet point 2 simply comes from the Lipschitzness of Hm, so ✏(m) only needs to scale inversely in this quantity for WF⇤ to be small.) Altogether, we conclude that Gm’s output coordinates are computable by constant-depth ReLU networks with polynomial size and Lipschitzness and logarithmic bit complexity ⌧ .

heading: 3.1 STRETCHING BITS TO BITS
text: As a warmup, in this subsection we prove the following special case of Theorem 3.1 when the target distribution and seed distribution are discrete. Theorem 3.2. Under Assumption 1, for any constant c > 1, there is a sequence of generators Gm : Rm ! Rd(m) for d(m) mc such that for all m,
1. Every output coordinate of Gm is computable by a network in C⌧,⇤L,S,m for ⌧,⇤, L, S = Oc(1).
2. WF⇤(Gm(Um), Ud(m))  negl(m), 3. W1(Gm(Um), Ud(m)) ⌦(1).
We emphasize that in this discrete setting, our quantitative guarantees are even stronger: all parameters ⌧,⇤, L, S of the generator are constant, and no polynomial-sized ReLU network can distinguish between Gm(Um) and Ud(m) with even non-negligible advantage.
As discussed in the introduction, a basic but important building block in the proof of Theorem 3.2 is the connection between Goldreich’s PRG and generative models computed by neural networks of constant depth/size/Lipschitzness. We begin by elaborating on this connection and showing that any predicate {±1}k ! {±1} can be implemented as a network in C⌧,⇤L,S,d where ⌧,⇤, L, S = Ok(1). As a consequence of known constructions for implementing Boolean functions with ReLU networks (see e.g. Lemma A.2 of (Chen et al., 2020b)), we can show: Corollary 3.3. For any k 2 N and any H and P as in Definition 5, the coordinates of the output of GP,H are computed by networks in C⌧,⇤L,S,m for ⌧ = O(k),⇤ = exp(O(k)), L = k, S = O(2kk).
Before we use this to prove Theorem 3.2, we need an extra technical ingredient to formalize the fact that a discriminator given by a ReLU network of polynomially bounded complexity yields a discriminator computable by a polynomial-sized Boolean circuit. The idea is that if WF⇤ is large so that there exists some ReLU network discriminator, then because the input to the discriminator is sufficiently well concentrated, some affine threshold of the ReLU network can distinguish between the two distributions:
Lemma 3.4. Given independent X and Y such that E[Y ] E[X] = ↵ and for which X E[X] and Y E[Y ] are 2-sub-Gaussian, there exists a threshold t 2 [E[X] O( p log( /|↵|)),E[Y ] + O( p log( /|↵|))] for which |P[X > t] P[Y > t]| min ⇣ 1/2, e⌦(|↵|/ ) ⌘ .
We can now sketch the proof of Theorem 3.2, deferring a formal argument to the supplement.
Proof sketch of Theorem 3.2. The parameter m will be clear from context in the following discussion, so for convenience we will refer to d(m) and Gm as d and G. Let k, P,G, negl(·) be such that the outcome of Assumption 1 holds. By Corollary 3.3, every output coordinate of G is computable by a network in C⌧,⇤L,S,m for ⌧ = O(k),⇤ = exp(O(k)), L = k, S = O(2kk).
The fact that W1(G(Um), Ud) > 1/3 follows from the fact that G(Um) is uniform over 2m points on the hypercube (with multiplicity), and Ud is (2m, 1/3)-diverse.
It remains to check that G fools F⇤ relative to Ud. Suppose to the contrary that there exists some f : Rd ! R in F⇤ for which |E[f(G(Um))] E[f(Ud)]| > d a for some constant a > 0. Note that for any threshold t 2 R⌧ , there is a Turing machine M⌧ : {±1}d ! {±1} that computes y 7! sgn(f(y) t) using ⌧ bits of advice. By applying Lemma 3.4 to random variables X = f(G(Um)) and Y = f(Ud), we get that there exists a threshold t 2 Rpoly(d) for which |E[M⌧ (G(Um))] E[M⌧ (Ud)]| > 1/poly(d), contradicting Assumption 1.

heading: 3.2 FROM BINARY OUTPUTS TO CONTINUOUS OUTPUTS
text: In this section we show how to extend Theorem 3.2 to the setting where the target distribution D⇤ is a pushforward of the uniform distribution on [0, 1]r. At a high level, the idea will be to post-process the output of the generator constructed in Theorem 3.2. Roughly speaking, we take weighted averages of clusters of output coordinates from the generator in Theorem 3.2 and pass these averages through the pushforward map defining D⇤. Formally, we show: Theorem 3.5. Let {Hm}m be a sequence of generators Hm : Rr(m) ! Rd(m) for r(m), d(m)  poly(m) whose output coordinates are computable by networks in C⌧
0(m),⇤0(m) L0(m),S0(m),r(m)
for ⌧ 0(m),⇤0(m)  poly(m). Suppose that Hm(Ir(m)) is (2m,⌦(1))-diverse.
Fix any ✏ : N ! [0, 1] satisfying ✏(m) max(negl(m), exp( O(m)). Under Assumption 1, there is a sequence of generators Gm : Rm ! Rd(m) such that for all m sufficiently large:
1. Every output coordinate of Gm is computable by a network in C⌧,⇤L,S,m for
⌧ = max(O(log(1/✏(m))), ⌧ 0(m), O(1)), ⇤ = O(⇤0(m)) · poly(m), L = L0(m) +O(1), S = O(r(m) · log(1/✏(m))) + S0(m).
2. WF⇤(Gm(Um), Hm(Ir(m)))  ✏(m) · poly(m), 3. W1(Gm(Um), Hm(Ir(m))) ⌦(1).
Theorem 3.5 retains many of the nice properties of Theorem 3.2, e.g. it can tolerate distinguishing advantage ✏(m) which is negligible, at the mild cost of an extra logarithmic dependence on 1/✏(m) in the bit complexity ⌧ . And as with Theorem 3.1, if the networks Hm are of constant depth, the resulting generators Gm are also of constant depth.
To prove Theorem 3.5, we begin by showing that for any pair of distributions which are close under the WF metric for some family of neural networks F , their pushforwards under a simple generative model will still be close under the WF 0 metric for some slightly weaker family of networks F 0. Lemma 3.6. Fix parameters ⇤,⇤0 > 1. Let F = C⌧,⇤L,S,s. If WF (p, q)  ✏ for some distributions p, q on Rs, then for any J : Rs ! Rr each of whose output coordinates is computed by a function in C⌧,⇤ 0
L0,S0,s for some L 0 < L and S0  S r 1r , we have WF 0(J(p), J(q))  2✏⇤ 0pr for F 0 = C⌧
0,⇤ L L0,S00,r where ⌧ 0 = ⌧ dlog2 ⇤ p re and S00 = S r(S0 + 1).
Now recall that in Theorem 3.2, we exhibited a GAN which is close in WF⇤ to Us. Using Lemma 3.6, we can show that a certain simple pushforward of this GAN will be close in WF⇤ to the uniform distribution over [0, 1]r for r slightly smaller than s. The starting point is the following:
Fact 3.7. For any 0 < ✏ < 1 and n log2(1/✏), let h : Rn ! R be given by h(x) = hw, x + 1i for w = 1/4, 1/8, . . . , (1/2)n+1 and 1 the all-1’s vector. Then W1(h(Un), I1)  ✏.
By leveraging Lemma 3.6 and Fact 3.7, we can get an approximation to the uniform distribution over [0, 1]r out of the uniform distribution over {±1}s: Lemma 3.8. Suppose ✏ > 0 satisfies log(1/✏)  poly(s). If a distribution eD over Rs satisfies WF⇤( eD, Us)  ✏, then for r , s/dlog(1/✏)e,5 there is a function J : Rs ! Rr each of whose output coordinates is computed by a function in CO(log(1/✏)),O(1)1,0,s such that WF⇤(J( eD), Ir)  ✏ · poly(r).
By further combining Lemma 3.6 and Lemma 3.8, we can thus extend the latter from the uniform distribution on [0, 1]r to simple pushforwards thereof. Lemma 3.9. Under the hypotheses of Lemma 3.8, for any d  poly(s) and any function H : Rr ! Rd each of whose output coordinates is computed by a function in C⌧ 0,⇤0
L0,S0,r for ⌧ 0  poly(s),
there is a function J 0 : Rs ! Rd each of whose output coordinates is computed by a function in Cmax(O(log(1/✏)),⌧ 0),O(⇤0 p d)
L0+1,r+S0,s such that WF⇤(J 0( eD), H(Ir))  ✏⇤0 · poly(s).
So for any pushforward H(Ir) of the uniform distribution on [0, 1]r, Lemma 3.9 lets us take the GAN given by Theorem 3.2 and slightly post-process its output so that it is close in WF⇤ to H(Ir). We can now sketch Theorem 3.5’s proof, deferring the full argument to the supplement.
Proof of Theorem 3.5. Condition 3 follows because G(Um) is a uniform distribution on 2m points (w/ multiplicity) and H(Ir) is (2m,⌦(1))-diverse. Next, let s = r · dlog(1/✏)e. As we are assuming ✏ exp( O(m)), s  r · m = mc for some constant c > 1. Take G0 to be the generator G : Rm ! Rs constructed in Theorem 3.2. By applying Lemma 3.9 to eD = G0(Um), we get a function J 0 : Rs ! Rd each of whose output coordinates is computed by a function in Cmax(O(log(1/✏)),⌧ 0),O(⇤0 p d)
L0+1,r+S0,s such that WFd(J 0(G0(Um)), H(Ir))  ✏⇤0 · poly(m)  ✏ · poly(m), so we get condition 2 of the theorem for G , J 0 G0. Finally, by Lemma 2.1, every output coordinate of G can be realized by a network in C⌧,⇤L,S,m for ⌧ = max(O(log(1/✏)), ⌧ 0, O(1)), ⇤ = O(⇤0 p ds) = O(⇤0) · poly(m), L = L0 +O(1), and S = O(s) + r+ S0 = O(s) + S0 (where we used the fact that r = s/dlog(1/✏)e < s). This establishes condition 1 of the theorem.

heading: 3.3 FROM BINARY INPUTS TO CONTINUOUS INPUTS
text: In Theorem 3.5, we have shown how to go from Um to any simple pushforward Hm(Ir(m)) of the uniform distribution over [0, 1]r(m). Here we complete the proof of our main result, Theorem 3.1, by giving a simple reduction showing how to use Gaussian seed m instead of Um. At a high level, the idea will be to pre-process the inputs to the generator constructed in Theorem 3.5 by appending appropriate activations at the input layer. We will need the following elementary construction. Lemma 3.10. For any ⇠ for which 1/⇠ 2 R⌧ , the piecewise linear function h⇠ which outputs 1 for inputs x  ⇠, 1 for x ⇠, and x/⇠ otherwise, lies in C⌧,1/⇠2,2,1 .
The function h⇠ will let us approximately convert from m to Um. Specifically, the following says that if we want to approximate the output distribution of the generator in Theorem 3.5 using Gaussians instead of bits as seed, it suffices to attach entrywise applications of h⇠ at the input layer: Lemma 3.11. Let G0 : Rm ! Rd have output coordinates computable by networks in C⌧ 00,⇤00
L00,S00,m00 .
For any ✏ > 0, let ⇠0 , ✏/ ⇣ ⇤00 p (2/⇡)m3d ⌘ and let ⇠ bethe multiplicative inverse of d1/⇠0e.
The function G : Rm ! Rd given by G(x) = G0(h⇠(x)), where h⇠(x) denotes entrywise application of h⇠ defined in Lemma 3.10, satisfies that 1) each of the output coordinates of G is computable by a network in C⌧,⇤L,S,m for the parameters ⌧ = max(⌧ 00, O(log(⇤00md/✏))), ⇤ = O(⇤00 2m2 p d/✏), L = L00 + 2, and S = 3m+ S00, and 2) W1(G0(Um), G( m))  ✏. 5We will assume for simplicity that this is an integer, though it is not hard to handle the case where dlog(1/✏)e does not divide s.
Remark 3.12. Note the only fact we use about m in the proof of Lemma 3.11 is that outside of an event with probability O(m⇠), h⇠( m) is uniform over {±1}m. In particular, the same would hold for any product measure each of whose coordinates is symmetric and anticoncentrated around zero. For instance, up to a constant factor in ⇠0, Lemma 3.11 also holds with m replaced by Im.
Proof of Theorem 3.1. Substitute the generator constructed in Theorem 3.5, call it G0, into Lemma 3.11; let G be the generator resulting from the lemma. Recall from Theorem 3.5 that each output coordinate of G0 lies in C⌧ 00,⇤00 L00,S00,m for ⌧ 00 = max(O(log(1/✏)), ⌧ 0, O(1)), ⇤00 = O(⇤0poly(m)), L00 = L0 + O(1), S00 = O(r log(1/✏)) + S0. So by Lemma 3.11, every output coordinate of G is computable by a network in C⌧,⇤L,S,m for ⌧ = max(⌧ 00, O(log(⇤0md/✏))) = max(O(log(⇤md/✏)), ⌧ 0, O(1)), ⇤ = O(⇤002m2 p d/✏) = O(⇤02poly(m)/✏), L = L00 + 2 = L0 +O(1), and S = 3m+ S00 = O(r log(1/✏)) + 3m+ S00.

heading: 4 EXPERIMENTAL RESULTS
text: To empirically demonstrate the existence of a constant depth generator that can fool polynomiallybounded discriminators, we evaluated the generator G given by Goldreich’s PRG (Goldreich, 2011) with input dimension m = 50, output dimension d = 200, and predicate P : {±1}5 ! {±1} given by the popular TSA predicate, namely P (x1, . . . , x5) = x1 · x2 · x3 · (x4 ^ x5). This is the smallest predicate under which Goldreich’s candidate construction is believed to be secure.
The target distribution D⇤ is the uniform distribution U200 over {±1}200. As we prove in Lemma A.13, Ud is sufficiently diverse that W1(G(Um), Ud) ⌦(1). We trained four different discriminators given respectively by 1, 2, 3, 4 hidden-layer ReLU networks, where each hidden layer is fully connected with dimensions 200 ⇥ 200, to discriminate the output of the generator G(Um) from the target distribution Ud. We used the Adam optimizer with step size 0.001 over the DCGAN training objective, with batch-size 128. As we can see in Figure 1, the test loss E[ log(D(X))]+E[ log(1 D(G(z)))] 2 log(2) stays consistently above zero, indicating that the discriminator can not discriminate the true distribution from the generator output, even though the Wasserstein distance between these two distributions is provably large.

heading: 5 CONCLUSIONS
text: In light of the obstructions presented in this paper, what are natural next steps for the theory of GANs? Here, we offer a couple of thoughts and possible future directions.
One limitation of our lower bound is that it holds for a specific generator. Of course, it is quite unlikely that we will ever encounter such a generator through natural GAN training. One way to circumvent our lower bound is to argue that the training dynamics of the generator may have some regularization effect which allows us to avoid these troublesome generators, and which allows GANs to learn distributions in polynomial time.
Another orthogonal perspective is that our results suggest that perhaps statistical learning is too strong of a goal. If our GAN is indeed indistinguishable from the target distribution to all polynomial time algorithms, then not only should the output of the GAN be sufficient for humans, but it should also be sufficient for all downstream applications, which presumably run in polynomial time. This raises the intriguing possibility that the correct metric for measuring closeness between distances in the context of GANs should inherently involve some computational component (e.g. in the sense of Dwork et al. (2021)) as opposed to the purely statistical metrics generally considered in the literature.

Review summaries:
This paper studies the problem of learning generative adversarial networks using a ploy-size ReLU generator and discriminator under the standard Wasserstein-1 metric. The main result is that there exists a "bad" generator that can cheat all discriminators under the estimation of the Wasserstein-1 metric while being far from the data distribution under the true Wasserstein-1 metric. The proof relies on two assumptions. The first one is on the diversity of the target data distribution. The second one is a standard assumption in cryptography as claimed by this paper while I'm not familiar with cryptography. The results explicitly consider the computation complexity of the model and may show the learnability of the GAN model in some sense.