A Statistical Analysis of Wasserstein Autoencoders for Intrinsically Low-dimensional Data
Authors: Saptarshi Chakraborty
Peter Bartlett
Venue: ICLR 2024 poster (2024)
Keywords: Wasserstein Autoencoders
Statistical Analysis
Error rates
Intrinsic Dimension
Primary area: learning theory
TL;DR: We show that WAE's can achieve an excess risk that, as a function of the number of samples, depends only on the intrinsic data dimensions rather than the high dimensions of the ambient feature-space.

Abstract: Variational Autoencoders (VAEs) have gained significant popularity among researchers as a powerful tool for understanding unknown distributions based on limited samples. This popularity stems partly from their impressive performance and partly from their ability to provide meaningful feature representations in the latent space. Wasserstein Autoencoders (WAEs), a variant of VAEs, aim to not only improve model efficiency but also interpretability. However, there has been limited focus on analyzing their statistical guarantees. The matter is further complicated by the fact that the data distributions to which WAEs are applied - such as natural images - are often presumed to possess an underlying low-dimensional structure within a high-dimensional feature space, which current theory does not adequately account for, rendering known bounds inefficient. To bridge the gap between the theory and practice of WAEs, in this paper, we show that WAEs can learn the data distributions when the network architectures are properly chosen. We show that the convergence rates of the expected excess risk in the number of samples for WAEs are independent of the high feature dimension, instead relying only on the intrinsic dimension of the data distribution.

Published as a conference paper at ICLR 2024
A STATISTICAL ANALYSIS OF WASSERSTEIN AUTOEN-
CODERS FOR INTRINSICALLY LOW-DIMENSIONAL DATA
Saptarshi Chakraborty UC Berkeley saptaarshic@berkeleeyycco
Peter L. Bartlett
Google DeepMind & UC Berkeley
petexiberkeley.cm edu
ABSTRACT
Variational Autoencoders (VAEs) have gained significant popularity among re- searchers powerful tool for understanding unknown distributions based on limited samples. This popularity stems partly from their impressive performance and partly from their ability provide meaningful feature representations in the latent space. Wasserstein Autoencoders (WAEs). a variant of VAEs, aim to not only improve model efficiency but also interpretability. However, there has been limited focus on analyzing their statistical guarantees. The matter is further com- plicated by the fact that the data distributions which WAEs are applied such as natural images- are often presumed to possess an underlying low-dimensional structure within a high-dimensional feature space, which current theory does not adequately account for, rendering known bounds inefficient. To bridge the gap between the theory and practice WAEs, in this paper, we show that WAEs can learn the data distributions when the network architectures are properly chosen. We show that the convergence rates of the expected excess risk the number of samples for WAEs are independent of the high feature dimension, instead relying only on the intrinsic dimension of the data distribution.
INTRODUCTION
The problem of understanding and possibly simulating samples from an unknown distribution only through some independent realization of the same is a key question for the machine learning com- munity. Parallelly with the appearance of Generative Adversarial Networks (GANs) (Goodfellow) jet al. 2014)) Variational Autoencoders (Kingma & Welling 2014) have also gained much attention not only due to their useful feature representation properties in the latent space but also for data gen- eration capabilities.
important to note that in GANs, the generator network learns to create new samples that are similar the training data by fooling the discriminator network. However, GANs and their popular variants do not directly provide a way to manipulate the generated data or explore the latent space of the generator. On the other hand, VAE learns latent space representation of the input data and allows for interpolation between the representations of different samples. Several variants of VAEs have been proposed improve their generative performance. One popular variant is the conditional VAE (CVAE) (Sohn et al. 2015), which adds conditioning variable to the gen- erative model and has shown remarkable empirical success. Other variants include Info VAE (Zhao) et al. 2017), B- VAE (Higgins et al., 2017), and VQ-VAE (Van Den Oord et al. 2017). etc.. which address issues such as disentanglement, interpretability, scalability, etc. Recent works have shown the effectiveness of VAFs and their variants in variety of applications, including image (Gregor jet al., 2015) and text generation (Yang al. 2017), speech synthesis (Tachibana al. 2018). and drug discovery
et al. 2018)) 8). A notable example is the DALL-E model (Ramesh ctt al. 202I), which uses a VAE to generate images from textual descriptions.
However, despite their effectiveness in unsupervised representation learning, VAEs have been heav- ily criticized for their poor performance in approximating multi-modal distributions. Influenced by the superior performance of GANs, researchers have attempted to leverage this advantage of adver- sarial losses by incorporating them into VAE objective (Makhzani et al.] 2016); MMscheder et al.] 2017). Wasserstein Autoencoder (WAEs) (Tolstikhin al. a (018)) tackles the problem from opti-

---

