On Deep Generative Models for Approximation and Estimation of Distributions on Manifolds
Authors: Biraj Dahal
Alexander Havrilla
Minshuo Chen
Tuo Zhao
Wenjing Liao
Venue: NeurIPS 2022 Accept (2022)
Keywords: Deep generative models
distribution estimation
low-dimensional manifold

Abstract: Deep generative models have experienced great empirical successes in distribution learning. Many existing experiments have demonstrated that deep generative networks can efficiently generate high-dimensional complex data from a low-dimensional easy-to-sample distribution. However, this phenomenon can not be justified by existing theories. The widely held manifold hypothesis speculates that real-world data sets, such as natural images and signals, exhibit low-dimensional geometric structures. In this paper, we take such low-dimensional data structures into consideration by assuming that data distributions are supported on a low-dimensional manifold. We prove approximation and estimation theories of deep generative networks for estimating distributions on a low-dimensional manifold under the Wasserstein-1 loss. We show that the Wasserstein-1 loss converges to zero at a fast rate depending on the intrinsic dimension instead of the ambient data dimension. Our theory leverages the low-dimensional geometric structures in data sets and justifies the practical power of deep generative models. We require no smoothness assumptions on the data distribution which is desirable in practice.

On Deep Generative Models for Approximation and Estimation of Distributions on Manifolds
Biraj Dahal
Alex Havrilla" School of Mathematics Georgia Institute Technology ahavrilla3@gatcch edu
School of Mathematics Georgia Institute of Technology bdahal60gater wagatechc edu
Minshuo Chen
Tuo Zhao
Electrical and Computer Engineering
Industrial and Systems Engineering
Princeton University mc0750@princeton.. edu
Georgia Institute of Technology tourzhaoOgatech. edu
Wenjing Liao
School of Mathematics Georgia Institute of Technology wliao600gatech. edu
Abstract
Generative networks have experienced great empirical successes distribution learning. Many existing experiments have demonstrated that generative networks can generate high-dimensional complex data from a low-dimensional easy-to- not be justified by existing
sample distribution. However, this phenomenon theories. The widely held manifold hypothesis speculates that real-world data sets, such as natural images and signals, exhibit low-dimensional geometric structures. In this paper, we take such low-dimensional data structures into consideration by assuming that data distributions are supported prove statistical guarantees of generative networks under the Wasserstein- loss. We show that the Wasserstein- I loss converges zero at fast rate depending on the intrinsic dimension instead of the ambient data dimension. Our theory leverages the low-dimensional geometric structures in data sets and justifies the practical power of generative networks. We require no smoothness assumptions on the data distribution which desirable in practice.
low-dimensional manifold. We
1 Introduction
Deep generative models, such as generative adversarial networks (GANs) Goodfellow et al. 2014
Arjovsky al., 2017] and variational autoencoder (Kingma and Welling 2013 Mohamed and
Wierstra 2014]. utilize neural networks to generate new samples which follow the same distribution as the training data. They have been successful many applications including producing photorealistic
images, improving astronomical images, and modding video games RRed et al., 2016 Ledig et al.)
2017 Schawinski al. 2017 Brock al. 2018 Volz al. 2018 Radford al. 2015 Salimans
et al.
2016].
To estimate data distribution Q, generative models solve the following optimization problem
mingweg discrepancy((19)) Q).
(1)
'These authors contributed equally to this work.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

