Statistical Guarantees for Variational Autoencoders using PAC-Bayesian Theory
Authors: Sokhna Diarra Mbacke
Florence Clerc
Pascal Germain
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Variational Autoencoders
PAC-Bayes
Statistical Learning Theory
TL;DR: We provide reconstruction, regeneration and generation guarantees for VAEs using PAC-Bayesian Theory

Abstract: Since their inception, Variational Autoencoders (VAEs) have become central in machine learning. Despite their widespread use, numerous questions regarding their theoretical properties remain open. Using PAC-Bayesian theory, this work develops statistical guarantees for VAEs. First, we derive the first PAC-Bayesian bound for posterior distributions conditioned on individual samples from the data-generating distribution. Then, we utilize this result to develop generalization guarantees for the VAE's reconstruction loss, as well as upper bounds on the distance between the input and the regenerated distributions. More importantly, we provide upper bounds on the Wasserstein distance between the input distribution and the distribution defined by the VAE's generative model.

Statistical Guarantees for Variational Autoencoders using PAC-Bayesian Theory
Sokhna Diarra Mbacke
Florence Clere
Université Laval
McGill University
sokhna-diarra mbacke. 1@ulaval. ca
florence. clerc@mail mcgill.ca
Pascal Germain
Université Laval
pascal heaillleeeaainiiii ulaval
Abstract
Since their inception, Variational Autoencoders (VAEs) have become central in machine learning. Despite their widespread use, numerous questions regarding their theoretical properties remain open. Using PAC-Bayesian theory, this work develops statistical guarantees for VAEs. First, we derive the first PAC-Bayesian bound for posterior distributions conditioned on individual samples from the data- generating distribution. Then, we utilize this result to develop generalization guarantees for the VAE's reconstruction loss, well upper bounds the distance between the input and the regenerated distributions. More importantly, we provide upper bounds the Wasserstein distance between the input distribution and the distribution defined by the VAE's generative model.
Introduction
In recent years, deep generative models have exhibited tremendous empirical success. Two of the most important families of generative models are Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) and Variational Autoencoders (Kingma and Welling, 2014; Rezende et al., 2014). GANs take an adversarial approach, whereas VAEs are based maximum likelihood estimation and variational inference. VAEs comprise two main components: an encoder which parameterizes approximation of the posterior distribution which parameterizes the likelihood. In addition to generative modelling tasks such as image generation (Vahdat and Kautz, 2020) and text generation (Bowman et al., 2016), VAEs have been successfully applied to other topics such as semi-supervised learning (Kingma et al., 2014), anomaly detection (An and Cho, 2015), and dimensionality reduction (Kaur et al., 2021). However, despite their empirical success, the question of statistical guarantees for the performance of VAFS remains largely open. Namely, how can certify that VAEs generalize well, both in terms of reconstruction and generation?
the latent variables, and decoder
PAC-Bayesian theory (McAllester, 1999; Catoni, 2003) is influential tool of statistical learning theory dedicated to providing generalization bounds for machine learning models. PAC- BAC-Bayes has been applied wide variety of problems such classification (Germain et al., 2009; Parrado- Hernández et al., 2012), meta-learning (Amit and Meir, 2018), co-clustering (Seldin and Tishby, 2010), domain adaptation (Germain et al., 2020), and online learning (Haddouche and Guedj, 2022). In recent years, PAC-Bayes has been used to derive non-vacuous generalization bounds for supervised learning algorithms based neural networks (Dziugaite and Roy, 2018; Pérez- Prtez- et al., 2021). See Guedj (2019) and Alquier (2021) for excellent surveys.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

