Rethinking Information-theoretic Generalization: Loss Entropy Induced PAC Bounds

Dear Reviewer Fiyn, thanks for your valuable comments! We address your raised questions as follows:

Should we assume the loss has finite alphabet so as to allow well-defined Shannon entropy?

Yes, the losses are assumed to be discrete and have finite cardinality. This assumption aligns well with digital computers employing floating-point numbers.

Other minor questions.

Thank you for the suggestions. These problems have been fixed in the updated manuscript.

The novelty of this work is limited.

As discussed in the Introduction, we briefly summarize our contributions in this paper as follows:

• We improve previous data-independent generalization bounds in (Kawaguchi et al., 2023) by introducing loss entropy. Our bounds are proven to be strictly tighter, and also provide the first information-theoretic understanding of the MEE criterion, showing that the generalization error scales with $O(\sqrt{H(E^w)/n})$.

• We explore a novel technique beyond the traditional Donsker-Varadhan formula (Lemma 3) for decoupling random variables, which is the core of information-theoretic generalization analysis (see the paragraph preceding Section 3.2.1). Benefitting from this, we are able to reduce the dimensionality of the key information quantities in information-theoretic generalization bounds to $1$-dimensional, yielding computationally tractable high-probability generalization bounds.

• By further exploring the thresholding strategy, we alleviate the stringent bounded loss assumption in previous high-probability and fast-rate generalization bounds, achieving significantly tighter bounds as verified by our empirical experiments.

Dear Reviewer gBmk, thanks for your detailed and constructive comments! We will address your concerns in the following response:

In Theorems 1, 2, 3, and 4, it is essential to specify the distribution under which the inequality holds.

As we stated in Section 2, for Theorem 1 and 2, the probability is taken over $S$; for the following Theorems 3 - 6, the probability is taken over $W$, $\tilde{S}_l$ (or $\tilde{S}_s$), and $U$ (or $\tilde{U}$). We have updated the expressions of these Theorems to reflect this.

The paper states that "the model $w$ is deterministic, which is commonly the case for modern deep learning models," but notes that $w$ is not truly deterministic due to initialization.

Sorry for the confusion, but we do not presume that the model itself is deterministic. Instead, we mean that the forward propagation of the neural network does not involve external randomness, such that the output $L^w$ can be determined given the sample $Z$, and we have $H(L^w|Z) = 0$ for any given model $w$. This is commonly seen in most CNN architectures.

In the discussion preceding Section 3.2, the authors mention that their data-independent bounds provide insights into understanding the generalization of the MEE criterion. However, for binary classification, margin-based loss functions, as discussed in [1], cannot be represented as a function of $E^w$.

Following the notations in [1], let $L^w = \phi(Y f(X))$ be a margin-based loss function and $E^w = Y - f(X)$. Here, $L^w$ can still be represented as a deterministic function of $E^w$ given $Y$: $L^w = \phi(Y (Y - E^w))$, so we have $H(L^w|Y) \le H(E^w|Y)$ by the data-processing inequality. The same conclusion then follows by the fact that $H(E^w|Y) \le H(E^w)$.

The effect of the learning algorithm on Theorems 1 and 2 is unclear. It seems that the model, $w$, remains fixed and independent of the training set, limiting the practicality of these upper bounds.

Theorem 1 and 2 are intended to be data-independent, where the model $w$ is assumed to be fixed and independent of $S$. As we discussed in the last paragraph of Section 3.1, these bounds are still applicable to pre-training or validation tasks. Note that the subsequent Section 3.2 provides data-dependent bounds, where the model $W$ is no longer fixed and is learned from $\tilde{S}_s$, enabling a wider range of applications in practice.

The proof of Lemma 13 lacks clarity. More elaboration is needed, especially in the last line of the proof.

We include more details in the proof of Lemma 13 for better clarity.

The assumption in Theorem 5 that $\kappa > B^{W,\tilde{S}}$ guarantees a valid $C_i$ due to the term $\log(2-e^{2\eta \hat{L}_i^W})$. However, Theorem 6 discusses the case where $\kappa < B^{W,\tilde{S}}$. Explain how $C_i$ remains valid in Theorem 6.

