Venue: ICLR 2018 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The authors provide an insight into the discriminative and generalizable aspect of the discriminator in GANs. They show that the richer discriminator set to enhance the discrimination power of the set while reducing the generalization bound. These facts are intuitive, but they made a careful analysis of it.

The authors provide more realistic analysis of discriminators by relaxing the constraint on discriminator set to have a richer closure of linear span instead of being rich by itself which is suitable for neural networks.

They analyze the weak convergence of probability measure under neural distance and generalize it to the other distances by bounding the neural distance.

For the generalization, they follow the standard generalization procedure and techniques while carefully adapt it to their setting.

Generally, I like the way the authors advertise their results, but it might be a bit oversold, especially for readers with theory background.

The authors made a good job in clarifying what is new and what is borrowed from previous work which makes this paper more interesting and easy to read.

Since the current work is a theoretical work, being over 8 pages is acceptable, but since the section 4 is mostly based on the previous contributions, the authors might consider to have it in the appendix.
review_title: An interesting insight to the GANs, especially the discriminators

final_score: rating: 3: Clear rejection
review_content: In more detail, the analysis of the paper is as follows.  Firstly, it primarily focuses on GAN objective functions which are "integral probability metrics (IPMs)"; one way to define these is by way of similarity to the W-GAN, namely IPMs replace the 1-Lipschitz functions in W-GAN with a generic set of functions F.  The paper overall avoids computational issues and treats the suprema as though exactly solved by sgd or related heuristic (the results of the paper simply state supremum, but some of the prose seems to touch on this issue).

The key arguments of the paper are as follows.

1. It argues that the discriminator set should be not simply large, it should be dense in all bounded continuous functions; as a consequence of this, the IPM is 0 iff the distributions are equal (in the weak sense).  Due to this assertion, it says that it suffices to use two layer neural networks as the discriminator set (as a consequence of the "universal approximation" results well-known in the neural network literature).

2. It argues the discriminator set should be small in order to mitigate small-sample effects.  (Together, points 1 and 2 mimic a standard bias-variance tradeoff in statistics.)  For this step, the paper relies upon standard Rademacher results plus a little bit of algebraic glue.  Curiously, the paper chooses to argue (and forms as a key tenet, indeed in the abstract) that the size of the generator set is irrelevant for this, only the size of the discriminator matters.

Unfortunately, I find significant problems with the paper, in order from most severe to least severe.

A.  The calculation ruling out the impact of the generator in generalization calculations in 2 above is flawed.  Before pointing out the concrete bug, I note that this assertion runs completely counter to intuition, and thus should be made with more explanation (as opposed to the fortunate magic it is presented as).  Moreover, I'll say that if the authors choose to "fix" this bug by adding a generator generalization term, the bound is still a remedial application of Rademacher complexity, so I'm not exactly blown away.  Anyway, the bug is as follows.  The equation which drops the role of the generator in the generalization calculation is the equation (10).  The proof of this inequality is at the start of appendix E.  Looking at the derivation in that appendix, everything is correct up to the second-to-last display, the one with a supremum over nu in G.  First of all, this right hand side should set off alarm bells; e.g., if we make the generator class big, we can make this right hand side essentially as big as the IPM allows even when mu = mu_m.  Now the bug itself appears when going to the next display: if the definition of d_F is expanded, one obtains two suprema, each own over _their own_ optimization variable (in this case the variables are discriminator functions).  When going to the next equation, the authors accidentally made the two suprema have the same variable and invoke a fortuitous but incorrect cancellation.  As stated a few sentences back, one can construct trivial counterexamples to these inequalities, for instance by making mu and mu_m arbitrarily close (even exactly equal if you wish) and then making nu arbitrarily far away and the discriminator set large enough to identify this.

B. The assertions in 1, regarding sizes of discriminator sets needed to achieve the goal of the IPM being 0 iff the distributions are equal (in the weak sense), are nothing more than immediate corollaries of approximation results well-known for decades in the neural network literature.  It is thus hard to consider this a serious contribution.

C. I will add on a non-technical note that the paper's assertion on what a good IPM "should be" is arguably misled.  There is not only a meaning to specific function classes (as with Lip_1 in Wasserstein_1) beyond simply "many functions", but moreover there is an interplay between the size of the generator set and the size of the discriminator set.  If the generator set is simple, then the discriminator set can also get away with being simple (this is dicussed in the Arora et al 2017 ICML paper, amongst other places).  Perhaps I am the one that is misled, but even so the paper does not appear to give a good justification of its standpoint.

I will conclude with typos and minor remarks.  I found the paper to contain a vast number of small errors, to the point that I doubted a single proofread.

Abstract, first line: "a minimizing"?  general grammar issue in this sentence; this sort of issue throughout the paper.

Abstract, "this is a mild condition".  Optimizing over a function class which is dense in all bounded measurable functions is not a mild assumption.  In the particular case under discussion, the size of the network can not be bounded (even though it has just two layers, or as the authors say is the span of single neurons).

Abstract, "...regardless of the size of the generator or hypothesis set".  This really needs explanation in the abstract, it is such a bold claim.  For instance, I wrote "no" in the margin while reading the abstract the first time.

Intro, first line: its -> their.

Intro, #3 "energy-based GANs": 'm' clashes with sample size.

Intro, bottom of page 1, the sentence with "irrelenvant": I can't make any sense of this sentence.

