Information-theoretic Generalization Analysis for VQ-VAEs: A Role of Latent Variables
Authors: Futoshi Futami
Masahiro Fujisawa
Venue: NeurIPS 2025 poster ()
Keywords: Information theoretic generalization analysis
IT analysis
generalization error analysis
VQ-VAE
vector quantized VAE
Primary area: theory
TL;DR: This study provides an information-theoretic analysis of discrete latent variables in VQ-VAEs, deriving a novel generalization error bound based on the complexity of the latent variables and encoder.

Abstract: Latent variables (LVs) play a crucial role in encoder-decoder models by enabling effective data compression, prediction, and generation. Although their theoretical properties, such as generalization, have been extensively studied in supervised learning, similar analyses for unsupervised models such as variational autoencoders (VAEs) remain insufficiently underexplored. In this work, we extend information-theoretic generalization analysis to vector-quantized (VQ) VAEs with discrete latent spaces, introducing a novel data-dependent prior to rigorously analyze the relationship among LVs, generalization, and data generation. We derive a novel generalization error bound of the reconstruction loss of VQ-VAEs, which depends solely on the complexity of LVs and the encoder, independent of the decoder. Additionally, we provide the upper bound of the 2-Wasserstein distance between the distributions of the true data and the generated data, explaining how the regularization of the LVs contributes to the data generation performance.

Information-theoretie Generalization Analysis for VQ-VAEs: A Role of Latent Variables
Futoshi Yutamii,1,2.3 Masahiro Fujisawa"
The University of Osaka,
RIKEN AIP, The University of Tokyo,
Equal Contribution
futami. www.::eeeosssssuuuaaoeaa jp, atgisaawaist..osaaauuu
Abstract
Latent variables (LVs) play a crucial role in encoder-decoder models by enabling effective data compression, prediction, and generation. Although their theoretical properties, such as generalization, have been extensively studied in supervised learning, similar analyses for unsupervised models such variational autoen- coders (VAEs) remain insufficiently explored. In this work, we extend information- theoretic generalization analysis vector-quantized (VQ) VAEs with discrete latent spaces, introducing a novel data-dependent prior to rigorously analyze the relationship among LVs, generalization, and data generation. We derive a novel generalization error bound of the reconstruction loss of VQ- VAEs, which depends solely on the complexity of LVs and the encoder, independent of the decoder. Additionally, we provide the upper bound of the 2-Wasserstein distance between the distributions of the true data and the generated data, explaining how the regu- larization of the LVs contributes to the data generation performance.
Introduction
Encoder-decoder (ED) models have demonstrated remarkable performance [23] in (un)supervised tasks such as classification [2, 4] and data generation [39, 70], compressing input data into latent variables (LVs) via encoder. The success of ED models hinges on how effectively the encoder can represent essential features of the input in LVs, stimulating analyses of the relationship between LVs and ED model performance, well developing algorithms designed to appropriately control LVs.
In supervised learning, the information bottleneck (IB) hypothesis [67, 60] has gained significant attention for proposing that minimizing the mutual information (MI) between input data and LVs enhances generalization by ensuring LVs retain the minimal information necessary for prediction. This hypothesis has motivated numerous learning algorithms for deep neural networks and empirical studies exploring their performance [66, 61, 56, 22, 1, 2]. Moreover, theoretical research about how LVs contribute to generalization has been actively pursued [71, 28, 38, 72] within the IB hypothesis. Recently, Sefidgaran et al. [57] has highlighted the limitations of these analyses, particularly in terms of assumptions and the sample complexity represented by the MI. To address these limitations, they proposed extending the supersample setting of information-theorett (IT) analysis [63]. Their approach induces symmetric, data- depende prior over LVs that facilitates rigorous analysis, which successfully characterizes generalization performance using the Hallbbcck-eebblee (KL) divergence between the posterior distribution of the LVs and this prior. These results suggest that, by carefully constructing the data-dependent prior distribution, we can obtain a decodee-indepeendent bound, which illustrates clearly how LVs contribute to the generalization for ED models in classification. Their analysis has recently been extended to multi- view learning settings [58, 59].
LVs play key role in deep generative models for unsupervised learning tasks such as data compres- sion and generation. For example, variational autoencoders (VAEs) [39] are trained by optimizing an
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

