Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors prove that feedforward ReLU networks (eq 3) can well-approximate probability distributions which are supported on a low dimensional manifold embedded in a higher dimensional Euclidean space. They compute explicit bounds on the size of a network required to achieve approximation error on the same order as the intrinsic *statistical* error between $\hat{Q}_n$, $Q$.

For a distribution $Q$ supported on a $d$-dimensional compact Riemannian manifold $\mathcal{M}$, the authors construct an oracle map $g^*$ such that $Q = (g^*)_{\\#} \rho$, where $\rho$ is a simple distribution.

Two notable facts about this construction are that (1) $\mathcal{M}$ is required to have positive *injectivity radius* and (2) the resulting $g^*$ has a form that is amenable to approximation by a ReLU NN.

As a consequence of (2), the authors are able to invoke approximation results (eg. Shen et al 2019, Ohn and Kim 2019, Yarotsky 2017) to bound the 'size' (width, depth, weight norms) of a ReLU network $g_\theta$ that well approximates $g^*$, in that $W_1( (g_\theta)_{\\#} \rho, (g^*)\_{\\#}\rho) < \epsilon$.

Combining this with existing statistical estimation results Wasserstein-1 convergence of low dimensional distributions (Weed and Bach, 2019), the authors prove explicit bounds on the size of a neural network approximation $g_\theta \approx g^*$ up to the statistical error threshold.
strengths_and_weaknesses: Strengths

1. Theorem 1 generalizes over existing work by removing the need to assume that $\mathcal{M}$ is globally homeomorhpic to a Euclidean space. Instead, $g^*$ is constructed as a weighted average of transport maps corresponding to local charts. In my opinion, this construction is the main contribution of this work. 
2. The proof of Theorem 1 is straightforward, intuitive, and clearly explained in the paper. To the best of my knowledge it is an original contribution that is of interest to a growing body of work on the expressivity and sample complexity of GAN models. 
3. The bounds in this work require relatively mild assumptions on Q (A.C. with upper and lower bounded density; supported on a manifold with positive reach). In particular, $\mathcal{M}$ is not required to be smooth.
4. The paper is clearly written with no major typos. Proofs are correct to the best of my knowledge. 

Weaknesses

1. The assumption of positive reach/positive injectivity radius isn’t justified in the paper, and it’s not intuitive whether this assumption holds for natural data. However, this assumption seems to be standard in previous work. 
2. The network sizes prescribed by Theorem 1 are unrealistically large. For example, practical GAN models are not trained at width exponentially larger than input dimension.
questions: What (if any) is the relationship between the reach of a manifold and quantities like its curvature or smoothness? Is there any intuitive reason that natural data manifolds should have positive reach?

Minor typo: line 242 “Lipscthiz” is misspelled 
limitations: The main limitation of this work seems to be that its approximation-theoretic results have limited relevance to practical GAN models trained on natural data. As some examples,

- The required network size is unrealistically large.
- The result says nothing about *trained* GAN models. As the authors note, practical GANs approximate $W_1$ with an adversarial training scheme, and it is generally not known whether these schemes can accurately optimize $W_1$ (eg. Arora Zhang 2017).
- This work assumes an extremely strict version of manifold hypothesis for natural data distributions, which is a heuristic that only holds approximately in practice. Small Gaussian sampling noise breaks this assumption, for example.

However, these problems are ultimately out of the scope of the current work, which I believe makes a valuable contribution to the literature on manifold fitting with GAN models.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the ability of deep generative models to approximate manifold-supported distributions. In particular, this work shows that generative models can indeed approximate these distributions to high accuracy (in Wasserstein-1 sense), and then shows that the statistical rate of approximation depends on the low intrinsic dimension as opposed to the high ambient dimension. The authors consider a fairly general setting wherein the target manifold is composed of an unspecified number of charts, and the target distribution only has its density (with respect to the restriction of the Hausdorff measure to the manifold) bounded above and below by some constants. The work is purely theoretical.
strengths_and_weaknesses: ## Overall Assessment

Altogether, I find this paper to be very impressive, although I have to admit that I did not have time to go through the proofs thoroughly and may have missed some mistakes. Assuming that everything is correct, though, this paper is very timely and significant as more and more works make the manifold hypothesis an important modelling assumption when performing deep generative modelling. However, I would have appreciated some more discussion on the broader impact associated with these results, and perhaps a bit more intuition on how the results are shown. I'll elaborate below.

## Strengths 

Overall, the contributions made by this paper appear to be quite impressive. I found the two research questions to be important to ask, and the answers to these questions help explain phenomena observed by practitioners of deep generative modelling for years. The proofs themselves appear highly nontrivial. 

The writing of the paper is generally good. I found the introduction provides a solid motivation for their results and gives a good overview of the paper. The authors also do a good job of making the paper self-contained.

Originality and quality are both very strong in this paper, while both clarity and significance are reasonably strong.

## Weaknesses

The most obvious weakness of this paper is the lack of experimental insight or direct verification of the theoretical results, which takes away from some of the significance of the results. I appreciate that past work has shown that deep generative models can do a decent job of fitting image-like data that lives in high-dimensional space, and this may be considered as experimental verification of the theoretical claims. However, I think it's possible to do more here:
1. It would be interesting to see an experiment wherein the generative process is controlled, such that, for example you can see how much the Wasserstein-1 distance decreases as a function of the number of observed samples.
2. At a higher level, it would be nice to have some new practical insight emerging from the theory that could then itself be tested. I'm not sure what that would be, and unfortunately the paper provides no guidance in this direction.

The next thing I think is a bit weak is the intuition about certain choices made in the paper. For example:
1. Why is the base, easy-to-sample distribution here a uniform on $d+1$ dimensions? Both the dimensionality ($d+1$) and uniform-ness are non-standard choices. I can see later that one of the dimensions is used as an indicator and the others are used for "indexing" the manifold in some sense, but I think an opportunity was missed to provide a bit more discussion on this. The non-Gaussian base distribution should also be expanded on a bit more - do you use a uniform instead of a Gaussian because that allows approximating a distribution with density bounded below away from $0$? Or is it used because $\mathcal M$ is compact?
2. Can we get some more discussion about the assumption that requires the groundtruth density to be bounded away from $0$, or perhaps some examples of distributions which _do not_ satisfy this requirement?

Generally, I think the theoretical results can be bolstered by further probing the assumptions as problem setup, rather than just dismissing these choices as "minimal". It would be nice to discuss how these choices relate to the problems considered by practitioners. The lack of discussion here does take away from the clarity a bit.
questions: 1. Does this theory provide any new experimental insight that was not known before? How does this result help practitioners moving forward?
2. Why is the base distribution uniform?
3. How do the assumptions on the manifold and corresponding density relate to real-world problems?
limitations: This paper is short on acknowledging its own limitations, namely that there is not experimental recommendation or direct benefit to practitioners emerging from this theory. I would appreciate it if the authors mentioned something about this.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents a theory of generative neural networks when it is assumed that the real-world data studied lies on a low-dimensional manifold. This is a common hypothesis in machine learning, to try and reconcile the very high dimensionality of most datasets with the effectiveness of classical machine learning methods, such as GANs.
Assuming that the data lies on a $d$-dimensional compact manifold, the authors show that for a specific GAN architecture, trained with the Wasserstein loss, the approximation error between the actual distribution $Q$ and the GAN measure $\mu_n$ trained by ERM on $n$ samples reads
$$ W_1(Q, \mu_n) \leq C n ^{1/d}, $$
independently of the embedding distribution $D$. The curse of dimensionality thus only applies for the intrisic dimension of the data, and not the ambient one.

The proof relies on partitioning the manifold $\cal M$ into finitely many disjoint (Voronoi) cells, that can be mapped to subsets of euclidean space via diffeomorphisms. Then, those subsets are mapped onto open balls, so that the distribution $Q$ is the pushforward of the uniform measure on a finite union of disjoint open balls in $\mathbb R^d$. This can be simplified further to the uniform measure on $[0, 1]^{d+1}$, using the last coordinate to choose which ball to sample from. The results then follow from classical theorems on ERM for the Wasserstein distance.
strengths_and_weaknesses: The mathematical study of how neural networks break the curse of dimensionality is a very interesting and challenging topic, with few rigorous results. This paper manages to show a very general bound for ERM, that depends only on the structure of the underlying manifold instead of the ambient space. The assumptions on the manifold $\cal M$ and the distribution $Q$ are quite lax, much more than the usual Gaussian features assumption (which would roughly correspond to the uniform distribution on the $d$-sphere). The main drawback, result-wise, is that the architecture of the resulting GAN is a priori highly dependent on the manifold structure; it would have been insightful to see if a general GAN with this structure can fit real or synthetic data with the proclaimed accuracy.

On the presentation side, the article is quite heavy with riemannian geometry concepts, which might not be familiar to most Neurips readers. It is therefore important that those concepts be clearly introduced, and for the most part this is nicely done. Some unclear points remain, which are categorized in the following section. The proof structure is clearly marked, with helpful figures providing additional clarity to the arguments. Overall, this is an interesting and insightful paper, somewhat hindered by the wealth of geometry notions to introduce in 10 pages, but still enjoyable to read.
questions: - what happens when the support of $Q$ is not compact, but still lies on a compact manifold?
- for Lemma 2, why isn't the map
$$ x \mapsto \frac{Lx}{R(x/\lVert x \rVert)} $$
sufficient, since  $R$ is lipschitz and bounded from below ?

Geometry questions/remarks:
- Definition 1 uses the concept of *geodesic* but without specifying its second endpoint; it might be helpful to explain why this is the case (i.e. how to intrisically define geodesics)
- Is equation (5) only valid for the exponential map ? If that is not the case, why choose the exponential map instead of any atlas ?
- the notion of *reach* of a manifold is ill-defined: it lacks the requirement that $r$ is the minimal distance from $v$ to $\cal M$.


limitations: I don't really agree that any paper working on generative models can claim not having "any negative social impact"; however, the potential risks of generative models are already quite well described in the literature.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors perform a theoretical analysis of the ability of deep neural networks to map an easy-to-sample distribution to a distribution supported on a low dimensional manifold embedded in a high-dimensional space.  They have two main theorems.  The first theorem identifies that there exists a Holder-continuous transport map that transforms the easy-to-sample distribution to a distribution supported on the low dimensional manifold.  Then it identifies that, for any epsilon>0, there exists a deep neural network that transforms the easy-to-sample distribution to a distribution that is epsilon-close to the desired manifold distribution in the Wasserstein-1 distance. The second theorem considers the case where there are only n samples of the target distribution.  It shows that, for any delta>0, one can design a deep neural network for which the expected Wasserstein-1 distance is upper bounded by a constant times n^{1/(d+delta)}, where d is the manifold dimension. For these results, the manifold is assumed to be a compact Riemannian manifold with a positive reach, the target distribution's density is assumed to be bounded from above and below, and the network is assumed to alternate between affine linear layers and ReLU layers.
strengths_and_weaknesses: The theory confirms what everybody knows from 1000s of GAN papers: generative neural nets can successfully approximate distributions on manifolds. I imagine that the results are of interest to the theoretical community, but I don't have sufficient expertise to say whether the proofs are completely sound or whether the results are as novel as suggested by the authors.  

As for weaknesses, it's not obvious that the results will have an impact on the practice of machine learning. For example, do they suggest any changes to how we currently design or train GANs?

And it's not clear how sharp the bounds are.  Is it likely that they will be improved in future work?  Do they agree with experiments?


questions: As a matter of terminology, it's not clear how "the network size is exponential in the intrinsic dimension d".  To me that would mean that some characterization of size (e.g., width) grows proportional to exp(d) or perhaps exp(d/alpha).  But the results show that the width grows as D*exp(-d/alpha).  

On line 49, the authors assert that existing results claim that "the sample size is required to be epsilon^{-D}" after which they plug in particular values for epsilon and D.  But I don't think any existing results claim exactly this many samples are required.  Rather they claim sample complexity that grows proportional to epsilon^{-D}, which prevents assigning any particular number of samples.

I have trouble with the interpretation of "reach" after Definition 3 and the sphere example.  To satisfy Definition 3, why can't we take two arbitrarily close points on the sphere and then a third point on the plane bisecting them, but off the sphere? Is the reach of the sphere really its radius according to Definition 3?  
limitations: I don't see any potential for negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proves approximation and estimation theories of deep generative networks for estimating distributions on a low-dimensional manifold under the Wasserstein-1 loss.

The assumptions on the manifold are standard and weaker than related work. In particular, it does not assume that the manifold is globally homeomorphic to Euclidean space.

The assumptions on the target data distribution are different from (weaker than?) the related work. It requires that the density is both upper and lower bounded without smoothness assumptions.

The resulting theories depend on the intrinsic dimension of the manifold instead of the dimension of the data.
strengths_and_weaknesses: Strengths

1. The paper is clearly written and the related work is properly discussed.

2. The problem is important and the technique is novel.

Weakness

1. The authors may discuss the bounded assumptions on the distribution. Does previous work make a similar one? How do C and c in Assumption 2 affect the results? 
questions: A minor thing: C in Assumption 2 and that in Theorem 2 have the same meaning?
limitations: I did not see a direct negative societal impact of the work since it is purely theoretical.
review_title: null

Meta-review: metareview: This paper presents a theory of generative neural networks when it is assumed that the real-world data studied lies on a low-dimensional manifold. In particular, they prove that feedforward ReLU networks can approximate probability distributions that are supported on a low dimensional manifold embedded in a higher dimensional Euclidean space, a common assumption in machine learning.

The clear consensus among reviewers is that this constitutes a valuable (and mathematically impressive) contribution to the theoretical literature on manifold fitting with GAN models, giving a strong foundation to the well-known fact that networks such as GAN can approximate real data extremely well.  The authors have also clearly answered the question raised by the various reviewers. 
confidence: Certain
Decision: Accept