How Tight Can PAC-Bayes be in the Small Data Regime?
Authors: Andrew Y. K. Foong
Wessel Bruinsma
David R. Burt
Richard E Turner
Venue: NeurIPS 2021 Poster (2021)
Keywords: PAC-Bayes
learning theory
generalization

Abstract: In this paper, we investigate the question: _Given a small number of datapoints, for example $N = 30$, how tight can PAC-Bayes and test set bounds be made?_ For such small datasets, test set bounds adversely affect generalisation performance by withholding data from the training procedure. In this setting, PAC-Bayes bounds are especially attractive, due to their ability to use all the data to simultaneously learn a posterior and bound its generalisation risk. We focus on the case of i.i.d. data with a bounded loss and consider the generic PAC-Bayes theorem of Germain et al. While their theorem is known to recover many existing PAC-Bayes bounds, it is unclear what the tightest bound derivable from their framework is. For a fixed learning algorithm and dataset, we show that the tightest possible bound coincides with a bound considered by Catoni; and, in the more natural case of distributions over datasets, we establish a lower bound on the best bound achievable in expectation. Interestingly, this lower bound recovers the Chernoff test set bound if the posterior is equal to the prior. Moreover, to illustrate how tight these bounds can be, we study synthetic one-dimensional classification tasks in which it is feasible to meta-learn both the prior and the form of the bound to numerically optimise for the tightest bounds possible. We find that in this simple, controlled scenario, PAC-Bayes bounds are competitive with comparable, commonly used Chernoff test set bounds. However, the sharpest test set bounds still lead to better guarantees on the generalisation error than the PAC-Bayes bounds we consider.

How Tight Can PAC-Bayes be in the Small Data Regime?
Andrew Y. K. Foong" University of Cambridge 7kf210cam ac uk
Wessel P. Bruinsma" University of Cambridge Invenia Labs wpb230cam ac
David R. Burt University Cambridge drb620cam. ac uk
Richard E. Turner University of Cambridge ret260cam ac uk
Abstract
In this paper, investigate the question: Given small number of datapoints, for example = 30, how tight can PAC-Bayes and test set bounds be made? For such small datasets, test set bounds adversely affect generalisation performance by withholding data from the training procedure. In this setting, PAC-Bayes bounds are especially attractive, due their ability to all the data to simultaneously learn a posterior and bound its generalisation risk. We focus on the case of i.i.d. data with bounded loss and consider the generic PAC-Bayes theorem of Germain et al. While their theorem is known to recover many existing PAC-Bayes bounds, it is unclear what the tightest bound derivable from their framework is. For a fixed learning algorithm and dataset, we show that the tightest possible bound coincides with a bound considered by Catoni; and, in the more natural case of distributions over datasets, we establish a lower bound on the best bound achievable in expectation. Interestingly, this lower bound recovers the Chernoff test bound if the posterior is equal to the prior. Moreover, to illustrate how tight these bounds can be, we study synthetic one-dimensional classification tasks in which feasible to meta-learn both the prior and the form of the bound to numerically optimise for the tightest bounds possible. We find that this simple, controlled scenario, PAC-Baye Bayess bounds are competitive with comparable, commonly used Chernoff test set bounds. However, the sharpest test set bounds still lead better guarantees on the generalisation error than the PAC-Bayes bounds we consider.
Introduction
Generalisation bounds are of both practical and theoretical importance. Practically, tight bounds provide certificates that algorithms will perform well unseen data. Theoretically, the bounds and underlying proof techniques can help explain the phenomenon of learning. Among the tightest known bounds PAC-Bayes (McAllester, 1999) and test bounds (Langford, 2002). In this paper, we investigate their numerical tightness when applied to small datasets (N s 30-60 datapoints). The comparison between PAC-Bayes and test bounds is particularly interesting in this setting as one cannot discard data to compute a test set bound without significantly harming post-training performance due a reduced training set size. PAC-Bayes the other hand provides valid bounds while using all of the data for learning, since it provides bounds that hold uniformly. The small
Equal contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

data setting can also be quite different from the big data setting, as lower-order terms in PAC-Bayes bounds have a non-negligible contribution, and the detailed structure of the bound becomes important.
Fortunately, we do not have to study each PAC-Bayes bound separately: remarkably. Germain et al. (2009) showed that wide range of bounds can be obtained as special cases of a single generic PAC-Bayes theorem that captures the central ideas of many PAC-Bayes proofs (see also Bégin et al. (2016)). This theorem has a free parameter: it holds for any convex function, A. By choosing A appropriately, one can recover the well-known bounds of Langford and Seeger (2001), Catoni (2007) and other bounds. We focus on two questions related this set-up. First, what is the tightest bound achievable by any convex function A? An answer would characterise the limits of the generic BAC-Bayes theorem, and thereby of a wide range of bounds, by telling us how much improvement could be obtained before new ideas or assumptions are needed. Second, since test set bounds are the de facto standard for larger datasets, but PAC-Bayes has benefits when N is small, we ask: in the small data regime, can PAC-Bayes be tighter than test set bounds?
In Section 3, Theorem 4, we show that in the (artificial) case when A can be chosen depending on the dataset (without taking a union bound), the tightest version of the generic PAC-Bayes theorem is obtained by one of the Catoni bounds (Catoni, 2007). In the more realistic case when A must be chosen before sampling the dataset, we do not fully characterise the tightest bound, but in Corollary 3 we lower bound the tightest bound achievable (in expectation) with any A. We also provide numerical evidence in Figure 2 that suggests this lower bound can in some cases be attained, by flexibly parameterising a convex function A with a constrained neural network. Interestingly. this lower bound coincides with removing lower-order term from the Langford and Seeger (2001) bound (something that Langford (2002) conjectured was possible), and relaxes to the well-known Chernoff test set bound (see Theorem 2 below) when the PAC-Bayes posterior is equal to the prior.
In Section 4, we investigate the tightness of PAC-Bayes and test set bounds in synthetic ID classification. The goal of this experiment is to find out how tight the bounds could be made in principle. We use meta-learning producing meta-learners that are trained to optimise the value of the bounds on this task distribution. We find that, in this setting. PAC-Bayes can be competitive with the Chernoff test set bound, but is outperformed by the binomial tail test set bound, of which the Chernoff bound is a relaxation. This suggests that, for standard PAC-Bayes to be quantitatively competitive with the best test set bounds on small datasets, new proof technique leading to bounds that gracefully relax to the binomial tail bound is required. Code to reproduce all experiments can be found at https:/ / htt//ggtthttt git.ttt........ com/ hhtp///abrbieeeeee
adapt all aspects of the bounds and learning algorithms,
pappppaaaeeeeaa tiwpressttgttttessstte small-dats
2 Background and Related Work
We consider supervised learning. Let X' and y denote the input space and output space, and let
Z = x'x Assume there is an (unknown) probability measure" D over Z, with the dataset S ~ D& Denote the hypothesis space by H C y A learning algorithm is then a map n + H. In PAC- Bayes, we also consider maps z + M1 where Mj is the set of probability measures on its argument. The performance of hypothesis h E H is measured by a loss loss function E: Z x H. - [0. 1]. The (generalisation) risk of h is (h) = ((z.))-D[{(( y), h)] and its empirical risk on S is (h( = tt (z.))s E((x, y), h). For Q E (H) its (generalisation Gibbs) risk is RQ( = EnNo (h)) and its empirical (Gibbs) risk is (Q) = En-ol [R (h)]. In PAC-Bayes, we usually fix prior P (M)... chosen without reference to S and learn posterior Q E Mi(H) which can depend on S. The Kl--diergeecee between Q and P is defined as (T](Q)))) = log de dQ if Q < P and oc otherwise. Let C' denote the set of proper, convex, lower semicontinuous (L.s.c.) functions I22 + E (+oo); if convex function's 's domain a subset of IR², extend it to all of R with the value +oo. See Appendix C for more details on convex analysis, which we use in Section 3.
Test Set Bounds. Test set bounds rely on a subset of data which is not used to select the hypothesis, called a test set or held-out set. Let = Strain U Stost, with |S| = N, |Strainl = Nerain and | = Niest. In Theorems 1 and 2, we assume h is chosen independently of Stsst For the zero- one loss, É((x, y), h) = 1[h(x) * y) we have that Nisest (h) is a binomial random variable with parameters (Nrest (h)). This leads to the following simple bound, which, for l E {0, 1). is tight among test set bounds:
We will colloquially refer to measures on sets without specifying a a o-algebra. We implicitly assume functions measurable with respect to the o-algebras on which the relevant measures are defined.