objective function that includes the KL divergence of the posterior from the prior in the LV space as regularization term. Extended methods such as 3- 3-VAE [34] highlight the importance of appropriately tuning the strength of KI. regularization to improve LV representations. Additionally, methods like vector-quantized VA (VQ-VAEs) [70], which discretize the latent space, have been developed to address posterior collapse. Numerous empirical studies have also evaluated model performance based on the MI, such as the IB hypothesis and rate-distortion theory [3, 9, 69, 12].
In contrast to supervised learning, theoretical insights into the relationship between the generalization of ED models and LVs in unsupervised learning remain limited. Although Chérief-Abdellatte et al. [13] has employed probably approximately correct (PAC) Bayes analysis [47, 6] to investigate the generalization error defined in terms of reconstruction loss, they consider the posterior and prior distributions over the encoder and decoder parameters. Similarly, Epstein & Meir [19] focused on the complexity of encoder and decoder parameters to analyze the generalization capability. Therefore, these studies lack the analysis of the relationship between LVs and generalization capability. Mbacke et al. [46] attempted to address this problem by deriving PAC-Bayes bounds based on the KI. divergence within prior and posterior distributions over LVs; however, their analysis relies on the impractical assumption that decoders are not trained, leaving significant challenges in achieving a practical understanding of the role of LVs in generalization performance.
To address these challenges, we provide the first first rigorous theoretical analysis of the relationship among LVs, generalization, and data generation in ED models, with a focus on VQ- VAES [70]. Motivated by Sefidgaran al. [57]. we construct data-dependent prior over LVs using the supersample setting from ITT analysis [63, 30, 32]. This approach yields a generalization error bound for the reconstruction loss, characterized by the KI. divergence between the prior and the posterior over LVs (Theorem 2). Similar to Sefidgaran et al. [57], our bound remains independent of decoder complexity even when the encoder and decoder are trained jointly, underscoring the critical role of designing the encoder network for the generalization.
However, we observe that the bound based on the supersample setting does not necessarily converge to 0 asymptotically with respect to the number of samples. To address this issue, we extend the super- sample framework by introducing novel data-dependent prior, called the permutation symmetric prior distribution, which explicitly accounts for the inherent symmetries specific to unsupervised learning tasks (Theorem 3). This formulation enables us to derive a generalization error bound that asymptotically converges to 0 as the number of samples increases and is independent of the decoder.
Finally, investigate the data generation capability of VQ-VAEs by deriving the upper bound the 2- Wasserstein distance between the true data and the generated data distributions (Theorem 5). Our analyses reveal that the generalization and data-generating capabilities of VQ- depend solely on the parameters of the encoder and LVs, remaining entirely independent of the decoder.
2 Background
In this section, we introduce the VQ-VAE and define the reconstruction--asee generalization error, which forms the basis of our analysis (Sections 2.1 and 2.2). We then present the IT analysis using supersamples (Section 2.3), highlighting its limitations in unsupervised settings (Section 2.4).
We use uppercase letters for random variables and lowercase letters for their realizations. The distribution of X is denoted by p(X), and the conditional distribution of Y given X by pY|]X). Expectations are written as Xx or Ex. The MI and conditional MI (CMI) are denoted by I(x:Y) and (X; I respectively. The KL divergence from p(X) to p(Y) is written as (L)p()))p(())) For E N, we define (a] ;= (1....,
Notations:
2.1 VQ-VAE and its stochastic extensions
Let X' C Rdd denote the data space, and assume an unknown data- lata-generating distribution D. The latent space is represented as 2 c Rdd,, where both X' and 2 are equipped with the Euclidean metric -| The discrete latent space comprises K distinct points, collectively referred to as the codebook, {e,}ı= E zk, which are learned from the training data.
denoted by e-
The VQ-VAE model consists of the encoder network fo X + Z and the decoder network go: Z - X' responsible for (i) data compression and (ii) reconstruction, where o & C. Igda and 0 E e Re

---

denote the parameters of the encoder and decoder, respectively. In the compression phase, data point mapped to (z), and the discrete representation e, selected from the codebook e. Then, the posterior distribution of the discrete representation indexed by j is denoted g(J = jle, Φ, a) for all j = .......... K. the original VQ-VAE [70], the following deterministic posterior is used:
1 for j argmin (z) -exll+
q( - jle, 0, = 0 otherwise,
where the distance between the encoder output and the codebook entries determines the posterior Recent extensions of VQ-VAE [82, 62, 55, 64] introduce a stochastic posterior defined by
q( - jle, o, x) x exp (-31ffo(z) - =
where a softmax is applied over codebook indices, and the temperature parameter 3 E RR controls the level of stochasticity. The data is then reconstructed by passing the selected latent representation eJ=j through the decoder, resulting in (e(=)=)) The fidelity of the reconstruction to the original input is measured by the reconstruction loss, defined as (z,, go (e(==)))) where / : X x - R..
2.2 Generalization error based on reconstruction loss
Hereafter, let the set of parameters be denoted as W = 0, E (== Given the training dataset S = (S E X consisting of independently and identically distributed (i..d.) data points sampled from the data distribution D, these parameters are learned jointly using a randomized algorithm AA; : X² + W that minimizes the reconstruction loss between a data point and reconstructed data (e,)) i..., (xx, (o(e))) Consequently, the learned parameters e, o 9 follow the conditional distribution g(e, Φb B|S). For simplicity, we define the expected recon- struction loss for input x and w lo- W x X' IR where (uww,,) x) dy(J)e.d..a)) (a, (e())) In this study, we consider the squared distance as 1. Accordingly, our objective is to minimize loww x) de,)))
θ).
[e over the training dataset S. We introduce the following assumption about the data space imposed on our analysis.
|||=
Assumption 1. There exists a positive constant A such that su ||x - x'll < 1/2
This assumption ensures that the reconstruction loss ((x, go({;)) is bounded by A for all æ, ej, and 0.
Our goal is to theoretically characterize the relationship between generalization performance and LVs in VQ-VAEs. To this end, analyze the following generalization error:
gnn D) = Es,x (o (W,
YI Σ L(W,
(3)
where the first term denotes the expected test reconstruction loss, and the second term is the empirical
training loss. Following the success of Sefidgaran et al. [57], we also consider analyzing Eq. (3)
under the IT analysis framework with the supersample (or ghost sample) setting [63, 30, 32].
2.3 Supersample settings for IT analysis
Now, we introduce the supersample setting for IT analysis. We begin by defining a supersample X E xxx2 as an n x 2 matrix containing 2n data points drawn i.i.d. from D. Each row m E [r]] of this matrix, denoted X,, represents pair of data points: (Xm,o._m..1 We then generate a random binary vector U (U1..... U,) Uniform (0, 1)"). which is independent of X. This index vector U determines the training and test sets by selecting exactly one sample from each row. The training dataset is formed as Xu := (Xm, )m= and the test dataset is composed of the remaining sample from each pair, Xo == (Xm, P where U.m = 1 - Um- After training a model W = A((x),, we define the loss matrix 40 (W, X) by evaluating the loss (oW,,) -) on all 2n data points in the original supersample matrix X. This results in an n x 2 matrix of loss values. This distinction between the n-point training set and the 2n-point loss evaluation matrix is key concept for the subsequent analysis. The IT analysis of Eq. (3) under the supersample setting gives the following result.
Theorem 1 (Hellström & Durisi [32]). Under Assumption and the supersample setting, we have
gen D) < A
(4)
3

---

e
j
U
Figure I: Graphical models illustrating different dependency structures for LVs. The left panel shows structure considered the standard supersample setting (Theorem 1). The right panel depicts our proposed structure tailored for unsupervised learning. See Appendix B.3 for further details.
The complete proof is provided in Appendix C. We refer to this bound as the basic IT-bound, as it arises from the direct application of existing IT analysis [32] developed for supervised learning. Unfortunately, we find that the basic IT-bound is insufficient to fully understand the role of LVs in the generalization performance of VQ-VAE. The next section elaborates this limitation.
2.4 Limitation of the direct application of IT analysis
The limitation of the basic IT-bound is that it does not offer clear interpretation of how the LVs contribute to the generalization performance independently of other random variables. Specifically, let J denote the random variable that follows the distribution q(J e, o, X), which is defined by applying g( Φ, elementwise to X. With this definition, we can upper bound Eq. (4) as
(l, UI) & (00:U18) I(;)))
(5)
See Appendix C.2 for the proof. This result implies that the generalization of VQ-VAE can be bounded by the CMI related the decoder parameter 0 and the selected index J. Note that selecting corresponds to selecting an LV 6, from the codebook. Therefore, the second term above illustrates how LVS contribute generalization. However, since conditioning the independent analysis of e. and 0. This dependence hinders a precise theoretical analysis of how LsS affect generalization performance.
is taken, it does allow
We can better understand this difficulty by considering how IT-based generalization analysis is typically formulated: it is framed the problem of inferring which samples were used for training, given a random supersample index, U, that determines the shuffling the dataset. The randomness introduced by this shuffling is governed by the design of the prior, which plays central role in applying the Donsker- Donsker-Varadhan inequality to derive an upper bound on the generalization error. In the basic IT-bound (Theorem 1), shuffling via U leads to randomly altering the training dataset, producing a bound that jointly depends on both model parameters and LVs, thereby entangling 0 and J. This illustrates that straightforward extension of standard IT analysis insufficient isolate the contribution of LVs to generalization, motivating the development of new analytical framework.
3 Proposed IT analysis under supersamples and its limitations
In this section, we first present the results of our generalization analysis for VQ-VAE (Section 3.1). We then offer a detailed interpretation of the resulting generalization error bound and discuss its limitations (Section 3.2). All corresponding proofs provided in Appendix D.
3.1 Our supersample setting and result
As discussed in Section 2.4, the naive application of the existing supersample setting in IT analysis is insufficient to capture the role of LVs. To address this limitation, we introduce posterior and prior distributions over J that explicitly encode the dependence between the supersample index U and the LVs, on the basis of the approach Sefidgaran et al. [57].
To this end, we define the following posterior distributions based both X and X q(]le, o, Xu)= = Im== q(mmle le, Φ. Xmm,u.,. and (J]e, Φ. X6) = II== q(mm/e, Φ. Xm, For notational simplicity, we write QI. = {J]ee, le Φ, X We then define the following joint distribution to capture the dependence of the LVs both Xy and Xe: Qj == q(]le, o, X6) -gJee, o, Xu))

---

o= 250
n= 1000
n= 2000
4000
0.025
0.08
0.04
0.020
0.06
0.015
0.02
0.3
0.010
0.02
0.005
0.00
0.000
Number of Fesidual Dbeks (decodar:
Sumber of Readual Slada (decocer, da)
Number of dasl Bloces (decoder:
Namber of Aanidual Bocts toscoder dut
The behavior of the generalization gap on the MNIST dataset when increasing the number of residual blocks to enlarge the decoder dimension de (K 128, dg 64). See Appendix for detailed experimental settings.
Figure 2:
We consider two types of prior distribution to facilitate the analysis of VQ- VAEs: a data cata-innependent prior P and data-dependent prior Qj defined as
P II xJmlle,)) and Qj Eu QJN (J, ( Xu),
(6)
where x (Jm/le, の) denotes an arbitrary distribution over LVs that is independent of both X and the supersample index U. For the data-dependent prior, we adopt the supersample setting specifically tailored to the LVs. The basis for introducing both types of prior is discussed following the main theorem. Figure illustrates the distinction in LV dependencies between the conventional supersample setting (as used in Theorem I) and our approach. The central idea is to apply supersample-based shuffling to the LVs directly. Under these settings, the following is our main result.
Theorem 2. Under Assumption and the supersample setting, we have
gen(n, S 22AV Ex (KL (KL, PP) KL (I,,11111
A
n
The upper bound comprises distinct complexity terms. The first, KL(Qq,ui PP, captures the complexity of the LVs. The second, KL(Qj,u (Q),, reflects the complexity of the LVs and the degree of overfitting when learning parameters and Φ, we will further discuss in Section 3.2.
Consistent with the findings of Sefidgaran al. [57], bound is independent of the decoder Gs. This indicates that increasing the complexity of ge has a limited effect on the generalization performance. Our empirical results support this implication. Figure shows that adding a single ResBlock-introducing approximately 74, 000 additional parameters-hal negligible effect on the generalization gap. Furthermore, Table in Appendix G shows the corresponding training losses. For larger sample sizes (n 2 1000), the training loss tends to decrease as the decoder becomes more complex, confirming its enhanced ability fit the training data. Critically, despite this improved expressiveness, the generalization gap remains largely unaffected. This strongly suggests that the key improving generalization lies not in the decoder's capacity, but the complexity of the encoder and the LVs. Further experiments across various datasets and decoder architectures in Appendix G reinforce this observation.
We emphasize that our results do not imply that the decoder is unimportant. Although our gener- alization bound independent of decoder complexity, sufficiently expressive decoder is still required to fit the training data. Otherwise, the test loss may remain high since Test Loss < Training Loss + Generalization Gap. Our analysis specifically focuses on bounding the general- ization gap, under the implicit assumption that the decoder can adequately fit the training data. In practice, this suggests that improving generalization in VQ-VAEs hinges more on careful encoder design, since overly complex encoders can increase the KL divergence of the LVs. We discuss this point further in Section
Why two types of prior are required: Our proof reveals that isolating the LVs from the decoder parameter and obtaining a reccoder-independe generalization bound requires the prior to satisfy two essential conditions: (A) it allows random shuftling without changing the LV distribution, and (B)

---

it supports swap between training and test samples to assess overfitting, From this perspective,
the shuffling induced by U in the basic IT-bound (Theorem 1) satisfies condition (B) but violates condition (A), as it changes the distribution of L.v. To address this issue, the proof of Theorem 2 decomposes the generalization gap into two components: the term associated with condition (A), which is controlled using data-independent prior P, and the term associated with condition (B), which is controlled using a data-dependent prior Q3. By combining both priors, we can derive the final upper bound in Eq. (7). For a detailed explanation, see Appendices B.3 and D.I.
Remark 1. When K = 1, VQ-VAEs map all input data to the same LV, effectively estimating the low-dimensional mean of the data distribution. In this case, the generalization error should not depend on the decoder. It is straightforward to show show-withou using our IT--aaeed analysis -taa gen(n, D) = O(1/vn). Notably, our bound Eq. (7) correctly reflects this behavior, as the square root term vanishes when K = 1 (see Appendix C.3 for details).
3.2 Further analyses of our bound and limitations on convergence
In this section, we further analyze the properties of the two KL divergence terms in Theorem 2 and discuss their asymptotic behavior as the sample size n increases.
Regarding (L,,,)111))) (le.)1).) o(e..tt))) (I, (.. Q5) S T(e, d; UIX) +
We can derive the following upper bound:
Bx,u
8).
(8)
Since = S, the data processing inequality implies that I(c, di U|x) I I(e, S). This quantity captures how much information about the training data is retained in the encoder, thereby reflecting the degree of overfitting of the encoder parameters. The term [(J: Ul, Φ,, X) can be viewed as regularization term for the LVs, analogous to the IB hypothesis; see Appendix D.6 for further details.
Next, we investigate whether each term in Eq. (8) exhibits asymptotic convergence as the sample size increases, which is key requirement for a valid generalization error bound. We begin by analyzing the asymptotic behavior of U[J:
Lemma 1. Let the posterior distribution over J be deterministic defined in Eq. (1), and denote the composition of this mapping with the encoder fo by T'es : X' + [K]. If the function class to which fag belongs has a finite Natarajan dimension, then [[J; Ule o, X)/n n = O(log n/n).
This result implies that if the encoder is appropriately regularized, the quantity [[:UUle é,, 8)/n converges asymptotically to zero. We also empirically evaluated this term in practical settings (see Appendix G) and observed that it indeed decreases as the sample size increases.
Next, the CMI term [(e, dz Ul has been extensively analyzed under the standard supersample setting of IT analysis [63]. Prior works have established its asymptotic convergence through various approaches, including algorithmic stability [63]. analyses of specific optimization methods such as stochastic gradient descent (SGD) [78] and stochastic gradient Langevin dynamics (SGLD) [20]. and complexity based arguments using covering numbers [83], all showing that I(c, Φ: U|X)/n - as n + cc. In conclusion, the term E E ((e.)) KL (Qj.r
can be shown to converge asymptotically under certain algorithmic conditions. For detailed discussion, see Appendix D.8.
Q2))/n (1j)):
Regarding KL(QQ,u u PP:: This term can be rewritten as |I(Qu,u|IP)) n. -m= (Lm e, d. Sm) ee Φ)), where the training data is selected via U, i.e. = (S),.... Sn). This quantity corresponds to the empirical KL divergence, which also appears in the analysis of Mbacke et al. [46], and reflects the complexity of the LVs. Such a term is commonly used as the regularization term appearing in many VAE training procedures [39, 33, 64].
Xu - =
A key factor in minimizing KL(QJ,U [PP) is the choice of the prior P. In VQ- a uniform distri- bution is typically adopted [64]; however, is this choice optimal for minimizing the KL divergence? The following lemma addresses this question.
Lemma 2. Assume that for any fixed training dataset S (81, 8p) and any permuta- tion T, the posterior satisfies permutation invariance, ie., q(e, o, ( a(e, o, ))S",, where S = (s St Then, the optimal prior that minimizes (L is

---

Generwirzttoon VS
K1,n First 1Q.17)).9..
K1. Iecond 1a
Geeend onoon Uop /aile
303
220
0.30
18m2 pm A2D
Cerclitton
EDno (w0.220
0 0.75
343
3.5
0.00
FB:
0.0
Rag segeediin line
6-0455
030
0.15
0:35
115
300
3.55
0.00
9.3
2.00
283
-1.00
250
1030
2030
250
1000
4000
2.00
1200
2000
250
320
010 0.55 030 035 01 beoond migh
Ki.n
Figure 3: The behavior of the generalization gap and the two KL terms from Eq. (7) on the MNIST dataset (K 128, d,- 64). The three leftmost panels show the asymptotic behavior of the generalization gap, the first KL term, and the second KL term as a function of sample size n. The two rightmost panels show scatter plots correlating the generalization gap with the first KI. term (fourth panel) and the second KL. term (fifth panel). these plots, the color indicates the number of decoder Residual Blocks (RB=2, 3, 4, or 5) and the marker shape indicates the sample size n. (Circle for n 250, Square for 1000, Diamond for n 2000, and Triangle for n 4000).
given by P T== gg ( d Sm)- Moreover, under this prior, we obtain (s (L( P*) -E.. 1 [J i Smle,
This connection provides insight into the choice of prior distributions in practical implementations for instance, encouraging the use of mixture priors similar to the VampPrior [68] (see Appendix D.2 for further discussion). We also note that the assumption in Lemma 2, namely permutation invariance of the posterior, is standard in the analysis of randomized algorithms [42], and is satisfied by commonly used training methods such as SGD and SGLD [81].
Next, we present the asymptotic behavior of the empirical KL divergence term follows:
Lemma 3. Suppose the assumptions in Lemma hold. Then, even under the optimal prior P given in Lemma 2, we have EggByee, s) (Q..u |P*)// O
This result indicates that asymptotic convergence cannot be achieved, even when using the optimal prior P", which minimizes KL (Q,,u [P), to regularize the complexity of the encoder. Our empirical results provide validation for this theoretical finding. As shown in Figure 3 (left and middle panels), the first KI. term, (L PP)/n, does not decrease as the sample size n increases, confirming the behavior predicted by Lemma 3 (see Appendix G.4 for additional experimental results). Furthermore, the right two panels Figure: 3 illustrate the relationship between these terms. The second KL term exhibits a consistent positive correlation (r 0.4660.60) with the generalization gap across all tested decoder complexities. This suggests that the second KL term is the component that effectively captures generalization behavior. Conversely, the non-converging first KL term, KL (Q,,u [PP) n, shows negative correlation, indicating it does not track generalization performance. This experiment empirically justifies our motivation introduce the new permutation symmetric setting in Section to climinate this converigggg and poorly correlated term.
In the supervised learning context, it has similarly been observed that empirical KI. terms analogous to KLT(QQ Qa | do not necessarily converge, even for models that generalize well [21, 57). Our findings are consistent with these results.
Remark 2. Even when the posterior of J is defined by Eq. (2), comparable upper bound the KL regularization term can still be derived by analyzing the encoder's complexity via metric entropy. For further details, Section 4.2 and Appendix E.4.
4 Proposed IT analysis under the new permutation symmetric setting
The observations presented in the previous section motivate the derivation of generalization error bound that avoids explicit dependence on KL (Q.uu [PP). We conjecture that the appearance of this term in Theorem 2 arises from a fundamental limitation of the supersample setting, which necessitates the use of data-independent prior (as defined in Eq. (6)) to satisfy the necessary conditions (A) and (B) described in Section 3.1. To overcome this limitation, in this section, we introduce an extension of the supersample framework namely, a novel permutation symmetric setting. This new setting enables the construction of data-dependent prior that satisfies both conditions simultancously,
7

---

thereby yielding generalization error bound that achieves asymptotic convergence. All the proofs of this section are provided in Appendix E.
4.1 Permutation symmetric setting
To simultaneously satisfy the two conditions in Section 3.1, we propose randomly shuffling all 2n data points in X using uniform distribution and taking their expectation as the data-dependent prior distribution. By definition, this distribution is permutation-invariin,, thereby satisfying conditions (A) and (B), allowing us to obtain the improved bound.
Formally, let denote random permutation of [2m] as = -Ti........ T2n): J. where each permutation appears with uniform probability, P(T) 1/(2n)!. Given supersample X (X1,..., X2n) 222n of 2n RVs drawn i.i.d. from D, reorder the samples using T expressed XT (XT...... ....... XT..). The first samples (XT....... Xr,) are used for the test dataset and the remaining samples (AT.41..... XT are used for the training dataset. We further express (To, Tı}. and Nr, = (X (Xi,,.... Xx,)) and Xr, = (X...)...., X1,,) represent the test and training datasets, respectively.
Given X and T, we define the posterior distributions over the LVs of the test and train- ing data, respectively, as q e, o, XT,) = Im q( lc, é, Xr.), q o, Xr,) = (i==1((m) le á XT XT We then define the joint posterior distribution Qj. ((]le, o, (T.))(Jee o, XT,).
Finally, we define our new data-dependent prior as
Qj = Er Erg(J d,
o, XT.).
We refer these settings as the permutation symmetric (supersample) setting. The following our main result. Theorem 3. Under Assumptions and the permutation symmetric setting, we have
Ex Bx 9 X (L Q5)
A
gen(n, n, D) S 3AV
T
Remark Unlike the existing supersample setting, where (Um)s } are independent, the elements of T are dependent, which makes the analysis more complicated.
Explanation of Theorem 3: Similar to Theorem 2, this bound is independent of the decoder go- The key difference is that the empirical KL term, KL(Qu,tf P)) is eliminated owing to our new data-dependent prior distribution Qj. The proposed permutation satisfies both conditions (A) and (B) in Section 1. eliminating the need for a
prior P.
Next, analyze the KL term in the bound. Similar to Eq. (8), we have
E x T Be
a(e XT,) KL KL(Q (Q3) - I(c, T + T(,,T(e,
Since XT, corresponds the training dataset I(e, Φi T| ((e, holds. Then, we can show that our generalization bound becomes
T(c. o; o; T X)
A
gen (n, D) - 3A
(10)
n2
Vn
Our bound consists of the complexity LV [[( o, X)) and the overfitting caused by learning encoder parameters (T(e, d; 5)) similar to Theorem This implies the two key factors identified in Theorem 2 of Kawaguchi et al. [38]: how much information the LV retains from the input data and how much information from the training dataset is used to train the encoder.
As discussed in Section 3.2, when using a sufficiently regularized deterministic encoder, fa,s X + [K] the CMI term satisfies [(J; Ule, Φ, X)/n / Ollog n/n); see Appendix D.7 for details. The parameter overfitting term can be controlled by specifying the training algorithm, as discussed in

---

Section 3.2. Under these conditions. the generalization bound decreases as - meaning that Theorem successfully characterizes generalization.
Although Theorem 3 shares a similar structure with Theorem 2, introduces refined shuffling strategy with T, which resolves the issues of the supersample settings as discussed in Section 3.2. This shuffling is based on the fact that the marginal distribution of the dataset, which is invariant under permutation, can be expressed by the LV model. This new symmetry allows defining a data-dependent prior that satisfies necessary conditions while preserving decoder independence. On the other hand, the shuffling in Theorem 2 based on the supersample setting and suitable for supervised learning, where overfitting is measured by swapping test and training data points. Practically, however, Theorem 2 relies on an n--dimensional variable, (with independent components), which facilitates CMI estimation and algorithm design. In contrast, Theorem 3 uses 2n-dimensional variable, T (with dependent components), which is theoretically more preferable but more difficult to estimate the CMI.
Comparison with Theorem 2:
4.2 Generalization bound based on metric entropy
When using a softmax distribution in Eq. (2) for J, we show that the generalization bound is governed by the metric entropy under the permutation symmetric setting. Consequently, does not require specifying a learning algorithm, which is required to discuss the convergence of Theorem 3 and provides a uniform convergence bound that depends solely on the function class of the encoder.
Let be the encoder function class equipped with the metric ||-I| Given x" := (I1...., ,I,) E X", define the pscudo-metric d, on F as d,, (f..g) g) maX
fxx,) g(x;)ll for f.g E F. The d-covering number of JF with respect to d, is denoted (6, F, x"), and we define (6, F, n) = "x (6, F, xx)).
Theorem 4. Assume that there exists positive constant AS such that sup,, || - 211l < A.. Then, when using Eq. (2) and under the same setting as Theorem 3, for any ö E (0, 11. we have
2 2log 2l,g.N66,FF 2n)
A
(on(n,D)= 23 + +3A
n
n
We note that the parameter overfitting term does not appear in the bound. Since the encoder is parameterized by Idds the metric entropy Odgdd log(1/8)) [74]. Setting ó O(1nn) gives gen(n, D) o (oVVVadds log This result suggests that regularizing the complexity of the encoder improves generalization, whereas the complexity of the decoder has limited influence on the generalization. See Appendix E.3 for the proof and further discussion.
IT analysis for data generation performance
Mbacke et al. [46] provided statistical guarantees for the generalization error and data generation performance of VAEs, albeit under the strong assumption of an untrained decoder. Building on their approach, provide theoretical guarantee for the data generation performance of VQ- VAEs from an IT analysis perspective when both the encoder and decoder are trained jointly.
We first briefly summarize the data generation process in VQ-VAEs. After training, new data is generated by sampling an index from prior distribution, π (J]c, Φ). often chosen as a uniform distribution [64], and using the decoder network go to reconstruct the corresponding latent representa- tion e. from the learned codebook e. Thus, the prior imposed on the latent representation is defined 1, I,... K, and the data distribution generated through this procedure
as π (e eyle () for all can be expressed as ~ = go # (ele, Φ). where # denotes the pushforward of the distribution π by the decoder network. See Appendix F for the formal definition.
The following the result our analysis on the data generation performance of VQ-VAB.

---

Theorem 5. Suppose that 9o is measurable for any 9 and Assumption 1 holds. Then, for any data-inda inteaiddeeendentt prior Te 6) as defined Eq. (6). we have EsBgie,,,0)))) W (D. (D - 22 vn
11 T1
E
E 5 ((
E
([Sm.go(e... 40,
KL(g(Jmle, (J) m=1
m== (e,
where (2(D, is the 2-Wasserstein distance between the data distribution DD and the generated-date distribution Jt.
The complete proof can be seen in Appendix F. The results indicate that the quality of approximating D by fi can be enhanced by minimizing the reconstruction loss and the KL regularization term on LVs, which aligns with common training strategies for VQ- (Q-VAEs. Furthermore, this bound holds for any prior that satisfies the conditions outlined in Theorem 2. Thus, designing prior that reduces this bound could lead to improved data generation accuracy. One potential approach is to use the data-dependent prior defined in Eq. (9). Although this prior was originally designed to yield tighter generalization error upper bound, our experiments reveal that it also provides practical benefits for the data generation task, consistently improving test performance over the baseline (see Table 4 in Appendix G). However, we do not claim this specific prior is optimal for minimizing the data generation bound. We expect that our findings will stimulate further discussions on prior designs that effectively improve the generalization performance and data generation capabilities of VQ- VA-E.
Conclusion and limitations
This work establishes decoder-independent generalization guarantees for VQ-VAEs. Across Theo- rems 2 to 4, we show that the generalization gap is governed by the encoder parameters (e, 6) and the induced LVs, while the decoder complexity (0) plays limited role. This central finding empirically supported by our extensive experiments (Appendix G.4).
Our theoretical analysis provides several actionable insights. The primary takeaway is that efforts to improve generalization should prioritize the design and regularization the encoder architecture work
and LV complexity, rather than investing in overly complex decoder. Furthermore, provides the first formal justification for the widely used practice of KL-based regularization on LVs (Theorems and 5), confirming it functions as valid regularizer for both generalization and data generation. Finally, our framework highlights the importance of prior design. Our analysis, in line with Sefidgaran al. [57], shows how data-dependent prior can improve performance. Our experiments (Table 4) validate this, demonstrating that a learned prior, which approximates a data-dependent prior, consistently outperforms the standard uniform prior in practice.
Limitation: Our findings have two main limitations, which point to important avenues for future research. The first limitation is that the upper bound presented in Theorem 3 is challenging compute numerically, making it impractical as an evaluation metric at present (see Sections 3.2 and 4). This difficulty stems from the CMI term in Eq. (10), where T is 2n-dimensional dependent random variable. Consequently, standard numerical evaluation methods for CMI cannot be directly applied. Developing alternative, computable bound is essential next step. The second limitation is that our analysis is currently justified only for VQ-VAFs, which are based on discrete LVs. Our proofs rely on properties of discrete random variables (the codebook index J) and apply concentration inequalities for each assignment. These proof techniques cannot be immediately applied to models with continuous latent spaces, where such assignments are not available. While one may consider forcibly discretizing continuous latent space, the resulting discretization error is non-negligible and would substantially affect the analysis. Extending our information- framework to continuous settings is therefore a crucial and non-trivial step for future work.
Acknowledgments and Disclosure of Funding
We sincerely appreciate the anonymous reviewers for their insightful feedback. FF was supported by ISPS KAKENHI Grant Number 1693K FF was supported by JST, PRESTO Grant Number JPMJPR22C8. Japan. MF was supported by KAKENHI Grant Number 3286.88. Japan.
10

---

References
[1] Achille, A. and Soatto, S. Information dropout:
Learning optimal representations through noisy computation. IEEE Transactions Pattern Analysis and Machine Intelligence, 40(12) 2897-2905, 2018. doi: 10.1109/PAMM..017. 2.274444..
[2] Achille, A. and Soatto, S. Emergence of invariance and disentanglement in deep representations. In 2018 Information Theory and Applications Workshop (ITA), pp. 1-9, 2018, doi: 10.1109/ ITA.2018.. 88503199..
[3] Alemi, A., Poole, B., Fischer, L., Dillon, J., Saurous, R. A., and Murphy, K. Fixing broken elbo. In International conference on machine learning, pp. 159-168. PMLR, 2018.
[4] Alemi, A. A., Fischer, I., Dillon, J. V., and Murphy, K. Deep variational information bottleneck.
In International Conference on Learning Representations, 2017.
[5] Alon, N., Ben-David, S., Cesa-Bianchi, N., and Haussler, D. Scale-sensitive dimensions, uniform convergence, and learnability, Journal of the ACM (JACM), 44(4):61 1997.
[6] Alquier, Ridgway, J., and Chopin, N. On the properties of variational approximations of Gibbs posteriors. Journal of Machine Learning Research, 17(236):1-41, 2016.
[7] Bartlett, P. L. and Maass, W. Vapmik-chervonenkis dimension of neural nets. The handbook of brain theory and neural networks, pp. 1188-1192, 2003.
[8] Bendavid, S., Cesabianchi, N., Haussler, D., and Long, P. Characterizations of learnability for classes of [0, ... n)-valued functions. Journal Computer and System Sciences, 50(1): wwtp://.....//.s..o.oooooo 74-86, 1995. ISSN 0022-0000. doi: https://oi..rr// 100 1006100066 1995. 1008. URL https: www.www..mmmmmmm www.ncediiicccccnem rect com/ occ.eeee/arrtcceep/////00000001/
[9] Blau, Y. and Michaeli, Rethinking lossy compression: The aite-distortionpprrppiooo tradeoff. In International Conference on Machine Learning, pp. 675 685. PMLR, 2019.
[10] Blum, A. and Langford, J. Pac-mdl bounds. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COL./Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, pp. 344-357 Springer, 2003.
[11] Bolley, F. and Villani, Weighted esiszár- kullback-pinsker inequalities and applications to transportation inequalities. Annales de la Faculté des Sciences de Toulouse, 14:331-355 2005. URL https: : /api. semant eschol ar www..rroo//.oooo...........oo.rr orgg Co coorpusTin ID: 1p895D61869555.. 18695658.
[12] Bond-Taylor, S., Leach, A., Long, Y., and Willcocks, C. G. Deep generative modelling: A
comparative review of vaes, gans, normalizing flows, energy-basse based and autoregressive models. IEEE transactions on pattern analysis and machine intelligence, 44(1) 4(11)::337773477 2021.
[13] Chérief-Abdellatif., B.-E., Shi, Y., Doucet, A., and Guedj, B. On pac- mac-bayesian reconstruction guarantees for vaes. In International conference on artificial intelligence and statistics, pp. 3066-3079. PMLR, 2022.
[14] Clarke, B. S. and Barron, A. R. Jeffreys' prior is asymptotically least favorable under entropy risk. Journal of Statistical Planning and Inference, 41:37-60, 1994.
[15] Cover, T. M. and Thomas, J. A. Elements of Information Theory. John Wiley & Sons, 2012.
[16] Daniely, A., Sabato. S., Ben-David, S., and erm principle. Proceedings of the 24th Annual Conference on Learning Theory, pp. 207-232. JMLR Workshop and Conference Proceedings, 2011.
S. Multiclass Icarnability and the
[17] Dong, Y., Gong, T., Chen, H., Yu, S., and Li, C. Rethinking information-theerrtiic generalization: Loss entropy induced pac bounds. In The Twelfth International Conference on Learning Representations, 2024.
[18] Dubhashi, P. and Ranjan, Balls and bins: A study in negative dependence. BRICS Report Series, 3(25), 1996.

---

[19] Epstein, B. and Meir, R. Generalization bounds for unsupervised and semi-supervised learning with autoencoders. arXiv preprint arXiv:1902.01449, 2019.
[20] Futami, F. and Fujisawa, M. Time-independent information-theorrt generalization bounds for SGLD. In Thirty-sevntth Conference on Neural Information Processing Systems, 2023. URL https: / wpwnreviewwwweeeeeeeeeeee..eeewe net/ forum? worrumid=nKsoBee d
[21] Geiger, B. C. and Koch, On the information dimension of stochastic processes. IEEE Transactions on Information Theory, 65(10):6496-65 6518, 2019, doi: 10. 10.1109/1112001.22221666
[22] Goldfeld, Z., Van Den Berg, E., Greenewald, K., Melnyk, I., Nguyen. N.. Kingsbury, B.. and Polyanskiy, Y. Estimating information flow deep neural networks. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2299-2308 PMLR, 09-15 Jun 2019.
[23] Goodfellow, I., Bengio, Y., and Courville, A. Deep Learning. MIT Press, 2016. http: //www. deep ea i ingbooo.ooo org..
[24] Goutlib, L.-A., Kontorovich, A., and Krauthgamer, R. Efficient classification for metric data. IEEE Transactions on Information Theory, 60(9):5750-575)) 2014.
[25]
Gray, R. M. Entropy and information theory. Springer Science & Business Media, 2011.
[26] Guermeur, Y. Lp-norm sauer-shelah lemma for margin multi-category classifiers. Journal of Computer and System Sciences, 89:450-473, 2017. ISSN 0022-0000.
[27] Guermeur, Y. Combinatorial and structural results for gamma-pss petata--s-ddiiiioomm. arXiv preprint arXiv:1899.07310, 2018.
[28) Hafez-Kolahi, H., Kasaei, S., and Soleymani-Baghhae M. Sample complexity of classification with compressed input. Neurocomputing. 415:286-291 294, 2020. ISSN 0925-2312.
[29] Haghifam, M., Gälve, B., Thobaben, R., Skoglund, M., Roy, M., and Dziugaite, G. K. Limitations of information-theoretii generalization bounds for gradient descent methods in stochastic convex optimization. International Conference on Algorithmic Learning Theory, pp. 663-706. PMLR, 2023.
[30] Harutyunyan, H., Raginsky, M., Steeg, G. V., and Galstyan, A. Information-theorrtic generaliza- tion bounds for black-box learning algorithms. In Advances Neural Information Processing Systems, pp. 24670-24682, 2021.
[31] Haussler, D. and Opper, M. Mutual information, metric entropy and cumulative relative entropy risk. The Annals of Statistics, 25(6))2451-2499 1997.
[32] Hellström, and Durisi, G. new family of generalization bounds using samplewise evaluated CMI. In Advances in Neural Information Processing Systems, 2022.
[33] Higgins, I., Matthey, I.., Pal, A., Burgess, C., Glorot, X., Botvinick, M., Mohamed, S., and Lerehner, A. beta-vae: Learning basic visual concepts with constrained variational framework. In International conference on learning representations, 2017.
[34] Higgins, I., Matthey, L., Pal, A., Burgess, C., Glorot, X., Botvinick, M., Mohamed, S., and Lerchner, A. beta- VAE: Learning basic visual concepts with a constrained variational framework. In International Conference on Learning Representations, 2017.
[35] Jang, E., Gu, S., and Poole, B. Categorical reparameterization with Gumbel-softmax. In International Conference on Learning Representations, 2017. URL httttt://opeeeeeiiiieee net/ www.moidduuuueee
[36] Jin, Y. Upper bounds on the natarajan dimensions of some function classes. In 2023 IEEE International Symposium on Information Theory (ISIT), pp. 1020-1025. IEEE, 2023.
[37] Jov, K. and Proschan, Negative association of random variables with applications. The Annals of Statistics, pp. 286-295, 1983.
12

---

[38] Kawaguchi, K., Deng, Z., Ji, X., and Huang. J. How does information bottleneck help deep learning? In Krause, A., Brunskill, E., Cho, K., Engelhard,, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 16049-16096. PMLR, 23-29 Jul 2023.
[39] Kingma, D. Auto-encoding variational bayes. arXiv preprint arXiv: 1rXiv:1312.61111 131.61114, 2013.
[40] Kraskov, A., Stögbauer, H., and Grassherger, P. Estimating mutual information. Physical Review E, 69:066138 38, 2004.
[41] LeCun, Y., Boser, B., Denker, J. S., Henderson, D.. Howard, R. E., Hubbard, W., and Jackel, I.. Backpropagation applied to handwritten zip code recognition. Neural Computation, 1(4): 541-551, 1989.
[42] Li, J., Luo, X., and Qiao, M. On generalization error bounds of noisy gradient methods for non-convex learning. In The Eighth International Conference on Learning Representations, 2020.
[43] Loftsgaarden, D. O. and Quesenberry, C. P. A Nonparametric Estimate of a Multivariate Density 1965.
Function. The Annals of Mathematical Statistics,
[44] Lyu, Y., Liu, X., Song. M., Wang. X., Peng, Y., Zeng. T., and Jing. L., Recognizable information bottleneck. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pp. 4028-442440 4036, 2023.
[45] Maddison, J., Mnih, A., and Teh, Y. W. The concrete distribution: continuous relaxation of discrete random variables. In International Conference on Learning Representations, 2017.
URL https::/p/ http:httts///peeeeeeeeeee hppp//ppeeveeeeeeeeeeeeeeeeeeeee n Forum?id=s) 1155511555.11.111
[46] Mbacke, S. D., Clerc, F., and Germain, Statistical guarantees for variational autoencoders
using pac-bayesian theory. Advances in Neural Information Processing Systems, 36, 2023.
[47] McAllester, D. A. PAC-Bayesian stochastic model selection. Machine Learning, 51(1):5-21 -21,,1, 2003.
[48] Mou, W., Wang, I.,, Zhai, X., and Zheng, K. Generalization bounds SGLD for non-convex learning: Two theoretical viewpoints. In Proceedings of the 31st Conference on Learning Theory, volume 75, pp. 605-638, 2018.
[49] Negrea, J., Haghifam, M., Dziugaite, G. K., Khisti, A., and Roy, D. M. Information-theorett generalization bounds for SGLD via data-dependent estimates. In Advances in Neural Informa- tion Processing Systems, volume 32, pp. 11015-11025, 2019.
[50] Neu, G., Dziugaite, K., Haghifam, M., and Roy, D. M. Information-theoretic generalization bounds for stochastic gradient descent. In Conference on Learning Theory, pp. 3526-3545. PMLR, 2021.
[51] Pensia, A., Jog, V., and Loh, P.-L. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pp. 546-550, 2018.
[52] Pollard, D. Quantization and the method of k-means. IEEE Transactions on Information theory, 1892):199-205, 2003.
[53] Rissanen, Universal coding, information, prediction, and estimation. IEEE Transactions on Information Theory, 30(4):629-636, 2006.
[54] Ross, B. C. Mutual information between discrete and continuous data sets. PLOS ONE, 9()) 1-101, 2014.
[55] Roy, A., Vaswani, A., Neelakantan, A., and Parmar, N. Theory and experiments on vector quantized autoencoders. arXiv preprint arXiv:1805.1100 2018.
[56] Saxe, A. M., Bansal, Y., Dapello, J., Advani, M., Kolchinsky, A., Tracey, B. D., and Cox, D. D. On the information bottleneck theory of deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2019(12): 2019.
13

---

[57] Sefidgaran, M., Zaidi, A., and Krasnowski. P. Minimum description length and generalization guarantees for representation learning. Advances in Neural Information Processing Systems, 36, 2023.
[58] Sefidgaran, M., Zaidi, A., and Krasnowski, P. Generalization guarantees for representation learning via data-dependent gaussian mixture priors. In The Thirteenth International Con- ference on Learning Representations, 2025. URL https: oownrevveeeeeeeeee/e/eeeee net/ forum? BFGEF.FBBQLFVV.
[59] Sefidgaran, M., Zaidi, A., and Krasnowski, P. Generalization guarantees for multi-view repre- sentation learning and application regularization via gaussian product mixture prior. arXiv preprint Xrxiv:2504. 18455, 2025.
[60] Shamir, O., Sabato, S., and Tishby, N. Learning and generalization with the information bottleneck. Theoretical Computer Science, 411(29))266-2711, 2010. ISSN 0304-3975. Algorithmic Learning Theory (ALT 2008).
[61] Shwartz-Ziv, R. and Tishby, N. Opening the black box of deep neural networks via information. arXiv preprint arXiv: 1703. 008.00 2017.
[62] Sønderby, C. K., Poole, B., and Mnih, A. Continuous relaxation training of discrete latent variable image models. In Beysian Deepleeariigg workshop, NIPS, volume 201, 2017.
[63] Steinke, T. and Zakynthinou, L. Reasoning About Generalization via Conditional Mutual Information. In Proceedings Thirty Third Conference on Learning Theory, volume 125, pp. 3437-3452, 2020.
[64] Takida, Y., Shibuya, T., Liao, W., Lai, C.-H., Ohmura, J.., Uesaka, T., Murata, N., Takahashi, S., Kumakura, T., and Mitsufuji, Y. SQ- VAE: Variational Bayes on discrete representation with eeff-annealed stochastic quantization. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 20987-21012. PMLR, 17-23 Jul 2022.
[65] Telgarsky, M. J. and Dasgupta, S. Moment-based uniform deviation bounds for k-means and friends. Advances in Neural Information Processing Systems, 26, 2013.
[66] Tishby, N. and Zaslavsky, N. Deep learning and the information bottlneck principle. In 2015 ieee information theory workshop (itw), pp. 1 1-5. IEEE, 2015.
[67] Tishby, N., Pereira, F. C., and Bialek, W. The information bottleneck method. arXiv preprint physies/0004057, 2000.
[68] Tomezak, J. and Welling, M. Vae with a vampprior. International conference on artificial intelligence and statistics, pp. 1214-1223. PMLR, 2018
[69] Tschannen, M., Djolonga, J., Rubenstein, P. K., Gelly, S., and Lucic, M. On mutual infor- mation maximization for representation learning. In International Conference on Learning Representations, 2020.
[70] Van Den Oord, A., Vinyals, O., al. Neural discrete representation learning. Advances in neural information processing systems, 30, 2017.
[71] Vera, M., Piantanida, P., and Vega, L. R. The role of the information bottleneck in representation learning. In 2018 IEEE International Symposium on Information Theory (ISIT), pp. 1580-1584, 2018. doi: 10. /19/ 0.8011188847799
[72] Vera, M., Rey Vega, L., and Piantanida, P. The role of mutual information in variational classifiers. Machine Learning, 1100331055-150,, 2023.
[73] Vuong, L. T. Task-driven discrete representation learning. In Li, Y., Mandt, S., Agrawal, S., and Khan, E. (eds.), Proceedings The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pp. 5203-5211 1. PMLR, 03-05 May 2025.
14

---

[74] Wainwright, M. J. High-dimensional statistics: A non-asymptotie viewpoint, volume 48. Cambridge university press, 2019.
[75]
Wainwright, M. Hligh-Dimeniionll Statistics; A Non-Asympiotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
[76] Wang. H., Huang, Y., Gao, R., and Calmon, F. Analyzing the generalization capability of SGLD using properties of Gaussian channels. In Advances Neural Information Processing Systems, volume 34, pp. 24222-24234, 2021.
[77] Wang, H.. Gao, R., and Calmon, F. P. Generalization bounds for noisy iterative algorithms using properties of additive noise channels. Journal of Machine Learning Research, 24(26): 1-43, 2023.
[78] Wang, and Mao, Y. On the generalization models trained with SGD: Information-theoree bounds and implications. In The Tenth International Conference Learning Representations, 2022.
[79] Wang. Z. and Mao, Y. Tighter information thecoricion-thcoreiiccc generalization bounds from supersamples. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pp. 36111-36137, 2023.
[80] Wang. Z., Huang, S.-L., Kuruoglu, E. E., Sun, J., Chen, X., and Zheng, Y. PAC-bayes information bottleneck. In International Conference on Learning Representations, 2022.
[81] Welling, M. and Teh, Y. W. Bayesian learning via stochastic gradient Langevin dynamics. In Proceedings of the 28th International Conference on International Conference on Machine Learning, pp. 681-688. 2011.
[82] Williams, W., Ringer, S., Ash, T., MacLeod, D., Dougherty, J., and Hughes, Hierarchical quantized autoencoders. Advances in Neural Information Processing Systems, 33:4524-4535, 2020.
[83] Xu, A. and Raginsky, M. Information--hheortiicc analysis generalization capability of learning algorithms. In Advances in Neural Information Processing Systems, volume 30, pp. 2524-2533. 2017.
15

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims in the abstract and Section match our theoretical and numerical claims in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Assumptions for each theorem are explicitly shown. Following each theorem, there is discussion about the theorem's limitations and implications. Additionally, Section includes discussion the limitations of the entire paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
16

---

Answer: [Yes].
Justification: Complete proofs of all theorems are provided in Appendices C and D. For the reader's convenience, the exact location of each proof is explicitly indicated alongside the corresponding theorem in the main text.
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes].
Justification: The experimental setup for reproducing our results is detailed in Appendix G. We submitted our source codes through OpenReview.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
17

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes].
Justification: We only used the popular benchmark datasets (such MNIST and CIFAR-I0) that can be easily obtained. The experimental setup for reproducing our results is detailed in Appendix G. We submitted our source codes through OpenReview.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https: /ppps///nipi /nnps/ips...... cc/
public /guidessssseeeeeee Coo/eooeeuuua Suboii ss seioPoooicyyy for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (ht
//nips cc/ http:c/pppcc/cccccccccccccccccct cubbic//ge ides (codeSubm i LonPol icy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes].
Justification: The experimental setup for reproducing results is detailed in Appendix G. We submitted our source codes through OpenReview.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes].
Justification: We reported the mean + std. of the generalization gap and our bound values for all experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
18

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We used NVIDIA GPUs with 32GB memory (NVIDIA DGX-1 with Tesla V100 and DGX-2) in our experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that tidn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /tw.riuuuu..////e//ee httppublicc/ttiicccu...e.
Answer: [Yes].
Justification: We confirmed that paper does not have issues concerning the NeurIPS Code of Ethics, although the primary emphasis of this paper is on theoretical analysis.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:[Yes]
Justification: Although the primary focus of this paper is theoretical analysis, discussions on the potential impacts of our research presented in Sections and 6.
Guidelines:
19

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considcrations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification: The primary focus this paper theoretical analysis, and although it includes experiments, their purpose is to numerically validate the theory. Therefore, the concerns raised in the question do not apply.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes].
Justification: We provide citations or reference URLs for all of the code, data, and models used in our experiments (see Appendix G). We also declared the name of the licence is CC-BY 4.0 in our submission page of OpenReview.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
20

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers thcode com / da t sets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
The primary focus of this paper theoretical analysis, and although it includes experiments, their purpose is to numerically validate the theory. Therefore, the concerns raised in the question do not apply.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification: We do not utilize such services, so the concerns raised in the question not applicable to us.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: The primary focus this paper theoretical analysis, and it has been con- firmed that the concerns raised in the question are not applicable.
21

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA].
Justification: This paper does not rely on LLMs for any theoretical analysis.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: : /t////eurr/////// ps conc/eeeeeessss / 2025/ LLM) for what should or should not be described.
22

---

A
Notation used in the main paper
We summarize the notation we used in the main part of our paper.
Category
Symbol
Meaning
The sample
X,2
A data and latent space
unknown generating distribution
A XCX
A radius of data space
A data
S [8.] E X
A training dalaset
model
e= == Rel
A codebook, where is the size of codebook
encoder parameter
8 Rd
A docoder parameter
(0, fe: X 2
A model parameters
An encoder network
Be 6.
A decoder network
A posterior distribution over J given c, X
A temperature parameter used softmax
A(A.F.a)
A é covering number with input for the encoder function class J
A:
A randomized algonthm
A randomized algorithm given 8 reconstruction loss function
Algorithm and loss functions
4:W x x +
An expected loss function over
gem(x,
The expected generalization error based on reconstruction
W2(D,A)
The 2- 2-Wasscrstein distance between P and á
x2
A supersample used in the IT analysis
The ys-th row X
U (Ui....,
Un) Uniformí (0, 13²)
Random index used in the IT analysis
Xu = (Xmo Ra-1
A training dataset in the supersample setting
Supersample setting
Ny = (X (Xmo, Pamn
A lest datasel in the supersample setting, where O.. Un
o. = Im glmmle d, Xmor..)
A joint distribution over index on the training datasct
X.) 11 g(mmle Xmm
A joint distribution over index
dataset A posterior distribution J
Oi al] XolalJo N.)
Q Eng(Jle, (eleeJl 0o)
A dependent prior distribution over
ml
A data-independent prior distribution over
12
PTT) 17(2))
randomn permutation lollowing a distirubiton
X1 An.......
Randomly permuted supersamples
Xr. (8n
Xx.)
The test dataset
Permutation symmetric setting
Nx. (X
The training dataset
ql NT.) - Im of a &r.)
A joint distribution over index on the test dataset
A joint distribution over index on the training dataset
Qr = gilee, Xn, (g Xr.)
A joint posterior distribution
Qi BotJlo, a. de
A data-dopendent prior distribution over
B Additional discussion and related work
Here, we provide additional discussion and comparison between our study and existing work.
B.1
Related work
Here we briefly introduce additional related existing work, especially about the IT analysis. In IT analysis [83], the generalization error is evaluated on the basis of the MI between learned parameters and training data. This approach closely related to PAC-Bayes theory and has been extended through supersample settings [63] to exploit the symmetry between test and training data. This setting has been applied to the study of gencralization based on outputs of functions [30], losses [32. 79], and hypothesis entropy [17]. The relationship between IT analysis and the IB hypothesis has been discussed from numerical and algorithmic perspectives [80, 44]. More recently, Sefidgaran et al. [57] theoretically studied latent variable models using IT analysis, demonstrating that generalization can be characterized by the complexity the encoder and latent variables without relying on decoder information. They also developed theoretical link among IT analysis, the IB hypothesis, and MDL by using compression bounds [10].
There exist several analyses focusing on VQ-VAE and related architectures. Vuong [73] investigated the supervised setting of vector-quantized models, whereas our analysis is purely unsupervised. Beyond the supervised-unsupervvss distinction, work differs from theirs in several fundamental
23

---

ways. First, they study continuous and differentiable relaxation of the discrete latent-variable model, making more amenable optimization analysis. Second, this relaxation allows their framework to examine not only the generalization gap but also how the magnitude of the training loss itself influenced by the discrete representation. Finally, their generalization guarantees rely on uniform convergence bounds, effectively reducing the problem to K-class clustering. In contrast, our analysis is based on algorithm-dependent, information-theoret bounds, following the line of work by Sefidgaran et al. [57].
Classical quantization theory also provides useful insights. Pollard [52] and Telgarsky & Das- gupta [65] established asymptotic consistency results for k-means clustering. Although their set- clusttrrnnn without deep models- differs significantly from ours, the quantization procedure they analyze is conceptually related to the discrete latent representations used in VQ-VAE Impor- tantly, Vuong [73] build their analysis upon these classical results. The main distinction is that the latter works provide asymptotic guarantees specific to clustering, whereas our analysis provides finite-sample, non-asymptotic guarantees for deep generative models. Nonetheless, the connection highlights how classical quantization theory can inform the study of modern deep architectures, and it suggests that such tools may prove valuable when extending our framework to analyze loss minimization in addition to generalization.
B.2
Comparison with existing bounds
Here, we compare our bounds with those in existing work. Theorem 2 resembles the results of Mhacke et al. [46] since both bounds include the empirical KI. term in the upper bounds, and the posterior distribution corresponds to the variational posterior distribution. The key difference is that Mbacke et al. [46] assumed fixed decoder, whereas our analysis incorporates the learning process under the assumption of discrete latent space and squared reconstruction loss. Another distinction is that their generalization bound does not become 0 as n + oo due to two reasons. One is the presence of the empirical KL term, which we address in Theorem using permutation symmetry. Our technique can be regarded as developing the appropriate prior distribution in PAC-Bayes bound. The second reason is the presence of the average distance n. Σm= Ex | Sm in the existing bound, which is inherent to the data distribution and may not vanish as - co. Our use of the squared loss in the analysis mitigates this problematic term, as detailed in Appendix D.1.
Our proof techniques are based on Sefidgaran et al. [57]. However, we could not directly apply their methods, as the reconstruction loss reuses input data, unlike in classification settings. We resolve this by combining the data regeneration technique used in the proof of Mbacke et al. [46]. Additionally, we introduced new permutation symmetric setting, leading to a bound that controls mutual information in Theorem 3. Our setting is closely related to the type-2 symmetry proposed in Sefidgaran al. [57]. which involves random permutations selecting n indices from 2n with uniform distribution 1/(2r), whereas our setting requires the consideration of the order of the permutation index to evaluate the exponential moment (see Appendix E. Finally, we theoretically studied the behavior of the CMI (Theorem 4) focusing on the complexity of the encoder, whereas Sefidgaran et al. [57] provided the bounds based on the CMI without such discussion.
The existing analyses based on the IB hypothesis [71, 28, 38, 72] assumed that both the latent variables and data are discrete, and their obtained bounds explicitly depend on the latent space size or show exponential dependence on the MI. In contrast, we assume that only latent variables discrete and the resulting bound does not explicitly depend on the number of discrete states nor exhibit exponential dependence MI. Furthermore, our bound shows the dependency on d2 not K, which is the significant difference compared with existing bounds.
B.3 Discussion and comparison of our prior and posterior and existing work
Here, we explain how the prior distribution is used in our proof and why two prior distributions are introduced in our bound. First, the IT analysis with supersample reformulates generalization analysis as the problem of estimating which samples were used for training when data is randomly shuffled based on U. If this estimation difficult, our model generalizes well. In the basic IT analysis (Theorem 1), such difficulty is measured by the CMI between U and the loss function lo
24

---

U
e, Φ, 0
U
e, Φ
J
Figure 4: Graphical models illustrating the different dependency structures of the random variables considered in the basic IT analysis and in this study. The left figure represents the dependency structure in the basic IT analysis, which simply evaluates the loss function in supervised learning settings, whereas the right figure corresponds to our analysis in the unsupervised learning setting.
Of course, such shuffling is not performed in actual algorithms; it is introduced only for theoretical analysis using the Donsker-Varee Varadhan incquality [25], where such shuffling is defined by the prior and posterior distributions dependent on U.
In basic IT analyses (Theorem 1) for supervised learning, by shuffling with U, we observe how the loss 4o (W, X) changes. Here, the goal is to estimate U from the observed losses. As depicted in Figure 4, U and loW, X) depend on all parameters, including the decoder, resulting in a bound that depends all parameters.
Our goal to eliminate the dependency between the decoder and latent variables (LVs). To achieve this, introduce prior and posterior that establish the dependency depicted in Figure 4. The key idea that by introducing a new dependency between U and LVs, we can directly shuffle U, leading to bound that isolates the role of LVs without involving the decoder. For additional discussions the necessary conditions for the prior, see Appendix D.2.
Finally, we show the additional explanation of Figure 1. The figure illustrates the difference between the existing fCMI and our new CMI. The left figure illustrates the setting of existing fCMI where J follows the distribution in the setting of Eq. (5), see Appnexdix C.2 for the detail. Thus, in the existing fCMI, J and U are conditionally independent given and 6 and X. On the other hand, the right figure is our setting and there is an edge between U and J directly, and thus J and U are conditionally independent given e and e and X, which results in the difference of existing fCMI and our CMI. See Appendix D.5 and Appendix D.3 for the additional discussion about the fCMI.
C Proofs for Section and additional discussion
C.1 Proof of Theorem
This is just the consequence of the existing eCMI bound [32]. We can confirm this as follows;
Note that the generalization error can be expressed as the supersample
gen D)
Es,x B 19( (XU
1
Σ
n m=
E
E
Σ m=1
E
Je e, m (( g0(emm))
X.U 0.0.0.0 Xx)
10, Bggt ((m....____mmmmmmm....0 90(em))))
Given that the loss is bounded by [0, A), the integrated is A-sub-Gaussian random variable. Thus, from Hellström & Durisi [32], the generalization error bound that satisfies the o² sub Gaussianity is bounded I(W; U)) holds by the data processing inequality.
20d T(((A( UI&), we obtain the result. Finally T(I(W, U):U(() <
25

---

C.2 Proof for Eq. (5) and additional discussion
Here we prove Eq. (5). It is important note that this upper bound characterized by the CMI [lo (W, UW; This CMI depends on the decoder and encoder information, distinguishing it from the results presented in our main Theorems 2 and 3, which do not require the decoder's information.
To clarify this distinction, let us introduce the necessary notation. Following the notation in Sec- tion 3.1, we define y = go (ey), where go(ez) implies applying go(:) elementwise to e Under these notations, have the following relations:
T(oo (W, U()) & I(Y:UIX) & T(0;UIX) + T(e
where the first inequality is obtained by the data processing inequality (DPI) and the second inequality is obtained by the chain rule of CMI and the DPI. This result demonstrates that the decoder information cannot be eliminated from the basic bound, which clarifies the fundamental difference compared to our result (Theorems 2 and 3), Moreover, since the decoder and encoder are learned simultaneously using the same training data, they are not independent. This makes unclear how the latent variables and the encoder's capacity affect generalization, as it is difficult to eliminate the decoder's 's dependency on them.
C.3 Additional discussion when K =
Another limitation of the basic IT-boound arises when considering K = 1 as limiting setting. From the definition of the squared loss, the generalization error is given by:
(
gen (n, D) <
Var[X]
(1I)
Vn'
The proof of this is described below. This upper bound is intuitive: for K = 1, the model effectively ignores the input data and embeds all samples into the same latent variable, which can be interpreted as form of strong regularization. Consequently, the impact of overfitting due to training the decoder network relatively limited, and the generalization error can be seen, in a sense, as being comparable to the inherent variability of the data itself.
develop a more sophisticated generalization bound that The above observations motivate explicitly captures the role of representation.
Proof of Eq. (11). Since K 1, we express {e). By using the definition of the squared loss, we have
gen(n, n, D) = Eg
[[X]
Σ m=1
Sm
so(e))
where we used the fact that the generated data always use as latent variable since {e) when K = 1. Then by using the Cauchy-Schwart inequality, we have
E. go(e)l
A
gen (n, D) S Var[X]
V1
where we used the fact that the diameter the instance space bounded by A.
D Proofs for Section
In the proofs, we repeatedly use the following type of exponential moment inequality, which is often used the proof of McDiarmid's inequality. A function f x IR has the bounded differences property if for some nonnegative constants cI,..., Cn. the following holds for all i:
sup ZI.... [f xn) (eo)-f(r1n..) f(r II-I 24 241.
Cs
1sisn.
Assuming X Ni...., , X, are independent random variables taking values X, we have the following lemma:
26

---

Lemma 4 (Used in the proof of McDiarmid's inequality). Given a function with the bounded differences property, for any E. we have:
22 E ( -/)BB//xx))xxxxxx,, -.. Xw)ll] s Ses Ei
D.1 Proof of Theorem 2
We express qJ]le, Φ. X) - q(J,Jle, Φ, Xo. Xu) = q(Jee, o. X (J]e, 9, Xy). Hereinafter, we simplify the notation by expressing X as X. For simplification in the proof, we omit the absolute operation for the generalization gap. The reverse bound can be proven in similar manner. We first express the generalization error of the reconstruction loss using the supersample as follows
E
o, oy (XX m, go(ex)) k=Jm k-Jmm
VTA
go(en))
Xm go(ex)] 1-=
k=1
K
Xm, go(ex)) 1 I (12)
R=
m=1
where the first term corresponds to the test loss and the second term corresponds to the training loss. Recall the learning algorithm and posterior distribution:
e, ④. 0 q(,, Φ, 0l)), Jm q(J o, Sm). Here fei...... ek] is the codebook, and J and (J represents the index chosen from the codebook.
Conditioned on X and U, then decompose Eq. (12) follows
K
g0 qne le.. k==
E
la (m. Ik=Jm
K
E Eyle a. (l (xx,e ge (0()) LRmmm
k=1
m=1
E Xx ge(ex))))_mm le.. Lk=dm
(13)
We will separately upper bound these terms.
D.1.1 Bounding first and second terms
The decomposition of the generalization error, as shown in Eq. (13), allows us bound the first and second terms as follows.
We apply Donsker-Varadee 's inequality between the following two distributions:
Q = P(U)q(e, o, 8 (z) Xx,
Ps == P(U)g((, o 0[x)) E q(], o, Xu..
(14)
P(U")
27

---

These correspond to the posterior and data-dependent prior distributions defined in Section 3.1. Then, for any RR+, have
K
E (ixeed. go(e)) (Eg(Jn
Mm (.q(Jmlle00X.mmmm k=J R. Aa JmJ
K
mm (o(e))) (I==Jm - 1m=dmm)
< [L(Q)Ps) + log Eps exp
Am m=1
To simplify the notation, we express J Jo, Jm Jm.o. J J1, and I' Jm. Let U be random variable taking 0, 1 with a uniform distribution. Since Ps is symmetric with respect to the permutation of Jo and J1. we can bound the exponential moment as:
K
log Ep(())((.. B ((Jo.J 1e.. exp p(0))
1(mm, 9o((x)) (Lx=Jmoo - 1 1x=Jm.))
k=1 m=1
log EP(Uieee,a))))
g v(Jo.Ji Mo.. P((M))) P(U))
K
1(X go(ex)) (KR=Smo lR=Jm.0))
exp
1= m=
log Bp(C)o(ess:0xx))
3 e(Jo.J (or Br p(o
1(Xm,0..:0 (1k=Jm..r k= Ix=Jm. Jm.w"
exp
In the final line, we apply McDiarmid's inequality since U are n i.i.d. random variables. To use McDiarmid's inequality Lemma 4, we use the stability caused by replacing one of the elements i.idd random variables. To estimate the coefficients of stability in Lemma 4, let U = (UT, ....... UK)) then
sup (UN D
1(X m (e(e))) (1 [I=Jm_ 1 JmJum
(15)
k= mm
12
I(X (0.mm0m go(e)))) (Ik=Jmoou Ik=Jm.
m momm
K
(Xmm.0,,90(Ex)) (1==J 1 k== ml wum
Σ (Xmm Dr. go(ex)) [Im=Ja - Jun wo
sup (UM D
21A
Σ u(xm (XXm, 0% so(ex)
(k=JJm om
1 -k= m
Here, the maximum change caused by replacing one element of U is 2XA/n, thus, its log of the exponential moment is bounded by (2AA/n)2 n X²22 /22.. Thus from Lemma 4, we have
log Ep(U)g(e.s)))))) B g(Jo.Ji le.d. exp p(O')
ΣΣ Σ
A
K
1(Xm, (Xm.e.).o(e.)) (Lu=Jm.o - LR=Jm.))
k= m=1
A
2n
The first and second terms in Eq. (13) are upper bounded by
AA
Ex ExXL(([Ps)
(16)
2n
28

---

D.1.2 Bounding third and fourth terms
Next, we upper bound the third and fourth terms in Eq. (13);
K
7
R
oo m,, g0(ck) Egt (e kl
(17)
k=1
m=1
We simplify the notation by expressing [ N. -k= as Pkem and use the square loss:
8x,0
E
(oxx))
Eote.s.01xx,)((MMmt. go(ex) Pk.
71
7
K
= Ex,u
E Reteed.0 (1) 112 mm 112) Pk.m
72
k=1
+ Ex.u
o (Xm,mm Xm,Um) go(ex) Pk.m
m=1
Ex,U
(IIX mm Om 112 mm 112) E
P Pkmm
n
k (Exx- - -Sm) B)(e,
+ Es
(f(e))lkm
m=1
2 Es n
(xx X Sm) B.gee S)
go( (o(c))Pksm)
(18)
k=1
where we express (NX,,,, Xn,U,) (Si,..., Sn) as the training samples. In the last inequality, we used Σ Pk.m = and Ex,U Em=1 (I)Xm, 112 |mX (1 = 0 since X and U are i.d.
To evaluate the final line, we use the Donsker- Valadhan inequality between
n
g(e, 0|S) II
(am d. Sm),
Ps = a(e, o, 0|S)
II < (Jmle,
m==1
where π (Jmle,, Ø) is the prior distribution. which never depends on the training data.
Then we have
2
Es
(Ex - Sm)) Eg(e.,,91s)
go (o(e))Prc Pr.m
m=
1=1
1
2X
< Es (L(Q)Ps) s) + log Kpg exp
(ExS X -ggee,..)))
go(ex) Li=Jm
n
< Es KL(Q)Ps)
1 + Es
log Ep. exp
21 n
Σ
(xx X Sm)
Σ
K
go(ee))(1 Pkmm)
n
A=1
K
+ Egg
2
Σ
(Exx X- - Sm)
Σ
(19)
m=1
29

---

where Pky
k.m (n(Jmo I==J,. Clearly, this does not depend on the index m, so we express
Ph. k
Then the last term becomes
K 1 Σ (ExX- Sm) Σ go(e)) S EsEps Ex
k
EsEPs
Σ
Sm
go
(ex
P
m=1
m=
Es
ExX
Sm m
VA
m=1
1 12
A Var
Σ
Sm
Var (X)
(20)
4n
2/n'
where we used the fact that the variance of random variables with bounded in (a, b) is upper bounded by (b- a)² /4m (the extension the d-dimensional random variable straightforward) and thus, Var (x)= S A/4. Then the exponential moment term becomes
K Σ
1 1 X
log Eps exp
21
Σ
(Ex X Sm)
(1(e))(1 k==m Pk.m)
m=1
k=1
1 Es log Epg exp
2X n
(Ex X
Sm)
go(ex)(Lk=1 P!")
n
Here we use the McDiarmid's inequality for n random variables J. Then we estimate the stability coefficient similarly to Eq. (15), which is upper bounded by AA/n. Then from Lemma 4, the AA2/2n exponential moment bounded by (2XA/m) x AA /2n Thus, the second term is upper bounded by
AA 2n
A
kL(QQ)ss) +
(21)
Vn
By optimizing the first and second terms of Eqs. (16) and (21), we have
E x E (
(T, (12) + Es KI
A
2
n
where
Q q( J e Φ X Xu)
Q2 P(U")
qJ.J J e, o. XU.)
Q II (Jm l, d. Sm). m=1
Ps
II (Tm ( 0). m=1
D.2 Necessarily conditions for the prior and the limitation of the existing supersample setting
Here, we further discuss the necessary conditions for the prior distribution to derive a meaningful generalization bound. The proof strategy in Appendix D. clarifies this point: in the proof, we decompose the generalization bound in Eq. (13) and separately upper bound the first two terms and the latter two terms.
30

---

For the first and second terms, the analysis follows standard generalization error techniques. When using a prior and posterior distribution characterized by the shuffling of the supersample X, such as the index variable U. the shuffling must swap test and training data to enable generalization evaluation. By ensuring this swap, we can properly assess overfitting.
For the third and fourth terms, after applying the Donsker- Vaaaadan lemma, is crucial ensure that the probability Pk,m does not depend on the sample index m to control the exponential moment in Eq. (19). This requires satisfying PK,,, = PK. meaning that the probability of assigning the mi-th data point to the k-th codebook must be independent of m. By definition, this condition holds when the distribution of the latent variables remains invariant after shuffling.
From these observations, we conclude that the prior used for shuffling must: (A) Preserve the distribution of the LVs to eliminate interdependencies between LVs and the decoder, and (B) Swap test and training data points to evaluate overfitting, as discussed in Section 3.1.
Using the supersample ensures condition (B). For condition (A), we employ the prior distribution (Jmn e, Φ), which removes sample index dependency and guarantees PK.. P Consequently, the empirical KL divergence in Theorem arises from the third and fourth terms in Eq. (13), as detailed in AppendixD.
Based on these findings, propose the following type of prior distribution:
I (Jm/le ó, Sm/),
Ps = q(e, 0, 015)
m=1m's m'
which provides an empirical approximation of the marginal distribution using available samples. Since this distribution does not explicitly depend on the sample index, we can bound the exponential moment similarly to the approach in Appendix D.1.2.
However, using the prior distribution in Eq. (14) to bound the third and fourth terms of Eq. (13) is not feasible. The issue is that applying the Donsker-Valadhan Valadhan lemma with Eq. (14) to these terms does not yield bound of order O(1/ (R)/ achieved in Eq. (20). This limitation arises because the dependency on the sample index in Eq. (14) prevents us from leveraging the symmetry between the test and training datasets via the supersample index U. As a result, the prior distribution's 's symmetry cannot be exploited to simplify the bounds for these terms.
D.3
Comparison with the FCMI
Here, we analyze the relationship between CMI and existing forms of fCMI in more detail. As highlighted in the main paper, a key distinction is that our CMI conditioned on all model parameters, whereas existing fCMI methods marginalize over these parameters.
To further explore this difference, we consider marginalizing over the encoder parameter, Φ. In the proof of Theorem 2, we perform this marginalization over Φ in Eq. (12) and obtain
E Fm Xmm
g0()))) k=J..
E X( (ole))
m==
K
E
qJmn Jm. 10,0, X Xm Ie
lxmmm. xo 8o(cx)l121 1-
k=1
mm
E
(ex) 1k=Jm 11
and proceed with the proof in the same way. We apply the Donsker-Varadhan inequality between the following distributions, instead of Eq. (14):
Q = P(U) ( 0, Xo, P = P(U)g(e, X E.. Xo.,
31

---

This incorporates marginalization over ø in Eq. (14), resulting in the following KL divergence in the upper bound:
ExKL(Q Ex E P(
Unlike Theorem 2, this CMI explicitly involves the decoder parameter 8. By marginalizing over ø. decoder information is integrated into the upper bound, making Theorem distinct from existing iCMI bounds. In Appendix D.5, further discussion from the viewpoint of the difference of the graphical model between our CMI and existing fCMI is given.
D.4
Proof of Lemma 2
We remark that the following relationship holds for m -l..., ...,, by definition;
1(Jmi Sm/e, Snlled o) o) Den log (Jmle, O,
(22)
(e (Jm ee o, Sm)
(Jm c, C. Sm)
= =Esl Bie Be(Jm log E (( e Sm)
Next, we show ( o, S1) = .... (c, S.)) holds under the given assumption. To prove this, it is suffice to show that g(S) e, 6) = _.. g(S, le, Φ) holds. Under the given assumption
((S:) =... =.. q(e,
holds, see Li et al. [42] for the proof. Then for E [n]], we have
dlc ((.:)((sss))) = g(S.)c, p)p(c, o)
and since all training data points are drawn i.idd form D. have
q(e, q
Then, for any j * i E [n], we also have
a(e, ,{ ((Syle, o)p(e,
since g(e, q(e, we conclude that g(S.(e, Φ) ((Syle, Φ). This implies Ey(S, (J)iee S1)= =--==-. By (so o. S.) holds under the given assumption. So we o, Sm). From Eq. (22), we have
use the joint distribution these P II 1e.
KT. (1 (u, P) T(Jmi S,
Finally, we show that above minimizes the E. KL (LJ, [P). We consider the prior P' that satisfies the assumption of the Theorem 7, that is, prepare some distributions that satisfies q(Jile, 6) = ... g(Jn le, Φ) and define P' == I1", (Jmlle, By the definition, have that
Es EsEy(e, KL PP') = I(Jm: Sm Sm, Φ) EsE KL.
Thus, when using P' P minimizes the empirical KL divergence.
32

---

D.5 Proof of Eq. (8)
Here discuss how we can upper bound of the complexity term of the obtained bound. From the definition, we have the following relation;
Ex, (
qJ. Jcc, Φ. Xr. Xg.Xx) Xu)
log
E q(J. J. 1 Xo.,
P(T))
q Je, X Xu)
=Bexppecxeeekk//jaaaxxxxxxxkk log
E P(U))
e No, Xu")
qJ X Xt)
RRAPPPONNSSUUUUAAAAAXAAEXXX log
E q(J, o, X
P(D))
yJJ,J]
Φ, X Xu)
-BxxprecossB/uessaaaaaaaaxxxx log
E
q(J JJ o. X Xyr)
E
q (J. J 0, X X
+ +erxrreccssxruuusxxxxaaeexxxxxx log ((
E P(U))
JJ. 0, X (u,))))
E
X
XX) + Tww.roayyrroonaandde.e..... log ((
E P(U))
qJ,,Jle 0 Xv.
e, 1 P(U'le,
log
P(U")
P(e,
= =[ij,J;Ule (xx)))))))xxx Bxx log
E P(e, 6|X, P") P(e, U')P(U")
= =[[J,J 0, X) Bx log
Eucuy P(e, d X, P(UP(U))
=[[J,J; o. X) ((e,
where used the data processing inequality of the KL divergence.
D.6 The role of / [j: (J:
The role of [[]; [[: Ule, o, X)) is clarified through the following upper bound:
O, S
Σ [eri Xm, ()) m=l +
(L.,
(23)
The first term represents the information retained by the LVs from the training data in the IB hypothesis, while the second term corresponds the regularization based on empirical KI. divergence discussed earlier.
Here we prove Eq. (23). We define (Jle,d (eee)) = II (Jmle, ø), oJ T(Jm e, Φ).
and n (J]e, Φ) (J, Φ) = (J e, d) (J(e, Φ)) where each x (Jmle, Φ)) the marginal distribu- tion of 7Jmmle, Xm))
33

---

Then by the definition of the CMI, we have 6,
= =Bx,u vie X KL[g(Jle o, ( Xo,,
S Exx, o X
(L (J
=Ex ( x
KL (Lgg (J)e, + Ex F ,( KL[g o, (J),
=xx o( )
(L,(([mlle, os (mmm))
+ E x pee
Σ
=) + EsBg(e,)1s)
m=1
EnT(es;Xle, By n
(m) 6)).
D.7 Proof of Lemma and and additional discussion
Proof of Lemma J. From the definition of the CMI, we have
Φ, X) H[J @2 X] H[JUU, e, o, X] H[Jee, o, X] H[]]x]. Here, we consider the case where fø. input data to one of the K indices. This scenario can be viewed as a K-class classification problem, allowing us to directly apply the results from Harutyunyan et al. [30]. They demonstrated that the CMI for multi-class classification problems can be hopeer-bunded using the Natarajan dimension, combinatorial measure that generalizes the VC dimension to the multiclass setting.
- [K] represents a deterministic encoder that maps
Using this concept, we obtain the following characterization:
When employing deterministic encoder network f/2 : X [K] that belongs class with finite Natarajan dimension dæ and assuming 2n > dx + 1, we derive the following bound:
[[J: Uc, o, X) < dx log ( K 2en
(24)
dk
The proof follows exactly as in Theorem of Harutyunyan et al. [30].
Thus, by regularizing the capacity of the encoder model (via the Natarajan dimension), the CMI term scales as Olog n)., ensuring controlled generalization behavior. Examples of models that satisfy the
finite Natarajan dimension are shown in Jin [36] and Daniely et al. [16]. Also, see Bendavid et al. [8], which shows that the VC dimension of the multiclass loss function characterizes the graph dimension, and the graph dimension upper bounds the Natarajan dimension.
Proof of Lemma 3. Since we consider the setting of Lemma 2, we consider the case of (P)
(L(QQ. [P) = Σm [Jmm; Sm e, Φ). Following the above setting of I(J; Ule, Φi, X), that is,
Legs X + [K] satisfies the Natarajan dimension dx > 1. Then for each we have
I(Jm; Sm le, Φ) = H[Jm le, Φ) Hmmm|mme Φ) = [] l Ø) < log K < (dx + 1) log K.
Thus (L PP) = Em [(Jm S,, /)/n < log K = O(1).
The difference between [(J; Ule 6, X) and [(Jm; Sm le, Φ) lies in their conditioning. Since I[J; Ule o, X) is conditioned all 2n data points, only depends the combinatorial num- ber of distinct index values. contrast, I [Jmm Sm,/c. Φ) does not condition on the input data, making regularization based solely the Natarajan dimension insufficient control complexity.
For the discussion the stochastic encoder, see Appendix E.4, where we consider the metric entropy of fo(-), which leads similar discussion.
34

---

D.7.1 Additional discussion for the Natarajan dimension
Here, we briefly discuss the Natarajan dimension. First, it can be both upper and lower bounded by the graph dimension, another common combinatorial measure for multi-class classification problems (see Lemma 4 and Proposition 1 in Guermeur [27]).
The Natarajan dimension can also be upper bounded by the 7 fat-shattering dimension of each class. Specifically, given f'e, Φ : X + [K], let the k-th element of its output be denoted as fe, の (kk) for k 1, ... K. If each s/( has finite 7-shattering dimension, then the Natarajan dimension of fe can be bounded by the sum the y-shattering dimensions of its components, multiplied by constant coefficient (see Lemma 10 in Guermeur [27]).
Examples of fat-shattering dimension evaluations can be found in Bartlett Maass [7], which analyzes neural network models, and Gottlieb et al. [24], which examines the fat-shattering dimension of Lipschitz function classes. If our encoder network satisfies these properties, its covering number can be appropriately bounded.
D.8 Discussion about the overfitting term
Here, we discuss how the overfitting terms relate to different algorithms. First, from the data processing inequality [15], we obtain
I(e, o; UI < I [(e, d)
where we express Ny as the training dataset S. Since this expression does not include conditioning, refer to it the parameter MI. Several existing studies have analyzed parameter MI under commonly used algorithms.
Pensia et al. [51] first established the relationship between noisy iterative algorithms and parameter MI. Subsequently, Wang et al. [76] and Wang et al. [77] investigated the parameter MI of the SGLD algorithm from the perspective of noisy iterative algorithms, while Futami & Fujisawa [20] analyzed it in the continuous- time limit. Neu et al. [50] was the first to examine parameter MI in SGD, with the step size. Furthermore, Haghifam et al. [29]
Wang & Mao [78] later improving its dependency provided formal limitations in the context of stochastic convex optimization.
In addition to these, in the Bayesian setting, where we assume that the training dataset is conditionally ii.d (see Clarke & Barron [14] for the formal settings), Clarke Barron [14] (see also Rissanen [53], Haussler & Opper [31]) clarified that the mutual information between learned parameter and training dataset is described as follows: w takes a value in d'dimensional compact subset Rd
and p(y|æ;; |a;; w) is smooth in w, then + we have
T(W; S) log
+ h(W) Elg det.J + o(1),
2xe
where h(W) is the differential entropy of W. and J is the Fisher information matrix of p(||X; W).
Steinke & Zakynthinou [63] clarified that the CMI is upper bounded by the the stability. For example, the training algorithm satisfies v 22e-differentially private (DP) algorithm, then CMI is upper- bounded by en. So this is controlled by the DP algorithm. The Gibbs algorithm equipped with [0, 1] bounded loss function, satisfies Oi/nn)-DP, thus CMI is controlled adequately. Steinke Zakynthinou [63] also clarified that if the algorithm is 5 stable in total variation distance, then CMI is upper bounded by ôn. Li et al. [42] studied the total variation stability for the SGD, and Mou et al. [48] studied such stability of the SGLD algorithm and its relation to the PAC-Bayesian bound. [49] investigated the CMI of SGLD as the noisy iterative algorithm.
E Proofs for Section 4
E.1 Proof of Theorem 3
We define T = (To. Tı}. where XT. "X,,,..,,yy. serves as the test datasct and XT, (X (XT..1...... XYan) serves as the training dataset. We further express Xr, = (X,,...., = (XT XTo..) and XT, .eb......,,..lll To emphasize the dependence of the
35

---

dataset on T, we write the posterior distribution as qJ]le, - [J. ,, qJJ. (J.JJe, 0, XT, XT,) = g e, o, (TJe, o, XT,)
Hereinafter, we express X as X to simplify the notation. Under the permutation symmetric settings, the generalization error can be expressed as
" Σ Bes.ullessssss.. go(esm))
(ll S,X
K
7
EX,T
By(Jmle,dd.Nn ( go(e)))1k=n
π
m=
EX.T
(e (XT,,,, (00T))...((((()ee__e_e
k=1
m=1
70
EXXT T
) XT. - go(e=)]l k=
T1
K
Ex,T
Be X1, (xT - go(ex))121 k=Jm
m=1
We then decompose the loss as follows
gen(n, n2, D)
(25)
K
Ex,
E
km
m=1
Ex,r
K
+ EX,T
or \/To. - go(ex)]1 (x=
71
m=1
K
EX,T
A.. XIX,, 10(ex)11211122
k=1
m=1
First, we upper bound the first two terms by applying the Donsker- Varadhan inequality. Consider the joint distribution and the prior distribution, defined as follows:
Q P(T) 8, 0 )g JJc o. XT). P P(T)q((, 9 x(xr.) E
(26)
Xr.).
P(T))
This corresponds to the posterior and data-dependent prior distributions defined in Section 4.1. Then we then obtain
EXT
011, - (e((e)) (Bn In- EEg Ii=Jm
m=l
K
< Ex K)( log Ep exp
1
XTo. so(ex)11 (1k=Jm - Iamsma) (27)
k= m=1
36

---

Note that E
g(J,Jle, 0, (rr)) symmetric with respect to the permutation of T. Thus, we have P(T))
K
log (rTT)((A,,)) E d.. p(1))
exp
((Tro,.. go(ex)) (Ix=Jm. 1x=Jmm)
1= m=11
= logg (p(T))(e(.d))x.) B PPT) P(T))
((XTo,.. oo (e(e))
exp
log E (P(T))(e,
p(T) (e.
E exp
A
I(XT. g0(ck)) (Ie-Jry
1 Jry
k= m=
To simplify the notation, define T" (To TT) (T......... that T J.m for 1,...,, and 0, are not independent of each other due the permutation that generates them. Therefore, we cannot directly apply standard concentration inequalities, as is possible in the existing supersample setting.
0. 1,1---.. T T Note
To address this, we use the results from Joag-Dev & Proschan [37], which concern the negative association of permutation variables. From Theorem 2.11 in Joag- Dev & Proschan [37], the distri- bution P(T) satisfics negative association. Additionally, as discussed in Section 3.3 of Joag-Dev & Proschan [37] and further in Proposition 4 and 5 of Dubhashi & Ranjan [18], we have that
log E (p())
E g(..Jle.
K
E exp
1 1(TT. (XXTom-9((en (1A=Jrg... 1k= 1k=Jry
m=
< log E ((T))((eA,)))))) E p(P))
E ETT. P(TY exp
(T go(ex)) (IamArg - Re= (em
m=
where P(T j.m) is the marginal distribution, implying that T i.m are now 2n independent random variables. Intuitively, the results in Joag-Dev & Proschan [37] indicate that the elements of the permutation index, which follow the permutation distribution, are negatively correlated. As a result, the expectation of the marginal distribution is larger than that of the joint distribution.
Since (T are independent, we can apply MeDiarmid's inequality, which leads to the results in
log (p(T)s(e.00)) B ((J.Jle, p(T))
K Σ
(TT. To 9o (ex)) (I=-Jm. Immman))
exp
< log E Ep(T))(ef.0))))) P(P)
E ofJ de))
E TT 1 P(T exp
1(Tr.
(o(ex)) (o(ex))(1 (x=
-Ik=dry
n Amm
m=1
X²A2
(28)
n
This is derived similarly to Eq. (15). Note that there are variables so the calculation of the upper bound is (AA/n)211 2n A²22 2//
37

---

Next, we focus on the third and fourth terms in Eq. (25). Similarly to Eq. (18), we have
K
n
EX,T
E 10 )1 Il go(ex) (o((e))l21ac 1k=
71
K
-XTTT
By Xm )q(e,
(o(())))1 1k=J
k=1
m=1
2
Bx,T
(Xr.. XTo.m)
go (ex) -i=Jm
m=
k=1
k
2A
S Ex (TT(Q/P)
Ex log exp
exp
(XTim
XTo
go I==
7
Exx 1 (I((PP))
< Ex
+ Ex x
log E ((T R mene
(()))
(J.JJo,
B 11 (0mi=:111000 11 P(T
2X
n
exp
m Xoom Σ L
(29)
m=1
We first evaluate the expectation of the exponential moment;
2
Ω = (
(Xr
XTro EE P(Tt)
Let us now focus on the expectation
E (J,, o, XT.. Due to the permutation symmetry, P(T))
g Jle.... Ek 1i= is the same for all m. P(T))
For instance, when n = 2. the possible permutations of are T (1,2,3, 4), 41, .).... resulting in 24 distinct patterns and thus
Pk.1 E qfJ (J.Jle.d.Xxo) I k=J, ha4///eeeeHHHdeeoHHHHHHHH0HHHHee 1R=s p(T))
Pk.2 E
q(..J (le.d). 1=jj= - haw. BagaaaokkKHHoaaeeeeeoooooooaooaa 1== P(T))
38

---

Thus, all Pk,m does not depend on the index m. So we express E
g {(J.Je.
Ex= k==mm as
p(r))
Pk. Then Eq. (30) can be written as
K Σ ge(en) Ps.
Ex ((p
XT,
XTo
m=l
m=1
k=1
Br
Σ
XT
XTo.m
Q,e (l8. Σ Po(e))
m=1
n
n
-Eprry ExtO
XT 1m
XTo.
g(e,0, o|
Σ go
1
71
K
BXTr
XT
Exro
XTO
q(c,0, 61
Pp
m=1
m=1
k=
-ErrriEXTT
XTim
ExX
go(en)
71
m=l
K ge(e))
s B ((e,0,)XX,))
XT - Exx
BRTTEE x
" m=1
k=1
1 XT,, Exx
< B ((e,),
B a(e,,,o) XT,
go(e)) P
k=1
S <Ep(T)ExTY
1
Σ XT ExX VA.
n
n
We bound the above exactly same ways as Eq. (20), that is, we can upper bound the above by the variance of bounded random variable and thus, we have
A
Ep(T)EXTT
XT
ExX
S
4n
m=1
Thus, we have
2
2
A Vn
XT.
XTi.
X
Σ (o <
n
n
Let us back to the evaluation of the exponential moment in Eq. (29), we will evaluate the following
2x
m
Ex 7 (L(P) + Ex x log Ep exp
(XTs. -TTo
Σ go - -A22
+ Ω.
m
(31)
We then evaluate this similarly to Eq. (28), which uses the negative association of the permuta- tion distribution and McDiarmid's inequality. The the exponential moment is upper bounded by (2AA/n)2/88 x 2n X²A2/n // We then obtain
EXTT
E (o
(o |I|X..m. go(ex)ll 1
m==
EX,T
B d. 10(0,6,11X1, XT, - go(ex)) 1 k=Jm.
7
K
1
21
< Ex = KL) + Ex I
log Ep exp
(XT.. - -XTo
-
+
m=1
km
A
< <L( +
(32)
39

---

In conclusion, from Eqs. (28) and (32) we have
5AA2
A
gen(n, D) Ex KL(Q/P) +
4n
Vn
and optimizing the A, we have
3ExKL(QIP)
A
gen(n, D) S V
2n
We can slightly improve the coefficient of the first term in the above bound as follows. The above proof follows the approach in Appendix D.I. We separately apply the Donsker- Valadhan lemma for the first two terms and latter terms in Eq. (25). However, since the posterior and prior distributions used for the Donsker- Valadhan lemma are the same as shown in Eq. (26), we only need to use the Donsker-Valle Valadhan lemma once. This leads to improved coefficient.
Specifically, the proof goes as follows; combining Eqs. (27) and (31), we have simultaneously treat all terms in Eq. (25). By Donsker- Valadhan lemma, we have
gen D)
1 log Ep
< Ex KL(Q)P) + Ex X
2A (Ti..
exp
To 9 (I==Jm. Im)
T
Σ ( X52 Ω.
From the negative association property, the exponential moment term can be upper-bounded as log (.
E q(J.J]e. BTT. I P(T,)
P(T))
exp
K
n
1(XTo m. go(ex))
(1k=Jz
-Ik=Jpp 1.m
+
2x
(XT
NTo
K (e ( k=yg
k=
-10)
n
n
Since (T [. are independent, we can apply McDiarmid's inequality. The the exponential moment is upper bounded by ((1 2)AA/n)2/8 2n 2x222/4n. Thus, we have
A
gen(n, D) s Ex KL(Q + 9x²22 44
Vn
By optimizing X, we have
Ex
A
gen(n, (n, D) < 3A
VTi
E.2
Proof of Eq. (10) and discussion about the deterministic encoder
First, show
E Ex yle & [ S I(c, o; + (J:: exactly same way as Appendix D.6.
By the definition of the CMI, the CMI is expressed as the difference of entropy and conditional entropy. Since J is discrete, the entropy is always larger than 0. Thus, we have
[[J; Tle, é. X)= < H[]ee, o X] s H[]
where H is the Shannon entropy. Note that the entropy is bounded by the growth function, i.e., the maximum number different ways in which a dataset size 2n can be classified in K. And such quantity is bounded in the proof of Theorem 8 of Harutyunyan et al. [30], thus
((5)
K
2en
I(J: T/e, X) < dx log
dx
holds similarly to Eq. (24).
Thus, by regularizing the capacity of the encoder model (via the Natarajan dimension), the CMI term [[]; Tle, o, X))n scales as Olognn) See Appendix D.7 for the additional discussion.
40

---

E.3 Proof of Theorem 4
To prove the theorem, we prove more general result than Theorem 4, and then we apply that result to the specific setting of Theorem 4. Therefore, we first derive such general result.
E.3.1 Discretization in encoder function
Here, present the results for general stochastic encoder. For fixed & and e, assume that for all E X, for any j [K]. and for fixed ò R the following holds: q(J jle, fo(z)) s q(J = j/c. fx))) with R R*
Theorem 6. Assume that there exists positive constant A such that sup,, ||2 z'1l < A..
Then, when using Eq. (2) and under the same setting as Theorem 3, for any 8 (0, 1], we have
2log 26, 2n)
gen(n, D) S 2D
20/nh(0) nh(o) + +3A
1
We can show that Eq. (2) satisfies h(6) = 834,6, see Appendix E.3.3 for this proof. Thus by substituting this into the above Theorem, obtain Theorem 4.
Proof. When analyzing the contribution of the encoder model generalization, it is often necessary to discretize the function or parameters of the encoder to control the CMI using the metric entropy of the model. To achieve this, we consider d-cover f of the function. In this derivation, we examine both the supersample and permutation-invariin settings, highlighting that the supersample setting fails to establish a uniform convergence bound.
First, we begin with the supersample setting. Given supersample X, we recall the definition of the indices, In this theorem, we focus on the distribution of the index defined by the codebook and 2 E Z, where represents the output of the encoder fo(-). Thus, we express it as q(J 2). Moreover, in this section, we use the notation g(e, 6, 0 1|X,00 U) = q(e, o, 0(Xx). The joint distribution then given by:
Q' = P(X)))(())((ee o. U, ()rfI,)
Q ) ó, 6, U...
where qJle, f) represents the elementwise application of q(]le, .) to f zdn And pff(o, X) is the elementwise application of p(flø..) to X, which simply computes the encoder output for each sample in X.
Then, in (f(()), the discretization process is performed using the 8-cover (thus, it is represented by the Dirac mass). We express this as rf = off, f*), where fo is the selected point from the d-cover. Then, for ff U), we randomly shuffle e R22 with U. formally defining fo = (fer, fg). Thus, we write pff U) off, fg). Similarly, we define p(f[f, U) 5(f, fz))
This definition differs slightly from the posterior distribution in Eq. (14), where we first shuffle X with U before passing it through the encoder. This simple modification allows us to derive the bound based on metric entropy. When evaluating the generalization error bound, we are only concerned with J. By integrating out f, di and f, we focus on following posterior distributions:
= P(t)))((U)/(e...00..00.
Q =188)
41

---

To prove this lemma, we first replace the output of the encoder with that obtained using the ó-cover of the encoder network. First note that the generalization error can be written as
gen(n, D) E P(U))(()
E bed :0 go()))) k==J.
= E wWlpeUteeeeeeeooooiiidee
Σ
Σ
1(x (x -i(iiiii__mmmmmmmmm (0(e)mun:9((e)))
m=1
We also define the generalization under the delta cover of original function, conditioned
K
gen(n, D.6) B Bp (UC
E
q( f. (. 90(k)))(mmm))))))))))))))
n2
K
J0 (( M ( Ikm
9o
= E =c
Σ
(XM..,...(eEx))l4e ((((mmmumi99(e)) m=
L==1
For the latter purpose, we define
D To evaluate these gap, we apply the Donsker- Valadhan lemma between the two distributions Q, and Donsker-Valadhan
90(e))
I((mmum. (0mmumm.o((()))) 90(ex))
Qá,J-
gen D)
(33)
S geen(n, D.8) + E ( (KL
E E log E p(iie.tg) exp (Λrr E pille dd ) U.X
U,X
gen(n, D, (g)) 2mh(6) A where evaluated the KL divergence
AA2
+
[ = liQ log Q
2nK log M6) -2nh(6).
The inequality is owing to the proper that for all x E X, for any j E [K], and for a fixed e R+, q(J = jle, fx)) < q = jle, fz))) holds by assumption. We also evaluated the exponential moment term by using the fact that ーA < XXXX. upper bound the exponential moment.
qJ
> Em 1(Sm. go (eJ..))) < XA to
This implies that the first term corresponds to the generalization bound when using the g-cover of the encoder network. We can bound this term similarly Theorem 2,
KT Q P2)) + KI Q
gen(n, D, s 2
where consider the following posterior and data-dependent, and data-independent prior distribu- tions:
Q = 0x U)((le, () () X),
P
X),
P 6.
X),
42

---

where x(f) is the data independent prior distribution over the ò-covering, such as the uniform distribution. Combining these, we have
(L P3) +
gen D 2A nh(d) v
+
Vn'
As for the CMI term, we have
KL(Q s F,,
(34)
The proof of Eq. (34) is shown in below and this term can be bounded (logg) under moderate assumptions.
However, the second term (L IP), which corresponds to the empirical KL term, cannot be small as discussed in Theorem 2. That is, under the settings of Lemma 2, the empirical KL. behaves O(1), which is undesirable behavior.
So consider using the permutation symmetric setting. We proceed the discretization almost the same in the above super sample setting. IUnder this distribution, the generalization gap can again upper bounded similar Eq. (33). Then from Theorem 3, we have
K
gen(n, (n, D) S Ex
Σ
E alJnle 11 Xr, | | - g0(xe)]] k=Jm
K
E X,T
E
(J 11t |Xr,, 9o(e))112 +2A nh(()
π1
k=
KL(Q'' [P))
A
- 3A
+2A/nh(0),
Vn
where
Q (( 0,0 () (fje T)(())))((()))))) X),
P P)= o 0x (Jje, htw.
We can show that
KL KL(Q)) < 2 (.))
(35)
see Appendix E.3.2 for the proof. We can analyze the behavior of the upper bound of Eq. (35) in Appendix E.4.
Thus, we have
2 log (6,
A
gen(n, D) s 3A
+ +2A +2A/nh(8)
n
E.3.2 Proof Eq. (34)
We consider the following posterior and data-dependent prior distributions
Q P()))(U))(eeee... o. (
P3 = p o. C. U.
43

---

When using the Donsker-Valadhan inequality, all calculation remains the same except for the KL divergence term as described below
Q
p(f]f, U)
Eq log wwwpeunwwesskkonoaadeeeeooohhhhe log Ps
E E U?)
U(
-ENNPPUUUAAA log
E ( ff U,
p(f(f,U)
-Bacsiaan log
P U!)
p(f|E, U)
- log
(PAR))PAXXPPPPPXXXXXXI log EAUIIE))(((
EMUN)((IE,
EpwrIIX U')
-(f;UU]f, X) + E ( log
Eu X)
<IffUU]E,X) + P log
p(U")
P(U" ((D(IX))(
=(fEUUfE,X) + B - log
Ex(UIx))((TUU' X)p(U")
= -[fi;U x)+ X(FUU)))
We derive the similar arguments for Q's and P and we have
KL (P')) < [(;; UI + [(f;Ulx)
Note that we consider the CMI for the discrete variable, it is upper bounded by the entropy [15], and we have
(i; X) < म[ X] H H[ < (6,
and
U(; S - - & [[[ < log.N N8, F,,F,2n)
The first inequality follows from the fact that MI is defined as the difference between the entropy and the conditional entropy, and the entropy of discrete variables is always non-negative. The second inequality arises because J. are outputs of a function evaluated at 2n points. Thus, considered the covering number at 2n points, defined as (6, F, n) == sup 2ng (8, F. Since the entropy is bounded above by the logarithm of the maximum cardinality, we obtain the second inequality.
E.3.3 Behavior of Eq. (2)
Finally, we show that Eq. (2) satisfies h(6) 834,6 8 because
q( = jle, fx))
qJ fx))
e -=
Σ k== e (1))
--A1)(())-a111
ΣR=1 e 811fo(z))<u)
n k
Σ (1)
-=11 x
Σ 1== (e)
-(00000---c)))))0(-1------------ (f())) ff(x)) x sup e
kE(R]
< ARA.0 132.8
44

---

E,4 Discussion about the metric entropy for regularized model
Here we discuss the upper bound of metric entropy in our setting. Since the latent variable lies in R the encoder network operates as fo R + R making it multivariate function.
Let define function class F; X' IR for 1.... dgan and define Fo II. F. Then by definition, F C Fu holds. We define the covering number for each Fü; Given x" == (Z1,... In X", define the pseudo-metric d', F; d', g) = maXig(a] [f(z) g(x;)l for f.g F, The δ-covering number of F; with respect to d', is denoted as (á, Fi, a²),, and we define (6, F) = = F6, x"). Then by definition, the cardinality of F is smaller than Fo, so we have
N.) S II ((.,
We can see a similar argument in Lemma in Guermeur [26], which considers more general settings. For simplicity, assume that F Fi follows
Fa, holds. Then, we rewrite Theorem 4 as
2d, log N(. Fr 2n) gen D) S 4 2 +3A
7
For example, assume that the encoder function, which has dø dimensional parameters. shows Lu- Lipschitz continuity (To > 0) with respect to parameter, then can obtain log.N((F) 1l,o, 6) x Lo do log 8 [75]. Thus, by setting å = ((1/(n)). we have that
(V
Valeda log(n)
gen(n, D) o
Instead of using the assumption of parametric function class, the metric entropy can be bounded by the fat-shattering dimension of each function, discussed in Lemma 3.5 of Alon et al. [5].
Examples of fat-shattering dimension evaluations can be found, for instance, in Bartlett & Maass [7]. which discusses neural network models, and Gottlieb al. [24], which addresses the fat-shattering dimension of Lipschitz function classes. If our encoder network adheres to these properties, we can bound its covering number accordingly.
As discussed in Appendix D.7.1, when we use the deterministic decoder, we can use the Natarajan dimension to quantify the complexity of the LVs and such Natarajan dimension be bounded by the fat-shattering dimension. Thus, it is essential to bound the fat-shattering dimension both deterministic and stochastie settings.
F
Proof of Theorem 5
Before the proof, we define the Wasserstein distance. Given a metric d(., .) and probability distribu- tions p and q on X, let 11(p. q) denote the set of all couplings p and q. The 2- 2-Wasserstein distance is defined as:
-v inf / d(z, ((dp(x)))((
W2(p. q)
Ven xxx
In this work, the Euclidean metric as d(...).
Next, we define the pushforward. Let и represent a distribution on Z, and us assume that for any 0 E O, the decoder go(-) 2 - X' is measurable. The pushforward of the distribution by the decoder, denoted as go #n, defines distribution on X' as # = x (gp (A4) for any measurable set A C X.
Proof. Conditioned on the encoder parameter, codebook, and input X, selecting the index J corre- sponds to selecting the latent representation é,. Since the posterior over the index is q(]le, Φ. X), we express the posterior imposed on the latent representation as g(e eyle, o, X) for all j I,..., K.
45

---

Using this notation, we first define the distribution obtained by the training dataset as follows; conditioned on e, Φ S, have
1 n
As
Σ n
From the triangle inequality, we have
W2 W2(D, () S W2 (s) + W2 (2( (t)
(36)
We then have
(D p)) - 2W (D,As) As) + 2W2 (ps.
The first term of Eq. (36) is bounded as follows;
1
(e (D, jis) S I8 1R (ie, Ex
Sm 5l
m==1
|| go (e())))
Σ
) x=-
The first inequality is obtained by the definition of the Wasserstein distance.
This term corresponds to the first term of Eq. (17), where X corresponds to the test data 0m.
Therefore, Eq. (37) can upper-bounded by applying Eq. (21), which serves as the upper bound for Eq. (17).
(s WD
(38)
1
1 E E Bes.s.le go(es,,)) )122+ (L(Q)))
AA
2
A
EsL gE
+
2n
where
Q = g(e, o B|S)
II (0mmle, Φ. Sm), m==
P P= (l, o, 0[S)
II m==
क (Jmle,
Next, the second term of Eq. (36) is bounded follows; [11].From the particular case 2.5. in Bolley & Villami [11], we directly have
the weighted CKP inequality
Es W3
(is; (Bs s 2K S A
2 n
KTlgota(ele, (el
(39)
A
2 SUl
m=1
Combining Eqs. (38) and (39), we have
W| (D,
< 2Es (e.0.)))
Σ
Eyle
Sm)) (. g0(e(m)))1
m=1
2 KL(Q|P)
AA
2A
1 n
+
24
2
(m)
n
Vn
72
Then by optimizing X, we have Es (D,
2 Σ
24
Feleemllesssss.ll.... go 30(e(m)))) + 44
2
Σ
Kb dh Sm))l x))
Vn
m=1
m=1
46

---

G Experimental settings and additional experimental results
Our experiments were based on the Gaussian stochastically quantized VAE (SQ-AEE) model proposed by Takida et al. [64], and were conducted by adapting the code from their GitHub 'to suit our experimental configurations. Therefore, we first introduce the basics of (Gaussian) SQ-VAE in Sections G.1 and G.2 and finally explain experimental settings in Section G.3.
G.1 Overview of SQ-VAE
The SQ-VAE is generative model that, similar to VQ- VA-, employs a learnable codebook e {e+}==1 zk The objective of SQ-VAE is to learn the stochastic decoder x ~ pe (2) Zg) using latent variables Zy to generate samples belonging to the data distribution (aaa(()), where pe (ge (Zg) og) II oI) is the Gaussian distribution with mean and equal variance parameter (m, I² o² E R4, and I is the identity matrix. Here, Zg is sampled from a prior distribution P(2g) over the discrete latent space ex
In the main training process of SQ-VAE, we assume P(Zz) to be an i.d. uniform distribution, identical to VQ- VAE, meaning each codebook element is selected with equal prohability (P(zg) = bR) 1/K for k [K]. Subsequently, second training stage is conducted to learn P(Zz)) Since computing the posterior po (Zg (z)) exactly intractable, we utilize an approximate posterior distribution qo (2, (r) instead.
At the encoding process, directly mapping from the discrete Zg is challenging due to the discrete nature of Z.. To overcome this issue, Takida et al. [64] proposed to construct stochastic encoder by introducing the following two processes:
Stochastic Dequantization Process:
The transformation function from Zg the auxiliary continuous variable, Z, denoted as pv (Z) Zy), where & is its parameters.
Stochastic Quantization Process: The transformation from Z to Z, is given by P(Z,) obtained via Bayes' theorem, which is represented as the
Po (Z) & categorical distribution q( @, x) through the softmax function as Eq. (2).
We can obtain 2g from a deterministic encoder fø(z), where we expect that Z, is close to Zg- Therefore, similarly define the dequantization process of Zg Z 2 (Z) Zg) By combining this process with the stochastic quantization process, we can establish the following stochastic encoding process from x to Z::: (z))) (Zzl where w = (ń) w) and q (Z(z)= = Py (Z) (Z).)
According to these facts, we can derive the following evidence lower bound (ELBO) for SQ- VAE:
L=s e)
(40)
log (0 2g (Z) qu (2(z)
= E (Z10)))2
+ +E (Z)m) H(P + (Const.),
=KL(Q|IP)
where H(Pp(Zg Z)) is the entropy of Po (ZylZ).
From the above, the optimization problem of SQ- (Q-V is minimizing Epp... [Csq(z; 0, w, e)] w.r.t. ( e). This approach eliminates the need for heuristic techniques traditionally required, such as stop-gradient, exponential moving average (EMA), and codebook reset [82].
Morcover, the categorical posterior distribution Pa (Z, Z = q(J o 2) can be approximated using the Gumbel-Softmax relaxation [35, 45], where the Gumbel-Softmax function is defined as, for all k (1 < k < K),
exp( exp(-81lfa(x) - 11 Gz)/T)
Σバ Σ exp(- e, + G2)/T)*
Inttps: :tttt:::///thbbbb. htte:s///g...aaa..c//o/////rrree https//www....eeeo////////////ea
47

---

Table 1: Experimental settings on MNIST.
Experimental MSIST Experiments
Model
Gausszan nocharacaly quanaed VAI (SQ-VAI) [69]
Network irchicctre
ComreesNes with sieee comelntional layer, two imneooe convelriional layers and one Resilickss
BonkTook and dimmenn laant quea d,
Uplinse
Adant with Inmial loaming rale
Batch aze
Num Iriningaaaddiiinn samples
200 2000, 2006
Num
specis
201
Num. of samples ln CM crimatos
Num. of samplings 1o
Table 2: Experimental settings on CIFARIO.
Experimental sctop
experimentts
Model
Gamesion ancharncally quarined VAI (SQ VAI) [64]
Netwerk archiecctre
Rechet with theee comelational lyyes, two imnquoo conveltional byvrs and one Reellincks
The vine of i mokebokk (K) and the dimenoon of the brent spear d.
K- [16. 32 61. 128 of
Aiben witk mital Kemigraa rat
Batch aze
X
Nom. of tnaninghalidation samlles
[1000, 5000, 10000) 2000]
Nom of speche
200
Kim of simplex for CMicematio
Num. of samplings For
where G₁ is an i.i.d sample from the Gumbel distribution and 7 is the temperature parameter that is deferent from in Eq. (2). This allows the application of the reparameterization trick from VAEs during backpropagation, enabling efficient gradient computation and model training.
G.2 Gaussian SQ-VAE
Gaussian SQ-VAE assumes that the dequantization process pa pa (Z) follows a Gaussian distribution.
In this paper, we set the following Gaussian distribution: Py Zz. ( Ii,),, where of R.. Then, the stochastic decoder and the stochastic dequantization process in SQ-VAE can be written as (a Zy) (goo (gg)) o²) and p& (Z,12g) (2 o
G.3 Details of experimental settings
Dataset: We used the MNIST dataset [41], which 28 28 gray scale images with 10 classes. We prepared the subset dataset with {1000, 2000, 4000, 8000] samples from the default training dataset (60000 samples). Then, we split as the training and the validation datasets following the supersample setting as in Section 2.3.
Model architecture and training procedure:
We adopted the ConvResNets with the architecture provided by Google DeepMind 2. We summarize the details of this model in Table 1.
Regarding the training procedure, we adopted the settings in Takida al. [64] as follows. We used the Adam optimizer with 0.001 initial learning rate. The learning rate was halved every 3 epochs if the validation loss is not improving. We trained the model 200 epochs with mini-batch size. As for the annealing schedule for the temperature parameter of the Gumbel-softmax sampling, we set as Jang al. [35], where is the global training step size.
exp(10
GPU environment: We used NVIDIA GPUs with 32GB memory (NVIDIA DGX-1 1 with Tesla V100 and DGX-2) our experiments.
Mutual information estimation: To estimate the mutual information [(]; U/e, o, X) in Eq. (7), developed plug-in estimator for it, which is computed using estimators for the prob- ability density of J and X, well as their joint probability density, employing k-nearest- neighbor- density estimation [43]. The estimation strategy is incorporated into the sklear feature serrre_eleee eeeettiin ion mutuallinfee cl assif function We set k = 3 fol- lowing the default setting of this function and Kraskov et al. [40], Ross [54].
ipynb selection.mutull info_classit.httm
www.a///awcrrrrreaeeooaaom feauue feature_
48

---

0.5
G 1000
0.5
5-0000
0.5
2= 10000
0.5
n- 20000
0.4
0.4
0.4
0.4
0.3
0.3
0.3
0.3
0.2
0.2
0.2
0.2
0.0
500
500
500
500
400
400
830
350
350
350
800
300
300
300
220
200
200
Mumber of hicitual Blcks ideooder.
Mumbbrr Resicual Blocks ldccederr
Mumber offee blocks tseccdor.dd
Namber offies dual Bloks idecedor dy
Figure 5: Behavior of the generalization gap and the empirical KL. term (KI. ( CIFAR-10 dataset (K 128, d_ = 64). The top row shows their asymptotic behavior as a function of sample size The bottom row shows their behavior as the decoder complexity (number of residual blocks) is increased (for 7 20000).
P)/n) n) on the
G.4 Additional Experimental Results
Here, we summarize our additional experimental results. These experiments are organized to empirically support the three central claims of our paper, which we present in sequence: (1) the decooder-independent nature of the generalization gap, (2) detailed analysis of the two KL terms in Theorem 2, and (3) the practical utility our theoretical framework.
G.4.1 Validation of Decoder-Independenee (Theorems 3, &
central claim of our paper is that the generalization gap independent of the decoder go. We validate this claim across various settings.
First, Figure shows the results the CIFAR- 10 dataset, which is more complex than MNIST. These results support our implication: increasing the complexity of go by adding a ResBlock (introducing approximately 74,000 parameters) has negligible effect the generalization gap.
Second, to provide a complete picture for Figure in the main text, we provide its corresponding training losses in Table 3. The table confirms that for larger datasets (n 1000), more expressive decoder (i.e., with more residual blocks) tends to achieve a lower training loss. This observation, when viewed alongside the stable generalization gap in Figure 2, strongly reinforces our central claim: the decoder's capacity to fit the training data is not the primary driver of generalization performance.
Third, we compare the behavior of stochastic (SQ- VAE, Theorem 4) and deterministic (VQ-VAL Theorems 2 & 3) encoders. The results in Figure 6 show two key findings:
SQ-VAE (Stochastic); As shown in the two left panels, the generalization gap is independent of the decoder complexity (lefimostt and instcad depends on the latent dimension dg (sccond from left). This perfectly consistent with Theorem 4, which is independent of the learning algorithm g(w S) and fully eliminates the decoder's 's influence.
VQ- (Deterministic): As shown in the two right panels, the gap also largely independent of the decoder (second from right) and dependent on d, (rightmost), supporting Theorems 2 & 3. However, we observe a slight tendency for the gap to increase in the moderate complexity range (e.g., 6 ResBlocks). This does not contradict our theory. Our bounds (which depend on g(w(S)) state that the upper bound is decodder-independent implying that while increasing complexity substantially does not worsen the gap, poorly learned g( S) in the moderate range can still affect generalization under that bound.
Overall, these findings suggest that the influence decoder complexity depends on whether the latent variable mechanism is stochastic or deterministic, which is important direction for future work.
49

---

Table Training loss corresponding to the generalization gap experiments in Figure (top row). As decoder complexity (number of Residual Blocks, RB) increases, the training loss tends to decrease for larger sample sizes (n 2 1000), confirming that a more expressive decoder can better fit the training data.
71
RB=2
RB=3
RB=4
RB=5
250
6,4851 + 0.2642
7.0816 = 0.2817
7.6026 + 0.2786
7.4940 = 0.7172
1000
3.4664 + 0.0293
3.4869 0.1286
3.3180
0.0398
3.2609 + 0.0905
2000
2.6391 + 0.0177
2.5114 + 0.0130
2.4645 + 0.0778
2.3915 + 0.1214
4000
2.1102 + 0.0478
1.9466 + 0.0152
1.9223 0.0115
1.9001 + 0.0475
SQ VAE: Gap vs Decoddr Blocks
SQ:VAE: Gap Latent Dim (dz)
VQ VAE Gap vs Decoder Blocks
VQ VAE: Gap vs Latent Dim (d2)
1.22
to 3001
Cisic in scass
1.00
Gen Cop
0,015
5.000
1.00
5.009
Dea87 11800
Decoder ResBlocks
Latent Dimension (de)
Decoder ResBlocks
Latent Dimension
Figure 6: Behavior of the generalization gap when increasing the number of residual blocks of the decoder network and the latent dimension d2 SQ-VAE (stochastic, left two panels) and VQ-VAE (deterministic, right two panels) models.
G.4.2 Analysis of the KL Divergence Terms (Theorem 2)
Theorem presents a bound comprising two KI. terms. We now empirically analyze the behavior of both terms.
Figure 7 shows the behavior of these terms on the MNIST dataset. As shown in the top row (left and middle panels), the first KL term (KL(Qu, u P)/n) does not decrease monotonically with n, consistent with our theoretical claim in Lemma 3. In contrast, the generalization gap (top left) and the second KL. term (CMI term, top right) both decrease steadily as increases. This suggests that the second KL term, not the first, correctly captures the generalization behavior. The bottom row also shows that both KL terms increase with the codebook size K, confirming our theoretical predictions.
To make this relationship explicit, we plot the correlation between the generalization gap and each KI. term in Figure 3. The results MNIST are clear: the second KI. term (right panel) exhibits a consistent positive correlation (r Rs 0.46-0.60) with the generalization gap across all decoder complexities. Conversely, the first KL term (left panel) shows a negative correlation, as its value does not decrease with n while the generalization gap does.
We further validate this finding the more complex CIFAR- 10 dataset in Figure 8. The trends observed in MNIST are not only confirmed but are even more pronounced. The asymptotic behavior (left three panels) again shows that both the generalization gap and the second KL term decrease with n, while the first KL term does not. Most importantly, the correlation plots (right two panels) provide definitive evidence. The second KI. term exhibits extremely strong and consistent positive correlation (r > 0.92) with the generalization gap. In stark contrast, the first KI. term shows a strong negative correlation (r -058).
This provides robust empirical evidence that the second term in Eq. (7) (the CMI term) is the component that correctly characterizes generalization behavior.
G.4.3 Practical Utility of the Data-Dependent Prior
In addition to validating our theoretical bounds, we also investigated the practical utility of our framework by implementing data-dependent prior following the approach of Sefidgaran et al. [57].
Variational Information Bouleneck (CDVIB), which is directly motivated by their theoretical results that bound the generalization error of
Sefidgaran et al. [57] proposed the Lossless
50

---

Generalization Gap vs
KL/n (first KL term in (q.(7) vs
KL/n V5 (second KL term in Eq.())
400
0.2
300
0.15
0.10
322
300
0.00
Generalization Gap
KL/n (first KL in Eq.(7))
KL/n (second KL in Eq.(7))
0.000
Generalication Gap
KL/n
CMinn
0.005
30000
8.000
0.035
280
3 30000
8.10
0.605
3.010
0.000
220
Figure Behavior of the generalization gap and the two KI. terms from Eq. (7) on the MNIST dataset (K 128, d2 64). (Top row) Asymptotic behavior function of sample size n. (Bottom row) Behavior as a function of codebook size (for n 2000).
Cercittion
25
20-44
8.00
R8-
Ragimedio
RD-5: r-0.15
0.2
3015
0.1
3003
2000
10000
20002
1200 5050
30006
20303
1000 5000
20002
20000
303 350 400 400
033
0.33 0.23 0.33
Figure 8: The behavior of the generalization gap and the two KL terms from Eq. (7) the CIFAR dataset (K = 128, dg = 64).The three leftmost panels show the asymptotic behavior of the gener- alization gap, the first KI. term, and the second KI term function of sample size n. The two rightmost panels show scatter plots correlating the generalization gap with the first KI. term (fourth panel) and the second KL term (fifth panel). In these plots, the color indicates the number of decoder Residual Blocks (RB=2, 3, 4, or 5) and the marker shape indicates the sample size n. (Circle for 1000, Square for 5000, Diamond for 10000, and Triangle for 20000).
encoder-decoder representation learning models. Their analysis demonstrates that the generalization error depends solely on the encoder and latent variables, rather than on the decoder. Consequently, unlike the standard VIB that employs a data-independent prior N(., /)), their bound suggests that data- -ataadeepndenn priors-which which capture the structure and "simplicity" of the encoder- can tighten thcoretical guarantees and improve generalization.
Building upon this insight, the Lossless CDVIB framework introduces a data-dependent Gaussian prior. To implement such prior, the mean and variance of each prior component are updated at every training iteration using an exponential moving average the corresponding batch statisties. This moving average enables the prior to gradually align with the encoder's 's latent representation, ensuring that KI. regularization term consistently tracks the geometry of the encoder. This adaptive alignment mitigates the mismatch between the encoder's 's latent distribution and the fixed isotropic prior used in standard VIB, Furthermore, since the "ghost" dataset assumed the theoretical analysis unavailable during training, the moving average empirically mimics this expectation by aggregating
51

---

Table Reconstruction error comparison between the baseline SQ-VAE (without data-dependent prior) and our proposed method (with a data-dependent prior) on test dataset. Our method demon- strates consistently lower test loss across all benchmark datasets, validating the practical benefits of our theoretical framework.
Dataset
SQVAE (baseline)
Proposed method
CIFARIO
10.75 + 0.10
10.68 = 0.04
Fashion-MNNN -NNIST
1.37 + 0.02
1.32 0.05
MNIST
3.23 + 0.04
2.99 = 0.04
statisties across past mini-batches. this sense, the moving prior reproduces the averaging effect of the ghost dataset, providing practical realization of the theoretical setup.
Motivated by these concepts, we introduce a similar data-dependent prior into the ELBO objective in Eq. (40). Specifically, we replace the entropy regularization term in Eq. (40) as follows:
1 N
E
En,, m=1
H(P + KLCDVII, (41)
where KLCDVIB is defined as follows. Recall that the entropy term is expressed as
B [((P((Z]12)]
yn. log Qn,kr
k=1
where In.6 denotes the simplified form of (2g))) for the data point En. We then define the proposed regularizer as
KT.CDVIB
ΣΣ
In.
log 4n.k T
==1k=
where the denominator 7y represents the moving average of the empirical statistics:
N
Pk
kn
N n=1
and the data-dependent prior ı is updated as
π a) x ap
a (0, 1).
Σj=1 IT
In practice, the empirical statistics are computed over each mini-batch. We employ mixture of data-independent and data-dependent priors the regularization term Eq. (41). Empirically, we observe that this mixture stabilizes training, while setting 3 too close to often leads to suboptimal performance.
We evaluated the test reconstruction loss in terms of MSE following the experimental protocol of Takida et al. [64]. For all experiments, we fixed 0.9 and 3 0.5. The numerical results are reported in Table 4. Here, the MSE represents the total pixel-wise reconstruction loss per image, rather than the per-pixel average. To ensure statistical robustness, we repeated each experiment with ten different random seeds, and report the mean and variance of the MSE across these 10 independent trials. We observed that incorporating the data-dependent prior consistently improves MSE performance across all settings.
52


Reviews:
[{"review_id": "CoL2bH5Uyb", "reviewer": "Reviewer_qLsN", "summary": "The paper presents an information-theoretic analysis of VQ-VAEs in a supersampling setting, aiming to understand how latent codes influence both generalization and generation. The authors: (1) derive new generalization bounds that evaluate reconstruction loss without invoking the decoder; (2) introduce a permutation-symmetric supersample setting, which lets them control the generalization gap by regularizing the encoder’s capacity; (3) provide an upper bound on the 2-Wasserstein distance between the true and generated data distributions, offering insight into the model’s generative quality.", "questions": "Please see strengths and weaknesses.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nhe paper addresses a critical question in the theory of unsupervised learning, specifically regarding VQ-VAE, and its finding that the generalization bound is independent of the decoder is particularly interesting.\n\n**Weakness**\n\nMy main concern is the lack of direct practical implications. While the insights into the generalization of VQ-VAE are interesting, the theoretical results do not offer clear guidance for the design and training of VQ-VAEs. \n\nThere are a few points I would like more discussion and clarification on, as listed below:\n\n- Table 4: *\"The results are consistent with Theorem 4, which suggests that when using a stochastic mechanism for latent variables (LVs), the upper bound of the generalization gap is independent of decoder complexity, but depends on $d_z$.\"* This result is both interesting and valuable. However, it’s also possible to increase the complexity or expressiveness of LVs by increasing the codebook size rather than $d_z$. Could the authors provide any discussion or insight on when it is preferable to increase $d_z$ versus the codebook size?\n\n- Figure 2: I believe the reconstruction error should be included in the analysis to observe whether increasing decoder size leads to better training error. This would ensure that the model is well-trained.\n\n- Figure 2: What are the implications of the behavior of the first LK term?\n\n- The finding regarding the 2-Wasserstein distance between the true and generated data distributions is not entirely novel. Reference [1] shows that the Wasserstein distance between the training and generated data distributions is equivalent to the reconstruction error and an arbitrary distance (e.g., KL divergence, Wasserstein) between the encoder output and the prior. Reference [2] discusses the consistency of the Wasserstein distance. I believe that combining the results from [1] and [2] aligns with the findings presented in Section 5, albeit in a more general framework. Reference [3] also addresses generalization between the true and generated data distributions. Could the authors provide further discussion on how these results compare?\n\n- Additionally, the authors mention that \"designing a prior that reduces this bound could lead to improved data generation accuracy.\" Since discrete latents learning and generalization are typically performed in two stages—first learning the latent variables, followed by learning the prior using autoregressive models like transformers, which effectively fit the encoder output—I'm unclear on the practical benefits and implications of the results presented in this section for data generation performance. Could the authors elaborate on this further?\n\n\n**Discussion:** While the generalization gap is independent of decoder, it should still be considered in the analysis, as it affects the overall performance of the VQ-VAE (e.g., training loss). Once the decoder is considered, my understanding is that there is a relationship between decoder size and latent size ($d_z$). As shown in Figure 6, latent size ($d_z$) is now correlated with the generalization gap. Therefore, generalization performance (not just the gap) is not independent of the decoder. Focusing solely on the generalization gap may lead to incorrect conclusions.\n\nOverall, I do believe the authors have done valuable work, and this research will benefit the community working with VQ-VAE models.\n\n[1] Vo, Vy, et al. \"Parameter estimation in DAGs from incomplete data via optimal transport ICML 2024 \n\n[2] D. Pollard, \"Quantization and the method of k-means,\" in IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 199-205, March 1982, doi: 10.1109/TIT.1982.1056481.\n\n[3] Vuong, Tung-Long. \"Task-Driven Discrete Representation Learning.\" AISTAT 2025.", "was_revised": true, "final_justification": "I have carefully reviewed the initial rebuttal discussion, additional experiments, and the follow-up rebuttal, all of which address my concerns, specifically:\n- The author has clarified the practical implications of the analysis results.\n- Additional experiments were conducted on the reconstruction error in Figure 2.\n- The rebuttal to my follow-up question regarding the impact of codebook size on generalization has addressed my remaining concerns from the initial rebuttal.\n\nI also reviewed the author's rebuttal to the other reviewer. Overall, I believe the authors have made valuable contributions, and this research will benefit the community working with VQ-VAE models. Based on this, I am raising the overall score to 5 and adjusting the quality and significance scores accordingly.", "rebuttal": "# Reviewer qLsN\nWe sincerely thank you for your insightful feedback.\n\n### Q1: On the lack of direct practical implications\n\nA. \nWhile our work does not propose a new algorithm, its primary goal is to provide a rigorous theoretical foundation with direct consequences for practitioners. Our analysis yields several key insights that explain and justify existing practices in VQ-VAE training:\n\n- **Importance of Encoder Design:** Our central results (Theorems 2, 3, 4) show the generalization gap is independent of decoder complexity and is instead governed by the encoder and latent variables (LVs). This provides a clear guideline: to improve generalization, focus on the encoder's architecture and regularization since the decoder's capacity has little impact on generalization.  This is empirically supported by our experiments (Figures 2, 4, 6).\n\n- **Justification for KL Regularization:** Our Theorems 2 and 5 provide a theoretical justification for using KL divergence as a regularization term. **While KL regularization appears naturally in variational Bayes, it was previously unclear if it truly functions as a regularizer for generalization and data generation**. Our research is the first to provide a formal justification for this widely used practice.\n\n- **Insight into Prior Design:** Lemma 2 suggests the optimal prior is an empirical marginal distribution from the training data, analogous to mixture priors like VampPrior, offering theoretical insight into prior choice.\n\nTo make these practical implications more explicit for the reader, we will add a summary of these points to our conclusion (Section 6).\n\n\n**Regarding the potential benefits of prior design:** We would like to clarify that our analysis shows how a data-dependent prior can improve generalization performance. In this respect, our theoretical findings are in line with the results of Sefidgaran et al. (2023), who demonstrated that incorporating a data-dependent prior as a regularization term during training improves supervised learning performance under a decoder-independent bound. Motivated by their findings, we conducted additional experiments to evaluate the practical utility of data-dependent priors within our framework. While standard SQ-VAE employs a uniform prior, we implemented a learned prior using a moving average over latent variables during training, effectively approximating a data-dependent prior as suggested by Sefidgaran et al. (2023). \n\nThe experimental results, shown below, indicate that the data-dependent prior consistently improved test loss compared to the baseline SQ-VAE across four benchmark datasets. These results provide evidence that such priors are not only theoretically justified but also practically beneficial for training the models of unsupervised learning. \n\n**Table 1: Test loss**\n\n| Dataset (train size) | SQVAE (without data-dependent prior) | Proposed method (with data-dependent prior) |\n|:---------------------|-------------------------------------:|--------------------------------------------:|\n| CIFAR10 (n=50000)    | 0.8523 ± 0.0364                      | 0.8403 ± 0.0247                             |\n| EMNIST (n=112800)    | 0.6564 ± 0.3811                      | 0.4327 ± 0.3032                             |\n| FashionMNIST (n=60000) | 0.4721 ± 0.2964                    | 0.3893 ± 0.2249                             |\n| MNIST (n=60000)      | 0.3887 ± 0.2215                      | 0.3290 ± 0.1669                             |\n\n### Q2: On choosing to increase latent dimension $d_z$ vs. codebook size $K$\n\nA. From a theoretical viewpoint, increasing the latent dimensionality $d_z$ enlarges the generalization bound, whereas the bound does not depend on the codebook size $K$. This follows from Theorem 4 (see Line 332): under suitable assumptions, the uniform convergence bound is independent of $K$ while depending explicitly on $d_z$. Consistently, our Appendix experiments indicate that enlarging $K$ has little effect on the generalization error.\n\nImportantly, these observations concern generalization (the generalization gap), not the overall performance, which is related to minimizing the training loss on the training set. As we also noted in our response to Q7, the fact that the bound does not depend on $K$ does not imply that $K$ is irrelevant to how small the training error can become. In practice, $K$ can influence representational capacity and optimization dynamics. A careful analysis of how $K$ affects actual performance (beyond the generalization bound) is therefore outside the present theory and is an important direction for further work. We will clarify this distinction in the paper.\n\n\n### Q3: On including reconstruction error in Figure 2\n\nA. \nBased on your suggestion, we have run this analysis and, following your suggestion, we will add a new plot for the training loss to Figure 2 in the final version of the paper. \nSince the NeurIPS rebuttal policy prohibits including updated figures via external links, we present the results in the table below for your convenience.\n\n\n#### Train Loss vs Number of Residual Blocks (MNIST)\n\n| n | RB=2 | RB=3 | RB=4 | RB=5 |\n|---|---|---|---|---|\n| 250 | 6.4851 ± 0.2642 | 7.0816 ± 0.2817 | 7.6026 ± 0.2786 | 7.4940 ± 0.7172 | \n| 1000 | 3.4664 ± 0.0293 | 3.4869 ± 0.1286 | 3.3180 ± 0.0398 | 3.2609 ± 0.0905 | \n| 2000 | 2.6391 ± 0.0177 | 2.5114 ± 0.0130 | 2.4645 ± 0.0778 | 2.3915 ± 0.1214 | \n| 4000 | 2.1102 ± 0.0478 | 1.9466 ± 0.0152 | 1.9223 ± 0.0115 | 1.9001 ± 0.0475 | \n\nAs shown in the table, for larger sample sizes ($n\\geq1000$), the training loss consistently decreases as the decoder complexity (number of Residual Blocks; RB) increases. This confirms that a more expressive decoder better fits the training data. For the small sample size setting ($n=250$), this trend is not observed, and the loss is noisy. We attribute this to the high variance inherent in training on very limited data, where a more complex model can be harder to optimize stably.\n\nCritically, even as the training loss decreases with decoder complexity (for $n\\geq1000$), the generalization gap shown in Figure 2 of our main paper remains largely unaffected. This finding more strongly supports our central claim: a more powerful decoder can reduce training error, but it does not contribute to reducing the generalization gap. \n\n### Q4: On the implications of the first KL term's behavior in Figure 2.\n\nA.\nThis KL term, $\\mathrm{KL}(Q_{J,U}\\|P)/n$, is related to the mutual information between the training data and the latent representation (see lines 231-232, and 240) and reflects how much information the encoder memorizes from the data.\n\nThe fact that this term does not converge to zero as $n$ increases is evidence that the model is learning meaningfully. If this value were to converge to zero, it would imply that the encoder has not captured any information from the training data.\n\nThis non-converging behavior of the empirical KL term is a known issue in IT-based analysis. \nIn fact, this challenge motivated us to introduce the novel permutation-symmetric setting in Section 4, which leads to our Theorem 3, a bound asymptotically converging to zero without this term (see lines 261-268). Therefore, the behavior of this KL term highlights a limitation of the standard supersample setting (and Theorem 2) and underscores the novelty and importance of our more advanced result in Theorem 3.\n\n### Q5: On the novelty of the 2-Wasserstein distance bound compared to prior work\n\nA.\nOur result is novel in providing guarantees from an information-theoretic perspective for the VQ-VAE framework where the encoder and decoder are trained jointly.\n\n- **Comparison with [1, 2]:** [1] is in the context of causal inference and [2] addresses the classical $k$-means setting, whereas our work targets modern, non-linear generative models. Our bound also uniquely connects the data generation performance to the KL regularization term. \n\n- **Comparison with [3]:** [3] focuses on task-driven settings, whereas our analysis is purely unsupervised. We will add this discussion to the paper to clarify our contribution's uniqueness.\n\nTo clarify the uniqueness of our contribution, we will cite these references and add a discussion comparing them with our work in Section 5 or Appendix B.2.\n\n### Q6: Practical implications of two-stage prior design\n\nA.\nTheorem 5 provides the following implication for two-stage prior strategies. In this process, at the first stage, the encoder produces the latent distribution $q(J∣S)$, and at the second stage, an autoregressive model (e.g., a Transformer) is assumed to learn the prior distribution $\\pi(J)$. Our theory explains that, if the objective of the second stage is trained so as to minimise the KL divergence $\\mathrm{KL}(q(J∣S)∥\\pi(J))$, then the upper bound of Theorem 5 is reduced, thereby improving data-generation performance. Meanwhile, the theory also suggests that the prior distribution $\\pi(J)$ should be data-independent, and thus methods that avoid the strong data dependence observed in the Vamp-prior are preferable.\n\n\n### Q7: On the validity of focusing only on the generalization gap, not overall performance\n\nA.\nOur claim is not that overall performance is independent of the decoder, but specifically that the generalization gap component is. We explicitly state that an expressive decoder is required for low training error (lines 182-185), which is essential for final performance. The core contribution is proving that the gap component can be bounded independently of the decoder. We will re-emphasize this distinction in the conclusion to avoid misunderstanding."}, {"review_id": "V7ULQvgRGo", "reviewer": "Reviewer_nKXf", "summary": "This paper develops an information-theoretic framework to analyze the generalization behavior of vector-quantized variational autoencoders (VQ-VAEs), focusing on the role of discrete latent variables (LVs). By extending the supersample-based generalization bounds from supervised learning to the unsupervised setting, the authors derive decoder-independent upper bounds on the reconstruction loss. They propose a novel permutation symmetric prior, allowing them to establish asymptotically vanishing generalization bounds under certain regularity conditions. Additionally, the authors provide an upper bound on the 2-Wasserstein distance between the true and generated data distributions, offering theoretical insight into data generation quality.", "questions": "I want to be upfront that I am not an expert in the topic of this paper.\n\n- Have you considered experiments that modify encoder or latent complexity and measure their correlation with your theoretical quantities? That could help demonstrate utility beyond the current generalization gap plots.\n\n- You mention this as future work, are there concrete barriers (e.g., measure-theoretic issues or lack of symmetry) that prevent your approach from being directly applicable to standard VAEs?\n\n- Given the decoder’s role is marginalized in generalization bounds, could the authors provide guidelines for determining when a decoder is “sufficiently expressive” to avoid affecting generalization?", "limitations": "Yes, the authors are upfront with the limitations. I appreciate it very much.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The paper provides a rigorous, information-theoretic treatment of generalization for VQ-VAEs.\n\n- The results show that generalization and data generation quality depend primarily on the encoder and latent structure, not the decoder. This insight is useful for guiding model design.\n\n- The introduction of a permutation symmetric setting provides a technically novel way to construct a data-dependent prior that leads to bounds with asymptotic convergence.\n\nWeaknesses:\n\n- Despite asymptotic guarantees, the derived bounds are too loose to be practical, often several orders of magnitude larger than observed generalization gaps.\n\n- While the bounds are decoder-independent and theoretically elegant, they do not translate into actionable training strategies or practical diagnostics for improving models.\n\n- The paper's notation and technical detail can be hard to follow. Key intuitions behind the bounds and assumptions could be better emphasized, especially for a broader NeurIPS audience.", "was_revised": true, "final_justification": "The paper provides interesting theoretical insights of the generalization of VQ-VAE. It can be improved with more accessible writing and  more empirical guidelines.", "rebuttal": "# Reviewer nKXf\nWe sincerely thank you for your insightful feedback.\n\n## On Weaknesses\n### 1\\. Regarding Looseness of the Bounds \nWe agree that the derived bounds are not numerically tight. However, our work is intended as a first step toward tight bounds for unsupervised learning models such as VAEs. As discussed in the Introduction, information‑theoretic bounds in supervised learning can become non‑vacuous by leveraging algorithmic information. In contrast, for unsupervised learning —particularly VAEs— our contribution is, to the best of our knowledge, the first to incorporate algorithmic structure (latent variables) into generalization bounds.\n\nOur primary goal was not to provide a tight estimator of the generalization gap, but to use the bounds to reveal structural dependencies of generalization in VQ‑VAEs. \nEven if numerically loose (and potentially vacuous in some regimes), the bounds provide practically relevant insights. In particular, the key structural conclusion—that the generalization gap is independent of the decoder—follows from our analysis regardless of the bound’s absolute value. Additional practical implications and supporting experiments are provided in the following. We will add brief clarifications in the revised manuscript.\n\nFinally, we respectfully mention that, among our results, **only Theorem 4 is asymptotic**; the others are **non‑asymptotic** and explicitly leverage algorithmic information. \n\n### 2\\. Regarding Actionable Strategies\nWe respectfully argue that our theory does provide actionable guidance, not by proposing a new algorithm, but by establishing a clear theoretical framework that justifies, explains, and guides high-level design decisions. Our analysis yields several key insights:\n\n- **Importance of Encoder Design:** Our central results, Theorems 2, 3, and 4, show that the generalization gap is independent of the decoder's complexity and is instead governed by the complexity of the encoder and the latent variables (LVs). This provides a clear design guideline: to improve generalization, one should focus on the complexity of the encoder's architecture and its regularization since the decoder's capacity has little impact on generalization. This finding is also empirically supported by our experiments in Figures 2, 4, and 6.\n\n- **Justification for KL Regularization:** The use of KL divergence as a regularization term on LVs is a common practice in variational Bayes for unsupervised learning, including VAEs. However, it was previously unclear whether it is a valid regularizer for generalization in LVs. Our Theorems 2 and 5 provide a first theoretical justification for this widely used practice.\n\n- **Insight into Prior Design:** Lemma 2 suggests that the optimal prior to minimize the empirical KL divergence is an empirical marginal distribution estimated from the training data, which is analogous to mixture priors like VampPrior. This provides direct theoretical insight into the choice of priors and justifies data-driven approaches.\n \n\n### 3\\. Additional experiments in the respect of Prior Design.\n\nOur theoretical findings are in line with the results of Sefidgaran et al. (2023), who demonstrated that incorporating a data-dependent prior as a regularization term during training improves supervised learning performance under a decoder-independent bound. Motivated by their findings, we conducted additional experiments to evaluate the practical utility of data-dependent priors. Specifically, while standard SQ-VAE employs a uniform prior, we implemented a learned prior using a moving average over latent variables during training, effectively approximating a data-dependent prior as suggested by Sefidgaran et al. (2023). \n\nThe experimental results show that, across four benchmark datasets, the data-dependent prior consistently improved test loss compared to the baseline SQ-VAE. These results indicate that such priors are not only theoretically justified but also practically beneficial for training the models of the unsupervised learning. As our primary focus is to provide a learning-theoretic understanding of VQ-VAE, the development of new state-of-the-art algorithms is beyond the current scope and is left for future work.\n\n**Table 1: Test loss**\n\n| Dataset (train size) | SQVAE (without data-dependent prior) | Proposed method (with data-dependent prior) |\n|:---------------------|-------------------------------------:|--------------------------------------------:|\n| CIFAR10 (n=50000)    | 0.8523 ± 0.0364                      | 0.8403 ± 0.0247                             |\n| EMNIST (n=112800)    | 0.6564 ± 0.3811                      | 0.4327 ± 0.3032                             |\n| FashionMNIST (n=60000) | 0.4721 ± 0.2964                    | 0.3893 ± 0.2249                             |\n| MNIST (n=60000)      | 0.3887 ± 0.2215                      | 0.3290 ± 0.1669                             |\n\n### 4\\. Regarding Clarity and Intuition\nWe sincerely apologize that our presentation made the work difficult to follow. To address your valid concerns, we will implement the following concrete changes in the final manuscript:\n- We will consolidate the \"actionable strategies\" discussed above into a new, dedicated \"Practical Implications\" section just before the conclusion. This will make the takeaways clear and accessible to a broader audience.\n- Furthermore, to improve the accessibility of our proofs, we will add high-level proof sketches or outlines at the beginning of each major proof in the appendix.\n\n## On Questions\n\n### Q1: On experiments correlating complexity with theoretical quantities\n\nA.\nIn fact, Figure 5 in our paper is designed to do exactly this.\n- Figure 5 (top row) shows how the two KL terms from our theoretical bound in Theorem 2 change with the number of samples (n). The second KL term (the CMI, which we prove converges) indeed decreases towards zero, while the first KL term (the empirical KL, which we argue does not) remains high.\n- Figure 5 (bottom row) shows that both KL terms increase as the codebook size ($K$) grows.\n\nThese results directly show that the theoretical quantities in our bounds behave as predicted by our analysis when latent complexity ($K$) and sample size ($n$) are varied. This provides empirical validation for the utility and correctness of our theoretical framework. We will revise the text accompanying Figure 5 to state this connection more explicitly.\n\n\n### Q2: On barriers to applying the method to continuous VAEs\n\nA.\nThe main technical barrier is given as follows, which we mentioned as an important direction for future work.\n\n- **Discrete vs. Continuous concentration:** Our proofs rely heavily on properties of discrete random variables (the codebook index $J$). For example, throughout the proofs we compute which discrete codebook each input datum is assigned to, and we apply concentration inequalities for each assignment. Therefore, in the continuous case such assignments are not available, and the proof techniques in this paper cannot be applied immediately. One may consider forcibly discretizing the latent variable space in the continuous case, but the resulting discretization error is not negligible and substantially affects the analysis. This is what makes extending our results to the continuous setting difficult.\n\nWe will add a more detailed discussion of these barriers to the limitations section (Section 6).\n\n### Q3: On determining if a decoder is \"sufficiently expressive\"\n\nA.\nWhile our theory does not offer a prescriptive formula for decoder architecture—a task beyond the scope of current generalization theory—it suggests a conceptual framework for reasoning about when a decoder might be considered \"sufficiently expressive.\"\n\nOur theory fundamentally decouples the components of test error: **Test Error = Training Loss + Generalization Gap**. We prove that the decoder's complexity does not affect the latter term. This leads to a crucial insight: the decoder's primary role, from a generalization perspective, is to minimize the training loss.\n\nThis principle allows one to form a diagnostic strategy. A decoder could be considered \"sufficiently expressive\" when it is no longer the limiting factor in minimizing the overall test error. In practice, one can monitor the training loss while increasing decoder capacity. If further increases in capacity no longer yield significant reductions in training loss, it suggests the point of diminishing returns may have been reached. At this stage, our theory indicates that additional decoder complexity is unlikely to help the generalization gap, and the focus could then shift to the encoder and LV regularization to reduce the gap.\n\nOur own experimental data is consistent with this line of reasoning. \nSince the NeurIPS rebuttal policy prohibits including figures via external links, we present the results in the table below for your convenience.\n\n#### Train Loss vs Number of Residual Blocks (MNIST)\n\n| n | RB=2 | RB=3 | RB=4 | RB=5 |\n|---|---|---|---|---|\n| 250 | 6.4851 ± 0.2642 | 7.0816 ± 0.2817 | 7.6026 ± 0.2786 | 7.4940 ± 0.7172 | \n| 1000 | 3.4664 ± 0.0293 | 3.4869 ± 0.1286 | 3.3180 ± 0.0398 | 3.2609 ± 0.0905 | \n| 2000 | 2.6391 ± 0.0177 | 2.5114 ± 0.0130 | 2.4645 ± 0.0778 | 2.3915 ± 0.1214 | \n| 4000 | 2.1102 ± 0.0478 | 1.9466 ± 0.0152 | 1.9223 ± 0.0115 | 1.9001 ± 0.0475 | \n\nThis demonstrates how our theoretical insights, while focused on the generalization gap, can inform a practical framework for reasoning about the entire model architecture. We will add this discussion and the supporting data to Appendix G.4 in the final manuscript to provide this valuable perspective to readers."}, {"review_id": "TppXOTgpp2", "reviewer": "Reviewer_kGca", "summary": "This paper presents a theoretical analysis of VQ-VAEs by extending information-theoretic generalization bounds to discrete latent spaces. Introducing a new data-dependent prior within a supersample framework, the authors derive decoder-independent generalization error bounds for reconstruction loss, emphasizing the critical role of the encoder and latent variables in both generalization and data generation. They further propose a permutation symmetric prior to ensure asymptotic convergence of the bounds and provide upper bounds on the 2-Wasserstein distance between true and generated data distributions.", "questions": "None", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n- The paper demonstrates a solid and deep understanding of VQVAE from a mathematical and theoretical perspective.\n- Highlights the crucial role of the encoder and latent variables in both reconstruction and generation, offering guidance for future model design.\n\n### Weaknesses\n- Despite the extensive mathematical theory and statistical error bounds presented, it is difficult to see how this work offers meaningful practical contributions to the community. At least from my perspective, the authors do not leverage their theoretical insights to propose improvements to VQ or demonstrate tangible benefits. Including more evaluations or experiments could strengthen the paper’s overall persuasiveness.\n- The theoretical results, while novel, may be challenging to translate directly into practical improvements or model design guidelines.\n- The focus on decoder-independence, while theoretically elegant, might overlook decoder contributions in real-world scenarios.", "was_revised": true, "final_justification": "Interesting paper with thought-provoking conclusions, but lacks sufficient experimental support.", "rebuttal": "We sincerely thank you for taking the time to review our paper.\n\n## On Weaknesses and Lack of Practical Contributions\n\nWe understand your main concern is that our theoretical work does not offer meaningful practical contributions. We respectfully disagree and believe this is due to our failure to clearly articulate the implications of our findings. Our work provides not just theoretical justifications for existing practices, but also **concrete, actionable guidelines for model design that are supported by both our theory and new empirical evidence**.\n\nWe summarize these practical contributions as follows:\n\n### 1\\. A Clear Guideline on Encoder vs. Decoder Design\nOur central results, Theorems 2, 3, and 4, show that the generalization gap is independent of the decoder's complexity and is instead governed by the complexity of the encoder and the latent variables (LVs). This provides a clear design guideline: to improve generalization, one should focus on the complexity of the encoder's architecture and its regularization since the decoder's capacity has little impact on generalization. This finding is also empirically supported by our experiments in Figures 2, 4, and 6.\n\nFurthermore, our analysis reveals a crucial distinction between the roles of the latent space dimension $d\\_z$ and the codebook size $K$. While their contribution to generalization might seem similar at first glance, our theory clarifies a fundamental difference. From a theoretical viewpoint, increasing the latent dimensionality $d\\_z$ enlarges the generalization bound, whereas the bound does not depend on the codebook size $K$. This follows from Theorem 4 (see Line 332), which depends explicitly on $d\\_z$ but is independent of $K$. Consistently, our Appendix experiments indicate that enlarging $K$ has little effect on the generalization error.\n\n\n### 2\\. Insight into Prior Design\n\nLemma 2 suggests that the optimal prior to minimize the empirical KL divergence is an empirical marginal distribution estimated from the training data, which is analogous to mixture priors like VampPrior. This provides theoretical insight into the choice of priors. Our Lemma 2 also suggest that **data-dependent priors are beneficial** in the unsupervised VQ-VAE context. Motivated by this, we conducted a new experiment where we replaced the standard uniform prior in SQ-VAE with a practical approximation of a data-dependent prior (a moving average of latent usage). The results below show this **theoretically-motivated change consistently improves test loss**, providing direct evidence that our theory can guide the development of better-performing models.\n\n**Table 1: Test loss**\n\n| Dataset (train size) | SQVAE (without data-dependent prior) | Proposed method (with data-dependent prior) |\n|:---------------------|-------------------------------------:|--------------------------------------------:|\n| CIFAR10 (n=50000)    | 0.8523 ± 0.0364                      | 0.8403 ± 0.0247                             |\n| EMNIST (n=112800)    | 0.6564 ± 0.3811                      | 0.4327 ± 0.3032                             |\n| FashionMNIST (n=60000) | 0.4721 ± 0.2964                    | 0.3893 ± 0.2249                             |\n| MNIST (n=60000)      | 0.3887 ± 0.2215                      | 0.3290 ± 0.1669\n\nWe will add this discussion and the supporting data to Appendix G in the final manuscript to provide this valuable perspective to readers.\n\n### 3\\. A Diagnostic Framework for Decoder Expressiveness\n\nOur theory clarifies the decoder's exact role. Since **Test Error ≈ Training Loss + Generalization Gap**, and we prove the decoder does not affect the gap, its primary role is to minimize the training loss. This yields a diagnostic strategy: a decoder is \"sufficiently expressive\" when further increasing its capacity no longer significantly reduces training loss. At this point, our theory proves that focus must shift to the encoder. \n\nTo verify this, we conducted an additional experiment. The results confirmed that for larger sample sizes ($n\\geq 1000$), increasing decoder complexity consistently reduces training loss, while the generalization gap remains flat (see Figure 2.). This provides empirical support for our theoretical framework.\nLet us refer our response to Q.3 of Reviewer nKXf for further details.\n\n#### Train Loss vs Number of Residual Blocks (MNIST)\n\n| n | RB=2 | RB=3 | RB=4 | RB=5 |\n|---|---|---|---|---|\n| 250 | 6.4851 ± 0.2642 | 7.0816 ± 0.2817 | 7.6026 ± 0.2786 | 7.4940 ± 0.7172 | \n| 1000 | 3.4664 ± 0.0293 | 3.4869 ± 0.1286 | 3.3180 ± 0.0398 | 3.2609 ± 0.0905 | \n| 2000 | 2.6391 ± 0.0177 | 2.5114 ± 0.0130 | 2.4645 ± 0.0778 | 2.3915 ± 0.1214 | \n| 4000 | 2.1102 ± 0.0478 | 1.9466 ± 0.0152 | 1.9223 ± 0.0115 | 1.9001 ± 0.0475 | \n\nThis demonstrates how our theoretical insights, while focused on the generalization gap, can inform a practical framework for reasoning about the entire model architecture. We will add this discussion and the supporting data to Appendix G.4 in the final manuscript to provide this valuable perspective to readers.\n\n### 4\\. A Theoretical Justification for Existing Practices\n\nFinally, our Theorems 2 and 5 provide a theoretical justification for using KL divergence as a regularization term. While KL regularization appears naturally in variational Bayes, it was previously unclear if it truly functions as a regularizer for generalization and data generation. Our research is the first to provide a formal justification for this widely used practice.\n\n### Our Revisions\n\nTo make these contributions undeniable, we will add a dedicated \"Practical Implications\" section to the paper to explicitly state these points. We hope these clarifications and our detailed plan for revision will convince you of the value of our work and merit a higher rating."}, {"review_id": "cvTfZeQzNG", "reviewer": "Reviewer_oZtU", "summary": "This work provides an information-theoretic (IT) analysis of the generalisation capacity and data generation quality of VQ-VAEs. \n\nAfter showing that the basic IT bound cannot be directly applied to such (unsupervised) setting if one wants to analyse separately the latent variables (LVs) and decoder parameters, the authors propose a new error bound which explicitly encodes the dependence between the latent variables and supersample indexes to remove this dependency. An analysis of this new bound reveals that the generalisation gap solely depends on the complexity of the LVs and encoders' parameters. However, the proposed bound contains the (non-converging) empirical KL divergence, and a new (converging) bound is proposed that removes any dependency on the empirical KL divergence. \n\nAdditionally, an upper bound on the 2-Wasserstein distance between the true and generated data is derived to assess the data generation quality, and here again, the authors show that the LVs significantly impact this.\n\n Overall, this paper demonstrates the importance of LVs' complexity (and their regularisation) for generalisation and data generation quality, providing some insights into why some training techniques worked well in VQ VAEs.", "questions": "[1] Could the authors provide a more detailed explanation of the supersample setting from Section 2.3? From what I understand, each entry is an $x$ drawn iid from $\\\\mathcal{X}$ and then one uses the associated index to select the $x$ from the correct column when one is in test or training setup. But then $\\\\mathcal{A}(\\\\mathcal{X}_U)$ would only use one element per row, and so $l_0$ would be an nx1 matrix. However, it is stated that $l_0$ is an nx2 matrix, so there is something that I did not understand correctly about how $\\\\mathcal{X}_U$ is created.\n\n[2] The $\\\\tilde{\\\\cdot}$ and $\\\\bar{\\\\cdot}$ are sometimes hard to distinguish (e.g. l. 1044). Could the authors replace the $\\\\tilde{\\\\cdot}$ with something more distinctive like $\\\\breve{\\\\cdot}$, for example?\n\n[3] l.5 I do not think that the authors truly mean \"insufficiently underexplored\". I suggest replacing it with either \"underexplored\" or \"insufficiently explored\". \nl. 378 \"that enabling\" should probably be replaced by \"enabling.\"", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "___Quality:___\n\n[+] The paper is sound, and the claims are well-supported. I did not find any issue with the proposed proofs. However, I am an expert in VAEs, not IT, and I may have missed something.\n\n[+] The limitations of the work are clearly stated and extensively discussed in the conclusion and appendix.\n\n[-] It would have been nice to see more of the experimental part in the main paper.\n\n\n___Clarity:___\n\n[+] The paper is well-written and easy to follow\n \n[+] The maths are clear and easy to follow; each variable is defined before use, and a notation table is provided in the appendix.\n\n[+] The main theoretical results are generally followed by one or two sentences summarising the key points in layperson's terms. This is greatly appreciated as it avoids breaking the flow of the paper and helps the reader check that their understanding is correct.\n\n[-] Some of the notations are difficult to distinguish and may gain in readability if slightly updated (see comment 2).\n\n[-] There are a few typos (see comment 3).\n\n___Significance:___\n\n[+] Formally showing that the generalisation and data generation quality strongly depends on the LVs regularisation is important as it helps understand why some practical settings of VQ VAEs worked well and opens some avenues for improving the capabilities of these models.\n\n[-] It is a shame that the result from Thm. 3 cannot be used as a generalisation score due to its computational cost, as this would have increased the significance of this work.\n\n___Originality:___\n\n[+] This paper provides a new understanding of why some empirical techniques used for VQ VAEs worked well.\n\n[+] While such analysis was previously done in a supervised setting, this has not been attempted in unsupervised learning (as far as I know, but as I said before, I am not an expert in IT and may have missed an existing pocket of literature). Although the current work is limited to a discrete latent space, it still advances our understanding of unsupervised models.\n\n[-] The results are not very surprising (the importance of LV regularisation was already observed empirically) and are restricted to VQ VAEs.", "was_revised": true, "final_justification": "The authors addressed any concerns I had. I still believe that this is a good paper, which should be accepted, but the paper's impact is not sufficient to further raise my score", "rebuttal": "We sincerely thank you for your insightful, and positive feedback.\n\n## On Weaknesses\n- **More experiments in the main paper:** Due to the strict page limit, we moved many experimental details and additional results to the appendix. We will revise the main text to include a more detailed discussion of our key experimental findings (e.g., from Figure 5) to better support our theoretical claims within the main paper.\n\n- **Significance and Originality:** While the importance of LV regularization was known heuristically, our work provides the first rigorous, information-theoretic proof that explains why this holds for VQ-VAEs, and that the generalization gap is independent of the decoder. We also agree it is a limitation that the bound in Theorem 3 is not immediately computable, but we see its main value as a theoretical tool that proves the existence of a well-behaved, asymptotically vanishing bound, paving the way for future work on practical estimators.\n\nMoreover, grounded in this rigorous theory, our analysis has direct practical implications. These include the importance of encoder design under a decoder‑independent bound, the theoretical justification of KL regularization, and insights regarding data‑dependent priors. For further details, please see our response to Reviewer qLsN (Q1). As also stated in our response to Reviewer qLsN (Q1), using a data‑dependent prior not only makes the bound theoretically evaluable but also leads to improved model performance numerically in practice. These implications follow from a formal theory, and we believe they provide important guidance for VQ‑s. We plan to add a new Practical Implications paragraph immediately before Sec. 6 to communicate the contribution of this paper more clearly to the community.\n\n## On Questions\n\n### Q1: On the detailed explanation of the supersample setting\n\nA.\nWe apologize that our explanation was confusing. Let us clarify the construction step-by-step:\n- **Supersample $\\tilde{X}$:** We start with a matrix $\\tilde{X}$ of size $n\\times 2$, containing $2n$ i.i.d. data points from the data distribution $\\mathcal{D}$. Each row $m$ contains a pair of data points: $(\\tilde{X}\\_{m,0}, \\tilde{X}\\_{m,1})$.\n- **Random Index $U$:** We generate a random binary vector $U = (U_1, \\ldots, U_{n})$, where each $U_{m} \\in {0,1}$.\n- **Training Set $\\tilde{X}_U$:** The training set consists of $n$ samples. For each row $m$, we select exactly one sample from $\\tilde{X}$ using the index $U_m$. Therefore, the training set is $\\tilde{X}\\_U = (\\tilde{X}\\_{1,U_1}, \\tilde{X}\\_{2,U_2}, \\ldots, \\tilde{X}\\_{n,U_n})$. This is a set of $n$ data points.\n- **Loss Matrix $l_{0}(W, \\tilde{X})$:** After training a model parameter $W$ on $\\tilde{X}\\_{U}$, we evaluate its loss on all $2n$ data points in the original supersample matrix $\\tilde{X}$. The notation $l_{0}(W, \\tilde{X})=((l_0(W,\\tilde{X}\\_{1,0}),l_0(W,\\tilde{X}\\_{1,1})),\\dots,(l_0(W,\\tilde{X}\\_{n,0}),l_0(W,\\tilde{X}\\_{n,1})))^\\top$ represents the resulting $n \\times 2$ matrix of loss values. \n\nThe confusion may have arisen from the distinction between the training set (which has $n$ points) and the matrix on which the final loss is evaluated (which has $2n$ points). We will revise Section 2.3 to make this process much clearer.\n\n### Q2: On the notation for $\\tilde{J}$ and $\\bar{J}$\n\nA.\n We will change $\\bar{J}$ to a more distinctive symbol, such as $\\breve{J}$ throughout the paper to improve readability. Thank you for this excellent suggestion.\n\n### Q3: On typos\n\nA. Thank you very much for catching these typos. We will correct \"insufficiently underexplored\" to \"insufficiently explored\" and fix \"that enabling\" in the revised manuscript."}]

Author rebuttal:

Meta-review: The paper presents an information theoretic analysis of vector quantized Variational Autoencoders (VQ-VAEs) with discrete latent spaces. Using a latent variable approach inspired by information bottleneck, the paper presents a novel data-dependent generalization bound based on the encoder and the complexity of the latent variables. The paper also provides an upper bound on the distance between the true and generated distributions, again independent of the decoder. 

The strengths of the paper are the novel decoder-independent generalization bound and the data-dependent prior, which provide nice theoretical results with clear ties to practice. The main weaknesses of the paper are the looseness of the bounds and the limited practical implications, which were discussed in detail with the reviewers. 

The paper presents a novel theoretical approach on a interesting class of models. Both data dependent and decoder independent bounds are novel, interesting results that will be of interest to the community. The task of improving the bounds and demonstrating concrete implications will inspire future work in the area.
Decision: Accept (poster)