Note that in Theorem 6, $\hat{L}_i^W$ is replaced by $\hat{L}_i^{W,\kappa}$ in the expression of $C_i$, where $\hat{L}_i^{W,\kappa} \le \kappa$ is guaranteed. Therefore, $C_i$ remains valid.

If the loss function is bounded, then $B^{W,\tilde{S}}$ is also bounded. Can the authors provide an example where the loss function is unbounded, but $B^{W,\tilde{S}}$ remains bounded?

To evaluate our bounds, $B^{W,\tilde{S}}$ is only required to be finite, and boundedness is not necessary. For example, although the cross-entropy loss is usually unbounded, we always get finite loss values during the training process, resulting in finite $B^{W,\tilde{S}}$. In fact, for any long-tailed loss distribution, we have $P(L_i^W<\infty) = 1$, so $B^{W,\tilde{S}}$ is guaranteed to be finite with probability $1$.

Please verify the equation between eq. (41) and (42) in the appendix.

Thanks for pointing out the typos in our proof. These typos have been fixed and do not affect our subsequent analysis.

The discussion after Theorem 5 is unclear. Define what an "interpolating regime" is, and clarify whether the empirical risk is considered a random variable in Theorem 5.

Interpolating regime is the cases where the model achieves $0$ training risk (Hellstrom & Durisi, 2022) (Wang & Mao, 2023), i.e. $L_{i,\tilde{U}_i}^W = 0$ for all $i \in [1,n]$. The empirical risk is considered a random variable in this paper, where the randomness comes from $W$, $\tilde{S}_l$ (or $\tilde{S}_s$), and $U$ (or $\tilde{U}$).

Thank you for your response. It addresses many of the points I raised. Below are some points where I still have concerns.

---

Regarding the assumption of discreteness and the binning:

I understand that the discrete assumption enables you to derive bounds with attractive properties, and that it has been used in prior works. Neither of these motivate applying it to continuous settings like regression, which needs further justification.

For the bins, I understand that it is impractical to choose machine precision as the bin size. Thus, it is misleading to say that the discrete approach “aligns well with digital computers employing floating-point numbers”—as you point out, this is still too impractical to be well-aligned.

Regarding Figure 5: Thank you for producing this additional figure. I do not agree that this demonstrates a mild impact. For MNIST, SGLD, for instance, the loss-entropy bounds increase by around a factor of 2. I suspect that this increase would continue until you reached machine precision — intuitively, one would expect some losses very close to 0, while the rest would almost invariably be in their own bin, right?

I think there are some valid conclusions that you can draw based on the binned bounds, though, but they only apply to the actual binned loss (which can be used to get upper bounds on the underlying loss). So, if you use a bin size of $0.5$ and get a bound of $0.6$, you can conclude that the actual loss is at most $1.0$.

---

Regarding the appearance of the test loss on the RHS of bounds: I understand that the maximum observed test loss is finite in practice. This does not change the fact that you are bounding the test loss in terms of the test loss. If the test loss is assumed to be known, you already have a very tight bound (an equality, in fact). Arguably, similar critiques can be raised against any e-CMI-type bound, but a dependence on information measures including the test loss can be more reasonably controlled than just the actual value of the test loss itself. This raises questions about the purpose of the bound.

---

Regarding the sub-Gaussianity assumptions: it is still not clear under what distribution the losses are sub-Gaussian. Here, $L^W_{i,0}=\ell(W, Z_{i,0})$. Do you mean that it is sub-Gaussian under the joint distribution of $W, Z_{i,0}$? Do you mean that, for a fixed $w$, it is sub-Gaussian under the expectation of $Z_{i,0}$? If it is the first one, then this is assuming sub-Gaussianity under the joint distribution of the hypothesis and training data, which is significantly different from the standard assumption, and if it is the second one, then this is not sufficient for the rest of the argument.

---

