Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper analyzes the generalization and the consistency of a function with Lipschitz continuity. In particular, the generalization and consistency bounds of Neural Networks (NNs) with Dropout or Spectral Normalization are derived. The number of layers
is logarithmic in sample size. Furthermore, the generalization of a GAN, whose discriminator and generator are both Lipschitz continuous, is given. 

main_review: In this work, the authors provide the generalization and consistency of Lipschitz neural networks (NNs) with spectral normalization and dropout. Consistency is basically the difference between the objectives achieved at the optimal solution and a computed solution. In order to get a meaningful generalization bound, previous results require the number of layers to be linear to the number of samples in the worse case, whereas the authors reduce the number of layers to be logarithmic in the sample size. Furthermore, the authors derived the Lipschitz-based generalization bounds for GANs, showing that imposing zero-order and first-order constraints on GAN loss could improve GAN generalization. 

Overall I think this is a work with very interesting theoretical results. The theoretical results are novel and the analysis seems to be solid. I have the following questions:

1. What does "curse of dimensionality" mean in this paper? When talking about the "curse of dimensionality", I thought that the dimensionality of each data sample is high, but it seems that the "curse of dimensionality" means something else in this paper. Is it the number of neural network layers?

2. In Theorem 1, 1 there is a $\lambda$ which is multiplied on $L$. Does that mean you can set an arbitrarily small $\lambda$ such that you do not need the Lipschitz continuity to ensure a function to generalize? 

3. $q$ in Theorem 2 and 3 are re-used. $q$ appears in Theorem 3, 1 SN-DNNs and 2 Dropout DNNs, but have different meanings. In one line below Dropout DNNs in Theorem 3, there is one sentence “If the number of layers $K \ge -\frac{1}{2} \log_q m$”, which $q$ is this?

4. I understand in Theorem 1 that a smaller Lipschitz constant $L$ could lead to better generalization performance. But I’m also wondering, could a smaller $L$ also induce a higher  $F(P_z, h^*)$ value in Theorem 5 and 6? Does that mean adding the Lipschitz constraint to NNs is bad, i.e., reducing the network capacity such that the error is always high? Similarly, in Sec. 4, could a smaller $L_g$ for the generator reduce the power of the generator to model the real data distribution? 

5. The bound in Theorem 8 is loose. Did the authors tighten the bound using spectral norm or Dropout? 

6. The authors analyze the effectiveness of using Lipschitz constraints in GANs from the generalization perspective. But I don’t think simply from the generalization error is sufficient to explain the effectiveness of imposing Lipschitz constraints. I think Lipschitz constraints could make the optimization of GANs easier, preventing the gradient from vanishing and exploding, as analyzed in the WGAN-GP paper. 

summary_of_the_review: The theoretical results are novel and solid to me.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper's primary focus is to provide insights into the relation between Lipschitz-continuity and the generalization of DNNs. 
Compared to previous work, tighter bounds connecting the Lipschitz-constant of the "loss" and the expected loss of the learned function are provided. The paper also provides insights into why SN and Dropout improve generalizability in DNNs. Some quite insightful theorems connecting the generalizability of GANs to various empirical tricks commonly used to improve their performance are also provided. 
main_review: The paper is very interesting and pretty much self-contained. It is fairly organized and connected to previous theoretical and empirical findings in the community (good related work). The background required to understand the details is provided and some quite interesting theorems are discussed and proven.  
A few minor issues can be improved to make it easier to understand some sections and claims of the paper.
 
* in the abstract "..our bounds show that penalizing the zero- and first-order informations of the GAN loss will..." it might not be clear yet what zero or first-order information means.

* notation of Z used both for data and noise in GAN isn't a good choice.

* output of D to be in [α, β] ⊂ (0, 1) as suggested by Salimans et al. (2016). While I agree with the authors that many implementations of saturating GANs do so (e.g. α = 0.1 β=0.9), to the best of my knowledge. Salimans et al only set  β < 1 but keep α at 0. 

* page 9, first line:  "one player (D or G) only can help, but maybe not enough" remove "only"?

* page 15, Definition 2: I think \bf{S} is a subset of Z^m (not an element) and ε(·) is from the power set of Z^m to R? 

