Venue: NeurIPS 2022 Conference

Reviews:

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 presents a new leave-one-out conditional mutual information method to bound generalization risk. Specifically, two information theoretic generalization upper bounds, namely loo-CMI and floo-CMI, are proposed. The authors claim compared to standard CMI, the proposed bounds are more cost-effective because they reduce the computing cost from 2^N to only N. Strong theoretical analysis are provided. In addition, some empirical results have been reported in image-classification problem. 
strengths_and_weaknesses: Strengths:
1.	The authors proposed the novel information generalization bounds. 
2.	The theoretical analysis is sound, and it shows the bounds have good properties.


Weakness:
1.	The authors should compare their methods to competing baselines. For example, the f-CMI bound from paper [1]. Moreover, the author should provide the results for more complex datasets, such as ImageNet.
2.	In Figure3, the authors should plot training errors+ proposed generalization bounds, do they dominate the test error? In addition, the stability analysis is missing. And the authors should repeat the experiments and report the error bar to show the variance of the bounds in Figure 2&3.
3.	The authors need to demonstrate their methods actually works in empirical settings. More concretely, the author should apply their methods on a set of different models trained on the same real-word dataset and show the predicted generalization bounds are consistent with the actual test error. 

[1] Harutyunyan, Hrayr, et al. "Information-theoretic generalization bounds for black-box learning algorithms." Advances in Neural Information Processing Systems 34 (2021): 24670-24682.

questions: 1. Can these bounds be used for model training? Or they only can be used to do model selection.
How costly does it take to compute the bounds?

2. It is puzzling that the results in Table 1 all have training error to be 0. Do they imply the models have overfitted the data?

limitations: My major concern is the utility of the methods, since the authors do not show any actual applications of their bounds to facilitate the real-world machine learning practices.
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 argues that standard conditional mutual information (CMI) bounds are difficult to compute and interpret. Inspired by the spirit of leave-one-out cross-validation, the authors present a computable and interpretable bound termed loo-CMI. In particular, the proposed loo-CMI assumes that a generalized algorithm should not be affected by a small perturbation (i.e., leaving one training sample out at random). Furthermore, they interpret their bound in the function space, which leads to a tighter bound (i.e., floo-CMI). Empirically, they evaluate the quality of the bound and provide sufficient analysis.
strengths_and_weaknesses: This idea is intrigued by an intuitive assumption that a generalized algorithm should not be affected by a small perturbation. The authors do a good job of motivating this work, and the proposed bounds (i.e., loo-CMI and floo-CMI) are simple but reasonable. Also, the paper is very well written and easy to understand.

My main doubts/concerns regarding the paper are the following:

- In Fig 2 and 3, there is a big difference between the main paper and supplementary material. Does it mean that the previous empirical results suffer from high randomness when the number of samples is small? Did the authors do ablation studies on ``the number of samples'', especially for the larger number?
- While the analysis of the dataset size during fine-tuning is interesting, I believe the pre-training dataset plays a more crucial role in determining the generalization ability of deep models. Can the authors compare their results on different pre-training dataset scales?

Minor:

- The code should mention the key lines corresponding to loo-CMI and floo-CMI.
- The Conclusion section needs to be added.
questions: 1. Does the small number of samples result in high randomness of the previous empirical results? Did the authors do ablation studies on ``the number of samples'', especially for the larger number?
2. How does the pre-training dataset size influence the quality of the proposed bounds?
limitations: Yes, the authors have addressed the societal impact of their work.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper considers conditional mutual information based generalisation bounds for understanding the generalisation properties of neural networks. It builds on techniques introduced by prior work and overcomes a practical limitation: prior work requires computations that grow exponentially in dataset size, while the proposal entails only linear growth in dataset size.
strengths_and_weaknesses: The paper is very well written. I am not an expert in this area (hence also low confidence in my review) but the paper was a pleasure to read. 

The paper is contributing to understanding generalisation in deep neural networks. This is one of the most important problems in the ML community today, and I welcome and support work towards this.

Since I am not an expert, I cannot fully evaluate the novelty of the work. However, if the authors are correct in their description of the current state of the field, I believe their results are very impactful. 

Nonetheless, I have a few comments and things that i think could improve the paper:



