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: The present work develops PAC-Bayes like generalization bounds using integral probability metrics in place of divergences between a prior and the posterior. The bounds combine aspects of data independent ‘uniform convergence’ bound (based on empirical process theory), and data-dependent bounds (as is typical of PB bound, as well as margin based bounds, etc.) in a way that generalizes both since the present work’s bounds are smaller than one would expect from either alone. The present work specializes this to two particular IPM’s, total variation distance and Wasserstein distance. The focus is on theoretical results;  specific examples and numerical evaluation of bounds are not discussed.
strengths_and_weaknesses: The paper has a number of strengths, which lead me to support its acceptance. 
The writing is very clear, easy to follow, concise and accurate. The paper was a pleasure to read.
The results are interesting, useful, and (to my knowledge) completely original. 
The proofs are straight forward and easy to follow. Thus the results appear to be sound.
An aspect of the work which I find quite compelling, and an especially good fit for Neurips, is that the Wasserstein bounds do not require the posterior to be abs.continuous w.r.t. the prior, which means the bounds can be applied to SGD  training of general models, without modification to ensure abs.continuity. This is in contrast to prior work where similar bounds are expressed in terms of divergences.

The main weakness that I would like to point out, and the only item which addressed well would likely lead me to increase my score, is the lack of experimental or numerical evidence that shows that the theoretical improvements to standard bounds made herein are material in practical settings. An example of a model+training method where UC and PB bounds are both loose and the bounds of the present work are tight would materially improve the paper.
questions: NA
limitations: Lack of experimental/numerical results showing the new bounds are materially better in practice than existing ones.
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: The paper derives PAC-Bayes generalization bounds taking as complexity term integral probability metrics, in particular Total Variation and Wasserstein distance.
Existing bounds based on such complexities stand in expectation over samples from the data distribution, while the new results stand with high probability.
The principal requirements for deriving such bounds is that the loss is bounded and Uniform Convergence stands. The new certificates are potentially tighter than this type of classical results as they are algorithm and data dependent.
strengths_and_weaknesses: ### strengths
1. To the best of my knowledge the results are novel and non-trivial, as it is not straightforward to derive bounds with Integral Probability Metric within the PAC-Bayesian framework. In my opinion, the main advantage of the new certificates is that they drop the requirement of absolute continuity, hence the prior distribution can have null mass on bad predictors of the hypothesis class.

2. The paper is generally well presented and the proofs are clear and easy to follow.

### weaknesses
1. I find the argument that this work should improve existing generalization bounds for over-parameterized model weak. lt is not clear whether the new factors really tighten the bounds enough to make them non-vacuous (at the very least). On the contrary introducing VC or Radamacher complexity measures in PAC-Bayes bounds might end up make them looser, as these complexity measures do not correlated well with generalization (see e.g. [1]). On the other hand, dropping the constraint of absolute continuity potentially allows to derive certificates for dirac posteriors, hence to remove the need to derandomize the bound for deterministic models. However, the IPM might become too big for the available sample size. An empirical analysis or reporting few example settings would have helped showing in which contexts the new results have practical interest.

2. The literature on early works on algorithm dependent guarantees is not reported. Please consider citing at least the following seminal works: Uniform Stability [2], Algorithmic Robustness [3].

### minors
#### Writing
Paragraph 40-54: specify when expectations/probabiltities are over data or over predictors; which uniform convergence assumptions do you refer to?
Discussion: which works are referred to as "localized based approaches"?

#### Typos
1. line 48: probabily -> probability
2. line 51: it can -> can
3. line 243: Wasserstein-BP -> Wasserstein-PB 
4. Discussion: divergences -> distances

[1] Jiang, Yiding, et al. "Fantastic generalization measures and where to find them." ICLR (2020).

[2] Bousquet, Olivier, and André Elisseeff. "Stability and generalization." The Journal of Machine Learning Research 2 (2002): 499-526.

[3] Xu, Huan, and Shie Mannor. "Robustness and generalization." Machine learning 86.3 (2012): 391-423.
questions: My principal question is detailed in weaknesses 2. In other words, in which settings the new results improve on both classical Uniform Convergence bounds and PAC-Bayesian bounds? 
limitations: The limitations of the work are adequately addressed.
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: The paper presents new generalizations bounds that aesthetically look like a mix between uniform convergence and PAC-Bayesian bounds.   In one instantiation, the new bound can improve on uniform convergence bounds by a factor proportional to the square root of the TV distance between a posterior and prior distribution. The authors achieve their results thanks to a new IPM-based generalization guarantee. 
strengths_and_weaknesses: The new IPM-based generalization guarantees seem new and would be of interest to the ML community in my opinion. One desirable feature of these bounds is that they allow for degenerate posteriors (the posterior need not be absolutely continuous w.r.t. the prior), which is not allowed in standard PAC-Bayesian bounds. 