Published as a conference paper at ICLR 2024
mal transport viewpoint. Incorporating such GAN-like architecture, not only preserves the latent space representation that is unavailable in GANs but also enhances data generation capabilities. Both VAEs and WAEs attempt to minimize the sum of reconstruction cost and regularizer that penal- izes the difference between the distribution induced by the encoder and the prior distribution on the latent space. While VABs force the encoder match the prior distribution for each input example, which can lead to overlapping latent codes and reconstruction issues, WAEs force the continuous mixture of the encoder distribution over all input examples to match the prior distribution, allowing different examples to have more distant latent codes and better reconstruction results. Furthermore, the use of the Wasserstein distance allows WAEs to incorporate domain specific constraints into the learning process. For example, if the data is known to have a certain structure or topology, this infor- mation can be used to guide the learning process and improve the quality of generated samples. This results in more robust model that can handle wider range of distributions, including multimodal and heavy-tailed distributions.
While VAE and its variants have demonstrated empirical success, little attention has been given to analyzing their statistical properties. Recent developments from an optimization viewpoint include Rolinek et al. (2019), who showed VAEs pursue Principal Component Analysis (PCA) embedding under certain situations, and Koehler et al. (2022), who analyzed the implicit bias of VAEs under linear activation with two layers. For explaining generalization, [Tang & Yangl (222)) proposed framework for analyzing excess risk for vanilla VAFs through M-estimation. When having access to n i..d. samples from the target distribution, Chakrabarty & Das (202I) derived a bound based on the
(VC) dimension, providing a guarantee of O 1/2) -coovverreeeeee with non-zero margin of error, even under model specification. However, their analysis is limited to a parametric regime under restricted assumptions and only considers theoretical variant of WAEs, known as f WAWS (Husain et al. 2019). which is typically not implemented in practice.
Despite recent advancements in the understanding of VAEs and their variants, existing analyses fail to account for the fundamental goal of these models, i.c. to understand the data generation mechanism where one can expect the data to have an intrinsically low-dimensional structure. For instance, a key application of WAEs is to understand natural image generation mechanisms and it is believed that natural images have low-dimensional structure, despite their high -igesiimessional pixel-wise representation (Pope et al. (020). Furthermore, the current state-of of-the-art views the problem only through a classical learning theory approach to derive On 11/2) or faster rates (under additional assumptions) ignoring the model misspecification error. Thus, such rates do not align with the well-known rates for classical pon-maraettiic density estimation approaches (Kim et al.) 2019). Additionally, these approaches only consider the scenario where the network architecture fixed, but in practice, larger models are often employed for big datasets.
In this paper, we aim to address the aforementioned shorteomings in the current literature and bridge the gap between the theory and practice of WAEs. Our contributions include:
We propose a framework to provide an error analysis of Wasserstein Autoencoders (WAEs) when the data lies in a low-dimensional structure in the high-dimensional representative feature space.
Informally, our results indicate that if one has independent and identically distributed (ii.d.) samples from the target distribution, then under the assumption of Lipschitz-smoothness of the true model, if the corresponding networks properly chosen, the error rate for the problem scales as x
where, dy. is the upper Minkowski dimension of the support of the target distribution.
The networks can be chosen as having (nn') many weights for the encoder and On")) for the generator, where, Tes To S 1 and only depend on d, and é (dimension of the latent space), respectively. Furthermore, the values of Je and 7 decrease as the true model becomes smoother.
We show that one can ensure encoding and decoding guarantees, i.e. the encoded distribution is close enough to the target latent distribution, and the generator maps back the encoded points close to the original points. Under additional regularity assumptions, we show that the approximating fush-forward measure, induced by the generator, is close to the target distribution, in the Wasser- stein sense, almost surely.
2

---

Published as a conference paper at ICLR 2024
1
+ 1
0.025
100
Deceommrten Eree
250
230
0.04
0.015
200
0.000
0.02
150
2050
1200
5000
8200
10350
2032
6009
6300
12000
2030
4035
0035
8300
32000
2020
1000
6200
3200
1030o
(a) FID scores for GAN- WAF
(b) Reconstruction emror (c) FID scores for MMD for GAN-WAE
(d) Reconstruction emror for MMD-WAF
WAF
Figure I: Average generalization error (in terms of FID scores) and reconstruction test errors for different values of for GAN and MMD variants of WAE. The error bars denote the standard deviation out 10 replications.
2 A PROOF OF CONCEPT
Before we theoretically explore the problem, we discuss experiment to demonstrate that the error rates for WAEs depend primarily only on the intrinsic dimension of the data. Since it is difficult to assess the intrinsic dimensionality of natural images, we follow the prescription of Pope et al. (2020) to generate low-dimensional synthetic images. We use a pre-trained Bi-directional GAN (Donahue) eet 2017) with 128 latent entries and outputs of size 128 x 128 3, trained on the ImageNet dataset (Deng et al., 2009). Using the decoder of this pre-trained BiGAN, we generate 11, 000 images, from the class, sooa-bbbblle
where fix most entries of the latent vectors to zero leaving only d_int free entries. We take d_int to be 2 and 16, respectively. We reduce the image sizes to 28 x 28 for computational ease. We train a WAE model with the standard architecture as proposed by TTossikkhin itt al. (2018) with the number of training samples varying in {2000, 4000,... 100000 and keep the last 1000 images for testing. For the latent distribution, we use the standard Gaussian distribution on the latent space I and use the Adam optimizer (Kingma & Ba 2015) with learning rate of 0.0001. We also take = 10 for the penalty on the dissimilarity in objective (4). After training for 10 epochs, we generate 1000 sample images from the distribution G. (see Section 3 for notations) and compute the Frechet Inception Distance (FID) (Heusel et al.) (017)) to assess the quality of the generated samples with respect to the target distribution. We also compute the reconstruction error for these test images. We repeat the experiment 10 times and report the average. The experimental results for both variants of WAE, i.e. the GAN and MMD are shown in Fig. [ It clear from Fig. I that the error rates for d_int 2 lower than for the case diint 16. The codes for this experimental study can be found at httpt:t///// htt.a///////////ctttcccco//////p
com
//AE
3 BACKGROUND
3.1 NOTATIONS AND SOME PRELIMINARY CONCEPTS
This section introduces preliminary notation and concepts for theoretical analyses.
Notation We use notations V y max(xx2) y and A yy: min(x, v). Tip denotes the push- forward of measure i by the map T. For function f - R. and probability measure y on S, let I == (Is (d)) 1/p Similarly, [[ == supze.4 [f()). For any function class F. and distributions P and Q, -
fdQ) denotes the Integral Probability Metric (IPM) w.r.t. F. We say An S Bn (also written as A,, OBB,)) if there exists >>O O, independent of n, such that A, < CBB, Similarly, we use the notation, A, 3 B, (also written as A,, = O(B))) if A,, I CB, log (en), for some C > 0. We say A, x B,, if A,, S B, and Bn $ An For function f dd Rd we write, ||f [| = sup 1
sup ff
Definition 1 (Neural networks). Let L E N and (Nibee C N. Then L-layer neural network f: R: No is defined as,
f(x) = A 10-00111-1111---.000
A1
(1)
Here, A, = Wiy + b, with W; E R N:N;; 1 and b, N: 1, with No d. oj is applied component-wist Here, (Wihsiss are known as weights, and (bihsiss. are known as biases. (ai)isigt-1 known as the activation functions. Without loss of generality, can take (0)
3

---

Published as a conference paper at ICLR 2024
0, AE E [L- the network; (Number of weights) The number of weights of the network f is denoted as W(f).
-5-1,, 1].
We define the following quantities: (Depth) L(f) L is known the depth of
(ooo))s 1,(L, W, R) {f of the form I L(f) S L, W(f) = W, sup ll - R}. æER
If (x)x) = x 0., for all j = 1..... 1, we denote A (o (o.hsssss-- (L, W. W.RR R) as (L, W. R). We often omit R in cases where is clear that R is bounded by constant.
Definition 2 (Hölder functions). Let f S + R be a function, where S S Rd. For a multi-index ا/- (.,, sa), let, 0-1 Ox."...oz ...
where, [8| Ei St. We say that a function f: -
is 3-Hölder (for 3 > 0) if
f0x)(x)= - f(vil
Ilflace =
Σ
11 +
Σ sup
1 - 1113-10 00.
<00
4:1a| 1 "wy
If f R4 Rd2, then we define II
|1f
For notational simplicity, let, (S), S2, C) = (s S + S2 11l1laxe S C}. Here, both S and S2 are both subsets of real vector spaces.
Definition 3 (Maximum Mean Discrepancy (MMD)). Let Hy be the Reproducible Kernel Hilbert Space (RKHS) corresponding to the reproducing kernel K(., defined on Rd. Let the correspond- ing norm in this RKHS be || || The Maximum Mean Discrepancy between two distributions P and Q is defined as: MMD (P, Q) = supfillfl,, S1 ( fdP fdQ).
3.2 WASSERSTEIN AUTOENCODERS
Let j be a distribution the data-space X [0, 1]d and 2 [0, 1] be the latent space. In Wasserstein Autoencoders (Tolstikhin et al. (2118). one tries to learn generator map, G' Z - X and an encoder map : X + by minimizing the following objective,
V(4 G, F) f c(x, Go F(x))du(()) Adiss Eyp,
(2)
Here, À > 0 is a hyper-parameter, often tuned based on the data. The first term in 2 aims to mini- mize reconstruction error, i.e. the decoded value of the encoding should approximately result in the same value. The second term ensures that the encoded distribution is close to known distribution that is easy to sample from. The function - a loss function on the data space. For exam- ple, Tolstikhin et al. (2118) took c(x, = | v113. diss(-..) is dissimilarity measure between probability distributions defined on the latent space. Tolstikhin et al. (2018) recommended either GAN-based dissimilarity measure or a Maximum Mean Discrepancy (MMD)- measure (Gret- ton al., 2012). this paper, we will consider the special cases, where this dissimilarity measure taken to be the Wasserstein-1 1 metric, which is the dissimilarity measure for WGANs (Arjovsky cct al. 2017 Gulrajani et al. 2017) or the squared MMD-metric.
In practice, however, one does not have access to μ but only sample {Xi assumed to be independently generated from p. Let ün be the empirical measure based on the data. One then minimizes the following empirical objective estimate E and G.
V (in, G, E) / c(2, G E(x))dāan (x) + Adiss( Egfn, v).
(3)
Here, diss(::)) is an estimate of diss(;; based only on the data, (Xi)se(m)- For example, if diss(:;)) is taken to be the Wasserstein-1 1 metric, then, diss Egin, v) W1 (Egfnn On the other hand, if diss(;,)) -) is taken to be the
one can take,
diss(EEfnn, v) = n(n
1
Σ ig
Σ/ n 1=1
2
2))x())
Of course, in practice, one does further estimation of the involved dissimilarity measure through 8z,- this
taking an estimate üm. based on m i.i.d samples (Z)))e(m) from v, i.e. im 1 case the estimate of V in (2) is given by,
V (inn P., G) / clz, Go Go E(z)ddinn + Adiss( Espnn vm).
(4)
4

---

Published as a conference paper at ICLR 2024
If diss(;,) -) is taken to be the Wasserstein- 1 metric, then, diss(Erffn, Dm) = W2 WI(Epfun Pm). On the other hand, if diss(-,-) is taken to be the MMDa-mmasuure, -measure one can take,
diss( Biss( Pm)) n(n
1
Σ ((XE(X)), m(m 1) K(Z,, 2,)
2
X(B(X,)) 2z).
=1j=1
Suppose that Opp > 0 is the optimization error. The empirical WAE estimates satisfy the following properties:
FC" E GES, FEE: Vi G, FJ
inf GES.BEE
U, + Aop
(5)
"emm,,mmmm E G REE: ((n, pn B) inf GES.EEE
V(nn: lm. G. B) + Aup
(6)
The functions in 9 and are implemented through neural networks with ReLU activation (L W₂) and RN W.). respectively.
4 INTRINSIC DIMENSION OF DATA DISTRIBUTION
Real data is often assumed to have a lower-dimeen wiver-dimensional structure within the high- nigh-dimenssonal feature space. Various approaches have been proposed to characterize this low dimensionality, with many using some form of covering number to measure the effective dimension of the underlying measure. Recall that the e-covering number of w.r.t. the metic @ is defined as ((;; S. g) inf(n N 3 Exi,... Fy such that U Be e) 2 S}. with Bg(z,e) e) {v e(z, y) < c}. We characterize this low-dimensional nature of the data, through the (upper) Minkowski dimension of the support of μ.. We recall the definition of Minkowski dimensions,
Definition (Upper Minkowski dimension). For bounded metric space e), the upper Minkwoski dimension S S is defined as dimas (S, e) -limsup,-o Ne; 9)
log(1/e)
Throughout this analysis, we will assume that @ is the -nom and simplify the notation to dim (S). dius of balls covering that set. As the concept of dimensionality relies solely covering numbers and doesn't 't require a smooth mapping to a lower-dimensional Euclidean space, encompasses both smooth manifolds and even highly irregular sets like fractals. In the literature, [Kolmogorov & Tikhomirov ( (I96T) provided a comprehensive study on the dependence of the covering number of different function classes on the underlying Minkowski dimension of the support. [akada & Imaizumi (2020) showed how deep regression learners can incorporate this low-dimensionality of the data that is also reflected in their convergence rates. Recently, Huang et al. (2022) showed that WGANs can also adapt to this low-dimensionality of the data. For any measure on [0, 1]a, we use the notation d₂ := dim (supp(H4)). When the data distribution is supported on -ow-dimesiiona structure in the nominal high-dimensional feature space, one can expect d, < d.
2) essentially measures how the covering number of S is affected by the ra-
It can be observed that the image of unit hypercube under a Hölder map has Minkowski dimen- sion that is no more than the dimension of the pre-image divided by the exponent of the Hölder map.
Lemma 5. Let, f E HY (A, 1362, C), with S [0, 1]ds, Then, dimas (f (A)) S dim (A)/(7
1).
THEORETICAL ANALYSES
5.1 ASSUMPTIONS AND ERROR DECOMPOSITION
To facilitate theoretical analysis, we assume that the data distributions are realizable, meaning that a "true" generator and a "true" encoder exist. Specifically, we make the assumption that there is true smooth encoder that maps the f to v, and the left inverse of this true encoder exists and is also smooth. Formally,
AL. There exists & E H (10, 1J2, [0. 118, C)) and È E I ((0, 118, [0, 1J C), such that, E.u and (G E)(-) id(:), ) a.e. [n].
5

---

Published as a conference paper at ICLR 2024
It is also important to note that AT entails that the manifold has single chart, in probabilistic sense, which is a strong assumption. Naturally, when it comes to GANs, one can work with a weaker assumption as the learning task becomes notably much simpler as one does not have to learn an inverse map to the latent space. A similar problem, while analyzing autoencoders, was faced Liu et al. (2023) where they tackled the problem by considering chart-autoencoders, which have additional components in the network architecture, compared to regular autoencoders. A similar approach of employing chart-based WAEs could be proposed and subjected to rigorous analysis. This potential avenue could be an intriguing direction for future research.
One immediate consequence of assumption AT ensures that the generator maps v to the target j.. We can also ensure that the latent distribution remains unchanged if one passes it through the generator and maps back through the encoder. Furthermore, the objective function ( at this true encoder- generator pair takes the value, zero, as expected.
Proposition 6. Under assumption Al the following holds: (a) Ggy 14, (b) (E G):y v, (c) V(,, u, Ō, B) =0.
From Lemma It clear that dp - dimar (supp(n)) S dimm (G(10,
(10, 119)
S max (E A 1), If é < and ag is not very small, then, d, = (arg A 1) < d. Thus, the usual conjecture of dy < d can be modeled through assumption when the latent space has much smaller dimension and the true generator is well- bellebehaved, i.c. ag is not too small.
A key step in the theoretical analysis is the following oracle incquality that bounds the excess risk in terms of the optimization error, misspecificatiion error, and generalization error.
Lemma (Oracle Inequality). Suppose that, F (x))) c(2, G F(())) GE S, F E. Then the following hold:
V(u, v, G", ,E S Amin + Doy + 211An u|lg + 2X sup REF.
(diss(Ezfinn v) - diss(E;;4) v/).
(7)
V(,, 6m. Em S Amin + Agg + 2l - n||= + 2A
sup diss(E (Eg Dm) - diss( Egp, v))l
(8)
BEe
Here, Amiss infGes,Ees V(,, v, E) denotes the misspecification error for the problem.
For our theoretical analysis, we need to ensure that the used kernel in the MMD and the loss function e(ss-) are regular enough. To impose such regularity, we assume the following:
A2. We assume that, (a) for some B > 0, K(x, y) S for all x, E [0, 1 (b) For some The
[5((,, u) - -K(x', ,u') S TTl[1 - 2'112 + 1ll y 2/(12)-
A3. The loss function c(.,-) is Lipschitz on [0, 1]a x 10. i.e. lc(2,)) c(ø', ./)l s re(llz
x'1la + lly 222) and c(x, y) I for all. x, y E [0.
5.2
MAIN RESULT
Under assumptions 3 one can control the expected excess risk of the WAE problem for both the W, and MMD dissimilarities. The main idea is to select appropriate sizes for the encoder and generator networks, that minimize both the misspecification errors and generalization errors to bound the expected excess risk using Lemma 7 Theorem g shows that one can appropriately select the network size in terms of the number of samples available, i. n, to achieve a trade-off between the generalization and misspecification errors as selecting a larger network facilitates better approximation but makes the generalization gap wider and vice-versa. The main result of this paper is stated as follows.
Theorem 8. Suppose that assumptions A A733 hold and Dopt < A for some fixed non-negative dy. Then we can find ny E and 3 > O, that
threshold A. Furthermore, suppose that might depend on d, E, agg, aee G and E, such that if n 2 no. we can choose 9 = RN(LL Wg) and & RN(Le, We), with, Le S 3 log n, W. < 1 log n, Lg I 3 log n and Ws, < 3n Belaggg log n, then, for the estimation problem
(a) EV
max
mg Reloo
log for diss(-,)) = Wi(..))

---

Published as a conference paper at ICLR 2024
(b) EV v, GTh "r,, + 24max oolagh1) log² for -
(max 2+ e ag 24 ((ngn))))) ((ev2)
Furthermore, for the estimation problem (6. if V
(c) EV (1, U, Gt, BT) S +n
max 2+
mg
L 2t melig log" n. for diss(-.)) Wi(()))
(d) EV U, Gn.m
En.my
21 a + n2
og on oalgghii log" n. for diss(:.-) (.
Before we proceed, we observe some key consequences of Theorem g
Remark 9 (Number of Weights), We note that Theorem g suggests that one can choose the net- works to have number of weights to be an exponent of n, which smaller than 1. Moreover, this exponent only depends on the dimensions of the latent space and the intrinsic dimension of the data. Furthermore, for smooth models i.c. ae and 0g are large, one can choose smaller networks that require less many parameters as opposed to non-smooth models as also observed in practice since easier problems require less complicated networks.
Remark 10 (Rates for Lipschitz models). For all practical purposes, one can assume that the di- mension of the latent space is at least 2. If the true models are Lipschitz, i.e. if ae 0g 1, then we can conclude that l = du- Hence, for both models, we observe that the excess risk scales as
On 2444) ), barring the poly-log factors. This closely matches rates for the excess risks for GANs (Huang et al. 2022).
Remark 11 (Inference for Data on Manifolds). We recall that we call a set M is d-regular w.r.. the d-dimensional Hausdorff measure Hd if IHI( (Z, r)) x rdd for all E M (see Definition 6 of Weed and Bach (2019)). It is known (Mattila, 1999) that if . is d-regular, then the Minkowski dimension of M is d. Thus, when supp(u) is d-regular, dy d. Since compact d-dimensional differentiable manifolds are d-regular (Proposition of Weed and Bach (2019)), this implies that for when supp(u) a compact differentiable d d-dimensional manifold. the error rates for the sample estimates scale as in Theorem 8, with dy replaced with d. A similar result holds when Suрр(μ)) is a nonempty, compact convex set spanned by an affine space of dimension d; the relative boundary of a nonempty, compact convex set of dimension d + 1; or self-similar set with similarity dimension d.
5.3 RELATED WORK ON GANS
To contextualize our contributions, we conduct a qualitative comparison with existing GAN liter- ature. Notably. Chen et al.] (2020) expressed the generalization rates for GAN when the data is restricted to an affine subspace or has mixture representation with smooth push-forward measures; while Dahal et al. (2022) derived the convergence rates under the Wasserstein- distance in terms of the manifold dimension. Both Liang (202T) and [Schreuder et al.] (021) study the expected excess risk of GANs for smooth generator and discriminator function classes. Liu et al. (202I) studied the properties of Bidirectional GANs, expressing the rates in terms of the number of data points, where the exponents depend on the full data and latent space dimensions.
is important to note that both Dahal et al. (2022) and Liang (202T) assume that the densities of the target distribution (either w.r.t Hausdorff or the Lebesgue measure) are bounded and smooth. In comparison, we do not make any assumption of the existence of density (or its smoothness) for the target distribution and consider the practical case where the generator is realized through neural networks as opposed to smooth functions as done by Liang] (2021) and Schreuder et al. (202I). Diverging from the hy- potheses of Chen et al. (2020), we do not presuppose that the support of the target measure forms an affine subspace. Furthermore, the analysis by Liu et al.) (202T) derives rates that depend on the dimension of the entire space and not the manifold dimension of the support of the data as done in this analysis. It is important to emphasize that Huang et al. (022) arrived at rate comparable to ours concerning WGANs (Arjovsky et al.) 2017). While both studies share common overarching approach in addressing the problem by bounding the error using an oracle inequality and managing individual terms, method necessitates extra assumptions to guarantee the generative capability of WAEs, which does not apply to WGANs due to their simpler structure. Interestingly, our derived rates closely resemble those found in GAN literature. This suggests limited room for substantial
7

---

Published as a conference paper at ICLR 2024
improvement. However, demonstrating minimaxity remains significant challenge and promising avenue for future research.
5.4 PROOF OVERVIEW
From Lemma 7 it is clear that the expected excess risk can be bounded by the misspec- ification error miss and the generalization gap, I| pully Xsupree [diss( Pqgi;; v) diss( EpH, 2)|- To control Amiss we first show that if the generator and encoders are cho-
sen as = RW, -s/a: log(1/<.) and Wg S (x0gg" -t/os log(1/<g) then, Amiss & 'g te - og log(1 ( We agde agge On the other hand, we show that the generalization enror is roughly Vn-"Wale log W. log n + Vn=I(W++ + (he + Tng) log We + W log n, with additional terms depending on the estima- tor. Thus, the bounds in Lemma 7 leads a bound roughly,
and = RN Le). with Le I ag log(1/Eg), Lg S
A + Vn- Wele log We log + Vn-1(We Wo)(Le L,) log(W, Wg) log (9)
By the choice of the networks, we can upper bound the above as a function of eg and c, and then minimize the expression w.r.t. these two variables to arrive at the bounds of Theorem X Of course, the bound in (9) changes slightly based on the estimates and the dissimilarity measure. We refer the reader to the appendix, which contains the details of the proof.
5.5 IMPLICATIONS OF THE THEORETICAL RESULTS
Apart from finding the error rates for the excess risk for the WAE problem, in what follows, we also ensure few desirable properties of the obtained estimates. For simplicity, ignore the optimiza- tion error and set upp O.
Encoding Guarantee Suppose we fix À > 0, then, is clear from Theorem 8 that EW, (E,,,,)) S
n moxe 21 + 21 (e( i) log" n and EMMD (E,J4, v) S n 2 1m nelogeat) log n. We can not only characterize the expected rate of convergence of EyJz to v but also can say that Figaa con- verges in distribution v, almost surely. This is formally stated in the following proposition.
Proposition 12. Suppose that assumptions A 7 hold. Then, for both the dissimilarity measures W2(..) and ( and the estimates and (6 Egjo S v, almost surely.
Therefore, if the number of data points large, i.e., n is large, then the estimated encoded distribu- tion Egg will converge to the true target latent distribution v almost surely, indicating that the latent distribution can be approximated through encoding with a high degree of accuracy.
Decoding Guarantee One can also show that E. f c(2, G {(x)))u(xx) S (,, B). for both the estimates in (5) and 6 For simplicity, if we let c(x,0) || v12.. then, it can easily co, where id(x) is the identity map from gd Rd. Furthermore, it can be shown that, [|)d(-) G E(- e. 0 stated in Corollary
seen that, Bllid(()) - G E.)
0
13
Proposition 13. Suppose that assumptions A 1 hold. Then, for both the dissimilarity measures W and (M)'s(.s)) and the estimates and 6 [[dd(.) & B())ll,
a.s. 0.
Proposition 13 guarantees that the generator is able to map back the encoded points to the original data if sufficiently large amount of data is available. In other words, if one has access to a large number of samples from the data distribution, then the generator is able to learn mapping, from the encoded points to the original data, that is accurate enough to be useful.
Data Generation Guarantees A key interest in this theoretical exploration whether one can guarantee that one can generate samples from the unknown target distribution through the gener- ator, i.e. whether G.p is close enough to in some sense. However, one requires some additional Tang & Yang 2021 & or the nature of convergence
assumptions CChakrabarty & Das 2021
8

---

Published as a conference paper at ICLR 2024
of EyJo to y to ensure this. We present the corresponding results subsequently follows. Before proceeding, we recall the definition of Total Variation (TV) distance between two measures Y and 72, defined Ω, as, (V 72) (())) Im (B) - (B()), where, B(22) denotes the Borel o-algebra S2
Theorem 14. Suppose that assumptions A 4 hold and TV (E3 + 0. almost surely. Then, G.v 4 almost surely.
We note that convergence in TV is a much stronger assumption than convergence in Wi or MMD in the sense that TV convergence implies weak convergence but not the other way around.
Another way to ensure that G.v' converges to fr is to put some sort of regularity on the generator estimates. Tang & Yang (2021) imposed Lipschitz assumption to ensure this, but one can also work with something weaker, such as uniform equicontinuity of the generators. Recall that we say family of functions, F is uniformly equicontinuous if, for anyf F and for all e 0, there exists a > such that, [f() f(y) S e, whenever, ||= - yll S ō.
Theorem 15. Suppose that assumptions A hold and let the family of estimated generators
hneN be uniformly equicontinuous, almost surely. Then, Cryy 4 μu, almost surely.
Uniformly Lipschitz Generators Suppose that diss(:,.) = Wi(-.). If one assumes that the estimated generators are uniformly Lipschitz, then, one can say that (I 14) is upper bounded by V(H, u, G, F.), disregarding some constants. Thus, the same rate of convergence as in Theorem holds for uniformly Lipschitz generator. We state this result formally as a corollary as follows.
Corollary 16. Let diss(-,-) = Wi(,,)) and suppose that the assumptions of Theorem & are satisfied and 8 > dy- Also let suPnEN || suPm,neN [| Lip S L,, almost surely, for some I, > 0. WI p) S (p,,u v, G,E) E) for both estimators and 6
It is important to note that although assumptions AD do not directly guarantee either of these two conditions, is reasonable to expect the assumptions made in Theorems 14 and [5 to hold in prac- tice. This is because regularization techniques are commonly used to ensure the learned networks É and & are sufficiently well-behaved. These techniques can impose various constraints, such as weight decay or dropout, that encourage the networks to have desirable properties, such as smooth- ness sparsity. Therefore, while the assumptions made in the theorems cannot be directly ensured by A[F3] they are likely to hold in practice with appropriate regularization techniques applied the network training. It would be key step in furthering understanding to develop similar error analysis for such regularized networks and we leave this as a promising direction for future research.
DISCUSSIONS AND CONCLUSION
In this paper, we developed framework to analyze error rates for learning unknown distributions ing Wasserstein Autoencoders, especially when data points exhibit an intrinsically low-dimensional structure in the representative high-dimensional feature space. We characterized this low dimen- sionality with the so-called Minkowski dimension of the support of the target distribution. We developed an oracle inequality characterize excess risk in terms of misspecification, generaliza- tion, and optimization errors for the problem. The excess risk bounds are obtained by balancing nispeiiiis and stochastic errors to find proper network architectures in terms of the number of samples that achieve this tradeoff. Our framework allows us to analyze the accuracy of encoding and decoding guarantees, i.e., how well the encoded distribution approximates the target latent distribution, and how well the generator maps back the latent codes close to the original data points. Furthermore, with additional regularity assumptions, we establish that the approximating push-forward measure can effectively approximate the target distribution.
While our findings provide valuable insights into the theoretical characteristics of Wasserstein Au- toencoders (WAEs), it's crucial to acknowledge that achieving accurate estimates of the overall error in practical applications necessitates the consideration of an optimization error term. However, the precise estimation of this term poses significant challenge due to the non-convex and intricate nature of the optimization process. Importantly, our error analysis remains independent of this opti- mization error and can seamlessly integrate with analyses involving such optimization complexities.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENT
We gratefully acknowledge the support of the NSF and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning through awards DMS-2031883 and #814639 and the NSF's support of FODSI through grant DMS-2023505.
REFERENCES
Martin Anthony and Peter Bartlett. Neural network learning: Theoretical foundations University Press, 2009.
Cambridge
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, pp. 214-223. PMLR, 2017.
Peter L Bartlett and Shahar Mendelson. Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. Journal of Machine Learning Research, 3(Nov):443-442, 2002.
Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mchrabian, Nearly-tight VC-dimension and pscudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):2285-232) 2019.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymp- totic theory of independence. Oxford University Press, 2013.
Anish Chakrabarty and Swagatam Das. Statistical regeneration guarantees of the wasserstein au- toencoder with latent space consistency. Advances in Neural Information Processing Systems, 34: 17098-17110, 2021.
Minshuo Chen, Wenjing Liao, Hongyuan Zha, and Tuo Zhao. Distribution approximation and statis- tical estimation guarantees of generative adversarial networks. arXiv preprint arXiv:2002.03938, 2020.
Biraj Dahal, Alexander Havrilla, Minshuo Chen, Tuo Zhao, and Wenjing Liao. On deep generative models for approximation and estimation of distributions on manifolds. Advances in Neural Information Processing Systems, 15:100155-1622 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. In 2009 IEEE Conference Computer Vision and Pattern Recognition, pp. 248-255, 2009. doi: 10. 200.C......0.220066660
Jeff Donahue, Philipp Krähenbühl, and Trevor Darrell. Adversarial feature learning. International Conference on Learning Representations, 2017. /ttl/httss////eerrriiie net/ forrmm?
id=BJtNZAFgg
Rafael BombzrBom Jennifer N Wei, David Duvenaud, José Miguel Bernández-Lobate Benjamín Sánchez-l Lengeling. Dennis Sheberla, Jorge Aguilera-Iparraguirre Timothy Hirzel, Ryan P Adams, and Alán Aspuru-Guzik, Automatic chemical design using data-driven contin- uous representation of molecules. ACS central science, 4(2):268-21) 276, 2018.
Ian Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative Adversarial Nets. In Advances in Neural Infor- mation Processing Systems, volume 27. Curran Associates, Inc., 2014.
Karol Gregor, Ivo Danihelka, Alex Graves, Danilo Rezende, and Daan Wierstra. Draw: A recurrent neural network for image generation. In International Conference on Machine Learning, pp- 1462-1471. PMLR, 2015.
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kereel sample test. Journal of Machine Learning Research, 13(25):723-773 2012. URL http: //mml r. www.o//pppg./.....333.
2a. html
10

---

Published as a conference paper at ICLR 2024
Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Im- proved Training Wasserstein GANs. Advances Neural Information Processing Systems, 30, 2017.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge local nash equilibrium. Advances in Neural Information Processing Systems, 30, 2017.
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with constrained variational framework. In International Conference on Learning Representations, 2017.
Jian Huang, Yuling Jiao, Zhen Li, Shiao Liu, Yang Wang, and Yunfei Yang. An error analysis of generative adversarial networks for learning distributions. Journal of Machine Learning Research, 23(116):1-44 43, 2022.
Hisham Husain, Richard Nock, and Robert C Williamson. A primal-dual link between gans and autoencoders. In H. Wallach, H. Larochelle, A. Beygelzimer. F. d'Alché-Buc E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, Cur- Associates, Inc., 2019. http:///e..eeeee222ee20000000500
httpttpsspppocceeeiiie ngs www.rpss....... wwwp:per_rpppppeeeeeeee fi l wtw..eariiss...cepppeeeeeeee
Alan Karr. Probability. Springer Texts in Statistics. Springer New York, NY, edi- tion, 1993.
doi: 10. 10110077978-114411-0081111 URL https: wtt.://oo..ooooooooooooooo 10. 1007/
978 105-144612 4612 0891-4
Jisu Kim, Jaehyeok Shin, Alessandro Rinaldo, and Larry Wasserman. Uniform convergence rate of the kernel density estimator adaptive to intrinsic volume dimension. In International Conference on Machine Learning, pp. 3398-3407. PMLR, 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Diederik P Kingma and Max Welling, Auto-encoding variational bayes. In International Conference
on Learning Representations, 2014.
Frederic Koehler, Viraj Mehta, Chenghui Zhou, and Andrej Risteski. Variational autoencoders in the presence of low-din -ww-dimensional data: landscape and implicit bias. In International Confer- ence on Learning Representations, 2022. URL https:://// http:///ppeeeeeeeeeeeeeee net/:enee//EEee forttffooummdd
y_ LLaWI.
Andrey N Kolmogorov and Vladimir Mikhaulovich Tikhomirov. e-entropy and e-capacity of sets in function spaces. Translations of the American Mathematical Society, 17:277-364, 1961.
Tengyuan Liang. How well generative adversarial networks learn distributions. The Journal of
Machine Learning Research, 22(1):10366-10400 2021.
Hao Liu, Alex Havrilla, Rongjie Lai, and Wenjing Liao. Deep nonparametric estimation of intrin- sic data structures by chart autoencoders: Generalization error and robustness. arXiv preprint arXiv:2303.09863, 2023.
Shiao Liu, Yunfei Yang, Jian Huang, Yuling Jiao, and Yang Wang. Non-asymptotic error bounds for bidirectional gans. Advances in Neural Information Processing Systems, 34:12328-12339, 2021.
Alireza Makhzani. Jonathon Shlens, Navdeep Jaitly, Ian Goodfellow, and Brendan Frey. Adversarial autoencoders. In International Conference on Learning Representations, 2016.
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. Adversarial variational bayes: Unifying variational autoencoders and generative adversarial networks. In Proceedings of the 34th Inter- national Conference Machine Learning- Volume 70, pp. 2391-2400. JML.R. org, 2017.
11

---

Published as a conference paper at ICLR 2024
Ryumei Nakada and Masaaki Imaizumi. Adaptive approximation and generalization of deep neural network with intrinsic dimensionality. Journal of Machine Learning Research, 21(174):1-38, 2020. CRLpttt:://// http://mmmmoorro.poooooaa wwwppppwppppppppptttttttt..eeett
pttppp/////////02222222 html
Phil Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrinsic dimension of images and its impact on learning. In International Conference on Learning Repre- sentations, 2020.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In International Conference Machine Learning, pp. 8821-8831. PMLR, 2021.
Michal Rolinek, Dominik Zietlow, and Georg Martius. Variational autoencoders pursue pea direc- tions (by accident). In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 12406-12415, 2019.
Mark Rudelson and Roman Vershynin. -hrihnn-riight inequality and sub-gaussian concentration. Electronic Communications in Probability, 18(none):1 2013. doi: 10.1214/ECPw18- 2865.65.
URL httptttss//doiooo///// 1tt.//...1/1111/1...... 221//CCPP...
Nicolas Schreuder,
Brunel, and Arnak Dalalyan. Statistical guarantees for gen- erative models without domination. In Algorithmic Learning Theory, pp. 1051-1071. PMLR, 2021.
Kihyuk Sohn, Honglak Lee, and Xinchen Yan. Learning structured output representation using deep conditional generative models. Advances in neural information processing systems, 28, 2015.
Hideyuki Tachibana, Katsuya Uenoyama, and Shunsuke Aihara. Efficiently trainable text-to-speech system based on deep convolutional networks with guided attention. In 2018 IEEE international conference on acoustics, speech and signal processing (ICASSP), pp. 4784 4788. IEEE, 2018
Rong Tang and Yun Yang. On empirical bayes variational autoencoder: An excess risk bound. In Conference on Learning Theory, pp. 4068 4125. PMLR, 2021.
Ilya Tolstikhin, Olivier Bousquet, Sylvain Gelly, and Bernhard Schoelkopf. Wasserstein auto- encoders. International Conference on Learning Representations, 2018.
Aaron Van Den Oord, Oriol Vinyals, al. Neural discrete representation learning. Advances in Neural Information Processing Systems, 30, 2017.
Roman Vershynin. High-dimenssonal probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Martin Wainwright. High-dimensional statistics: A Non-asymptotic Viewpoint, volume 48. Cam- bridge University Press, 2019.
Zichao Yang. Zhiting Hu, Ruslan Salakhutdinov, and Taylor Berg-Kirkpatricks Improved varia- tional autoencoders for text modeling using dilated convolutions. In International Conference on Machine Learning, pp. 3881-389) PMLR, 2017.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Shengjia Zhao, Jiaming Song, and Stefano Ermon. Infovae: Information maximizing variational autoencoders, arXiv preprint 1rXivv1706.02266 2017.
12