Intro, bottom of page 1, "is a much smaller discriminator set": no, the Lip_1 functions are in general incomparable to arbitrary sets of neural nets.

From here on I'll comment less on typos.

Middle of page 2, point (i): this is the only place it is argued/asserted that the discriminator set should contain essentially everything?  I think this needs a much more serious justification.

Section 1.1: Lebegure -> Lebesgue.

Page 4, vicinity of equation 5: there should really be a mention that none of these universal approximation results give a meaningful bound on the size of the network (the bound given by Barron's work, while nice, is still massive).

Start of section 3.  To be clear, while one can argue that the Lipschitz-1 constraint has a regularization effect, the reason it was originally imposed is to match the Kantorovich duality for Wasserstein_1.  Moreover I'll say this is another instance of the paper treating the discriminator set as irrelevant other than how close it is to being dense in all bounded measurable functions.
review_title: This paper provides a mathematical analysis of the role of the size of the adversary/discriminator set in GANs.  It argues that on the one hand, large discriminator sets are useful as they help isolate the target distribution; on the other hand, small discriminator sets help with small sample effects.  Unfortunately, I seem to have found some flaws.

final_score: rating: 6: Marginally above acceptance threshold
review_content: == Paper Summary ==
The paper addresses the problem of balancing capacities of generator and discriminator classes in generative adversarial nets (GANs) from purely theoretical (function analytical and statistical learning) perspective. In my point of view, the main *novel* contributions are: 
(a) Conditions on function classes guaranteeing that the induced IPMs are metrics and not pseudo-metrics (Theorem 2.2). Especially I liked an argument explaining why ReLu activations could work better in discriminator that tanh.
(b) Proving that convergence in the neural distance implies a weak convergence (Theorem 2.5)
(c) Listing particular cases when the neural distance upper bounds the so-called bounded Lipschitz distance (also know as the Fortet-Mourier distance) and the symmetrized KL-divergence (Corollary 2.8 and Proposition 2.9).

The paper is well written (although with *many* typos), the topic is clearly motivated and certainly interesting. The related literature is mainly covered well, apart from several important points listed below.

== Major comments ==
In my opinion, the authors are slightly overselling the results. Next I shortly explain why:

(1) First, point (a) above is indeed novel, but not groundbreaking. A very similar result previously appeared in [1, Theorem 5]. The authors may argue that the referenced result deals only with MMDs, that is IPMs specified to the function classes belonging to the Reproducing Kernel Hilbert Spaces. However, the technique used to prove the "sufficient" part of the statement is literally *identical*. 

(2) As discussed in the paragraph right after Theorem 2.5, Theorem 10 of [2] presents the same result which is on one hand stronger than Theorem 2.5 of the current paper because it allows for more general divergences than the neural distance and on the other hand weaker because in [2] the authors assumes a compact input space. Overall, Theorem 2.5 of course makes a novel contribution, because the compactness assumption is not required, however conceptually it is not that novel.

(3) In Section 3 the authors discuss the generalization properties of the neural network distance. One of the main messages (emphasized several times throughout the paper) is that surprisingly the capacity of the generator class does not enter the generalization error bound. However, this is not surprising at all as it is a consequence of the way in which the authors define the generalization. In short, the capacity of discriminators (D) naturally enters the picture, because the generalization error accounts for the mismatch between the true data distribution mu (used for testing) and its empirical version hat{mu} (used for training). However, the authors assume the model distribution (nu) is the same both during testing and training. In practice this is not true and during testing GANs use the empirical version of nu. If the authors were to account for this mismatch, capacity of G would certainly pop up as well.

(4) The error bounds of Section 3 are based on a very standard machinery (empirical processes, Rademacher complexity) and to the best of my knowledge do not lead to any new interesting conclusions in terms of GANs.

(5) Finally, I would suggest the authors to remove Section 4. I suggest this mainly because the authors admit in Remark 4.1 that the main result of this section (Theorem 4.1) is a corollary of a stronger result appearing in [2]. Also, the main part of the paper has 13 pages, while a recommended amount is 8. 

== Minor comments ==

(1) There are *MANY* typos in the paper. Only few of them are listed below.
(2) First paragraph of page 18, proof of Theorem 2.2. This part is of course well known and the authors may just cite Lemma 9.3.2. of Dudley's "Real analysis and probability" for instance.
(3) Theorem 2.5: "Let ..."
(4) Page 7, "...we may BE interested..."
(5) Corollary 3.2. I doubt that in practice anyone uses discriminator with one hidden unit. The authors may want to consider using the bound on the Rademacher complexity of DNNs recently derived in [3]. 
(6) Page 8, "..is neural networK"
(7) Page 9: "...interested IN evaluating..."
(8) Page 10. All most ---> almost.

[1] Gretton et al., A Kernel Two-Sample Test, JMLR 2012.
[2] Liu et al, Approximation and Convergence Properties of Generative Adversarial Learning, 2017
[3] Bartlett et al, Spectrally-normalized margin bounds for neural networks, 2017
review_title: Purely theoretical paper on GANs with several novel but not groundbreaking contributions

Meta-review: I recommend acceptance. The two positive reviews point out the theoretical contributions. The authors have responded extensively to the negative review and I see no serious flaw as claimed by the negative review.
Decision: Accept (Poster)