where p is an easy-to-sampll distribution, 9 is a class of generating functions, discrepancy is some distance function between distributions, and (go :P denotes the pushforward measure of p under go. In particular, when we obtain sample from p. we let go(=) be the generated sample, whose distribution follows (go)sp.
There are many choices of the discrepancy function in literature among which Wasserstein distance attracts much attention. The so-called Wasserstein generative models (Arjovsky et al. 2017 consider the Wasserstein-1 distance defined as
Wi(K,
sup feLip,
-x-nl/(X))-By--Jll
(2)
where n,, v are two distributions and ( consists of 1-L-ipshhizz functions on RD.. The formulation in ( is known as the Kantorovich-Rubinsee dual form of Wasserstein-1 distance and can be viewed as integral probability metric [Müller 1997].
In deep generative models, the function class G is often parameterized by deep neural network class GNN. Functions in GNN can be written in the following compositional form
go(x)) Wr. oWWi. ... (W1 2 + bi) + ... br.-1) br..
where the Ws and b;'s are weight matrices and intercepts/biases of corresponding dimensions, respectively, and is ReL.U activation applied entry-wise: a(a) max(a, 0). Here 0 (:; b denotes the set of parameters.
Solving
is prohibitive in practice, we only have access to finite collection of samples, Q. Reelacinn Q by its empirical counterpart Qn n 5x,, we end up with Xn ~
X1, X1,....
iid
gn = argmin Wi ((ge):P, Qn).
(4)
Note that is also known as training deep generative models under the Wasserstein loss in existing deep learning literature [Frogner et al. 2015 Genevay et al., 2018). It has exhibited remarkable
ability in learning complex distributions in high dimensions, even though existing theories cannot
fully explain such empirical successes. In literature, statistical theories of deep generative models
have been studied in Arora et al. [017]] Zhang al. [2017], 1, Tiang et al. [2018] Bai et al.
(2018]
Liang] [2017] 2018). Uppal et al. [2019] Chen et al. 2020), Lu and Lu [2020], Block et al. [202]
Luise et 2020). Schreuder et al. [2021]] Due the well-known curse of dimensionalle ity. the
sample complexity in Liang] [017]] Uppal et al. 2019 Chen et al. (2000) Lu and Lu (2020) grows
exponentially with respect underlying the data dimension. For example, the CIFAR-I0 dataset
consists of 32 32 RGB images. Roughly speaking, to learn this data distribution with accuracy
c, the sample size is required to be cD where D 32 32 x 3072 is the data dimension.
Setting e = 0.1 requires 100072 samples. However, GANs have been successful with 60, 000 training samples [Goodfellow et al. 2014).
A common belief to explain the aforementioned gap between theory and practice is that practical data sets exhibit low-dimensional intrinsic structures. For example, many image patches are generated from the same pattern by some transformations, such as rotation, translation, and skeleton. Such a generating mechanism induces small number of intrinsic parameters. It plausible to model these
data as samples near a low dimensional manifold [Tenenbaum et al. 2000 Roweis and Saul 2000 Peyré 2009 Coifman al. 20055.
To justify that deep generative models can adapt to low-dimensional structures in data sets, this paper focuses (from theoretical perspective) the following fundamental questions of both distribution approximation and estimation:
Q1: Can deep generative models approximate a distribution on a low-dimensional manifold by rep- resenting it as the pushforward measure of a low cow-dimensional eusy-to-sample distribution? Q2: If the representation in Q1 can be learned by deep generative models, what is the statistical rate of convergence in terms of the sample size n.?
This paper provides positive answers to these questions. We consider data distributions supported on d-dimensional compact Riemannian manifold M isometrically embedded in TR.. The easy-to-sample distribution p is uniform on (0, 1) To answer Q1, our Theorem I proves that deep generative

---

models are capable of approximating a transportation map which maps the low-dimensional uniform distribution p large class of data distributions on M. To answer Q2. our Theorem 2 shows that the Wasserstein-1 loss in distribution learning converges to zero al a fast rate depending on the intrinsic dimension d instead of the data dimension D. In particular we prove that
EWi ((ā))()))))) Q) Cn als
for all 8 >> O where C' is a constant independent of n and D.
Our proof proceeds by constructing an oracle transportation map g such that SpP Q. This construction crucially relies on cover of the manifold by geodesic balls, such that the data distribution Q is decomposed as the sum of local distributions supported on these geodesic balls. Each local distribution is then transported onto lower dimensional sets in IR from which transport theory. We then argue that the oracle g* can be efficiently approximated by deep neural networks.
apply optimal
We make minimal assumptions on the network, only requiring that go belongs neural network class (labelled GNN) with size depending on some accuracy c. Further, we make minimal assumptions on the data distribution Q, only requiring that it admits a density that is upper and lower bounded. Standard technical assumptions are made on the manifold M.
2 Preliminaries
We establish some notation and preliminaries on Riemannian geometry and optimal transport theory before presenting our proof.
Notation. For E Id, |a||| is the Euclidean norm, unless otherwise specified. Bx (0, r) is the open ball of radius in the metric space X. If unspecified, we denote B), = Bg (0, r). For function f: _Rd - Rd and A S IRd, (A) denotes the pre-image of A under f. 2 denotes the differential operator. For index a. lo denotes the oo norm of a function, vector, or matrix (considered as vector). For any positive integer N. we denote by [N] the set (1.2....,
a E we denote by Ca the class of Hölder continuous functions with Hölder
2.1 Riemannian Geometry
Let (M,g) be a d-dimensional compact Riemannian manifold isometrically embedded in R Roughly speaking manifold is set which locally Euclidean i.e. there exists function continuously mapping a small patch on M into Euclidean space. This can be formalized with open sets and charts. At each point E M we have a langeni space T&M which, for a manifold embedded in DR is the d-dimensional plane tangent to the manifold at x. We say M is Riemannian because it equipped with a smooth metric IN. Tr T.M- thought of as a local inner product. We can define the Riemannian distance dM : M x M - IR on M
(where x is a basepoint) which can be
dm(x, v) (L))) is (MM curve such that (0) z. (1) y\.
i.c. the length of the shortest path or geodesic connecting x and An isometric embedding of the d-dimensional M in T is an embedding that preserves the Riemannian metric of M, including the Riemannian distance. For more rigorous statements, see the classic reference Flaherty and do Carmo 2013).
We next define the exponential map at a point I E M going from the tangent space to the manifold.
Definition 1 (Exponential map). Let x E M. For all tangent vectors v E T,,,, there is a unique geodesic y that starts at with initial tangent vector i.e. 7(0) and (0) v. The exponential map centered at x is given by exp,, (v) = (1), for all v E T.M.
The exponential map takes vector the tangent space T.M as input. The output, exp,, (v), is the point on the manifold obtained by travelling along geodesic curve that starts at x and has initial direction (see Figure 1 for an example).
well known that for all x E M, there exists a radius 8 such that the exponential map restricted to Br, M (0, 8) is a diffcomorphism onto its image, i.c. it is smooth map with smooth inverse. As
3

