Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: PAC-Bayes generalization bounds are often derived from Donsker Varadhan, allowing one to bound a function g that depends on the empirical risk and risk of the predictor. Choosing different forms of g gives rise to different bounds, that may be tighter or loser depending on the regime (often empirical risk magnitude). When it comes to information theoretic bounds, these bounds often come in the most “basic” form, that is comparable to taking g to be of a form of risk - empirical risk. Part of the contribution of the paper is deriving a diverse set of bounds that depend on information-theoretic quantities, similarly as it’s been done in PAC-Bayes setting. The authors present both, bounds that hold in expectations, and high probability bounds.
strengths_and_weaknesses: The connection between PAC-Bayesian bounds and information theoretic ones is one that is, by now, well understood. Indeed, Catoni's 2004 manuscript already spells out the relationship, but it's one that occasionally needs to be rediscovered or reiterated in the literature when we have our heads down and we forget to exploit this connection.

Is this work sufficiently novel/technical? The basic techniques for simultaneously deriving high probability and expected generalization bounds in the PAC-bayesian/info-theory setting have been provided, for example, in Hellstrom and Durisi (who the authors cite) and expanded recently by Grunwald, Steinke, and Zakyinthinou. And the MGF bounds for different g functions follow fairly trivially from Lemma 1, which itself appears in various forms in a number of papers (including Lever et al 2012 and some other works by Shawe-Taylor) used to derive basically any PAC-Bayes bound (just an expectation version of it). 

Still, somehow the work on mutual information bounds has never gone beyond linear comparisons of the risk and empirical risk (leading to bounds on expected generalization error). The bounds displayed here for the case where empirical risk is zero are particularly interesting in my opinion, as similar bounds have been derived recently, but not from this perspective. And so I think in fact we had lost sight a bit about the role of a jointly convex comparator and it will be a useful observation for this subcommunity to reacquaint themselves with.

While the idea of combining these old insights from PAC-Bayes to mutual information bounds seems now obvious, the form of the resulting bounds (e.g., Theorem 4) is not what I expected, and so there seem to be some surprising consequences.
questions: The comment under Theorem 8 says that the “resulting bounds essentially recover previously established generalization guarantees”. Are these previously established guarantees optimal? Are there lower bounds? What does “recover” here mean? Is the rate wrt the number of samples optimal in the minimax sense?

Numerical results (Section 6): 
- the authors do not really explain what they hope to gain by performing the empirical evaluations, and what questions they are answering. It seems that the motivation is evaluating the numerical tightness of the bounds. Is that right? It would have been nice to extend the evaluation in a few dimensions, beyond varying the number of training epochs and the number of training points. I encourage the authors to check out a paper by Dziugaite et al ("In search of robust measures of generalization") and proposed evaluation frameworks. How do the bounds vary as the depth changes? Width? As the learning rates vary? 
- What insight would we gain from the bounds if they are tight in the cases tested? What insight into generalization in deep learning in general do evaluated CMI bounds provide?
- I wanted to confirm that the bounds for SGD (Adam) are for unperturbed-in-any-way classifiers, given that evaluated CMI is used. How was the averaging over draws of the data been done?

Other comments:

 - line 27 missing Neu et al COLT ’21, and Haghifam et al ’20 reference;

- Line 39: sounds like the measures are overfitting… but in any case, overfitting is a loaded word and here the authors should choose a different word precisely describing what they mean, in my opinion
- Eq. 25 bottom line, in P_{lambda | \tilde{Z}S} is it supposed to be  \tilde{Z}_S?
limitations: There is no explicit discussion of limitations. The assumptions are stated, though, but it might be good to add a short paragraph on the main assumptions that most theorems use, and that could be relaxed in future work.
review_title: null

final_score: 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.
review_content: summary: This paper presents a new family of information-theoretic generalization bounds in terms of the disintegrated, sample-wise, evaluated conditional mutual information (CMI), an information measure that depends on the losses incurred by the selected hypothesis rather than on the hypothesis itself. The authors demonstrate the generality of this framework by recovering and extending previously known information-theoretic bounds. In some scenarios, this novel bound results in a tighter characterization of the population loss of deep neural networks than previous bounds.

strengths_and_weaknesses: This paper tightens existing information-theoretic generalization error bound using a simple but effective idea, i.e., the information measure involves the losses incurred by the selected hypothesis is always smaller than that of the hypothesis itself. Remark 1 clearly states this benefit using data processing inequality. Although a similar idea of using f-CMI has been adopted in [15], such an improvement significantly enlarges the usage of information-theoretic generalization error bound as it can be evaluated numerically for deep neural networks, as shown in Sections 5 and 6.