---

Theorem (Binomial tail test set bound, Langford, 2005, Theorem 3.3). (et k, = sup {p= 8 - Ei= (1) pp)--p))-i- For any h E H. l E {0, 1) and à E (0, 1).
Pr [RD (1) S ENNest Neet Rs (h), 2 1 - 8.
(1)
Often, looser bounds with a simpler form are applied. These can be obtained via the Chernoff method:
Theorem (Chernoff test set bound, Langford, 2005, Corollary 3.7). For q.P E [0, 11, let k)(g,p) = q log 1 + (1 q) log H For any E H, l E [0, and d E (0, 1),
Pr (I. (h), (b)) S Newcet log !) 2 1--6.
(2)
PAC-Bayes Bounds. The PAC-Bayes approach bounds the generalisation Gibbs risk of stochastic classifiers, and does not require discarding data, as all the data can be used to choose the posterior, while still obtaining a valid generalisation bound. Since the seminal paper of McAllester (1999), a large variety of PAC-Bayes bounds have been derived. Germain et al. (2009) prove very general form of the PAC-Bayes theorem which encompasses many of these (see also Bégin et al. (2016) and Rivasplata et al. (2020)). Their proof technique consists of a series of incqualities shared by PAC-Bayes proof's (Jensen's ss change of measure, Markov's 's, supremum over risk"), and reveals their common structure. Thus understanding the properties of this generic theorem can give insight into many PAC- -Byye bounds at once:
Theorem 3 (Generic PAC-Bayes theorem, Bégin et al. (2016) and Germain et al. (2009)). Fix P E Mi MH)). E [0, 1), 5 (0, 1), and A proper, convex, L...c. function [0, 1] + R U (+00).
Then
Pr ((V)) (t) S + [L(QIP) + log Ia(N) where Ia(N)= == suPre(o.1)
2 1 11160 -,
(3)
(1)
We lose generality in assuming A(g, -) is monotonically increasing for all q E [0,1], 1]. i.e. for any convex we can define a A that is monotonically increasing in its second argument and produces bound that is at least tight as the bound produced by A. See Appendix D for proof.
Remark 1.
Note that the PAC-Bayes bound holds simultaneously for all posteriors Q, and hence is valid even when Q is chosen by minimising the bound. For completeness, provide a proof of Theorem 3 in Appendix B. Following Germain et al. (2009), we briefly recap some of the bounds that can be recovered as special cases (or looser versions) of Theorem 3. Setting A(g,p) Cz(g.p) = -log(1 p(c-8 - 1)) Bq for 0, we recover the Catoni bounds:
Corollary (Catoni, 2007, Theorem 1.2.6). For any O, Pr (VQ) (Q) S - [| 1-exp exp (-BRs(Q) + (KL(QIIP) + log f))) 2 2- (4)
This specifies a bound for every value of 3 > 0. If we instead choose A p) = kllg, p). we obtain the bound of Langford and Seeger (2001), also called the PAC-Bayes-ki bound, but with the slightly sharper dependence on N established by Maurer (2004):
Corollary (Langford and Seeger, 2001, Theorem 3, Maurer, 2004, Theorem 5).
Pr (QAQ) (Q))s(Q), (Q) S 1/4 [KT(QIIP) log 2/N
2 1 8.
(5)
Corollary 2 is actually very slightly looser than Theorem 3 with A = kl, since Maurer (2004) upper bounds Za( (N) by 2/N using Stirling's formula. 5 The Catoni and PAC-Bayes-kl bounds are among the tightest PAC-Bayes bounds known and have been applied in settings where numerical tightness key, such as obtaining generalisation bounds for stochastie neural networks (Dziugaite & Roy, 2017: Zhou et al., 2019). Many other bounds be obtained by loosening these bounds. Applying Pinsker's 's inequality kl(g. p) 2 2(g- - p)2 to Equation (5) yields the "square-root" version of the
'The supremum over risk step was introduced in Bégin et al. (2016), although for certain A it can be omitted. 'We state a simpler version of their result WLOG, absorbing a free parameter into the function A. 'Maurer (2004) only proves this bound for N 2 8, but the cases where 1 < N < 7 can be easily verified numerically (Germain et al., 2015, Lemma 19).
3

---

Potential limits of the generic PAC-Bayes theorem (Thevrem 3)
Test set bounds
Catoni: A = CB
EA?
A
(Corollary 1)
Q-PP P
Q=P
PAC-B.-kI: A= kl
B
conjectured PAC-B.-kl
Chernoff
Binomial tail (Theorem
(Corollary 2)
(Theorem
(Corollary 3)
(Theorem
Figure I: Illustration of the relationship between various PAC-Bayes and test set bounds; Section 3. It unclear if there always exists A that recovers the conjectured PAC-Bayes -ress-l bound (and hence the Chernoff' bound when Q = P: see Open Problem 1), but there certainly does not exist a that recovers the Binomial tail bound when Q = P.
PAC- Bayes theorem (McAllester. 1999, 2003). The "PAC- BAAC-Bayes-' (Thiemann et al., 2017) and "PAC- PPAC-Bayes-quadratic bounds (Rivasplata al., 2019) can be derived as loosened versions of the PAC-Bayess bound using the inequality kl(g.p) )) 2 (q p)2 (2p), valid for < p. The "linear"
bound in McAllester (201)) can be derived by loosening the Catoni bound using: Cs(g. S
2 1-3/2 (q + AA), which is valid for $ (0,
How Tight Are PAC-Bayes Bounds? A fundamental question we can ask about generalisation bound is how tight it is, and whether can be tightened. Comparing the PAC-Bayes-ki and Chernoff test set bounds when Q P (so the PAC-Bayes bound essentially becomes test set bound) shows they are identical except for a NN/N on the RHS of the PAC-Bayes-kl bound. Whether this term (or similar discrepancies between PAC-Bayes and Occam bounds (Langford, 2002. Corollary 4.6.2); see Appendix A) can be removed has been an open question since Langford (2002, Problem 6.1.2). Maurer (2004) reduced this term its current form, improving Seeger (2001). Interestingly, Germain et al. (2009, Proposition 2. shows that the expression obtained by dropping log (2/N)/N from the PAC-Bayes- bound is identical to that obtained by illegally minimising the Catoni bound with respect to 3; Catoni (2007, Theorem 1.2.8) shows that a union bound can be used to. in a legal way, approximately optimise with respect to | at the cost of an additional lower order term. The Chernoff test set bound is itself a looser version of the binomial tail bound, raising the question of whether PAC-Bayes bound can be found that reduces the binomial tail bound when Q = P. We provide new insights into these problems in Section 3.
work by Langford and
Researchers have also compared PAC-Bayes bounds numerically actual learning problems. Lang- ford (2005) and Germain et al. (2009) were able to obtain reasonable guarantees on small datasets. However, Langford (2005) found that on datasets with N x 145, PAC-Bayes was outperformed by test set bounds. Dziugaite and Roy (2017), Langford and Caruana (2001), and Pérez-Ortiz et al. (2021) provide non-vacuous bounds for neural networks using PAC-Bayes. Even so, Dziugaite et al. (2021) states that tighter bounds would be obtained using a test set instead. In Section 4 we find that if the bounds and learning algorithms are optimised for task distribution, PAC-Bayes enough to compete with the Chernoff test set bound, but not the binomial tail test set bound.
be tight
3 Characterising the Limits of the Generic PAC-Bayes Proof Technique
This section establishes our main theoretical contributions, which characterise the limits of the generic PAC-Bayes theorem (Theorem 3). For convex A C, Theorem 3 gives high-probability upper bound on A (Q)s(Q), RD(()). (((Q). Define B[f y] = sup {p 10 fp) I y} for f: [0, 1] - R and y E R, where we take sup 2 = 1. This upper bound (Theorem 3) can be "inverted" to obtain a bigh-probability upper bound on (Q):): with probability at least 1 - 8, for all Q E M1.)).
(Q( PA where Pa (Q), -), > (KL(QIIP) + log Ia(N)
(6)
Since (6) holds for all A C, natural question is: Which A minimises PA This would characterise how tight, numerically. PAC-Bayes theorems can be made without introducing ideas beyond those needed to prove the bounds stated in Section 2. Before considering the case when A is selected before observing S ~ D.N we first characterise the optimal A in the simplified scenario where A can depend on the dataset S and the posterior Q (Theorem 4). This setting is artificial, since choosing
6That is, optimising 3 depending on the dataset S without taking union bound.

---

10a
10
10-1
10
10-1
Ele
10
10
10-2
10
Elpal
10-²
10-1
10
10
10'
10
(b)
10F (c)
(d)
10F
Iteration
Iteratio
Iteration
Iteration
Figure 2: The tightest Catoni bound is the optimal generic PAC--Bayes bound for a fixed dataset, but not the optimal expected bound for a random dataset. We optimise convex function with H hidden units to minimise Pa with ô N. = 30. (a) and (b) consider fixed q and KL (precise values below) and show the difference with the best Catoni bound (Theorem 4); (c) and (d) consider random ạ and KT, and show the expected difference with the conjectured PAC-Bayes-ki bound (Corollary 3). Shaded regions show the minimum and maximum over ten initialisations. All plots show the PAC-Bayes-kr bound (dotted red) and (c) and (d) show the optimal Catoni bound with parameter 3 (dashed orange). All runs quickly converged to non-vacuous values. (a): (g. KL)
(2%. 1). S R 2.24, H 256. (b): (g. KL) (5%, 2). 8 1.84, H 256. (c): (q, KL) E ((2%) 1), (5%.2) 2)} uniformly, 3 1.99. H 512. (d): (g. KL) E {(30%, 1). (40%, 50)3 uniformly, 3" = 2.32, H 1024.
A based on S (without taking a union bound) does not yield a valid generalisation bound. However, using Theorem 4 as a building block, we later derive a lower bound on the best possible generic PAC-Bayes bound (in expectation) in the more realistic case when we cannot choose A based on S (Corollary 3). We then connect this lower bound to various existing PAC-Bayes and test set bounds. An overview is shown in Figure 1. We now state our first result:
Theorem 4. Given any fixed dataset S and any Q.P E MM(H), the tightest Catoni bound is as tight as the tightest bound possible within the generic PAC-Bayes theorem (Theorem 3). Precisely, let A E C and d (0, 1). Choose some fixed values for Rs(Q) q E [0, 1] and (L(Q))P) KL E [0, o0). I > 0, then there exists a 3 E (0, 00) such that Ps 2 PC,, where p is defined in Equation (6). Moreover, if = O, then PA= 2 -iim PC..
Remark 2. By Theorem 4. for all A E C, we have PA 2 inf Pc,, and, by Proposition 2.1 of Germain et al. (2009), 3= Pc, = Blkd(q ), N (KL++ log b).. Hence, for all A E C, it holds that PA > B [l[g -), N (KL+ log !)}, which is also shown directly in the proof of Theorem 4 (Equation (17)). Note that optimising / in this way is illegal in the general case when the dataset S (and hence q and KI.) is stochastic, and would typically require a union bound to be valid.
We defer the proof of Theorem 4 to the end of this section. We numerically verify Theorem by optimising PA with respect to arbitrary convex A for various settings of fixed q and KL. To parametrise a convex A, we use a ane-hidden--eee layer and softplus nonlinearities. The inversion performed by B is approximated numerically by discretising the second argument of A and detecting an uperossing. Gradients are then approximated using the inverse function theorem: de B[fa,c(0)) = (0oc(0) for details.? 7 Figures 2a and 2b show the difference between the numerically optimised A and the best Catoni bound for two settings of fixed E [0, 1] and KL E [0, co). In both cases, PA innf Pc; appears to converge to zero from above, as expected from Theorem 4. Interestingly. Appendix F shows that the learned A can deviate substantially from Cz. suggesting that there are choices for A besides Catoni's which achieve inf PA.
neural network with positive weights at the output
(Ox:))/a See Appendix F
For any fixed dataset S. Theorem 4 states that the tightest bound is one of the Catoni bounds; precisely: inf PA = inf Pc,, Note that the optimal value of 3 may depend on the dataset S. The more interesting question is whether, when S ~ D is sampled randomly, one of the Catoni bounds can still achieve the tightest bound (in expectation) for a single value of 3 that is chosen before sampling S. The answer is no: Figure 2d gives a numerical counterexample where sec BPP E Pal infase aso B-Pc2l- Since the Catoni family of bounds cannot generally achieve the tightest bound in expectation, which A do? And how tight is inf sec E EpAA? Whilst we do not have full answer, we establish a simple lower bound on inf Elpa]. Define the conjectured
7 Numerical inversion of A when A = kl has been considered by many authors, including Dziugaite and Roy (2017) who use Newton's method and Majumdar and Goldstein (2018) who propose using convex optimisation methods. However. to our knowledge, the specific inversion algorithm we propose for general convex A, along with the method for backpropagating through the inverse, novel in the PAC-Bayes setting.
5

---

PAC- PAC-Bayes-kl bound p as the quantity from Remark 2, which equals the PAC-Bayes-ki bound without the N log (NV) term on the RHS:
= ([)( ), N (KL(QI)P) + log #)
The conjectured PAC-Bayes- -l bound has not been proven to be a valid generalisation bound. When S ~ DV is random, Remark 2 tells us that anf Pa 2 a.s. Taking expectations and interchanging the expectation and infimum yields the following corollary:
Corollary 3. Consider the setting from Theorem 3. Then the expected conjectured PAC- PAC-Bayes-k bound Elp) gives a lower bound on all expected generalisation bounds obtained through the generic PAC-Bayes theorem (Theorem 3). That is, for any distribution over datasets, any prior, and any learning algorithm.
(8) Moreover, there exists distribution over datasets, prior, and a posterior such that equality holds. For example, let (x, y) be constant almost surely, which reduces to the setting of Theorem 4. Note that in (8), A is chosen not depending on S, which leads valid generalisation bound the LHS.
inf ETTAl Ely)
Figure| shows how Corollary 3 fits into the picture so far. The conjectured PAC-Bayes-kl bound is at least tight as the bound achieved by any A, but Corollary 3 does not establish the existence of a A which achieves it. Corollary 3 has practical utility: the conjectured PAC-Bayes-ki bound can be used prove optimality of a choice of A. Specifically, if a practitioner computes valid bound based on the generic PAC-Bayes theorem, and finds that it is close to the conjectured PAC-Bayes-ke bound, they can be assured by Corollary 3 that they would not have gotten a much better bound (in expectation) with any other choice of A. Conversely, the conjectured PAC-Bayes-kl bound can quantify potential slack in the bound due to a suboptimal choice of A. Appendix H considers an example of this application of Corollary in the simplified scenario where Rs
2 almost surely.
The conjectured
bound also recovers the Chernoff test set bound (Theorem 2) when setting Q P. Since the binomial tail bound (Theorem 1) is strictly tighter than the Chernoff bound, this shows there does not exist A such that the generic PAC- BByee bound (Theorem 3) recovers the Binomial tail bound when Q P; this is illustrated in Figure 1. What is unclear, however, is whether there always exists a A such that Theorem recovers the Chernoff test set bound; or, alternatively, such that the conjectured PAC- ACC-Bayes-kl bound is attained. A positive answer to the latter would establish that the conjectured PAC-Bayes-K bound is a valid generalisation bound. 8 As a first piece of evidence, the traces from Figures 2c and 2d suggest that convex function could actually achieve Ely); see Appendix G for more traces. We leave a full resolution of this question as an open problem; see Section 5. Interestingly, Figure 2c shows that Catoni bound is sometimes nearly optimal even in the stochastic case; we will see another example of this in Figure 3.
We end this section with the proof of Theorem 4. Recall that the Catoni family of bounds follows from Theorem 3 by considering A(g, p) = Cs(g. p) = Fp 3q with Fp(p) == - log(p(e - 1) 1) and 8 > O. To simplify the notation, we denote a = v (KL + log 4) E (0, oo).
Proof of Theorem 4. The proof proceeds in three steps. In the first two steps, we lower bound 1 log IA (N) and upper bound A. In the third step, we use these bounds lower bound B[A ), + N IogIa(N)) and identify the result with particular Catoni bound.
Lower bound A(g.p) = A (q. = supe,.SEER (Cof + cpP - A (cy, (p)), where * denotes convex conjugation.
N INV) Since A C, it is equal to its own double convex conjugate:
Let X ~ Bin(r,N). Then
[N = suprejo.11 Ele NA(X/NN) = sup 1 El
sup X4 (cne))))
(9)
2 suprejo.1] sup
ER No. NA S
(10)
where Efea,x] (r(e - 1) + 1) is the moment-generating function of X. Consequently, taking log, dividing by N, and noting that y log E[ea =-F-c,(")
N log IA (N) 2 A where A == sup suPe A (cg; cp) + sup - FFa, (11)
By Remark 2, Pa 2 p. pp Elgl implies that PA p a.s., meaning that p is a valid gen. bound.

---

Upper bound on A: We upper bound A by making A as small as possible without exceeding the supremum from (11). Note that A finite, because A is proper. Define Á' as follows: Á sn(c; (p) = - A + suppejo.1|Cp7 F-c, (r)). Note that A is proper, convex as a pointwise supremum of convex functions, and l.s.c. as a supremum of Ls..c functions. In fact, Á is finite for
all imputs. As the notation suggests, define Á = (Â+)*. Then Á is indeed the convex conjugate of A, because A E C, so it is equal to its own double convex conjugate. Moreover,
Â(q. p) A + supe, sup,,,,, (G/ + cpp - suprejo.1(Gpr Fra,(r)]]
(12)
A + SuPe,ER leg + SuPE,ER (Gpp- F-,, (c,]]
(13)
= A + suPe,eR legg + FFc,(()),,
(14)
by observing that + F-c, (p) E C. so it is equal to its own double convex conjugate. Therefore,
p(g.p) = A + SUPE,RR C-e, (1.P) A + kl(g.))
(15)
where (i) follows from a direct computation; see Lemma E. (Appendix E). Claim: For all g.p E [0, 1]. Š(q. p) 2 A(1. p). This follows from the definitions and finiteness of À and A: for all Cg R.
(cg cp) + sup - -Fc, (r)) = A 2 - Acg. Cp) + -uppretonneerr- - (ra, (16)
which means that A I A", so Á 2 A by the order-reversing property of the convex conjugate. Conclusion: Assume that FA < 1; otherwise, any B 0 works. To begin with, use the previous steps:
Pa B[ .) + 1. log IA (N)) 2 BJ²(q, .).a + A] (15) Blklqg ). = p. (17)
(II), claim
Since a > 0. clearly p q, so 0 S 9 < P 1. Hence, if > O, then there exists B > 0 such that kl(g. p) = Cp(g, p) (Lemma E.2; Appendix E). Using that p - Cg.g. is continuous and strictly
increasing for all B > 0, we have that p B(Ca(4, a). so
Pa 2 BlCa(g. a) @ B[Ca(q. -),a N log Ic, (N) Pc.
(18)
where (i) uses that 1 Io, (N) = (Lemma E.3; Appendix E). If q = 0. then kl p) = limg-+oo CO p) (Lemma E.2; Appendix E), so PA Z B lim Co(O,) :), a]. and conclude like in (18)
N
using Lemma E.4 (Appendix E).
8-000
4 Meta-Learning the Tightest Bounds for Synthetic Classification
We now consider, for a particular distribution over tasks, how tight each bound can be made in expectation. Two questions naturally arise: Which PAC-Bayes bounds are rightest? and Can PAC- Bayes bounds be tighter than test set bounds? While test set bounds have traditionally been considered tighter than PAC-Bayes bounds, here we work in the small data regime where a substantial proportion of the data must be removed to form a test set, which could impact generalisation performance and hence lead to worse bounds. Our goal is not to compare these bounds when using standard practice, but to see how tight they can be in principle if we use every tool in our toolbox to minimise the expected bounds. 9 While these optimisations will be impractical for large models and datasets, they can provide some statistical insight.
Learning Algorithm. Certain learning algorithms may work better with test set bounds, and others with PAC-Bayes bounds. Instead of choosing a fixed algorithm, we mela-learn (Schmidhuber. 1987; Thrun& & Pratt, 2012) separate algorithms to optimise each bound in expectation: we parametrise a hypothesis space He and a posterior map Qe: : NN + .M1 (Ha) by a finite dimensional vector 6, which is trained to optimise the expected bound (we will amalgamate all meta-lcarnable parameters into the single vector 0). This is explained in more detail below. This way, we obtain algorithms that are optimised for each bound. After meta-learning, we can further refine each PAC- MAC-Bayes posterior by minimising the PAC-Bayes bound, see Appendix I.4.
Task Distribution. In meta-learning, we refer to a data-generating distribution D and dataset S D as lask. We consider distribution over tasks, D ~ T, where T is a distribution over
9Our goal here is to minimise high probability PAC-Bayes and test set bounds in expectation. See Dziugaite al. (2021, Appendix J) for relevant discussion.
7