---

TLM
geodlesi
exp,(e)
Figure I: Exponential map on M.
Figure 2: Manifolds with large and small reach.
the sufficiently small 5-ball in the tangent space may vary for each E M, we define the injectivity radius M as the minimum over all E M.
Definition 2 (Injectivity radius). For all M, we define the injectivity radius be inj ma( sup(ō > 0] exp= Br,M(00 = T.M - MM is diffeomorphism), Then the injectivity radius of M is defined
inj(M)= = in)(ini MJ.
For any x M,, the exponential map restricted to ball of radius inj(M) in T.M is well-defined diffeomorphism. Within the injectivity radius, the exponential map diffeomorphism between the tangent space and patch of M, with exp denoting the inverse. Controlling quantity called reach allows us to lower bound the manifold's injectivity radius.
Definition 3 (Reach). The reach of manifold M is defined as the quantity (Federer 19599
inftr 0: 3x y M, R2D such that r || vl |1 v/
inf se.
|| w
Intuitively, if the distance of a point x to M smaller than the reach, then there is unique point in M that is closest to However, if the distance between and M is larger than the reach, then there will no longer be a unique closest point to x in M.. For example, the reach of sphere is its radius. A manifold with large and small reach is illustrated in Figure The reach gives control over the injectivity radius inj(M); in particular, we know inj(M) > क (see Aamari and Levrard (009 for proof).
2.2
Optimal Transport Theory
Let μ, v be absolutely continuous measures on the sets X, Y s Rd respectively. We say a function
X - transports μ onto if feu v. In words, for all measurable sets A Y we have
v(A) fam(A) =F
where (A) is the pre-image of A under f.
Optimal transport studies the problem of transporting source measures μ on X to target measures on Y while minimizing cost с X x Y - R20 However, the results are largely restricted to transport between measures on the same dimensional Euclidean space. this paper, we will make use of the main theorem in Caffaarrlll [1992], in the form presented in Villani (2008).
Proposition 1. Let c(x, y) = I yll2 in Rd x Idd and let Qt, Ut be nonempty, connected, bounded, open subsets of R.d. Let fi, f2 be probability densities on S2 and Q2 respectively. with fi. f2 bounded from above and below. Assume further that U2 is convex. Then there exists unique optimal transport map T 22 - 22 for the associated probability measures p(dx) f1 (x) 3 da and v(dy) = f2(y) dy. and the cost Furthermore, we huve that T (*)) for some E (0, 1).
This proposition allows to produce Hölder transport maps which can be further approximated with neural networks with size depending on given accuracy.
To connect optimal transport and Riemannian manifolds, we first define the volume measure on manifold M and establish integration on M.
Definition 4 (Volume measure). Let M a compact d-dimensional Riemannian manifold. define the volume measure μ. M as the restriction of the d-dimensional Hausdorff measure Hd.

---

A definition for the restriction of the Hausdorff measure can be found in Federer 1959
We say that the distribution Q has density y if the Radon-Nikodym derivative of Q with respect to M. is q- According to Evans and Gariepy [1992], for any continuous function f M - IR supported within the image of the ball Br, (0,c) under the exponential map for inj have
( Jon (fq) exp,
/ det gf (v) dv.
(5)
Here gij = (deep, expx with ea) an orthonormal basis of T.M
3
Main Results
We will present main results in this section, including an approximation theory for large class of distributions on a Riemannian manifold (Theorem T and a statistical estimation theory of deep generative networks for distribution learning (Theorem
We make some regularity assumptions on a manifold . and assume the target data distribution Q supported on .M. The so-mle distribution is taken to be uniform on (0, 1)d+1.
Assumption 1. .M is a d-dimensional compact Riemannian manifold isometrically embedded in ambient dimension D. Via compactness, M is bounded: there exists M 0 such that |=| & M Vx E M.. Further suppose M has a positive reach T >
Assumption Q is supported on M and has density q with respect the volume measure on M. Further we assume boundedness of q i.e. there exists some constants C > O such that & & C.
To justify the representation power of feedforward ReLU networks for learning the target distribution Q, we explicitly construct a neural network generator class, such that a neural network function in this generator class can pushfoward p to good approximation of Q.
Consider the following generator class GNN
GNN(L.p. {g [91. ... 9D] Rd+1 and max width while || & k. lbb1l < x. for all i E [L].] E [D]},
PR in form (3) with at most layers
where || |l is the maximum magnitude in matrix vector. The width of neural network is the largest dimension (i.e. number of rows/columns) among the Wi's and b, ss
Theorem (Approximation Power of Deep Generative Models). Suppose M and Q satisfy Assump- tions I and respectively. The easy-to-sampl distribution p is taken to be uniform on (0, 1)d+!. < 1 (independent of D) such that for any 0 < E 1, there exists
Then there exists constant
a ga (L, p, K) with parameters
L = log (2)) p= o (DE ==
that satisfies
W Wi((g)) Q) <
Theorem ! demonstrates the representation power of deep neural networks for distributions Q on M. which answers Question Q1. For given accuracy there exists neural network which pushes the uniform distribution on (0, 1 1)d+1 forward to a good approximation Q with accuracy e. The network size is exponential in the intrinsic dimension d.
We next present statistical estimation theory answer Question Q2.
Theorem 2 (Statistical Guarantees of Deep Wasserstein Learning). Suppose M and Q satisfy Assumption / and P respectively. The easy-to-sample distribution p is taken be uniform on
(0, 15d+1 Let n be the number of samples of X; Q. Choose any ō > O. Set e n. æiz in Theorem 7 so that the network class GNN L,,,, (,K) has parameters
L =0 (log (nato)) p O Dn (Dnoddoo), M.
5

---

Then the empirical risk minimizer In given by 4 has rate
(EWi(( Q) & Cn
where C' is a constant independent of n and D.
Additionally this result can be easily extended to the noisy case. Suppose we are given n noisy i..d. samples X1, _i..... X,, of the form X; X; É,, for X; in Q and & distributed according to some noise distribution. The optimization in (4) is performed with the noisy empirical distribution Qn 1 8x,-
Then the minimizer In satisfies
(Wn(() Q) & On
Cnn*nt के. + V
where Ve= El is the variance of the noise distribution.
Comparison Related Works. To justify the practical power of generative networks, low- dimensional data structures are considered in Luise et al. 2020)] Schreuder et al. [2021], Block et al.
202T]. Chae et al. [202T] These works consider the generative models in (T). They assume that the high-dimensional data are parametrized by low-dimensional latent parameters. Such assumptions
correspond the manifold model where the manifold is globally homeomorphic Euclidean space, i.c. the manifold has single chart.
In Luise et al. 2020), the generative models assumed be continuously differentiable up to order 8. By jointly training of the generator and the latent distributions, they proved that the Sinkhorn divergence between the generated distribution and data distribution converges, depending on data intrinsic dimension. Chae et al. [2021] and Schreuder et al. [2021] assume the special case where the manifold has single chart. More recently, [Bock et 2202 proposed estimate the intrinsic dimension of data using the Hölder IPM between some empirical distributions of data. This theory is based on the statistical convergence of the empirical distribution the data distribution. As an application to GANs, [Block et al.) [021] Theorem 23] gives the statistical error while the approximation error is not studied, In these works, the single chart assumption is very strong while general manifold can have multiple charts.
Recently, Yang et al. [2022], Huang al. [022 showed that GANs approximate any data distribution (in any dimension) by transforming an absolutely continuous 1D distribution. The analysis in Yang al. [2022), Huang et al. (2022) can be applied the general manifold model. Their approach requires the GAN to memorize the empirical data distribution using ReLU networks. Thus is not clear how the designed generator capable of generating new samples different from the training data.
In contrast, explicitly construct an oracle transport map which transforms the fow-dimensional -ommpll distribution to the data distribution. Our work provides insights about how distribu- tions manifold can be approximated by neural network pushforward of low-dimensional sasmple distribution without exactly memorizing the data. In comparison, the single-chart assumption in earlier works assumes that oracle transport naturally exists. Our work is novel in the construction of the oracle transport for a general manifold with multiple charts, and the approximation theory by deep neural networks.
4 Proof of Main Results
4.1 Proof of Approximation Theory in Theorem
To prove Theorem I
we explicitly construct an oracle transport g* pushing p onto Q, i.c. 9 p Q.
Further this oracle will be piecewise a-Hölder continuous for some a (0, 1). Lemma 1. Suppose M and Q satisfy Assumption |
and respecciey The easy-lo-sample distribu- tion is taken to be uniform on (0, 1)d+1, Then there exists a function g" (0, 1) - M such that 9 p where
(*()) Ej Lr, 1. (2,))21)) (I2.d+1)
(6)
for some a-Hölder (0 < a 1) continuous functions o .......9. 93 and some constants -To <
T1 <J =1

---

Proof. We construct a transport map 9" (0, (0,1)a+1 - MM that can be approximated by neural networks. First, we decompose the manifold into overlapping geodesic balls. Next, we pull these local distributions on these balls back to tangent space, which produces d-dimensional tangent distributions. Then, we apply optimal theory on these tangent distributions to produce maps between the source distributions on (0. 1 to the appropriate local (geodesic ball) distributions on the manifold. Finally, we glue together these local maps with indicators functions and a uniform random sample from (0, 1). We proceed with the first step of decomposing the manifold.
Step 1: Overlapping ball decomposition. Recall that M is a compact manifold with reach > Then the injectivity radius of M is greater than or equal to тт (Aamari et al. (2019]). Set 22 For each e E M. define an open set Ue_ ( ()) S M. Since the collection {Ue : E M] forms an open cover of M (in P). by the compactness of M we can extract a finite subcover which we denote as (Un For convenience, we will write Uj Uey-
Step 2: Defining local lower-dimensional distributions. On each Uj. we define a local distribution Qj with density qj
((x)) QUU,)
43 (2)
Ug (T).
Set (2) Σý=1 Lu, (2) (x) as the number of balls U, containing x. Note 1 K(x) & J for all E M. Now define the distribution Qj with density 73 given by
Ro R zy (z)
(x(x)
Soy (t)
Write Kj Seg k(a) (z))) as the normalizing constant. Define gb( = (
exPo, expo))(o) /dtt (v) where D is the Riemannian at cj. This quantity can be thought of as the Jacobian of the exponential map, denoted by Meexp. (v) in the following step. Then &g is a density on Ug expe, (Ug), which is a ball of radius ar 2 since
1= Jug 7 (z))) J/, Vdet getl (x)7, (v))du S( (v)do
Let Q, be the distribution in Edd with density qz. By construction, we can write
Q (expey):.j-
Step 3: Constructing the local transport. We have that expe, is bi-Lipschitz on U, and hence its 1 Jacobian is upper bounded. Since |Jexp,, (n)l = 1J Mapp, (x)) we know that |eexp.y! lower bounded.
Since dj is lower bounded (away from 0), this means Ø is also lower bounded. Now the distribution 9J supported on U, B(O, 3)) fulfills the requirements for our optimal transport result: (1) Its density p; is lower and upper bounded; (2) The support B(0, 7 is convex. Taking our cost to be c(z, y) = 1 x y/ 2 (i.c. squared Euclidean distance), via Proposition we can find an optimal transport map T, such that
(T))
(8)
where Pa is uniformly distributed on (0, 1)d. Furthermore, T3 e Cai for some aj (0, Then we can construct a local transport onto U, via
5
expe, oT;
(9)
which pushes Pa forward to Q,- Since 5 is a composition of a Lipschitz map with an o, Hölder continuous maps, it is hence oj Hölder continuous.
Step 4: Assembling the global transport. It remains to patch together the local distributions Q, to form Q. Define 7 KU,(U,). Notice
7

---

Mc MCR
R
(0, 1)ad
R
T3
exP
65
Pa
i₂ (Tş)aPa
Figure 3: Local transport 9 in mapping on (0, 1)d to local distribution Q3 supported on Uy.
k(x) (x)
Σ (x) 1-1
Σ KgQ(U,)
Σ Q(U)) Q(U,)
Kj
5-1
Σ
1
K(x) (o) ((())
l0, (x) [0,(2)
g(x).
K(x)
Hence it must be that 2 fl 1. Set a minja(J] aj. We can now define the oracle g*. Let IE (0, 1)d+1. Write
g (x(x)= = Ei [ (1)_) (I24+1),
(10)
where 21 is the first coordinate and 22:d+1 are the remaining coordinates with IT Ex=1 j- ~ p. Then g( ~ Q. We see this as follows. For A S M we can compute
17. Let
PZ)* E AA Σ P(m Z1 Pgg
(Z (2.a+1)
E Un) Σ (AAnn) Uz) 5-1
Σ Tii J ( = S, Σ (z)()) q())dH- Q(A) j=1
which completes the proof.
We have found oracle g which piecewise Hölder continuous such that 9 Q. We can design neural network ge to approximate this oracle g* Now in order minimize Wi Wi((g)): Q) Wi ((g(g)) g p). show it suffices to have ge approximate g" in L'
Lemma 2. Let μ be absolutely continuous probability distribution f.g: 7 - R be transport maps. Then
Z S Rd. and let
Wi(Jan,9e)) CCJ gll
for some C O.
The proof can be found in Section B.1 in the appendix. We now prove Theorem |
Proof of Theorem 1 By Lemma
there exists
transformation g*(r)
E/=1 (15-11 (1a )9f (f2.411) such that Tpp Q. By Lemma 2 suffices approxi- mate g with a neural network go e INN(L. p, k) in L norm, with a given accuracy > 0. Let (g*)()) denote the ith component of the vector valued function g*h Then it suffices to approximate
(x)
1 (x)) (x2.++1
8

---

for each <i< D, where (o,)(* denotes the ith component of the function 9j. We construct the approximation (9*)()) by the function
(g0) (x)
Σ xz (1))))))))))))))))) (5,7) ((2441))
(1I)
where x is a ReLU network approximation to the multiplication operation with 52 accuracy, i
(m)-1.)7)) is ReLU network approximation to the indicator function with 61 accuracy. and (0),)) )
is a ReLU network approximation to (o² (1) with 63 accuracy. We construct these using the approxi-
mation theory outlined in Appendix
First, we obtain [(= (myy).my) via an application of Lemma Next, we obtain x from an application
of Lemma
Finally, we discuss 97 Let j E [J] To approximate the Hölder function g we use the following Lemma 3 that is proved Appendix A Similar approximation results can be found in Shen et al. 2022] and Ohn and Kim 2019 well. In Lemma our approximation error is in L'
norm and all weight parameters are upper bounded by a constant. In comparison, the error Ohn
and Kim
2019 is in L norm and the weight parameter increases decreases.
Lemma 3. Fix M > 2. Suppose I C 1) (0, with [/ < M. Let Then there exists a function implementable by a ReLU network such that
If
<.
The ReLU network has depth at most ei log (t). width at most 02 #, and weights bounded by M (where e1 and 02 are constants independent of e..
We can apply Lemma 3 to (g))()) for all 1 & j J and i D, since they are all elements of (0, (0, 1)d and elements of C* (0, 1)dh can be extended to CO 17". Thus there exists neural network ( (+) E GNN(L, p, x) with parameters given as above such that
(9 (0)) L 83.
The goal is now to show the L distance between ga (as defined in and g* is small. We have llg* go 1. < DJ(M 82 + 6z)
where 8 is the neural network approximation error of indicator functions in L', 82 is the approxima- tion error of multiplication, and 83 is the approximation eтror of our a-Hölder local transport maps. We carefully argue in Appendix A.4 that each of these components appropriately sized network. To complete the proof we conclude go can be exactly represented by neural network in GNN(L, p, s!) with parameters
be approximated with the
L - log ) p - ODO k M.
4.2
Proof Statistical Estimation Theory in Theorem 2
The proof of Theorem 2 is facilitated by the common bias-variance inequality, presented here lemma.
Lemma 4, Under the same assumptions of Theorem
we have
EWi(( Q) inf
Wi Q) 2EW1 Q)
(12)
96E
where Qn is the empirical distribution.