The paper is well-written and technically sound to me.
questions: I am curious if the proposed e-CMI bound could provide a tight characterization of the generalization for the Gaussian mean estimation example considered in section IV-A of [10]? If it works, it would be a good example for readers to compare different types of bounds and understand the idea.

I have one minor comment about the organization. The high-probability bound in section 3 seems to be standard in this type of analysis, and the usage of e-CMI is more critical here. Maybe the Gaussian example and the current Section 4 (Appendix B.3) should be highlighted?

--------------------------------
Post rebuttal:
The explanation of the Gaussian example resolves my concern. It is a nice paper. I will keep my score unchanged.



limitations: I think the authors fully addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: 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.
review_content: summary: This paper derives new information-theoretic generalization bounds based on sample-wise evaluated CMI, among which the square-root bound and the linear bound are tighter than existing bounds, and the binary KL bound is empirically shown to be superior for low-training loss settings. Furthermore, they also show that the derived bounds can be used to recover generalization bounds for multiclass classification with finite Natarajan dimension.
strengths_and_weaknesses: Strengths:
This paper is rich, presenting a series of results both novel and deep. The presentation is complete in the sense that discussions on the comparison of the bounds and the corresponding numerical demonstration are included.

Weaknesses:
The notation is heavy, which is necessary, but makes it a bit hard to follow all the results. Maybe adding a table that concludes the derived bounds in Section 5 will make the comparison part more clear.
questions: 1. How tight are the bounds in Theorem 8? Is it possible to have some plots demonstrating how much the improvement is?
2. It may be worth mentioning in previous sections that some terms in the derived bounds will later be shown to have upper bounds in Section 4.
limitations: The assumptions made for the theorems to hold are stated clearly.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper considers the problem of providing generalization bounds based on the information-theoretic measures. In particular, this paper is on extending and improving the work by Steinke-Zakynthinou and Harutyunyan et al. One line of work in this area is on proving generalization bounds based on “sample-wise” measures, initiated by Bu et al. The main contribution of this work is proving new generalization bounds by combining the idea of evaluated CMI and sample-wise generalization bounds. The authors also provide some generalization bounds based on “disintegrated mutual information” formalized by Negrea et al. One generalization bound which is new in this line of work is the binary KL bounds in Section 2.3. Furthermore, the authors provide some numerical results showing that their bounds are not vacuous in DL settings. 


strengths_and_weaknesses: The most interesting aspect of the paper is providing a generic tool in Lemma 1 which can be used to redervie existing bounds, and proving new results. Also, the results on the binary KL bounds are completely novel, and have not been reported before.

My main concern about this paper is novelty. It seems the authors combine, in a straightforward way, a line of work by Steinke-Zakynthinou, Harutyunyan et al., and Bu et al. Also, in terms of technical novelty, I found the proof of Lemma 1 straightforward. I would like the authors to clarify on the novelty of their work.

-How can we compare the high probability bounds in Section 3 with the results of Grünwald-Steinke-Zakynthinou, Hellström-Durisi? Are the bounds in the paper tighter?

-Is the result in Theorem 8 minmax optimal?  

-I would like to raise a general concern regarding the numerical results. In general, in learning theory we use the generalization frameworks to gain new insights regarding the algorithms. For instance, the existing results for generalization of SGD show that the size of the weights can determine the generalization performance; for SGLD, we know the covariance of the training samples’ gradients affects the generalization, etc. I would like to compare this approach with the case that we are “only” interested in the “value” of the generalization error. In the former case, we often use the validation set, and the numbers we report can accurately estimate the test error. First question is what can we learn about your numerical results? From the experiment details, I think you need the holdout samples to estimate the mutual information.  If you use the holdout samples to estimate the test error, what would be the results? In general, what is the gain of using your bounds compared to the validation set approach? 

questions: I have raised some concerns and asked several questions in the Strengths And Weaknesses part.
limitations: I could not find any section on the potential limitations in the paper.
review_title: null

Meta-review: metareview: This paper presents a novel sequence of results providing generalization bounds for multi-class classification within PAC-Bayesian framework. These results extend and improve some of the existing bounds. Under some assumptions, these results give a tighter bound for multi-class classification with deep neural networks than previously existing results.

These results are of interest to theoretical ML community and a valuable contribution to the conference.
confidence: Certain
Decision: Accept