---

geteereeea distributions, and aim to find the best expected bounds for this distribution achievable by an optimised algorithm. 10 We choose especially simple learning tasks synthetic 1-dimensional binary classification problems, generated by thresholding Gaussian process (GP) samples - which allows us to fully control the task distribution and easily inspect predictive distributions visually to diagnose learning. Appendix 1.1 contains full details.
Priors. The choice of prior is crucial in PAC-Bayes, and the role of data-dependent priors (DDPs) (Ambroladze et al., 2007; increased attention. This involves splitting the dataset into N = Npriirr + NNisk datapoints. The DDP is allowed to depend on the prior set of size N Nprior (standard priors use N Vpcior 0), and the risk bound is computed on the risk set of size Nrisk- Crucially, the bound is valid when the posterior depends on all N datapoints. Recently, Dziugaite et al. (2021) showed that DDPs can lead to tighter expected bounds than the optimal non-data-dependent prior, and are sometimes even required to obtain non-vacuous bounds. Pérez-Ortiz et al. (2021) also report much tighter bounds when using DDPs. In our experiments we meta-learn a DDP as a map from the prior set to the prior. Pa: Z Nprior + MM (H). To compare PAC-Bayee DDPs against test set bounds, we sweep the prior/train set proportion from 0 to 0.8 and see what the tightest value obtained is. Strictly this would require union bound over the proportions, but here we are primarily interested in comparing the various bounds against each other on an even footing and vary the proportion for illustrative purposes.
et al., 2012: Pérez-Ortiz et al., 2021) has been gaining
The Meta-Learning Objective. We now discuss meta-learning in more detail. During meta-training, 0 is trained to optimise the expected PAC-Bayes generalisation bound over the task distribution:
ES-TES_DN B| RRs,,.. (S), -), 1 ( Po (proo) )) + log Tap (Nana)
)] (19)
N.sk
where the f in Ag denotes that some bounds (Catoni and learned convex function) have lear-lea parameters. Alternatively, for a meta-learner that minimises a test set bound, the objective is simply ED-.ES.D R.s... (Strann))) since all test set bounds are monotonic in the test set risk. We use the 0/1 loss. As the classifiers are stochastic, the empirical risk is still differentiable with respect to 0. In contrast to PAC-Bayes, the predictor that minimises the test set bound can be made deterministic after 0 is learned, since it tends to eventually learn essentially deterministic classifiers; see Appendix 1.2. We sample T = S0 000 tasks D. ~ T, with associated datasets S, ~ Df" These form the meta-trainset. Additionally, we sample 1024 tasks that form meta-testser used to estimate the average bounds over T after meta- training. For the PAC-Bayes bounds, we then Monte Carlo estimate (19). Hence, the final objective for PAC-Bayes meta-leamer is (a minibatched version of):
+ -T= B (Qo(S.)), )), Neisk
(KL(Qu()))IPd(Ss.o))) )) + log Ioa (Nask)
).
(20)
Similarly, the objective for the test set bound meta-learner is + Ex= RSS.. (rr(tn) The bounds we compute on datasets in the meta-testset, after meta-training is complete and 9 is frozen, are valid even though 0 was optimised on the meta-trainset. This highlights a contrast between our procedure and the PAC-Bayes meta-learning in Amit and Meir (2018), Liu et al. (2021), and Rothfuss et al. (2021) and Farid and Majumdar (2021). While those works use PAC-Bayes to analyse generalisation of a meta-learner on new tasks, we use PAC-Bayes to analyse generalisation within individual tasks.
Parametrising the Meta-Learner and Hypothesis Space. We now describe how to parametrise the hypothesis space He and the maps Qs, Po. We meta-learn a feature map de: IR + I k and choose"" Hig = (h. : (z) = sign (w, (z)), )) w E IR K J. For Qo and Pe Gaussian, this hypothesis space allows us to compute the empirical Gibbs risk without Monte Carlo integration; see Appendix 1.3 for details. For the form of Qg. we take inspiration from Neural Processes (NPs) (Garnelo, Rosenbaum, et al., 2018; Garnelo, Schwarz, et al., 2018; Kim et al., 2019). NPs use neural networks to flexibly parametrise a map from datasets to predictive distributions that respects the permutation invariance of datasets (Zaheer al., 2017). They are regularly benchmarked on ID leaannng tasks, making them ideally suited. We make a straightforward modification to NPs to make them output Gaussian measures over weight vectors E R Hence, they act as parametrisable maps from N to the set of Gaussian measures on K
We could also consider drawing all datasets from single task D. which would more directly match Section 3. We regard this case as less interesting, since we would often want a bound to perform well on a variety of tasks.
The dimensionality K is fixed a priori.
8