---

Proof. We compute recalling the definition of 9n. as the empirical risk minimizer.
EWi((On)tp, Q) < E )P, Qn) + LEW Q)
E inf W Wi((ge);/ Qn)) JEW, (Q Q)
goE
E inf W1((go) Q) 2EW (Q Q)
geElsN
where we recall Wi (()n)sp Qn) inn geE Wi((ge)sP, Qn) from
The bias term can controlled via Theorem To control convergence of the empirical distribution On to Q we leverage the existing theory (Weed and Bach 2019] to obtain the following lemma. Lemma 5. Under the same assumptions Theorem 2 for all 8 > 0, 3Cs > 0 such that
E [W (2)) & Can at.
(13)
This follows directly from Theorem from [Weed and Bach 2019). We attach full proof in Section B.2 of the appendix. Finally, we prove our statistical estimation result in Theorem
Proof of Theorem 2 Choose > 0. Recall from Lemma 4 we have
Wi((On)sP Q) E inf Wi((ge):P, Q) + 2EW1 Q) gaEgsN
The first term the approximation error which can be controlled within arbitrarily small accuracy Theorem shows the existence of a neural network function with O (log (t) layers and
O(De 100-4/:0 4/cx log =)) neurons such that Wi Wi((go)ae (0; Q) & e for any > O. choose e = n aiv to optimally balance the approximation error and the statistical error. The second term is the statistical
error for which we recall from Lemma that E [Wi Q)
& Can хभअ for some constant Cg.
Thus have
EWi((G))pp Q) En + 2Cpn +े.
On कमअ
by setting C = 1 2Cg. This concludes the proof.
We remark the above proof proceeds similarly in the noisy case, which is presented in Section B.3 of the appendix.
Conclusion
We have established approximation and statistical estimation theories of deep generative models for estimating distributions on low-dimensional manifold. The statistical convergence rate in this paper depends on the intrinsic dimension of data. In light of the manifold hypothesis, which suggests many natural datasets lie on low dimensional manifolds, our theory rigorously explains why deep generative models defy existing theoretical sample complexity estimates and the curse of dimensionality. In fact, deep generative models are able to learn low-dimensional geometric structures of data, and allow for highly efficient sample complexity independent of the ambient dimension. Mcanwhile the size the required network scales exponentially with the intrinsic dimension.
Our theory imposes very little assumption on the target density Q, requiring only that it admit density with respect to the volume measure and that is upper and lower bounded. In particular make smoothness assumptions on q. This is practical, datasets to exhibit high degrees of smoothness.
do not expect existing natural
In this work, we assume access to computation of the W, distance. However during GAN training a discriminator is trained for this purpose. It would of interest for future work investigate the low-dimensional role of such discriminator networks which approximate the W, distance in practice.
10

