A unified framework for information-theoretic generalization bounds

Summary

The paper studies the generalization error of the statistical learning algorithms from the information-theoretic point of view. In particular, by leveraging a “decorrelation lemma”, the authors show how various previously established upper bounds on the generalization error, including the common information-theoretic bounds, PAC-Bayes bounds, and chaining versions of them, can be recovered using this decorrelation lemma; and therefore, present a unifying methodology for establishing these bounds.

Strengths

The authors using the introduced decorrelation lemma managed to compactly recover various existing upper bounds on the generalization error. In particular, the method naturally can be combined with the chaining methods to recover a number of results such as the generalization bounds of Zhou et al., Asadi et al., and the bound of Fernique and Talagrand on the expected supremum of a stochastic process. Moreover, the work presents high probability bounds; which is rarely common in the information-theoretic bounds on the generalization. I believe the decorrelation lemma is a powerful technical lemma using which hopefully, new understandings and bounds can be achieved in future works. For this reason, I think the paper could be of interest to the part of the Neurips audiences that are interested in the theoretical understating of statistical learning algorithms.

Weaknesses

1. The main weakness of the work is that it remains only at the technical level. - 1.a. The form of the general bounds, e.g. Theorem 3, does not seem to be easy to compute. It is not clear whether the general results can be leveraged to derive new bounds or to give a new understanding of the generalization error of the learning algorithms (in general or for a particular algorithm). Can authors provide cases where the results of this work give “new” and “simple” or "practical" results? I think the authors would agree that the justification of how coupling in Theorem 3 can be used to show that the expected generalization error is zero when $P_{W|S}=P_W$ is not convincing enough to show the utility of that. - 1.b. The only cases where these general results give concrete results are when they recover previous results (e.g. Information-theoretic bounds or PAC-Bayes ones) but only with the worst coefficients. - 1.c. Moreover, even at the intuition level, it is not clear if this work, and more specifically, this decorrelation lemma, gives any new “understanding" of the generalizability of the learning algorithms. Does this work, and this decorrelation lemma, can provide any new intuition/understanding? For these reasons, unfortunately, the paper remains only on the “technical level” and we can only hope that this interesting tool can be used for establishing new concrete results/understandings. 2. The paper lacks a proper literature review and comparison with other works. Indeed, only 25 works have been cited; most of which are purely listed in the very short introduction. The authors are needed to widen the comparison of the current work with previous literature on generalization error (including different information-theoretic approaches, PAC-Bayes ones, compression-based ones, etc.) to make a clear picture of where this work/tools stand. 3. As an example of the previous point, perhaps, as claimed by the authors, one of the main advantages of this work is the unifying methodology for deriving various existing bounds. This is indeed interesting, as has been done in some other works before. Non-exhaustive examples of some of these works, sorted by year, are: “PAC-MDL Bounds” (Blum and Langford 2003), arXiv:1912.01439, arXiv:2006.13057, arXiv:2105.01747, arXiv:2110.11216, arXiv:2111.05275, arXiv:2203.02474, arXiv:2303.05369. Although some of these works are less directly related as they consider different approaches (and some maybe are more directly related), I believe it is helpful to put this work in this context as well: how does the unifying approach of this work differ from previous attempts? What are the similarities? What are the “limitations” of those works and this one?

Questions

The main ones are mentioned above. Some other minor typos/comments: - Although trivial but K and C are not introduced in line 93. - In lines 120-121, it is claimed that “the right-hand side can be further upper-bounded in terms of the information divergence $D(P_{Y|X}\| Q_Y)$ using Proposition 1.” Can it be done for any function $f(y)$? - Typo in line 141: $\frac{|gen(w,S)|}{\sigma \sqrt{6/n}}$ - The proof of Theorem 5, or a comment on how it is derived seems to be missing. - There are typos in the proof of Proposition 1; after line 367, the LHS should be $\frac{d\mu}{d\nu}\log(\frac{d\mu}{d\nu}+1)$. A similar typo exists on the first line after 368. - The term “f” seems to be missing in the last line of equations after line 379.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Mentioned above.

