How Tight Can PAC-Bayes be in the Small Data Regime?
Year: 2022

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.

text: 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.

heading: 1 Introduction
text: Generalisation bounds are of both practical and theoretical importance. Practically, tight bounds provide certificates that algorithms will perform well on unseen data. Theoretically, the bounds and underlying proof techniques can help explain the phenomenon of learning. Among the tightest known bounds are PAC-Bayes (McAllester, 1999) and test set bounds (Langford, 2002). In this paper, we investigate their numerical tightness when applied to small datasets (N ≈ 30–60 datapoints). The comparison between PAC-Bayes and test set 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 to a reduced training set size. PAC-Bayes on 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 (NeurIPS 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 a 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, ∆. By choosing ∆ appropriately, one can recover the well-known bounds of Langford and Seeger (2001), Catoni (2007) and other bounds. We focus on two questions related to this set-up. First, what is the tightest bound achievable by any convex function ∆? An answer would characterise the limits of the generic PAC-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 ∆ 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 ∆ 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 ∆. 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 ∆ with a constrained neural network. Interestingly, this lower bound coincides with removing a 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 1D classification. The goal of this experiment is to find out how tight the bounds could be made in principle. We use meta-learning to adapt all aspects of the bounds and learning algorithms, 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, a 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://github.com/cambridge-mlg/pac-bayes-tightness-small-data.

heading: 2 Background and Related Work
text: We consider supervised learning. Let X and Y denote the input space and output space, and let Z = X×Y . Assume there is an (unknown) probability measure2 D over Z , with the dataset S ∼ DN . Denote the hypothesis space by H ⊆ YX . A learning algorithm is then a map ZN → H. In PACBayes, we also consider maps ZN → M1(H), where M1 is the set of probability measures on its argument. The performance of a hypothesis h ∈ H is measured by a loss function ℓ : Z ×H → [0, 1]. The (generalisation) risk of h is RD(h) := E(x,y)∼D[ℓ((x, y), h)] and its empirical risk on S is RS(h) := 1 N ∑
(x,y)∈S ℓ((x, y), h). For Q ∈ M1(H) its (generalisation Gibbs) risk is RD(Q) := Eh∼Q[RD(h)] and its empirical (Gibbs) risk is RS(Q) := Eh∼Q[RS(h)]. In PAC-Bayes, we usually fix a prior P ∈ M1(H), chosen without reference to S and learn a posterior Q ∈ M1(H) which can depend on S. The KL-divergence between Q and P is defined as KL(Q‖P ) = ∫
log dQdP dQ if Q ≪ P and ∞ otherwise. Let C denote the set of proper, convex, lower semicontinuous (l.s.c.) functions R2 → R ∪ {+∞}; if a convex function’s domain is a subset of R2, extend it to all of R2 with the value +∞. 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 S = Strain ∪ Stest, with |S| = N , |Strain| = Ntrain and |Stest| = Ntest. In Theorems 1 and 2, we assume h is chosen independently of Stest. For the zeroone loss, ℓ((x, y), h) := ✶[h(x) 6= y], we have that NtestRStest(h) is a binomial random variable with parameters (Ntest, RD(h)). This leads to the following simple bound, which, for ℓ ∈ {0, 1}, is tight among test set bounds:
2We will colloquially refer to measures on sets without specifying a σ-algebra. We implicitly assume functions are measurable with respect to the σ-algebras on which the relevant measures are defined.
Theorem 1 (Binomial tail test set bound, Langford, 2005, Theorem 3.3). Let e(M,k, δ) := sup {
p : δ ≤ ∑ki=0 ( M i ) pi(1−p)M−i } . For any h ∈ H, ℓ ∈ {0, 1} and δ ∈ (0, 1), Pr ( RD(h) ≤ e(Ntest, NtestRStest(h), δ) ) ≥ 1− δ. (1)
Often, looser bounds with a simpler form are applied. These can be obtained via the Chernoff method:
Theorem 2 (Chernoff test set bound, Langford, 2005, Corollary 3.7). For q, p ∈ [0, 1], let kl(q, p) := q log qp + (1− q) log 1−q 1−p . For any h ∈ H, ℓ ∈ [0, 1], and δ ∈ (0, 1),
Pr (
kl(RStest(h), RD(h)) ≤ 1Ntest log 1 δ
)
≥ 1− δ. (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 a 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 inequalities shared by PAC-Bayes proofs (Jensen’s, change of measure, Markov’s, supremum over risk3), and reveals their common structure. Thus understanding the properties of this generic theorem can give insight into many PAC-Bayes bounds at once:
Theorem 3 (Generic PAC-Bayes theorem, Bégin et al. (2016) and Germain et al. (2009)).4 Fix P ∈ M1(H), ℓ ∈ [0, 1], δ ∈ (0, 1), and ∆ a proper, convex, l.s.c. function [0, 1]2 → R ∪ {+∞}. Then
Pr ( (∀Q) ∆(RS(Q), RD(Q)) ≤ 1N [ KL(Q‖P ) + log I∆(N)δ ])
≥ 1− δ, (3) where I∆(N) := supr∈[0,1] ∑N k=0 ( N k ) rk(1− r)N−keN∆(k/N,r).
Remark 1. We lose no generality in assuming ∆(q, ·) is monotonically increasing for all q ∈ [0, 1], i.e. for any convex ∆ we can define a ∆′ that is monotonically increasing in its second argument and produces a bound that is at least as tight as the bound produced by ∆. See Appendix D for a proof.
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, we 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 ∆(q, p) = Cβ(q, p) := − log(1 + p(e−β − 1))− βq for β > 0, we recover the Catoni bounds:
Corollary 1 (Catoni, 2007, Theorem 1.2.6). For any β > 0,
Pr ( (∀Q) RD(Q) ≤ 11−e−β [ 1− exp ( −βRS(Q)− 1N ( KL(Q‖P ) + log 1δ ))]) ≥ 1− δ. (4)
This specifies a bound for every value of β > 0. If we instead choose ∆(q, p) = kl(q, p), we obtain the bound of Langford and Seeger (2001), also called the PAC-Bayes-kl bound, but with the slightly sharper dependence on N established by Maurer (2004):
Corollary 2 (Langford and Seeger, 2001, Theorem 3, Maurer, 2004, Theorem 5).
Pr ( (∀Q) kl(RS(Q), RD(Q)) ≤ 1N [
KL(Q‖P ) + log 2 √ N
δ
])
≥ 1− δ. (5)
Corollary 2 is actually very slightly looser than Theorem 3 with ∆ = kl, since Maurer (2004) upper bounds Ikl(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 is key, such as obtaining generalisation bounds for stochastic neural networks (Dziugaite & Roy, 2017; Zhou et al., 2019). Many other bounds can be obtained by loosening these bounds. Applying Pinsker’s inequality kl(q, p) ≥ 2(q − p)2 to Equation (5) yields the “square-root” version of the
3The supremum over risk step was introduced in Bégin et al. (2016), although for certain ∆ it can be omitted. 4We state a simpler version of their result WLOG, absorbing a free parameter into the function ∆. 5Maurer (2004) only proves this bound for N ≥ 8, but the cases where 1 ≤ N ≤ 7 can be easily verified
numerically (Germain et al., 2015, Lemma 19).
PAC-Bayes theorem (McAllester, 1999, 2003). The “PAC-Bayes-λ” (Thiemann et al., 2017) and “PAC-Bayes-quadratic” bounds (Rivasplata et al., 2019) can be derived as loosened versions of the PAC-Bayes-kl bound using the inequality kl(q, p) ≥ (q − p)2/(2p), valid for q < p. The “linear” bound in McAllester (2013) can be derived by loosening the Catoni bound using: Cβ(q, p) ≤ A =⇒ p ≤ 11−β/2 (q + 1βA), which is valid for β ∈ (0, 2).
How Tight Are PAC-Bayes Bounds? A fundamental question we can ask about a generalisation bound is how tight it is, and whether it can be tightened. Comparing the PAC-Bayes-kl and Chernoff test set bounds when Q = P (so the PAC-Bayes bound essentially becomes a test set bound) shows they are identical except for a log(2 √ N)/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 to its current form, improving on work by Langford and Seeger (2001). Interestingly, Germain et al. (2009, Proposition 2.1) shows that the expression obtained by dropping log (2 √ N)/N from the PAC-Bayes-kl bound is identical to that obtained by illegally6 minimising the Catoni bound with respect to β; 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 a PAC-Bayes bound can be found that reduces to the binomial tail bound when Q = P . We provide new insights into these problems in Section 3.
Researchers have also compared PAC-Bayes bounds numerically on actual learning problems. Langford (2005) and Germain et al. (2009) were able to obtain reasonable guarantees on small datasets. However, Langford (2005) found that on datasets with N ≈ 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 a task distribution, PAC-Bayes can be tight enough to compete with the Chernoff test set bound, but not the binomial tail test set bound.

heading: 3 Characterising the Limits of the Generic PAC-Bayes Proof Technique
text: This section establishes our main theoretical contributions, which characterise the limits of the generic PAC-Bayes theorem (Theorem 3). For a convex ∆ ∈ C, Theorem 3 gives a high-probability upper bound on ∆(RS(Q), RD(Q)). Define B[f, y] := sup {p ∈ [0, 1] : f(p) ≤ y} for f : [0, 1] → R and y ∈ R, where we take sup∅ = 1. This upper bound (Theorem 3) can be “inverted” to obtain a high-probability upper bound on RD(Q): with probability at least 1− δ, for all Q ∈ M1(H),
RD(Q) ≤ p∆ where p∆ := B [ ∆(RS(Q), · ), 1N ( KL(Q‖P ) + log I∆(N)δ )] . (6)
Since (6) holds for all ∆ ∈ C, a natural question is: Which ∆ minimises p∆? 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 ∆ is selected before observing S ∼ DN , we first characterise the optimal ∆ in the simplified scenario where ∆ can depend on the dataset S and the posterior Q (Theorem 4). This setting is artificial, since choosing
6That is, optimising β depending on the dataset S without taking a union bound.
∆ 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 ∆ 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 ∈ M1(H), the tightest Catoni bound is as tight as the tightest bound possible within the generic PAC-Bayes theorem (Theorem 3). Precisely, let ∆ ∈ C and δ ∈ (0, 1). Choose some fixed values for RS(Q) =: q ∈ [0, 1] and KL(Q‖P ) =: KL ∈ [0,∞). If q > 0, then there exists a β ∈ (0,∞) such that p∆ ≥ pCβ , where p is defined in Equation (6). Moreover, if q = 0, then p∆ ≥ limβ→∞ pCβ . Remark 2. By Theorem 4, for all ∆ ∈ C, we have p∆ ≥ infβ>0 pCβ , and, by Proposition 2.1 of Germain et al. (2009), infβ>0 pCβ = B[kl(q, · ), 1N (KL+ log 1δ )]. Hence, for all ∆ ∈ C, it holds that p∆ ≥ B[kl(q, · ), 1N (KL+ log 1δ )], 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 KL) 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 4 by optimising p∆ with respect to an arbitrary convex ∆ for various settings of fixed q and KL. To parametrise a convex ∆, we use a one-hidden-layer neural network with positive weights at the output layer and softplus nonlinearities. The inversion performed by B is approximated numerically by discretising the second argument of ∆ and detecting an upcrossing. Gradients are then approximated using the inverse function theorem: d
dθB[fθ, c(θ)] = (∂θc(θ)− ∂θfθ(x))/∂xfθ(x). See Appendix F for details.7 Figures 2a and 2b show the difference between the numerically optimised ∆ and the best Catoni bound for two settings of fixed q ∈ [0, 1] and KL ∈ [0,∞). In both cases, p∆ − infβ>0 pCβ appears to converge to zero from above, as expected from Theorem 4. Interestingly, Appendix F shows that the learned ∆ can deviate substantially from Cβ , suggesting that there are choices for ∆ besides Catoni’s which achieve inf∆∈C p∆.
For any fixed dataset S, Theorem 4 states that the tightest bound is one of the Catoni bounds; precisely: inf∆∈C p∆ = infβ>0 pCβ . Note that the optimal value of β may depend on the dataset S. The more interesting question is whether, when S ∼ DN is sampled randomly, one of the Catoni bounds can still achieve the tightest bound (in expectation) for a single value of β that is chosen before sampling S. The answer is no: Figure 2d gives a numerical counterexample where inf∆∈C E[p∆] < E[pkl] < infβ>0 E[pCβ ]. Since the Catoni family of bounds cannot generally achieve the tightest bound in expectation, which ∆ do? And how tight is inf∆∈C E[p∆]? Whilst we do not have a full answer, we establish a simple lower bound on inf∆∈C E[p∆]. Define the conjectured
7Numerical inversion of ∆ when ∆ = 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 ∆, along with the method for backpropagating through the inverse, are novel in the PAC-Bayes setting.
PAC-Bayes-kl bound p as the quantity from Remark 2, which equals the PAC-Bayes-kl bound without the 1N log Ikl(N) term on the RHS:
p := B[kl(RS(Q), · ), 1N (KL(Q‖P ) + log 1δ )]. (7) The conjectured PAC-Bayes-kl bound has not been proven to be a valid generalisation bound. When S ∼ DN is random, Remark 2 tells us that inf∆∈C p∆ = p 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-Bayes-kl bound E[p] 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, inf∆∈C E[p∆] ≥ E[p] (8) Moreover, there exists a distribution over datasets, a 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), ∆ is chosen not depending on S, which leads to a valid generalisation bound on the LHS.
Figure 1 shows how Corollary 3 fits into the picture so far. The conjectured PAC-Bayes-kl bound is at least as tight as the bound achieved by any ∆, but Corollary 3 does not establish the existence of a ∆ which achieves it. Corollary 3 has practical utility: the conjectured PAC-Bayes-kl bound can be used to prove optimality of a choice of ∆. Specifically, if a practitioner computes a valid bound based on the generic PAC-Bayes theorem, and finds that it is close to the conjectured PAC-Bayes-kl 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 ∆. Conversely, the conjectured PAC-Bayes-kl bound can quantify potential slack in the bound due to a suboptimal choice of ∆. Appendix H considers an example of this application of Corollary 3 in the simplified scenario where RS(Q) = 1 2 almost surely.
The conjectured PAC-Bayes-kl 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-Bayes 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 ∆ such that Theorem 3 recovers the Chernoff test set bound; or, alternatively, such that the conjectured PAC-Bayes-kl bound is attained. A positive answer to the latter would establish that the conjectured PAC-Bayes-kl bound is a valid generalisation bound.8 As a first piece of evidence, the traces from Figures 2c and 2d suggest that a convex function could actually achieve E[p]; 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 a 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 ∆(q, p) = Cβ(q, p) := Fβ(p)−βq with Fβ(p) := − log(p(e−β −1)+1) and β > 0. To simplify the notation, we denote α = 1N (KL+ log 1 δ ) ∈ (0,∞).
Proof of Theorem 4. The proof proceeds in three steps. In the first two steps, we lower bound 1 N log I∆(N) and upper bound ∆. In the third step, we use these bounds to lower bound B[∆(q, · ), α+ 1N log I∆(N)] and identify the result with a particular Catoni bound. Lower bound on 1N log I∆(N): Since ∆ ∈ C, it is equal to its own double convex conjugate: ∆(q, p) = ∆∗∗(q, p) = supcq,cp∈R (cqq + cpp−∆∗(cq, cp)), where ∗ denotes convex conjugation. Let X ∼ Bin(r,N). Then
I∆(N) = supr∈[0,1] E[eN∆(X/N,r)] = supr∈[0,1] E[esupcq,cp∈R(cqX+Ncpr−N∆ ∗(cq,cp))] (9)
≥ supr∈[0,1] supcq,cp∈R eNcpr−N∆ ∗(cq,cp)E[ecqX ] (10)
where E[ecqX ] = (r(ecq − 1) + 1)N is the moment-generating function of X . Consequently, taking log, dividing by N , and noting that 1N logE[e
cqX ] = −F−cq (r), 1 N log I∆(N) ≥ A where A := supcq,cp∈R[−∆∗(cq, cp) + supr∈[0,1](cpr −F−cq (r))]. (11)
8By Remark 2, p ∆ ≥ p, so E[p ∆ ] = E[p] implies that p ∆ = p a.s., meaning that p is a valid gen. bound.
Upper bound on ∆: We upper bound ∆ by making ∆∗ as small as possible without exceeding the supremum from (11). Note that A is finite, because ∆∗ is proper. Define ∆̃∗ as follows: ∆̃∗(cq, cp) = −A + supr∈[0,1](cpr − F−cq (r)). Note that ∆̃∗ is proper, convex as a pointwise supremum of convex functions, and l.s.c. as a supremum of l.s.c. functions. In fact, ∆̃∗ is finite for all inputs. As the notation suggests, define ∆̃ := (∆̃∗)∗. Then ∆̃∗ is indeed the convex conjugate of ∆̃, because ∆̃∗ ∈ C, so it is equal to its own double convex conjugate. Moreover,
∆̃(q, p) = A+ supcq,cp∈R[cqq + cpp− supr∈[0,1](cpr −F−cq (r))] (12) = A+ supcq∈R [cqq + supcp∈R [cpp−F∗−cq (cp)]] (13) = A+ supcq∈R [cqq + F−cq (p)], (14)
by observing that p 7→ F−cq (p) ∈ C, so it is equal to its own double convex conjugate. Therefore,
∆̃(q, p) = A+ supcq∈R C−cq (q, p) (i) = A+ kl(q, p) (15)
where (i) follows from a direct computation; see Lemma E.1 (Appendix E). Claim: For all q, p ∈ [0, 1], ∆̃(q, p) ≥ ∆(q, p). This follows from the definitions and finiteness of ∆̃∗ and A: for all cq, cp ∈ R, −∆̃∗(cq, cp)+supr∈[0,1](cpr −F−cq (r)) = A ≥ −∆∗(cq, cp)+supr∈[0,1](cpr −F−cq (r)), (16)
which means that ∆̃∗ ≤ ∆∗, so ∆̃ ≥ ∆ by the order-reversing property of the convex conjugate. Conclusion: Assume that p∆<1; otherwise, any β>0 works. To begin with, use the previous steps:
p∆ = B[∆(q, · ), α+ 1N log I∆(N)] (11), claim ≥ B[∆̃(q, · ), α+A] (15)= B[kl(q, · ), α] = p. (17) Since α > 0, clearly p > q, so 0 ≤ q < p < 1. Hence, if q > 0, then there exists a β > 0 such that kl(q, p) = Cβ(q, p) (Lemma E.2; Appendix E). Using that p 7→ Cβ(q, p) is continuous and strictly increasing for all β > 0, we have that p = B[Cβ(q, · ), α], so
p∆ ≥ B[Cβ(q, · ), α] (i) = B[Cβ(q, · ), α+ 1N log ICβ (N)] = pCβ , (18)
where (i) uses that 1N log ICβ (N) = 0 (Lemma E.3; Appendix E). If q = 0, then kl(0, p) = limβ→∞ Cβ(0, p) (Lemma E.2; Appendix E), so p∆≥B[ lim
β→∞ Cβ(0, ·), α], and conclude like in (18)
using Lemma E.4 (Appendix E).

heading: 4 Meta-Learning the Tightest Bounds for Synthetic Classification
text: 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 tightest? and Can PACBayes 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 meta-learn (Schmidhuber, 1987; Thrun & Pratt, 2012) separate algorithms to optimise each bound in expectation: we parametrise a hypothesis space Hθ and a posterior map Qθ : ZN → M1(Hθ) by a finite dimensional vector θ, which is trained to optimise the expected bound (we will amalgamate all meta-learnable parameters into the single vector θ). 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-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 ∼ DN as a task. We consider a 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 et al. (2021, Appendix J) for a relevant discussion.
data-generating 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 I.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; Parrado-Hernández et al., 2012; Pérez-Ortiz et al., 2021) has been gaining increased attention. This involves splitting the dataset into N = Nprior + Nrisk datapoints. The DDP is allowed to depend on the prior set of size Nprior (standard priors use Nprior = 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, Pθ : ZNprior → M1(H). To compare PAC-Bayes 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 a 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.
The Meta-Learning Objective. We now discuss meta-learning in more detail. During meta-training, θ is trained to optimise the expected PAC-Bayes generalisation bound over the task distribution:
ED∼T ES∼DN B [ ∆θ(RSrisk(Qθ(S)), · ), 1Nrisk ( KL(Qθ(S)‖Pθ(Sprior)) + log I∆θ (Nrisk)δ )] , (19)
where the θ in ∆θ denotes that some bounds (Catoni and learned convex function) have meta-learnable parameters. Alternatively, for a meta-learner that minimises a test set bound, the objective is simply ED∼T ES∼DN RStest(Qθ(Strain)), 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 θ. In contrast to PAC-Bayes, the predictor that minimises the test set bound can be made deterministic after θ is learned, since it tends to eventually learn essentially deterministic classifiers; see Appendix I.2. We sample T = 80 000 tasks Dt ∼ T , with associated datasets St ∼ DNt . These form the meta-trainset. Additionally, we sample 1024 tasks that form a meta-testset 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 a PAC-Bayes meta-learner is (a minibatched version of):
1 T ∑T t=1 B [ ∆θ(RSt,risk(Qθ(St)), · ), 1Nrisk ( KL(Qθ(St)‖Pθ(St,prior)) + log I∆θ (Nrisk)δ )] . (20)
Similarly, the objective for the test set bound meta-learner is 1T ∑T
t=1 RSt,test(Qθ(St,train)). The bounds we compute on datasets in the meta-testset, after meta-training is complete and θ is frozen, are valid even though θ 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 Hθ and the maps Qθ, Pθ. We meta-learn a feature map φθ : R → RK and choose11 Hθ = {hw : hw(x) = sign〈w, φθ(x)〉, w ∈ RK}. For Qθ and Pθ Gaussian, this hypothesis space allows us to compute the empirical Gibbs risk without Monte Carlo integration; see Appendix I.3 for details. For the form of Qθ, 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 et al., 2017). They are regularly benchmarked on 1D meta-learning tasks, making them ideally suited. We make a straightforward modification to NPs to make them output Gaussian measures over weight vectors w ∈ RK . Hence, they act as parametrisable maps from ZN to the set of Gaussian measures on RK .
10We could also consider drawing all datasets from a 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.
11The dimensionality K is fixed a priori.
2.0 1.5 1.0 0.5 0.0 0.5 1.0 1.5 2.0 0.00
0.25
0.50
0.75
1.00 Bin. tail/Chernoff bound: 0.20/0.24, gen. risk: 0.087, test risk: 0.06.
(a) Binomial tail/Chernoff test set bounds, showing the learned hypothesis (—), the train set (#) of size 12 and the test set (#) of size 18.
2.0 1.5 1.0 0.5 0.0 0.5 1.0 1.5 2.0 0.00
0.25
0.50
0.75
1.00 Gen. bound: 0.22, gen. risk: 0.045, KL: 1.43.
(b) Learned convex bound with data-dependent prior, showing the prior (—) and posterior (—) predictive, prior set (#) of size 12 and risk set (#) of size 18.
Figure 4: Predictions on one of the 1D datasets in the meta-test set with N = 30 and prior/train proportion 0.4. For each method, we report the generalisation bound and actual generalisation risk. For the test set model, we also show the risk on the test set, and for the PAC-Bayes model we show the KL-divergence. 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 I.5 and I.6) Although the MLP-NP is very flexible, the state-of-the-art in NPs on 1D 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 to produce tighter (or comparable) average bounds to 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 a 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 I.7.
Results. We show example classification tasks and average bounds on the meta-test set in Figures 3 and 4. Note that the test set classifier became deterministic and makes hard predictions whereas the PAC-Bayes classifier shows uncertainty; see Appendix I.2 for a discussion. The PAC-Bayes-kl bound is loosest, which is unsurprising as it has no optimisable parameters to 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 3, 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 ∆ here. We also see 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 to a 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
12This is in contrast with usual applications of PAC-Bayes, where one does not have a meta-dataset 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.

heading: 5 Conclusions, Open Problems, and Limitations
text: 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-Bayes theorem of Germain et al. (2009) and Bégin et al. (2016) which encompasses a wide range of PAC-Bayes bounds, cannot produce tighter bounds in expectation than the expression obtained by discarding the log(2 √ N)/N 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-kl bound is a valid generalisation bound, numerical evidence suggests (Figures 2c and 2d) that there may exist a convex function ∆ which achieves it, at least for the distributions over empirical risk and KL-divergence we considered. This suggests the following open problem:
Open Problem 1. For an arbitrary distribution over datasets, does there exist a choice of ∆ 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 a valid generalisation bound (see Section 3) and resolve Problem 6.1.2 of Langford (2002) in the affirmative.
We then considered, in a 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 (Theorem 1) when the posterior is equal to 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 our proof relies primarily on tools from convex analysis, and Jensen’s inequality is ubiquitous in PAC-Bayes bounds, it would be interesting to see if our arguments can be extended beyond the limited setting we focus on.
Finally, our meta-learning experiments only considered 1D 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 is an important, but potentially challenging, avenue for future work.
Acknowledgements and Funding Transparency Statement
We would like to 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).