summary_of_the_review: I find the paper's findings quite interesting and to be the best of my verification correct.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors provide generalization bounds on GANs and some DNNs in terms of the Lipschitz continuity of the networks and loss functions. These bounds show that by decreasing the Lipschitz constant of the networks and loss functions, one can generalize better. Moreover, they show that with dropout and spectral normalization, one can escape the curse of dimensionality in terms of generalization error. Finally, they claim that this theory supports the empirical results we see when GANs which use Lipschitz penalization (e.g., WGAN, GP-WGAN, SN-GAN, etc.) perform well in practice.
main_review: **Writing in the abstract and introduction:**

The introduction and abstract are not written well and need several revisions before the paper is fit for publication. This is one of the biggest weaknesses of the paper. I will provide three examples here of areas of improvement. Specifically, the introduction does not do the paper justice and can easily turn off a reader before they even get to the bulk of the work (which is interesting and has value). 
1) The whole abstract is very vague and doesn’t explain much. The first sentence is not saying almost anything at all and the last sentence mentions “the long mystery of why imposing a Lipschitz constraint can help GANs to generalize well in practice” offhandedly. The last sentence was actually very confusing to me at first because plenty of work discusses Lipschitz constraints on GANs, so initially I thought that the authors were not aware of these (not-so-obscure) papers. However, after reading the related works I understood that the authors meant something more like “although experimentally Lipschitz constraints have been used with great success, the relationship between imposing a Lipschitz constraint and GAN generalization is not theoretically understood”. Whatever the authors choose to say, it should be really clear what they mean, ESPECIALLY in the abstract and introduction. 
2) There are also several typos and things that are worded strangely. For example, in the second paragraph it is written “... two players competing each other.” This should be “... competing against each other.” 
3) The introduction does very little to explain the actual problem in the context of literature. The authors say that “little has been known about the generalization of the trained players” and “The standard learning theories still lack an efficient tool to analyze GANs”. These are too vague for a reader to understand what THIS paper is addressing specifically. 

**Specificity and confusing things:**

The authors lack specificity in several areas. Without being specific, the paper is confusing and the reader must guess what is going on. I will provide three examples here of the lack of specificity. The following are all weaknesses:

1) In the abstract itself, the authors say that GANs are “complex” in their first sentence. This is true in many ways so it is unclear how the authors address this. They say that they use efficient tools, but what does efficiency even mean here? In other words, in the abstract it isn’t clear how the work done is addressing actual open problems because of a lack of specificity. 
2) In the first paragraph of the paper, they introduce the latent distribution z. In section 3, they call the data distribution (as far as I can tell) z, which is confusing. If they want to use z to represent both the latent variable and the data, then they should explicitly say that they are switching notation, although they should just stick to one.
3) The theorems and lemmas are labeled together; for example, Theorem 1, Theorem 2, Theorem 3, Lemma 4, then Theorem 5 without having Lemmas 1-3 and 5 and not having Theorem 4. However, the corollaries have independent numbering, which is confusing when trying to find things. Stick to one convention.

**Theorem 1:**

Many of the assumptions are valid, which is a big strength. For example, it is reasonable that Z is bounded by B as image datasets typically lie in the hypercube.
However a few of the assumptions are not representative for GANs in practice, which is a weakness. It doesn’t seem reasonable that the loss is bounded, as most losses are not. The typical GAN loss stated in this paper is not bounded and hence Theorem 1 does not apply. The Wasserstein loss and f-divergences in general need not be bounded. So, the authors need to justify this hypothesis. 
Regardless, this result is very interesting and a great contribution (strength). The result that you can generalize better with simpler functions seems to go against the intuition that a highly complex hypothesis class is beneficial. Although this raises the important question… Since the generalization error is based on the loss f (and F), are we just generalizing better because we are making BOTH $F(P_z, h)$ and $F(\hat P_z, h)$ less able to distinguish differences? For example, clearly if we choose f = 0 then it is 0-Lipschitz and we get “perfect generalization” but obviously this isn’t good. This is a weakness until it is explained.

**Theorem 2 and 3:**

Theorem 3 is great and reasonable (strength). The authors do a great job showing how dropout and spectral normalization can be used to get better generalization bounds. It seems to me that Theorem 2 might be better renamed as a proposition because it isn’t central and not very hard to prove. But that’s just my opinion.

**Section 3.2:**