In terms of weaknesses, the fact that uniform convergence is required in most bounds is not ideal. Especially, since the new bounds depend on the uniform convergence error which can be large for Neural Networks, for example. After all, having non-vacuous bounds for large classes was one of the main motivations behind the paper. 
questions: Have you done/can you include any experiments to compare the new bounds to previous PAC-Bayesians ones? 
limitations: Some suggestions for improvement (mainly typos):
- It would be good to include an explicit comparison of the new bounds to those of, e.g., Neu and Lugosi (2022). (If space is an issue, at least include the bound of the latter in the appendix).
- Eq (4), f_S is not defined within Def 3
- Line 199: with the the zero-one -> with the zero-one
- Line 234: $K(m,\delta')$-Lipschitz? Do you mean just $K$-Lipschitzness with $K$ that may depend on $m$ and $\delta'$? If so, this is a little confusing---just say $K$-Lipschitz. 
- Line 239-240: "is K-Lipschitz with high probability, where the rate of $K$ is preferably $O(1/m)$" Not clear what you mean by this. Clarify.
- Line 273: "Assume that for any fixed $z ∈ Z$, $f(h,z)$ is continuously differentiable for any $h \in H$". This is redundant as it is already a condition in Def 13.
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: Authors open the classical PAC-Bayesian framework to new type of divergences, going beyond the classical KL-divergence or the $f$-divergences. They introduce the general notion of Integral Probability Metric (IPM) and they derived from it general templates for a new type of IPM-PAC-Bayesian bounds. 

From those general bounds, authors provide new concrete results for two classical divergences: the TV distance and the Wasserstein distance. 
strengths_and_weaknesses: MAJOR ISSUE:

To my understanding (please correct me if there is an argument that I missed), the preliminary theorem (Prop 4.) is not correct. Authors stated this result holds "with probability $1-\delta$, for all $Q\in\mathcal{M}(\mathcal{H})$..." while the correct formulation is  "for all $Q\in\mathcal{M}(\mathcal{H})$,with probability $1-\delta$..."

I provide below a corrected version of author's proof which starts from the line 458 of the appendix.

NEW PROOF--

Inequalities (23) and (24) imply $\\forall (Q,P)\\in \\mathcal{M}(\\mathcal{H})^2,$

 $\\mathbb{E}\_{S \\sim \\mathcal{D}^{m}} \\exp \\left(\\underset{h \\sim Q}{\\mathbb{E}}\\left[f\_{S}(h)\\right]-\\gamma_{\\mathcal{F}_{S}}(Q, P)\\right) \\leq m .$

Therefore, by Markov's inequality, for any $t>0$ we have  $\forall (Q,P)\in \mathcal{M}(\mathcal{H})^2,$

\begin{multline*}
  \mathbb{P}\_{S \sim \mathcal{D}^{m}}\left(\exp \left(\underset{h \sim Q}{\mathbb{E}}\left[f_{S}(h)\right]-\gamma_{\mathcal{F}\_{S}}(Q, P)\right) \geq t\right) \\
   \leq \frac{\mathbb{E}\_{S \sim \mathcal{D}^{m}} \exp \left(\underset{h \sim Q}{\mathbb{E}}\left[f_{S}(h)\right]-\gamma_{\mathcal{F}\_{S}}(Q, P)\right)}{t} \leq \frac{m}{t} .
\end{multline*}


Or, equivalently, $\forall (Q,P)\in \mathcal{M}(\mathcal{H})^2,$
$$
\mathbb{P}\_{S \sim \mathcal{D}^{m}}\left(\underset{h \sim Q}{\mathbb{E}}\left[f\_{S}(h)\right]-\gamma_{\mathcal{F}\_{S}}(Q, P) \geq \ln (t)\right) \leq \frac{m}{t}
$$

Let $\delta \in(0,1)$, we set $t=\frac{m}{\delta}$, and plug in $f_{S}(h) \stackrel{\text { def }}{=} 2(m-1) \Delta_{S}^{2}(h)$ to get
$$
\forall (Q,P)\in \mathcal{M}(\mathcal{H})^2,\mathbb{P}\_{S \sim \mathcal{D}^{m}}\left(\underset{h \sim Q}{\mathbb{E}}\left(2(m-1) \Delta\_{S}^{2}(h)\right)-\gamma_{\mathcal{F}\_{S}}(Q, P) \geq \ln (m / \delta)\right) \leq \delta
$$
Rearranging the above, we have that, for all $Q,P \in \mathcal{M}(\mathcal{H})^2$, with probability at least $1-\delta$ over the samples $S \sim \mathcal{D}^{m}$, the following inequality holds
$$
\underset{h \sim Q}{\mathbb{E}}\left(\Delta\_{S}^{2}(h)\right)<\frac{\gamma_{\mathcal{F}\_{S}}(Q, P)+\ln (m / \delta)}{2(m-1)} .
$$
By Jensen's inequality applied to $\Delta\_{S}(h)^{2}$
$$
\left(\underset{h \sim Q}{\mathbb{E}} \Delta_{S}(h)\right)^{2} \leq \underset{h \sim Q}{\mathbb{E}}\left(\Delta_{S}^{2}(h)\right) \leq \frac{\gamma_{\mathcal{F}}(Q, P)+\ln (m / \delta)}{2(m-1)}
$$
The theorem follows for any pair $(Q,P)$ with probability $1-\delta$ by taking the square root of both sides.

--

The problem with author's proof is that they did not realise that they were applying Markov's inequality on a random variable depending on the sample $S$ and the distributions $Q,P$. **Modifying the posterior distribution changes the variable onto which we apply Markov's inequality and then requires a novel application of this bound.** That is why Prop 4. cannot hold with high probability for all posteriors (except on the case of a finite posterior class $C$ where one can apply an union bound on the events and maintain the result at the cost of an extra $\log(|C|)$).

That is why the change of measure inequality is so important in classical PAC-Bayesian proofs: it allows a deterministic control over the whole class of posterior by bounding a moment depending on $Q$ by a KL divergence plus a random variable depending only on the prior $P$ and the sample $S$. Then one can apply a single time Markov's inequality on this random variable to obtain an uniform PAC bound over all the posteriors.


Thus, this apparently small modification of the result has actually huge consequences:

- All the theorems provided in the paper lose the strength of having a global control over the posterior class : they only have a local control over a single posterior, which is not catastrophic but I believe this fact changes the spirit of the paper. Indeed, I think authors should now also focus on constructive procedure to exhibit concrete posteriors (which still benefits from author's theoretical guarantees)

- The place of the change of measure inequality is crucial to obtain strong global guarantees and is not only a mathematical technique to involve KL-divergence. Authors should also check and refer to the work of (Picard-Weibel and Guedj, 2022) which tries to generalise the change of measure inequality to others type of divergences.


Other points:

- This major point being said, I am not sure on how I should consider the rest of the new resuts of the paper as they are all derived from Prop. 4.  I see plenty of results which are now local on the choice of the couple $(Q,P)$. Then I am wondering if one can derive some concrete optimisation routes from those upper bounds if one restricts to specific classes. More generally, I did not see much discussion about the range of the proposed results which is a shame, especially when authors still have more than a half page available.

- I would have appreciated more discussion about the proposed theorems, their novelty and the interest of considering such new distances (although I admit  the end of Sec. 5 goes in this direction) given the extra space authors still have

- I find interesting the idea of exploit IPM onto a PAC-Bayes framework. It may be a fruitful tool to extract PAC-Bayes from KL and $f$-divergences.


CONCLUSION: My main problem with this work is Prop. 4's proof. To me, this point weakens the paper a lot as it shows that for instance the TV distance nor the Wasserstein one are 'less adapted' to PAC-Bayesian than the KL divergence as it allows to only recovers local results for a similar framework. This point, to me, should be at least acknowledged and a discussion about the change of measure inequality should be proposed in this work. However, I think that with a more careful study, this line of research could be fruitful and I do not contest the novelty of the proposed approach. A convincing axis of work would be to focus on the practical extensions of their work and exploit the fact that, according to the authors, Wasserstein distance is potentially more stable in practice. Having concrete extensions would for me, compensate the local behavior of those results.



 
questions: Do authors have an argument to counter my claim on Prop. 4 's veracity? 

- Is there any cases where one can compute TV-distance nor the Wasserstein one? To the local nature (see the major issue of Strengths&Weaknesses section) of all the proposed result I believe insisting on the practical extensions is now essential on this work.

- I am wondering about the choice of the universal constant in Cor. 8. Is it an accessible quantity? I am wondering if the proposed bound remains fully empirical.

- In Th. 11, do authors have an instance of a non-Lipschitz function verifying the assumption of being Lipschitz with high probability? 

limitations: Autors are clear on their framework and the remits of their contributions.
review_title: null

Meta-review: metareview: PAC-Bayes bounds provides a control of the risk of aggregation of predictors. In these bounds, the Kullback-Leibler divergence between the aggregation distribution and a prior appears in the upper bound on the risk. In this paper, the authors prove variants where the KL is replaced by an IPM (Integral Probability Metrics), including the total variation distance and Wasserstein. The important point is that these bounds are close to "uniform" (Vapnik-type) bounds in some unfavorable settings, but also can improve on them is more favorable scenarios.

The reviewers agreed that the results are novel and that the paper is technically sound. These bounds really extend the framework of PAC-Bayes bounds (for example, they are not necessarily vacuous when the posterior is not absolutely continuous with respect to the prior), and the fact that they recover uniform bounds in the worst case is also nice. All the reviewers recommended to accept the paper, and I agree with them.

The reviewers pointed out a few missing references, I will ask the authors to include them in the paper as promised during the discussion. I will add the following references that were not mentioned by the reviewers, and thus leave the authors decide to include them or not:
- Alquier and Guedj (2018) actually provided PAC-Bayes bounds based on f-divergences, that were then improved by Ohnishi and Honorio (2021) (especially the dependence with respect to the confidence level).
- there were a few attempts to replace the KL by the Wasserstein distance. The benefit were not as clear as in the present paper, but the authors might want to comment on the paper https://hal.archives-ouvertes.fr/hal-03262687/ or Lopez & Jog (2018) on MI bounds...
confidence: Certain
Decision: Accept