Venue: ICLR 2018 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 
Summary:
This paper studies GANs in the following LQG setting: Input data distribution (P_Y) is Gaussian with zero mean and Identity covariance. Loss function is quadratic. Generator is also considered to be a Gaussian distribution (linear function of the input Gaussian noise). The paper considers two settings for discriminator: 1)Unconstrained and 2) Quadratic function. For these settings, the paper studies the generalization error rates, or the gap between Wasserstein loss of the population version (P_Y) and the finite sample version (Q_n(Y)). The paper shows that when the discriminator is unconstrained, even though the generator is constrained to be linear, the convergence rates are exponentially slow in the dimension. However constraining the discriminator improves the rates to 1/\sqrt{#samples}. This is shown by establishing the equivalence of this setting to PCA.


Comments:


1) This paper studies the statistical aspects of GANs, essentially the sample complexity required for small generalization error, for the simpler LQG setting. The LQG setting reduces the GAN optimization to essentially PCA and I believe is too simple to give insights into more complex GANs. 

2)The results show that using high capacity neural network architectures can result in having solutions with high variance/generalization error. However, it is known even for classification that neural networks used in practice have high capacity (https://arxiv.org/abs/1611.03530) yet generalize well on *real* tasks. So, having slow worst case convergence may not necessarily be an issue with higher capacity GANs, and this paper does not address this issue with the results.

3) The discussion on what is natural loss is very confusing and doesn't add to the results. While least squares loss is the simplest to study and generally offers good insights, I don't think it is either natural or the right loss to consider for GANs.

4) Also the connection to supervised learning seems very weak. In supervised learning generally Y is smaller dimensional compared to X, and generalization of g(X) depends on its ability to compress X, but still represent Y. On the contrary, in GANs, X is much smaller dimensional than Y.
review_title: LQG setting reduces the GAN optimization to essentially PCA and I believe is too simple to give insights into more complex GANs. 

final_score: rating: 4: Ok but not good enough - rejection
review_content: First of all, let me state this upfront: despite the sexy acronym "GAN" in the title, this paper does not provide any genuine understanding of GANs. Conceptually, GANs are an algorithmic instantiation of a classic idea in statistics, mamely minimum-distance estimation, originally introduced by Jacob Wolfowitz in 1957 (*). This provides the 'min' part. The 'max' part comes from considering distances that can be expressed as a supremum over a class of test functions. Again, this is not new -- for instance, empirical risk minimization, in both supervised and unsupervised learning, can be phrased as precisely such a minimax problem by casting the convergence analysis in terms of suprema of suitable empirical processes (see, e.g., "Empirical Processes in M-Estimation" by Sara Van De Geer). Moreover, even the minimax (and, more broadly, game-theoretic) criteria go back all the way to the foundational papers of Abraham Wald.

Now, the conceptual innovation of GANs is that this minimax formulation can be turned into a zero-sum game played by two algorithmic architectures, the generator and the discriminator. The generator proposes a model (which is assumed to be easy to sample from) and generates a sample starting from a fixed instrumental distribution; the discriminator evaluates the current proposal against a class of test functions, which, again, are assumed to be easily computable, e.g., by a neural net. One can also argue that the essence of GANs is precisely the architectural constraints on both the generator and the discriminator that make their respective problems amenable to 'differentiable' approaches, e.g., gradient descent/ascent with backpropagation. Without such a constraint, the saddle point is either trivial or reduces to finding a worst-case Bayes estimate, as classical statistical theory would predict.

This paper essentially strips away the essence of GANs and considers a stylized minimum-distance estimation problem, where both the target and the instrumental distributions are Gaussian, and the 'distance' between statistical models is the quadratic Wasserstein distance induced by the Euclidean norm. This, essentially, stacks the deck in favor of linear strategies, and it is not surprising at all that PCA emerges as the solution. It is very hard to see how any of this helps our understanding of either strengths or shortcomings of GANs (such as mode collapse or stability issues). Moreover, the discussion of supervised and unsupervised paradigms is utterly unconvincing, especially in light of the above comment on minimum-distance estimation underlying both of these paradigms. In either setting, a learning algorithm is obtained from the population version of the problem by substituting the empirical distribution of the observed data for the unknown population law.

Additional minor comments on proper attribution and novelty of results:

1) Lemma 3 (structural result for optimal transport with L_2 Wasserstein cost) is not due to Chernozhukov et al., it is a classic result in the theory of optimal transportation, in various forms due to Brenier, McCann, and others -- cf., e.g., Chapters 2 and  3 of C. Villani, "Topics in Optimal Transportation."

2) The rate-distortion formulation with fixed input and output marginal in Appendix A, while interesting, is also not new. Precise characterizations in terms of optimal transport are available, see, e.g., N. Saldi, T. Linder, and S. Yuksel, "Randomized Quantization and Source Coding With Constrained Output Distribution," IEEE Transactions on Information Theory, vol. 61, no. 1., pp. 91-106, January 2015.

(*) The method of Wolfowitz is not restricted to distance functions in the mathematical sense; it can work equally well with monotone functions of metrics -- e.g., the square of a metric.
review_title: This work does not explain GANs, it merely revisits minimum-distance density estimation

final_score: rating: 4: Ok but not good enough - rejection
review_content: *Paper summary*

