Statistical Regeneration Guarantees of the Wasserstein Autoencoder with Latent Space Consistency
Year: 2021

Abstract:
The introduction of Variational Autoencoders (VAE) has been marked as a breakthrough in the history of representation learning models. Besides having several accolades of its own, VAE has successfully flagged off a series of inventions in the form of its immediate successors. Wasserstein Autoencoder (WAE), being an heir to that realm carries with it all of the goodness and heightened generative promises, matching even the generative adversarial networks (GANs). Needless to say, recent years have witnessed a remarkable resurgence in statistical analyses of the GANs. Similar examinations for Autoencoders, however, despite their diverse applicability and notable empirical performance, remain largely absent. To close this gap, in this paper, we investigate the statistical properties of WAE. Firstly, we provide statistical guarantees that WAE achieves the target distribution in the latent space, utilizing the Vapnik–Chervonenkis (VC) theory. The main result, consequently ensures the regeneration of the input distribution, harnessing the potential offered by Optimal Transport of measures under the Wasserstein metric. This study, in turn, hints at the class of distributions WAE can reconstruct after suffering a compression in the form of a latent law.

heading: 1 Introduction
text: Unsupervised data generation has been a time-hallowed problem in machine learning theory. Though not its strongest suit, Variational Autoencoders (VAE) [1] have been implemented for generative purposes to a great extent. Once emerged as a crucial unsupervised method for representation learning, its poor performances in this particular area somewhat depreciate its appeal. On the contrary, generative adversarial networks (GANs) [2] have proven to be superior when it comes to the quality of the generated image samples. The theoretical elegance of the adversarial training method can be duly credited for this achievement. In an attempt to adopt this merit, such ‘adversarial loss’ functions were incorporated into VAE objectives [3, 4]. The Wasserstein metric, also being used in GANs [5] previously, was an inevitable choice, since it brings along the beckoning of Transportation Theory. Using the same to measure the reconstruction loss in a VAE, Wasserstein Autoencoder (WAE) [6] was conceived. By approaching generative modeling from an Optimal Transport (OT) point of view, it not only achieved remarkable reconstruction standards but also strengthened the theoretical backbone.
An appropriate WAE framework consists of two components, namely an encoder (E) and a decoder (D), which are represented by neural networks in practice. Samples from an input distribution (PX) are fed into the encoder, which aims at resulting in a target law (PZ) in the latent space (Z). The decoder deals with the reconstruction of the original distribution from this ‘encoded’ signal. Mathematically, the objective of WAEs is to minimize L = R(D,E) + Ω(E) over the
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
set of probabilistic encoders E. Here, R() ensures the reconstruction of samples put in whereas, Ω() ensures the attainment of the latent distribution. Needless to say, R() is represented by the Wasserstein discrepancy.
As the name suggests, our primary interest lies in investigating whether a suitably characterized WAE can learn a distribution, which represents its latent behaviour, without losing the memory of the initial signal it was fed. When it comes to the question of memorizing the input distribution in the form of reconstruction, theoretical guarantees in the context of GANs, have been provided rigorously. In the absence of a flexible discriminator, WAEs need more care and closer observation. Moreover, the concurrent task of sculpting a desired latent distribution adds nuances to its mechanism. Most of the existing literature on deep generative models, under adversarial loss, misses out on this very point. Against such a backdrop, this first of its kind study substantiates the simultaneous performances of WAE, from a theoretical viewpoint.
Our analysis starts with a special family of WAEs, namely f -Wasserstein Autoencoders (f -WAE) [7], which arises due to the specific choice of Ω() as f -divergences (1). We follow a non-parametric approach in defining both the networks involved and the distributions under consideration. The transformations induced by the encoder and the decoder are conceived as measurable functions between spaces. The nature of an ‘ideal’ encoder in our language, is a network that preserves information. Whereas, the decoder is characterized by a map that propagates the information retained, precisely. Our statistical assumptions on the same reflect these very ideas. As a result, the two concurrent objectives of f -WAE boil down to non-parametric estimation of laws, under vastly different circumstances.
Our major findings can be summarized in the following way,
• Given a non-negative margin of error, f -WAEs can learn latent space distributions with a convergence rate of O(n− 12 ), under fairly gentle assumptions on the input and target law (1). The proof involves a realistic characterization of the transformation, induced by the encoder network.
• Under a geometry preserving representation of the decoder map, Hölder densities can be successfully reconstructed by f -WAEs up to a constant margin (2). Our work also produces deterministic concentration bounds on the regeneration error and hence, the rate of convergence of the empirical laws.
• A particular instance of our analysis goes on to show that the input distribution converges strongly to its latent counterpart under encoding, in the form of empirical measures. Also, f -WAEs can exactly reproduce samples from smooth densities in the sense of weak convergence (4).
• Inferences, identical to that in case of f -WAE, can be drawn for the original WAE [6], under additional assumptions on the decoder (2).

