Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes to study the best numerical tightness of PAC-Bayes bounds, it comparison with test set bounds. The main motivation given is that in small sample problems one cannot afford to hold out a subset of the data to compute a test set bound. 

The main theoretical results are Theorem 4 with its Corollary 3, presented in Sec. 3. In Thm 4 the dataset is fixed, and the best divergence function is sought for the general PAC-Bayes bound, which produces the tightest bound. This turns out to be one of Catoni's bounds. In Cor 3 the data set is no longer fixed, and the authors find that Catoni's bounds can no longer achieve the tightest bound, and the authors conjecture the "optimistic MLS bound" is a tight lower bound, which they show to be a tight lower bound. Apparently the conjecture was previously stated by Langford. While the present paper still leaves this open, it makes some progress in terms of insights.
The theoretical investigation is complemented with numerical experiments, which also add insight.

Furthermore, Sec 4. presents extensive experimental work addressing the question of which PAC-Bayes bounds are tightest and how they compare with the test set bound, by optimising the bounds numerically, with respect to the algorithm and the task. Results from the experiments are presented in Figs 3 and 4, and several interesting observations are made, including that PAC-Bayes can be as tight as the test-set bound, and that the "optimistic MLS bound" is indistinguishable from Catoni's. While it is indeed interesting to see that PAC-Bayes bounds can be really tight, of course it doesn't mean they will be tight when applied on some given task and some given algorithm.        

The main outcomes of the study are summarised in Sec 5. in the for of 2 open problems: 1. echoes the one of Langford, 2. asks for the possibility that a PAC-Bayes bound be as tight (at its best) as the tightest set set bound. 

main_review: Originality: While the bounds studied here are not new, and the open problems that result from the study are also existing ones, the questions formulated and the methodology to pursue them are original. It is one of those studies where "the journey is more important than the destination". It is insightful to see those connections and limitations of the PAC-Bayes methodology, despite there is no better alternative is being proposed. In addition, the study also has pedagogical value as it could easily serve to attract newcomers to the field.

Quality: The study is well designed, and rigorous. The paper is well written. I found Sec 3 stronger than Sec 4. The latter seems more exploratory. 

Clarity: The presentation is mostly clear, except few places. 
- I wasn't sure about the pairs of plots in Fig 3 - is the first plot the upper bound on the second, and the third plot the upper bound on the fourth? If so, my concern would be not so much about numerical tightness but the differences in behaviour - eg. generalisation risk decreasing when the bound is decreasing? I suspect I misunderstand something regarding this figure, could the authors clarify? 
- the reduction of PAC-Bayes to test set bound should be explained with more care because the purpose of these two types of bounds is quite different and the latter uses a test set whereas the former doesn't.
- In statement of Thm 4 "a fixed dataset" - do you mean any fixed dataset? or one particular dataset?
- on page 4, "discretising the inputs to \Delta": \Delta takes 2 arguments, so please clarify what is meant here? Sam in Thm 4: \Delta convex *in its 2nd argument* - right?
- in Sec 4 when parameterising the meal-learner and hypothesis space, and taking Q_{theta} and P_{theta} to be Gaussian, then I think the results be specific to this choice of distributions? If so, is there anything general that we can learn from the results?
- instead of "optimistic MLS" I'd suggest "wishful MLS" (reason being that optimistic bounds normally refer to bounds that exhibit a faster convergence rate).
- I don't quite agree with the statement that the "optimistic MLS" can quantify potential slack - because, as the authors rightly point out, it is not yet proven to be a valid generalisation bound. 
- on page 5, "Catoni's bound is sometimes nearly optimal" sounds very sounds like a formal claim, but if I got it right here it refers to a visual assessment of the experimental figure?

Significance:
- The study is exploratory, and provides interesting insights about and connections between state-of-the-art generalisation bounds, but no definite conclusions or improvements of the bounds or bounding techniques. The main outcome of the study is echoing 2 open problems.
Nevertheless the focus on state-of-the-art bounds and the timely questions investigated have good pedagogical value that can easily serve as entry point for newcomers to the field.
- The study is only concerned with numerical tightness of the bounds, not the (increasing/decreasing) behaviour, which is more important for the bounds to be useful in practice.
- As we know, the PAC-Bayes bounds assume a Gibbs classifier, while we sometimes want to apply it to classifiers in the frequentist framework to classifiers that don't have uncertainly in their parameters. Could the authors comment on how to reconcile this?  
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: As far as I see, this submission is motivated by the desire to understand the ability of PAC-Bayes bounds to give tight numerical values such that they could be used as numerical measures intended to certify the post-training performance of randomised classifiers. The submission leverages the so-called generic PAC-Bayes theorem which is stated in terms of an arbitrary convex function $\Delta : [0,1]\times[0,1] \to \mathbb{R}$ and which can be seen as the basis for deriving the known PAC-Bayes bounds (the one of McAllester, the one of Langford and Seeger, the parametric family of bounds of Catoni, possibly others) as shown by Germain et al. [2009].