The paper considers GANs from a theoretical point of view. The authors approach GANs from the 2-Wasserstein point of view and provide several insights for a very specific setting. In my point of view, the main novel contribution of the paper is to notice the following fact:

(*) It is well known that the 2-Wasserstein distance W2(PY,QY) between multivariate Gaussian PY and its empirical version QY scales as $n^{-2/d}$, i.e. converges very slow as the dimensionality of the space $d$ increases. In other words, QY is not such a good way to estimate PY in this setting. A somewhat better way is use a Gaussian distribution PZ with covariance matrix S computed as a sample covariance of QY. In this case W2(PY, PZ) scales as $\sqrt{d/n}$.

The paper introduces this observation in a very strange way within the context of GANs. Moreover, I think the final conclusion of the paper (Eq. 19) has a mistake, which makes it hard to see why (*) has any relation to GANs at all.

There are several other results presented in the paper regarding relation between PCA and the 2-Wasserstein minimization for Gaussian distributions (Lemma 1 & Theorem 1). This is indeed an interesting point, however the proof is almost trivial and I am not sure if this provides any significant contribution for the future research.

Overall, I think the paper contains several novel ideas, but its structure requires a *significant* rework and in the current form it is not ready for being published. 

*Detailed comments*

In the first part of the paper (Section 2) the authors propose to use the optimal transport distance Wc(PY, g(PX)) between the data distribution PY (or its empirical version QY) and the model as the objective for GAN optimization. This idea is not novel: WGAN [1] proposed (and successfully implemented) to minimize the particular case of W1 distance by going through the dual form, [2] proposed to approach any Wc using auto-encoder reformulation of the primal (and also shoed that [5] is doing exactly W2 minimization), and [3] proposed the same using Sinkhorn algorithm. So this point does not seem to be novel.

The rest of the paper only considers 2-Wasserstein distance with Gaussian PY and Gaussian g(PX) (which I will abbreviate with R), which looks like an extremely limited scenario (and certainly has almost no connection to the applications of GANs).

Section 3 first establishes a relation between PCA and minimizing 2-Wasserstein distance for Gaussian distributions (Lemma 1, Theorem 1). Then the authors show that if R minimizes W2(PY, R) and QR minimizes W2(QY, QR) then the excess loss W2(PY, QR) - W2(PY, R) approaches zero at the rate $n^{-2/d}$ (both for linear and unconstrained generators). This result basically provides an upper bound showing that GANs need exponentially many samples to minimize W2 distance. I don't find these results novel, as they already appeared in [4] with a matching lower bound for the case of Gaussians (Theorem B.1 in Appendix can be modified easily to show this). As the authors note in the conclusion of Section 3, these results have little to do with GANs, as GANs are known to learn quite quickly (which contradicts the theory of Section 3).

Finally, in Section 4 the authors approach the same W2 problem from its dual form and notice that for the LQG model the optimal discriminator is quadratic. Based on this they reformulate the W2 minimization for LQG as the constrained optimization with respect to p.d. matrix A (Eq 16). The same conclusion does not work unfortunately for W2(QY, R), which is the real training objective of GANs. Theorem 3 shows that nevertheless, if we still constrain discriminator in the dual form of W2(QY, R) to be quadratic, the resulting soliton QR* performs the empirical PCA of Pn. 

This leads to the final conclusion of the paper, which I think contains a mistake. In Eq 19 the first equation, according to the definitions of the authors, reads
\[
W2(PY, QR) = W2(PY, PZ),   (**)
\]
where QR is trained to minimize min_R W2(QY, R) and PZ is as defined in (*) in the beginning of these notes. 
However, PZ is not the solution of min_R W2(QY, R) as the authors notice in the 2nd paragraph of page 8. Thus (**) is not true (at least, it is not proved in the current version of the text). PZ is a solution of min_R W2(QY, R) *where the discriminator is constrained to be quadratic*. This mismatch is especially strange, given the authors emphasize in the introduction that they provide bounds on divergences which are the same as used during the training (see 2nd paragraph on page 2) --- here the bound is on W2, but the empirical GAN actually does a regularized training (with constrained discriminator).

Finally, I don't think the experiments provide any convincing insights, because the authors use W1-minimization to illustrate properties of the W2. Essentially the authors say "we don't have a way to perform W2 minimization, so we rather do the W1 minimization and assume that these two are kind of similar".

* Other comments *
(1) Discussion in Section 2.1 seems to never play a role in the paper.
(2) Page 4: in p-Wasserstein distance, ||.|| does not need to be a Euclidean metric. It can be any metric.
(3) Lemma 2 seems to repeat the result from (Canas and Rosasco, 2012) as later cited by authors on page 7?
(4) It is not obvious how does Theorem 2 translate to the excess loss? 
(5) Section 4. I am wondering how exactly the authors are going to compute the conjugate of the discriminator, given the discriminator most likely is a deep neural network?


[1] Arjovsky et al., Wasserstein GAN, 2017
[2] Bousquet et al, From optimal transport to generative modeling: the VEGAN cookbook, 2017
[3] Genevay et al., Learning Generative Models with Sinkhorn Divergences, 2017
[4] Arora et al, Generalization and equilibrium in GANs, 2017
[5] Makhazani et al., Adversarial Autoencoders, 2015
review_title: GANs studied theoretically under extremely strong assumptions

Meta-review: While the reviewers agree that this is an important topic, there are numerous concerns novelty, correctness and limitations. 
Decision: Reject