The objective of this work is to utilize PAC-Bayesian theory to derive statistical guarantees for VAEs. Our generalization bounds investigate the reconstruction, regeneration, as well as the generation properties of VAEs.
1.1 Related Works
In order explain the empirical success of deep generative models, a lot of attention has been put into deriving theoretical guarantees for these models. Most of the results, however, have been dedicated to GANs and their variants (Arora et al., 2017; Zhang et al., 2018; Liang, 2021; Singh et al., 2018; Schreuder et al., 2021; Biau et al., 2021; Mbacke et al., 2023). A possible explanation for this plethora of theoretical results is the adversarial loss function, which directly offers an estimation of the discrepancy between the input distribution and the generator's 's distribution. Despite being central tools in modern machine learning, VAEs have not benefited from such a thorough theoretical analysis (Chakrabarty and Das, 2021).
The work of Chakrabarty and Das (2021) studies the regeneration properties of Wasserstein autoen- coders (WAEs) (Tolstikhin et al., 2018), which come from the same family as VAEs. Using VC theory, Chakrabarty and Das (2021) derive rates of convergence for the Wasserstein distance between the input distribution and the distribution regenerated by the WAE, as well the total variation distance between the empirical latent distribution and the latent prior. Taking a more empirical approach, Ahérief-Abbellan et al. (2022) use PAC-Bayes to study the generalization properties of stochastic reconstruction models. They define a [0, -o-unddd reconstruction loss function, then utilize McAllester's 's bound (McAllester, 2003) to formulate generalization bound for models with probabilistic neural networks (Langford and Caruana, 2001). Then, they re-scale their loss and compare the empirical results the reconstruction of standard VAEs benchmark datasets.
We also mention the work of Mbacke et (2023), who developed PAC-Bayesian bounds for the analysis of adversarial generative models. Using McDiarmid's 's inequality, they proved upper bounds on the distance between the input distribution and the generator's distribution, for WGANs (Arjovsky et al., 2017) and EBGANs (Zhao et al., 2017).
1.2 Our Contributions
In this work, we derive theoretical guarantees for variational autoencoders using PAC-Bayesian theory. We provide three types of guarantees: reconstruction guarantees showing that VAEs can successfully reconstruct unseen samples from the input distribution; regeneration guarantees proving upper bounds on the Wasserstein distance between the input distribution and the distribution regenerated by the VAE, given the training set as input; and finally, generation guarantees showing upper bounds on the Wasserstein distance between the data- cata-gennra distribution and the VAE's generated distribution defined by the latent prior and the decoder. To the best of our knowledge, these are the first generalization bounds for the standard VAE's reconstruction and regeneration properties, well as the first statistical guarantees for the VAB's generative model.
In our analysis, the PAC-Bayesian posterior coincides with the variational posterior, which requires the PAC-Bayeste posterior to be conditional. Since, to the best of our knowledge, such PAC- PAC-Bayes bounds do not exist in the literature, start by developing the first PAC-Bayesian bound for conditional posterior distributions. Then, we provide upper bounds for the VAE's performance under two main assumptions: we start by assuming the instance space is bounded, then we take advantage of the manifold hypothesis. Our bounds are functions of the optimization objective of the VAE, namely, the empirical reconstruction loss, and the empirical KL-loss.
The remainder of this paper is organized as follows. In Section 2, we define some preliminary concepts, then briefly introduce VAËs and PAC-Bayesian theory. Section 3 presents our general PAC- Bayesian theorem for conditional posteriors. Then, in Sections 4 and 5, we present our generalization bounds for the reconstruction loss, and the regeneration and generation guarantees.

---

2 Preliminaries
2.1 Definitions and Notations
Given metric spaces (R, d) and (),, dd), and a real number K 0, a function f x - 3 is
K-Lipschitz continuous if for any x, y X, we have
d' f()x)) s Kd(x,y).
The smallest K such that this condition is satisfied is called the Lipschitz norm or Lipschitz constant
of f and denoted |I Iapp' Moreover, the set of K-Lipschitz continuous functions f X - y is denoted (xt, )) (the underlying metrics will clear from the context).
Throughout the paper, we use lower case letters p, q to denote both probability distributions and their densities w.r.t. the Lebesgue measure. We may add variables between parentheses to improve readability (e-g- p(z) to emphasize that is a distribution on the space of variables z, and g(z) x) to indicate that y is a conditional distribution). The set of probability measures on space X' denoted M (2'). The Kullback-Leible (KL) divergence between p. q MM (X)) is denoted KL q). We omit the absolute continuity condition p < q in the statements of the results below, since if is not satisfied, then one may assume the KL divergence is infinite and the bounds hold trivially.
Integral Probability Metrics (IPMs, see Müller (1997)) are class of pseudo metrics defined on the space of probability measures. Given family F of real-valued functions defined on X, the IPM defined by FF is denoted d, and defined as
dr = sup fer / f (idd-ssdg
=sup
Idy Vp. E M2
Stemming from the theory of optimal transportation (Villani, 2009), the Wasserstein distances (see Definition A.2) are class of metries between probability measures. The Wasserstein distance of order 1, also referred to simply as the Wasserstein distance, is the IPM defined by the set == (f X + R s.t. IIf 1}.
Finally, we recall the definition of a pushforward measure. Let p be probability distribution space Z and g + X' be a measurable function. The pushforward measure defined by and p and denoted gtp is probability distribution on X' defined as gēp( A) = p()= for any measurable set A S X. other words, sampling x ~ gip means sampling z ~ p first, then setting x = g(z).
2.2 Variational Autoencoders
We consider a Fuclidean observation space X, a data-generating distribution 1a E M. (2),, and a latent space Z = Rddx VAEs comprise two main components: the encoder network whose parameters are denoted σ, and the decoder network whose parameters are denoted 0. For simplicity, we may refer to 6 and 0 as the encoder and decoder respectively. The encoder parameterizes a distribution (z|zx) over the latent space Z, which is a variational approximation of the Bayesian posterior pa (z x). The likelihood pe (x z) is parameterized by the decoder network. In this work, we consider the standard VAE, with a standard Gaussian prior p(z) (0 I) on Z and Gaussian latent distributions qs (z x). More precisely, for any x E X, the distribution 2o (2 x) is Gaussian distribution with diagonal covariance matrix ((s (x) diag( (o) (x))) where
Ps X' + Z = dd and 0o : X
220
Note that diag(o) denotes the diagonal matrix whose main diagonal is the vector a. In order to simplify some of the expressions below, it may be useful to express the encoder network as function
= [Ma (x) T (x)
Qs : - 2d2, where Qo (x)
(2)
We express the decoder as a parametric function 2 - X. For any x E X' upon receiving z ~ gs(2) (z(2))), x)), the decoder's output go (z) is reconstruction of x. Given training set S (x,,...,,,, the encoder and decoder networks are jointly trained by minimizing the following objective:
(6, 0)
(x/xx) [- log (x + (KL((g (z|x;) (1)(())
(3)
m
3

---

where the first part of (3) is the reconstruction loss and the second part is the KL-divergence between the latent distributions (associated to the training samples) and the prior over the latent space, weighted by hyperparameter 3 > 0 (Higgins et al., 201 7). The reconstruction loss measures the similarity between x and its reconstruction go (z), and can be defined in many ways. With Gaussian likelihood, the reconstruction loss is the squared Lg norm ||x 9o
After training, the VAE defines generative model using the prior p(z) and the decoder go (Kingma and Welling, 2014). The distribution gotp(z) &M' allows one to generate new samples by first sampling a latent vector from the prior, then passing it through the decoder. We refer to gotp(z) as the VAE's generated distribution.
2.3 A Brief Introduction to PAC-Bayesian Theory
Dating back to McAllester (1999), PAC-Bayesial theory develops bigh-probbbility generalization bounds for machine learning algorithms. In essence, PAC-Bayes frames the output of such an algorithm as a posterior distribution over class of hypotheses, and provides an upper bound on the discrepancy between a model's s empirical risk and its population risk.
PAC-Bayes considers the following concepts: a hypothesis class H. a training set S = (x1,..... x,) iid sampled from an unknown distribution j over an instance space X', and real-valued loss function É H. x X' + [0, oo). Moreover, the primary goal of PAC-Bayes is to provide generalization bounds uniformly valid for any posterior q E M (H). These bounds are dependent on the empirical performance of q and its closeness chosen prior distribution p E M (H), as measured by the KL-divergence. The empirical and true risks of posterior distribution q M4 (H) are defined as
R
E k>-g(h)
1 1
Σ 71
E(h,
xi)
and R(g)
E h-q(h)
((h, x) x~-
E
As an illustration, consider the following PAC-Bayesian bound for bounded loss functions developed by Catoni (2003).
Theorem 2.1. Given probability measure μ on X, hypothesis class H. a prior distribution on
H. a loss function& E H x X - [0, 11, real numbers (0, 1) and X > O, with probability at least
1 8 over the random draw of S ~ 2 the following holds for any posterior q MM (H):
A
KL(g l1 p) + log
R(g)= & Rs(()) +
8n
A
The connection between PAC-Bayesiag theory and Bayesian inference was highlighted by Grünwald (2012) and Germain et al. (2016), who showed that with a proper choice of and the negative log-likelihood the loss function f, the optimal posterior minimizing the right-hand side of Catoni's bound is the Bayesian posterior. Note that although the Bayesian posterior is unique (for a given prior and likelihood), "PAC-Bayesian posterior" could be, in principle, any distribution over H.
In our PAC-Bayesian analysis of VAEs, we will use the latent space 2 as our hypothesis class, so that the VAE's prior will coincide with the PAC-Bayesian prior and the variational posterior g (z|x)) will stand for our PAC-Bayesian posterior. An immediate concern with this approach is that the encoder's distributions are conditioned individual samples μt, whereas the usual PAC- BCCyeBia bounds hold for unconditional posteriors (h). We address this issue in the next section, by developing a novel PAC-Bayesiaa bound for posterior distributions q(- xx). This general result will be later utilized to analyze VAEs.
3 General PAC-Bayesian Bound with a Conditional Posterior
In this section, we present general PAC-Bayesian bound with a conditional posterior distribution. Note that the novelty of this result is not the conditioning on observations, since this can be achieved by exploiting the existing PAC-Bayesian bounds. Indeed, Haddouche and Guedj (2022) utilized the general theorem of Rivasplata et al. (2020) to derive bounds for the online learning framework.
In supervised learning, the instance space has the form X x y where X is set of features, and ) set of labels. We use more general formulation encompass the unsupervised learning setting.

---

Instead, the contribution of Theorem 3.1 is to predict the behavior of q(l]x), for any (previously unseen) x ~ μ., when the posterior q was only learned using the training samples {x...... To the best of our knowledge, this is the first PAC-Bayesian bound where the posterior distribution is conditional distribution conditioned on individual elements from the instance space. This bound will require the posterior q and the loss function e to satisfy the following technical assumption.
Assumption 1. We say that a distribution q( (x) and a loss function satisfy Assumption with a constant K 0 if there exists a family & of functions H - IK such that the following properties hold.
1. The function x+> <(-lx) is continuous in the following sense: for any X1,X2 E X. de (q(h)x)). x2)) S K Kd((1, X2).
2. For any x E X. the function ((,, x) H IR is in E: x(,x)) E for any x E X.
Before stating the general result, let us pause and discuss this assumption. Intuitively, the goal of a generalization bound is to predict the behavior of the posterior distribution (/(lx) on previously unseen examples x μ. Since the posterior qf ( ()) is learned by minimizing the loss function & on the training samples S = (X1..... ),), one may need two things to be true.
First, the mapping x + (())x) has to be somewhat continuous. This is ensured by the first part of Assumption 1, which states that the posterior q is ppsshitz-continunng and the underlying metric d on X. Indeed, this tells us that if X and X2 are close w.r.t the underlying metric on X, then q()(x1) and q(h X2) are close, w.r.t. the IPM de.
with respect to the IPM de
Second, that continuity has to be "understood" by the loss function É, which corresponds to the second part of the assumption. It states that the loss function's discriminative power is weaker than the one defined by the IPM dg. In other words, the discrepancy measure used to measure the similarity between the distributions ((((x)) and q(h (x2) needs to be just strong enough to fool the loss function into thinking that the distributions are close to each other. An alternate formulation of Assumption 1 provided in the supplementary material (Remark F.1).
Finally, we emphasize that Assumption 1 is not as restrictive as it may seem at first. For instance, it is satisfied by VAE's variational posterior, when the encoder and decoder networks have finite Lipschitz norms and the reconstruction loss is defined with the L2 norm (see Proposition 4.1). We are ready to state our first result.
Theorem 3.1. Let (X, d) be a metric space. Consider probability measure μ X, a hypothesis class H. a prior distribution p(h) on H. a loss function f: xxXX real numbers ō E (0, 1) and X >>0 O. With probability at least 1 - 8 over the random draw of S SSni the following holds for any conditional posterior q(h(x) such that Assumption is satisfied by q(llx) and with constant
K > 0:
AK Σ
E E ((1,x) x 1owa(h x)
E ((b,,x)) S X hmg(t//x))
KT (L (lp()))))))))))))))))))))))))))) +
E d(x, x:) + xrp
1 + log
e (Bat x1xx)) ((1x)))))
log g
E
E x-
hwwp(h)
In order to prove Theorem 3.1, we start by deriving a bound where the expected loss for samples x f is computed w.r.t. distributions g(h(x;) associated to the training samples (see Lemma 1). This result uses standard PAC-Bayesian techniques, with a key difference: we start with n iid hypotheses from the prior p(h), then we perform the change of measure with n posteriors du (z) (xlx)).....4. (2((2)x)) and show that the resulting exponential moment is equal the one in Theorem 3. Moreover, one of the original aspects of this work comes from Assumption 1, which enables us to obtain a bound where the expected loss for x ~ p is computed w.r.t. the posterior g(h) x), associated x itself instead of all the training samples. However, the price to pay for having a posterior (h(xx) for each x E X' is that the bound depends on E Ex (xx, x,), which we refer to as the average distance.
dd is a pseudo- pssudo-metric in the general case, so we abuse the definition by calling this Lipschitz continuity, since the latter concept is only defined for metric spaces.
5

---

Applied to supervised learning, Theorem 3.1 bounds the expected risk of Gibbs posterior which, upon receiving a previously unseen datapoint x lA, samples a predictor dependent on x. and uses it to make prediction. Note that the family & from Assumption 1 does not appear in the bound, which has nice consequences practice. Indeed one may pick loss function & that fits the problem, and then find a family & for which the continuity assumption is satisfied with constant K that is as small as possible.
Note also that, in the tradition of PAC-Bayesian bounds, Theorem 3.1 does not make any assumptions on the nature of the elements of H. (e.g. H. could be a class of functions, a set of neural network's 's parameters, etc). Therefore, the theorem is very general and could be applied to different domains and models. In the following sections, we will use a specific kind of hypothesis class 2, in order to capture the VAE's latent space.
Generalization bounds for the Reconstruction Loss
For the remainder of this work, ||-I| denotes the L2 norm, and we assume the instance space X' is Euclidean, and the latent space Z [ddz where dz > Both X and 2 are equipped with the Euclidean distance as the underlying metric. Therefore, if x, x' E X, d(x, x') = ||x x'|.-
The following assumption states that the encoder and decoder networks have finite Lipschitz norms. Assumption 2. The encoder and decoder are Lipschitz-comtinuour w.r.t their inputs, meaning there cxist real numbers K Kg > 0 such that for any X1 X2 E and zz, Z2 E Z.
11Q (x1) - Qs (xe )1 - K || X2ll
(4)
and
(1 go(2))ll S Ko ||z|
z2ll
(5)
Recall the definition of Qa from Equation (2). Note that in practice, one can estimate the Lipschitz constant of trained networks (Fazlyab et al., 2019; Latorre al., 2020) train the VAE with preset Lipschitz constants (Barrett et al., 2022).
Moreover, we define the reconstruction loss e with the L2 norm, instead of the squared L2 norm, which enables to exploit the properties of metric. We discuss this choice in Section 6. In order to be consistent with the PAC-Bayesian framework, we define the loss function as follows: 69 2 x X oo),
(z, x)
|x
go [z)ll--
Our goal is apply the general bound of Theorem 3.1 the VAE model. But first, since Theorem 3.1 requires Assumption I to be satisfied, we start by showing that if the encoder and decoder networks have finite Lipschitz norms, then Assumption holds.
Proposition 4.1. Consider a VAE with parameters ó and 0 and let Kş, Kg be the Lipschitz norms of the encoder and decoder respectively. Then the variational distribution a (z(z))) satisfies Assumption 1, with È = {f Z + R s.t. If < Ko). e= = and K =
=K KgKg.
Proof idea. The proof of Proposition 4.1 is in Appendix C, we provide brief summary here. To prove the first part of Assumption I, we first notice that & is the set of real-valued Ka-Lipschitz continuous functions, then de is scaling of the Wasserstein distance. In addition, since W1 W using the closed form of the Wasserstein-2 distance between Gaussian distributions, one can show that de [x1). g (-(xx) < Ko ||x] xxll- Finally. the second part of the assumption is consequence of the definition of the loss function and the Lipschitz continuity of the decoder. [
Proposition 4.1 tells that Assumption holds for VAEs. Consequently, we can utilize our general bound of Theorem 3.1 to obtain generalization guarantees. This leads the following general PAC-Bayesian bound for the VAE's reconstruction loss.
Theorem 4.2. Let X be the instance space, μ E M2 (X) the data- gentrainnn distribution, Z the latent space, p(z) E M (2) the prior distribution the latent space, 0 the decoder's parameters,

---

E 10, O be real numbers. With probability at least 1 - over the random draw of S ~ p the following holds for any posterior (z(z(x)
E
E
mc (z,
E 4o (2/xx)
eo 2, (1) +
Σ KL (g (z)
2o (x)
E d(x, x;) + log 3 + n nlog
I
E
(p
x=-p(x)
Xrups
where Kg and Ko are the Lipschitz norms of the encoder and the decoder (see (4) and (5)) and (x)()) is a shorthand for Ex--ng (x)x))
Note that the choice of the hyperparameter 3 in the VAE's optimization objective (3) correlates with the choice of the hyperparameter À in Theorem 4.2 (e.g. À = n corresponds to 3 = 1). Note also that
the encoder and decoder are not treated the same way in Theorem 4.2. Indeed, the inequality holds for given decoder, but uniformly for any encoder. We discuss this subtle difference and its practical consequences in Section 6.
Theorem 4.2 can be seen as a general framework. In order to obtain a useful upper bound, one needs to bound the average distance and the exponential moment on the right-ham side. In the sections below, we provide upper bounds for these terms under various assumptions on the instance space.
4.1 Reconstruction Guarantees for Bounded Instance Spaces
In the following theorem, we provide a special case of Theorem 4.2 when the instance space's diameter A def suPx,x'xx d(xx x') is finite (see Section C.2 for the proof).
Theorem 4.3. Let X be the instance space, A oo its diameter, μ E (X) the data generating distribution, Z the latent space. p(z) Mr (Z) the prior on the latent space, the decoder's 's parameters, å E (0, 1), > be real numbers. With probability at least - over the random draw of S ~ 0n, the following holds for any posterior (z(2)x):
E
e Tec
2
2 (2, (0(2))))
+
1 A
Σ KL (go [[]()) +
(x
π
AKgKo + log
8n
The left-hand side of this inequality is the expected reconstruction loss for samples x ~ while the right-hand side is the empirical reconstruction and KI. losses, plus additional term depending on the Lipschitz constants of the VAE and the model's s diameter.
Note that for real-life datasets, the diameter of the instance space might be very large and non- representative of the structure and complexity of the data. Indeed, is common to scale image datasets in order utilize specific architecture (Radford et al., 2016). In the following section, provide a special case Theorem 4.2 under the manifold hypothesis on the data data-generating process.
4.2 Reconstruction Guarantees under the Manifold Assumption
The manifold assumption (Fodor, 2002; Narayanan and Mitter, 2010; Fefferman et al., 2016) states that most high- dinenmiieiinlll datasets encountered in practice lie close to oiw-dinnsiioal manifolds. This assumption is exploited by latent variable generative models such as GANs and VAEs, which approximate high-dimensional datasets using transformations of distributions space. The works of Schreuder et al. (2021) and Mbacke et al. (2023) provide generalization bounds for GANs, by assuming that the data-generating distribution is smooth transformation of the uniform distribution on [0, 1]dd, where d' is the intrinsic dimension. However, since the standard VAE calls for a standard Gaussian prior, in the following theorem, we assume μ is a smooth transformation of the standard Gaussian distribution p" on Rdd We consider the case when p* is the uniform distribution on [0, 1]dd in the supplementary material.
ciw-dimensional
7

---

Theorem 4.4. Let X be the instance space, μ (x) the data generating distribution. Z the latent space, p(z) E M4 (2) the prior distribution on the latent space, 0 the decoder's parameters, 8 E (0. 1).1 0 > real numbers. Assume the data- teattaagnertinnggg distribution μ = 9 tp", where p" the standard Gaussian distribution on Rd and g" E Lipp.. (R. ,X). With probability at least
1 1-5 5-5- nd" c=a²12 12 over the random draw of 5 n the following holds for any posterior go (z)x)))
E E
lec (2, x)
E (o(2)x))
Ged (2, xi)
1
Σ
(T((g(2(xx)) p(())
xm qo (2/x)
n
KK (1 a2 + log 1
A²
2n
Let us clarify the role of the new parameter a > O. Each training sample x; E S can be expressed as x; = 9 (w:), where w; ~ p"" Since p" is the standard Gaussian distribution on Rd all samples w; will be inside a hypercube [-a, a] with high probability. This uncertainty is reflected in the lowered confidence (from 1 - ô in Theorem 4.2 to 1 8 nd a-2/22 in Theorem 4.4), and can be controlled by choosing a large enough value of a. The proof of Theorem 4.4 is in the supplementary material (Section C.3), provide short summary below.
e
Proof idea. The proof starts with Theorem 4.2, and uses the assumptions of Theorem 4.4 to obtain upper bounds on the exponential moment and the average distance. To derive the upper bound on the exponential moment, we observe that the function z + (z. x) is K, -Lipschitz continuous, then we a dimension-free upper bound the MGF of Lipschitz-continuous functions of Gaussian random variables. Furthermore, we obtain the upper bound on the average distance 1 >'= Ex- ||x x;Il- by using Holder's inequality and the expectation of a non-central x² distribution. Then, we upper- bound the probability that w, E [-a,a]] al" for all S i I n using the error function and Bernoulli's inequality. Finally, use the union bound to update the overall confidence.
5 Generalization Bounds for Regeneration and Generation
Let ú0,00 be the empirical regenerated distribution, meaning
P + E golgo(
In other words, sampling Pa.e is done by sampling (z(()x)) ) where i is uniformly sampled from {l.....n. n). then passing z through the decoder: x = go (z). It is therefore the distribution regenerated by the VAE, given the training set S = (....... x,, input.
In this section, we provide statistical guarantees on the regenerative and generative properties of VAES. More precisely, we derive upper bounds for the quantities W1 (n. Po.0) and (1,,, gotp(z)). Note that the average distance term does not appear the bounds of this section. This is because instead of relying Theorem 3.1, the results of this section depend upon preliminary lemma (Lemma B. l), which does not necessitate Assumption 1.
5.1 Regeneration and Generation Guarantees for Bounded Instance Spaces
The following theorem presents our first upper bound on the distance between the input distribution and the empirical regenerated distribution.
Theorem 5.1. Under the definitions and assumptions of Theorem 4.3, we have that with probability at least 5 over the random draw of S ~ n the following holds for any posterior qo (z)x)):
Wi S
& (Z, xi) + (o(2)x))
(L + log 3 +
8n
As we can see, the right-hand side of Theorem 5.1 depends on the empirical reconstruction loss and Kl.-divergence. This guarantees that as the VAE's empirical risk decreases, the regenerated distribution gets closer to the data- getereeennating distribution. The proof of Theorem 5.1 exploits the fact
8

---

that the underlying metric on X' is the Euclidean distance x(x,x') ||x -x'Ii,,, define the reconstruction loss f (see Equation 6). The full proof can be found in Appendix D.
x'I,, ||, which is also used to
The following theorem provides upper bound of the distance between the input distribution and the VAE's generated distribution.
Theorem 5.2. Under the definitions and assumptions of Theorem 4.3, we have that with probability at least å over the random draw of S ~ u the following holds for any posterior go (z(z)x);
Wi (1(,1900p(2) -
E (0(x)(x))
E (2)
(2 (l(()))
1
A
K
|Ime (x;))1 + ox (x:) - -1|
log
8
8n
==1
where T E TRd2 denotes the vector whose entries are all 1.
The right-hand side of Theorem 5.2 is equal to the right-hand side of Theorem 5.1, plus additional term depending on the Wasserstein-2 distance W2(1s (z xx), p(z)) which is used the proof because of its closed form for Gaussian distributions. Hence, the right-hand side of Theorem 5.2 augments the VAE's optimization objective with W2 (z)gx(z)x, p(z)). suggesting that a good generative perfor- mance may require the latent codes to be even closer to the prior. This is consistent with the findings of Zhao et al. (2019), who showed that in order to improve generative performance, the latent codes need to be much closer to the prior, which may disrupt the balance between reconstruction loss and KL-loss.
5.2 Regeneration and Generation Guarantees under the Manifold Assumption
Similar to what we did in Section 4.2, we assume that the sata-gennrattig distribution is a smooth transformation of the standard Gaussian distribution on Rdd", where d' is the intrinsic dimension of the dataset. This yields the following results.
Theorem 5.3. Under the definitions and assumptions of Theorem 4.4, with probability at least 1 - 6 over the random draw of S s the following holds for any posterior (z(z)))
x²
W (o, I
Che (2. xi)
(L((g(2)x,) 11 p()) + log
(0(3)x))
2n
Note that the intrinsic and extrinsic dimensions do not explicitly appear in this inequality, although they may affect the reconstruction and KL. loss.
We now present our last result, an upper bound on the Wasserstein distance between the input distribution and the VAE's generated distribution, under the manifold assumption.
Theorem 5.4. Under the definitions and assumptions of Theorem 4.4, with probability at least 1 over the random draw of S n the following holds for any posterior (z)x)))
W1 W1 gz)p(z))
1
E
el
(Z,
x.)
1 A
KL(g,(Z|x;) (l
n
(2/2x)
A²K2
Ko
lime (x:))12 (0o 11(
log
2n
n
where I E dR denotes the vector whose entries are all 1.
Theorem 5.2 and Theorem 5.4 show that by minimizing the VAE's objective, one is also minimizing the Wasserstein distance between the input distribution and the VAE's generated distribution.
From the upper bounds given by Theorems 5.1 and 5.3, one can deduce rates of convergence of O(2-1/2) (when À / n) for the empirical regenerated distribution. Note that À leads to the much faster rate of n but then the bounds do not converge to the empirical risk, but to a larger the input distribution. Similarly, Theorems 5.2 and 5.4 provide rates
positive number, dependent of convergence of O(n -1/2) for the VAE's generated distribution.

---

Discussion and Conclusion
The different treatments of 0 and Φ. The bounds we've presented in this work hold for given decoder 0, but uniformly for all encoders. In practice, this means that the risk certificate has to be computed using samples different from the ones used to train the VAE. This is different from the usual PAC-Bayesian trick (Germain et al., 2009;
et al., 2012; Pérez-Ortiz et al., 2021, see also Remark F.2) of splitting the training set to learn the prior, then training the model on the whole training set, because the decoder and encoder are jointly optimized. Instead, one has to make sure that the model is only trained on samples distinct from the ones used to compute the bound. The
method would be necessary when computing the risk certificates given by the recent Ba-yssy bounds of Rivasplata et al. (2020) and Haddouche and Guedj (2022), since those bounds are not uniformly valid for any posterior.
The reconstruction loss. In our bounds, the reconstruction loss is the Lg norm (RMSE), instead of the squared L2 norm (MSE). In practice, one can still optimize VAE with the MSE (or any other reconstruction loss, e.g. the cross entropy loss), and then compute the bounds using the RMSE. However, if the reconstruction loss not the RMSE, then the optima of the chosen optimization objective might differ from the ones minimizing the right-hand side of the bounds. Therefore, if the goal is to minimize the bounds, one should utilize the RMSE as the reconstruction loss.
Conclusion. It is common, when applying PAC-Bayesian theory to new problems, add additional stochasticity in order to account for the PAC-Bayesian distributions on the hypothesis class. For instance, Mbacke et al. (2023) added distributions the parameters of WGAN's generator, in order to perform a PAC-Bayesian analysis. However, because of the seamless integration of the PAC-Bayesian and VAE frameworks, such modification to the original problem has been avoided in this work. We matched the prior and posterior distributions on the VAE's latent space to the PAC-Bayesian prior and posterior, which allowed us recover the VAE's optimization objective. We provide preliminary experiments on synthetic datasets in the supplementary material.
This work is humble contribution to the theoretical understanding of VAEs. We developed novel PAC-Bayesian bounds suited to the analysis of VAFs and provided generalizations bounds for the also derived upper bounds the Wasserstein distance
VAE'S reconstruction loss. In addition, between the input distribution and the VAE's generative model's distribution. These bounds depend on the VAB's empirical optimization objective and the data-generating process. By integrating the VAE and PAC-Bayesian frameworks, we hope to establish PAC- FAC-Bayesian theory as a prime tool for the theoretical analysis of VAEs.
Acknowledgements
This research is supported by the Canada CIFAR AI Chair Program, and the NSERC Discovery grant RGPIN-2020- 07223. F. Clerc is funded by IVADO through the DEEL Project CRDPJ 537462 18 and by grant from NSERC.
References
Alquier, P. (2021). User-friendly introduction to PAC-Bayes bounds. arXiv:2110.11216.
arXiv preprint
Amit, R. and Meir, R. (2018). Meta-learning by adjusting priors based on extended PAC-Bayes theory. In International Conference on Machine Learning, pages 205-214. PMLR.
An, J. and Cho, S. (2015). Variational autoencoder based anomaly detection using reconstruction probability. Special Lecture on IE, 2(1):1-18.
Anil, C., Lucas, J., and Grosse, (2019). Sorting out Lipschitz function approximation. In International Conference Machine Learning, pages 291-301. PMLR.
Arjovsky, M., Chintala, S., and Bottou, L. (2017). Wasserstein generative adversarial networks. In International Conference Machine Learning, pages 214-223, PMLR.
10

---

Arora, S., Ge, R., Liang, Y., Ma, T., and Zhang, Y. (2017). Generalization and equilibrium in generative adversarial nets (GANs). In International Conference on Machine Learning, pages 224-233 PMLR.
Barrett, B., Camuto, A., Willetts, M., and Rainforth, T. (2022). Certifiably robust variational autoencoders. In International Conference on Artificial Intelligence and Statistics, pages 3663- 3683. PMLR.
Biau, G., Sangnier, M., and Tanielian, U. (2021). Some theoretical insights into Wasserstein GANs. Journal of Machine Learning Research.
Björck, Å. and Bowie, C. (1971). An iterative algorithm for computing the best estimate of an orthogonal matrix. SIAM Journal on Numerical Analysis, 8(2):358-364,
Boucheron, S., Lugosi, G., and Massart, P. (2013). Concentration inequalities: A nonasymptotic theory of independence. Oxford university press.
Bowman, S. R., Vilnis, L., Vinyals, O., Dai, A. M., Józefowicz, R., and Bengio, S. (2016). Generating sentences from continuous space. In Conference on Computational Natural Language Learning. CoNLL, pages 10 10-21. ACL.
Catoni, O. (2003). A PAC- PAC-Bayesian approach to adaptive classification. preprint LPMA, 840.
Chakrabarty, and Das, S. (2021). Statistical regeneration guarantees of the Wasserstein autoencoder with latent space consistency. In Advances in Neural Information Processing Systems.
Chérief-Abdellatif, B.-E., Shi, Y., Doucet, A., and Guedj, B. (2022). On PAC-Bayesian reconstruction guarantees for VAEs. In International Conference on Artificial Intelligence and Statistics, pages 3066-3079. PMLR.
Chu, T. (1955). On bounds for the normal integral. Biometrika, 42(1/2):263-265.
Donsker, M. D. and Varadhan, S. S. (1976). Asymptotic evaluation of certain markov process expectations for large time-iii. Communications pure and applied Mathematics, 39)4)389 461.
Dziugaite, G. K. and Roy, D. M. (2018). Data-dependent PAC-Bayes priors via differential privacy. In Advances in Neural Information Processing Systems, volume 31.
Fazlyab, M., Robey, A., Hassani, H., Morari, M., and Pappas, (2019). Efficient and accurate estimation of Lipschitz constants for deep neural networks. In Advances in Neural Information Processing Systems, volume 32.
Fefferman, C., Mitter, S., and Narayanan, H. (2016). Testing the manifold hypothesis. Journal of the American Mathematical Sociery, 1944
Fodor, I. K. (2002). survey of dimension reduction techniques. Technical report, Lawrence Livermore National Lab.. CA (US).
Germain, P., Bach, F., Lacoste, A., and Lacoste-Julien, S. (2016). PAC-Bayesian theory meets Bayesian inference. Advances in Neural Information Processing Systems, volume 29.
Germain, P., Habrard, A., Laviolette, F,, and Morvant, E. (2020). PAC-Bayes and domain adaptation. Neurocomputing. 379:379-397.
Germain, P., Lacasse, A., Laviolette, F., and Marchand, M. (2009). PAC-Bayesian learning of linear classifiers. In International Conference Machine Learning, page 353-360.
Givens, C. R. and Shortt, R. M. (1984). A class of Wasserstein metrics for probability distributions. Michigan Mathematical Journal, 31(2):231-240.
Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. (2014). Generative adversarial nets. Advances Neural Information Processing Systems, volume 27.

---

Grünwald, P. (2012). The safe Bayesian learning the learning rate via the mixability gap. In Algorithmic Learning Theory, volume 7568 of Lecture Notes Computer Science, pages 169-183. Springer.
Guedj, B. (2019). A primer on PAC-Bayesian learning. In Proceedings of the French Mathematical Society, volume 33, pages 391 1-14. Société Mathématique de France.
Haddouche, M. and Guedj, B. (2022). Online PAC-Bayes learning. In Advances in Neural Information Processing Systems.
Higgins, I., Matthey, I.., Pal, A., Burgess, C., Glorot, X., Botvinick, M., Mohamed, S., and Lerchner, A. (2017). heta-VAF; Learning basic visual concepts with a constrained variational framework. In International Conference on Learning Representations.
Kaur, D., Islam, S. N., and Mahmud, M. (2021). variational autoencoder- based dimensionality reduction technique for generation forecasting in cyber-physical smart grids. In 2021 IEEE International Conference on Communications Workshops (ICC Workshops), pages 1-6. IEEE.
Kingma, P., Mohamed, S., Jimenez Rezende, D., and Welling, M. (2014). Semi-supervised learning with deep generative models. In Advances in Neural Information Processing Systems, volume 27.
Kingma, D. P. and Welling, M. (2014). Auto-encoding Variational Bayes. In International Conference on Learning Representations.
Langford, J. and Caruana, R. (2001). (not) bounding the true error. In Advances in Neural Information Processing Systems, volume 14.
Latorre, F., Rolland, P., and Cevher, V. (2020). Lipschitz constant estimation of neural networks via sparse polynomial optimization. International Conference on Learning Representations.
Liang, T. (2021). How well generative adversarial networks learn distributions. Journal of Machine Learning Research, 22((28):1-41.
Mbacke, S. D., Clerc, F., and Germain, P. (2023). PAC-Bayesian generalization bounds for adversarial generative models. In International Conference on Machine Learning, volume 202, pages 24271- 24290. PMLR.
McAllester, D. A. (1999). Some PAC-Bayesian theorems. Machine Learning, 37(3):355-363
McAllester, D. A. (2003). PAC-Bayesian stochastic model selection. Machine Learning, 51(1):5-21.
Mitrinovic, D. S. and Vasic, P. M. (1970). Analytic inequalities, volume 1. Springer.
Müller, A. (1997). Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2):429 443.
Narayanan, H. and Mitter, S. (2010). Sample complexity of testing the manifold hypothesis. In Advances in Neural Information Processing Systems, volume 23.
Hurrado-Heráánee E., Ambroladze, A., Shawe- Shawe-Taylor, J., and Sun, S. (2012). PAC- MAC-Bayes bounds with data dependent priors. Journal of Machine Learning Research, 13(1):3507-3511
Pérez-Ortizz M., Rivasplata, O., Shawe- Taylor, J., and Szepesvári, C. (2021). Tighter risk certificates for neural networks. Journal of Machine Learning Research, 22.
Petersen, K. B. and Pedersen, M. S. (2008). The matrix cookbook. Version 20081110
Radford, A., Metz, L., and Chintala, S. (2016). Unsupervised representation learning with deep convolutional generative adversarial networks, In International Conference on Learning Represen- tations.
Rezende, D. J., Mohamed, S., and Wierstra, D. (2014). Stochastic backpropagation and approximate inference in deep generative models. International Conference on Machine Learning, pages 2278-1286 PMLR.
12

---

Rivasplata, O., Kuzborskij. L,, Szepesvári, C., and Shawe-Taylor J. (2020). PAC-Bayes analysis beyond the usual bounds. In Advances Neural Information Processing Systems, volume 33, pages 16833-16845.
Schreuder, N., Brunel, V.-E., and Dalalyan, A. (2021). Statistical guarantees for generative models without domination. In Algorithmic Learning Theory, pages 1051-1071. PMLR.
Seeger, M. (2002). PAC-Bayesian generalisation error bounds for Gaussian process classification. Journal of Machine Learning Research, 3(Oct):233-22) 269.
Seldin, Y. and Tishby, (2010). PAC-Bayesian analysis of co-clustering and beyond. Journal of Machine Learning Research, 11(12).
Singh, S., Uppal, A.. Li, B., Li, C.-L., Zaheer, M., and Póczos, B. (2018). Nonparametric density estimation under adversarial losses. In Advances Neural Information Processing Systems, volume 31.
Thiemann, N., Igel, C., Wintenberger, O., and Seldin, Y. (2017). A strongly quasiconvex PAC- Bayesian bound. International Conference on Algorithmic Learning Theory, volume 76, pages 466-492. PMLR.
Tolstikhin, I., Bousquet, O., Gelly, S., and Schoelkopf, B. (2018). Wasserstein auto-encoders. In International Conference on Learning Representations.
Vahdat, A. and Kautz, J. (2020). NVAE: A deep hierarchical variational autoencoder. In Advances in Neural Information Processing Systems, volume 33, pages 19667-19679.
Villani, C. (2009). Optimal transport: old and new, volume 338. Springer.
Zhang, P., Liu, Q.. Zhou, D., Xu, T., and He, X. (2018). On the in GANs. In International Conference Learning Representations.
tradeoff
Zhao, J., Mathieu, M., and LeCun, Y. (2017). Energy-based generative adversarial networks. In International Conference on Learning Representations.
Zhao, S., Song, J., and Ermon, S. (2019), Info Balancing learning and inference in variational
autoencoders. In AAAI Conference on Artificial Intelligence, volume 33, pages 5885-5892.
13


Reviews:
[{"review_id": "sFKBG9LQvg", "reviewer": "Reviewer_sohu", "summary": "【Post-rebuttal Comments】\nI thank the authors for the discussions after the authors' rebuttal. My questions about variance estimation are appropriately answered. So, I want to keep my score and vote for acceptance.\n\n【Original Comments】\nThis paper derives the PAC-Bayes bound on the hypothesis set by conditional distributions (Theorem 3.1). As an example of its application, this paper gives three kinds of generalization bounds for Variational AutoEncoder by interpreting its encoder as a hypothesis set. Specifically, this paper provides guarantees for the reconstruction of data points (Theorem 4.3), the regeneration of data distributions (Theorem 5.1), and the generation from prior distributions (Theorem 5.2). Furthermore, by assuming the manifold hypothesis for the input distribution, sharper bounds are derived that depend on the manifold's dimension rather than the input dimension (Theorem 4.4, Theorem 5.3, Theorem 5.4).", "questions": "By applying uniform concentration inequality with respect to the decoder parameters (more specifically, the family of loss functions parametrized by the decoder), can we give uniform bound with respect to the decoder parameters at the cost of worsening the sample size rate?\n\nl.134: iid -> i.i.d.", "limitations": "This paper discusses limitations in Section 6: (1) the parameters of the decoder are fixed in the derived bounds, and (2) the L1 loss is used as the reconstruction loss instead of the commonly used L2 loss (this is equivalent to modeling the decoder as the Laplace distribution instead of the Gaussian distribution).\n\nAnother limitation is that the VAEs used in this analysis have a fixed decoder variance (l.116). If I do not miss any information, it is not discussed whether we can extend the obtained bounds to VAEs that also estimate variance.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Instead of simply applying the existing PAC-Bayes bound, this paper derives PAC-Bayes bounds for the posterior distribution conditioned on samples drawn from the data distribution. They are novel from the perspective of statistical learning theory, verified by the comparison with existing work on the PAC-Bayes bound for conditional distributions (Rivasplata et al. (2020)) and generalization bound for VAE (Chakrabarty and Das, 2021 and Cherief-Abdellatif et al., 2022).\n- Many generalization bounds for VAE are systematically derived from a single PAC-Bayes bound, showing its generality.\n- The paper is well-written. Both the organization and mathematical descriptions of the paper are appropriate. I had no significant difficulties in reading the paper.", "weaknesses": "- The obtained bounds are not uniform with respect to decoder parameters. This restriction affects the sample size rate of the bounds: If I understand correctly, the O(1/n) terms in the upper bounds come from the fact that the decoder is a single hypothesis so that the (non-uniform) Hoeffding bound can be applied.\n- The decoder outputs mean parameters only, and the variance of the distribution modeled by the decoder is fixed. This architecture is different from the one we often use practically.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we thank the reviewer for their thoughtful review and insightful comments.\n\n> By applying uniform concentration inequality with respect to the decoder parameters (more specifically, the family of loss functions parametrized by the decoder), can we give uniform bound with respect to the decoder parameters at the cost of worsening the sample size rate?\n\nIt is possible to obtain a uniform bound with respect to the decoder's parameters $\\\\theta \\\\in \\\\Theta$, if we assume $\\\\Theta$ is finite. In this case, the union bound leads to a penalty of $\\\\log \\\\lvert \\\\Theta \\\\rvert$. The problem with this is that since $\\\\Theta$ is a set of neural network parameters, this assumption may not be accurate unless $\\\\lvert \\\\Theta \\\\rvert$ is very large, which may significantly worsen the bound. \n\nRegarding uniform concentration inequalities, we believe their usage would require some assumption on the complexity of $\\\\Theta$, and we do not believe the problem to be straightforward. We agree with the reviewer that obtaining uniform bounds w.r.t. $\\\\theta$ is important, and we plan on exploring that in future works.\n\nWe also mention that the non-uniformity w.r.t. $\\\\theta$ is due to the fact that in general, PAC-Bayes considers a single loss function, and in this case, the loss function depends on the decoder's parameters.\n\n> the VAEs used in this analysis have a fixed decoder variance (l.116). If I do not miss any information, it is not discussed whether we can extend the obtained bounds to VAEs that also estimate variance.\n\nIndeed, the variance of the decoder is fixed, and there is a way to extend the results to optimize the variance as well. Assuming the standard deviation $\\\\sigma$ is constant, our bounds yield $\\\\sigma \\\\propto \\\\frac{n}{\\\\lambda}$ (because in our expressions, the sum of KL divergences is only divided by $\\\\lambda$, whereas it is usually divided by $n$ as well). Hence, optimizing the decoder's variance $\\\\sigma^2$ is equivalent to optimizing the hyperparameter $\\\\lambda$, which can be done for PAC-Bayes bounds, but at a cost.\n    \nMost PAC-Bayes bounds (including ours) do not directly allow one to optimize $\\\\lambda$ (see Section 2.1.4 of Alquier, 2021 and references therein). And, although there are some ways around this restriction, we are not aware of any results that allow one to optimize $\\\\lambda$ in the general case (meaning continuous $\\\\lambda$ and unbounded loss). If the loss function is $[0, 1]$-bounded, [1] developed a PAC-Bayes bound uniformly valid for a trade-off parameter $\\\\lambda' \\\\in (0, 2)$. For unbounded losses, if one assumes $\\\\lambda \\\\in \\\\Lambda$, where $\\\\Lambda$ is finite, a union bound argument allows one to make the bound uniform with respect to $\\\\lambda \\\\in \\\\Lambda$, at the cost of $\\\\log \\\\lvert \\\\Lambda \\\\rvert$. One can still optimize with respect to a continuous set $\\\\Lambda$, by replacing $\\\\lambda$ with $\\\\lfloor \\\\lambda \\\\rfloor$. So, for instance, if $\\\\Lambda = [1, n]$, and we replace $\\\\lambda$  with $\\\\lfloor \\\\lambda \\\\rfloor$, the penalty is $\\\\log n$. \n\nIn summary, we can use the union bound to extend our results to VAEs that estimate the variance of the likelihood. This extension comes with a penalty depending on the size of the chosen space. We will mention this in the main paper, and add some formal details in the supplementary material.\n\n[1] A strongly quasiconvex PAC-Bayesian bound. Thiemann, N. and Igel, C. and Wintenberger, O. and Seldin, Y.; International Conference on Algorithmic Learning Theory 2017\n\nOnce again, we thank the reviewer for their hard work and interesting questions. We hope that the reviewer finds our answers satisfactory, and we will happily answer any further questions.\n"}, {"review_id": "RCzN4hoWXF", "reviewer": "Reviewer_8cep", "summary": "In this paper, the authors provide a novel general PAC-Bayesian bound for a posterior distribution conditioned on individual elements of the instance space (and not only on observed samples). They then use it to derive generalization bounds for reconstruction loss, regeneration, and generation in VAE (both for bounded instance space and under the manifold assumption).", "questions": "Minor comments:\n\nl. 46: I would be careful about calling WAE a variant of VAE.\n\nl. 92: $p\\ll q$ could be explained.\n\nl. 106: Is \"data generating distribution\" the same as \"input distribution\"?\n\nl. 134: footnote character '1' should be before a comma.\n\nl. 170 (bottom): ',' --> '.'.\n\nl. 192: '.' --> ':'.\n\nl. 219: \"exists\" --> \"exist\".\n\nl. 289: Is the word \"uniform\" necessary here?\n\nl. 321, 327: Add ':' at the end of the line.", "limitations": "The authors adequately addressed the limitations of the paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The results of the paper appear to be original and significant. As the authors claim, this is probably the first work that provides statistical guarantees for VAE.\n\n2. The paper is clearly written, so it is easy to understand.\n\n3. The paper contains a formal theoretical analysis and an intuitive discussion of assumptions and results.", "weaknesses": "1. Perhaps the main weakness is the lack of experimental results. However, I am not sure they are necessary (compare, e.g., with the related work [1]).\n\n[1] Chakrabarty, A. and Das, S. (2021). Statistical regeneration guarantees of the Wasserstein autoencoder with latent space consistency. In Advances in Neural Information Processing Systems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and thoughtful suggestions, which will help us improve the paper. \n\n> Perhaps the main weakness is the lack of experimental results. However, I am not sure they are necessary (compare, e.g., with the related work [1]) \n\nIndeed, the main objective of this work is theoretical. [1] present asymptotic bounds on the regeneration properties of WAEs, while our bounds are empirical, and cover the reconstruction, regeneration, and generation properties of VAEs. We also address the question of the experiments in our general response.\n\n> I would be careful about calling WAE a variant of VAE.\n\nWe understand how this could be bothersome. We will rewrite that sentence accordingly.\n\n> l. 106: Is \"data generating distribution\" the same as \"input distribution\"?\n\nYes, they are the same thing. Both designations refer to the distribution later denoted $\\mu$.\n\n> l. 289: Is the word \"uniform\" necessary here?\n\nYes, it is necessary, and we agree that the sentence is a bit ambiguous. Here, the word \"uniform\" refers to the choice of $ i \\\\in \\\\{1, \\\\dots, n \\\\}$, such that the distribution $q\\_\\\\phi(\\\\mathbf{z} | \\\\mathbf{x}\\_{i} )$ is used to sample $\\\\mathbf{z} \\\\sim q\\_\\\\phi(\\\\mathbf{z} | \\\\mathbf{x}\\_i)$. \nIn other words, it is not $\\\\mathbf{z}$ that is sampled \"uniformly\", but $ i \\\\in \\\\{ 1, \\\\dots, n \\\\} $ that is sampled uniformly, since all the coefficients in the empirical regenerated distribution are equal to $\\\\frac{1}{n}$. We will reformulate the sentence to eliminate the ambiguity.\n\nOnce again, we thank the reviewer for their hard work. We are grateful for the reviewer's suggestions, and will use them to improve the manuscript.\n\n"}, {"review_id": "Mei8TjclxW", "reviewer": "Reviewer_3pjC", "summary": "This paper derives novel PAC-Bayesian bounds for VAEs by treating the variational posterior as the PAC-Bayes posterior. To do this, the authors must adapt the PAC-Bayes theorem to also hold in the case where the posterior is conditioned on a learning sample.", "questions": "- Have the authors tried numerically computing these bounds in any situations? How tight are they? How far are they from being non-vacuous?", "limitations": "The authors describe the limitations well in their Discussion and Conclusion section, which is well-written and insightful.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Well-written paper, with well presented results\n- Limitations clearly stated without exaggeration\n- Clearly addresses an important theoretical topic\n- Novel theoretical results", "weaknesses": "- Bound unfortunately needs to be computed using samples different from those used to train the VAE. This runs counter to one of the most interesting and useful aspects of PAC-Bayes bounds - that they can be used as learning objectives.\n- The bounds are not numerically computed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments and their appreciation of our theoretical contributions.\n\n> Bound unfortunately needs to be computed using samples different from those used to train the VAE. This runs counter to one of the most interesting and useful aspects of PAC-Bayes bounds - that they can be used as learning objectives.\n\nThe reviewer is right. As mentioned in the conclusion, the bounds need to be computed using a set of samples disjoint from the training set. We note that since the results in Section 5 provide upper bounds on the Wasserstein distance between distributions on (possibly) high-dimensional spaces, having empirical upper bounds may still be very useful, because of the difficulty of estimating the Wasserstein distance in high dimension in the general case. \n\n> Have the authors tried numerically computing these bounds in any situations? How tight are they? How far are they from being non-vacuous?\n\nWe are currently working on experiments on synthetic datasets, and we will add the results to the manuscript. We also address the question of the experiments in our general response. \n\nOnce again, we thank the reviewer for their hard work and insightful review."}, {"review_id": "evO7Wf0KLS", "reviewer": "Reviewer_Hutj", "summary": "The paper introduces generalization bounds for variational autoencoders (VAEs) by employing PAC-Bayesian bounds. Initially, the authors derive a PAC-Bayesian bound utilizing a posterior distribution (Theorem 3.1). This result is subsequently utilized to establish a generalization bound for the reconstruction loss (Theorem 4.2) and the generated distribution of the VAE (Theorem 5.1). These two outcomes rely on relatively broad quantities, which are further elaborated in corollaries that incorporate additional assumptions, namely bounded instance spaces and manifold assumptions.\n", "questions": "* Does the dimension of the latent space has any direct influence on the bound, or is it present only through e.g. the space's diameter? ", "limitations": "The authors mention the limitation of their approach in the conclusion.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well written, presenting a notable and original scientific contribution to the field. The assumptions are thoroughly discussed, and despite the technical nature of the results, the authors make an effort to provide the reader with intuitive explanations, which is commendable.\n", "weaknesses": "Considering the nature of the NeurIPS conference, it would be beneficial to include an experimental section in the paper. Given its strong theoretical content, conducting experiments on synthetic problems could be valuable in assessing the asymptotic behavior of the bound concerning various parameters such as reconstruction losses, $\\lambda$, and Lipschitz constants. For example, these synthetic experiments could utilize the assumption of bounded instance space, with a 1D input space, allowing for accurate approximation of the Lipschitz constants of the models.\n\nAside from this suggestion, as I am not familiar with PAC-Bayes theory or the VAE literature, I am unable to identify any evident flaws or weaknesses in the paper that could aid the authors in improving their work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful review and positive assessment of our work.\n\n> Given its strong theoretical content, conducting experiments on synthetic problems could be valuable in assessing the asymptotic behavior of the bound\n\nGiven the technical nature of the results, our focus was on making the presentation as clear and intuitive as possible, without sacrificing mathematical accuracy. We address the question of numerical experiments in our general response. \n\n> Does the dimension of the latent space has any direct influence on the bound, or is it present only through e.g. the space's diameter?\n\nThis is a great question. Although it does not explicitly appear in the expressions, the dimension $d\\_\\\\mathcal{Z}$ of the latent space does have an influence on the bounds, because it affects both the reconstruction loss, and the discrepancy between $q\\_\\\\phi(\\\\mathbf{z} | \\\\mathbf{x}\\_i)$ and $p(\\\\mathbf{z})$. Indeed, if $d\\_\\\\mathcal{Z}$ is too small, then depending on the complexity of the encoder and decoder networks, the model may not be able to properly reconstruct the samples, which leads to larger empirical and population reconstruction losses. On the other hand, if $d\\_\\\\mathcal{Z}$ is too large, then the KL divergence may get too large as well, and if $q\\_\\\\phi(\\\\mathbf{z} | \\\\mathbf{x}\\_i)$ and $p(\\\\mathbf{z})$ are too far apart, then the upper bounds on the Wasserstein distance between $\\\\mu$ and $g\\_\\\\theta \\sharp p(\\\\mathbf{z})$ becomes larger, because they depend on the Wasserstein-2 distance between $q\\_\\\\phi(\\\\mathbf{z} | \\\\mathbf{x}_i)$ and $p(\\\\mathbf{z})$.\n\nNote that in our bounds leveraging the manifold assumption (Theorems 4.4, 5.3 and 5.4), the intrinsic dimension $d^*$ can be different from the latent dimension $d\\_\\\\mathcal{Z}$. The intrinsic dimension explicitly appears in the bound of Theorem 4.4, but not Theorems 5.3 and 5.4. This is because the upper-bound on the exponential moment is dimension-free, and the bounds of Section 5 do not depend on the average distance.\n\nWe thank the reviewer again for their hard work and insightful review.\n\n\n"}]

Author rebuttal:
We are extremely grateful to all the reviewers for taking the time to read our work and make thoughtful comments and suggestions. 

All the reviewers seem to agree that the subject of this work (extending PAC-Bayes theory to conditional posteriors and deriving statistical guarantees for VAEs) is important, and the theoretical results are novel and significant. The reviewers also seem to agree that the paper is well-written and the assumptions and results are clearly presented.

Some of the reviewers inquired about the numerical behavior of our bounds. We agree that this is an interesting question, and we are working on the implementation and some experiments on toy datasets. We will add the results to the final version of the manuscript, and the code will be publicly available. Nevertheless, we emphasize that our primary objective was to develop novel theoretical results and present them with as much clarity as possible. Given the importance of VAEs in the Machine Learning community and the lack of statistical guarantees, our goal was to establish a new theoretical framework for the analysis of the statistical properties of VAEs. We hope our work will foster new ideas and insights in the community.

Once again, we thank the reviewers for their hard work, and positive assessment of our manuscript.

Meta-review: All reviewers are excited of the novel approach and the new perspective that PAC-Bayesian theory adds to generative learning. We are excited to see this work at NeurIPS
Decision: Accept (spotlight)