In particular, the submission compares theoretically the best bounds that could be hoped for when using the parametrised family of bounds of Catoni (there's one such bound for each $\beta>0$), and the generic bound for a given $\Delta$. Then it also discusses what's the best one can hope for when optimising $\Delta$ from a class of convex functions. Then in some empirical studies with (artificial) datasets of small size the values of the bounds are evaluated and compared. For individual (as opposed to randomised) predictors, the values of two "test set bounds " are also shown: the binomial tail inversion bound and the Chernoff relative entropy bound. If I understand correctly, the intended goal is to compare the tightness of the PAC-Bayes bounds (for randomised predictors) with the tightness of the test set bounds (for individual predictors). The experiments culminate with a setting where the parameters of the bounds are meta-learned, and the claim is that in this setting the PAC-Bayes bounds give better results than the test set bounds. The discussions, however, suggest settings in which test set bounds, in particular the so-called binomial tail bound, dominate.
main_review: ORIGINALITY

The generalisation bounds (PAC-Bayes and other) that appear in this paper are all known. An novel thing that this submission does is leverage the generic PAC-Bayes theorem which holds for an arbitrary convex function $\Delta$ of two arguments, and convex analysis tools (convex duality) in order to reason about the best $\Delta$ that could be used and the tightness of the resulting bound. The related literature is acknowledged (some comments on the cited literature of missing references are pointed below).

SIGNIFICANCE

I am leaning to say that this work is likely to generate fruitful discussions and follow-up works. I admire the effort to use sound theoretical analysis in order to reason about generalisation of learning methods using a language and experimental demonstrations that may appeal to the less theory-minded part of the machine learning community, it could have a positive effect of leading by example.

CLARITY / QUALITY /  READABILITY

The paper is relatively well written and the organisation is okay. Some parts require attention to make them more clear/readable. A few parts require mode delicate attention to rule out sources of possible confusion or misleading the community. My comments are below, together with some questions and there is also more extensive feedback of editorial nature.

EDITORIAL FEEDBACK

Comment on the abstract: On a first reading of this abstract I had the impression that it is a bit overloaded and it did not clearly summarise the paper. After a pass at the whole paper, I think the abstract is a bit misaligned. Try to make it concise and simple while keeping it aligned with the paper, essentially address these questions in the abstract: What problem the paper is about (from the title, it looks that the paper is about tightness of PAC-Bayes bounds in the small data regime); how does the paper approach the said problem (e.g. by analytical and numerical comparison with other kinds of generalisation bounds); what are the most salient observations (e.g. in one setting bound A is tighter than B, but in another setting the reverse order holds); and explicitly advertise the novelties (if any) here. Also, on the note of simplicity, or as matter of style, I recommend typing in (last)names rather than using \cite in the abstract, and keeping citations to a minimum. The last point can be accommodated e.g. like ​this: "generic PAC-Bayes theorem shown by Germain and others." and "family of PAC-Bayes bounds considered by Catoni." and "the family of bounds of Catoni can be suboptimal." and "proof framework of the generic PAC-Bayes theorem, we establish [...]"

L.32: " significantly harming post-training performance due to a reduced training set size."

L.33: this sentence calls for a reference, Perez-Ortiz et al. [2020] is relevant here.

L.36: As fas as I know, the generic PAC-Bayes theorem is originally due to Germain et al. [2009], while others (e.g. Begin et al. [2016] and Rivasplata et al. [2020]) restructured the presentation of the proof or gave extensions to other divergences (Begin et al.) or to setting with relaxed restrictions (Rivasplata et al.) hence it would be more accurate and fair to write something like "remarkably, Germain et al. [2009]  showed that a wide range of bounds can be obtained as special cases of a single \emph{generic PAC-Bayes theorem} that captures the central ideas of many PAC-Bayes proofs [see also Begin et al., 2016 and Rivasplata et al., 2020]."

L.39: "holds for any convex function $\Delta : [0,1]\times[0,1] \to \mathbb{R}$."

L.40: After "Catoni [2007]" insert "and other bounds"

L.41: "to this setup."

Warning note: Two distinct types of applications of PAC-Bayes bounds are: (1) using such a bound for evaluating a numerical risk certificate for (the randomised predictor defined by) some distribution over hypotheses learned by some method; and (2) using such a bound as optimisation objective by declaring to learn a distribution over hypotheses by minimizing the bound. The second kind of use is possible because PAC-Bayes bounds hold simultaneously (i.e. uniformly) for all distributions over a given hypothesis class. See e.g. the corresponding discussion given by Tolstikhin & Seldin [2013] or by Thiemann et al. [2017]. It appears that this submission is not making a clear distinction between these two uses, and perhaps conflating them when claiming that PAC-Bayes allows to use of all the available data that avoid splitting the data while at the same time getting a certificate on the post-training performance (see corresponding discussion given by Perez-Ortiz et al. [2020]). This must be addressed for the sake of clarity and to avoid misleading follow-up research.

L.46-47: This passage needs clarification/elaboration. Risk bounds (aka generalisation bounds, including PAC-Bayes bounds) studied in statistical learning theory are inequalities that hold with high probability with respect to the random choice of datasets (of a given size). Hence reading "fixed dataset" here raises a question mark that begs for clarification. On the other hand, in the typical problems studied by the machine learning community, datasets are fixed (e.g. MINIST, CIFAR-10, ImageNet) and there is the question of whether or under what cases the assumptions of the risk bounds (e.g. i.i.d. data, or at least randomly generated data) are met or can be considered to be reasonable for a given data set so that using the high-probability bounds is justified.

L.48: Replace "stochastic dataset" with "random dataset"

Reason: "random" refers to something that is picked according to a given *fixed* probability distribution (e.g. a random digit, or a random matrix of size 10x10) while "stochastic" in my mind refers to a *changing* probability distribution, e.g. changing with respect to a time parameter (e.g. a Brownian motion) or a space parameter (e.g. a Poisson point process). In your setting, it appears that the assumption on the dataset is that it is generated randomly according to a fixed (but unknown) data-generating distribution $D$. Accordingly, calling it a "random dataset" is preferable. (Alternatively, justify why to call it stochastic.)

L.51: A bit surprising to read that a neural network parametrises a convex function.

L.52: " bound of Langford and Seeger, and relaxes" (space-saver, since the year has been acknowledged already,)

L.53: insert a reference for the Chernoff test set bound (or insert "(see Theorem 2 below)" since it provides the reference)

L.54-60: by the end of reading this paragraph it should be clear to the reader whether you are using bounds for numerical evaluation of certificates only, or if you are using the bounds for learning (by bound-minimisation) and for numerical evaluation of the certificate. In other words, what I missed in this introduction is a high-level description of what kinds of predictors are being considered, for which the certificates on post-training performance are applied.

L.62 (and rest of the paper): I recommend the capital calligraphic $\mathcal{X}$ and $\mathcal{Y}$  for the sets that encompass all possible inputs and all possible labels (resp.), and $\mathcal{Z} = \mathcal{X}\times\mathcal{Y}$ for the set of all possible input-label pairs. Then this will be consistent with your use of $\mathcal{H}$ for the set of all possible hypotheses, etc.

L.77-78: "For the zero-one loss $\ell(h,(x,y)) = \mathbb{I}[h(x) \neq y]$ we have the binomial random variable [..] with parameters [...]"
Also, the number of trials should be "$N_{\mathrm{test}}$" I think?

L.81: the sum should start from 0?

L.86: For the same reason explained above, I recommend replacing "stochastic" with "randomised"
(regardless of what the PAC-Bayes literature has done before, unfortunately)

L.87: As mentioned above, a claim "does not require discarding data" needs to be supported (clarification or reference(s))

L.88-89: "Germain et al. [2009] prove a very general form of the PAC-Bayes theorem which encompasses many of these [see also Begin et al., 2016 and Rivasplata et al., 2020]."

L.90-21: The part of taking supremum over the risk is special to Begin et al. I think
(i.e. Germain et al. [2009] did not do this last step as fas as I remember)

L.96: this theorem needs to clarify that the probability is over the random choice of dataset $S$ of size $N$.
(i.e. could replace $\operatorname{Pr}$ with $D^{\otimes N}$, since the probability is w.r.t. distribution of the size-$N$ random sample)

L.97-98: I did not understand this remark. Note that the choice $\Delta(x,y) = 2(x-y)^2$ is a possible choice for $\Delta$, which gives the classical form of the PAC-Bayes bound, i.e. the one that resembles the bound of McAllester.

L.99: Germain et al. [2009] discussed how Catoni's bound follows from their generic PAC-Bayes theorem, hence in this case I feel that the attribution to Begin et al. is a bit misleading.

L.103-104: "we obtain the bound of Langford and Seeger [2001], also called the PAC-Bayes-kl bound [e.g. Seldin, 2012], but with the slightly sharper dependence on $N$ established by Maurer [2004]:"

L.105: Note that in fact this inequality holds for all $N \geq 1$, the small $N$ cases have been verified numerically
(see "Risk bounds for the majority vote: From a PAC-Bayesian analysis to a learning algorithm")

L.106: Why not refer to this, more suggestively, as the PAC-Bayes-kl bound?
(I am objecting the use of the acronym MLS due to being uninformative and potentially misleading)

L.107: The accurate thing to comment is that Corollary 2 is a special case of Theorem 3 in which the $\mathcal{I}_N(\Delta)$ has been upper-bounded by $2\sqrt{N}$ using Stirling's formula, as shown by Maurer [2004]. It is misleading to say that Corollary 2 is looser than Theorem 3, since the theorem is generic and the $\mathcal{I}_N(\Delta)$ has not been controlled.

L.108-110: Again, the two different uses of PAC-Bayes bounds are being conflated in this passage.
Also, the list of references in the square brackets should start with Langford and Caruana 2001 and end with Perez-Ortiz et al., 2020
(Note that the publication year of "(Not) Bounding the True Error" is 2001, regardless that Google Scholar incorrectly gives 2002)

L.112: [McAllester, 1999, 2003]

L.123: replace "value" with "form"

L.132-133: There are significant differences between the three references that are worth bringing to attention: Langford & Caruana [2001] trained a randomised neural network classifier by some method (which has nothing to do with PAC-Bayes, it was by some sort of sensitivity analysis) and used the PAC-bayes-kl bound to evaluate a numerical bound on the risk of this classifier; while Dziugaite & Ropy [2017] trained a randomised neural net classifier by a PAC-Bayes method (a training objective based on McAllester's bound) and used the PAC-Bayes-kl bound to compute a numerical bound on the risk of the classifier, so the last step is identical to the corresponding step done previously by Langford & Caruana, but the novelty was that D&R demonstrated *non-vacuous* bound values for an architecture of like two hidden layers of 600 hundred units per hidden layer (the demonstration was on a "binarised" version of MNIST (where the digits 0, 1, 2, 3, 4 were declared to be a single class and the digits 5, 6, 7, 8, 9 another single class), hence the first instance of a non-vacuous bound for the overparametrised setting where there are a lot many more trainable parameters than training data); and Perez-Ortiz et al. [2020] trained randomised neural net classifiers by several PAC-Bayes methods (including the one used by D&R 2017) and used the PAC-Bayes-kl bound to compute numerical bounds on the risk of these classifiers (like D&R and L&C before), and the novelty of this work is demonstrating *tight* bound values (not just non-vacuous) on full 10-class MNIST and on CIFAR-10, not just feed-forward architectures but also convolutional architectures, and showing that learning the prior on part of the data is key for obtaining tight values of the numerical risk certificates, and called it "self-certified learning" because the whole procedure outputs simultaneously a predictor learned from data and a certificate on the risk of this predictor, hence this work is quite related to your work making similar claims, and they also did come other things like comparing several predictors (fixed, randomised, ensemble, classic ERM, and "Bayes by backprop") and showing that the PAC-Bayes-kl bound can do model selection. [The important point of the work of Perez-Ortiz et al. is that the whole training data was used to learn the predictor, and the certificate was evaluated using part of this training data (the part that was not used to learn the prior), and the value of the certificate is reasonably close to the test set errors (the latter is evaluated on a held-out set), and this tightness indicates that the computed certificates are informative of the post-training performance of the randomised classifiers learned by their methods, hence it makes sense to call it a certificate, unlike a case where you have a non-vacuous numerical bound value of say $\sim 20$ percent for a classifier with test error $\sim$[single digit] percent, in which case the non-vacuous value is uninformative because it is not tight.] 

L.141: "This upper bound (Them 3) can be "inverted" to obtain [...]" 

L.146: "random dataset"

L.146-147: I am not sure what is meant by these cases of "fixed dataset" and "random dataset" --- as far as I understand, the theorems hold with high probability (of at least $1-\delta$) over the random datasets, hence when you have a fixed instance of a dataset (one realisation of the random dataset, generated by a distribution that meets the requirements of the theorems) you apply the inequality given by the theorem to this fixed dataset, and the reasoning is that this fixed dataset could be one of the bad datasets for which the inequality does not hold, but the probability that it is a bad dataset is small (of at most $\delta$). 

L.147: Replace "Next" with "Later"

L.149: "realistic case of a random dataset"



L.151-154 (Theorem 4): This theorem needs to be reformulated according to the intended meaning and

L.156-158 (Remark 2): since the lower bound gives infimum over $\beta>0$, there might exist values of $\beta$ for which $p_{\Delta}$ is less than $p_{C_\beta}$?

L.161-162: This passage is missing some justification for the implicit claim that a one-hidden-layer neural network with positive weights [...] parametrises a general $\Delta \in \mathcal{C}$. Or insert a reference for this?

L.162-163: This describes the same idea used by the numerical inversion of the binary kl which has been used extensively in the PAC-Bayes literature [Langford & Caruana, Ambroladze et al, Parrado-Hernandez et al., many many others]

L.167-168: the claim that this difference converges to 0 from above suggests that there are no $\beta$ for which $p_{\Delta}$ is less than $p_{C_\beta}$? Then if that is true then in fact $p_{\Delta}$ would be at least as large as the sup of $p_{C_\beta}$.

L.170-171: Still it is not clear how the cases of "fixed data" and "random data" give different things. 
This suggests at the very least that clarification is needed.

L.172: This line is comparing the average values of the inversions corresponding to different $\Delta$'s, is this legit?

L.178-180: The statement of this Corollary, or some discussion before or after it, should comment on how to make sense of comparing the expectations of the upper bounds, versus comparing the upper bounds for given settings of their components.

Only skimmed at the Proof of Theorem 4 but happy to get back to it between rebuttal and final decision if we get there.
A quick question: Care to give some intuition on why lower-bounding $N^{-1}\mathcal{I}$ and upper-bounding $\Delta$?
At first look it seems to make sense upper-bounding $\mathcal{I}/N$ and lower-bounding $\Delta$, feel free to check me what I misunderstood.

L.230: In "minimise the expected bounds" does this mean minimising the expectation of the bounds, with the expectation over the distribution of the random datasets of a given size? If this is what is meant, some justification is needed for this procedure, taking into account that the PAC-Bayes bounds are high-probability bounds over such distribution.

L. 235-239: This paragraph is missing some references for the meta-learning literature especially the literature based on PAC-Bayes bounds. The works of Maurer, Amit and Meir, and some others might be relevant here.

L.236: This suggests that there is one hypothesis space (i.e. a function class) $\mathcal{H}_{\theta}$ for each possible $\theta$ --- is that correct? Also, the "posterior map" is formally a stochastic kernel (aka Markov kernel).

L.241: The notation $\mathcal{T}$ needs to be declared. Is it intended for denoting the set of all possible tasks?
I think the distribution over tasks should use a different notation than the distribution that generates random dataset for a given task.

L.247: "Perez-Ortiz et al., 2020" is relevant to these references for data-dependent priors gaining attention.

L.249: replace "empirical risk" with "risk bound"

L.250: This is precisely the protocol used by Perez-Ortiz et al. for learning the data-dependent prior say on data $S_1$ and evaluating the risk certificate on dataset $S_2$ while the randomised predictor (the "posterior") is learned on $S = S_1 \cup S_2$. this procedure was used before by Ambroladze et al. and Parrado-Hernandez et al. for SVMs, while Perez-Ortiz et al. were the first to use it for deep learning.

L.251-252: "and Perez-Ortiz et al. demonstrated empirically that learning priors from data is key for obtaining tight risk certificates" 
(the latter are much (!) better than non-vacuous bound values)

L.253: The mapping at the end of this line is better formalised as a stochastic kernel.

L.255: this choice to "ease notation" has the effect of obscuring the dependencies --- can it be fixed?

L.261: "learned convex function"

L.267: If $t$ denotes an individual task, and $D_{t}$ the distribution that generates data for this task, then it is clear that the notation $S_t \sim D_{t}^N$ stands for a dataset of size $N$ for task $t$ (but probably $N_t$ should be used for sample size if diferent sizes were to be used for different tasks). However, it is unclear what the notation "$D_t \sim \mathcal{T}$" is trying to communicate. In case, as a few lines above, $\mathcal{T}$ is the set of all possible tasks, and $D \in M_1(\mathcal{T})$ is the distribution according to which one can select a random task, then writing $t \sim D$ is okay, and then writing $S_t \sim D_{t}^N$ for the chosen $t$ (but I think this is missing some conditionals to clearly communicate the order in which the random choices are made, i.e. $D_t$ is in fact a conditional probability distribution, and some regularity must be assumed on the space $\mathcal{T}$ to justify that one can calculate with these distributions in a way that resembles calculations with unconditional distributions).

In general, my impression is that this section could improve a lot by better/explicit math notation and definitions.

L.279: It might be relevant to comment whether the feature space dimension $K$ is set a priori, or it depends on data and is only known a posteriori as in the case of kernel learning (and corresponding RKHS).

L.292-293: This is expected in view of the higher representational power of the CNN compared to MLP?

L.296: Confused by "the test set classifier" --- should this be "the test set bound"? (Or else, explain.)
L.297: The "PAC-Bayes classifier" is the randomised classifier, according to the PAC-Bayes posterior distribution?

L.304-305: The "binomial tail test set bound with a train set proportion 0.4" --- this needs clarification. Is it that the procedure consists of using 40% of the training data for learning a predictor, and the remaining 60% of the data for evaluating the binomial tail test set bound? 

Okay, I guess it lakes sense to compare the binomial tail bound (Theorem 1) and the Chernoff bound (Theorem 2) in Fig.4(a) because both these bounds apply to individual predictors $h$, while the separate Fig.4(b) plots the PAC-Bayes bound (is this correct?) which applies to randomised predictors (i.e. distributions over the $h$'s)

L.340: and "Rivasplata et al. [2020]"

L.343: Not sure about the claim that "Gibbs classifiers are not often used in practice" --- could this be substantiated?

Overall this is an interesting/informative discussion in Section 5. however I'd like to flag one thing: It is not clear to me if the analyses carried out in this paper are specific to the small data regime. It if is, this should be highlighted (places in the paper where the analysis holds for small $N$ but not for large $N$). in fact my impression is that the theoretical arguments put forward here might be valid for arbitrary $N$, while the *experiments* were done on small datasets (N=30 and N=60). Interesting paper, regardless.

Would like for all my feedback above to be addressed in the response.

limitations_and_societal_impact: Sure.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper investigates the relative tightness of PAC-Bayesian and test set bounds (Langford, 2002) in the small data regime for losses bounded in the unit interval. 

main_review: Focusing on the small dataset regime, the paper investigates the relation between test set bounds (Langford, 2002) and PAC-Bayesian bounds, notably, (1) the family of bounds due to Catoni (parameterized by $\beta$), (2) Maurer's PAC-Bayes-kl-inequality and (2) the generic PAC-Bayesian bound due to Germain et al (2009), Begin et al (2016) that involves a free parameter (convex function $\Delta$). Maurer's (non-parametric) bound behaves like Catoni's bound (and it's relaxation, McAllester's linear bound) but holds uniformly for all $\beta$ at the cost of a $O\left(\tfrac{\ln \sqrt{n}}{n}\right)$ term that comes by way of a union bound argument. It might benefit the reader to clearly state this fact just after the statements of Corollaries 1 and 2.  

For a fixed dataset, the authors show that Catoni's bound achieves the tightest version of the generic PAC-Bayesian bound (involving the free parameter $\Delta$). On the other hand, in the random dataset setting, Catoni's bound is not optimal. I checked the proof of Theorem 4 and it appears correct. The authors also experimentally demonstrate in a controlled setting that PAC-Bayesian bounds are competitive with the Chernoff test set bound. 

The analysis in this paper applies only to loss functions bounded in the unit interval. Though the authors acknowledge this as a limitation and hint at the potential of extending the analysis beyond some of the restrictions (l.344-349), it is not immediately clear, for example, if the analysis can be extended to unbounded losses. As a minor gripe, this comes about as a bit unsatisfactory given that there are well-known “generic” PAC-Bayes inequalities for unbounded losses to start with (see, e.g., Theorem 2.1 in Tong Zhang, 2006 that recovers Catoni's bound when restricted to the 0-1 loss; http://tongzhang-ml.org/papers/it06-bound.pdf). Overall, I found the paper well-written with a clear motivation albeit with only incremental contributions. 
limitations_and_societal_impact: Addressed by the authors. I do not foresee any potential negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper first proves that, regarding the choice of convex function Delta in PAC-Bayes generalization bounds (Theorem 3), the family of Delta as in Catoni 2007 always contains a function that minimizes the upper bound on expected risk (Theorem 4). It then proves that for all convex functions Delta, the expectation of the upper bound on expected risk is bounded below (Corollary 3). Finally, the paper studies a meta learning situation (in which some parameters of Delta are fitted based on data) and reports the gap between held-out test error and value of the generalization bound. 
main_review: I have concerns about the clarity of the paper. 

Originality. The paper chooses to address an important and unsolved theoretical problem, which is characterizing how Delta, a design choice in PAC-Bayes, affects the best possible generalization bound. Applied researchers have experimented with different families of Delta to attain the best numerical results (generalization bound versus test error). Before experimentation, it is not clear which Delta should be preferred. A theoretical result of the flavor “it is sufficient to search in this/that family of Delta” would be a good tool, since it narrows down the set of options over which a practitioner must search. The use of Figure 2 as an illustration for Theorem 4 is very helpful. 

Clarity/quality. My biggest concern is that I am not sure what “meta-learning the tightest bounds” in Section 4 mean. As a result, I do not understand how the numbers being plotted Figure 3 were generated and how to interpret them. It would be good if the paper provided more details to distinguish PAC-Bayes in the meta-learning setting with PAC-Bayes in the classical iid setting. For instance, Equation 6 shows that the p_Delta quantity from iid PAC-Bayes is a high-probability upper bound on the risk of a stochastic classifier drawn from Q. Is there an analog derivation for Equation 19 i.e., is the quantity an upper bound for some classifier’s risk? Lines 259-260 appears to be a big departure from the iid PAC-Bayes case. The convex function Delta here has parameters that depend on the data in the meta-learning task. This seemingly contradicts with the comment in line 147, which states that Delta cannot depend on data (this is also clear from Theorem 3, in which Delta needs to be fixed before seeing data). For Figure 3, if the goal is comparing generalization bounds with test error, it would be better to plot the two curves on the same panel / plot the difference between the two of them. Currently, it is hard to compare the generalization bound and test error because they are plotted on different panels and the limits/scales of the y axes do not align with each other. I have some smaller comments. In Equation 7, instead of kl(q, .), it should read barR(Q). The notation of small q is rather confusing, and out of scope (since it’s only in Theorem 4 that q is defined to be equal to barR(Q)). Overall, it might be better to remove the notation q and KL --- currently there is an inconsistency in Equation 7, since it’s using both q and KL(Q || P). The notation barR(Q) conveys the dependence of the empirical risk on data better than just q. 

Significance. Theorem 4/Corollary 3 are exciting theoretical results, of use to researchers searching for PAC-Bayes bound that closely approximate test error from above.  

Updates after initial rebuttal: The authors gave a concrete way of improving clarity in Section 4.

limitations_and_societal_impact: A direction for future work is that, does Theorem 4 mean that the best option is to use Catoni’s definition of Delta, allowing for different betas using some union bound argument? 

Regarding potential negative societal impact, PAC-Bayes bounds are used to derive/certify the quality of data-driven classifiers, so they have the potential to make unfair classification decisions against protected populations.
review_title: null

Meta-review: This work deepens our understanding of PAC-Bayes bounds. While the study is mostly exploratory, and perhaps unconventional for a NeurIPS paper, the reviewers believe that there is clear value to the community, as do I. The connections studied in this work are interesting and have pedagogical value, and it is quite likely that interesting discussions will come out of this work. While the open questions/problems are not yet resolved, the understanding gained may lead us closer to their being resolved. In more detail, Theorem 4 is quite interesting (and one reviewer mentioned that the proof checks out). Especially from the discussion phase, all reviewers support acceptance of this paper. This paper will make for an interesting contribution to the NeurIPS proceedings, and I hope serve as a great reference for future works as well.
Decision: Accept (Poster)