In Theorem 5 and Corollary 1, it is not clear that these models are consistent, which is a weakness. This needs to be cleared up because that is the claim of this section. Obviously as $m \rightarrow \infty$ we have that $2(LB + 2C)m^{−\alpha/n} \rightarrow 0$ but we don’t know if $\epsilon_0 \rightarrow 0$. Of course, the authors have this as a condition in Corollary 1, but when this condition is met is not known as far as I can tell. Because of this, one cannot conclude that the models are consistent. The authors mention that sometimes $\epsilon_0 = 0$ but this just shows that $\epsilon_0 = 0$ is attainable.

**Section 4.1:**

The authors state “Theorem 7 also suggests that penalizing the zero-order (C) and first-order (L) informations of the loss can improve the generalization.” This is true but it begs the question, as I mentioned above, of why? More specifically, if L becomes 0, then the loss becomes meaningless. In this case, we have that we generalize perfectly but it is not interesting. If C is decrease, why does this matter? If it is just an upper bound on the loss (as mentioned on assumption 1) then this is interesting but not intuitive. However, if the whole loss is bounded as explained in the second paragraph of Section 3, then it is clear why generalization is good, because with C = 0, the loss will always be zero and hence we generalize perfectly again but the problem is not interesting. The authors need to address these core ideas and hence this is a weakness.

**Note on theory:**

Overall the theory seems very thorough and correct, although I did not go through the proofs. For this reason, this is a strength, a really big one. The authors do a great job on the actual theory and I did not find a problem with it. Most of the paper’s weaknesses which I state above are with the writing or the interpretation of the results.
summary_of_the_review: Please provide a short summary justifying your recommendation of the paper.

**Strengths:**

1) The math is solid and seems well developed.
2) The results are interesting as they tie generalization to Lipschitz continuity.

**Weaknesses:**

1) The abstract and introduction are poorly written
2) The implications of the mathematical results have serious potential logical problems. I asked the authors to clarify in case there is some confusion. However, as it stands, it seems to me that their limiting-Lipschitzness idea does not actually reflect good generalization in practice, which is what they claim. This is because in their framework, one can use the 0 function for generator and loss and “generalize perfectly” although this is not intuitively what we want.
3) The consistency results are also questionable because they have a hypothesis in the theorems that is almost as strong as the result, which causes an almost circular reasoning. To be blunt, the actual logic is correct, but their result is very weak given this hypothesis.

If the authors had addressed these two weaknesses, I would have given them an 8 since this paper is solid otherwise.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper tries to bound the generalization error of deep learning models and generative adversarial networks with the Lipschitz coefficient of the model. The main idea supported by the paper's discussion is that bounding the Lipschitz constant of the neural networks will lead to good generalization performance. The paper observes the connection between spectral normalization and norm-bounded dropout with the Lipschitz coefficient of the neural network and extends the proven bounds to those regularization methods. 
main_review: Generative adversarial networks (GANs) usually achieve satisfactory generalization performance in practice, although their optimization problems are solved over deep neural network models with large capacities. This paper attempts to understand how the generalization error will depend on the Lipschitz constant of the neural networks in GANs. To reach this goal, the paper shows Theorem 1 bounding the generalization error with the Lipschitz constant of the neural network function (L) and the diameter of the learned variables B. Then, the paper applies this result to the GAN problem and connects the assumption on the Lipschitz constant to spectral normalization and dropout regularization techniques.

The paper studies a highly interesting theoretical problem to understand the success of Lipschitz regularization methods. However, I think the shown bounds are too conservative and do not justify the generalization success in GANs. This is because the generalization result in Theorem 1 aims to bound the generalization error uniformly over the entire space of 1-Lipschitz functions. Consequently, the bounds are all exponentially growing with the dimension of data vector (n) and become vacuous for moderately high-dimensional data vectors with a dimension greater than 20 or so. Therefore, the bounds do not address the curse of dimensionality in deep learning experiments and only show the generalization error is bounded with an exponential function of dimension n which does not apply to practical deep learning settings.  On the other hand, the generalization bound in (Arora et al 2017) does not exponentially grow with data dimension through bounding the number of variables of the neural net players as a specification for the GAN problem.  Also, the paper does not provide any numerical evaluation of the shown bounds and how they change with the actual generalization error in GANs. Due to these reasons, I do not recommend this paper for publication in its current form. The paper's generalization bounds can be significantly improved by taking the optimization algorithm and the design of neural network players into account, and I suggest the authors improve their results in that way.  
summary_of_the_review: While the paper proves several generalization bounds, its main result (Theorem 1) models a neural network by only its Lipschitz constant and tries to bound the generalization error uniformly over all 1-Lipschitz functions. Therefore, the bounds grow exponentially with the data dimension and lose their power for even moderately large data vectors including all practical deep learning settings. Therefore, I think the paper's analysis does not help with understanding generalization in GANs and needs to be significantly improved by considering the design of neural net players and the optimization algorithm.
review_title: null

