Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

The 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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: The paper is interesting. However, I have the following questions about the presentation and its significance. 

1. 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.

2. 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? 

3. 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.

4. 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_review: Overall, I think this is an interesting paper and currently, I tend to accept it if all of the concerns are well addressed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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:

+ 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)
+ are discrete and far (in Wasserstein distance) from any "diverse" distribution
+ cannot be distinguished from (a simple) diverse target distribution using any polynomial discriminator network (polynomial size/depth/Lipschitzness)

The proof is based on a cryptographic assumption, namely the existence of a local pseudo-random generators (they use a specific one proposed by Goldreich).
main_review: The results are novel, interesting, and non-trivial. The construction draws connections between GANs and local PRGs which is interesting. 

The 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.

I 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)

My 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.

The 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). 

=================
More comments

+ In Theorem 1, $\gamma_m$ is not defined before.
+ 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
+ would be helpful to define negl function in the main text since it's been used in the main theorem statements
+ 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)?
+ In equation (1) we see $D_{d(m)}$. Should this be $f(D^*_{d(m)})$?


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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.

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. 

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. 

Besides, I would like to provide some suggestions for the paper writing. 

1. In Theorem 1.1, the $\gamma_m$ is not defined. This makes the theorem hard to understand.

2. 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". 

3. 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.

4. 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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
main_review: Major Comments:

- 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.

- The assumptions imposed by the paper such as poly-sized neural network discriminators and diverse target distribution seems natural. 

- To the best of my knowledge, it is novel to apply pseudorandom generators theory to study GAN. 

- The numerical part is simple but enough to support the validity of the theory.

Minor Comments (several typos in the paper):

- Definition 2: $\mathbb E_{x\sim q}(f(y))$
should be replaced by 
$\mathbb{E}_{x\sim q} (f(x))$?

- Eq (1): $\mathcal D_{d(m)}$ 
should be replaced by 
$\mathcal D^{\ast}_{d(m)}$?

- 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_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.
review_title: null

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)