---

Published as a conference paper at ICLR 2024
Appendix
CONTENTS
Introduction
2
A Proof of Concept
3
Background
3.1
Notations and some Preliminary Concepts
3.2
Wasserstein Autoencoders
Intrinsic Dimension of Data Distribution
Theoretical Analyses
5.1
Assumptions and Error Decomposition
Main Result
5.3
Related work GANs
5.4
Proof Overview
5.5
Implications of the Theoretical Results
6
Discussions and Conclusion
Additional Notations
14
B Proof of the Main Result (Theorem) 8)
14
Misspecification Error
14
B.2 Bounding the Generalization Gap
15
B.3 Proof of Theorem
16
Detailed Proofs
17
Proofs from Section
17
Proofs from Section
18
C.2.
Proof of Proposition
18
Proof of Lemma
18
Proofs from Section B.
19
Proof of Theorem
19
Proof of Lemmal
21
Proots from Section
22
C.4.
Proof of Lemma
22
C.4.2
Proof of Corollary
23
C.4.
Proof of Lemma 22
23
13

---

Published as a conference paper at ICLR 2024
4.44 4
Proof of Lemma
24
Proof of Lemmal
25
4,66
Proof of Lemma
26
5
Proots from Section
28
C.6
Proofs from S.5
28
C.6.1
Proof of Proposition 12
29
Proof of ."..............................
C.6.2
C.6.3 Proof of Theorem 14
30
C.6.4 Proof of Corollary 16
30
D Supporting Results for Approximation Guarantees
31
Supporting Results from the Literature
32
A ADDITIONAL NOTATIONS
For function classes F1 and F2, F1 o F = ff
Definition (Covering and Packing Numbers). For a metric space (S, g). the e-covering number w.r.t. is defined as: N S,; 2) in N ..,,... such that U B Be( 2 S). minimal cover of denoted C(e; g) Similarly, the e-packing number is defined as: M,e:S,g) m N: 31: Zm E 8 such that ,, 2 e, for all i ( $}..
B PROOF OF THE MAIN RESULT (THEOREM 8
B. MISSPECIFICATION ERROR
We begin with theoretical result to approximate any function low-dimensional structure using a ReLU network with sufficiently large depth and width. Let f belong to the space J (IRd, d IR, C?), with C > 0, and let y be measure Rd For notational simplicity, let M supp(?). Then, for any and > dry we prove that there exists ReLU network, denoted by f. with a depth of most (log(1/ ( and number of weights not exceeding (cc-a/8 log(1/<)): and bounded weights. This network satisfies the condition || - fll (M)) S c. A similar result with bounded depth but unbounded weights was derived by Nakada & Imaizumi (2020).
Theorem 18. Let I be element of HD (RR, R, C), where C> Then, for any s >> dy, there exists constants (which may depend on 7) and a, (which may depend on B, d, and C), such that if c E c0, ReLU network f can be constructed with L(f) < a log(1/c) and W(f) < log(1/e)e==// s/3, satisfying the condition, |I -flle. S.c.
Applying the above theorem, assumptions 3 we derive the following bound on the misspecification error. is important to note that none of the network dimensions depend on the dimensionality of the entire data space, i.e.
control Amise. when the network size is large enough. Under
d.
A hold and let, diss(-.-) = Wi(:--) or MMD Also, let > dn. Then, we can find positive constants cp. on and R. that might depend on d,e,G and F, such that if0 < Eg, Ee S eo and 9 = RW Lgg R) and RN Le, Rt), with
Lemma 19. Suppose assumptions
Le S au log(1/cg)) Lg I an log(1/ag), W. I cayc 3/ac log(1/ce) and Wg I auc t/a, log(1/c,)
then, Amiss S Eg l1
14