Meta-review: This paper proposes to analyze the generalization error of deep learning models and GANs using the Lipschitz coefficient of the model.

There was significant discrepancies in the evaluation of the paper among reviewers. While all reviewers acknowledged the interesting theoretical approach to understand generalization and the relevance to ICLR of the problem, they disagreed about the readiness level of the paper. Some concerns were expressed in terms of clarity (and the AC agrees with these), but most importantly, reviewer wKt9 pointed an important flaw in the current analysis that was not properly responded to by the reviewers (see below). In discussion, other reviewers were also concerned by this flaw, and so the AC decided to recommend a major revision of the paper taking the reviewers comments in consideration.

## Important flaw in the paper analysis (from wKt9)

Basically, Theorem 1 assumes that a loss $f(h,x)$ is $L$-Lipschitz w.r.t. input $x$ in some compact set of diameter $B$ for any $h$. The author shows that the:
$\sup_{h \in H} |E_{P} f(h,X) - E_{\hat{P}} f(h,X)|$ is upper-bounded by $L B + C \sqrt{\text{stuff}/m}$.

The concern of wKt9 is that the LHS is upper-bounded *trivially* and deterministically by the tighter $L B$ [see proof sketch next] for any distribution $P$ and $\hat{P}$ just because of the compactness of the input set and that $f$ is $L$-Lipschitz; one does not even need to include the number of samples $m$ in the analysis (thanks to the very strong assumption on $f$). The reviewer also was concerned that later (Theorem 3), the authors study ways that we can make $L$ exponentially small (which is interesting), but this has both the issues that:
1) it tells you nothing about the absolute performance of your network, as this only bounds the variation between any two distributions (indeed including the empirical and true distribution; but the fact that it also contains all distributions should indicate how loose this bound is!), and so perhaps the best empirical error one can obtained is still big
2) the current version of Theorem 3 uses a loose bound with a dependence on $m$ which was not even needed (as per the result above).

While it's true that empirically one can observe small empirical error, and thus combining this with a small Lipschitz constant would indicate good absolute performance; but the current presentation of the theory is rendered quite problematic by the above refinement, and should be corrected in a revision.

### Proof sketch:
For simplicity, I'll prove it for $P$ being a discrete distribution and $\hat{P}$ being the empirical; but I'm pretty sure you can extend it to continuous distributions as well.

Note that we have $|f(h,x) - f(h,x')| \leq L B$ for all $x, x'$ in the compact set of diameter $B$ and for all $h$.

Now $$E_{P} f(h,X) - E_{\hat{P}} f(h,X) = \sum_j \pi_j f(h, x_j') - \frac{1}{m} \sum_i f(h,x_i)$$

For each $x_i$, associate several $x_j$'s so that the total sum of their probabilities is $1/m$ (split some $\pi_j$ in multiple pieces if necessary) -- we can augment the index set for these new pieces, to obtain new probabilities $\pi_j'$ and call $I_i$ the set of associated indices to $x_i$. We have $\sum_{j \in I_i} \pi'_j = 1/m$

We thus have:
$$E_{P} f(h,X) - E_{\hat{P}} f(h,X) = \sum_i \sum_{j \in I_i} \pi'_j \left[ f(h, x'_j) - f(h,x_i) \right]$$

Thus:
$$|E_{P} f(h,X) - E_{\hat{P}} f(h,X)| \leq  \sum_i \sum_{j \in I_i} \pi'_j \left| f(h, x'_j) - f(h,x_i) \right| \leq L B$$

This is true for any $h$, so this is also true for the $\sup$, *deterministically*! QED
Decision: Reject