---

References
Eddie Aamari and Clément Levrard. Nonasymptotic rates for manifold, tangent space and curvature estimation. The Annals of Statistics, 2019.
Eddie Aamari, Jisu Kim, Frédéric Chazal, Bertrand Michel, Alessandro Rinaldo, Larry Wasserman, et al. Estimating the reach of a manifold. Electronic Journal of Statistics, 13(1):1359-139, 2019.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference machine learning, pages 214-223. PMLR, 2017.
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (gans), arXiv preprint arXiv: 3XXiv:7033005755 2017.
Yu Bai, Tengyu Ma, and Andrej Risteski. Approximability of discriminators implies diversity in gans. arXiv preprint arXiv: 10586, 2018.
Adam Block, Zeyu Jia, Yury Polyanskiy, and Alexander Rakhlin. Intrinsic dimension estimation. arXiv preprint arXiv:2 2021.
Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale gan training for high fidelity natural image synthesis. arXiv preprint arXiv: /809. 1096, 2018.
Luis Caffarelli. The regularity of mappings with a convex potential. Journal of the American Mathematical Society, 5(1):99-104, 1992.
Minwoo Chae, Dongha Kim, Yongdai Kim, and Lizhen Lin. likelihood approach non- parametric estimation of a singular distribution using deep generative models. arXiv preprint 0rXiv:2105.04046. 2021.
Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Nonparametric regression on low- dimensional manifolds using deep relu networks. arXiv: Learning, 2019.
Minshuo Chen, Wenjing Liao, Hongyuan Zha, and Tuo Zhao. Statistical guarantees of generative adversarial networks for distribution estimation. CoRR, abs/2002.03933 2020. URL https
//arxiv. org/
03938
Ronald R Coifman, Stephane Lafon, Ann B Lee, Mauro Maggioni, Boaz Nadler, Frederick Warner, and Steven W Zucker. Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps. Proceedings of the national academy of sciences, 102(21):746-7431, 2005.
I. C. Evans and R. F. Gariepy. Measure theory and fine properties of functions. 1992.
Herbert Federer. Curvature measures. Transactions of the AMS, pages 418-494, 1959.
F. Flaherty and M.P. do Carmo. Riemannian Geometry. Mathematics: Theory & Applications. Birkhäuser Boston, 2013. ISBN 9780817634902. URL https::: google com/books?
1ddcc91XCWEEEUCC
Charlic Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya, and Tomaso A Poggio. Learning with wasserstein loss. Advances in neural information processing systems, 28, 2015.
Aude Genevay, Gabriel Peyré, and Marco Cuturi. Learning generative models with sinkhorn diver- gences. In International Conference on Artificial Intelligence and Statistics, pages 1608-1617. PMLR, 2018
Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. 2014.
Jian Huang, Yuling Jiao, Zhen Li, Shiao Liu, Yang Wang, and Yunfei Yang. An enror analysis of generative adversarial networks for learning distributions. Journal of Machine Learning Research, 23(116):1-44 2022.
11