Review summaries:
As far as I see, this submission is motivated by the desire to understand the ability of PAC-Bayes bounds to give tight numerical values such that they could be used as numerical measures intended to certify the post-training performance of randomised classifiers. The submission leverages the so-called generic PAC-Bayes theorem which is stated in terms of an arbitrary convex function $\Delta : [0,1]\times[0,1] \to \mathbb{R}$ and which can be seen as the basis for deriving the known PAC-Bayes bounds (the one of McAllester, the one of Langford and Seeger, the parametric family of bounds of Catoni, possibly others) as shown by Germain et al. [2009].  In particular, the submission compares theoretically the best bounds that could be hoped for when using the parametrised family of bounds of Catoni (there's one such bound for each $\beta>0$), and the generic bound for a given $\Delta$. Then it also discusses what's the best one can hope for when optimising $\Delta$ from a class of convex functions. Then in some empirical studies with (artificial) datasets of small size the values of the bounds are evaluated and compared. For individual (as opposed to randomised) predictors, the values of two "test set bounds " are also shown: the binomial tail inversion bound and the Chernoff relative entropy bound. If I understand correctly, the intended goal is to compare the tightness of the PAC-Bayes bounds (for randomised predictors) with the tightness of the test set bounds (for individual predictors). The experiments culminate with a setting where the parameters of the bounds are meta-learned, and the claim is that in this setting the PAC-Bayes bounds give better results than the test set bounds. The discussions, however, suggest settings in which test set bounds, in particular the so-called binomial tail bound, dominate.

This paper proposes to study the best numerical tightness of PAC-Bayes bounds, it comparison with test set bounds. The main motivation given is that in small sample problems one cannot afford to hold out a subset of the data to compute a test set bound.   The main theoretical results are Theorem 4 with its Corollary 3, presented in Sec. 3. In Thm 4 the dataset is fixed, and the best divergence function is sought for the general PAC-Bayes bound, which produces the tightest bound. This turns out to be one of Catoni's bounds. In Cor 3 the data set is no longer fixed, and the authors find that Catoni's bounds can no longer achieve the tightest bound, and the authors conjecture the "optimistic MLS bound" is a tight lower bound, which they show to be a tight lower bound. Apparently the conjecture was previously stated by Langford. While the present paper still leaves this open, it makes some progress in terms of insights. The theoretical investigation is complemented with numerical experiments, which also add insight.  Furthermore, Sec 4. presents extensive experimental work addressing the question of which PAC-Bayes bounds are tightest and how they compare with the test set bound, by optimising the bounds numerically, with respect to the algorithm and the task. Results from the experiments are presented in Figs 3 and 4, and several interesting observations are made, including that PAC-Bayes can be as tight as the test-set bound, and that the "optimistic MLS bound" is indistinguishable from Catoni's. While it is indeed interesting to see that PAC-Bayes bounds can be really tight, of course it doesn't mean they will be tight when applied on some given task and some given algorithm.          The main outcomes of the study are summarised in Sec 5. in the for of 2 open problems: 1. echoes the one of Langford, 2. asks for the possibility that a PAC-Bayes bound be as tight (at its best) as the tightest set set bound.  

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.