Summary

This paper describes some steps of the standard formula to obtain generalization error bounds: (i) decoupling of the joint distribution + (ii) chaining. Then, they use this formula contributing mainly on the first front by deriving new decoupling results based on Orlicz $\psi\_p$-norms that can be cast into the standard decoupling results based on the relative entropy. Additionally, they also include a section describing results based on couplings between the hypothesis' distribution obtained with the algorithm's kernel evaluated on a training set and the hypothesis' marginal distribution. These are used to develop their bounds on chaining, but they can stand alone independently. Finally, the authors note that their results can be extended to high-probability PAC-Bayes bounds and that these can be used to also recover bounds of the type of Fernique's and Talagrand's bounds on the expected supremum of a stochastic process.

Strengths

The paper is generally well-written and easy to follow. It does a good work summarizing how to derive generalization error bounds using Orlicz norms and, therefore, using the relative entropy of the posterior hypothesis distribution $P\_{W|S}$ with respect to a prior $Q\_W$. Their decoupling result (or "decorrelation lemma") is interesting and they gain clarity and interoperability by relaxing the tighter standard result they could have obtained with Young's inequality. I believe that Lemma 1 is the main result of the paper, which is later interpreted and contextualized into the generalization error set-up. It is good that the presented bounds can be brought down (up to constants) to known bounds in the community. This is usually a necessary "goodness test" to know if the results obtained are valuable. Particularly, it was good to see that Fernique's and Talagrand's bounds were recoverable this way. [*Even though the strengths section will be shorter than the weaknesses, I believe this is a good paper. The authors should note that this will be the case only to help them improve the manuscript and to expand on each of the weaknesses so it can be easily addressed.*]

Weaknesses

While their "decorrelation lemma" is novel and interesting, the applications of this lemma afterwards for the estimates using couplings, the usage of chaining in the space of measures, and the tail estimates are standard and shown otherwise with different decoupling lemmas (see e.g. [7,9,11,15,16,17,18] of the references of their own paper). While probably not on purpose, the paper seems to position itself as if it is introducing this set of steps to obtain this kind of bounds. This is not accurate, as these procedures have been used and done previously, just with a different (although maybe less general in some situations) decoupling lemma. I believe it would benefit the paper to make this clear both in the introduction and at the start of each of these sections. The paper obtains results based on the inverse of an Orlicz norm of the Radon-Nikodym derivative of the posterior with respect to the prior. While this seems to be more general, the paper only gives examples of this instantiating into relative entropy-based bounds. In the end, it does not provide any example of anything new to gain by using their framework with respect to what was already known. This is not super problematic, but when the constants of the bounds are deteriorating under this framework, it is good to show that it can produce new results that lead to interesting conclusions. Similarly to the comment above, the paper does not give examples or motivation to many of their bounds. For instance: - Why are the bounds using couplings useful? The paper mentions the fact that when the algorithm ignores the data, i.e. $P\_{W|S} = P\_W$ a.s. and the prior $Q\_W$ is chosen to be the real marginal of the hypothesis $P\_W$, then the resulting bound is exactly zero, which is not the case for the bounds presented in Section 4. However, the bounds in Section for are for the expected *absolute* generalization error, where the extra term $O(1/\sqrt{n})$ is hard to avoid (or unavoidable in many cases). In Section 5, the bounds are for the expected generalization error instead, where the standard bounds (e.g. from [7]) already achieve a zero generalization error with this set-up. - Why are the bound using chaining useful? The paper basically uses the same techniques as [17] with their "decorrelation lemma". In [16,17] they come up with a slightly artificial example to showcase why their results are useful when compared to previous bounds. It is unclear if this technique provides any practical advantage to previous results, either in terms of obtaining bounds with a better rate in certain settings, in terms of interpreting the resulting bounds, or even in terms of simplicity to obtain actually computable bounds. The paper does not discuss some relevant literature in certain parts of the text: - In line 102 they state that they "define the conditional divergence [...]". This is a standard notation for the conditional divergence, sometimes credited to Verdú, although I am unsure which is the origin. Probably this is just a writing thing, but it contrasts with the previous introduction of the relative entropy where they introduce it with "[...] is defined as". - Even though the techniques employed are different, some mention to [A] would be interesting in the introduction and/or in the preliminaries. In this paper, they obtain PAC-Bayes bounds considering Orlicz norms with general Orlicz function, not necessarily $\exp(x^p) - 1$. - In Section 5, it would be interesting to compare and/or mention other works that deal with the couplings of the posterior and the prior to bound the generalization error, e.g. [B,C,D]. In [C], for instance, they also mention the relationship of these bounds with chaining in Appendix A and with the relative entropy and subgaussian conditions in Appendix B. - In Section 7, it would be good to compare and discuss the work in [E] regarding chained generalization error bounds. **Additional References** [A] Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa. "Generalization Error Bounds Via Rényi, f-Divergences and Maximal Leakage". IEEE Transactions on Information Theory. 2021. [B] Hao Wang, Mario Diaz, José Cândido S. Santos Filho, and Flavio P. Calmon. "An Information-Theoretic View of Generalization via Wasserstein Distance". IEEE ISIT. 2019. [C] Borja Rodríguez-Gálvez, Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. "Tighter Expected Generalization Error Bounds via Wasserstein Distance". NeurIPS. 2021. [D] Ron Amit, Baruch Epstein, Shay Moran, and Ron Meir. "Integral Probability Metrics PAC-Bayes Bounds". NeurIPS. 2022. [E] Eugenio Clerico, Amitis Shidani, George Deligiannidis, and Arnaud Doucet. "Chained Generalisation Bounds". COLT. 2022.

