Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs
Authors: Sitan Chen
Jerry Li
Yuanzhi Li
Raghu Meka
Venue: ICLR 2022 Poster (2022)
Keywords: theory of GANs
distribution learning
pseudorandom generators
cryptography

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-Risteski-Zhang '18) suggest 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. Our techniques reveal a deep connection between GANs and PRGs, which we believe will lead to further insights into the computational landscape of GANs.

Published as a conference paper at ICLR 2022
MINIMAX OPTIMALITY (PROBABLY) DOESN'T T IMPLY DISTRIBUTION LEARNING FOR GANS
Sitan Chen UC Berkeley
Jerry Li Microsoft Research
Yuanzhi Li CMU
Raghu Meka UCLA
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) sug- gests local optimality of the empirical training objective is insufficient. Yet, it does not rule out the possibility that achieving a true population minimax optimal solu- tion might imply distribution learning. In this paper, we show that standard cryp- tographic assumptions imply this stronger condition still insufficient. Namely, we show that if local pseudorandom generators (PRGs) exist, then for large fam- ily of natural target distributions, there are ReLU network generators of constant depth and poly size which take Gaussian random seeds 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 objec- tive 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 further insights into the computational landscape of GANs.
INTRODUCTION
When will generative adversarial network (GAN) trained with samples from a distribution D actu- ally output samples from distribution that is close to D? This question one of the most founda- tional questions in GAN theory-indeed, it was raised since the original paper introducing GANs. However, despite significant interest, this question still remains be fully understood for general classes of generators and discriminators.
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 Allen-Zhu & L. 2021) 1) as well as the generalization error the GAN objective (Zhang et al,, Arora al. 2017 Thanh-
2020
2017
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 be tacit belief that if we able to achieve the minimax optimal solution to the population-level GAN objective, then the GAN should be able learn the target distribution. In this work, take a closer look this assumption.
What does it mean to learn the target distribution? As starting point, we must first formally define what we mean by learning distribution; more concretely, what do two distributions are close? The original paper of (Goodfellow et al. 2020) proposed to measure closeness with KL divergence. However, learning the target distribution KL divergence is quite unlikely to be satisfied for real-world distributions. This is because learning distributions in KL divergence also requires to exactly recover the support of the target distribution, which we cannot really hope to do if the distribution lies in an unknown (complicated) oiw-iiensional manifold. To rectify this, one may instead consider learning in Wasserstein distance, as introduced in the context of GANs by (Arjovsky al. (017)) which has no such "trivial" barriers. Recall that the Wasserstein distance between two distributions D1, D2 over Id is given by
when we say that
Wi (Di,
sup Ep, Ifl Ep, Lip(f)1

---

Published as a conference paper at ICLR 2022
where for any f R R, let Lip(f) denote the Lipschitz constant of That is, two densities are close Wasserstein distance if no Lipschitz function can distinguish between them. In this work we will focus Wasserstein distance 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 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 I-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 E N, let "n be the standard Gaussian mea- sure over R Assuming local pseudorandom generators exist, the following holds for any suffi- ciently large m E L, d,r S. (oly(m), and any diverse" target distribution D over [0, 1] given by the pushforward of the uniform distribution L, on [0, 1|" by a constant depth ReLU network of polynomial Stz/Lipschitzzess:
There exist generators G 1m + Fd computed by (deterministic) ReLU networks of constant depth and polynomial size for which no ReLU network of polynomial depptusize/Liisschirzees can tell apart the distributions G(7m)) and DD" yer G(7i)) and D are 12(1)-far in Wasserstein distance.
While Theorem 1.1 pertains to the practically relevant setting of continuous seed and output dis- tributions, we also give guarantees for the discrete setting. In fact, we replace D and 7m by the uniform distributions over [=1]d and {=1}", show this holds for generators whose output coordinates are given by constant-size networks (see Theorem 3.2p.
We defer the formal definition of local pseudorandom generators (PRGs) to Section 2.2 to make a number of remarks about this theorem.
We pause
First, 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 of polynomial depth/Size/Lipscchttness
we have that
- (EF(((()))))
-
(1(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 allowed to be much more complex, namely any ReLU network of poly- nomial 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 2 m and d < m, so long as the input and output dimensions related by polynomial factors.
See Definition 6 In the discussion proceeding this definition, we give number of examples making clear that this mild and practically relevant assumption to make.
WWhe we say "polynomial." we are implicitly referring to the dependence on the parameter m. though because d,y r are hounded by poly(m), "polynomial" could equivalently refer to the dependence those pa- rameters if they exceeded
2

---

Published as a conference paper at ICLR 2022
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 vali- dations 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 Goldre- ich's '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 dis- criminator 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 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 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 TC (see Theorem C.2 and Remark C.3 This complements Theorem 1.1 as it says that we can unconditionally construct generators which fool realistic discriminators, then make progress on long- stag-itaningg questions in circuit complexity. We believe that exploring these connections may be crucial to achieving deeper understanding of what GANs can and cannot learn.
1.1 RELATED WORK
GANs and Distribution Learning The literature on GAN theory vast and we cannot hope to do it full justice here. For more extensive review, see e.g. GGui 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. 2020al Schreuder et al. (021). 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 complex- ity theory (see e.g. (Vadhan 2012)) From this literature, the object most relevant to the present work is the notion of local PRG. These are part of a broader research program of building constant parallel-time cryptography (Applebaum et al., (006)) One popular local PRG candidate was sug- gested in (Goldreich) 2011). 1). By now there is compelling evidence that this candidate is a valid PRG, as a rich family of algorithms including sum-of-squne of--uue (ODonnell & Witmer 2014) and statistical query algorithms (Feldman 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 number of works showing hardness for various supervised learning problems (Daniely & Vardi, 202I; Daniely et al.) 2014 Daniely] 2016), Daniely & Shalev-Shie -Swaar-S 2016 Applebaum et al. [2066] Applebaum & Raykov 2016). We consider a very different setting, and our techniques are very different from the aforementioned papers.
2 TECHNICAL PRELIMINARIES
Notation Denote by Un the uniform distribution over {+1)". by 2n the standard n-dimensional Gaussian measure, and by In the uniform measure on [0, 1]".. Given distribution D over RT and measurable function G R IRd, let G(D) denote the distribution over Ied given by the push-
3

---

Published as a conference paper at ICLR 2022
forward of D under G sample from the pushforward G(D), sample from D and output G(x)).
Given a : IR + R and vector E IR,, denote by a(v) E R the result of applying o entrywise to v. To avoid dealing with issues of real-valued computation, let R, I be the set of multiples of 2 2- bounded magnitude by 2".
2.1 GANS AND PSEUDOR ANDOM GENERATORS
In this section we review basic notions about generative models and PRGs.
Definition 1 (ReLU Networks). Let CL,S,d d.d denote the family of ReLU networks F RR R of depth L and size S. Formally, F CL.S.d if there exist weight matrices W1 E Rixd W2 Blank
WL E IR 1glki and biases b1 E IR by E IR22 ...,bL meta...,ba R such that
F(x) WLO (W L-10 (... (W b1)....) bL-1) +b,,
and E(=1 Ki = S, where d(2) & max(0, 2) is the ReLU activation. Additionally, we let CT.AA be the subset of such networks which are additionally A-Lipschitz and whose weight matrices and biases have entries in - we will refer to the bit complexity of the network.
L,S,d
The following allows us to control the complexity of compositions of ReLU networks:
Lemma 2.1. Let J : + R' be a function each of whose output coordinates is computed by some network in
CTa.A1 S1,s,, and let f E CT2.A2 L2,7 Then f J E CT-A L = max(T1, T2), A1A2 L1+ + L2, and S= (S1 + 1)r + Sz. Furthermore, for the network in CT. realizing f J, the bias and weight vector entries in the output layer lie in Ryy.
Next, we formalize the probability metric will work with.
Definition 2 (IPM). Given a family F of functions, define the F-integral probability metric between two distributions p. q by Wy(p. q) sup supper[Ey=pp family of --ipschitz functions, this is the standard Wasserstein-1 metric, which we denote by W,.
1f (y)ll. When consists of the
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 Sa Ted - RR indexed by d E N, whose size, depth, Lipschitzness, bit complexity grow at most polynomially d.
We now formalize the definition of GANs, which closely parallels the definition of PRGs.
Definition 4 (GANs/PRGss. Let e N [0, 1] be an arbitrary function, and let {d((m) be some sequence of positive integers. Given a sequence of seed distributions {Dm }m over I." sequence of target distributions (Dam))) over (Rdim), a family of discriminators f Rd(m) + IR
and a sequence of generators Gm R + gd(m), we say that {Gm} e-fools FF relative to (Di(m))
with seed {Dm}} } for all sufficiently large m,
(D - E[f((" & e(() Vf efe,, FfeF Rd))) + R.
(I)
Note that in the notation of Definition is equivalent to (G Dism)) I <(m)
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 refer sequences of target/seed distributions and discriminattor//eeeraaoo as in Definitions 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 belongs sequence of networks which lies in F= And for distributions p, q which implicitly belong to sequences {pu}. {qd}. when we refer to bounds on W (p. g) we really mean that for any sequence discriminators la E F*, [E[S(paa) - E[[a(ga]] is bounded.
Here are slightly abusing notation F contains functions which have domain not equal to Rd(m), and ignore these functions in the supremum.
4

---

Published as a conference paper at ICLR 2022
2.2 LOCAL PSEUDORANDON GENERATORS
In complexity theory. the role of neural network diseriminators is played by Boolean circuits, which one can roughly think of networks which take in Boolean strings input and whose activations are logical operations (e.g. AND/OR/NOT) rather than ReLUs (see Section A.2 in the supplement).
widely believed that there exist so-called local PRGs capable of fooling all polynomial-sin Boolean circuits and all of whose output coordinates are functions of constant number of input coordinates (Applebaum et al. 2006). One prominent candidate Goldreich's PRG:
Definition ((Goldreich) 2011). Let H be collection of d subsets Si...., Sa of {1,... m), each of size and each sampled independently from the uniform distribution over subsets of (I...., m}
size k. Let P: {+1} + {+1} be a Boolean function; P is often referred to as a predicate.
Let G.. : {#1)m + {=1]d denote the Boolean function whose f-th output coordinate is com- puted by evaluating P on the coordinates of the input indexed by subset Se in H.
The following is standard assumption in cryptography (see (Applebaum) 2016)), namely that the incredibly simple functions in Definition fool all Boolean circuits of polynomial size:
Assumption 1. For any > 1, there exists k- E N and P [+1]* & (+1} such that for m sufficiently large, with probability 0m (1) over the randomness of H in Definition the function G G.. h negl(m))fools all polynomial-sie Boolean circuits relative Um with seed Um for some negligible function negl: N > [0,
2.3 DIVERSE DISTRIBUTIONS
Recall that the main result of this paper is to construct generators that look indistinguishable from natural target distributions D" according any poly-sized neural network, but which are far from DD in Wasserstein. In this section we describe in greater detail the properties that these DD satisfy. Bd
Definition 6. A distribution μ over Rdd is (N, -iveerse if for any discrete distribution supported on at most N points, W Wp,
B.
The main fact we use about (N, BN,.8e-ivverss distributions is that they cannot be approximated by pushforwards of Ulug, (see Lemma A.12 in the supplement for formal statement).
Note that Definition 6 is very mild assumption that simply requires that the distribution not be tightly concentrated around 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 distri- butions like uniform distributions over well-separated discrete point sets and over [0, 1] diverse (Lemma A.13 Lemma A.155in supplement). Definition also captures random expansive neural networks with leaky ReLU activations:
Lemma 2.3 (Random expansive leaky ReLU networks). For No....,,kt KT. E N satisfying k; 2 1.1k for all dom weight matrices, where every entry of W, s is an independent draw from NOO, 1/ki). For the function F Ro + Be given by F(x) & WL (W (.../// (WWW)) W.z)...)). where ()x(=) = (x(=) = z/2 + (1/2 - A)|z| is the leaky ReLU activation, F(Tea) (2mh (2m,;)) -i-viree for m (ko/ /2) log ko/ -1/1111 - and 3 (())= with probubility at least exx(-Q((d),
[4]. let W1 Rh xka, W2 Rk2xkı ...., WL IRLiXLL- be ran-
For example, i L (1), then ((T..)) is (2 log ka), ((1)) (dii))ddvverse diverse for ko sufficiently large.
It is easy see that the networks in Lemma 2.3 can be implemented 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.
FOOLING RELU NETWORK DISCRIMINATORS DOES NOT SUFFICE
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-
9 N Rgo negligible if for every polynomial p. g(m) [1/r(n)] for all sufficiently large
5

---

Published as a conference paper at ICLR 2022
stein. We begin by describing simple version of this result over discrete domains in Section 3.1 In Section [.22 we extend this to target distributions over continuous domains, but where the gen- erator still takes in discrete-valued seed. Finally, in Section 3.3 we give simple reduction that extends these results to give generators that take in continuous-valued random (Gaussian) seed, culminating in the following main result:
Theorem 3.1. Let {Hm}m be a sequence of generators Hm : -R((m))
Rd(m)) for
r(m), r(m) & (mly(m) whose output coordinates are computable by networks in C (m).X'(m) (mm), A (m) I poly(m). Suppose that (m(()(m)) (2"h, (2(())))1)))))))) diverse
("(m)
Fix any N [0,1] satisfying <(m) 2 max(neg)m)), (m)(-))m)). Under Assumption there is sequence of generators G. IIRm Idd(m) such that for all sufficiently large:
Every output coordinate of Gm computable by a network in CT, L.
= max(O(log({ AA' (m) m (m)
A O(A((m) poly(m)/c(m))) (0)((mm)p))((()m((mm)
L'mm) O(1),
S= 5=0(r())log(L/(mm))) + 3m ('m)..
2. Wy- (mm (7mm), Hm (mm))) s <(m))-oly(m))
3. W1 (G Hm Hm((r(m))) 2(11).
Note that a natural choice of parameters for Hm, would be
('m) I O(log m)) (m(m),5'mm) (m()) s poly(m), I'(m) S O())
(In fact, the (oly(m) factor in bullet point 2 simply comes from the Lipschitzness of Hm. so (mm only needs to scale inversely in this quantity for W5- to be small.) Altogether, we conclude that Gm's 's output coordinates are computable by constant-depth ReLU networks with polynomial size and Lipschitzness and logarithmic bit complexity T.
3.1 STRETCHING BITS TO BITS
As 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 [ for any constant e there is a sequence of generators
Gm R + Rd(m)) for d(m)) 2 m such that for all m,
1. Every output coordinate of G. is computable by a network in CLA for T, =
2. Wx. (Gm (Um), U'd(m)) S. negl(m).
3. W1 (G (mm), Ud(m) 2 Q(1).
We emphasize that in this discrete setting, our quantitative guarantees are even stronger: all parame- ters T, A, L, S of the generator are constant, and no polynomial-sized ReLU network can distinguish between (Um)))) m 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 's PRG and generative models computed by neural networks of constant deptt/size/Lipssciineess We begin by elaborating this connection and showing that any predicate { {+1}* * > (+1) can be implemented
network in CT.A where т, A, L, (1). As 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 Gr.H are computed by networks CT.A LLS.m = O(k),
and any H and as in Definition the coordinates of the output of exp(O(())) k. -(th)))
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 discriminator computable by polynomial-siee siizei Boolean circuit. The idea is that if W 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:

---

Published as a conference paper at ICLR 2022
Lemma 3.4. Given independent X and Y such that E[Y] - -[ and which X E[X] and Y Y are Pe-sub-Gaussiann there exists threshold t [ O(a (oglo//al)), BV]] +
O(1 / logía/ [ol))] for which | t]
P|Y t]| 2 min (1/2, (
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 discus- sion, so for convenience we will refer to d(m) and Gm as d and G. Let k, P. G, (-) be such that the outcome of Assumption I holds. By Corollary 3.3 every output coordinate of G' computable L.S.m
by a network in CT.A for = O(k), A exp(O(k)); L= k ())*
The fact that Wi (G((U,). on the hypercube (with multiplicity), and Ua is 10/),113divennm
(. Ua) > 1/3 follows from the fact that G(Um) is uniform over 2nd points
remains to check that G fools F relative to Ua- Suppose to the contrary that there exists some f: Fd + R in F for which [Bf(G(Um)) E[f(U))]] d= for some constant >> 0. Note that for any threshold E R, there is a Turing machine M, - {+1} that computes y H (gv( t) using r bits of advice. By applying Lemma 3.4 to random variables X = (U(()))
-
and = f(aa). we get that there exists a threshold E (ooty(d) for which [E(M,(G(Umm))
B[M,(Ua)) > 1 1/poly(d), contradicting Assumption [
3.2 FROM BINARY OUTPUTS TO CONTINUOUS OUTPUTS
In this section we show how to extend Theorem 3.2 the setting where the target distribution D is
pushforward of the uniform distribution on [0, 1 at high level, the idea will be to post-procens the
output of the generator constructed in Theorem 3.2 Roughly speaking, take weighted averages
of clusters of output coordinates from the generator in Theorem33.2)
pass these averages through
the pushforward map defining D Formally, we show:
Theorem 3.5. Let { be a sequence of generators Hm IB(()) r(m), I poly(m) whose ousput coordinates are computable by networks in c (m) L'
Rd(m)) for
f'm) A' (mm I poly(m). Suppose that Hml(f((m) is (2 ddvveee
Fix any e: N + [o. 1] satisfying e(m) 2 (mx(negl()) exp(-O Under Assumption is sequence of generators Gm IR -> dRd(()) such that for all m sufficiently large:
there
1. Every output coordinate of Gm is computable by a network in CT, for
T max (aolllg((////mm/ (c((m))), 0(1))
A O poly(m), log(1/((m))) + (mm).
== [mmm) ((), $ (r(mm
Wy (Um) (4m) S <(m) (oly(m).
3. Wi (G Hm (Ir())) 2 2(1).
Theorem 3.5 retains many of the nice properties of Theorem 3.2 e.g. it can tolerate distinguishing advantage e(m) which is negligible, at the mild cost of an extra logarithmic dependence on 1/e(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 W5 metric for some family of neural networks F, their pushforwards under simple generative model will still be close under the W5 metric for some slightly weaker family of networks F'.
Lemma 3.6. Fix parameters A, N' > 1. Let F CLS.s" If WFv(p q) S for some distributions p, q on IR, then for any J R= + R' each of whose output coordinates is computed by function in CT.N" .s some L' L and S < 8-r-1, we have (J())()) J(a)) < 2e 2e /F for F
CT A y where T' = [log2 A/r and S" r(S' + 1
Now recall that in Theorem 3.2 exhibited GAN which is close in WF- to U.. Using
Lemma we can show that a certain simple pushforward of this GAN will be close in W,+ to the uniform distribution over [0, 1]" for slightly smaller than The starting point is the following:
7

---

Published as a conference paper at ICLR 2022
Fact 3.7. For any 0 < < and n (1/c), let h: R" - R be given by h(x) = (w, + 1)
for w (1/4,)8......1)/))))))) (1/2)=tt) and the all-I's vector. Then (U()(Un): J1 S.
By leveraging Lemma 3.6 and Fact 3.7 we can get an approximation to the uniform distribution over [0, 1J" out of the uniform distribution over {+1}²:
Lemma 3.8. Suppose
0 satisfies log(L/e) S poly(s). Ifa distribution D over R satisfies Wy (D,(D,U)) S c. tthe for a s/[og[1//e]] there is function J : :R - RR" each of whose outpur coordinates is computed by a function in C1,0.
(og(L)))))00)) such that Wy. (J(D), I,) S c 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]" to simple pushforwards thereof.
Lemma 3.9. Under the hypotheses of Lemma 3.8 for any d S poly(s) and any function H : F- + Rd each of whose output coordinates is computed by a function in C xr T' S poly(s), there is a function J' : IR. + Re each of whose oulput coordinates is computed by a function in ),) such that W (J'(D) S EA' poly(s). C 1--1,++
So for any pushforward HII,) of the uniform distribution on [0, 1J", Lemma 3.9 lets us take the GAN given by Theorem 3.2 and slightly post-process its output that it is close W5- to (T.).
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 2 points (w/ multiplicity) and (I,,) is (2 (iv))-diverse Next, let = r [log[1/e]] As we are as- S r. m m for some constant e > 1. Take G" to be the gen- erator G 1 + IR* constructed in Theorem 3.2 By applying Lemma 3.9 to D = -G"(mm) get a function J' IR* IR each of whose output coordinates is computed by fuucciion in
suming e 2 exp( exp(-O(m)),
(max((((og(()e))))))))))) /d) such that WF, (J((""))))) (I,)) I cA' poly(m) I <oooy(m),
so we get condition 2 of the theorem for G - J' o G.. Finally, by Lemma 2.1 every output coordinate of G can be realized by a network in CT.A L.S.m for T ma))
= dds) = O(A) (oly(m). ), L = L' + O(1), and S = 0(s) +r S' = (s)) + (where used the fact that s/ [og (1/c)] < s). This establishes condition of the theorem.
3.3
FROM BINARY INPUTS TO CONTINUOUS INPUTS
In Theorem 3.5 we have shown how to go from Um to any simple pushforward Hm (4r(m) of the uniform distribution over (0, 1]((m), Here 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 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/C E R, the piecewise linear function hę which outputs 1 for L/E inputs z < -, 1 for x 2 E, and z/ otherwise, lies in 2,2.1
The function lgg will let us approximately convert from Tm to Un. 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 hg at the input layer:
Lemma 3.11. Let Go R. + Rd have output coordinates computable by networks in Ci" AA"
8"
For any e > O, let 5¹ 2 c/ (22((2m)) and let & bethe multiplicative inverse of [1/g",
The function G Immm + R given by G(x) = Go (x)), where he(x) denotes entrywise applica- tion of hig defined in Lemma satisfies that 1) each of the output coordinates of computable by a network in CT.A L.S.m. for the parameters T = max(7" O(log(A (A"md/c)), A = O m2 (d/c),
L. = I." + 2, and S = 3m + S", and 2) W1 (Go G(Tm) S.
'We will assume for simplicity that this is an integer, though it is not hard to handle the case where [o](1)ee] does not divide
8

---

Published as a conference paper at ICLR 2022
Remark 3.12. Note the only fact event with probability ((mE), hg (7m) 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 g', Lemma also
about 7/ in the proof of Lemma 3.11 is that outside of an
also holds with 7m replaced by Im-
Proof of Theorem 3.7 Substitute the generator constructed in Theorem 3.5 call Go. into
Lemma 3.11 let G be the generator resulting from the lemma. Recall from Theorem 3.5 that c=" each output coordinate of Go lies in s" m for 7" max(O(log(L/e)) T', O(1), A" O ((A'pol(mm)), L" L' + O(1), s" = (rrlo((/e)) + S'. So by Lemma 3.11 every out- put coordinate G is computable by a network CTAA L.S.m for T = max(7", ((log(A (A'dd/)))/)) poly(m)()))) mdd/))))
max(O(log( (Amooommmmmmmmmm////// (())) A L' + O(1), and S = 3m + S" Or (og(/c) + 3m S".
I" +
4 EXPERIMENTAL RESULTS
To empirically demonstrate the existence of a constant depth generator that can fool polynomially- bounded discriminators, we evaluated the generator G' given by Goldreich's ' PRG (Goldreich) 2011))
with input dimension m = 50, output dimension = 200, and predicate P: {=1f - (#1} given by the popular TSA predicate, namely P(z1.... Fς) = I1 I2 2y (Iq A k5)). This is the smallest predicate under which Goldreich's ' candidate construction believed to be secure.
The target distribution D is the uniform distribution U200 over [=1]200. As prove in Lemma AA.13 Ua is sufficiently diverse that W (G(G(U)) 2 Q(1). We trained four differ- discriminators given respectively by 2, 3,4 hidden-layer ReLU networks, where each hid- den layer is fully connected with dimensions 200 x 200, to discriminate the output of the gener- ator 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 | the test loss El- Bl-log(D(C)) (D)()(X))] E|- log(1 ((G()))) 2 log(2) (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.
one hiddden layer discrminator
two dden-layer discrminator
three hidden-layer discmiinator
tou whwdhhddd---yerrrr discrminatoo
2.0
0.002
0.00
0.00
0.00
0.000
0.002
0.00
50
100
250
20C
50
100
150
200
50
220
350
200
0
30
300
250
200
Zua aliamt
Daral ama
Eutraticn
kerations
Figure 1: Test loss (BI log loogll(())))) D(X)) + l ((G()))) - log(2) over course of training. Discrim-
inators cannot distinguish generator output from true distribution, though Wasserstein provably large.
CONCLUSIONS
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 that holds for specific generator. Of course, it is quite unlikely that we will ever encounter such 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 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 opposed to the purely statistical metrics generally considered in the literature.
Dwork et al. 2021)

---

Published as a conference paper at ICLR 2022
The authors would like to thank Boaz Barak, Adam Klivans, and Alex Lom- bardi for enlightening discussions about local PRGs. SC was supported by NSF Award 2103300. This work was done while the first, second, and fourth authors were visiting the Simons Institute for the Theory of Computing.
Acknowledgments
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. Forward super-resolution: How can gans learn hierarchical generative models for real-world distributions. arXiv preprint arXiv:2106.02611 2021.
Benny Applebaum. Cryptographic hardness of random local functions. Computational complexity, 25(3):677-722, 2016.
Benny Applebaum and Pavel Raykov. Fast pseudorandom functions based on expander graphs. In Theory of Cryptography Conference, pp. 27-56. Springer, 2016.
Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC SIAM Journal Computing, 36(4):845 888, 2006.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 214-223. PMLR, 2017.
Sanjeev Arora and Boaz Barak. Computational complexity: modern approach. Cambridge Uni- versity Press, 2009.
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (gans). In International Conference on Machine Learning, pp. 224- 232. PMLR, 2017.
Sanjeev Arora, Andrej Risteski, and Yi Zhang. Do gans learn the distribution? some theory and empiries. In International Conference on Learning Representations, 2018.
Yu Bai, Tengyu Ma, and Andrej Risteski. Approximability of discriminators implies diversity in gans. In International Conference on Learning Representations, 2018
Hugo Berard, Gauthier Gidel, Amjad Almahairi, Pascal Vincent, and Simon Lacoste-Julien. A closer look the optimization landscapes of generative adversarial networks. arXiv preprint arXiv:/906.00 04848, 2019.
Lijie Chen and Roei Tell. Bootstrapping results for threshold circuits "just beyond" known lower bounds. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. pp. 34 41, 2019.
Minshuo Chen, Wenjing Liao, Hongyuan Zha, and Tuo Zhao. Statistical guarantees of generative adversarial networks for distribution estimation. arXiv preprint arXiv:2002..33338 2020a.
Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan. Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. In Ran Raz (ed.). 31st Conference on Computational Complexity (CCC 2016), volume 50 of Leibniz International Proceedings in Informaicss (LIPlcs), pp. 1:1-1:35, Dagstubl, Germany, 2016. Schloss Dagstuhl-Leibniz Zentrum fuer Informatik. ISBN 978-3-95977-008-88 doi: 1w23////Pccs.CC..... http://drops: dagstuhl de
URL
6/5844
Sitan Chen, Adam R Klivans, and Raghu Meka. Learning deep relu networks is fixed- seed-parameter tractable. arXiv preprint arXiv:2009 205522000..111., 2020b.
Amit Daniely. Complexity theoretic limitations on learning halfspaces. In Proceedings of the forty- eighth annual ACM symposium Theory of Computing, pp. (05-117, 2016.
Amit Daniely and Shai Shalev-Shwartz. Complexity theoretic limitations learning dnf's. In Conference on Learning Theory, pp. 815-830. PMLR, 2016.
Amit Daniely and Gal Vardi. From local pseudorandom generators to hardness of learning. arXiv preprint arXiv: 10100830, 2021.
10

---

Published as a conference paper at ICLR 2022
Amit Daniely, Nati Linial, and Shai Shalev-Shwarde From average complexity to improper learning complexity. In Proceedings of the forty-sixth anmual ACM symposium on Theory of computing. pp. 441 2014.
Constantinos Daskalakis, Andrew llyss, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint arXiv:171..00144 2017.
Cynthia Dwork, Michael P Kim, Omer Reingold, Guy N Rothblum, and Gal Yona. Outcome in- distinguishability.. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1095-1 108, 2021.
Soheil Feizi, Farzan Farnia, Tony Ginart, and David Tse. Understanding gans: the lęg setting. arXiv preprint arXiv: 10793, 2017.
Vitaly Feldman, Will Perkins, and Santosh Vempala. On the complexity of random satisfiability problems with planted solutions. SIAM Journal on Computing, 47(4):1294 22411129943338 2018.
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Si- mon Lacoste-Julien and Ioannis Mitliagkas. Negative momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1802-1811. PMLR, 2019.
Mikael Goldmann and Marek Karpinski. Simulating threshold circuits by majority circuits. SIAM Journal on Computing, 27(1):230-246, 1998.
Mikael Goldmann, Johan Håstad, and Alexander Razborov. Majority gates vs. general weighted threshold gates. Computational Complexity, 2(4):277-300, 1992.
Oded Goldreich. Candidate one-way functions based on expander graphs. In Studies in Complexity and Cryptography, Miscellanea on the Interplay between Randomness and Computation, pp. 76- 87. Springer, 2011.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(1 63(11):139-144, 2020.
Jie Gui, Zhenan Sun, Yonggang Wen, Dacheng Tao, and Jieping Ye. A review generative adver- sarial networks: Algorithms, theory, and applications. arXiv preprint Stti:::0001009933 2020.
Russell Impagliazzo, Ramamohan Paturi, and Michael E Saks. Size-depth tradcoffs for threshold circuits. SIAM Journal on Computing. 26(3):693-707, 1997.
Qi Lei, Jason Lee, Alex Dimakis, and Constantinos Daskalakis. SGD learns one-layer networks in wgans. In International Conference Machine Learning. pp. 5799-5809 PMLR, 2020.
Jerry Li, Aleksander Madry, John Peebles, and Ludwig Schmidt. On the limitations of first-order approximation in gan dynamics. In International Conference on Machine Learning, pp. 3005- 3013. PMLR, 2018.
Tengyuan Liang. How well generative adversarial networks learn distributions. arXiv preprint arXiv:1811.03199, 2018.
Shuang Liu, Olivier Bousquet, and Kamalika Chaudhuri. Approximation and convergence proper- ties of generative adversarial learning. arXiv preprint arXiv:1705.0899) 2017.
Ester Mariucci and Markus ReiB. Wasserstein and total variation distance between marginals of lévy processes. Electronic Journal of Statistics, 12()):482-25144, 2018.
Ryan ODonnell and David Witmer. Goldreich's prg: evidence for near-optimal polynomial stretch. In 2014 IEEE 29th Conference on Computational Complexity (CCC), pp. 1-12. IEEE, 2014.
Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao. Why and when can deep-but but not shallow-networks avoid the curse of dimensionality: a review. Inter- national Journal of Automation and Computing, 14(5):003-519 2017.

---

Published as a conference paper at ICLR 2022
Mark Rudelson and Roman Vershynin. Smallest singular value of random rectangular matrix. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62(12):1707-1739, 2009.
Nicolas Schreuder, Victor-Emmanuel Brunel, and Amak Dalalyan. Statistical guarantees for gen- erative models without domination. In Algorithmic Learning Theory, pp. 1051-1071. PMLR, 2021.
Shashank Singh, Ananya Uppal. Boyue Li, Chun-Liang Li, Manzil Zaheer, and Barnabás Póczos. Nonparametric density estimation under adversarial losses, In NeurlPS, 2018.
Michael Sipser. Introduction the theory of computation. ACM Sigact News, 27(1):27-222 1996.
Hoang Thanh-Tung and Truyen Tran. Catastrophic forgetting and mode collapse in gans. In 2020 International Joint Conference on Neural Networks (IJCNN), pp. 1-10. IEEE, 2020.
Hoang Thanh-Tung Truyen Tran, and Svetha Venkatesh. Improving generalization and stability of generative adversarial networks. arXiv preprint arXiv:1902.03964 2019.
Ananya Uppal, Shashank Singh, and Barnabas Poczos. Nonparametric density estimation & conver- gence rates for gans under besov ipm losses. Advances in Neural Information Processing Systems, 32:9089-91000 2019.
Salil P Vadhan. Psendorandommess, volume 7. Now Delft, 2012.
Emanuele Viola. The sum of d small-bias generators fools polynomials of degree d. Computational Complexity, 18(2):209-217, 2009.
Ingo Wegener. The complexity of Boolean functions. John Wiley & Sons, Inc., 1987.
Maciej Wiatrak, Stefano V Albrecht, and Andrew Nystrom. Stabilizing generative adversarial net- works: A survey. arXiv preprint 1xiv:1910.00922 2019.
Pengchuan Zhang, Qiang Liu, Dengyong Zhou, Tao Xu, and Xiaodong He. On the discrimination- generalization tradeoff in gans. arXiv preprint arXiv:1711.02771,, 2017.
12

---

Published as a conference paper at ICLR 2022
provide some additional technical preliminaries, in- cluding background on Boolean circuits. n Section we give the deferred proofs from Section 3 for our main result, Theorem 3.1 In Section C.1 we give background on circuit lower bounds for TC", and in Section C we prove Theorem C.2 which effectively says that if one could exhibit genera- tors with even logarithmic stretch which can fool constant-depth, sufficiently superlinear-sin ReLU networks, then this would imply breakthrough circuit lower bounds.
Roadmap for Supplement In Section
A ADDITIONAL TECHNICAL PRELIMINARIES
More Notation and Miscellancous Tools Let 1, denote the all-ones vector in dimensions; when is clear from context, we denote this by 1.
Given a vector v E Rd, we let || denote its Euclidean norm. Given r > O, let ((e,)) r) C IR denote the Euclidean ball of radius with center Given matrix W, we let |[W]] denote its operator norm. Let min (W) denote minimum singular value.
Given distribution let pen denote the product measure given by drawing independent samples from p.
Define the function sgn(x) 2 {1
x 2 0
x <00
Let R + R denote the ReLU activation (0z) - max(0, Let dix R -> R denote the leaky ReLU activation ()) = 2/2 (1/2 2 2)|=|. Note that
xx = (1 - Ajo(=) - AØ(-
We will need the following well-known result: Theorem A.1 (Kirszbraun extension). Given an arbitrary subset C. Rd and f S
+ R which is
L-Lipschilz, there exists an L-Lipschitz extension J IRd + R.for which f(y) = (wy) for all E S.
We will need the following basic fact about composing Lipschitz functions:
Fact A.2. gt, ...,,...,9 Gr Rd + are A-Lipschitz and R2" + R is A -Lpiscchiiz, then the function
x + (z) (x)
AA Li-iischitz.
Proof. For any 2, x', we have 19.(x) 9x(2') Aliz I'11, (Eir(,,(x)) -2(22))3) AVFll æ'|], This implies that (z). (x)) h(gg AA' x' as desired.
Fact A.3. The volume of d-dimensional Euclidean ball of radius I is most (18/d)d/2.
Proof. It is a standard fact that the volume of the ball can be expressed as 2 (#/2)1d/21 di!
If d is
even, then d!! = 2d/2, (d/2)) 2 24/2 o(d/e]"
d/2 (d/e) If d is odd, then d!!
[2/2]1121//3] 2
d!
edd/2oj//2-2477 = (d/e)4/2, We conclude that the volume is at most (2te/d)d/2 < (18/d)//2.
O
A.1 CONCENTRATION OF MEASURE
We will use the following consequence of McDiarmid's inequality:
Lemma A.4 (McDiarmid's Inequality). Suppose [+1) n - (+1) is such that for any x, a'
(11)n differing on exactly one coordinate, [F(x) F(x')) Then
28
[1f(=) x-111"
P [ff(=)]] S exp
ne²
13

---

Published as a conference paper at ICLR 2022
Corollary A.5. Given F {=1}" + {=1} which is A-Lipschitz, define the random variable X _ F(Un). Then X- [[X] is MV2n-sub-Gaussin
Proof. Because F is Lipschitz, it satisfies the hypothesis of Lemma A.4 with c A, so the corollary follows by the definition of sub-Gaussianity.
Theorem A.6 (Theorem 1.1, (Rudelson & Vershynin 2009 ). For n. d E N with 2 d, let W Raxd be a random matrix whose entries are independent draws from ((0, 1). Then every e >> 0,
P PImmiu (W) S e(vnnva--i s <CC))= + t
for absolute constants C, > 0.
A.2 BOOLEAN CIRCUITS
In the context of pseudorandom generators, the set of all polynomial-sized Boolean circuits is the canonical family of discriminator functions to consider when formalizing what it means for a gen- erator to fool all polynomial-time algorithms.
Here we review some basics about Boolean circuits; for more thorough introduction to these concepts, we refer the reader to any of the standard textbooks on complexity theory, e.g. (Arora & Barak 2009: Sipser 1996).
Definition 7 (Boolean circuits). Fix a set G of logical gates, e.g. A, A Boolean circuit C Boolean function (+1}" + {+1} given by a directed acyclic graph with n imput nodes with in in-reeree zero and an output node with out-degree zero, where each node that isn' I an input node is labeled by some logical gate in G. Unless otherwise specified, we will take G to be (A, V.
The size S of the circuit is the number of nodes in the graph, and the depth D is given by the length of the longest directed path in the graph. The value of C on input E [+1] R is defined in an inductive fashion: the value at node e in the graph is defined be the evaluation of the gate at v on the in-neighbors of (as the graph is acyclic, this is well delf-defined), and the value of C on x is then the value of the output node.
We will occasionally also be interested in the number W of wires in the circuit, i.e. the number of edges in the graph. Note that trivially
(2) Definition (P/poly). Given T N. SIZE(T(m)) denote family of sequences of Boolean functions {fn [=1]" + { for which there exist Boolean circuits {Cn} with sizes {Sn} that compute {fr} and such that Sn < (n)).
S S W +1.
Let P/poly & UEs1 SIZE(n"). We refer to (sequences of) functions in P/poly as functions com- putable by polynomial-sizer circuits.
The following standard fact about bounded-depth Boolean circuits will make it convenient to trans- late between them and neural networks.
Lemma A.7 (See Theorem 1.1 in Section 12.1 of (Wegener) 1987 For any Boolean circuit C of size S and depth D with gate set G. there is another circuit C' of size D S and depth D with gate set G which computes the same function as C but with the additional property that for any gate in C", all paths from an input to the gate are of the same length.
The upshot of Lemma A.7 is that for any length f, we can think of the gates of C' at distance from the inputs comprising "layer" in the circuit.
A less combinatorial way of formulating the complexity class captured by polynomial-size circuits in terms of Turing machines with advice strings.
Fact A.8 (See e.g. Theorem 6.11 1 in Arora & Barak 2009)). A sequence of Boolean functions
} is in P/poly if and only if there exists a sequence of advice strings {a,) } where an {+1}" for an I (n)y(n). and Turing machine M which runs for most (oly(n) steps and, for any n E N. takes as input any x E {+1}" and the advice string on and outputs M M(x, 0n) (00== (x).
(fn : {+1}" + {+1}}
14

---

Published as a conference paper at ICLR 2022
This fact will be useful for translating discriminators computed by neural networks into discrimina- tors given by polynomial-size Boolean circuits.
A.3 MORE ON GANS AND PRGs
In this section we fill in some additional details regarding the contents of Section 2.1 We begin with a simple remark about Definition
Remark A.9. In Definition [ if L 1, then S = 0 and the definition specializes linear functions. That is, C. is simply the class of affine linear functions F(x) (w, x) + for R and b E IR, satisfying ||o||| A.
Next, we fill in the proof of Lemma 2.1 which we restate below for the reader's convenience.
Lemma A.10. Let J R Rº be a function each of whose oulput coordinates is computed max(T1, T2),
by some network in CT1.A1 L1, and let f CT2.A2 122 Then fo J E &CT,A. .
A AAA2VT. L L1 + L2, and S = (S1 + 1)r + Sz. Furthermore, for the network in L.S, realizing o J, the bias and weight vector entries in the output layer lie in B.y
Proof. Suppose that the i-th output coordinate of J is computed by neural network with weight matrices w E R xe wht E R 1xx and biases 61 R .....,,,,,
R.
Define the (E M x weight matrix W1 by vertically concatenating the weight matrices w(1) w(") For every j L1 define the Ei=1k Ei=ib weight ma- trix W by diagonally concatenating the weight matrices w W Similarly, define the For the bias vectors in these layers, for every s I L1 define by to be the vector given by concate- nating (1)) "......,"" 1/77
r x (E k())) matrix WL, by diagonally concatening the column vectors ( ,...... w
Now suppose that f is computed by neural network with weight matrices W Wi+11 E R W +1++22 E Rlxke Lg and biases bb.+1 E 12......... .....,L..... R. Then by design, for any Rº we have
f(J(y)) WL W W (iy w1)+ ..) bb + bL
This network has depth L, + L2 and size
4-11 Σ
LitL -
+r+
Σ j=1.11
+r
The bit complexity of the entries of the weight matrices and biases obviously bounded by max(T1, 72), and the Lipschitzness the network is bounded by A1A2rr by Fact A.2
Finally, we will also use the following standard tensorization property of Wasserstein distance later:
Fact A.11 (See e.g. Lemma 3 in (Mariucci & ReiB 2018)). If p.g satisfy Wi (i(p.)) q) 6, then (i ( < <vnR.
A.4 DIVERSE DISTRIBUTIONS: MISSING PROOFS
Here we fill some missing details from Section 2.3 We first show that diverse distributions cannot be approximated by pushforwards of Um. if m is insufficiently large. This follows immediately from the definition of diversity:
Lemma A.12. For any 0 < 1, D is a (2"h , di)deeesss distribution over TR. then for any function G {+1)m + IRd, (G(G) D*)
Proof. G(U,). is a uniform distribution on 2n points, with multiplicity if there are multiple points in (+1) Im that map to the same point in d under G. so the claim follows by definition of diversity. [T
15

---

Published as a conference paper at ICLR 2022
Below give some simple examples of diverse distributions.
Lemma A.13 (Discrete, well-separated distributions). For any > 0 and any N, E N satisfying
N N'. Let I& be a set of points such that for any 2, z' E Q || z'Il 2 a. Then the uniform distribution y any N' points from Q is (N,,NN (N, N.Byeeiversse for 3 = a N/N").
Proof. Take any discrete distribution y supported on at most N points y1.... MN in R4. Consider the function f : R + R: for any y in the support of v, let f(y) = 0, and for any y not in the support of v/ let fly) 1. As function from ! to R, where !2 inherits the Euclidean metric, is clearly 1/a-Lipschiie over 12. By Theorem A.1 there exists a 1/a-Lipschitz extension f Rd R of f, and we have
[[f(A]] - R[f( = Bif(A) 2 N/N'.
so (1( 11-NNNN as desired.
We now turn to examples of continuous distributions which are diverse. We first observe that a distribution is (N, di-vveree if satisfies certain small-ball probability bounds.
Definition 9. For a distribution D over RS, define the Lévy concentration function Qp(r) & SUP IP PIZD [||a: x'1l S
Lemma A.14. If a distribution D over Rd satisfies Qr(r) I a, then D is rN, (N)---aa)--ivrrsss
Proof. Take any N points 21...., NN E Rd. By the bound on Qp(r), the union S of the balls of radius around these points has Lebesgue measure at most Na. Define the function f (z1...., zN\ U (R) (55) - 1) to be zero on (2).... 2x } and one on Rd,,, This func- tion is 1/r-Lipschitz on its domain, so by Theorem A.1 there is extension f Rd R of which remains 1/r-Lipschitz on its domain. Define the function (xx A [f(=)) Note that for μ the uniform distribution on f21,...,ZN' /
[[f(()] Eff Bif(D)I 1 -Na,
so we conclude that (H, 2 - (r1-~Na)
Lemma A.15 (Uniform distribution on box). Ia is diverse for N I (d/18)4/2.
(r) < (18r² /djd/2, Taking 1 and applying Lemma A.14 allows us to conclude that W1,,, Ia) 2 N(18/d)d/2 from which the lemma follows.
Proof. By Fact A.3
As we stated in Lemma 2.3 large family of pushforwards of the uniform distribution over [0, 1]d are similarly diverse. Below we restate this lemma and provide a complete proof.
O. For ku, ..., ky E N satisfying k; 2 (1 + +k for all i E [L], ler W1 E k W2 E Rizxki, ..... W, &LL be random weight matrices, where every entry of W; an independent draw from (0, 1/k,). For the function F. ko + Re given by
Lemma A.16 (Random expansive leaky ReLU networks). Let 0.
F(x) A WLW (W WWL-IW (-.. (-...)/(11)--.... (W
have that F(TE,) is (2Th 3) diverse for
(kg/2)log(ko/))) kL/l
8 6 2/
So for example, if X, L are constants, then F(JKa) is (2 log ko), ((1))-diirrre ko sufficiently large.
We will prove this inductively by first arguing that pushing anticoncentrated distributions through leaky ReLU (Lemma 1.17) or through mildly "expansive" random linear functions (Lemma A.18)
preserves anticoncentration some extent:
16

---

Published as a conference paper at ICLR 2022
Lemma A.17. Let 0 < <X 1/2. If distribution D over R satisfies QD(r) a, then the pushforward 'D' & (D) also satisfies QD.(rr S o, where here ()x(-..) denotes entrywise application of the leaky ReLU activation.
Proof. Consider any ball Bv,, Ar) in R.. Take any orthant Kg of R given by points whose i-th coordinates are nonnegative for E S and negative for & S. Let By be the intersection of B with this orthant. Then Px (Bs) consists of points E Kg for which
E(2e + +00++(11111 A)2 - v1)2 S x IS
(11
(3)
igS
We can rewrite the left-hand side of as
2
z - (==3, + (1 x)² Σ
(2) 01((1
- 1))2 2 22|1= - USS)??
YSS
Kgs
where in the last step we used X < 1/2 and define the vector v E Rd by
[VL/A /A iES
uf
( /11 -) i E
In other words, v/ (Bs) is contained in Kg ((v(S)), r). In particular,
$5 (BB(B) C C Ks B(v(S)rr)
8
so PANDr (o E B] < a by a union bound.
Lemma A.18. Suppose n, d E N satisfy n 2 (1+7)d for some : > Let W E Rudd be a matrix whose entries are independent draws from (0, 1/n). Ifa distribution D over Rd satisfies Qu(r) S then for the linear map J + Wa, the pushforward DD A J(D) satisfies QD with probability at least 1 exp(-S((d)).
7
S
2(1+x)
Proof. By Theorem A.6 for any we have that amin (W) 2
d-1
with probability
least 1 (Ce)n-d4t on Taking c = 1/2C and noting that
d-1
we conclude
n
147
that
min W)
>
2 1 -
2(1 + +
Condition on this event. Now for any v IR,", if we write as W + /² where μ is orthogonal to the column span of W, then Wz-v/|2
(w(=+))l+++1 -12 So || x- vll S 2(1+7)
or implies
that I| (a- ----- #1ll S 2((
But because mmin (W) 2 श(ो we conclude that ||x =ll S r, from
which the lemma follows.
We are now ready to prove Lemma 2.3
Proof of Lemma 2.3
By LemmeLmm.alll. 14 suffices to bound the Lévy concentration function. We will induct on the layers of F. For i [L]. let F(O) denote the sub-network
Wabx (WL-1th (.. 3 (.z)...))
and let D; denote the pushforward (()) (Ika). which is a distribution over R We would like to apply Lemma A.mmalA.18) to each of the weight matrices W Wi...., W,, so condition on the event that the lemma holds for these matrices, which happens with probability at least exeep((((((p00)
Recalling from Fact A.3 that Qiao (r) < (18r²/ ////// Mo/2 for any r O, we get from Lemma A.18
applied to W, that QD,
7T" 2(+7)
< (18r2 ko//2
ko/2
17

---

Published as a conference paper at ICLR 2022
Suppose inductively that have shown that QD. (re) < 0g for 7t. a Lemma A.17 and Lemma A.18 applied to weight matrix W s41, we conclude that
0.
Then by
Xyn
QDi4 (Ti+1) S a+t1 for T2+1 2(1 + 7)
ait1 az
(4)
Unrolling the recursion
we conclude that @DL(re) Sa for
L
X7
7
A
Fr. -
2r.
2r.
2(1 + 71
2(1
2 elle
a7 solattthh kz (18r /ko) koo2 2h2 2 (18r/ /ko) ko/
(5)
where the inequality (5) follows from the fact that b .... kL-1 S kL-1 1 - k2/7. By
Lemma A. F(,,)) = Dr is (N, -diveee The lemma follows by taking r = 1/3
and 2 N 1/2aL.
B DEFERRED PROOFS FROM SECTION 3
B. PROOF OF COROLLARY
Corollary 3.3 is immediate consequence of the following which appeared in (Chen et al. 20206):
Lemma B.1. For any function P {=1} + {+1}, there is collection of k weight matrices
W....., We with entries in Ro(s) for which
P(x)
(6)
for all x. E {+1]} and for which || |Wlll S 0(1). Furthermore, the size of the network on the right-hand side of (6) is at most ( k).
We give proof for completeness to make explicit the dependence of the parameters on k.
Proof. Consider the Fourier expansion F(x) = EscM
F[S) Iles Ts. We show how to represent
each Fourier basis function lhe as a ReLU network with at most k layers. Observe that for any I1. {
L = 6(I1 + x2) + o(-x1 x2) - -(1)) x(-22),
(7)
which a two-layer neural network of size 4 whose two weight matrices have operator norm at most 3. Suppose inductively that for some m < n, there exist weight matrices W W.... W for which m and that i=1 J; W p(. (o..:.((WWaa) ((W(x)... ..) for all x E [+1)*, that this network has size 4m,
Will S 6
We now show how to compute I Define W by adding the m-th standard basis vector as new row at the bottom of W . For every S m, define W to the matrix given by appending column of zeros to the right of W and then new row at the bottom consisting of zeros except
in the rightmost entry. Note that ||W]|l = max(1, W/l)). Define the network Fm R + R by
(x) w W" & (Wix)....)
Letting v, E
2 be the vectors (1,1) and (0, 1), we can use 7 to conclude that
2,
II I. + Im+1
④ (-Il II 21 xm+1
x((m-11) 6((-xm+a)
<(w Fm (x)) + o(-vT T
a(e Fm(()) :b(-TTPrn Pm)())).
We thus write 1 2i the ReLU network
m++1
x; = W!!!!
mi Φ( ((W'..(("")).))
(8)
18

---

Published as a conference paper at ICLR 2022
where
W
W m
W m+1 = -1,1, -1) W
W =
=W A1 S i m.
W
m
W
m
Note that the entries of any W are in {0, and thus have bit complexity at most 2. Additionally,
and || = max(1, [lll) for all | m++1 S 2, W I 3|| W|W Wlll = max(1, || I/,,,,,),. II.
6m*11 Furthermore, the size of the network in (8) is 4m + 4. This completes the inductive step and we conclude that any Fourier basis function lies 2; can be implemented by an |S|-layer ReLU network with size 4 and the product of whose weight matrices' operator norms at most 6|s).
1 so I m+ |
In particular, as the biases in the network are zero, we can rescale the weight matrices so they have equal operator norm, in which case they each have operator norm at most ((1) and entries in Ro()
Finally note that because the Fourier coefficients given by E (F((x) Iles #i), they all multi- ples of 1/2* and thus have bit complexity O The proof follows from applying Lemma B.2 to these Fourier basis functions and À given by the Fourier coefficients of P, as ||||| ||||| =
The above proof required the following basic fact:
Lemma B.2. Let T' E N, and let X E RT. Given neural networks FI,...,F, Rd IR each with L layers and whose weight matrices (W(")..... (W(r)) have operator norm bounded by some R > and entries in R.,, their linear combination E, X,F is a neural network with L layers, size given by the sum of the sizes Fi Fi...ry Er, and weight matrices W WI...., W E with entries in (o(++r') and satisfying [| I|l S RVT, [|W S R|]A||, and [[ll S for all < i < L. Here
IR is the vector with entries Aç-
Proof. Denote the i-th weight matrix of Fj by w()). Define W, to be the vertical concatenation
of w(1) (1) ((()) and for every 1 < < L, define W, be the block diagonal concatenation of w() ..... ((r) Finally, define WL to be the row vector given by the product
w
0
2
0
A
L
0
0
w!!)
0
For 1 < < L., |W/l| S max W(]], and additionally || S Eラ w 12 and
||Lll < [||| max W
B.2 PROOF LEMMA 3.4
We will need the following helper lemma about means of truncations of sub-Gaussian random vari- ables:
Gaussian and mean zero, then for any interval I [a, b] with a S 0 b, we have [ Z [ 7]] < O(b + a) exp(- min(-a,b)) 2
Lemma B.3. If Z is oassub-Gaussian
19

---

Published as a conference paper at ICLR 2022
Proof. Define the random variable Z' Z 1[ 1). Then by integration by parts,
E|Z' S E|Z 1[2 b]]
PIz' > tjdt
= bplz b] +
PIZ > t]dt
S bbep(( -b2/20² O exp(-b² /202)
I 50(+
1200
and similarly, E||" 2 Z 1 < - 2 0(a 0) exp(-b² /20²), completing the proof.
We now complete the proof of Lemma 3.4
Proof of Lemma 3.4 Without loss of generality we can assume that E[X] and E a. 2 ca for some sufficiently large absolute constant, then we can simply take t = a/2 and get that |P[X > -|-P d]] 1/2. Now suppose < ca, and let / = [-r,r+a] for ov Iog(Co/a))
for some large constant > O. Note that by this choice of
rexp(-r2/2o*) < O(a).
where the constant factor can be made arbitrarily small by picking O sufficiently lage. Define the random variables X' & X 1[X I] and Y & Y 1[Y I]. Then
E E[ = B[Y" - + E[y 1[Y $ IlI - E|X 1[X $ I]}.
(9)
By Lemma
E[X 1[X & f]] s 0(2r
-
()) -xp-)) s 0(r) exp(-r² /20 S O(a) (10)
and similarly
B. y & /]] < B[|
o & +2 (rp( a0)/2))
2a exp(-xii + O(a).
(11)
Additionally, we have
por
(Dr (x: 1 (xxx - - (2)
E - E|Y
(12)
where (2) denotes the edf at of random variable Z. Putting conclude that
12
together,
patt (1 ox- (x)) I" (x) Ty (y))) M(a)) (br
min
where the constant factor can be made arbitrarily close to 1/2 by making C sufficiently small. By averaging, we conclude that there exists / E [-ox, + r] for which
IP > | - P(Y' > $] 2 9(a/r).
But P(X & PY & [ <(exp((-- /2)²)) S ((arr) where the absolute constant can be made arbitrarily small by making C' sufficiently small. The claim follows by union bound, recalling the definition of X',Y" Y.
B.3 THRESHOLDS OF NETWORKS AS CIRCUITS
In the proof of Theorem 3.2 we also need the following basic fact that signs of ReLU networks can be computed in P/poly.
Lemma B.4, For any f E F*, there is a Turing machine that, given any input y, outputs sgn( (v)) after (dl steps.
20

---

Published as a conference paper at ICLR 2022
Proof. Recall that the weight matrices Wi.... W. of f have entries in R, for T poly(d). So
for any 1 S i S L, diagonal matrices D2 E {0, 13 xh , y E {=1}", every entry of the vector
D E {0, 1 1x 1, and vector
W,D
(W1y + b1) ..) + b)-1) + be
has bit complexity bounded by
E-1 h;
log2
e. (0(r))
O(T + S) - poly(d),
where in the second step we used that log(k;) I k; for all i E [e - 1]. So for any input to f, every intermediate activation has poly(d) bit complexity.
The Turing machine we exhibit for computing sgn(f(v) will compute the activations in the network layer by layer. The entries of Why + by can readily be computed in poly(d) time. Now given the vector of activations
Weo(- <e Wiy + b1)...)) ...) ..+)))+)
for some é 2 1 (where is represented on tape of the Turing machine a bitstring of length poly(d)), we need to compute W W4+10(v) + be+1. The ReLU activation can be readily computed in poly(d) time, in poly(d) additional steps can form this new vector of activations at the (++1)-layerr So within S poly(d) = poly(d) steps the Turing machine will have written down f(v) (represented bitstring of length poly(d) on one of its tapes, after which it will return the sign of this quantity.
B.4 PROOF OF THEOREM 3.2
We now give a complete proof of Theorem 3.2
Proof. The parameter m will be clear from context in the following discussion, so for convenience we will refer to d(m) and Gm as and G. Let k, P. G be such that the outcome of Assumption holds, and negl(-) denote the function indicating the extent to which G fools poly-sized circuits.
By Corollary 3.3 every output coordinate of G is computable by a network in CT.A for L.S.m
O(k),A = exp(O(k)), L= k = k2*
We first check that W (G(U( Ua) > 1/3. Note that G(Um) has support of size 2n. In Lemma A.13 we can take = Up and conclude that j is (2 2(1 - 2m ) so (G(U Ua) 2 2(1 - 2m- = 2(1 - - 2 2.
It remains to check that G fools F relative to Ua. Suppose the contrary that there exists some f E F and absolute constant a > 0 for which (G(() Eff(U,)] > 1/d". We will argue that this implies there is poly-sized circuit C:: {=1] [+1] distinguishing G(U,.) from Ua.
First note that for any threshold / E Rr, by Lemma B.4 there is a Turing machine M, : { {+1} that computes y + sg (f)) - t) with 7 bits of advice. So there existed a threshold t E, for which
(UM]( 1/d"',
(13)
for some constant a' > 0. then by Fact A.8 there would exist a Boolean circuit C' distinguishing (U,,) from UA with non-negligible advantage, contradicting Assumption I and concluding the proof.
We will apply Lemma 3.4 to show the existence of such a threshold t. Specifically, define random variables X ((G(Um) m and Y = f(Ua). By Corollary A.5 applied to the poly(d)-Lipschiz function f {+1]d (+1), Y E|y] is (oly(d)-sub-Gauusii)
And recalling that G E CLSSm for A exp() we can apply Corollary A.5 to the poly(d) (1)-iisshitzz function f G (=1)m + {+1} to conclude that X E[X] is Ses-uu--ausssae for a - poly exp(O(k)) (d)y By Lemma 3.4, there exists threshold & for which the left-hand side of 13) exceeds min m1,2 (/))), which is not negligible.
remains to verify that has bit complexity at most poly(d). As the entries in the weight matrices and biases in f all have bit complexity poly(d) and f has size and depth poly(d), f'(y has bit
21

---

Published as a conference paper at ICLR 2022
complexity poly(d) for any y E {=1} Similarly, the entries in the weight matrices and biases in G all have bit complexity O(k) = O(1). so f(G(z)) has bit complexity poly(d) for any æ E [ By the bound in Lemma 3.4 and our bound above, t therefore also has poly(d) bit complexity.
B.5 PROOF LEMMA 3.6
Proof. Suppose to the contrary that there existed some function f E F' for which
-(f((\)))))))) 2e A'
By Lemma 2.1 and choice of 5" the composition f J IR. IR can be computed by network in AA of whose bias and weight vector entries in the output layer lie in Ry L,
We first show why this would lead contradiction. Consider the function h _ th So for
C = 2 flogg N' VFl E [A',2A),
which can be computed by taking the network computing fo and scaling the bias and weight vector in the output layer by C. Note that this scaling results in bias and weight vector entries the output layer for h with bit complexity r' + [log2 A' /vrl Furthermore, h is AA Vr/C S A-Lipschitz, the other hand, we would have so h E CT.A
[B[M(p)] - 1E [((())l > 2: VF/C2
yielding the desired contradiction of the assumption that Wy(p.9) Sc.
B.6 PROOF OF FACT 3.7
Proof. Note that h(U,,) is the uniform distribution over multiples of 1/2" in the interval [0, 1). Given any such multiple 2, let p= denote the uniform distribution over [2, 2 + 1/2"). One way of sampling from I is thus to sample z from hU,,) and then sample from p..
Now consider any I-Lipschitz function f + R. Note that for any a' in the support of p.. (f(=) f(=') 1/2" S We have
E [f(x) 5(611 [f())=
-
E
=~)(U,)
plrup
as desired.
B.7 PROOF OF LEMMA 3.8
Proof. Let n [og(1/e)] For every i [r]. define S; A + 1...,,,; Take J to the linear function IR' to (w, + where wy is outside of S, and, over coordinates indexed by Si. equal to the vector (1/4,..,,1/2") 1/2n-1). Note that each output coordinate of is computed by function in C 1,01)
be the linear function where for every i E [r]. the i-th output coordinate which maps
By Fact 3.7 and Fact A.II
W5- (J(U.), S poly(r) WI(J(U.), I,) S poly(r) .e.
On the other hand, by Lemma 3.6 and the fact that the union of C² plo-lo AVFLA (sly is still F², we conclude that
over T, A, L,
W ()))) O(EVT)
from which the lemma follows by triangle inequality.
22

---

Published as a conference paper at ICLR 2022
B.8 PROOF OF LEMMA 3.9
Proof. Let J ; R + R' be given by Lemma 3.8 We know that (5-(J(D), S poly(r). By Lemma 3.6 applied to these two distributions and the generator function H, together with the
A, L, poly(s) is still FC, thus have that Wx (H(())) H(I)) S O(eNv poly(r) eA' polyys))
fact that the union of C L', 1/,5 (1)
-[log A Ava
We will thus take J' in the lemma to be o J. By Lemma 2.1 each output coordinate of J' is computed by a function in 1/+1+48'
) as claimed.
B.9 PROOF OF THEOREM 3.5
The parameter m will be clear from context in the following discussion, so for convenience we will refer to ((m),d(m); (m)) Hm, Gm as r, 6, H, G, and similarly for the network parameters L',
Proof of Theorem 3.5
is easy verify condition before we even define G: because G(Um) ) uniform distribution on 2m points (with multiplicity) and H (I,) is (2"h. ((()))-diverse, W (G(UU, Ia) 2 2211) as claimed.
Let
[og((1 [o){1/e)]] As we assuming e exp(-O(m)), S r m m for some constant e > 1. If 8 & y,, then define G' I - IR to be the map given by projecting to the first s coordinates so that (Um) and U, are identical distributions. Otherwise, take G' to be the generator G 1 + Rs constructed in Theorem 3.2 recalling that Wy- (U" S negl(m) Sc.. c.
Next, by applying Lemma 3.9 to D = (Umm,, we get a function J' : R + Rd each of whose
output coordinates is computed by a function in (0oxx(0rlo((//)))))))0.) va) such that 1/41,448'
(F))) H(I)) eA' poly(m) S polyymmm.
(14)
where the second step follows by our assumption on A'
We will take G - J' G". [4] establishes condition 2 of the theorem. Finally, by Lemma 2.1 every
output coordinate of G can be realized by network in CT.A L.S.m for max(O(log(1/c)) O(1),
= O = O(A' (m)y L = L' O and $ = 0(s) - S (where used the fact that s/ [log(//c))) < s). This establishes condition of the theorem.
L
B.10 PROOF LEMMA 3.10
Proof. Note that
6(1/5 11,
(15)
so we can take weight matrices
1/E 1/E
W1
W₂ (1 -)
and biases (1,-1) and
1. Note that he 1/E-Lipschitz. We conclude that he
C2.2,1
B.11 PROOF OF LEMMA 3.11
Proof. We first verify that W (Go(Um), G(Tm)) < e. Take any I-Lipschitz function f. Note that can sample from Um by sampling vector g from Tm. applying he entrywise to g, and replacing each resulting entry of he(g) by its sign; importantly, the last step only affects entries i E [m] for which Ig:l <.
We will define E to be the event that 1gs1 2 & for all i [m²] noting that
P[E] > 1 m- (o.1)
[|g|
E Z
mg 2/
23

---

Published as a conference paper at ICLR 2022
We can thus write [[J((G(Um)) E(((G((m))
E gryim
-[(])))))___11]1111 ( 1[1"
E ([[[G gm
(16)
By Fact A.2 f Go is A" dd-Liscciizz. Furthermore, because he(g) 1-11, 11mh, (sgn(he(0) he(o))
m. We can thus upper bound (T6) by
< mid P(E9)= S (2/T((/))m)))) S
Wi (Go(Um), G(Tim)) S desired.
remains to bound the complexity of G. For any E [d], we can apply Lemma 2.1 with f given by the i-th output coordinate of Go and J given by the map which applies he to every entry of the input. CT.A We thus conclude that G LLS,m for
max(T". (0 (1/() max(r",
Vm/ OAA" v
L" + S 3m S" claimed.
C FOOLING RELU NETWORKS WOULD IMPLY NEW CIRCUIT LOWER BOUNDS
this section we show that even exhibiting generators with logarithmic stretch that can fool all ReLU network discriminators of constant depth and slightly superlinear size would yield break- through circuit lower bounds.
First, in Section C.1 review basics about average-case hardness and recall the state-of the-art for lower bounds against TC Then in Section C.2 we present and prove the main result of this section,
Theorem
C.I AVERAGE-CASE HARDNESS AND TC
One of the most common notions of hardness for class of functions F is worst-case hardness, that is, the existence of functions which cannot be computed by functions F.
Definition 10 (Worst-case hardness). Given class of Boolean functions F, sequence of functions fa : {= + {+1} is worst-case-hard for F if for every f {=1)" + {+1} } in F, there is some input x E [#1]" for which f(x) + (z))).
A more robust notion of hardness is that of average-case hardness, which implies worst-case hard- ness. For any fn F, rather than simply require that there some input on which f and fn disagree, we would like that over some fixed distribution over possible inputs, the probability that f and fn output the same value is small. Typically, this fixed distribution the uniform distribution over (+11", but in many situations even showing average-case hardness with respect to less natural distributions is open.
Definition 11 (Average-cane hardness). Given class of Boolean functions F, a function e:N
[0, 1/2), and a sequence of distributions (Dn), over [+1]", a sequence of functions Ja {+1)
(+1) (1/2+ + ((rr))-average-caseeeeee for F with respect (Dn) for every f: (+1)" (11)
in F.
P [f(x)= fx(x)) < + <(n). D=D,
By counting argument, for any reasonably constrained class F there must exist functions which are worstlaverage-case hard for F. A central challenge in complexity theory has been to exhibit explicit hard functions for natural complexity classes. In the context of this work, by explicit simply mean that there is polynomial-time
algorithm for evaluating the function.
The complexity class we will focus on in this section is TCº, the class constant-depth linear
threshold circuits of polynomial size:
24

---

Published as a conference paper at ICLR 2022
Definition 12 (Linear threshold circuits). A linear threshold circuit of size S and depth D is any Boolean circuit of size S and depth D whose gates come from the set G of all linear threshold functions mapping E [=1]" sgn((w, z) b) for some arity E N, vector w E R", and bias
b E I.. TC is the set of all linear threshold circuits of size poly(n) and depth (1))
The best- kest-known worst-case hardness result for TC is that of (Impagliazzo et al. 1997) who showed:
Theorem C.1 (Impagliazzoo et al., (197)). Let fn : {=1}" - {=1} be the parity function on n bits. For any depth D 2 1, any linear threshold circuit of depth D must have at least n +20 D wires, where c > O and 0 > 1 are absolute constants.
In (Chen et al. 2016) this worst-case hardness result was upgraded to an average-case hardness result with respect the uniform distribution over the hypercube. Remarkably, this slightly superlinear lower bound from (Impagliazzo et al. 1997> has not been improved upon in over two decades!
We remark that the discussion about lower bounds for threshold circuits is very limited snapshot of a rich line of work over many decades. We refer to the introduction in (Chen & Tell 2019) for a more detailed overview of this literature.
C.2 HARDNESS VERSUS RANDOMNESS FOR GANs
For convenience, given sequences of parameters D S(m) E N (these will eventually correspond to the depth and size of the linear threshold circuits against which we wish to show lower bounds) let
C)( & ppoly(d).poly(d) "e(D)),d+e(S)
This will comprise the family of ReLU network discriminators that we will focus on. We now show that if one could exhibit generators that can provably fool discriminators in CD(D, S), then this would translate to average-case hardness against linear threshold circuits of depth D and size D. Formally, we show the following:
Theorem C.2. There is an absolute constant
0 for which the following holds. Fix quences of parameters D(m),5(m) E N. Suppose there is an explici sequence of generators S c(m)
Gm : Rm + RRd(m) for d(m) 2 cm log m such that Waam ( ((m)) G for some E(m) 2 1/poly(m) and such that each output coordinate of Gm is computable by net- work in F=, then there exists sequence of functions ha(m) : {+1]d(m) + {+1} in NP which are 112++(mm)22-mm -mmmm)))) -aa--m---------a-------- -average-case caseeeaaaca-ad with respect some sequence of explicit distributions (Dn,.) for linear threshold circuits of depth (m)) and size S(m).
Remark C.3. In particular, this shows that if we could exhibit explicit generators fooling all discrimi- nators given by neural networks of polynomial Lipschitzness/bii complexity of depth D(m) and size ((((m))+oxp)) +exp(-D(m)) ))), then by (2) we would get new average-case circuit lower bounds for TC
In fact it was shown by (Chen & Tell 2019) that such result would imply TC * NC², which would be a major breakthrough in complexity. This can be interpreted in one of two ways: 1) it would be extraordinarily difficult to show that particular generative model truly fools all constant-depth, ReLU network discriminators, or 2) gives a learning-theored motivation for trying to prove circuit lower bounds.
aurely-superlincrr
Regarding the proof of Theorem studied connections between hardness and randomness in the study of pseudorandom generators. In fact, readers familiar with this literature will observe that Theorem C.2 is the GAN analogue of the "casy" direction of the equivalence between hardness and randomness: an explicit pseudorandom generator that fools some class of functions implies average-case cardddee for that class.
note that the statement is closely related to existing well-
In order to leverage this connection however, we need to formalize the link between GANs (over continuous domains) and pseudorandom generators (over discrete domains) in the next lemma. It
"Sometimes TC" is defined with the gate set taken to consist of {A, V, -} and majority gates, though these classes are equivalent up to polynomial overheads (Goldmann et al. 1992 Goldmann & Karpinski 1998), Moreover, because circuit of size S and depth D using the latter gate set clearly implementable by a circuit size S and depth using the former gate set, so our lower bounds against the former gate set immediately translate to ones against the latter. By explicis, we mean that are provided a way to evaluate these functions in polynomial time.
25

---

Published as a conference paper at ICLR 2022
turns out that in the preceding sections we already developed most of the ingredients for establishing this connection.
Lemma C.4. Suppose there is an explicit sequence of generators Gm R - Rd(m)) such that Cattm ((m)) (Gm [m); dmm) S e(m) for some e(m) = 1/poly (m) and such that each output coordinate of Gm is computable by network in F Then there is explicit sequence of pseudorandom generators G {{+]]((m) - {+1) ( for n(m) = (m log m) that 2e(m))-fool linear threshold circuits of depth D(m) and size S(m).
Proof. As in the proofs of the theorems from Section 3 the parameter will be clear from context, so we will drop m from subscripts and parenthetical references.
Recall the function hg from Lemma 3.10 we will take ç = c/poly(m). Also define n - (log(m/e)) and recall from the proot of Lemma 3.8 the definition of the linear function J Rmn + R"; for every E [m]] the i-th output coordinate of J is the linear function which maps Rm to (w,, x + 1), where w, is zero outside of indices ((i-1) 1) n + I...., n) and equal to the vector (1/4,1/8..... 1,/,1/ 1/2"+1) on those indices.
Given generator G fooling Ca. we will show that the Boolean function G' {=1]mm {+1}a given by
G² he G
is pseudorandom generator that fools TC circuits. To that end, suppose there was TC circuit f: [=1]dd + } for which [f' mm))]] E[f(Ua)] > 2e. We will show that this implies
the existence of a ReLU network f Ca(D, for which [G] E[f c.
Our proof proceeds in three steps: argue that
1. o Ca(D,S)
2. [(((Ua)) x (iS(he(La) (Ta))]
3. E[G = B[f(hg(G([mm))
Note that 2 and 3, together with the fact that is discriminator for G¹, imply that f & f he a discriminator for G. then ensures that this discriminator is a ReLU network with the right complexity bounds, yielding the desired contradiction.
To show step 1, we will show that f can be computed by a network in (ooly()).poy(d)) poly).o) and then apply Lemma 2.1 and Lemma 10 Suppose the threshold circuit computing f has depth D, where D is some constant. Recall from Lemma A.7 that may assume, up to additional blowup in size by D, that the constant-depti threshold circuit C' computing f is comprised of layers Si...., Sp such that Sy consists of all gates in C for which any path from the inputs to the gate is of length
Let k; denote the number of gates in S; (where k = 1), and for each E [Ki], suppose the linear threshold function computed by the j-th gate in S, given by sgu( sgn((w.,5 - -b,,) for way E R As each linear threshold takes at most poly(d) bits as input, we can assume without loss of generality that b.j and the entries of w lie in R, for poly(d). For this r, note that for any w RR R,, x E (+1]*,
sgu((w, x) - 6) = hg ((w, x) b),
for some g = 1/poly (d), where h1 /d) (.) is the function defined in Lemma 3.10 and recall
from the proof of Lemma 3.10 that it can be represented as two-layer ReLU network via (5). For
every i E [D], we can thus define two weight matrices w(l)) 222 xk; and w!(2
E R x22; by
Wi.1
0
Wi,1
( (1)
w!!
Wikk
26

---

Published as a conference paper at ICLR 2022
and biases 6 RR2 and b,2) RR by
6 = (1,-1,1, -1, I, -1) 6,²)= = ---1.....
so that for all x E {+1}"
f(z) - W ( (...((()))) (w(" +
+ + (17)
The entries of the weight matrices and bias vectors are clearly in [poly(d) and because each hg is poly(d)--ipschitzz and there are D (1) layers in the circuit, the funetion in (17) is poly(d)- Lipschitz as a function over Rd. The size and depth of the network are within a constant factor of the size S and depth D of the circuit. Lemma 2.1 and Lemma 3.10 then imply that f fo hi has depth (D) and size 3d + ((S), as well as Lipshitzness and bit complexity polynomial in m because e 2 (/poly(m) so that ç 2 1/poly(m). Therefore, f hg E CD.
To show step 2. recall from Lemma 3.11 and Remark 3.12 that (U (Im)) < c/))ly(m). Recalling that f is poly(d)
poly(mm)-Lipshhitz we obtain the desired inequality [E(((2))] (hg())]] I c/2. Here the factor of 1/2 is an arbitrary small constant coming from taking the poly(m) the definition of & sufficiently large.
Finally, to show step 3, recall by Fact 3.7 that Wi (J(UU I S </poly(( by our choice of n = (log(mm/e) (the e² comes from taking the constant factor in the definition of n sufficiently large). By applying Fact A.2 folg and G. we know that the composition f fo oG is poly(m)/e- Lipschitz. It follows that E (Un.)) ( (h((())) I c/2. The factor of 1/2 is an arbitrary small constant coming from taking the constant factor in the definition of sufficiently large.
Putting everything together, we conclude by triangle inequality that B[f(G([m)) E[f(Ta)] 6,
a contradiction.
The following lemma gives the standard transformation from pseudorandom generators average- case hardness. We include a proof for completeness.
Lemma C.5 (Prop. 5 of (Viola) 2009)). Suppose the sequence of functions G.n [=1]
(+1]dm)) e(m))-ools class of Boolean functions F. Define the function ha(m) {=1]d(m)
{+1} by
hdim) (o)
exists y {+1)m such that G(y)
otherwise
Let Dalm)) be the distribution over (m1]d(m) given by the uniform mixture between Ua(m) and G(Um)..
Then the sequence of functions (ha(m)) } is (1/2 + e' (Da(m)) for e'(m) e(m)/4 /4+ + 2mm-2(m))) d(m)-1
for FF with respect to Proof. As usual, we will omit most subscripts/parenthesss referring to the parameter m. Let f [+1]²= {+1} be any function in F. Then
(Df = ha 2 P(f(Ua) = ha(Uu)) + F(f(G(Um)) = ha(GUU))))
(P(f(Ua) 0] + +Plha(Ua) 1]) P[f(G(U,..)
2
1
(PIf(Ua) 0] + 2 2m--) Pif(G(U,m) = 1]
2
1
1
(PIf(U2) = +] 2 + (P(f(Ua) = =1]
2
2 + +
where in the second step we used a union bound and the fact that h(G(Um)) )) is deterministically by construction, in the third step used the fact that Plha(Us)] < 2 because there are at most
2t elements in the range of G, and in the fourth step we used the fact that G e-fools functions in F.
27

---

Published as a conference paper at ICLR 2022
We now ready to prove Theorem C.2
Proof of Theorem C.2 By Lemma C.4 we can construct out of the generators Gm an explicit se- quence of pseudorandom generators that stretch (m log m) bits to d(m) c log m bits and 2c(m)-fool linear threshold circuits of size S(m) and depth D(m). The theorem follows upon substituting this into Lemma C.5 which implies (1/2 + ((m))--vrrgge-ccs--haaee
for such circuits with respect to the explicit distributions D Da(m) defined in Lemma C.5 where e'mm) c(m)/2+ 20 log m) -(m)) e(m))/2+m -9(m), provided the absolute constant e sufficiently large.
Finally, note that the average-case-han functions ha(m) we get from Lemma C.5 are in NP because given input and certificate y, one easily verify whether G(y)
28


Reviews:
[{"review_id": "czr6XlpgLbm", "reviewer": "Reviewer_DfoH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is interesting. However, I have the following questions about the presentation and its significance. \n\n1. The assumption on the diversity of the data distribution is not discussed in detail, especially the one used in the main Theorem. The authors only say it is a large family of distributions while it is unclear and not so intuitive for readers.\n\n2. How large is the $\\epsilon(m) poly(m)$ in Theorem 3.1? Is it meaningful in practice? Does the result provide any insight on training GANs since the estimation of the Wasserstein-1 metric is monitored during training? \n\n3. As discussed in the conclusion, the paper only proves the existence of a \"bad\" generator while optimizing the GAN objective does not always lead to the worst case. The authors claim \"MINIMAX OPTIMALITY $\\textbf{(PROBABLY)}$ DOESN’T IMPLY DISTRIBUTION LEARNING FOR GANS\" while the paper does not discuss how likely we really meet this in practice, which limits the significance of the paper.\n\n4. There is a gap between the experiments and theory. The authors train 4 different discriminators, which may not cover all of the possible ones. It would be better if the authors can conduct an example where the generator can cheat all of the discriminators.", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall, I think this is an interesting paper and currently, I tend to accept it if all of the concerns are well addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "UHus2KLJUfs", "reviewer": "Reviewer_qEsw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results are novel, interesting, and non-trivial. The construction draws connections between GANs and local PRGs which is interesting. \n\nThe authors interpret the result of the paper as saying \"minimax optimality does not imply distribution learning\". This is by itself a rather inaccurate statement: distribution learning is naturally defined based on a measure of success. The authors have shown that minimax optimality does not imply learning w.r.t. Wasserstein distance (under some assumptions). The choice of Wasserstein is natural but somewhat arbitrary. For example, if we change the Wasserstein to another IPM (e.g,. one which is directly defined based on set of neural nets rather than Lipschitz functions) then the result would be false. In fact part of the success of GANs in applications like image generation can be attributed to the fact that they don't really optimize the usual notions of distance/divergence between distributions. This has been discussed to some extent in the conclusions of the paper, but I still think the message of the paper in other parts of the paper can be misleading.\n\nI think the presentation of the paper can be significantly improved. More specifically, some of the notations are hard to follow. Moreover, some background on PRGs are missing in the main text, making it hard to follow the paper for those who are not familiar with them (I suppose this is the case for most of the audience of this ICLR submission)\n\nMy understanding is that the authors use random networks as their generators, and this enables to have generators that receive discreet seed distributions but the distribution of their output is continuous. Therefore my understanding is that one of the main reductions of the paper does not go through with the use of deterministic (e.g, ReLU) nets. Please elaborate. If this is the case, then it should be mentioned clearly, since most generators used in practice adopt deterministic networks.\n\nThe experiments section is rather weak. For one, the target distribution is chosen to be discreet whereas in usual applications the target distribution is rather continuous (like images). \n\n=================\nMore comments\n\n+ In Theorem 1, $\\gamma_m$ is not defined before.\n+ throughout the intro (e.g., theorem 1), we see \"polynomial discriminator\" and \"polynomial generator\"; it would be helpful if you mention the parameter(s) w.r.t. which we are taking about in each case\n+ would be helpful to define negl function in the main text since it's been used in the main theorem statements\n+ In Thm 3.1 we see that the size of the parameters as well as W_{F*} depend on \\epsilon(m). This makes it hard to evaluate the strength of the bound. In other words, the generator is also getting more complicated as m grows. Can you demonstrate the power of your bound by choosing a good \\epsilon(m)?\n+ In equation (1) we see $D_{d(m)}$. Should this be $f(D^*_{d(m)})$?\n\n", "summary_of_the_paper": "The papers offers strong evidence that even if (population) minimax optimality is satisfied for a GAN the generator may not have learned the distribution with respect to the Wasserstein distance. More specifically, the authors show that there exits distributions that:\n\n+ can be generated by simple generators nets (variants of randomized ReLU nets with constant depth and polynomial size and Lipschitzness) that are fed with simple seed distributions (e.g., uniform on a cube)\n+ are discrete and far (in Wasserstein distance) from any \"diverse\" distribution\n+ cannot be distinguished from (a simple) diverse target distribution using any polynomial discriminator network (polynomial size/depth/Lipschitzness)\n\nThe proof is based on a cryptographic assumption, namely the existence of a local pseudo-random generators (they use a specific one proposed by Goldreich).", "summary_of_the_review": "This is a solid work and proves an interesting result. The presentation can be improved, and in general the paper is not easy to read. The experiments are quite weak.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PQ71X4acVIy", "reviewer": "Reviewer_yN8S", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper reduce the problem of \"whether there exists a bad solution of GAN objective\" to the existence of local pseudorandom generators. This is an interesting and novel idea. Then the paper shows that under some artificial case, the min-max optimality cannot imply that the GAN learns the distribution. The paper is highly theoretical. \n\nMy major concern is the significance of the result. It seems to be well-known and intuitive that fooling a weak class of discriminators does not imply exactly learning the target distribution. \n\nBesides, I would like to provide some suggestions for the paper writing. \n\n1. In Theorem 1.1, the $\\gamma_m$ is not defined. This makes the theorem hard to understand.\n\n2. Definition 5 is extremely difficult for people who are unfamiliar with cryptography to understand. What do \"uniformly random k-uniform hyper-graph\" and \"k-ary predicate\" mean? I also cannot understand what is \"circuits in P/poly\". \n\n3. In Lemma 2.4, the authors should indicates the failure probability, that is, with probability at least $1-\\delta$ the result holds. Otherwise the lemma just looks erronous.\n\n4. There are a lot of Lemmas that are spread across the paper that make the paper looks somewhat broken and also increase the burden for readers to understand. For example, Lemma 2.1 is only used in the Proof of Theorem 3.6. Lemma 2.3 looks immediate from the definition and is never used in the paper. The authors may not want to present those Lemmas in the paper. ", "summary_of_the_paper": "The paper shows that if Goldreich’s PRG is able to fool all Boolean circuits of polynomial size, then we can construct a poly size ReLU network as a generator that outputs a distribution that has a constant $W_1$ distance to the target distribution but all poly-size ReLU networks cannot discriminate between the two distributions.\n", "summary_of_the_review": "The paper is highly theoretical. My major concern is the significance of the result. It seems to be well-known and intuitive that fooling a weak class of discriminators does not imply exactly learning the target distribution.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "Efa5gD-q7Rc", "reviewer": "Reviewer_v7TX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well organized. Although there are many technical details, which are relatively hard to follow every bit, it is due to the rigor and complexity of the theory. I like the flow of the paper, especially building the theory from easier discrete cases to continuous generalization. Yet some improvement can be made in Section 3.2 and Section 3.3. For example, the connection between Section 3.2 and Section 3.1 is somewhat vague, and some high level idea of extending binary output to continuous output is helpful appearing before Theorem 3.6.\n\nThe experiments are for illustrative purpose. However, I find it a bit confusing. Does figure 1 report the training loss or testing loss? If I understand correctly, we should achieve approximately zero training loss, while the Wasserstein distance between the data distribution and the generated distribution shows a nonzero gap. In figure 1, the Wasserstein distance is claimed to be large, without numerical verification. By the way, I am curious how is the loss $\\mathbb{E}[-\\log (D(X))] + \\dots$ is computed.", "summary_of_the_paper": "The paper provides an interesting negative result on that polynomial sized discriminator lacks sufficient discriminative power to distinguish the data distribution and generated distribution by a constant depth generator. The argument rigorously indicates that a small neural IPM over the discriminator network can still yield a large Wasserstein distance.", "summary_of_the_review": "The theory in the paper utilizes polynomially-sized Boolean circuit theory, which is an interesting connection. The paper does not have obvious contribution to practically trained GAN models, however, this hardness result provides revealing insights of GANs. In fact, the paper opens some directions to investigate and should be highly important to GANs. For example, if we change the architecture of the generator, does the discriminator in the paper still lack power? Maybe an easier (somewhat orthogonal) question is if the generator network is powerful in representing the data distribution in Wasserstein distance, does there exists good choice of discriminator (poly size for example) to guarantee the distribution recovery in Wasserstein distance. Overall, I am positive on the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "33suSG1lxSZ", "reviewer": "Reviewer_h3Jv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Major Comments:\n\n- The potential impact of this paper is strong: by revealing that the class of poly-sized discriminator may not be rich enough to achieve distributional learning, the paper motivate us to reconsider if GAN is more suitable for feature learning rather than distributional learning. Given the successful empirical performance of GAN, one may also reconsider if Wasserstein distance is a reasonable objective function to use.\n\n- The assumptions imposed by the paper such as poly-sized neural network discriminators and diverse target distribution seems natural. \n\n- To the best of my knowledge, it is novel to apply pseudorandom generators theory to study GAN. \n\n- The numerical part is simple but enough to support the validity of the theory.\n\nMinor Comments (several typos in the paper):\n\n- Definition 2: $\\mathbb E_{x\\sim q}(f(y))$\nshould be replaced by \n$\\mathbb{E}_{x\\sim q} (f(x))$?\n\n- Eq (1): $\\mathcal D_{d(m)}$ \nshould be replaced by \n$\\mathcal D^{\\ast}_{d(m)}$?\n\n- Last sentence in the proof sketch of Theorem 3.2: we get that there exist a threshold $t\\in \\mathbb{R}_{\\mathrm{poly}(d)}$ for which $|\\mathbb{E}[\\mathcal{M}_\\tau(G(U_m))] - \\mathbb{E}[\\mathcal{M}_\\tau(U_d)]|,...$, I suspect the inequility for $|\\mathbb{E}[\\mathcal{M}_\\tau(G(U_m))] - \\mathbb{E}[\\mathcal{M}_\\tau(U_d)]|$ is incomplete here.", "summary_of_the_paper": "The paper leverages the techniques in cryptographic to prove a surprising result that a uniform small error against against all poly-size neural network discriminators can not guarantee a small error in type-1 Wasserstein distance. ", "summary_of_the_review": "The paper provides a new perspective on the important problem if GAN is able to achieve distributional learning. In general, the paper is well-written, and to the best of my knowledge, the proposed methodology is novel to this type of problem. Thus I recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The provides a complexity theoretic look at GANs. The exposition is multi-disciplinary, and in my personal opinion, it is an interesting look at the GANs in the context of random number generators.
Decision: Accept (Poster)