Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies information-based generalization bounds and derive several improved versions of existing generalization bounds using mutual information. The paper suggests a function-based conditional mutual information in order to tighten the existing generalization bounds and discusses some numerical results to support the shown generalization bounds.
main_review: This work uses an information-theoretic approach to analyze the generalization properties of neural network classifiers. The work uses the mutual information between observed data and model parameters to bound the generalization error and then proves several variants of the existing information-based bounds through the application of conditional mutual information and function-based mutual information measures that focus on the classifier's output instead of the input samples. 

In general, the paper tries to address an important problem in learning theory on the generalization properties of overparameterized deep neural networks. The paper's analysis seems to improve the existing mutual information-based generalization bounds. However, I am not completely sure how to estimate the bounds from real data because the paper has no guarantees that the estimation error for the information measures is bounded. In addition, the paper contains many theoretical statements, which makes it hard for a reader to focus on and understand the paper's main contribution.

To further explain the comments above, my main concern with this work is how to evaluate the generalization bounds for standard datasets and deep neural network classifiers. The generalization bounds include conditional mutual information terms which are hard to evaluate from real data in practical settings. Also, the upper bound in Corollary 2 includes n mutual information terms where for every term we have only one observed sample. Therefore, it is not clear how one should estimate every mutual information term from only one sample.

In addition to the estimation of information measures, the current paper includes too many theoretical statements that makes it hard to distinguish the paper's main contribution from the existing results in the literature. I highly suggest removing the less important results from the main text and further explaining how the generalization bounds in this work can be more useful than existing information-based generalization bounds. The current draft seems to only suggest that the new bounds rely on conditional information measures, while this new feature may not be that useful in practice because the conditional information measures are statistically unaffordable to estimate.
limitations_and_societal_impact: Please refer to my comments in the main review.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper continues a line of work which develops information-theoretic bounds on the generalization gap (i.e. the difference between e,pirical and population loss) in supervised learning.
Its main contributions are:
1. the authors introduce a natural “transductive” variant of the conditional mutual information bound (Section 3) and show that it is stronger than all previous bound. (Eg one can use it to prove that any proper learner for a VC class generalizes).
2. The authors quantitatively improve some of the previous bounds on input-output mutual information (theorem 2.2, 2.3), and on conditional mutual information (Theorem 2.6), by moving the expectation outside the square-root in the RHS of the inequality.

main_review: Overall I liked this paper: I think it the transductive variant of the recently-well-studied conditional mutual information is natural, simple, and they show that this variant is in fact stronger. 
Moreover, they also derive quantitative improvements over the previous bounds. 

Some specific comments and questions to the authors:
1. I was not very convinced by the motivation using deep learning. The main reason is because the bounds studied in this paper imply that the empirical and population losses are close, and perhaps the greatest mystery DNN demonstrate is that they generalize, however they do not necessarily satisfy this property.
2. I would appreciate if the authors can elaborate more on their quantitative improvement over previous bound (by moving the expectation outside the square-root). Are there concrete, natural examples where it gives better bounds? How complicated is this improvement comparing to the previous (weaker) derivations?
3. In Theorem 4.1, please add that the learning algorithm is proper. Otherwise the statements seems false.
4. Can you please elaborate on the application wrt to ensemble methods? In which ways is it better than previous bounds?

limitations_and_societal_impact: I don't see any potential negative social impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper derives information-theoretic bounds for learning algorithms. The bounds are based on the predictions of the learned model, rather than the weights (output), which makes them tighter by the data-processing inequality and can yield non-vacuous bounds in cases where weight-based mutual information bounds are vacuous. The authors validate the analysis with a few experiments. 
main_review: The paper derives information-theoretic bounds for learning algorithms. The bounds are based on the predictions of the learned model, rather than the weights (output), which makes them tighter by the data-processing inequality and can yield non-vacuous bounds in cases where weight-based mutual information bounds are vacuous.  The new bounds build upon the earlier works of Xu & Raginsky (2017) and the more recent work of Steinke & Zakynthinou (2020) using the notion of the conditional mutual information (CMI). 

First, the authors present a theorem that generalizes a bound of  Xu & Raginsky (2017) (Theorem 2.2 in the paper) in which the mutual information is measured between the weights W and the full dataset S. Theorem 2.2 uses a subset of S. However, I don't see how this theorem is different from Theorem 2.1 since taking a proper subset of a training set (i.e. for any fixed choice of u in the theorem), the distribution of S_u is the same as the distribution of a training sample of size m drawn iid. Would you please clarify why Eq 5 is not equivalent to Eq 4?