heading: 2 Related Work
text: In recent times, scrutiny of the empirical achievements of deep generative models from a theoretical point of view has gained great momentum. GANs [2], being at the helm, have received most of the attention [8, 9]. Possibly, the cornerstone of success for a GAN lies in its adversarial training and the accompanying loss functions. A plethora of GAN variants have been devised by incorporating different losses, such as Wasserstein distance (WD) [5], f -divergence [10], Maximum Mean Discrepancy [11] and Sobolev distances [12], to name a few. The generative aspect, in particular, has attracted a lot of research in the form of distributional estimation studies [13, 14]. Additionally, [15] has proved weak convergence of distributions under several of the aforementioned adversarial losses. In a recent study, [16] has also discussed the convergence of the empirical measures in the case of WGAN, under parametrized network assumptions. VAEs, despite being used vastly as generative tools, have not experienced such a level of independent theoretical investigation, which comprehends its latent space mechanism.
In a novel approach to unify the deep generative techniques, Adversarial AEs [3] were introduced. Subsequent work to establish resemblance [17, 4], has only strengthened that foundation. Eventually, the formulation of WAE [6] bridged the gap significantly by matching regeneration standards. The equivalence in performance is a direct reflection of the similarity of its objective to that of GANs’ [7].
This ‘primal-dual relationship’ prepares a basis to explore the generative facets of WAE, in particular, now with the collective experience provided by GANs.
Typically, WD serves as the measure of discrepancy used to represent the reconstruction loss in WAEs. Non-parametric density estimation under this metric has seen the establishment of minimax bounds based on covering numbers, under fairly general assumptions [18, 19]. The same has also been achieved by [20], for unbounded metric spaces, assuming that some moments are finite. Singh et al. [21] established minimax convergence rates in the same context, under smoothness assumptions on the networks employed in the generation. Despite being influential in their own ways, none of the above aim at discussing the coinciding objectives of WAEs. In a recent empirical study, Diffusion VAE [22] was introduced, which attempts at capturing arbitrary latent manifolds using kernels of Brownian motion. However, without precise conceptual insight. As such, the theoretical questions regarding the parallel machinery of WAEs remain largely unanswered. Our analysis is a humble attempt at filling this void of statistical understanding.

heading: 3 Preliminaries

heading: 3.1 Notations
text: We start with denoting the input space by X , which can be assumed to be Polish (i.e., separable and completely metrizable). We will use Z for the latent space. Both may be thought of as Euclidean spaces, since it is a typical characterization. The space of probability measures (distributions) defined on X is denoted by P(X ). The set of all measurable functions from X to Z is refered to as F (X ,Z). For example, observe that a probabilistic encoder E belongs to F (X ,P(Z)). For any function T : X → Z , we denote the pushforward measure of µ as T#µ ∈ P(Z), i.e. for any measurable set ω ⊂ Z we have T#µ(ω) = µ({x ∈ X : T (x) ∈ Z}) = µ(T−1(ω)). To denote absolute continuity of a measure µ with respect to λ, we use the notation µ λ. The Support of µ is denoted by Supp(µ). To indicate the Closure of X we use X̄ and Int(X ) denotes the set of its Interior Points. Given S ⊆ X , the S-distance between a pair of functions f and g is given by, ‖f − g‖S = supx∈S
∣∣f(x)− g(x)∣∣. When the sup is taken over the whole space, we call it the uniform norm. The total variation distance between probability measures µ and γ ∈P(X ) is denoted by‖µ− γ‖TV . Now we introduce some useful concepts that are made use of later. Definition 1 (f -Divergence). Let P,Q ∈ P(X ) such that P Q. For a convex function f with f(1) = 0, the f-divergence of P from Q is defined as
Df (P,Q) = ∫ X f (dP dQ ) dQ.
Definition 2 (Yatracos Family [23]). For a class of real-valued functions F , defined on Z , the Yatracos family associated to F is a collection of subsets of Z defined as
Y(F) = {x ∈ Z : f(x) ≥ g(x); f, g ∈ F}. Definition 3 (Empirical Yatracos Minimizer [24]). The Empirical Yatracos Minimizer is a function
LP(Z) : ∞⋃ n=1 Zn −→P(Z) defind as
LP(Z)n = argmin q∈P(Z) ‖q − p̂n‖Y(P(Z)),
where p̂n is an empirical distribution based on a sequence of observations {Zi}ni=1 from Z . Definition 4 ( -Closeness). A pair of distributions f, g ∈P(X ) are said to be -close to each other with respect to the metric c if c(f, g) ≤ . Definition 5 (Quasi-Isometric Embedding). A map f : (Z, d1) −→ (X , d2) is called a quasiisometric embedding if there exists a constant A ≥ 1 such that,
1 A d1(x, y) ≤ d2(f(x), f(y)) ≤ Ad1(x, y) ∀ x, y ∈ Z.
Definition 6 (Covering Number [18]). Let S ⊆ X . Then, the minimum integer m such that there existsm closed balls {Bi}mi=1 of diameter each 3 S ⊆ ⋃ 1≤i≤mBi, is called the -covering number of S. We denote it by N (S).