Regarding $P(\Delta(W,\tilde{S}_l,U) \ge t)$: the notation you use still has the same issue as I commented about. If you either use lower-case letters to indicate fixed instances, or use $P_U$ to notate the probability under the randomness of $U$, or potentially write that it is the probability given (W,\tilde{S), it would be clearer.

---

Regarding the discussion of related work in Appendix G.1: I appreciate that you tried to cover all related work, but the suggestion mainly regarded giving some qualifications for the statement “these bounds are primarily restricted to average-case scenarios” when discussing information-theoretic generalization bounds.

I am not sure the way the term “PAC” is used is really consistent with PAC learning. PAC bounds are typically uniform in some sense, whereas the bounds in this paper are tail bounds under the joint distribution of data and hypothesis.

PAC bounds typically indicate generalization bounds that hold for a certain class of hypotheses, where the probability is taken over the draw of the training dataset. Generally speaking, Theorem 1 and 2 can be regarded as a special case of PAC bounds, where the hypothesis class is taken as a single $w$. Upon further literature review, we agree that the terminologies of "high-probability bounds" or "single-draw bounds" are more suitable to characterize our theoretical results. As defined in (Hellstrom et al., 2023), single-draw bounds are generalization bounds that hold with high probability over the draw of both the dataset and the hypothesis. We have updated our main text accordingly to enhance clarity.

Hellstrom F, Durisi G, Guedj B, Raginsky M. Generalization Bounds: Perspectives from Information Theory and PAC-Bayes.

p.5, “The most notable improvement of…” here, a comparison is made to CMI bounds instead of e-CMI bounds, which are arguably more relevant; “This illustrates a novel trade-off” is it really a trade-off? Both are just preferred to be small.

As indicated by the second equation on page 5, the loss entropy term $H(R^W)$ is also likely to be tighter than the e-CMI quantity $I(R^W;U|\tilde{S}_l)$. During training, only the training loss entropy can be explicitly minimized. To balance the minimization of training and test loss entropies, one needs to adopt certain regularization (e.g. weight decay, dropout), which may negatively affect training loss entropy, implying a trade-off between the two.

In the numerical evaluations, the cross-entropy loss is used, which is continuous. To compute bounds for MNIST etc, a binning with a bin size of 0.5 is used. The usefulness of the results, despite the assumption of discreteness, was motivated by the fact that floating-point numbers are used in practice. Certainly, machine precision is significantly smaller than 0.5. This specific choice is also not motivated. What is the effect when decreasing the binning size? Is there any reason to believe that this is a sensible choice?

It is impractical to choose machine precision as the bin size, as we do not have enough samples to estimate the probability of each bin. Separating the data into $5 - 10$ bins is a common choice for entropy estimation (Yu et al., 2019) (Kawaguchi et al., 2023). In our empirical studies, the number of bins is roughly $15$, already larger than the common value $10$. We further report the visualization results with a bin size of $0.3$ in Figure 5. It can be seen that the bin size only has a mild impact on the final results. Considering that we only have $40$ samples for each loss for CIFAR10 experiments, there will not be sufficient samples for probability estimation once we further decrease the bin size.

Yu S, Giraldo LG, Jenssen R, Principe JC. Multivariate Extension of Matrix-Based Renyi's $\alpha$-Order Entropy Functional.

In the numerical evaluation, optimization is performed over several constants in the bounds. In the derivation, they are assumed fixed, and the bounds hold with a certain probability for this fixed value. In order to have a valid bound while optimizing, one needs to perform some kind of union bound, or other argument to guarantee the validity. Otherwise, it should be stated that the bounds are not actually valid due to this optimization, but are just illustrative. Did I miss something that motivated this optimization?

In this paper, our bounds are presented in the form of $P(\Delta \le B) \ge 1 - \delta$, where $\Delta$ is the validation error and $B$ is the upper bound involving the constants $\kappa$, $\gamma$, etc. Let $b = \mathbb{E}[B]$ be the expectation of $B$ taken over $W$, $\tilde{S}_s$, and $\tilde{U}$. We then optimize the constants by minimizing $b$, which is a constant independent of the randomness in our bounds. Such an optimization strategy is sufficient to guarantee the validity of our results.

The bounds are said to be compared to the Binary KL bound of Hellstrom and Durisi, but Theorem 10 in the paper is not a binary KL bound. Furthermore, in HD Thm. 7, the information measure that appears is not a CMI, but a random KL divergence depending on the supersample and selection variable. Also, the binary KL bound does not imply a bound on the generalization gap, but instead, directly bounds the population loss given a training loss. Finally, the binary KL bound is inherently only valid for bounded losses, as the binary KL is undefined for inputs outside of $[0,1]$. Is the comparison actually to Thm. 10, i.e., the square-root bound of Hellstrom and Durisi?

Sorry for the confusion, and we have corrected Theorem 10 to represent the binary KL bound. Since the stochastic KL divergence is hard to estimate, we conduct the comparison by averaging both bounds over multiple draws of $\tilde{S}_s$ and $\tilde{U}$. In this way, the averaged stochastic KL divergence approaches the CMI quantity, which is then estimated through a lower bound approximation. To accommodate unbounded losses, we empirically estimate the largest loss $B^{W,\tilde{S}_s}$ and adopt the scaled loss $\ell(W,\cdot)/B^{W,\tilde{S}_s}$ as suggested by (Hellstrom and Durisi et al.).

The plots show the generalization gap, rather than the bound on the population loss itself. Arguably, the latter is more interesting, since a low generalization gap with a high training loss is not very useful. Is it possible to show the bound on the population loss?

As the population loss is defined in terms of expectation, our results are not directly applicable to bound the population loss. Fortunately, in the supersample setting, the population loss can be approximated by the average test loss when $n$ is large enough. We additionally visualize the comparison between different upper bounds for the test risk in Figure 6.

Several of the bounds on the generalization gap have an explicit dependence on the value of the test loss itself on the right-hand side. For bounded losses, this can simply be upper-bounded, but otherwise it seems quite puzzling.

Note that evaluating these bounds only requires the losses to be finite but not necessarily bounded. Even for unbounded loss functions, the losses are still finite in practice, e.g. one always gets finite training and validation loss values using the cross-entropy loss. For any long-tailed loss distribution, we have $P(L_{i,0}^W < \infty) = 1$, so the right-hand side of these bounds is always finite in practice.

The bounds depend on average quantity (entropy), and are hence not empirical. This may merit a discussion.

Indeed, the underlying distributions of the losses are unknown in practice and can only be approximated by sampling. This requires repeating the training progress several times to acquire sufficient samples. The most widely used entropy estimators are kernel density estimation and binning methods, which are both adopted in this paper as we discussed in Section F.

PAC-Bayesian bounds are not discussed much, despite being closely related. They are particularly relevant since you point out that recent bounds are “primarily restricted to average-case scenarios”. Moreover, the supersample setting is equivalent to almost exchangeable priors (Audibert, “A better variance control for PAC-Bayesian classification,” 2004 and Catoni, 2007). It also seems relevant to compare to single-draw bounds from, e.g., Esposito et al., "Generalization Error Bounds Via Rényi-, f-Divergences and Maximal Leakage”, 2020.

We replenish discussions with these related works in the Appendix, see Section G.1.

As noted in Theorem 3, the proofs require sub-Gaussianity under the selection random variable, which has to hold for any fixed instance of the loss matrix/vector. This seems to get lost in the later derivations. First, in Lemma 14, it is assumed that $\ell(w,X)$ is sub-Gaussian. This seems to mean that it is sub-Gaussian when taking the expectation over $X$. However, in the proof, it is needed that $\ell(w,x_U) - \ell(w,x_{1-U})$ is sub-Gaussian under $U$ for all $w$, $x_0$, and $x_1$ (or under the distribution where $X$ and $W$ are distributed jointly and $U$ is drawn independently). This does not follow from the sub-Gaussianity that is assumed. There are cases beyond bounded losses that one can consider (e.g., Steinke & Zakynthinou, Thm. 5.1 and Sec 5.4). Is my reading correct or did I miss something? The same issue occurs in Theorem 9.

In Theorem 3, the sub-gaussianity is only required for the single draw of $W$ and $\tilde{S}\_l$. In other words, $\Sigma_{R^W}$ is a random variable that is determined by $R^W = \\{L_1^W, \cdots, L_{n+1}^W\\}$. $\Sigma_{R^W}$ can be treated as a tightened version of $B^{W,\tilde{S}\_l}$, e.g. given two losses $R^W = \\{0, 2\\}$, we have $\Sigma_{R^W} = 1 < B^{W,\tilde{S}_l} = 2$.

The typo in Lemma 14 and Theorem 9 has been fixed. We are actually assuming the sub-gaussianity of the loss variables $L_{i,0}^W$ and $L_{i,1}^W$. It is easy to prove that the sum of two (possibly dependent) $\sigma$-subgaussian variables is $2\sigma$-subgaussian by its definition.

Also, for, e.g., the equation preceding (29), it is written $P(\Delta(W,\tilde{S}_l,U) \ge t)$. This is misleading, as it appears that the probability holds over a joint draw of $(W,\tilde{S}_l,U)$, but in fact, only $U$ is random while $W$ and $\tilde{S}_l$ is fixed. Is this correct?

Yes. We have updated the proof of Theorem 3 and 4 for better clarity.

At the end of p.4: the supersample generalization gap approaches the true one, but the same is not true for the leave-one-out, as the test loss is still evaluated on only one sample. Does this limit the usefulness of the LOO results?

This is a natural limitation of the LOO setting that cannot be overcome from the perspective of generalization bounds. In the last paragraph of page 5, we discussed the possibility of using our techniques to explore alternative supersample settings of randomly selecting $n < m$ samples from $m$ supersamples. By letting $n \rightarrow \infty$ as $m \rightarrow \infty$, this limitation could be overcome in these new settings.

Dear Reviewer YPBm, thank you for the thorough reading and constructive comments! They are really helpful for us to further improve our manuscript. In the following response, we will address your concerns one by one:

Most of the weaknesses arise from the application to potentially unbounded losses. If the results are specialized to the 0-1 loss, all of the notable issues seem to disappear.

Note that the applications of our bounds are not limited to classification but also regression tasks, where the 0-1 loss is no longer applicable. Even for classification tasks with 0-1 loss, the previous binary KL bound is still intractable due to its high-dimensional nature. This is the main benefit of our results compared to the previous bounds.

The bounds assume discrete loss functions, which enables the use of the entropy and the typicality arguments. Still, the bounds are applied to, e.g., the cross-entropy loss, which is continuous, with the motivation that all losses can be considered discrete due to floating-point numbers. I am not sure if this is convincing. Increasing the precision used would affect the cardinality of the loss, and potentially degrade the bounds. This does not seem like reasonable behavior, and would require a stronger motivation.

We highlight that the discrete assumption is common and adopted in previous works (e.g. Shwartz-Ziv et al., 2019, Kawaguchi et al., 2022; 2023). It allows the adoption of the well-defined discrete Shannon's entropy, which is always positive, and facilitates developing generalization bounds based on $1$-dimensional information measures. Otherwise, the differential entropy can be arbitrarily negative, so the generalization analysis will be restricted to mutual information measures, which are at least $2$-dimensional and therefore harder to estimate.

In addition, such a discrete scheme enables a brand-new technique beyond the Donsker-Varadhan formula (Lemma 3) for decoupling random variables by separating the "typical subset" and then taking the union bound over them. The new technique, detailed in the paragraph preceding Section 3.2.1, is pivotal for our generalization analysis and enjoys broad extendability beyond leave-one-out and supersample settings.

Lastly, many learning tasks naturally satisfy the discrete assumption, including semantic segmentation (with risk in pixels), discrete ordinal regression, generative models with hamming distance losses, and ranking losses over multiple objects. It is also possible to discretize the loss function before evaluation, e.g. round to 1 decimal. Such strategies are widely adopted in information-theoretic learning tasks (Biesiada et al., 2005) (Vinh et al., 2014), and only cause a mild impact on the generalization error.

Shwartz-Ziv R, Painsky A, Tishby N. Representation compression and generalization in deep neural networks.

Biesiada J, Duch W, Kachel A, Maczka K, Palucha S. Feature ranking methods based on information entropy with parzen windows.

Vinh N, Chan J, Bailey J. Reconsidering mutual information based feature selection: A statistical significance view.

In the data-independent bounds, it is assumed that the features are generated from a function that depends on an $m$-dimensional nuisance variable, and that the model has finite sensitivity to the nuisances, even in a worst-case sense. This seems like quite a strong modeing assumption, but is not motivated or discussed in detail.

The nuisance variables are assumed to be the source of randomness in $X$ given $Y$. Their existence is well-motivated, e.g. for an animal classification task, the background, the position, or the behavior of animals do not affect the true classification label, and are therefore nuisance variables. It is also natural to assume that $m$ is finite and smaller than the dimensionality of $X$. For a given hypothesis $w$, one can determine the set of possible loss values $\mathcal{L}^w$, which is assumed to be finite. Then it is trivial to show that the sensitivity is finite by noticing $c^w \le \sup_{l_1,l_2 \in \mathcal{L}^w}|\log P(L^w = l_1) - \log P(L^w = l_2)|$. Since $m$ and $c^w$ are both constants irrelevant to $n$, these terms could be simply ignored for asymptotical analysis when $n \rightarrow \infty$, and allow us to mainly focus on $H(L^w)$ or $H(L^w|Y)$.

Theorem 3 is said to be most useful in the interpolating setting. The interpolating bound of Haghifam et al decays with log(n), unlike the presented bound. This merits a mention and discussion.

The generalization errors in (Haghifam et al., 2022) are expressed as expectations and thus are not directly comparable with our results. We add relevant discussions in Section G.2.

Thank you for your reply.

---

Sub-Gaussianity: Okay, I think the steps are essentially fine, although I think the argument sort of implicitly assumes zero-mean? However, when you take the difference of the two terms I think this does not matter. The assumption of sub-Gaussianity under the joint distribution of the data and hypothesis is a bit strange, and I am unsure if this really takes you much further than essentially bounded losses (e.g., sub-Gaussian under $P_Z$ for all $w$ does not imply your condition).

---

Regarding the appearance of the test-loss: okay, for some cases the exact value is not needed. But I don't see how you get away $\tilde C_1^W$ in Theorem 4 -- how would you estimate/bound the sum of squared test-train-loss gaps without knowing the test loss?

---

Regarding the discretization: the technique you present in App. G.3 appears to be neat and to work. However, your figures appear to be the same. Unless I misunderstand, G.3 does not mean that your results as-presented are valid -- you would need to estimate both training and test loss using the perturb-discrete approach, and also use these perturb-discretized losses to estimate the loss entropy. Could you clarify this point?

Dear Reviewer xf1n, thanks for your valuable suggestions! We address the raised questions as follows:

The major concern with this work is that the analysis relies on $b^w$ and $B^{w,S}$, which represent the maximum of the loss. I think this makes the bounds sensitive to noise. In fact, it is sufficient that one sample has a relatively high loss to make the whole bound loose. The authors do not perform any experiments or analysis to show how robust their bounds are to noise.

The quantities $b^w$ and $B^{w,S}$ are only considered in our data-independent bounds (Theorem 1, 2), which are mainly for qualitative analysis purposes. In the following data-dependent analysis, our main results (Theorem 3, 4, 6) overcome this limitation by tightening the $b^w$ and $B^{w,S}$ terms with the subgaussian norm or $L_2$ norm of loss differences, which are naturally more robust against noises. We refer the reviewers to Figure 3 for a comparison between these robust bounds (Theorem 6) and the bound explicitly relying on $B^{W,\tilde{S}_s}$ (Theorem 5). In fact, this is one of the major contributions of our work: while the previous binary KL bound is easily loosened by the largest loss, our bounds are insensitive to extreme loss values and greatly improve over the binary KL bound (see Figure 2).

Compared to the bounds in (Kawaguchi et al., 2023), the introduced bounds in this paper, e.g., Theorem 2, do not have any explicit dependency on the input variable $X$. Interestingly, It only depends on the label $Y$. Can the authors comment on this point?

The data-independent bounds are implicitly dependent on $X$ through $L^w$: recall that $L^w = \ell(w, Z)$, where $Z$ denotes a pair of $X$ and $Y$. This is actually one of our main contributions: the loss entropy measure $H(L^w|Y)$ is strictly tighter than the original term $I(X;T^w|Y)$ in (Kawaguchi et al., 2023), as we remarked below Theorem 2.

Related to my first question, as the bounds depend directly on $Y$, it would interesting to see how sensitive they are to label noise. Do the authors have any comments on this? I think in this case, it might be interesting to conduct an additional experiment with label noise to evaluate how robust the bounds are.

Our data-independent bounds (Theorem 1, 2) are incapable of quantitative analysis since they involve the properties of the underlying nuisance variables ($c^w$ and $m$). Instead, we conduct a correlation analysis following (Kawaguchi et al., 2023) and show that $H(L^w)$ and $H(L^w|Y)$ can better reflect the behavior of the generalization error. As suggested by the reviewer, we conducted additional experiments with 20% label noise in Table 2. It can be seen that our loss entropy metrics are consistently the better indicators of generalization.