---

Generalisation Bound
Generalisation Risk
Generalisation Bound
Generalisation Risk
0.40
0.08
0.25
0.05
0.35
0.20
0.04
0.30
Risk
0.15
0.03
0.25
0.05
0.20
0.04
0.10
0.02
0.6
0.8
0.2
0.0
0.6
Priantrain proportion
Priantrain proportion
Priontrain proportion
Pricrttrain proportion
(a) N 30 datapoints.
(b) N 60 datapoints.
Figure 3: Average generalisation bound and actual generalisation risk (# two standard errors) for CNN-NP neta-leammrs trained to optimise Catoni (,), PAC- AAC--ayes-kl kl (L), conjectured PAC- Ba--s-yyskk (0), Iearned convex ()), Chernoff' test set (4), and binomial tail test set (+) bounds. Catoni, conjectured PAC-Bayes Bayes- kl, and learned convex overlap. The generalisation risks for Chernoff and binornal tail test set bounds are identical as they share the same meta-learner; only the hound computation differs. The bounds are valid with failure probability
= 0.1 except for conjectured PAC- PAC-Bayes-ke which should be a lower bound on the best bound achievable with Theorem 3. Corresponding plots for the MLP-NP are in Appendix J.2.
tal//hemoff bound: 0200 91, gen. risk: 0.087, test risk 0.06.
Gen. bound: o 22, gen. risk: 0,040, KL; 1.43.
1.00
1.00
W
X
0.75
0.50
0.50
0.00
0.00
-2.0
-1.5
-1.0
-0.5
0.0
0.5
1.0
1.5
2.0
-1.5
-1.0
-0.5
0.0
0.5
3.0
1.5
2.0
(a) Binomial tail/Chernoff test set bounds, showing the learned hypothesis (-), the train set (X) of size 12 and the test set (X) of size 18.
(b) Learned convex bound with data-dependent prior. showing the prior (-) and posterior (-) predictive. prior set (X) of size 12 and risk set (X) of size 18.
Figure 4: Predictions on one of the ID datasets in the meta-test set with N = 30 and prior/rain proportion 0.4. For each method, we report the generalisation bound and actual generalisation risk. For the test model, we also show the risk on the test set, and for the AAC-Bayes model we show the -iveeieeeeecee The learned convex bound meta-learner has learned a DDP that provides a "first guess" given the prior set, which is then refined by the posterior. Figures for other PAC-Bayes bounds and datasets are provided in Appendix J.1.
We considered two kinds of NP, one based on multilayer perceptrons (MLP-NP) and another based on convolutional neural networks (CNN-NP) (detailed in Appendices 1.5 and 1.6) Although the MLP-NP is very flexible, the state-of-the- art in NPs on ID tasks is given by CNN-based NPs (Bruinsma et al., 2021a; Foong et al., 2020; Gordon et al., 2020). We use an architecture closely based on the Gaussian Neural Process (Bruinsma et al., 2021a), which outputs full-covariance Gaussians. As expected, we found the CNN-NP produce tighter (or comparable) average bounds the MLP-NP, while using far fewer parameters, and training much more reliably and quickly. This is because the CNN-NP is translation equivariant, and hence exploits key symmetry of the problem. Hence, we focus on the CNN-NP, but report some results for the MLP-NP in Appendix J.2. Hyperparameter details are given in Appendix 1.7.
Results. We show example classification tasks and average bounds on the meta-test set in Figures and 4. Note that the test set classifier became deterministic and makes hard predictions whereas the PAC-Bayes classifier shows uncertainty; see Appendix 1.2 for a discussion. The PAC-Bayes- bound is loosest, which is unsurprising it has optimisable parameters adapt to T. 12 Surprisingly, the results for Catoni, conjectured PAC-Bayes-kl, and learned convex are nearly identical. As long as optimisation has succeeded reasonably, this suggests empirically that, in light of Corollary one of the Catoni bounds may be very nearly optimal among all convex functions for this task distribution there is not much "slack" from choosing suboptimal A here. We also that the Catoni and learned convex bounds with prior proportion 0.4 are tighter than any Chernoff test set bound. Hence, PAC-Bayes can provide slightly tighter (or comparable) generalisation bounds Chernoff test set bound. However, we see that the binomial tail test set bound with 40% of the data used for the selecting the predictor and the remaining 60% used for evaluating the bound leads to
This is in contrast with usual applications of PAC- Bayes where one does not have a meta-datase with which to optimise parameters of the bound. In that setting, it can be an advantage to not have tunable parameters.

---

the tightest generalisation bounds overall. Corollary 3 sheds light on this behaviour: the optimal generic PAC-Bayes bound reduces, at best, to the Chernoff test set bound when the posterior equals the prior. However, the Chernoff bound is itself looser than the binomial tail bound. Of course, the posterior does not equal the prior here, but Corollary 3 indicates there is an extra source of looseness that PAC-Bayes has to overcome relative to the binomial tail bound. Finally, although the test set meta-learner leads to the tightest generalisation bounds, its generalisation risk is roughly double that of the PAC-Bayes meta-learner when the prior/train set proportion is 0.4.
Conclusions, Open Problems, and Limitations
PAC-Bayes presents a potentially attractive framework for obtaining tight generalisation bounds in the small-data regime. We have investigated the tightness of PAC-Bayes and test set bounds in this regime both theoretically and experimentally. Theoretically, we showed that the generic PAC- PAC-Bayes theorem of Germain et al. (2009) and Bégin et al. (2016) which encompasses wide range of PAC- Bayes bounds, cannot produce tighter bounds in expectation than the expression obtained by discarding the (//2/N)/NN term in the Langford and Seeger (2001) bound (i.e. the conjectured PAC-Bayes-kl bound; Corollary 3). Although we did not prove that the conjectured PAC-Bayes-ki bound is valid generalisation bound, numerical evidence suggests (Figures 2c and 2d) that there may exist a convex function A which achieves it, at least for the distributions over empirical risk and Kl--divegeence we considered. This suggests the following open problem:
Open Problem 1. For arbitrary distribution over datasets, does there exist choice of A such that the expected conjectured PAC-Bayes-kl bound is attained (Corollary 3)? If not, how close can one get to the expected conjectured PAC-Bayes-kl bound?
If such A exists, then that would imply the conjectured PAC-Bayes-kl bound is valid generalisation bound (see Section 3) and resolve Problem 6.1.2 of Langford (2002) in the affirmative.
We then considered, in controlled experimental setting where meta-learning all parameters of the bounds and learning algorithms was feasible, whether PAC-Bayes bounds could be tighter than test set bounds. Although we found PAC-Bayes competitive with Chernoff bounds, both were outperformed by the binomial tail test set bound. This motivates a second open problem:
Open Problem 2. Can a PAC-Bayes bound be found that relaxes gracefully to the binomial tail test set bound (Thherrm 1) when the posterior equal the prior?
Resolving these problems could have a significant impact on the tightness of PAC-Bayes applied to small-data, and clarify our understanding of the relationship between PAC-Bayes and test set bounds.
Limitations. In this paper, we concern ourselves with understanding the tightness of bounds in what might be called the standard PAC-Bayes setting of supervised learning: bounded losses, i.i.d. data, and Gibbs risk. We also focus on bounds that are first order in the sense that they rely only on the empirical Gibbs risk, though extending the analysis to consider other PAC-Bayes theorems (e.g. Rivasplata et al. (2020) and Tolstikhin and Seldin (2013)) would be of interest, especially with regards to Open Problems 1 and 2. For many practical applications in which performance guarantees are needed (e.g. health care), the i.i.d. assumption should be considered carefully, as it is likely an unrealistic simplification. Furthermore, Gibbs classifiers are less commonly used than deterministic classifiers in practice. To address these and other concerns, PAC-Bayes has been generalised in many directions beyond the scope of the standard setting we consider. Examples include bounds for non-i.i.d. data (Alquier& Guedj, 2018; Rivasplata et al., 2020; Seldin et al., 2012), unbounded losses (Germain et al., 2016), derandomised classifiers (Blanchard & Fleuret, 2007; Viallard et al., 2021), and Bayes risk (Germain et al., 2015; Masegosa et al., 2020). Bounds based on other divergences besides the KL have also been proposed (Alquier & Guedj. 2018; Bégin et al., 2016). As proof relies primarily on tools from convex analysis, and Jensen's 's inequality is ubiquitous in PAC- BaC-Bayes bounds, it would be interesting to see if our arguments can be extended beyond the limited setting we focus on.
Finally, our meta- veta-learning experiments only considered ID classification, and the results might not necessarily be representative of more realistic datasets. We also only consider Gaussian prior and posterior distributions in our experiments for the sake of tractability. Scaling up the experiments and considering more flexible distributions an important, but potentially challenging, avenue for future work.
10

---

Acknowledgements and Funding Transparency Statement
We would like thank Pierre Alquier and Yann Dubois for insightful discussions, John Langford for clarifying a remark on test set bounds, David Janz, Will Tebbutt, and Austin Tripp for providing helpful comments on a draft version of this paper, and Omar Rivasplata for helpful comments on an earlier version of this manuscript. Andrew Y. K. Foong gratefully acknowledges funding from a Trinity Hall Research Studentship and the George and Lilian Schiff' Foundation. Wessel P. Bruinsma was supported by the Engineering and Physical Research Council (studentship number 10436152). David R. Burt acknowledges funding from the Qualcomm Innovation Fellowship and the Williams College Herchel Smith Fellowship. Richard E. Turner is supported by Google, Amazon, ARM, Improbable, Microsoft, EPSRC grant EP/T005637/1, and the UKRI Centre for Doctoral Training in the Application of Artificial Intelligence to the study of Environmental Risks (AI4ER).
References
Alquier, P., & Guedj. B. (2018). Simpler PAC-Bayesian bounds for hostile data. Machine Learning, 107(5), 887-902 (cit. on p. 10).
Ambroladze, A., Parrado-Hernánder E., & Shawe-Taylos J. (2007). Tighter PAC-Bayes bounds. Advances in neural information processing systems (cit. on p. 8).
Amit, R., & Meir, R. (2018), Meta-learning by adjusting priors based on extended PAC-Bayes theory. International Conference on Machine Learning (cit. on p. 8).
Bégin, L., Germain, P., Laviolette, F., & Roy, J. (2016). PAC-Bayesian bounds based on the Rényi divergence. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, AISTATS (cit. on pp. 2, 3, 10, 14).
Blanchard, G., & Fleuret, F. (2007). Occam's ' hammer. International Conference on Computational Learning Theory, 112-126 (cit. p. 10).
Boucheron, S., Lugosi, G., & Massart, P. (2013). Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press. (Cit. p. 14).
Bruinsma, W. P., Requeima, J., Foong, A. Y. K., Gordon, J., & Turner, R. E. (2021a). The Gaussian neural process. Proceedings of the 3rd Symposium on Advances in Approximate Bayesian Inference (cit. on pp. 9, 25).
Bruinsma, W. P.. Requeima. J., Foong, A. Y., Gordon, J., & Turner, R. E. (2021b). The Gaussian neural
process - contributed talk. https wwwsellb. gi github. / assets talks/ /Bruinsma,
(Handout). - pdf. (Cit. p. 25)
Catoni, O. (2007). PAC- Bay-BByennnn supervised classificattin:: The thermodynamics of statistical learning. Institute of Mathematical Statistics, Beachwood Ohio, USA. (Cit. pp. 2-4, 17).
Cremer, C., Li, X., & Duvenaud, D. (2018). Inference suboptimality in variational autoencoders.
International Conference on Machine Learning, 1078-1086 (cit. on p. 24).
Dziugaite, G. K., Hsu, K., Gharbieh, W., Arpino, G., & Roy, D. (2021). On the role of data in PAC-Bayes. International Conference on Artificial Intellignnce and Statistics, 604-614 (cit.
pp. 4, 7, 8).
Dziugaite, G. K., & Roy, D. M. (2017). Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. Uncertainty in Artificial Intelligence, UAI (cit. on pp. 3-5, 19).
Farid, A., & Majumdar, A. (2021). PAC-bus: Meta-learning bounds via PAC-Bayes and uniform stability, arXiv preprint urXiv:2102.06588 (cit. on p. 8).
Foong, A. Y. K., Bruinsma, W. P., Gordon, J., Dubois, Y., Requeima, J., & Turner, R. F. (2020). Meta-learning stationary stochastic process prediction with convolutional neural processes (H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, & H. Lin, Eds.). Advances in Neural Information
Processing Systems (cit. on p. 9).
Garnelo, M.. Rosenbaum, D.. Maddison, C., Ramalho, T., Saxton, D.,, Shanahan, M. Teh, Y. W.. Rezende, D., & Eslami. S. A. (2018). Conditional neural processes. International Conference on Machine Learning, 1704-1713 (cit. on pp. 8, 24).

---

Garnelo, M.. Schwarz, J., Rosenbaum, D., Viola, F., Rezende, D. J., Eslami, S., & Teh, Y. W. (2018). Neural processes. ICML Workshop on Theoretical Foundations and Applications of Deep Generative Models (cit. on p. 8).
Germain, P., Bach, F., Lacoste, A., & Lacoste-Julien, S. (2016). PAC- PAC-Bayesian theory meets Bayesian inference. Advances in Neural Information Processing Systems (cit. on p. 10).
Germain, P., Lacasse, A., Laviolette, F., March, M., Roy. J.-F. (2015). Risk bounds for the majority
vote: From a PAC-Bayesian analysis to a learning algorithm. Journal of Machine Learning Research, 16(26), 787-860 (cit. on pp. 3, 10).
Germain, P., Lacasse, A., Laviolette, F., & Marchand, M. (2009). PAC-Bayesing learning of linear classifiers. Proceedings of the 26th Annual International Conference on Machine Learning, 353-360 (cit. pp. 2-5, 10, 17).
Gordon, J., Bruinsma, W. P., Foong, A. Y., Requeima, J., Dubois, Y., & Turner, R. E. (2020). Convo- lutional conditional neural processes. International Conference on Learning Representations (ICLR), 8th (cit. on pp. 9, 25, 26).
Kim, H., Mnih, A., Schwarz, J.. Garnelo. M., Eslami, A., Rosenbaum, D., Vinyals, O., & Teh, Y. W. (2019). Attentive neural processes. Proceedings of the 7th International Conference on Learning Representations (cit. on p. 8).
Kingma, D.P., P.,& & Ba, (2015). Adam: A method for stochastic optimization. Internation Conference Learning Representations, ICLR (cit. on pp. 24, 26).
Kingma, D. P.,& & Welling, M. (2014), Auto-encoding variational bayes. International Conference on Learning Representations, ICLR (cit. on p. 24).
Langford, J. (2002). Quantitatively tight sample complexity bounds (Doctoral dissertation). Carnegie Mellon University. (Cit. on pp. 1, 2, 4, 10, 14).
Langford, J. (2005). Tutorial on practical prediction theory for classification. Journal of machine learning research, 6(3) (cit. on pp. 3, 4, 14).
Langford, J., & Caruana, R. (2001). (Not) bounding the true error. Advances in neural information processing systems. (Cit. on 4.
Langford, J., & Seeger, M. (2001). Bounds for averaging classifiers (tech. rep.). Carnegie Mellon University. (Cit. on pp. 2 2-4, 10).
Liu, T., Ju, Yan, Z., & Zhang, G. (2021). PAC-Bayes bounds for meta-learning with data-dependent prior. arXiv preprint arXiv:2 (02.03748 (cit. on p. 8).
Majumdar, A., & Goldstein, M. (2018). Pac-bayes control: Synthesizing controllers that prov- ably generalize novel environments. In A. Billard, A. Dragan, J. Peters, & J. Morimoto
(Eds.), Proceedings of the 2nd conference on robot learning (pp. 293-305). PMLR. https: / //ppoceedings.n.t mlr. press/v871 / jmaammmmmm1111a1 html. (Cit. on p. 5)
Masegosa, A., Lorenzen, S., Igel, C., & Seldin, Y. (2020). Second order PAC-Bayesian bounds for the weighted majority vote. Advances in Neural Information Processing Systems (cit. on p. 10).
Maurer, A. (2004). A note on the PAC Bayesian theorem. arXiv preprint arXiv:es/0411099 (cit. on pp. 3, 4, 14).
McAllester, D. (2013). A PAC-Bayesian tutorial with a dropout bound. arXiv preprint arXiv:1307.2118 (cit. on 4).
McAllester, D. A. (1999). PAC-Bayesian model averaging. Proceedings of the twelfth annual confer- ence on Computational learning theory, 164-170 (cit. on pp. 3, 4).
McAllester, D. A. (2003). PAC-Bayesiaa stochastic model selection. Machine Learning, 51(1), 5-21 (cit. on p. 4). E.,, Ambroladze, A., Shawe-Taylee Taylor, J., & Sun, S. (2012). PAC-Bayes bounds with data dependent priors. The Journal of Machine Learning Research, 13(1), 3507-3531 (cit. on
p. 8).
Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E.,. DeVito, Z., Lin, Z., Desmaison, A., Antiga,
L., & Lerer, A. (2017). Automatic differentiation in PyTorch (cit. on p. 23).
Pérez-Ortiz, M., Rivasplata, O., Shawe-Taylor J., Szepesvári, C. (2021). Tighter risk certificates for neural networks. Journal of Machine Learning Research, 22(227), 1-40. http: // /jmlr. org/papersa papers/v22/200 201222222-77 879. html (cit. on pp. 4, 8)
12

---

Rivasplata, O., Kuzborskij. I., Szepesvári, C., & Shawe-Taylor, J. (2020). PAC-Bayes analysis beyond the usual bounds (H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, & H. Lin, Eds.). Advances in Neural Information Processing Systems (cit. on pp. 3, 10).
Rivasplata, O., Tankasali, V. M., & Szepesvari, (2019). PAC-Bayes with backprop. arXiv preprint 190Xi (cit. p. 4).
Rockafellar, T., & Wets, Ronneherger, O., Fischer, P., & Brox, T. (2015). U-net: Convolutional networks for biomedical image
(2010). Variational analysis. Springer. (Cit. on pp. 15, 16).
segmentation. International Conference on Medical image computing and computer-assisted intervention, 234-241 (cit. p. 26).
Rothfuss, J., Fortuin, V., Josifoski, M., & Krause, A. (2021). PACOH: Bayes-optimal meta-learning with PAC-guarantees. In M. Meila & T. Zhang (Eds.), Proceedings of the 38th international
conference on machine learning (pp. 91 9116-9126). PMLR. https : proceedings mlr
press/v13/ press/v139/rottauss222 html.. (Cit. p. 8)
Schmidhuber, J. (1987), Evolutionary principles in self-referential learning. On learning how to learn:
The tarta-mmmtttmmtt.--hootoo [diploma thesis]. (Cit. on p. 7).
Seldin, Y.. Laviolette, F., Cesa-Bianchi N., Shawe-Taylor, J., & Auer, P. (2012). PAC-Bayesian inequalities for martingales. IEEE Transactions Information Theory, 58(12), 7086-7093 (cit. on p. 10).
Thiemann, N., Igel, C.. Wintenberger, O., & Seldin, Y. (2017). A strongly quasiconvex PAC- PAC-Bayesian bound. International Conference on Algorithmic Learning Theory, 466-4946 (cit. on 4).
Thrun, S., & Pratt, L. (2012). Learning to learn. Springer Science & Business Media. (Cit. p. 7).
Tolstikhin, O., & Seldin, Y. (2013). CCCC-Bycs-emirrial-BBeemne Bernssten incquality. Advances in Neural Information Processing Systems (cit. p. 10).
Viallard, P., Germain, P., Habrard, A., & Morvant, E. (2021). general framework for the derandom- ization of PAC-Bayesian bounds. arXiv preprint arXiv:2102.08647 (cit. p. 10).
Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R., & Smola, A. (2017). Deep sets. Advances in Neural Information Processing Systems 30 (cit. on p. 8).
Zhou, W., Veitch, V., Austern, M., Adams, R. P., & Orbanz, P. (2019). Non-vacuous generalization bounds at the imagenet scale: A PAC-Bayesian compression approach. Proceedings the 7th International Conference on Learning Representations (cit. on p. 3).
13


Reviews:
[{"review_id": "yPBPxEQsaIb", "reviewer": "Reviewer_15BA", "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I have concerns about the clarity of the paper. \n\nOriginality. 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. \n\nClarity/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. \n\nSignificance. Theorem 4/Corollary 3 are exciting theoretical results, of use to researchers searching for PAC-Bayes bound that closely approximate test error from above.  \n\nUpdates after initial rebuttal: The authors gave a concrete way of improving clarity in Section 4.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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? \n\nRegarding 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "PdU0l4rwxzj", "reviewer": "Reviewer_tRQX", "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. \n\nThe 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.\nThe theoretical investigation is complemented with numerical experiments, which also add insight.\n\nFurthermore, 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.        \n\nThe 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. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nQuality: 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. \n\nClarity: The presentation is mostly clear, except few places. \n- 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? \n- 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.\n- In statement of Thm 4 \"a fixed dataset\" - do you mean any fixed dataset? or one particular dataset?\n- 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?\n- 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?\n- instead of \"optimistic MLS\" I'd suggest \"wishful MLS\" (reason being that optimistic bounds normally refer to bounds that exhibit a faster convergence rate).\n- 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. \n- 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?\n\nSignificance:\n- 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.\nNevertheless 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.\n- 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.\n- 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?  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "30"}, "extra_text": {}}, {"review_id": "K7gdhYcRcQ7", "reviewer": "Reviewer_4Rmy", "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].\n\nIn 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.", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "ORIGINALITY\n\nThe 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).\n\nSIGNIFICANCE\n\nI 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.\n\nCLARITY / QUALITY /  READABILITY\n\nThe 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.\n\nEDITORIAL FEEDBACK\n\nComment 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 [...]\"\n\nL.32: \" significantly harming post-training performance due to a reduced training set size.\"\n\nL.33: this sentence calls for a reference, Perez-Ortiz et al. [2020] is relevant here.\n\nL.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].\"\n\nL.39: \"holds for any convex function $\\Delta : [0,1]\\times[0,1] \\to \\mathbb{R}$.\"\n\nL.40: After \"Catoni [2007]\" insert \"and other bounds\"\n\nL.41: \"to this setup.\"\n\nWarning 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.\n\nL.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.\n\nL.48: Replace \"stochastic dataset\" with \"random dataset\"\n\nReason: \"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.)\n\nL.51: A bit surprising to read that a neural network parametrises a convex function.\n\nL.52: \" bound of Langford and Seeger, and relaxes\" (space-saver, since the year has been acknowledged already,)\n\nL.53: insert a reference for the Chernoff test set bound (or insert \"(see Theorem 2 below)\" since it provides the reference)\n\nL.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.\n\nL.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.\n\nL.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 [...]\"\nAlso, the number of trials should be \"$N_{\\mathrm{test}}$\" I think?\n\nL.81: the sum should start from 0?\n\nL.86: For the same reason explained above, I recommend replacing \"stochastic\" with \"randomised\"\n(regardless of what the PAC-Bayes literature has done before, unfortunately)\n\nL.87: As mentioned above, a claim \"does not require discarding data\" needs to be supported (clarification or reference(s))\n\nL.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].\"\n\nL.90-21: The part of taking supremum over the risk is special to Begin et al. I think\n(i.e. Germain et al. [2009] did not do this last step as fas as I remember)\n\nL.96: this theorem needs to clarify that the probability is over the random choice of dataset $S$ of size $N$.\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)\n\nL.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.\n\nL.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.\n\nL.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]:\"\n\nL.105: Note that in fact this inequality holds for all $N \\geq 1$, the small $N$ cases have been verified numerically\n(see \"Risk bounds for the majority vote: From a PAC-Bayesian analysis to a learning algorithm\")\n\nL.106: Why not refer to this, more suggestively, as the PAC-Bayes-kl bound?\n(I am objecting the use of the acronym MLS due to being uninformative and potentially misleading)\n\nL.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.\n\nL.108-110: Again, the two different uses of PAC-Bayes bounds are being conflated in this passage.\nAlso, the list of references in the square brackets should start with Langford and Caruana 2001 and end with Perez-Ortiz et al., 2020\n(Note that the publication year of \"(Not) Bounding the True Error\" is 2001, regardless that Google Scholar incorrectly gives 2002)\n\nL.112: [McAllester, 1999, 2003]\n\nL.123: replace \"value\" with \"form\"\n\nL.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.] \n\nL.141: \"This upper bound (Them 3) can be \"inverted\" to obtain [...]\" \n\nL.146: \"random dataset\"\n\nL.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$). \n\nL.147: Replace \"Next\" with \"Later\"\n\nL.149: \"realistic case of a random dataset\"\n\n\n\nL.151-154 (Theorem 4): This theorem needs to be reformulated according to the intended meaning and\n\nL.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}$?\n\nL.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?\n\nL.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]\n\nL.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}$.\n\nL.170-171: Still it is not clear how the cases of \"fixed data\" and \"random data\" give different things. \nThis suggests at the very least that clarification is needed.\n\nL.172: This line is comparing the average values of the inversions corresponding to different $\\Delta$'s, is this legit?\n\nL.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.\n\nOnly skimmed at the Proof of Theorem 4 but happy to get back to it between rebuttal and final decision if we get there.\nA quick question: Care to give some intuition on why lower-bounding $N^{-1}\\mathcal{I}$ and upper-bounding $\\Delta$?\nAt first look it seems to make sense upper-bounding $\\mathcal{I}/N$ and lower-bounding $\\Delta$, feel free to check me what I misunderstood.\n\nL.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.\n\nL. 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.\n\nL.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).\n\nL.241: The notation $\\mathcal{T}$ needs to be declared. Is it intended for denoting the set of all possible tasks?\nI think the distribution over tasks should use a different notation than the distribution that generates random dataset for a given task.\n\nL.247: \"Perez-Ortiz et al., 2020\" is relevant to these references for data-dependent priors gaining attention.\n\nL.249: replace \"empirical risk\" with \"risk bound\"\n\nL.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.\n\nL.251-252: \"and Perez-Ortiz et al. demonstrated empirically that learning priors from data is key for obtaining tight risk certificates\" \n(the latter are much (!) better than non-vacuous bound values)\n\nL.253: The mapping at the end of this line is better formalised as a stochastic kernel.\n\nL.255: this choice to \"ease notation\" has the effect of obscuring the dependencies --- can it be fixed?\n\nL.261: \"learned convex function\"\n\nL.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).\n\nIn general, my impression is that this section could improve a lot by better/explicit math notation and definitions.\n\nL.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).\n\nL.292-293: This is expected in view of the higher representational power of the CNN compared to MLP?\n\nL.296: Confused by \"the test set classifier\" --- should this be \"the test set bound\"? (Or else, explain.)\nL.297: The \"PAC-Bayes classifier\" is the randomised classifier, according to the PAC-Bayes posterior distribution?\n\nL.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? \n\nOkay, 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)\n\nL.340: and \"Rivasplata et al. [2020]\"\n\nL.343: Not sure about the claim that \"Gibbs classifiers are not often used in practice\" --- could this be substantiated?\n\nOverall 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.\n\nWould like for all my feedback above to be addressed in the response.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sure.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "CvTTHPZ9QQJ", "reviewer": "Reviewer_d92V", "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. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.  \n\nFor 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. \n\nThe 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Addressed by the authors. I do not foresee any potential negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)