heading: 3.2 Wasserstein Duality: A Brief Exposition
text: The equivalence relation between Wasserstein Distance and Integral Probability Metrics (IPMs) [25] is a fairly well-studied topic in optimal transport theory. We exploit this fact to serve our purpose. For a detailed elucidation on this subject, one may take refuge in [26, 27].
Let P,Q ∈P(X ) and c : X × X → R≥0 forms a metric. Then,
Wc(P,Q) = inf γ∈Γ(P,Q) {∫ X×X c(x, y)dγ(x, y) }
= sup l∈L 1c {∫ X l(x)dP (x)− ∫ X l(x)dQ(x) } = IPML 1c (P,Q),
where Γ(P,Q) = { γ ∈P(X × X ) : ∫ X γ(x, y)dy = P, ∫ X γ(x, y)dx = Q } denotes the coupling between P and Q. The class of 1-Lipschitz functions with respect to the metric c is represented by L 1c . Later in the study however, we will use the notation dL 1c for Wasserstein metric, for clarity.

heading: 3.3 Problem Setup
text: A typical WAE architecture intends to solve the minimization problem,
WAEc,λ(PX , D) = inf E∈F(X ,P(Z)) {∫ X Ez∼E(x)[c(x,D(z))]dPX(x) + λ.Ω(E#PX , PZ) } , (1)
where c : X × X → R≥0 and λ > 0 serves as a hyperparameter. Arbitrary divergence metrics between measures, belonging to P(Z), are deployed in the form of Ω. In this paper however, we modify this formulation to facilitate theoretical analyses. The reshaped objective that our study is based on is given by,
f -WAEc,λ(PX , D) = inf E∈F(X ,P(Z))
{ Wc(PX , (D ◦ E)#PX) + λ.Df (E#PX , PZ) } . (2)
This category of AEs are called f -Wasserstein Autoencoders [7]. The key difference between this family and the ordinary WAE arises due to the choice of the reconstruction loss. Wc is the manifestation of the expected cost of transportation, over all couplings of the pair of distributions under consideration. This alteration, however, does not impact the characterization significantly. Equivalence between these two systems can be attained by imposing mild restrictions on the decoder transformation, which we elaborate on at a later stage. As such, this can be marked as a valid foundation to work on.
Observe that, the regularizer metric used in (2), to measure the discrepancy between the target latent distribution and the encoded signal is taken to be Df . In this analysis, our specific choice of f -Divergence is Total Variation Distance (TV). Its rich theoretical appeal motivates us to do so. TV as a measure of deviation is symmetric with respect to the distributions under consideration. Moreover, it can pose both as a f -Divergence and an IPM [28]. The original WAE, in one of its characterizations, uses Jensen–Shannon divergence (JS) to penalize the loss instead [6]. TV, on the other hand, acts as an upper bound to JS [29], which also justifies our choice.
Remark. WAEs act as a generalization to AAEs [3]. We stress on the fact that, a specific choice of c as L22 in (1), establishes an equivalence between the two [6]. Keeping that in mind, our analysis does not restrict the choice of c and hence can also cater to the theory of AAEs.

heading: 4 Theoretical Analysis
text: Before moving forward, let us rewrite the minimization problem (2) in the so-called constrained form
inf E∈F(X ,P(Z))
{ Wc(PX , (D ◦ E)#PX) } subject to Df (E#PX , PZ) ≤ t, (3)
for some t ≥ 0. By Lagrangian duality [30], for every value of t where the constraint Df (E#PX , PZ) ≤ t holds, there exists a value of λ that produces the same solution from (2). Conversely, the solution to the problem (2), say Ê also solves the bound version with t = Df (Ê#PX , PZ).
As such, there is an one-to-one correspondence between the constrained problem (3) and the Lagrangian one (2). This formulation gives us a direction to move ahead to establish regeneration guarantees and consistency of measures in the latent space.
Our analysis consists of two stages, going forward. Firstly we show that probabilistic encoders can successfully transform input densities into realistically characterized latent space laws, under TV distance, up to a constant margin of error. The mild assumptions imposed in the process are fairly practical. Once the constraint of the minimization problem is met in the form of latent space consistency, we provide deterministic upper bounds to the empirical reconstruction loss.
Throughout our discussion, we denote with µ ∈ P(X ) the input data distribution. The target distribution which characterizes the latent space is denoted by ρ. For simplicity, we assume that both µ and ρ happen to have corresponding densities, namely pµ and pρ with respect to the Lebesgue measure λ, in their respective spaces. Both densities need explicit characterization, which we state in the form of certain assumptions.
Assumption 1. pµ, (i) based on a compact and convex support is (ii) bounded away from 0 by a constant factor c > 0, i.e. infx pµ(x) ≥ c. Assumption 2. pρ, (i) also defined on a compact support, is easy-to-sample-from and (ii) infinitely smooth, i.e. pρ ∈ C∞(Z).
The input density being far from nullity, passes on the same nature to the reconstructed law, even under near-ideal situations. This poses as a measure to prevent the regenerated law from being a degenerated one, at zero. We point out that, in the non-parametric approach of this work, we often use empirical distributions corresponding to ρ, which are based on observations from the same. In high-dimensional statistics, there are distributions from which it is practically not feasible to draw samples. For example, the drawing of uniform samples from a high-dimensional unit sphere. Although in our analysis, the need for such samples is strictly theoretical and the practical feasibility is somewhat immaterial, we describe ρ this way to avoid complication. Given these assumptions, suppose the ‘encoded’ pushforward measure E#µ ∈ P(Z) has density pE#µ. Then, every such pE#µ is a potential candidate to represent pρ. However, our analysis does not assume the existence of a density. We denote Supp(pρ) by C, such that Assumption 3. VC-dim[Y(P(C))] is finite.
This assumption too is very much plausible in its own right. For example, let Gd and Ad denote the class of d-dimensional Gaussian distributions and the class of d-dimensional axis-aligned Gaussian distributions respectively. It can be shown that, VC-dim[Y(Gd)] = O(d2) and VC-dim[Y(Ad)] = O(d) [31]. The introduction of Yatracos class of distributions, in turn, facilitates the search for the minimum distance estimate of a measure. For a detailed exposition on the same, one may turn to [24].
Perhaps the most challenging of tasks in studying the theoretical aspects of deep neural networks lies in their basic characterization. Several depictions of networks as a collection of functions, indexed by parametric classes have produced notable results in the past [9, 13]. This paper rather explores the mathematical properties a network has to embody to function in a WAE system. The following representation of an encoder map reflects our motivation. We consider an E ∈ F (X ,P(Z)) such that,
Assumption 4. (i) E#µ is supported on C and is also easy to draw samples from. (ii) Given any arbitrary empirical measure µ̂n (based on n samples) corresponding to µ, there exists an empirical counterpart (̂E#µ)n of E#µ which is -close to µ̂n under E, with probability at least
1 − k exp{−nr 2}, where r ≥ 1 and k ≥ 0. In other words, P (∥∥∥E#µ̂n − (̂E#µ)n∥∥∥ TV ≤ ) ≥ 1− k exp{−nr 2}.
Part (ii) of Assumption (4) is provided only to give coherence to the definition of E. It suggests that the probability of ‘the discrepancy between the two quantities involved being arbitrarily small’ increases exponentially with the r-th power of n. As such, if one has a superlinear rate of increment in information in the form of samples, the portion lost in transition decays sharply. This embodies our idea of an encoder, that preserves information. It is often seen in practice that AEs, with ReLU encoders, can reconstruct images accurately, despite having the encoded observations to be almost degenerate. In such a case, the two measures under consideration can always be said to be arbitrarily
close. Part (ii) is a gentler approximation of the same idea. We now present the main result that enables one to prove consistency in estimating the latent space distribution.
Theorem 1. Let, (̂E#µ)n stands for an empirical measure based on n ≥ 1 i.i.d. samples from E#µ. Then, under assumptions [1(i), 2(i), 4(i)], for positive constants c1, c2, c3 and δ ∈ (0, 1) there exists λ∗ ≥ 0 such that, ∥∥∥ρ− (̂E#µ)n∥∥∥ TV − λ∗ ≤ 1√ n { c1 √ v + c2 √ ln (c3 δ
)} holds with probability ≥ 1− δ, where v = VC-dim[Y(P(C))].
To prove this theorem, we introduce some crucial results from the estimation theory of measures. Proofs of all the lemmas stated henceforth can be found in the supplement. Lemma 1. For f, g ∈P(C),‖f − g‖TV = ‖f − g‖Y(P(C)) . Lemma 2. Let γ ∈ P(Z). Also, let γ̂n denote the empirical distribution based on n ≥ 0 i.i.d. samples drawn from γ. Then there exist positive constants k1, k2 such that
P ( ‖γ − γ̂n‖Y(P(Z)) ≤ k1 √ v n + t ) ≥ 1− exp (−k2nt2),
where v stands for VC-dim[Y(P(Z))].
Proof of Theorem 1. Given n observations from ρ, let ρ̂n denote the corresponding empirical measure. Now, using the triangle inequality we have,∥∥∥ρ− (̂E#µ)n∥∥∥ TV ≤ ∥∥ρ− E#µ∥∥TV + ∥∥∥E#µ− (̂E#µ)n∥∥∥TV
≤ ‖ρ− ρ̂n‖TV + ∥∥∥E#µ− (̂E#µ)n∥∥∥ TV + ∥∥ρ̂n − E#µ∥∥TV . (4)
Define, L∗n = argmin
q∈P(C) ‖q − ρ̂n‖Y(P(C)).
Observe that, ∥∥ρ̂n − E#µ∥∥TV ≤ ‖ρ̂n − L∗n‖TV + ∥∥L∗n − E#µ∥∥TV = ‖ρ̂n − L∗n‖Y(P(C)) +
∥∥L∗n − E#µ∥∥TV (5) ≤ ‖ρ− ρ̂n‖Y(P(C)) +
∥∥L∗n − E#µ∥∥TV . (6) Lemma (1) ensures the equality in (5). (6) is due to the definition of L∗n. Now, ∥∥L∗n − E#µ∥∥TV = infτ∈T (L∗n,E#µ) ∫ c(x, y)dτ(x, y) (7)
= inf τ∈T ′ (L∗n,µ)
∫ c(x,E(y))dτ(x, y), (8)
where T and T ′ are couplings of measures. The metric c : Z × Z → R≥0 in (7) is the trivial metric c(x, y) = 1x6=y [26]. This implies, the transformation induced by the encoder should be such that, it minimizes the adversarial loss (8). In case c is lower semi-continuous, there exists a τ ∈ T ′ which minimizes (8), and hence an E [32]. For example, c(x, y) = 1C(x, y), where 1C(x, y) is the indicator on an open set C. In our situation however, we can always choose a sub-optimal E such that (8) ≤ λ∗, for a non-negative λ∗. Villani et al. [26] describes various ways to get hold of such a τ . Going back to (4),∥∥∥ρ− (̂E#µ)n∥∥∥
TV − λ∗ ≤ 2‖ρ− ρ̂n‖Y(P(C)) + ∥∥∥E#µ− (̂E#µ)n∥∥∥Y(P(C)) . (9) Thus, (9) along with lemma (2) proves the theorem.
It is worth mentioning that in reality however, we only have a sample of size n ∈ N+ from the input distribution, say {Xi}ni=1. Based on the same, an empirical distribution µ̂n = 1n ∑n i=1 δXi is what we have at hand. Corollary 1. Under the additional assumptions [3, 4(ii)],∥∥E#µ̂n − ρ∥∥TV − λ∗ = OP(n− 12 ). Remark. Despite the fact that the optimal value of (8) cannot be made arbitrarily small directly, in case we obtain λn, n ∈ N, such that, lim supn→∞ λn = λ∗; the same conclusion can be drawn. We call Corollary (1) ‘consistency up to λ∗’ in this light. Note that, for a given margin of error λ in the latent space, E needs to be chosen such that, λ∗ ≤ λ. On the other way round, starting with an unspecified λ, one can learn about the feasible margin of error by observing λ∗.
Theorem (1) shows that the discrepancy between the ‘encoded’ and the ‘target’ law can be made arbitrarily small around a constant with high probability. Corollary (1), consequently establishes our idea of consistency in latent space. Proof for the same can be found in the supplement. As such, for any suitably chosen t∗, the constraint in problem (3) is satisfied. We now investigate whether the decoder network is capable of regenerating a distribution ‘close’ to µ, from E#µ. A probabilistic decoder, in this context, is formally defined as a function D : Z −→ X such that D#ρ ∈P(X ). The residual task at hand can be formally written as the minimization of
dL 1c ((D ◦ E)#µ, µ) = sup l∈L 1c
{ Ex∼(D◦E)#µ [ l(x) ] − Ex∼µ [ l(x) ]} over E ∈ F (X ,P(Z)) which follows assumption (4). Which, however under an observed empirical measure µ̂n boils down to its sample counterpart, given by
dL 1c ((D ◦ E)#µ̂n, µ) = sup l∈L 1c
{ Ex∼(D◦E)#µ̂n [ l(x) ] − Ex∼µ [ l(x) ]} . (10)
We remark that the role of the class of functions L 1c while minimizing (10) is to behave as ‘critics’. GANs, during their training, gradually learn to be a better judge by casting this functional class through a discriminator [5]. This freedom of choice in turn gives one more flexibility to interpret its regenerative capabilities [13, 9, 14]. In the case of AEs however, the choice depends solely on the preassigned discrepancy metric. Hence, the theoretical justification of reconstruction for AEs needs additional maneuvering. Our first step in doing so is an assumption on the input distribution. Assumption 5. (i) pµ ∈ Hα(X ) with α > 0, where Hα(X ) denotes the Hölder class based on X ; such that, the ith order derivative p(i)µ exists (i ≤ bαc) and is bounded on X̄ . Also,
D bαc pµ = supx,y ∣∣∣p(bαc)µ (x)−p(bαc)µ (y)∣∣∣ ‖x−y‖2 α−bαc <∞, for x 6= y ∈ Int(X ). Remark. Assumption (5) enables one to assign the Hölder norm, defined as∥∥pµ∥∥Hα = maxi≤bαc∥∥∥p(i)µ ∥∥∥∞ +Dbαcpµ . Moreover,
∥∥pµ∥∥Hα turns out to be bounded. Smoothness assumptions on input data distribution, in the form of Hölder or Sobolev densities are quite familiar in the theory of density estimation for generative models [13, 14, 21]. Observe that, earlier results still hold under this additional assumption. The smoothness of both the input and latent densities (2(ii)) together ensures the existence of certain regenerative maps, which are crucial to the forthcoming discussion. Lemma (3) formalizes the same. Lemma 3 ([33]). Under assumptions [ 1, 2, 5 ] , there exists a map T ∈ Hα+1 from Z to X such that, T#ρ = µ.
In our discussion, similar to the encoder transformation, we do not impose specific structural restrictions on the decoder network. However, the mathematical assumptions that are made, are inspired and supported by real architectures. Assumption 6. The quasi-isometric embedding D : (Z, ‖ ‖TV ) −→ (X , c) induced by the decoder network is -close to T in uniform norm, where T is as defined in lemma (3). Also, (D ◦E)#µ shares the same support with µ.
Classes of functions, learned by generator networks in GANs, are often taken to be smooth [13, 21] to achieve minimax convergence rate. Our assumption of quasi-isometric embedding is gentler in principle. We mention that an alternative weaker assumption of Lipschitz continuity would have sufficed in our analysis. Assumption (6) on the other hand, takes one step forward to comment on the broader geometry of the two spaces under consideration. Moreover, precise specification of parameters of a ReLU network can always result in a map, which is capable of approximating the optimal Monge solution [34, 35], which in our case turns out to be smooth. Note that, the metric on Z can be equivalently taken as ‖ ‖1. The following lemma provides an oracle inequality by fragmenting the empirical loss as in (10), into disjoint parts. Lemma 4. Given an encoder transformation E∗,
dL 1c ((D ◦ E ∗)#µ̂n, µ) ≤ E1 + E2 + 2E3,
where E1 = dL 1c ((D ◦ E ∗)#µ̂n, D#ρ) is the ‘Encoder Approximation Error’; E2 = dL 1c (D#ρ, T#ρ) stands for the ‘Decoder Approximation Error’ and E3 = dL 1c (µ̂n, µ), the ‘Statistical Estimation Error’.
We remark that successful regeneration by the f -WAE can be ensured by showing: these individual errors are arbitrarily small or they approach zero in any probabilistic sense. To demonstrate the same in the case of E3, we introduce some concepts from [36, 18]. Definition 7 (1-Upper Wasserstein Dimension). For γ ∈P(X ), the ( , τ)-covering number is given by
N (γ, τ) = inf S⊆X {N (S) : γ(S) ≥ 1− τ}.
Consequently, we define the ( , τ)-dimension as δ (γ, τ) = N (γ,τ) − log( ) . Under this setup, the Upper Wasserstein Dimension for p = 1 is
δ∗1(γ) = inf{s ∈ (2,∞) : lim sup →0 δ (γ, s s−2 ) ≤ s}.
Lemma 5 ([18]). Let diamc(Supp(µ)) = B. Then, for n ≥ 0 and s > δ∗1(µ), P ( dL 1c (µ̂n, µ) ≤ O(n − 1s ) + t ) ≥ 1− exp { − 2nt 2
B2
} .
Now, we propose the main theorem which provides a guarantee regarding regeneration. Theorem 2. Given a margin of error λ∗ in latent space, let µ̂n denote an empirical input measure, consistent up to λ∗, under encoder map E∗. Also, let diamc(Supp(µ)) = B. Then, there exists a constant ζ∗ ≥ 0 and δ ∈ (0, 1) such that
dL 1c ((D ◦ E ∗)#µ̂n, µ)− ζ∗ ≤ O(n− 1 s ) +O(n− 12 )
with probability at least 1− δ, where s > δ∗1(µ).
Proof of Theorem 2. Observe that, the error committed by the encoder
E1 = dL 1c ((D ◦ E ∗)#µ̂n, D#ρ) = inf
υ∈Υ(E∗#µ̂n,ρ)
∫ c(D(x), D(y))dυ(x, y) (11)
≤ A inf υ∈Υ(E∗#µ̂n,ρ)
∫ ‖x− y‖TV dυ(x, y)
≤ λ∗AB +O(n− 12 ), (12) where (12) holds with probability ≥ 1 − δ (using Theorem (1)). Υ in (11) denotes the associated coupling and A ≥ 1 is the constant related to the embedding D. Denote, ζ∗ = λ∗AB. Similarly,
E2 = dL 1c (D#ρ, T#ρ) = sup l∈L 1c
{ Ex∼ρ [ l(D(x)) ] − Ex∼ρ [ l(T (x)) ]} ≤ Ex∼ρ [ ‖D − T‖∞ ] ≤ ∗, (13)
which is a consequence of the fact that,‖D − T‖∞ ≤ (Assumption (6)). Here, ∗ is an arbitrarily small quantity corresponding to .
Also, lemma (5) suggests that for s > δ∗1(µ),
E3 = dL 1c (µ̂n, µ) ≤ O(n − 1s ) + 1√ n B
√ 1
2 ln (1 δ ) (14)
with probability at least 1− δ. As such, (12), (13) and (14) together prove the theorem.
Remark. Let us weigh up on a special case, which carries notable significance. Suppose, one obtains λn as an upper bound to (8), corresponding to L∗n, n ∈ N+, such that λn = o(1). We do not prove the existence of such a sequence, which might be taken up as a future work. However, under the assumption of existence, corollary (1) implies that,
sup A∈F ∥∥E#µ̂n(A)− ρ(A)∥∥ −→ 0, where F is the Borel σ-algebra on Z . As such, E#µ̂n converges strongly to ρ. This theoretically ensures the achievement of a target latent law.
Similarly, such an {λn} will have a remarkable effect on the regeneration process. In that case, Theorem (2) will imply,
dL 1c ((D ◦ E ∗)#µ̂n, µ) −→ 0,
i.e. (D ◦E∗)#µ̂n converges weakly in P(X ) to µ [26]. This result serves as an exact reconstruction guarantee.
Now, let us look back at the original WAE objective in (1). Denote by
d∗c(PX , (E,D)) = ∫ X Ez∼E(x)[c(x,D(z))]dPX(x)
the reconstruction loss. In general, this acts as an upper bound to the f -WAE counterpart [7]. However, under additional restrictions on D, they become equivalent [7]. In such a case, if Ω in (1) is taken to be Df , the two objectives in their entirety also follow the same trait. In our study, the measure of discrepancy between distributions in latent space was throughout taken to be TV. JS divergence, being upper bounded by TV, is obliged to follow the results established exactly. As such, the only task remaining is the transferral of regeneration guarantees to WAEs.
Corollary 2. There exists a specific margin of error κ ≥ 0 in the latent space such that, Theorem (2) holds exactly for d∗c(µ̂n, (E ∗, D)), where D is also invertible.
Proof of Corollary (2). Husain et al. [7] had suggested the existence of a κ ≥ 0, such that for all margin or error λ > κ, (1) and (2) are exactly equal. The proof however, demands the decoder transform to be invertible. In such a case, for an encoder E∗ and Ω = Df imply that
d∗c(µ̂n, (E ∗, D)) = ∫ X Ez∼E∗(x)[c(x,D(z))]dµ̂n(x) ≤ dL 1c ((D ◦ E ∗)#µ̂n, µ) + dL 1c (µ̂n, µ).
Hence, using lemma (2) and Theorem (2) we say that
d∗c(µ̂n, (E ∗, D))− ζ∗ ≤ O(n− 1s ) +O(n− 12 )
holds with probability at least 1− δ, for s > δ∗1(µ).
We emphasize the fact that the argument of weak convergence, however, as given in (4), does not apply directly to this case. The Wasserstein distance metrizes P(X ), i.e. weak convergence holds if and only if dL 1c −→ 0. On the other hand, d ∗ c does not satisfy the axioms of a distance. As such, WD produces stronger inferences, even though under carefully taken assumptions they tend to be equal.

heading: 5 Further Theoretical Implications
text: An important aspect of the VAE’s operations lies in its involvement in ‘disentanglement’. While the concept lacks a robust definition, it can arguably be described as the process of achieving a factorial representation; one with ‘expressive’ and perhaps independent coordinates, which characterize the features. A somewhat gentle depiction of the same might be a distribution with a diagonal dispersion matrix. The non-parametric portrayal of latent distributions in this analysis does not comment on the covariance structure of the underlying random variables. However, this seemingly unrestrained characterization in turn may allow for such specific distributions also, as far as they follow the assumptions of our framework. For example, we mention that if P(C) is taken to be the class of finite-dimensional axis-aligned Gaussians, our results hold true.
A practitioner might also feel divided between the two architectures that appear in [6]. Although we focus mainly on the one deploying JS divergence, there is no evidence of theoretical superiority that MMD enjoys, to the best of our knowledge. Uniform convergence bounds on empirical MMD between distributions, as established by [37] in a different context, however, also produce a convergence rate of O(n− 12 ). As such, this section can be regarded as a note of encouragement for closer observations on these very topics.

heading: 6 Conclusion
text: Our analysis, besides serving as the first of its kind theoretical promises regarding the simultaneous tasks a WAE has to perform, also points toward untraveled avenues. An immediate extension might look into broader classes of discrepancy measures in latent space. The latent space and hence the distribution that characterizes it might also be in focus. An even elaborate characterization can deliver it further justice. Our study includes a commentary on the geometry preserving nature of deep generative networks from a fairly new perspective. Being a novel representation, it creates new opportunities for inventive scrutiny. We also restrict our analysis to a non-parametric regime, which may encourage similar endeavours under a parametrized setup. Such an approach could be the key to revealing the effect of network parameters such as depth, width, activation functions etc. on regeneration and consistency in the latent space. This, in turn, may improve the theoretical results by allowing training plans on board as well.

Review summaries:
This paper analyzes the statistical properties of WAE, providing theoretical guarantees for both sample reconstruction and latent distribution tasks. To do so, the authors use the family of so-called f-Wasserstein autoencoders due to the specific choice of discrepancy selected for measuring the target and latent distribution. Here total variation distance is chosen. After setting up necessary preliminaries, and assumptions the authors prove the first of two main theorems, consistency in estimating the latent space distribution. Under suitable conditions, the second theorem provides a guarantee regarding the regeneration. Since they analysis was conducted using TV, which upper bounds the Jenson-Shannon divergence, the final corollary transfers the regeneration guarantees to WAEs. Fairly gentle assumptions and interesting theoretical results are discussed in detail. 

The submission aims to provide rigorous theoretical results for the Wasserstein Autoencoder (WAE) - A model that has achieved great empirical success yet remains severely understudied. In particular, their main contribution in showing learning theoretic bounds such as complexity and convergence guarantees. As a feature of the Autoencoder set-up, they introduce the notion of statistical regeneration and go out to prove this statement for their learning setting.