The authors then discuss the choice of the subset size m. They argue that having a smaller m yields a tighter bound. However, there is an early work that makes the same argument and is not discussed in the paper. In Alabdulmohsin (2015),  m=1 is used to derive non-vacuous bounds and it is shown that those bounds were tight (see for instance [1] and the subsequent works summarized in [2]). Note that the difference between using the weights and using the function itself (decision boundary) was discussed there as well using data-processing. Since this is an earlier work that makes the same argument, it should be discussed. 

The main contribution of this work is Theorem 3.1, in which the authors introduce the notion of functional CMI. It is analogous to the notion of CMI introduced by Steinke & Zakynthinou (2020) but uses the predictions rather than the weights (output). One interesting difference is on the connections between mutual information and the VC dimension. Earlier works (e.g. Alabdulmohsin (2018) and Steinke & Zakynthinou (2020)) prove that an ERM *exists* in a VC class that has a small mutual information between the weights and the data. Using functional CMI, the authors show that all functions in a VC class have a finite f-CMI, which is a neat result. The difference here is that by looking at the predictions, they rule out cases in which the data is encoded in the weights without impacting the decision boundary significantly. 

The authors then discuss some implications. For example, they look into the case of ensemble learning and show that the f-CMI of an ensemble can be bounded using the f-CMI of the base models. However, this argument is not really useful because it does not explain why an ensemble method tends to generalize better. The bound for the ensemble is larger than the bound of any base classifier. 

Finally, the authors validate the analysis with a few experiments. The authors argue that the f-CMI bound "closely tracks" the generalization gap but this is misleading because the difference is one order of magnitude and the fact it is decreasing with increasing sample size does not make it "tracking" the generalization gap. After all, all useful generalization bounds decrease with increasing sample size. I suggest that the authors rephrase that claim (perhaps by only arguing that the bound is non-vacuous). Also, in Line 319, the statement is false because weight-based mutual information bounds need not be vacuous (e.g. when m=1 as discussed earlier). Yes, they can be vacuous but need not be. 

One minor comment. In Lines 128 and 129, I think there is a typo. Shouldn't "n" be "2n"? 

Overall, the paper is well-written and brings together several recent works. The only comment I have is that there is a related line of work missing in the discussion. As mentioned above, Alabdulmohsin (2015) was an early work that proposed measuring the mutual information with a subset of size m=1 and showed that it was tight (in a certain sense). Based on that, a bound similar to Theorem 2.1 was derived for bounded losses and an equivalence relation was established with the VC dimension, which is similar to the works discussed in Section 4.2, in addition to concentration bounds. These are summarized in [2]. They should be included in the related works for completeness.

[1] Alabdulmohsin, "Algorithmic stability and uniform generalization." NeurIPS (2015).

[2] Alabdulmohsin, "Towards a Unified Theory of Learning and Information." Entropy 22.4 (2020): 438.

======== 

Post-rebuttal:

I have read the authors' response and I intend to keep my score as is. I find this paper a worthwhile contribution overall.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors build upon recent literature on information theoretic bounds on generalization error and specifically the conditional mutual information bound by Steinke and Zakynthinou [28]. They propose an improved bound that is tigther than [28] and easier to compute in practice. It is achieved by replacing the weight-parameter vector in the mutual information expression of [28] with a prediction function evaluated on a subset of in-sample (training) data and a subset of out-of-sample data.  This enables the authors to give performance guarantees on deterministic training algorithms. Several toy examples and experimental results are presented to illustrate the advantages of the improved generalization bound.
main_review: The proposed bound involving mutual information between the sample index variables and prediction function involving the first n samples is interesting and has practical advantages. However the proof seems to follow prior works and builds upon Lemma 1. Can the authors explain what aspects are non-trivial in the derivation of the new bound? 

Can the authors comment on how the result in Thm. 4.2 compares with other generalization results on deterministic algorithms n the literature? 

In the experimental section I was wondering why the authors did not compare their bound with bounds other than Negrea et al.? There are other state of the art bounds (such as the work of Haghifam et al) that are better than Negrea et al. for SGLD.  Are there difficulties in comparing with these works?
limitations_and_societal_impact: The authors have not listed societal impact. Limitations have been discussed.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes new information-theoretic generalization bounds. These bounds extend some existing results and seem easier to compute. The authors also demonstrate their bounds through some applications and experiments.
main_review: Strengths:
Using the information-theoretic framework, introduced by Xu and Raginsky, for studying the generalization error is interesting.