---

Published as a conference paper at ICLR 2024
B.2 BOUNDING THE GENERALIZATION GAP
Let f: IRd + Rdd and (Xihetm C R. We define fIx... as (S(X)) : :..:; [(Xx)] E BRd' xn For
function class F, we define
Fx = Uxx EEFFC Rd
The covering number of Fix,., with respect to the Lo -orm is denoted by (e; (o The result extends the seminal works of Bartlett et al. (2019) to determine the metric entropy of deep learners with multivariate outputs.
Lemma 20. Suppose that n 2 6 and F are a class neural network with depth at most L and number of weights at most W. Furthermore, the activation functions are piece-wise polynomial activation with the number of pieces and degree at most k E N. Then, there is a constant (that might depend on d and d' , such that, i 0(W 6d' 2d' L) 3) (log(W V + -dd + 2d' L) L 3),
nd'
Log,N(;;; (ex
(W 6d' + 2d' LL + 3) (log(W + 6d + 2d 2d + L + log
where d' is the output dimension of the networks in F.
We can use the result above provide bounds on the metric entropies of the function classes de- scribed in Lemma 7 This bound is a function of the number of samples and the size of the network classes 9 and E.
Corollary 21. Suppose that W(E) S We. L(E) Le. W(S) S Wa and L(9) S Lg. with Te, Tug 2 3. W. 2 bl + 20 and W, 2 6d + 2dL.g. Then, there is a constant E1, such that if E1 (We + Wg (T) + Ing) (log(We Wg) + Le I.g),
log.V (c; (x:8)xmm(a)) We We + Le) log
nf
log.V( ( los) S(W. Wg)(Le + Lg) (log(We + +,,) + Le Lgg log
nd
Using Corollary 21 the following lemma provides a bound on the distance between the empirical and target distributions w.r.t. the IPM based on F.
Lemma 22, Suppose R(9) S and F = (f(x) = c(a, G o E(x)) G E 9, E E E}. Fur- thermore, let, L(E) < T... W(S) & W, and L(9) Tag with bay Tug 2 3, W. 2 68 28
and W, 2 6d + 2dLg. Then, there is constant &z, such that if 2 &eW + Wg) + Lg) (log(W: (W. + Wg) Le + Lg)
EllAA ally S 1/2 ((We+ + Wy)(L. Ly) (log(W + Wg) + L. + Lg) log(nd)) 1/2
To control the fourth terms in 7 and 8). we first consider the case when diss(.,)) .) is the W1- distance. Lemma 23 controls this uniform concentration via the size of the networks in & and the sample size
Lemma 23. Let fnn = 1 En 5x, and = RL, We). Then,
W. Loe (log W. + La) log(ne)
sup (1 FEE
112 1/2 logn) +
n
Furthermore,
sup (Eghnn -W S BEE
(1 1n0 v 11/2 logn) + (m-1/e
1/6 v m 1/2 log m
W. WeLe We + Le) log(nE)
+
n
Before deriving the corresponding uniform concentration bounds for IMM (Egūnn)) MMD (Fgjin))) or |MMD& (Fejinn Bm)) (MDD((FFgnnn 2)], recall the definition of
15

---

Published as a conference paper at ICLR 2024
Rademacher complexity (Bartlett & Mendelson 2002). For any real-valued function class F and data points X1m = {Xi..... X. the empirical Rademacher complexity is defined as:
R(F - -B
Ea sup Σ oxi)) n JEF
where a,'s are i.i.d. Rademacher random variables taking values in {-1,+1}, with equal proba- bility. In the following lemma, we derive a bound on the Rademacher complexity of the class of functions in the unit ball w.r.t the Hoy-norm composed with &. This lemma plays a key role in the proof of Lemma 24 The proof crucially uses results by Rudelson Vershynin (2033.
Lemma 24. Suppose assumption A2 holds and let, L(E) I Le and L(S) S Lg with Le 2 3. We 2 28(3 + Le). Also suppose that, + = {ō E Hly: lax I 13, then,
V WeLo (log We Le) log(n()
R(( 8), Xim)
Using Lemma 24 we bound the fourth term in and for diss(...) = MMD (:,,), in Lemma
25
Lemma 25. Under assumplion A the following holds:
MMDx (Egfnn v) MMD (E & We log W. log(nz)
(a) E sup BEE
(b) E sup EEe
MMD MMD
W. W.L,(log W.+L L. log
8
mm
B.3 PROOF THEOREM g
Theorem 8. Suppose that assumptions A73 hold and Dapt S A for some fixed non-negative
threshold A. Furthermore, suppose that dp- Then we can find no E and 3 > 0, that might depend on d, e, Org, Oce, G and E, such that if 2 no. we can choose 9 = RN Wg) and & RN, We), with, Thc S 3 Blogn, W. S Bnzacta log n, by S 3 Boog n and W, < 3n Pol log then, for the estimation problem
(a) EV(,, v. GTh Ed) <n
24 delagnay log" n, for diss(...) = W.(.,)).
(b) EV v, GTh ETH SA+n
24:mAx anlága))
log² n, for diss(.,) MMD
m+ og 2+
du ()) ((v2)
Furthermore, for the estimation problem 66. if n
(c) EV (1, 6Th ET) S A max
( 2+ ag on (agggn
log² n. for diss(-;) (....).
(d) EV Cm. Enmy S
+n
24max Bg Belagasl
log" n, for diss(-.-) = &M
Proof. Proof of part (a) From Lemmas
22 and 23 we get,
EV EV 6Th En)
54 + cg + coall +
W. La log W. log
(Wa + WL) + Lgg Loglog((
log(Wo, We + Wg log
(n-2/e vn 1/22)
3/2
ce s/0c log
(ce s/aa + cgg
-t/ag) logn
SA+ + t ayhl + log
1
+ (n-i/ vn -2/2)
E6 A Eg
n
<A+ + EdaAl + +(10g log
1
3/2
Ce
8/oc log
Eg
Ltjag log n
+ +(n (111 -11/2
Ee A AE
16

---

Published as a conference paper at ICLR 2024
We choose, 6g = n 21 and 6e AlngA1)-0 This makes,
(H, G", En) + log n max ay oelig A2] + -n1//
Proof of part (b) From Lemmas 22 and 25 we get,
(M, v, G", ,",
WeLe Le log We log
(We + W Lg) loglog(W + Wg logn
AA + co + tgg
n
n
<A Co + cogAl
log
3/2
8/0 log
(Ec
-8/0 -t/og) log
Eg n
co n Eg.
n
2A + + @gg1+ log
Ee A Eg )
3/2
a/o log
Eg
_t/ay log
n
n
We choose, Cg x n 2t and Co x n [(agAi)- ac. This makes,
EV 6th Em) <A + log xxx
Proof of part (c)
Again from Lemmas 22 and
we get,
EV (H, &mh En) SA + eg + Eagh [log
Eo A (=1=))
3/2
s/ac log
Cg
f/og
log
n
n1
vn (n-1/vvn v 11/2)
(1/ 1mmm-1 m-1/2)
1/8
Choosing cy x n result.
Ce x
AagAist and m as in the theorem statement gives us the desired
Proof of part (d) Similarly, from Lemmas 22 and 25
we get,
EV(u,, &n, Em) SA + + c ag + log
3/2
Ee
s/ac
log
Eg
t/as
log
A
n
m
Choosing Eg x x n ziggnbit oe and m as in the theorem statement gives us the desired result.
C DETAILED PROOFS
C.I PROOFS FROM SECTION 4
Lemma S. Let, f E HY (A, [o, 1]da,C) with A (0, 1] Then, dimms (J S dim (A)/(7A
1).
Proof. Then, for any g,y A. 11(x)) - f(v)lloc I [f(x) - f())l12 5 L||x y 1 s
Tak Ta( vllaal. Thus, / (e: (A) .1),ll (1.0) N
( (e/))(()) ;A, -112))
log (e/T)) :.A.I || 11x0)
log (e: (A), )lo0) lim
dim (A)
dimm (f (A)) = lim
= log(1/e)
log(1/e)
17

---

Published as a conference paper at ICLR 2024
C.2 PROOFS FROM SECTION 5.1
C.2.1 PROOF OF PROPOSITION
Proposition 6. Under assumption A the following holds: (a) ue (,) (E G)
u, (c),, G, F.) =.
Proof.
(a) Let f 2 + R be any bounded continuous function. Then.
I [())d((p)))) - / (( f((()))du(z)
| (G((())))dp(o)
(10)
/ (())dp(x)
(11)
Hence, Gyv = μa. Here both (10) and follows from
(b) Let f X - IR be any bounded continuous function. Then,
I f(x)d (Bo
/ ((B(G(2)))d((2)
f ((E(x))du(z))
(12)
/ f(=)du(2).
(13)
Here, (12 follows from part (a) and (13) follows from A
(c) To prove part (c), We note that, Wi (F MMD = 0 and (G B)(-) id(-), a.c. [u].
C.2.2 PROOF LEMMA 7
Lemma (Oracle Inequality). Suppose that, 3 [f(x)) c(2, Go Ge 9, E 8). Then the following hold:
V(u,v, GTh """) S Amin + Doys + 21 ully + 2X sup REE
diss Eris,E v) - diss Expt v)].
(7)
V(u,e, Gmmm En Amin + Agr + 2l A||s + 2λ sup diss diss(EE Dm)) - diss( Egp, v)).
(8)
Bee
Here, Amiss infGes.FEE V(,,u, G) denotes the misspecification error for the problem.
Proof. To prove the first inequality, we observe that, V(ūn; &r F:)) S V, F) + Asps.
for any G E 9 and &. Thus,
(M,
G, (V (pn &", Br7) + (V(Rm,,, C,, - (V,, -V
SV(,,,G,EE V", En) V(p,, 6 B²) (V(P,,,,G.E) V(,.n, Agn
<Anp V(,,,, G.E)+2 +2 sup GES.
[Vnn,, v, G) (H,,
Amp + "H,,,,GEE)
c(z Gz Go ((x))dfn(()) Adiss (afissEEfun.1) v) / /
+2 sup GES, EEE
Go G Adiss(Egu,
18

---

Published as a conference paper at ICLR 2024
-a
0
a b
Figure 2: Plot of Ea,b(-)
SAm + V(,, G, 2 -Mlls + 2A sup diss (ggnn 1/) Eiss(EEj1, v)).
BEe
Taking infimum G and E, get inequality
7
Inequality (8) follows from similar derivation.
C.3 PROOFS FROM SECTION B.
C.3.1 PROOF THEOREM 18
Fix 6 > For > du. we can say that (e; fxe S Ce-", for all e > Let K = For any i E [K] let 0² = (e 2(11 I)c..... c 2(ia 1)c). We also let, P. = [Be,. (0', :0:22 [K]*]
sets in P. are disjoint. We first claim the following: Lemma 26. |fA E. AnM 0}| - =
By construction,
Proof. Let, r = Nee (5o) and suppose that {ai...., a,) be an e-net of M and Pe (Biz (a,,e) i [r]] be an optimal e-cover of M. Note that each box in Pe can intersect most 2d boxes in Pe. This implies that,
MM < [Pe n [ (a, e))l 1U (Pe Be (ai, e)) s 2
which concludes the proof.
We are now ready to prove Theorem follows:
18
For the ease of readability, we restate the theorem as
Theorem 18. Let f be an element of H (R. R, C), where C Then, for any s > dy, there exists constants (which may depend on 7) and a, (which may depend on B, d and C), such that if E (0, ReLU network f can be constructed with L(f) S a aolog(1 /c) and W(f) s log((/e)ee=fff satisfying the condition, Ilf fll Sc
Proof. We also let {ie [K]2: Be_ (0',e) nM # #0. We also let It {j [K]d
minjer | - -1l1 < 1}. We know that [Z|] < 3d s (E; For < b S a, let,
I + a b-
x x
x ---b -==))
(as(x) = ReLU
ReLU
ReLU
ReLU
a- a-
a-
pictorial view of this function is given in Fig. and can be implemented by ReLU network of depth two and width four. Thus, L(Ea,)) = 2 and W(E..)) = 12. Suppose that 0 < 8 < e/3 and let, ((w) H7_ (xE), It is easy observe that (C(- 0²) It} forms partition of unity on M, i.e. EiEr ((x - 0²) 1, Var M.
We consider the Taylor approximation of f around 0 as.
0 (())
Po(a:)
Σ
(x 0)*
s!
| |8]
19

---

Published as a conference paper at ICLR 2024
Note that for any E [0, f(x) - Po(x) ->:lee==[0] (x-0)' f(y) 8 f(0)), for some y,
which is convex combination of and 0. Thus,
(x 0)*
1
f(x) - Po(x) =
Σ
(0 f(y) - 0 f(0)
<| x 010
Σ
100 f(y) 8 f(0)
s!
8!
8:
[8]
<| 0
0
1y 0
11 L
20
<| 0 0
(14)
Next we define f(x=) Eiezi ((x (ar)). Thus, if x E M,
f(x)] =
Σ <i0- - (f((x) - Pox(x)) 5
Σ
[f(x) - Por(2)
iEZt
KE 1|- 1|-----0 12
- E.
(15)
We note that, f(x))
Eiezi ((x (ox) EiErt E|s|||a|
0'())))
{( -0i) xz 0²)²
al
Let ai,a 0" )(0') and
8l
[1, =prodddttolllleeeo (Se,, (x1 - -0)) 0f)..... Sea (vd - 02), (x1 - ,..... ( 09)
81 times
(x) - o2)..... (sa - (oaa-
times
where, prod(.) is defined in Lemma 34 Here, prod [=]] has at most d + |s| S d + [8] many inputs. By Lemma 34 prod a [s]) can be implemented by ReLU network with ((prod((+)))) W(prod!/tlal) S cym. Thus, L(fa.)) S cym+22 and W(fe.) S cdm+ <
in
cam + 8d + 4k. With this fe... we observe that,
(d + 181)3
[(,((x)) ( <(xx - 0²) (x- 10-00)
22m+2 Vo E M.
(16)
Finally, let, f(x) = Eieri E1n (()) Clearly, C(fe,a) S eam + and w(f S Ad (cam + 8d + 4k). This implies that,
[f(x)) f(x)) S
Σ
Σ lai fi)))aa(a))) -(x 0¹)
sezt: a 0' S2e |8|[|8
2d
|00.0|
fascos,a -c.,6(x - p((((a)) (a g
|+|
(d + |
22
We thus get that if x E M,
(d 18))
[f(x) f(x))f(x)) {x) - f(x)] + 1f(x))
f(x)] < 24+3.3 + 22m+2-d
(17)
We choose e
イ )
1/3 and m [oogo (d+R))0C)
+ Then,
7
|l - flli,ce (Mr) Sn.
We note that f has [Zt] S (dN.(M) S 6dc- many networks with depth cym +
and number of weights [8] (cym + Sd + +118)).
Thus, L(f) I cym + and w(f) s
(6 (cym + 8d 4[88). we thus get,
<()) cam + +4 ca (i [[oos3
(d (a+ (8])8C8)
] + .d-11 4 ca logog (
20

---

Published as a conference paper at ICLR 2024
where C₁ is function of 6, [B] and d. Similarly,
W(F) Sc
(61,3)) (cam (0
Sd + +181))
#/3
(6(3))² c3 (1og2
(d+ (d+ (3)+ + d d1- + sd + 4181)
2d+2+2
Seg log(l//))))
Taking a = C4 V co gives the result.
C.3.2 PROOF LEMMA 19
Lemma 19. Suppose assumptions AD hold and let, diss(:..) Wi(--) or (- Also, let 8 du- Then, we can find positive constants co, og and R. that might depend on d, e, and E, such that if0 < Ee 6o and 9 = RN(W gr Log R) and & RN(We: Le, R), with
Le S ag log(L/Eg), Lg I ag log(L/ag), We S a log(L/Ee) and W, S a0eg" t/a, log(1/Eg)
then, Amiss S Ey CE" lv'e
Proof. We first prove the result for the Wasserstein-1 1 distance and then for the MMDxx-merri.
Case 1: diss(..-) = ((((s) For any and E E, we observe that,
V, G, F) SV(u, G, F. (V,,,, F) - V,, F))
s|lcs, B(-)) cl. Go B(-))ll (20) + (FgM,, W1 -W((,,)
I E- El (1 + (14Ep Expt)
SIG E G Elllac (s)) (supp(()) + | - EEl (supp(u))
S|G E G Ell1... (supp(n)) ) + |1 o E G El (supp(H)) + ||E (spp(i())))
(supp(a))
SIG - G'IL... (1a.119) + | - E 1 (s)) + I E I (supp(a))
ag
We take 9 (Rog()1 approximating in each of the individual coordinate wise output of the vector-valued functions G and É and stacking them parallelly. This makes,
L//a 1og(1/en)) (//))) and & = RW (log(1//////// te t/ log(1 (og(1)))) by
V(u, G, + E +ce tee +c
Case 2: diss(-.-) MMD Before we begin, we note that,
IMM (Ea v) MMD3 (EqH,n) v)
XX (EE)), E(X') - Ex (B((), E(X))
22 X(E(X),
((
<2Tk E Ellla (supp(u)) + 1 -E (supp(()))
=47 |E E Eillanc (supp(μ))
(18)
For any G and E E, we observe that.
V(u v, G,
-V G, B) +V -) G,
=I|c(, G B(-)) cl. Go E(-)) (())))lLo((((p((())
(Supo(H)) + MMD (EHH, - (MDD<(EEA v)
< G E- G Blllin(()) 4Th ArxlEE E (llEx((upp(()))
(19)
SIG o 8-G- - Ell1 1111. (xmpp())) (m)) + E -Elleeu
S|G E - G Elliase (((pp(c((mpp(r)) (supp(n)) + 11ā E - Ô (s
(supp(u)) + ||
(supp(n))
G| - 11111_11100000 (10.1]1) + |I 1 (supp(e)) + |I E (( (supp(a))
21

---

Published as a conference paper at ICLR 2024
fxx
f(x) + y
22
h(x, y)
0.25
id
y
f(x)
Figure 3: A representation the network h(;,)) .). The magenta lines represent d' weights of value 1. Similarly, cyan lines represent d' weights of value -. Finally, the orange and teal lines represent d' weights (each) with values -0.25 and -0.25, respectively. The identity map takes 2d' L(f) many weights (see remark 15 (iv) of Nakada & Imaizumi (2020)). The magenta, cyan, orange and teal connections take 6d" many weights. All activations are taken to be ReLU, except the output of the yellow nodes, whose activation o(x) x².
In the above calculations, we have used 18 to arrive at 19 As before, we take 9 = (RV((og(1/eg))e -t/os log(1/e,)) and & R.N (log(L/ee) -a/Be log(1/ee)) by approximating in each of the individual coordinate wise output of the vector-valued functions G and F. and stacking them parallelly. This makes,
G, Sc @aAl +ee cg caAA1
C.4 PROOFS FROM SECTION B.2
C.4.1 PROOF LEMMA 20
Lemma 20.
Suppose that n 2 and F are a class neural network with depth at most I, and number of weights at most W. Furthermore, the activation functions piece-wise polynomial activation with the number of pieces and degree at most k E N. Then, there is constant (that might depend on d and d' ,, such that, i Z 0(W + 6d' 2d' L)(L 3) (log(W* + 6dd + 2d' L) L 3).
nd
log.N (o; ((e,,
.oo) (W 6d' + 2d' L) 3) (log(W + 6d' + L) + L + log
where d' the output dimension of the networks in F.
Proof. We let, h(2,1) v) T f(x) and let H =
E FJ. Also, let, T {(h(X, ex) (e))ee() E ad E H). Here e, denotes the b-th unit vector. By construction of T, it is clear that, (e; lxo) Tox)) We observe that,
h(,, y) = (1le + f(x)11 11y f(x)113
Clearly, can be implemented by a network with L(h) = L()) + and W(h) = W(f) + 6d' + 2d' L(f) (see Fig. for such construction). Thus, from Theorem 12.9 of Anthony & Bartlett (2099) (see Lemma 37), we note that, if n 2 Pdim(H).
2end' Pdim(H)
N(E: <
ePdim(H)
with,
Pdim(H) & W(h) W(h) (1))
22

---

Published as a conference paper at ICLR 2024
from applying Theorem 6 of Bartlett al. (2019)
(see Lemma 38
This implies that,
2end'
log.N H, (x)
<Pdim(H) log
<Pdim(H)
nd'
<Pdim(H) log
S (W(())C())log ((h) log nd'
Plugging in the values of W() and [hh yields the result.
C.4.2 PROOF COROLLARY 21
Corollary 21. Suppose that W(E) < We, L(E) Les W(S) S W and L(9) S Lg. with Le, Ly 2 3. We 2 6l 2LLe and W 9 6d 2dLg. Then, there is a constant εr, such that if n 2 (W + WL + Lg) (log(We + Wg) + Le + Lg),
log.N (e; Xxm 1o0) SWeLe Llog We + Le) log
nl
log (e (90 S(W. + Wg)(Le + Lg) (log(W, + W2) + Le - Lg) log
nd
Proof. The proof easily follows from applying Lemma 20 and noting the sizes of the networks in and 9 &
L
C.4.3 PROOF OF LEMMA 22
Lemma 22. Suppose R()) S. and F (f(x) ca, E(x)) G E 9, E E}. Fur- thermore, let, ((E) < Le. W(S) < W, and L(9) S Lg with Les bg 2 3, W. 2 66 + 28Le
and Wg > 6d + 2dbg. Then, there constant &z. such that Lg) (log(We + Wg) Le Lg)
& (Le +
Eli pl1s5 S n 1/222((W W2) + Lgg (log(We + Wg) + L. + I.g) log(nd)) 1/2
Proof. Let R(9) < B, for some B > 0 and let B. suPoSe5B [c(x)) From Dudley's chaining Wainwright 2019
Theorem 5.22),
Be/2
BlAn Allss SEx... inf oSA5B./2
8
v log F boo)de
(20)
Vn
Let For any G and E, we can find w E C(e; (9 o E) (oo), bxo),
such that, |I(G E) E) - vlllo I c. This implies that [|(G (X),, - villo I c, for all i E [n]. Let,
A vi),...,, un)) UE E (808)) }. Thus, For any GE EEE,
max |c(X,, Go E(X.)) c(X,, vx)l ST. max Isisn
0. 0iloo T.C.
Isi
Thus, A constitutes a T.e-cover of I Ix.... Hence,
Tand
(Logg) (ee Fxx S N(E/To (GoE) lao (We+ LLg (log(We + W,,) + L. + Lg) log
Here, the last inequality follows from Lemma 20 Plugging the above bound in equation 20 get,
/
Be/2
E An - 1lls SExI. inf
i
Nle loo
Vn.
23

---

Published as a conference paper at ICLR 2024
(We + (he + lzg) log(W. W. + w) fde Vlo8 de
BB
/ (Tand
(W. + Wo)(Lo Lg) (log(W, + W₂) + Le Lgg log(nd)
n
C.4.4 PROOF OF LEMMA 2
Lemma 23. Let iin E ōx, and & (T. W.). Then,
[Wi v) 1, (E (0:is(nn111 (n-2/e V -1/2 11/21ogg) +
W. (log We + Le) log(ne)
sup FEE
n
Furthermore,
sup [Wi - (n- vn 11/2 vn + (m 1/e
im-1/e v m 11/2 log m
Bee
W. W.Ln W. + La) log(ne)
+
n
Proof. Note that if diss(:,-) -) = -W((, then
sup BEE
disss Ey diss(Egp,,)) sup [Wi v) -W1(E, sup W₂ (EgEnnn Esp) BEe
EEE
We note that,
sup W (Egh, Eppr) = sup sup BEE
E (B()
EEe f:llfliss
We take Fi = (f 00, 1
I 1 = (VL). By the result of Kolmogorov &
Tikhomirov (991) (Lemma 36 we note that log Feg,Nee;,,,ee S =- Furthermore, if we take F2 = E, we observe that, Nog Exx,, fxo) S W. W.I.elog We + T.e) log (=t) from Lemma 21
From Dudley's 's chaining, we observe the following:
E sup W(EgA, Eqp) EEE
=E sup sup BEE f:11/11n21
E Exx,, (xap.xxa((B(X)) f(E(8))
=E| ft pll,,
VoggN o (o0)dc
< inf 0.8 R
6 +
Vn
<
inf 0. Rt
8 +
| log.N
(e/2 + No & Ro0 )oo)de de
VT
Vi [
inf
8 +
(11oNN(e/2:Fi,,bb))
V (e/2;
(e/2, E|xra los) de
0585R.
inf 0S85R.
8
VlogN (i) + Vn Saa
R.
ViogN & Eixmm loo ) de
Vn
R
Vn (''
2enl de
inf 0SB5R.
+
E -1/22
WeLe W. + Le) log
vn J8
W. WaLe W. + La) log(ne)
inf 0S65R.
s+ V
-1/2de +
24

---

Published as a conference paper at ICLR 2024
+ vn Js (mm Rh
(W L. log We log n + +V
inf 0505R. R.
c1/22e
n
n 1/f
118 Vn 1/2 logn) +
W. Wobellog We Le) log(ne)
n
C.4.5 PROOF OF LEMMA 24
Lemma 24. Suppose assumption A2 holds and let, ((E) S Le and L(9) S Lig with Le 2 3.
W. 2 28(3 + Le). Also suppose that, + fo E Hix 1|0 1}, then,
We We We Le) log(ne)
x V
n
Proof.
R(( E), X1m)
1
Σ aff(f((i))
a
sup
7
FEB
1
o (I(((()))
sup
n
JER
n o ((
sup
n
fEE
sup JEE
o(X(((()))))
n
Exx
1
E
sup
sup fEe
oi (I( x(f(())), K((r)))
DEC (
(1
Hx
1
n
n
sup
sup fEE
Σ
o, K(Ux
[x((((;),,) - K(vs, I1mx
11
fox) DEC (1E
n
Ex
i=1
1
Σ a;KK(uu,) -)
<
E
max
+ +272
(21)
DEC
(E
(x))
HHx
For any C (c, let, Yo = | o1,( and K. ((K(us, vz)) E pnn
1/2 2rl. By Theorem 2.1 of Rudelson & It easy observe that, Y? Ko and Y, || Vershynin 2013), we note that,
et2 2 exp
{
dt
TP [ //l
K Ils
>>
< 2 exp
{
|
|
for some universal constant
0. From Berron-Frobenius theorem, we note that,
K.ll || <
max S
K(vi, uy) & B
Hence,
ct2
P
-||K3/21 >t) s 2exp
n.B
25

---

Published as a conference paper at ICLR 2024
This implies that,
cxa
exp(X(I|k)/ o11 || S exp
for some absolute constant d', by applying Proposition 2.3.2 Vershynin 2018 From Theorem 2.5 of Boucheron et al. (013), observe that,
( [| | (lus) S VnlogN (s, ( Gixxmn
max vEC
Ximn tx)
From equation 21 we observe that,
R(o &, X131
max
Σ o,K((us.))
+ 12
n
fx)) (
vEC
i=
Fxx
E
max
111/2//00 20 -11K7// 1 + || (1Hs) + C
(
(1|Kg 1/2 1/2 P0l - -IIK! / llHs)
<
max
11
wEc(
fize
1
|| || + V2TRE
max
DEC ( (1,E111n Axo)
log.N
c, & loo
B
+
+ Ve
Vi
We Le log We log nl)
S
+ Vi
(22)
We take L. (log W. + I..) (og(
makes R(( Xin) S
W. Le (log W. + Le log(nE)
C.4.6 PROOF LEMMA 25
To prove Lemma we need some supporting results, which we sequentially state and prove as follows. The first such result, i.c. Lemma ensures that the kernel function is Lipschitz when it is considered as map from a real vector space to the corresponding Hilbert space.
ennsuress
Lemma 27. Suppose assumption A2 holds. Then, [[]((z,)) K(y, >lf S 2Txl|I v112.
Proof. We observe the following:
[[((,,)) - K(v. Ia. =K(x, + KK(yy 2K(x,
=(K(a,, - K(x,, v)) + (K((,, v) K(x v))
22Th
-yl12- 1
Lemma 28 states that the difference between the estimated and actual squared MMD-dissimilarit scales as (l/nn) for estimates (5) and O(1/n + 1/m) for estimates (6).
Lemma 28. Suppose assumption holds. Then, for any E.
(a)
x (Fgfin v) (MMD2 v) < 2B²
(b) MMDx (Fgfin Pm.) .MD2 (Egún, v) < 2B2 ( +))
26

---

Published as a conference paper at ICLR 2024
Proof. We note that,
2 MMD (BAAn, -MMD' (MDD(EERnss. 1)
n
X(E(X)),
Σ
X(E(X)),
n(n 1) ifj
n12
A,==1
X(F(X,), F(()))
F((.))
X(E(X,)) F(X.))
n² n2 1) if1
n
Thus,
MMDx (Erfn, MMD? MMM v) S nn(nn 1) nnn 1)B² nB² 2B²
1
+ n²
n
Part (b) follows similarly.
We also note that the MMDx metric is bounded under A2 as seen in Lemma 29 Lemma 29. Under assumption A2 MMDxx(P, (P,Q) Q) - 2B, for any two distributions P and Q.
Proof. 1f(x) = (K(x, f s [[](,, MIn suP (s pdPP (dQ) S 2B
B. This implies that MMDx (P,Q)
Lemma 30. Suppose assumption A2 holds. Then,
(a) Esup MMDxx v) MMDx((EMMM..
S
W. W.Loolog W.+ L. log(ne)
(b) E supEec
MMDDy(Fsfinn Pm) MMIDs((F91.1))
We Welaallog W. +L+ log(ne)
a
mm
Proof. Proof of Part (a)
We begin by noting that,
E sup MMDx((E2. v) MMDx (E FEE
< sup FEE
MMDx v) MMD (EgH, v\1 E sup FEE
MMD (EgPn, v)
MMDx (Ep w)
I
< sup MMDx EEH) + 2B BEE
(23)
(f (((E(())ddpuao)))
((E(=))du(o) ((())))))))(((( + +BB +BBV
-E sup sup BEE gE#
<2R( a M, + 2B 2B
(24)
Weog We + Le) log(ne)
(25)
In the above calculations, 23 follows from Lemma 28
Inequality
24
follows from symmetriza-
tion, whereas, (25) follows from Lemma 24
Proof of Part (b) Similar to the calculations in part (a), we note the following:
E sup
MMD pm)) MMMx((EE,, v)
< sup EEE
MMD (Fggin P.)) MMM (F/ v) + E sup BEE
MMD (MDip(Fpnn Um)
MMDx (Fegfin v)
<B sup MMD,(E,;n,, E.P) + (P.. v) 2B + m
EEE
27

---

Published as a conference paper at ICLR 2024
1
1
<2R( o +) 2B
n
m
WoLe (log We + Le) log(n))
/
n
m
We now ready prove Lemma 25
For of readability, restate the Lemma as follows.
Lemma 25. Under assumption A2 the following holds:
(a) I sup MM v) MMD33(Eg1)) w) x
W. I. log log(nf)
EEE
(b) E sup EEC
2 MMDg (MMDg(PeBnn:.e (Fylnn (m) - ( w)
Wel,ellog We Li (ng(
m
Proof. Proof of part (a) We begin by noting the following:
E sup REE
MMD (EgAm, (E
2MMDxx (EEH,, MMDx((EgRm. v) MMD + (MMD:x(EsRnn) MMD (EEp, 2
E sup BEE
<2BE sup REE
MMDx((Egmm
(E,..) + E sup RE?
MMDx(EE/n: (FD)((F w)
(26)
WW L. (log We logn
(27)
n
Inequality 26 follows from applying Lemma 29 Proof of part (b) Similarly,
whereas,
27
is consequence of Lemma 30
E sup EEE
MMD (EgAns (MDDs(EE Pm)) MMD3 (EgU,
E sup REE
2MMD (BEH, v) MMDx (Egfne Pm) - MMD (EAH,() + (MMDx MAMDDx(E:Rm... Pm) MMDxx(Ess..P
<2BE sup FEE
MMDx (Egên, Pm)
(E w)
E sup REE
MMDx MMDx(E;fmn (EşAin Dm) MMDx v)
(W. Ta (log Wa The logn
n
m
C.5 PROOFS FROM SECTION 5.2
In this section, we prove the main result of this paper, i.e. Theorem g
C.6 PROOFS FROM SECTION 5.5
To begin our analysis, we first show the following:
Theorem 31. Under assumptions, A
V(n, Gn. P.) 0, almost surely.
Proof. For simplicity, consider the estimator (5). A similar proof holds for estimator ( Con- sider the oracle incquality (7). We only consider the case, when, diss = W, the case when, diss MMD can be proved similarly.
28

---

Published as a conference paper at ICLR 2024
We note that F is bounded function class, with bound Be. Thus, simple application of the bounded difference inequality yields that with probability at least 1 - 8/2.
log(1/8) n
| Mlls s Bllá, Mlls 01
for some positive constant 1 The fourth term in 5 can be written as: (Eg v) W (Fejt,
sup REE
Suppose that jl, denotes the empirical distribution on (X1,... Xi-1, X/,... Xa). Then replacing fin with V2 yields an error at most,
1 - S(E(X)) 1 n
sup [W] (Eginn Wi (Ba v) FEE
sup EER
WiEE Bgi()) S sup sup REE f:ll
since by construction, E's are chosen from bounded ReLU functions. Again by simple application of bounded difference inequality, get,
log(1/0)
log L/0)
2λ sup [Wi (Eghm, v) W (Egu, 1 S 2XE sup (Wi(en (Ig v) + O2 BEE with probability at least 8/2. Hence, by union bound, with probability at least
BEE
2| - Hller + 2A sup BEE
[Wi(EAAn, v) - (2
log(1 1/8)
<2E A115 + 2XE sup [W1 v) Wi v) + 0s
BEE
for some absolute constant 03. Since, all other terms in 7 are bounded independent of the random sample, with probability at least -,,
V(, u. &. v, G, + 0s1 1og(1/8)
c) S "5. this implies that Enzi ((]V(,, v, G, B) - EV(H v. G, c) < cc. A simple application the first Borel- Cantelli Lemma yields (see Proposition 5.7 of Karr 1993) that this implies that [V v, G, B) EV(u, v, G, E)1 + 0, almost surely. Since, lim,
From the above, P(IV(H,,,GEE)
EV G, E)1
EV(u, v, G, É) = O, the result follows.
C.6.1 PROOF PROPOSITION 12
Proposition 12. Suppose that assumptions W2(+)) and MMD3x(-) (-))) and the estimates and Egja S almost surely.
3 hold. Then, for both the dissimilarity measures
Proof. Let diss W,. From Theorem 31 is clear that, W, W, v) + almost surely. Since convergence in Wasserstein distance characterizes convergence distribution, Ez 4 v, almost surely.
When, diss MMD we can similarly say that (BaH,,) O, almost surely. From Theorem 3.2 (b) of Schreuder et al. (2021). we conclude that Ezgu 4 almost surely.
L
C.6.2 PROOF OF PROPOSITION 13
Proposition 13. Suppose that assumptions hold. Then, for both the dissimilarity measures Wi(,)) and (M)))(;))) and the estimates and ( |[dd(.) G F(.)1laa0)) a.8. 0.
Proof. The proof follows from observing that 0 < |lid(.) G E(-) S Vuu,, G) and applying Theorem 31
29

---

Published as a conference paper at ICLR 2024
C.6.3 PROOF OF THEOREM 14
Theorem 14. Suppose that assumptions A hold and TV (EE,, O, almost surely. Then,
G.V 4 ps almost surely.
Proof. We begin by observing that,
W (G SWi(C (G. + WG E)
(28)
We first note that
TV (G E)sn)=
sup (EB(Rd) [(G ((C (B)
In( - (FHH)((
sup BEB(R")
sup BEB(R()
(v(B) (Br))(B)
(29)
=V, Eyux) - 0, almost surely.
Here 29 follows from the fact that (B) B E R²) _ TR',, since G's are measurable. Thus, TV(C,, (G E)au) + O, almost surely. Since convergence in TV implies convergence in distri- bution, this implies that W1 (Grr, (G o E)(p) - almost surely.
We also note that, from Proposition 13 Ex~xll |X G E(X) + O, almost surely. This implies
that ||X - G [XXII Eg 0, almost surely, which further implies that G oo E(X) 4 X, almost surely. Hence, WiGG F)),, ()) + 0, almost surely. Plugging these in 28 gives us the desired result.
Theorem 15. Suppose that assumptions A A hold and let the family of estimated generators (G") JnEN be uniformly equicontinuous, almost surely. Then, Gyv S almost surely.
Proof. We note that from the proof of Theorem 14, equation (8) holds and W1 (G )3H4 p)) + O, almost surely. We fix an in the sample space, for which, Wi WI o E E p4) - 0 and (Em),u 4 v. Here we use the subscript w to show that &" and En might depend on w. Clearly, the set of all w's, for which this convergence holds, has probability
By Skorohod's 's theorem, we note that we can find sequence of random variables (Yn hnE and Z, such that Y, follows the distribution Ég μ and Z v, such that Y, -6 Z. Since {G neN uniformly equicontinuous, for any 0, can find > such that if [y, < 6, Thus, C% (z) a.e, Since this implies that (Y,) (Z) 4 it easy to see that, (I GB (2)) - O. Now, since, Wi (G CZ
(v.) - (>)
W ((C)),, (Gm ET), we conclude that W, (V())))) (G o Er)au) - 0, as a + 0o. Thus, with probability one, the RHS of 28 surely.
goes to as n - 0c. Hence, Wi - 0, almost
C.6.4 PROOF OF COROLLARY 16
Corollary 16. Let diss(...) = W, (.. :) and suppose that the assumptions of Theorem 8 are satisfied
and & > dy- Also let supnen ||ā" I I supm, [| Lip S L, almost surely, for some L > O.
Wi(U,, p) S (p, G, for both estimators and 6
Proof. Denoting & as either of the estimators and 66) it is easy to see that,
W₁ (G(Guu,)) SW, (Gy,, (G E)gu) + wi o E)gu, u)
STW, Bap) W (G A)p
30

---

Published as a conference paper at ICLR 2024
SWi( + / B() x0(ddu(x))
D SUPPORTING RESULTS FOR APPROXIMATION GUARANTEES
Lemma 32. (Proposition of Yarotsky (017)) The function f(x) = x² on the segment [0, can be approximated with any ervor by a ReLU network, sqm(),, such that,
1. [(sqm), W(sqm) cim.
2. sqm (smm) g
)² for all k 0,0,,...... 1,..,
3. |sqm x² 1l ((0.1) 22
Lemma 33. sqm (.) be taken as Lemma 32 then, ||sqm
xx2 llaca S 2m-1-
Proof. We begin by noting that, sqm (x)
=
(k++1)² 2
A² 2
(x
2m
+ 2m
whenever, æ E
K 2
). Thus, on & )),
(I: + 1)2
122
1
|sqm.
x² 1bae =I|sqm
x Ilo ((2tn ( 2111)
2x
2m
2
( (ggm
22m+2
2
2m-1
This implies that, ||sqm x.? llace 2m-1-
Lemma 34. Let M > O, then can find a ReLU network prod such that,
1. ((prod ((prod( S c2m,, for some absolute constant Cz-
2. [pro ry (M.MM
M
22
Clearly, prod (1 0, ay O. We note that, ((prod S Cn + 1 < 02ml and ((prod S 201m 2 S C2m,, for some absolute constant C2. Clearly,
Proof. Let prod! (2) (z, v) M²
$4m
x+-1 21V
19m
[-=y|
2M
M
||rodd -yyll (IMMMMMMMMM 22M x [L(001111) S
22m+1
Lemma 35. For any m 2 3, we can construct a ReLU network prod any 21, ......, Fa [-1, [prodd (II,..., va)
R2d - R. such that for d3
I xa xalli ([-1..))
I
Z.
Proof. Let M prod (2) (x) Ix
1 and d
2 2. We define prod ( Ix)
3. Clearly W(prod (prodd (d)
I c3dm,
for some absolute constant c3.
We also note that, |prod m
(d) (x1...., Ta)l
S
M
+
2
aaa prodd (x). ,.l:...,KA, xa-1)l
- + M (pprod(d-1)) (2 (x1, Fd-1)]
M
M
M
23mFT + Md < ZT + (d - 2 = d + ZT < d - 1. From induction, it is easy to see that, prod!!! (k)
Má
M2
m <
Taking M = d 1, we get that,
(pro (æi,..., Fz) - 3ı x Il ([-1,1]
-|lpood (prod (ooodddd)(()),......
(I1, Ix- xr) I1 ... L lal ([-1,1]²)
M
pro (2). (21...,, x8-1) - 21 x ((11)))) + 22m+2
31

---

Published as a conference paper at ICLR 2024
dM2
2
d
2mm+2
E SUPPORTING RESULTS FROM THE LITERATURE
This section lists some of the supporting results from the literature, used in the paper.
Lemma 36. (Kolmogorov & Tikhomirov 1961) The e-covering number of of ([0, 1]4 R) can be bounded as,
log ((e) (10, 11", 11 E d/18
Lemma 37. (Theorem 12.2 of Anthony & Bartlet (2009) Assume for all f E F, ll S M. Denote the pseudo-dimension of as Pdlm(FF), then for 2 Pdim(F), we have for any and any X X X
Pdiml
MeMn
Ne, F2, koo) S
ePdim(FF)
Lemma 38. (Theorem 6 of Bartlett et al. (2019) Consider the function class computed by a feed- forward neural network architecture with W many weight parameters and U many computation units arranged functions with p 1 pieces and degrees more than d, and the output unit has the identity function as its activation function. Then the VC-dimension and pseudo- dimension are upper-bouncee as
layers. Suppose that all non-output units have
activation
VCdim(F), (Cdmm())) S SC- LW Lolog(pU) + I.2W log d.
32


Reviews:
[{"review_id": "NBqAjYm31V", "reviewer": "Reviewer_oqXa", "summary": "The paper introduces a comprehensive framework for analyzing error rates in learning unknown distributions through Wasserstein Autoencoders (WAEs), particularly in scenarios where data points exhibit an intrinsic low-dimensional structure within a high-dimensional feature space. By characterizing this dimensionality using the Minkowski dimension of the target distribution's support, the paper establishes an oracle inequality that effectively balances model-misspecification and stochastic errors, offering insights into the trade-offs achievable through appropriate network architectures. Furthermore, the framework allows for a thorough examination of the accuracy of encoding and decoding guarantees, as well as the approximation of the target distribution by the generated push-forward measure. \nWhile the paper offers valuable insights into the theoretical underpinnings of WAEs, it acknowledges the challenges associated with accurately estimating the complete error due to the complexities of the optimization process. Notably, the paper emphasizes the need for further analysis, especially in contexts involving non-deterministic network outputs and Gaussian-based latent distributions, which are commonly employed in practical applications.", "questions": "No question", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper demonstrates several strengths, particularly in its provision of theoretical analyses and implications regarding the selection of network sizes for encoders and decoders based on the number of training data samples. Notably, the theoretical results, particularly Theorem 8, provide valuable insights that ensure encoding and decoding guarantees, highlighting the paper's ability to establish a close relationship between the encoded distribution and the target latent distribution. Furthermore, the paper emphasizes the effectiveness of the generator in accurately mapping the encoded points back to their original positions, showcasing its robust understanding of the intricacies involved in data transformation and representation within the context of the study.", "weaknesses": "The paper exhibits certain weaknesses that should be addressed to strengthen its overall contribution. Firstly, while the paper presents intriguing theoretical results, the absence of an experimental demonstration, even with synthetic datasets, limits its practical applicability and hinders the validation of the theoretical findings in real-world scenarios. The lack of empirical evidence to support the theoretical claims diminishes the paper's credibility and inhibits a comprehensive understanding of the practical implications of the proposed concepts. Additionally, the paper falls short in elucidating how the theoretical results can be practically employed to guide the selection or design of encoder/decoder networks, particularly for enhancing the generation of sharper and more realistic images within the context of Wasserstein Autoencoders (WAEs). The absence of clear guidelines or methodologies for leveraging the theoretical findings to improve the image generation process highlights a critical gap in the paper's applicability and its potential impact on practical applications within the field. Addressing these limitations would significantly enhance the paper's overall credibility and ensure its relevance and practical significance within the research domain.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "fy5fWYZvgg", "reviewer": "Reviewer_GHGf", "summary": "The paper provides a statistical analysis for Wasserstein Autoencoder (WAE) method. Specifically, the paper gives an upper bound for the excess risk for the empirical estimator of the encoder and decoder when both are approximated by neural networks. Under certain assumptions, the proposed method obtains an approximate of the optimal en/decoders, which is shown to have a converging excess risk. The analysis is applied to both Wasserstein and MMD dissimilarities. Furthermore, the adequate latent dimension is used in the bounds, showing that lower dimensional data complies with the corresponding rate.", "questions": "Please see above (section Weaknesses) for details.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is overall well written and presented, and the the ideas are original to the knowledge of the reviewer. The discussion of all results seem plenty and extensive. Some strengths:\n1. The idea of analyzing WAE statistically seems to be an interesting question, as most of such study seem to be on other generative models. The paper provides solid convergence guarantees, which seems expected but still crucial. \n2. The paper provides thorough discussion on the error and convergence of the model, including both sample complexity and asymptotics. The error bound accounts for sample size, neural network size, optimization oracle, and dimensionality dependence, which is rather complete, as these includes almost all aspects of concern in practice. The limitations are also adequately addressed.", "weaknesses": "1. Though the paper provides the analysis all the way to containing both sample complexity and misspecification, the single question of sample complexity seems to be an interesting question on its own, i.e. population v.s. empirical over the same Holder class, not neural networks. In this setting, optimization is out of the picture, thus questions such as the convergence rate of $\\|id - G\\circ E\\|$ or $\\|\\hat{G}-G\\|$ can be asked without ambiguity. The reviewer understands that this is additional work, but encourages the authors to provide a discussion, rather than stuffing all ingredients all at once. This could possibly be related to the tightness (minimaxity) of the proposed bound.\n\n2. In Remark 11, the construction of $E^*$ does not seem correct, as repeating $E_1$ several times will only result in a graph supported on the diagonal, thus $E^{*}_\\sharp\\mu$ is not the uniform distribution over the higher dimensional cube. Similarly, the next claim in the remark over the use of $\\nu$ with independent marginals seems unjustified.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "zbtspOEFJi", "reviewer": "Reviewer_JGBa", "summary": "The paper proves statistical sample complexity for Wasserstein autoencoders on low-dimensional data. The provided sample complexity depends on the data intrinsic dimension, indicating that autoencoders are adaptive to the data intrinsic structures. The analysis also includes MMD divergence. This study is relatively new in the literature, as it is parallel to the GANs analyses and compared to \"Deep nonparametric estimation of intrinsic data structures by chart autoencoders: Generalization error and robustness\", this paper includes the regularization using Wasserstein distance or MMD.", "questions": "See weakness above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is quite theoretical, but the presentation is relatively easy to follow. The error decomposition in Lemma 7 is helpful in understanding the rate in later sections. As far as I can tell, the theoretical claims are correct.\n\nThe paper also provides some numerical results suggesting that the performance of autoencoders depends on data intrinsic dimension. This is good to have as a motivation for the study.", "weaknesses": "The theoretical analysis is based on a strong assumption that the low-dimensional data has a global parameterization. This can limit the application of the results.\n\nThe analysis in the paper appears to be standard, and the majority of the idea is adapted from existing research on GANs. However, I would like to emphasize that putting all the details together is not a straightforward task. Moreover, the analysis to MMD is relatively not very common in existing literature. Therefore, I am not criticizing the contribution of the paper, but just pointing out that the technical novelty might not be significant.\n\nI would suggest writing a corollary in Remark 11.\n\nIn Section 4, it might be helpful to provide some examples, such as a smooth $d$-dimensional manifold has an upper Minkwoski dimension bounded by $d$. More discussions can be found in \"Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "xQYVCREpL8", "reviewer": "Reviewer_e5jX", "summary": "The paper summarizes the statistical error bounds for Wasserstein Autoencoders (WAE). Assuming the existence of the true smooth autoencoder model and (intrinsic) low-dimensionality of data distribution, this paper derives the order of the errors of the estimated model with respect to sample number $n$ and other assumed quantities. The resulting corollaries are also given.", "questions": "Can you show a numerical experiment that supports up the asymptotical rate of the presented error bound? Figure 1 may be close to this, but the comparison with $O(n^\\alpha)$ or quantity of the whole objective function should be presented.\n\nAlso, is the theorem applicable for WAE-GAN?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The asymptotical error bounds for the estimated WAE is clearly presented with thorough proofs. This guarantess the asymptotical convergence of the WAE model if the target distribution and the true encoder/decoder are well-regularized.", "weaknesses": "The assumption of the existence of true generator and the true encoder seems to be a strong assumption. Practically, the low-dimensional prior distribution is chosen to be Gaussian, and this distribution may not be able to represent the intrinsic structure of the data distribution.\n\nAlso, it is common to use GAN loss as the dissimilarity measure for the penalty in the objective function, but it seems that GAN loss is not considered.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)