---

Haoming Jiang, Zhehui Chen, Minshuo Chen, Feng Liu, Dingding Wang, and Tuo Zhao. On computation and generalization of gans with spectrum control. arXiv preprint arX1v:1812.10912. 2018.
DP Kingma and M Welling. Auto-encoding variational bayes. ielr 2014 2014. arXiv preprint 131.v:1312.61 14, 2013.
Christian Ledig, Lucas Theis, Ferenc Huszár, Jose Caballero, Andrew Cunningham, Alejandro Acosta, Andrew Aitken, Alykhan Tejani, Johannes Totz, Zehan Wang, et al. Photo-realistic single image super-resolution using generative adversarial network. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4681 1681-4690, 2017.
Tengyuan Liang. How well can generative adversarial networks learn densities: A nonparametric view. arXiv preprint arXiv: 1wtp:::2222.24400 2017.
Tengyuan Liang- On how well generative adversarial networks learn densities: Nonparametric and parametric results. arXiv preprint arXiv: 18110317 2018.
Yulong Lu and Jianfeng Lu. A universal approximation theorem of deep neural networks for expressing probability distributions. Advances in neural information processing systems, 33: 3094-3105, 2020.
Giulia Luise, Massimiliano Pontil, and Carlo Ciliberto. Generalization properties of optimal transport gans with latent distribution learning. arXiv preprint 20t.::0007.16444,, 2020.
Shakir Mohamed and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. 2014.
Alfred Müller. Integral probability metries and their generating classes of functions. Advances in Applied Probability, 29:429-443. 1997. ISSN 00018678. URL http:://ww. jstor org/
stable/1428011 1428011
Ilsang Ohn and Yongdai Kim. Smooth function approximation by deep neural networks with general activation functions. Entropy, 21(7):627, 2019.
Gabriel Peyré. Manifold models for signals and images. Computer vision and image understanding. 113(2):249-261)) 2009.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint 1rXiv:1511.0644 2015.
Scott Reed, Zeynep Akata, Xinchen Yan, Lajanugen Logeswaran, Bernt Schiele, and Honglak Lee. Generative adversarial text to image synthesis. arXiv preprint arXiv:1605.05396 2016.
Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 290(5500):2323-
2000.
Tim Salimans, Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. In Advances in neural information processing systems, pages 2234-222222 2242, 2016.
Kevin Schawinski, Ce Zhang, Hantian Zhang, Lucas Fowler, and Gokula Krishnan Santhanam. Generative adversarial networks recover features in astrophysical images of galaxies beyond the deconvolution limit. Monthly Notices of the Royal Astronomical Society: Letters, 467(1): L1100-L114, 2017.
Nicolas Schreuder, Victor-Emmanuel Brunel, and Amak Dalalyan. Statistical guarantees for gen- erative models without domination. Algorithmic Learning Theory, pages 1051-1071. PMLR, 2021.
Zuowei Shen, Haizhao Yang, and Shijun Zhang. Optimal approximation rate of relu networks in terms of width and depth. Journal de Mathématiques Pures et Appliquées, 157:101-135, 2022.
Joshua Tenenbaum, Vin De Silva, and John C Langford. global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):33199233200 2000.
12