- please use the actual submission template with line numbers, it makes it much easier to review
- typo page 2, paragraph 2, line 3: our loo-CMI only needS to 
- theorem 4.1: I didn't understand what U' brings. In equation 16, doesn't the independence of U' mean that  p_{w|zn, u'} = p_{w|zn} ? Or do you mean "independent" in the sense of "another" or "duplicate" rather than the statistical sense?
- could you comment on the computational requirements of this method? You need to train N models, one for each datum right? This must be very slow for reasonably sized datasets. 
- One idea for evaluating your method on larger datasets: practitioners sometimes fine-tune just the last layer of a DNN, rather than the whole network. If you precompute features of the data up to this last layer, this is like training a linear classifier. This could enable you to try out your method on larger datasets.
questions: See above
limitations: See above
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Several generalization bounds have been derived in the literature for machine learning models using some notion of mutual information. These differ in how to measure the mutual information (e.g. whether it is between the hypothesis and the entire sample S or a subset of it) and whether or not the mutual information is conditional on other random variables and so on. In this work, the authors present yet another approach in which a single example is removed from the training set. The authors argue that the primary advantages of this approach are that it can be computed in O(n) time (since there are n examples to remove from) and that it is non-vacuous. They further show that measuring the mutual information between the predictions of the model and the data also yields similar bounds, which are tighter by the data processing inequality. Finally, the authors relate such bounds to stability and flatness. 
strengths_and_weaknesses: *Strengths*:

1- The paper introduces a new approach for analyzing the generalization gap that can be useful to the community. 

2-  The authors connect it nicely to related concepts, such as stability and flatness. 

*Weaknesses*:

1- There are no tightness results. In fact, the bounds seem to be vacuous in most settings. 

2- The SGD bound is odd because the bound increases with the number of SGD steps T, when a reasonable bound should be decreasing with T. 

**Details**

The paper introduces a new information-theoretic approach for bounding the generalization gap of machine learning models. The paper is well-written and I think it offers great insight. For example, it suggests a new approach for quantifying flatness of the local minima that does not suffer from pitfalls observed in prior works (e.g. that one can arbitrarily change it via re-parameterization without changing the decision boundary). I think it would strengthen the paper to apply this measure of flatness on techniques that arguably improve flatness (e.g. by comparing it for neural networks trained with or without skip connections, SAM optimizer [1] or by applying it to methods trained via reinitialization [2, 5]). 

On the downside, the authors emphasize that their approach yields non-vacuous bounds. However, the form of the bounds in Corollary 4.1 does not really support that argument. If the quadratic term in the exponent is bounded away from zero by a small epsilon, the entire bound is O(log n), which is vacuous for large training sets. For SGD, it seems strange to me that the bound increases with T, when it should decrease. 

In the experiments, the authors use small datasets with a few thousand training examples. At minimum, the authors should show that larger training sets yield better bounds as they should given the interpretation in terms of stability. For example, they can train on subsets of the data and report results as the subset size increases. Also, the authors use pretrained models and fine-tune for a few epochs. These are (by nature) stable since pretraining improves stability. I think the authors should include experiments without pretraining to show that they still obtain useful (non-vacuous) bounds. The reason I am emphasizing on this is that this has been a main motivation throughout the paper so it should be demonstrated experimentally. 

Overall, I still think the paper is worthwhile and I hope that the authors would address the issues above in the experiments to make their argument more convincing. 

Some minor comments:

1- The technique of introducing noise to control the bound has been used in PAC-Bayes methods and it has been connected to flatness as well. See for example [3] and [6].  Perhaps, this should be mentioned in the related works. It would be useful to include some of those bounds in the comparison. 

2- In Section 5, the authors claim that the earliest works were published in 2016. There are earlier works that derive non-vacuous generalization bounds with tightness results (see for instance [4]), in which the mutual information is measured between the hypothesis h and a single training example. In the latter case, the bounds are non-degenerate even for deterministic algorithms with uncountable hypothesis spaces. It has also been connected to stability, like in the present work.

3- Typo in Definition 4.2: "we say that $\beta_1$ test stability if". 

[1] Foret, P., Kleiner, A., Mobahi, H. and Neyshabur, B. "Sharpness-aware minimization for efficiently improving generalization." ICLR, 2021. 

[2] Alabdulmohsin, I., Maennel, H., & Keysers, D. (2021). The impact of reinitialization on generalization in convolutional neural networks. arXiv preprint arXiv:2109.00267.

[3] Neyshabur, B., Bhojanapalli, S., McAllester, D. and Srebro, N., "Exploring generalization in deep learning." NeurIPS, 2017.

[4] Alabdulmohsin, I. "Algorithmic stability and uniform generalization." NeurIPS, 2015.

[5] Zaidi, S., Berariu, T., Kim, H., Bornschein, J., Clopath, C., Teh, Y.W. and Pascanu, R., 2022. When Does Re-initialization Work?. arXiv preprint arXiv:2206.10011.

[6] Dziugaite, G.K. and Roy, D.M., 2017. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008.

questions: - Please double check the bound in Lemma 4.1 
limitations: Please see the comments above for the limitations of the work. Since this is a theoretical work, there are no societal impact as far as I can see.
review_title: null

Meta-review: metareview: The paper derives an information theoretic generalization bound based on a mutual information measure that relies on a leave-one-out procedure to reduce the cost of previous estimators. This estimator reduces the complexity from exponential ($2^N$ where $N$ is the sample size) to linear.

Overall, the general feeling among the reviewers and myself is that the paper does make a rather novel contribution, which is backed up by theoretical bounds. I think the reduction in terms of complexity from  to  is significant, but one could still argue this is not quite sufficient yet for modern tasks in machine learning, where  can be very large, so  evaluations of a large neural network can still be very costly. This aspect seems a bit hidden in the paper where the experiments are only on very small datasets. The authors do not even seem to explicitely mention the size of the datasets.

Still, I think the theoretical contribution of the paper is significant enough so I recommend acceptance but I stronlgly encourage the authors to further discuss the computational aspect.

I would like to point out two additional relevant work:

1) https://arxiv.org/pdf/2206.14800.pdf
This paper seems to develop very similar bound also using a concept of mutual information and LOO.

2) https://arxiv.org/pdf/2203.03443.pdf
This paper reduces the computational aspect of LOO, although it seems to be only applicable to kernels.
confidence: Certain
Decision: Accept