The new generalization bounds in Section 3 seem easier to compute compared with existing mutual-information-based generalization bounds. 

The experimental results seem to suggest that the new bounds in this paper are promising. 

Weaknesses:

My main concern of this paper is its novelty and unclear comparison with existing literature. 

1. The comparison with existing literature is unclear. For example, in the abstract, the authors claimed that their bounds improve over the existing information-theoretic bounds since (a) they give meaningful results for deterministic algorithms and (b) they are significantly easier to estimate. In the second paragraph of the paper, the authors echoed their claim and provided some references. However, it seems that many existing papers have already contributed to the above two challenges. In fact, the generalization bounds in [4,28] are applicable to deterministic algorithms, and the bounds in [11,19,20] seem easy to compute as well. There are some missing references that also contribute to these two directions. Hence, I recommend the author revise their introduction and clarify their contributions.

2. The authors provided a generalization bound in Theorem 2.2 and stated that this bound matches the result of Bu et al. [4] when m=1. Then authors proved that this bound is non-decreasing in m. Hence, if I understand correctly, Bu et al. have already derived the tightest case. Then what is the purpose of introducing other weaker bounds? In the same vein, bounds with similar forms have already appeared before. For example, Raginsky has presented a similar result in a tutorial at NASIT 2019 (see the recorded video at https://www.itsoc.org/conferences/schools/nasit2019 1:25:05). Negrea et al introduced a similar bound. Although their bound is slightly weaker than Thm 2.2. in this paper, it does not seem that the improvement is significant. 

Similar comments also apply to some bounds in Section 2.2.

3. Section 3. The authors considered a different framework where they assumed that the learning method implements a function f: Z^n \times X \times R \to K. This framework has been considered in the following missing reference for studying excess risk. Hence, it seems that the authors just applied the existing bounds introduced in [28] to this new framework.

Xu, A. and Raginsky, M., 2020. Minimum excess risk in Bayesian learning. arXiv preprint arXiv:2012.14868.

My second concern is the experiments in this paper. 
1. The authors compared their bound with the one in Negrea et al [19] in Fig 1 (b). For the first 12 epochs, the bound in Negrea et al [19] outperforms the bound in this paper. Given that the SGLD algorithm converges in 16 epochs, it seems that the new bound introduced in this paper is often weaker than the bound in Negrea et al [19] before the algorithm converges. 

2. The bound in Negrea et al [19] blows up after the algorithm convergences and that’s the region where the bound in this paper is sharper. However, a follow-up work [11] has already proposed a new generalization bound which seems to address this issue and becomes much tighter. This bound is extended to the setting of SGLD in the following missing reference. Hence, I wonder how the generalization bound in this paper compares with these new bounds. 

Rodríguez-Gálvez, B., Bassi, G., Thobaben, R. and Skoglund, M., 2021, April. On random subset generalization error bounds and the stochastic gradient Langevin dynamics algorithm. In 2020 IEEE Information Theory Workshop (ITW) (pp. 1-5). IEEE.

3. The generalization bound in this paper is decreasing w.r.t. the number of epochs in Fig. 1. However, it seems that the true generalization gap is increasing which is captured by the bound in Negrea et al [19]. How can you interpret this phenomenon?

Other comments

The generalization bounds in Eq.(29). It is unclear to me why the second term has a $n$ inside the square root. How to explain this dependence? Does that suggest that the generalization gap is increasing w.r.t. the sample size. Also, how does this bound compare with other existing stability bounds?

The authors provided some high-probability bounds (e.g., Eq. 3 and Line 88) in the paper. I wonder how they compare with the one in [34]. It seems that using the “monitor technique” can lead to a tighter bound compared with the bound obtained from Markov’s inequality. Also, how do these high-probability bounds compare with the ones in the following reference?
Esposito, A.R., Gastpar, M. and Issa, I., 2021. Generalization error bounds via Rényi-, f-Divergences and Maximal Leakage. IEEE Transactions on Information Theory.

Line 112—113. The authors wrote “While these bounds are worse than the corresponding bounds of Thm. 2.2, it is sometimes easier to manipulate them analytically.” This is unclear to me. Can the authors elaborate more?
limitations_and_societal_impact: See my above comments.
review_title: null

Meta-review: The paper continues a line of work which develops information-theoretic bounds on the generalization gap (i.e. the difference between e,pirical and population loss) in supervised learning. Almost all reviewers were favorable for acceptance, and found the results innovative.


Please address reviewers comments in the final version.
Decision: Accept (Poster)