---

Ananya Uppal, Shashank Singh, and Barnaás Póczos. Nonparametric density estimation & conver genee of gans under besov ipm losses. arXiv preprint arXiv:1902.0351,, 2019.
Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
Vanessa Volz, Jacob Schrum, Jialin Liu, Simon M Lucas, Adam Smith, and Sebastian Risi. Evolving mario levels the latent space of deep convolutional generative adversarial network. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 221-228, 2018.
Jonathan Weed and Francis R. Bach. Sharp asymptotic and inite-sample rates of convergence of empirical measures in wasserstein distance. Bernoulli, 2019.
Yunfei Yang, Zhen Li, and Yang Wang. On the capacity of deep generative networks for approximating distributions. Neural Networks, 145:144-154, 2022.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural networks the official journal of the International Neural Network Society, 94:103-11 114, 2017.
Pengchuan Zhang, Qiang Liu, Dengyong Zhou, Tao Xu, and Xiaodong He. On the discrimination- generalization tradeoff in gans. arXiv preprint x 2017.
13

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], , or [N/A] - You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See our conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [No] We dont foresee any negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] They are attached in the appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you's 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "mzfD0GyXqRq", "reviewer": "Reviewer_ufvV", "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.\n\nThe 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.\n\nThe 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.\n\nThe resulting theories depend on the intrinsic dimension of the manifold instead of the dimension of the data.", "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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. The paper is clearly written and the related work is properly discussed.\n\n2. The problem is important and the technique is novel.\n\nWeakness\n\n1. 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? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hCL8Kp2o_Gk", "reviewer": "Reviewer_Rb3G", "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$.\n\nFor 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.\n\nTwo 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.\n\nAs 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$.\n\nCombining 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.", "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?\n\nMinor 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,\n\n- The required network size is unrealistically large.\n- 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).\n- 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.\n\nHowever, 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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. 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. \n2. 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. \n3. 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.\n4. The paper is clearly written with no major typos. Proofs are correct to the best of my knowledge. \n\nWeaknesses\n\n1. 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. \n2. 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SCwLoGRMgBL", "reviewer": "Reviewer_Q3cg", "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.", "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).  \n\nOn 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.\n\nI 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.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.  \n\nAs 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?\n\nAnd 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?\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PytkezdPhfF", "reviewer": "Reviewer_P4YA", "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.", "questions": "1. Does this theory provide any new experimental insight that was not known before? How does this result help practitioners moving forward?\n2. Why is the base distribution uniform?\n3. 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.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Overall Assessment\n\nAltogether, 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.\n\n## Strengths \n\nOverall, 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. \n\nThe 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.\n\nOriginality and quality are both very strong in this paper, while both clarity and significance are reasonably strong.\n\n## Weaknesses\n\nThe 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:\n1. 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.\n2. 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.\n\nThe next thing I think is a bit weak is the intuition about certain choices made in the paper. For example:\n1. 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?\n2. 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?\n\nGenerally, 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HMOtT4okiOa", "reviewer": "Reviewer_CSiC", "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.\nAssuming 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\n$$ W_1(Q, \\mu_n) \\leq C n ^{1/d}, $$\nindependently of the embedding distribution $D$. The curse of dimensionality thus only applies for the intrisic dimension of the data, and not the ambient one.\n\nThe 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.", "questions": "- what happens when the support of $Q$ is not compact, but still lies on a compact manifold?\n- for Lemma 2, why isn't the map\n$$ x \\mapsto \\frac{Lx}{R(x/\\lVert x \\rVert)} $$\nsufficient, since  $R$ is lipschitz and bounded from below ?\n\nGeometry questions/remarks:\n- 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)\n- Is equation (5) only valid for the exponential map ? If that is not the case, why choose the exponential map instead of any atlas ?\n- 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$.\n\n", "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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nOn 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept