Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This work provides novel generalization bounds, which limit (in expectation) the gap between a classifier’s empirical risk, i.e. how well it performs on the training data, and population risk, i.e. how well it performs on the true distribution. Generalization bounds can be in terms of many parameters of the problem, and this paper focuses on Wasserstein distances. Specifically, it provides bounds in terms of the Wasserstein distance between the hypothesis distribution before and after a single sample (“single-letter”), before and after a random subset of the samples (“random-subset”), and before and after the full set of samples (“full-dataset”). These Wasserstein distances were studied in previous work as well, but these bounds are tighter than the predecessor bounds.

main_review: The first four main results of the paper are for single-letter and random-subset generalization bounds in the standard and randomized-subsample settings. Note that in the latter setting, twice the typical number of samples are drawn, but coin flips are used to decide which subset of those samples is actually used; the distributions considered differ in whether the results of those coin flips / the identities of the samples are known. The bounds in the standard setting are showcased by considering a particular application regarding estimating the mean of a Gaussian distribution given its covariance matrix and comparing the proposed bounds to previous Wasserstein / mutual information bounds. Since this setting is simple, the precise generalization error can be computed and is plotted as well; the new bounds are much closer to the correct generalization error than previous work.

The paper then also discusses how the results above can be made to work with backward channels instead of forward channels (e.g. how knowing the hypothesis changes the distribution over samples), as well as how they can be converted to other information measures, such as launtum information.

Overall, I think this is a thorough collection of theory results that pushes the boundaries relative to a variety of prior work. I am a bit concerned about the practicality of these results (see the Limitations and Societal Impact section), but I would still lean towards acceptance.

Miscellaneous:
- Line 3: “and their analogous in” analogous -> analogues.
- Line 153: “tighter than (1)” Took a moment for me to parse this reference, I think it would be clearer if it were more explicit e.g. Inequality (1) or perhaps Formula (1)? Similarly on line 160.
- Line 210: “impact on the samples’ identities” on -> of

-----
I have read the author's response and they have addressed my concern about there being cases where these bounds improve on practical cases, so I have adjusted my score accordingly to an accept.
limitations_and_societal_impact: The paper itself admits “The Wasserstein distance is difficult to characterize and/or estimate,” and the one application presented (Gaussian mean estimation) is already on the easy side because its generalization can directly be computed. Is there an application where these results produce the generalization bounds, even compared to non-information based techniques?
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of obtaining generalization bounds using the statistical measure of dependence between the input and output of a learning algorithm. Tha main contribution of this paper is to provide a generalization bound using the Wasserstein distance between the posterior distribution and P(W). This result is further improved by considering the single sample case where the generalization bounds are based on the Wasserstein distance P(W|Z_i) and P(W). Also the authors extend their results to the setup of Steinke and Zakynthinou ‘20. The authors specifically follow the literature of information-theoretic generalization bounds, and compare their bounds to the existing bounds in the literature. In all cases, the authors show that the bounds using Wasserstein distance are tighter than the bound using mutual information (or KL).

Also, they show for a toy example of estimating the mean of gaussian distribution their bound provides “order-wise” improvement over the mutual information bounds where the mutual information based bounds gives upper bounds on the generalization that decays as 1/sqrt(n) but the Wasserstein distance based bound gives a bound that decays as 1/n.

The authors also use the joint-range technique to provide generalization bounds based on f-divergences.


main_review: 
-The Wasserstien distance is defined using a metric. The most important shortcoming I found with the paper is that there is no discussion on how we can find an appropriate metric for the hypothesis space. I just want to emphasize that the concept of using the geometry of the hypothesis space has been used in learning theory before. For instance for VC classes this seminal work considers the VC classes:

	Haussler, David. "Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension." Journal of Combinatorial Theory, Series A 69.2 (1995): 217-232.

Later it was used for obtaining bounds on the Radmacher complexity by chaining technique. Another question is what is the impact of the algorithm on the chosen metric? Assume we have a hypothesis space and two different algorithms for learning. Do we need to choose different metrics when analyzing different algorithms for the same hypothesis space?

-The concept of chaining mutual information bounds has been considered in [13], [11], and a recent work by Asadi, Abbe where the authors propose a learning algorithm based on their chaining method. I just want to understand what are the main differences of this paper compared to those results? The aforementioned papers  also provide bounds that depend on the learning algorithm as well as the geometry of the space.

-The example of the Gaussian location model implies that in some cases the proposed bounds can give much tighter characterization of the generalization bound.  Is there any specific practical problem that your generalization bound can give new insights and analysis? Also, does this generalization bound guide us to design a new training algorithm?

-Most of the results in the paper depends on the distribution of output conditioned on a single sample, i.e., P(W|Z_i). I think in most problems it should be hard to quantify this kernel. The authors also discuss the bounds that depend on P(W|S) however those bounds are much looser. Is there any way to improve the bounds based on P(W|S)?

-Another important property of the Wasserstein distance is that it is defined based on “inf” over the coupling. However, in the paper there is no discussion on how to find a good coupling? I think the authors should also comment on this aspect.

-Theorem 2: why do you want to add extra info R? I think we can add extra information by considering a specific coupling.

-Backward channel: I could not understand what is the main idea behind considering backward channel? I think characterizing the kernel P(S|W) is a very very hard problem. How can we use this bound in practice to gain a new insight? I would appreciate it if the authors comment on why they consider the backward channel in the paper. I have looked at the appendix on the connection to the rate distortion theory, but that section is not very clear.


Some typos:
What does the word “single letter” mean in the paper? 
Line 33, there are three and in a row and it is difficult to understand the sentence.
Line 38, what is j?
Line 151: in the first sentence it seems there is a typo.


limitations_and_societal_impact: I think the limitations discussed by the authors in the paper is important. Also, I would like to add that the authors should add results regarding how we can choose a good metric and how we can find a good coupling.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work presents several expected generalization error bounds in terms of the Wasserstein distance. Several settings (full-dataset, single-letter, and random-subset) are considered in the paper. Under the assumption that the loss function is bounded and using Hamming distance in the Wasserstein distance, the proposed bounds are shown to be tighter than the existing mutual information (or KL divergence) based generalization error bound. The author also claims that serval new bounds based on a variety of information measures can be obtained using these Wasserstein distance-based bounds.


main_review: The paper is technically sound and well-written.

My major concern about this work is the novelty. The idea of bounding generalization error using Wasserstein distance is presented in [14] and [16] in the reference of the paper. And the techniques used in the paper to tighten the Wasserstein distance-based bounds are originally designed for tightening mutual information-based bounds, including single-letter characterization from [6], random-subset [9] and randomized subsample setting from [1].

However, the result obtained by combining those techniques with Wasserstein distance-based bounds is significant. Example 1 shows that the proposed method could provide an order optimal bound for the generalization error of Gaussian mean estimation problem, which seems to be the first order optimal information-theoretic bound based on my knowledge. It was shown in [6] that simply using individual mutual information I(W;Z_i) will result in a sub-optimal bound, so I would like the author to provide more explanation and discussion about this improvements. It seems that the improvement is related to the metric used in the Wasserstein distance. Also, it is the best to include more examples to demonstrate the powerfulness of the proposed bound.  

Minor comments:
1.	The results presented in section 3.3 and 3.4 are quite straight forward, and it is hard for me to see the values of those results based on the discussion in the current paper. More discussion and some potential applications of these results would be helpful. Otherwise, there is no reason to include some looser bounds in the main body of the paper.
2.	The comparison of the Wasserstein distance-based bounds presented in Appendix C should be included in the main body of the paper to demonstrate the tightness of the proposed bound. It would also be helpful to construct a table which summarizes the comparisons between all these bounds.
3.	The ICIMI bound from [12] could be added in Figure 1 as another baseline. 

limitations_and_societal_impact: Most limitations are well addressed in Section 3.5 and 4.1. Another limitation is that the Wasserstein distance is hard to evaluate and estimate in practice. I would like the authors to add more discussions to address this issue.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper new generalization error bounds based on Wasserstein distance are derived. As shown in the paper, these bounds are tighter than existing bounds based on mutual information. Also, the authors briefly discuss how their bounds could be extended to deal with backward channels (instead of forward channels), and how they could lead to bounds based on general f-divergences.
main_review: The literature review is very well done, which helps to put the paper contribution in perspective. While no new techniques are introduced, the authors made a good job in refining and combining different existing techniques. As far as the reviewer is concerned, it seems like the bounds presented in this paper are close to the best that can be done with existing techniques at the proposed level of generality. Applying these bounds beyond toy examples still requires some effort (probably a big one), but the paper reveals a clear path to do so. Overall, this paper represents a solid step towards practical generalization bounds.

Minor Suggestions
- It would be helpful for the reader if the authors emphasize, perhaps in a graphical manner, the taxonomy of current generalization bounds in terms of performance.
- Bobkov-Götze's theorem has a similar role to the HB inequality, although the former is not presented in the preliminaries. Perhaps it is useful to add the BG theorem to the preliminaries.
limitations_and_societal_impact: Yes, the authors adequately addressed the limitations of their work.
review_title: null

Meta-review: Overall, the reviewers were positive about the paper. My main concern is regarding its novelty: it seems that this paper combines Wang et al. 2019 with the individual sample approach proposed by Bu et al., 2020 and with the conditional mutual information approach proposed by Steinke and Zakynthinou, 2020, respectively. There are also limitations in terms of how useful the Wasserstein-based generalization bounds proposed in this paper are in practice, particularly regarding estimation of Wasserstein distance from data. The bounds seem difficult to instantiate even for very basic examples. As noted by several reviewers, it is unclear how the paper's results would translate to more complex models. Note that recent work in the area of information-theoretic generalization bounds provide numerical results to fairly sophisticated settings (e.g., the analysis of SGLD by Negrea and Haghifam et. al.) and, despite the bounds themselves often being vacuous, at least they correlate with the generalization behavior of neural networks on real-world data. The reviewers also pointed out several changes to the paper that I view as "mandatory," especially the points raised by reviewer 61bD. 

However, I do find that this paper moves the needle on generalization bounds forward. Despite mostly relying on a combination of existing theoretical tools used in the area of information-theoretic generalization bounds, it combines these tools in a novel way. The limitations/future work section is particularly thoughtful and reveals interesting new research directions. Together, the positive aspects of the paper outweigh its limitations, making me lean towards acceptance --- with the caveat that the authors should add the changes promised in their rebuttal.
Decision: Accept (Poster)