Questions

- I believe in the equations after line 379 there is an $f$ missing in the last equality. - I don't really follow the set of inequalities after line 381. Could you please clarify it? - Can (how does) this framework incorporate other advances in generalization error bounds based on mutual information like the single sample bounds from [8], [F], [G] or the data-dependent bounds from [H], [12], [F]? - How can we interpret the provided bounds? Can new results be obtained from them other than recovering the standard relative entropy-based bounds? Could you give some examples where the abstraction to Orlicz norms is beneficial to the analysis? **Additional References** [F] Borja Rodríguez-Gálvez, Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. "On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm". ITW. 2020. [G] Ruida Zhou, Chao Tian, and Tie Liu. "Individually Conditional Individual Mutual Information Bound on Generalization Error". IEEE Transactions on Information Theory. 2022. [H] Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. "Information-theoretic generalization bounds for SGLD via data-dependent estimates". NeurIPS. 2019.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The limitations of the paper are not generally pointed out in the paper (e.g. some of the questions and weaknesses above are not discussed such as how the extension to Orlicz spaces gives any advantage to the standard relative entropy and the decoupling lemma using Donsker-Vardhan). Regarding potential negative societal impact, there is no mention but there is no need to be as this is theoretical, fundamental research.

Summary

The paper presents a unified perspective of information-theoretic generalization bounds through decorrelation and coupling/chaining. Various existing generalization bounds in the literature are recovered or generalized via this perspective. The Fernique-Talagrand upper bound on the expected supremum of subgaussian processes also emerge as a special case from this framework.

Strengths

I did not check carefully the proofs in the supplementary materials, but the presented results look sound to this reviewer. The paper offers a good service to the learning theory community for understanding information-theoretic generalization bounds and key techniques therein for their development. The development in this paper is original, to this reviewer. The paper is also clearly written. I appreciate the authors' informal summary in section 1.1, making the paper easy to read.

Weaknesses

On the minor side, the work appears to be limited only to unification, without aiming at developing novel and/or tighter bounds using the developed tool, despite that some bounds are stated in more general forms (e.g., Theorem 7) and some are shown to have certain improvement (e.g. Theorem 3). It would be much better appreciated if the authors can further demonstrate the power of their framework by presenting novel bounds of greater significance.

Questions

In the discussion after Theorem 3, the authors demonstrated the advantage of the theorem in the trivial case where W and S are independent. Are there more interesting (i.e. less trivial) cases where such an advantage can be demonstrated?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See weakness.

Summary

This paper proposes a unified framework for deriving information-theoretic generalization bounds for learning algorithms. The main technical result relies on a probabilistic decorrelation lemma based on a change of measure and Young’s inequality in $L_{\psi_p}$ Orlicz spaces. Combining it with other techniques, such as summarization, couplings, and changing the space of probability measures, new upper bounds on the generalization error can be obtained both in expectation and in high probability. The proposed framework also recovers many of the existing generalization bounds as special cases, including the ones based on mutual information, conditional mutual information, stochastic chaining, and PAC-Bayes inequalities. Strength: Lemma 1 provides a very general way to derive generalization error bounds in multiple setting, and it recovers many existing results as special case.

Strengths

The decorrelation Lemma 1 provides a very general way to derive generalization error bounds in multiple settings, and it recovers many existing results as a special case.

Weaknesses

As the proposed bounds are not based on standard information measures, is there a way to evaluate these quantities even in some illustrative examples, like the mean estimation problem considered in [8] and [17]?

Questions

Could the proposed framework recover the ICIMI bounds obtained in the following paper? In general, is it compatible with the individual sample technique used in [8] and [12]? Zhou, Ruida, Chao Tian, and Tie Liu. "Individually conditional individual mutual information bound on generalization error." IEEE Transactions on Information Theory 68, no. 5 (2022): 3304-3316.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The limitation has been addressed well in the confusion section.

Thank you for the response.

I am keeping my rating.

Answer to rebuttal

Thank you for your rebuttals (both the individual one and the general one). Let me expand further on some things that remain unclear to me. 1. You mention that the decorrelation lemma allows you to work with the tails of the Radon-Nikodym instead of various expected values, such as the relative entropy. It is true that $D(\mu \Vert \nu) = \mathbb{E}\_\mu \log \frac{d\mu}{d\nu}$, but you also deal with $\mathbb{E}\_\mu f \psi\_p^{-1} \frac{d\mu}{d\nu}$. Hence, I do not agree with that statement. 2. Continuing with the point above, I agree that working with an Orlitz norm gives you more generality than working with the relative entropy and that a better understanding of the tail of $\frac{d\mu}{d\nu}$ can be gained in certain situations. However, I am still missing some examples of this. Could you give some example of some "common" tail behavior where the abstraction to an Orlitz norm provides some advantage? I believe this would improve the paper substantially. 3. Regarding the couplings. I like this interpretation, I believe it should be mentioned in the paper to give some intuition. I still do not see there is a practical benefit on its own, but I like it conceptually. Also, I enjoyed that you can use it together with chaining to obtain Wasserstein-2 based bounds without a Lipschitz assumption. Could that be done without the need of chaining? * I still believe that in Section 5 it should be acknowledged that the fact that bounds that go to 0 can be obtained is not from the fact that one is using couplings, but to the fact that one is bounding the generalization error instead of the absolute generalization error. 4. Regarding chaining. Again, I like the bound presented in the general rebuttal, it is conceptually nice. I understand that the successive refinements will make the bound not to go to infinity in certain situations. Also, I appreciate Dudley's metric entropy to bound the suprema of processes. \ However, we have applications of the metric entropy to real scenarios. For instance, we can study the Wasserstein concentration of the empirical measure to the true measure, and obtain a true rate of $\mathcal{O}(1 / \sqrt{n})$. On the other hand, I do not see how this can be used for the generalization error of a learning algorithm. The examples given in [16,17] are quite artificial. Could you give some example where we can see some application of this bound to a learning problem?

Thank you for the response.

I believe the paper will benefit from discussing some simpler examples, and I will keep my score.