Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound
Authors: Reuben Adams
John Shawe-Taylor
Benjamin Guedj
Venue: NeurIPS 2024 poster (2024)
Keywords: PAC-Bayes
Generalization
Statistical Learning Theory
Primary area: learning_theory
TL;DR: We prove a novel PAC-Bayes bound which provides rich information on the types of errors likely to be made at inference time.

Abstract: Current PAC-Bayes generalisation bounds are restricted to scalar metrics of performance, such as the loss or error rate. However, one ideally wants more information-rich certificates that control the entire distribution of possible outcomes, such as the distribution of the test loss in regression, or the probabilities of different mis-classifications. We provide the first PAC-Bayes bound capable of providing such rich information by bounding the Kullback-Leibler divergence between the empirical and true probabilities of a set of $M$ error types, which can either be discretized loss values for regression, or the elements of the confusion matrix (or a partition thereof) for classification. We transform our bound into a differentiable training objective. Our bound is especially useful in cases where the severity of different mis-classifications may change over time; existing PAC-Bayes bounds can only bound a particular pre-decided weighting of the error types. In contrast our bound implicitly controls all uncountably many weightings simultaneously.

Controlling Multiple Errors Simultaneously with a PAC-Bayes Bound
Reuben Adams
John Shawe-Taylor
Department of Computer Science University College London
Department of Computer Science
University College London
reuben. adams 20@ucl ac. uk
j j.shawe- taanoeee-tylorruccllc.c ac uk
Benjamin Guedj
Department of Computer Science, University College London and Inria
b. guedj @ucl. ac. uk
Abstract
Current PAC-Bayes generalisation bounds are restricted to scalar metrics of perfor- mance, such the loss or eπror rate. However, one ideally wants more information- rich certificates that control the entire distribution of possible outcomes, such as the distribution of the test loss in regression, or the probabilities of different mis-classifications. We provide the first PAC-Bayes bound capable of providing such rich information by bounding the Kullback-Leibler divergence between the empirical and true probabilities of set of M error types, which can either be discretized loss values for regression, or the elements of the confusion matrix (or a partition thereof) for classification. We transform our bound into differentiable training objective. Our bound is especially useful in cases where the severity different mis clisciaasiiiianoonn may change over time; existing PAC-Bayer bounds can only bound a particular pre-decided weighting of the error types. In contrast our bound implicitly controls all uncountably many weightings simultancously.
Introduction
Generalisation bounds are core component of the theoretical understanding of machine learning algorithms. For over two decades now, PAC-Bayesian theory has been at core of studies on generalisation abilities of machine learning algorithms. PAC-Bayes originated in the seminal work McAllester [1998] [999] and was further developed by Catoni [2003] 2004 2007]. among other authors- refer to the surveys Guedj [2019) and Alquier [022 for an introduction to the field. The outstanding empirical success of deep neural networks in the past decade calls for better theoretical understanding of deep learning, and PAC-Bayes has emerged one of the few frameworks that can be used to derive meaningful (and non vacuous) generalisation bounds for neural networks: the pioneering work of Dziugaite and Roy [2017) has been followed by a number of contributions, including Neyshabur et al. 20188) Zhou et al. [2019]. Letarte et al. [2019], PPérez-Ortiz et al. 2021
Perez-Ortiz al. 2021 and Biggs and Guedj [202a b), name but a few.
Much of the PAC-Bayes literature focuses on the case of binary classification, or of multiclass classification where one only distinguishes whether each classification is correct incorrect. This is in stark contrast to the complexity of contemporary real-world learning problems, such as medical diagnosis where the severity of Type I and Type II errors may be crucial and context-dependent This work aims to bridge this gap by deriving generalisation bound that provides information -ich measures of performance test time by controlling the probabilities of errors of any finite number of user-specified types. More precisely, we bound the KL-divergence between the empirical and true
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

distributions over the different error types. From this single bound one can then derive bounds on arbitrary linear combinations of these error probabilities, which will all hold simultaneously with the same probability as the original bound. In addition, these bounds are guaranteed to be non-vacuous (this follows since the -ivveieeeeeeee blows up on the boundary of the simplex).
As a concrete example, if the severity of Type and Type II errors of medical test are context- dependent, one would want to be able bound arbitrary linear combinations of these error probabili- ties. Existing bounds could only bound finitely many pre-specified weightings by employing a union bound, which would also degrade the bound. In contrast, by constraining the KL-divergence between the true and empirical error probabilities, our bound constrains all uncountably many weightings of the error probabilities simultaneously.
The usual setting of PAC-Bayes bounds is that of binary classification, namely an input set X, output set y 1) hypothesis space H C )x and a sample S (X' 3 drawn i.i.d. from data- generating distribution D. A number of PAC-Bayes bounds in this setting (e.g. Maurer (2044) have
been unified by single general bound found in Bégin et al. (2016). Briefly, [égin al. 2016 prove
a bound on the discrepancy d( (RR((Q) Rn(()) between the error probability RD of a stochastic
classifier Q (a distribution over H. which classifies by first drawing h Q and then classifying according to h) and its empirical counterpart (Q) (the fraction of the sample Q misclassifies). The bound holds with high probability for all Q simultaneously. The bound in Béegin et al. [2016] is binary in the sense that )' contains two elements, but a more subtle way to look at this is that only two cases are distinguished- correct classification and incorrect classification. While it can be applied to multiclassificattin provided one maintains the second binary characteristic by only distinguishing correct and incorrect classifications. It is this heavy restriction that our result lifts, by considering the new framework of error types.
A new framework of errors types We consider user-specified partition of the space y x y of prediction-truth label-pairs into a finite partition of error types Ei...., EM. Our bound then simultaneously constrains the probability with which errors of each type occur. In multiclass classification for example, one can choose the error types to be the set of all different possible mis-classifications, in which case our bound will control the entire confusion matrix, bounding how far the true confusion matrix (i.c. expected over the tata-generating distribution) can diverge from the empirical one (i.e. on the training set). From this can then derive bounds the probabilities with which each clisccaassiiiatoonn may be made, and arbitrary linear combinations of these error probabilities, and all of these will hold simultaneously with the same probability as the original bound. Our bound therefore paints a far richer picture of the performance of the final learned model than can be provided by any existing PAC-Bayes bound.
Formally, we let د F. be a user-specified disjoint partition of y² into finite number of M error types, where we say that a hypothesis h E H makes an error of type j on datapoint (z., y) if (h(z),)) E E3 (by convention, every pair (g.v) E y is interpreted as predicted value followed by true value y. in that order). It should be stressed that not all of the E, need correspond to mislabellings-indde indeed, some of the E, may distinguish different correct labellings.
Relation to previous results. Our framework of a finite number of user-specified "error types" includes multiclass classification as a particular case, and it in this field that one finds the work most closely related to ours. Little is known of multiclass classification from theoretical perspective and, to the best of our knowledge, only a handful of relevant strategies or generalisation bounds can be compared to the present paper.
The closest is the work of Morvant et al. [2012), which establishes a PAC-Bayes bound on the spectral norm of the difference between the true and empirical confusion matrices. Our bound differs from theirs in two respects. First, they consider the confusion matrix, whereas ours applies the more general setting of finite number of error types, which can be the set of all mis-classifications, or some partition thereof. Second, they deal with the spectral norm, whereas we employ the KL-divergence. Since the KL-divergence follows simple formula, this means we can much more easily infer bounds on the individual error probabilities, which would be very challenging for the spectral norm. The follow-up work Koço and Capponi (2013) shows how a proxy of the spectral norm bound can be used as a training objective that may deal with imbalanced classes. In the present work, we show how our bound can be used as differentiable training objective directly (without the need of a proxy) and

---

that it can more sensitively deal with imbalanced classes, or errors of different severity, by assigning each error type a user-specified loss value.
Laviolette et al. 2017] extend the celebrated C-bound in PAC-Bayes to ensembles, obtaining a bound on the risk of the majority vote classifier in the case of multiclass classification. In this context, our bound is able to distinguish different mis-classifications and control them, whereas they bound the
scalar risk which lumps all mis-classifications together. The C-bound has alternately been generalised
by Lacasse et al. [2006] (see also Germain et al.] (0155) to simultaneously control three metrics, namely the so-called expected disagreement, expected joint success and expected joint error of the posterior. While they restricted themselves to the ternary case, some of their proof techniques share similarities with ours. In cases where one has exactly three error types, for example the (-1, 0, 1}- valued excess loss, the work of Wu and Seldin [2022) is applicable; they construct so-called 'split-kl' inequalities (both classical and PAC-Bayesian) which deftly handle this specific scenario.
Pires et a 2013 present a comprehensive analysis of convex surrogate losses in cost-sensitive multiclass classification, providing conditions for consistency, bounding the excess loss of predictor, and extending the analysis to the "Simplex Coding" scheme. We are considering the generalisation gap rather than the excess loss. Lei et al. [201]] study data-dependent bounds for multiclass classification. Their analysis is restricted to SVMs however, whereas ours applies to arbitrary hypothesis spaces.
Outline. We fix notation in Section 2 Theorem T in Section 3 is our main result- a PAC-Bayes bound the KL-divergence between the true and empirical error distributions. For multiclass classification with a fully refined partition this becomes a bound on the KL-divergence between the true and empirical confusion matrices. Proposition I then bounds the individual error probabilities. Our second main result, Theorem 2 in Section + allows us to use bounds on linear combinations of error probabilities training objectives. We prove Theorem [ in Section [5] via Proposition [ which bounds the distribution of errors via a general convex function d and may be of independent interest. Section outlines positive empirical results] from using our bound training objective for neural networks and Section 7 gives perspectives for follow-up work..
2
Notation
For any set A, let M(A) be the set of probability measures on A. Let X' and Y be arbitrary input (e.g., feature) and output (e.g., label) sets respectively, and D E M(X x Y) be data-generating distribution. For any sample S D drawn i.i.d. from D, let D(S) M(X'' x )) denote the empirical distribution D(S)= = EinnEE 8(za))- We consider the setting where the user has specified partition (Fi,..., FAs) ) of yd2 into M error types.
We are interested in simple hypotheses h X' + Y and soft hypotheses H : X
M(Y).. For example, a neural network outputting scores (logits) in RR' is converted to a simple or soft hypothesis, respectively, by passing the scores through the argmax or softmax function, respectively. For any A J. H (A) can be interpreted as the probability according to H/ that the label of x is in A. We will see in Section 4 that soft hypotheses permit more flexible training procedures and a more fine- grained analysis. Note that while soft hypotheses output distributions, they do so deterministically. always returning the same distribution for the same input æ. and so are distinct from the stochastic classifiers introduced shortly.
For a simple hypothesis h x y and j E [M], define the j-risk of h to be R = ((x())-((h(())))))) v) E Ez), namely the probability that h makes an error of type E, for ran- domly sampled (z.v) D. For a soft hypothesis H X M(')) define the j-risk of H to be (H) == IP (=.,)>>,)--(>>((( y) E Ej), namely the probability that one would make an error of type E, on randomly sampled (z.
D if one predicted by sampling ý from the distribution Hxx). From now until Section 4 it will not matter whether we are dealing with simple or soft hypotheses. So, unless stated explicitly, we will refer both simply as hypotheses, denote both by lowercase h, and refer to the hypothesis class H. whether it is a subset of y or M())**
Our goal is to control the risk vector RD (h) (h), ... RM (h)). since controlling this vector controls all linear combinations of j-risks. Since this is unobervable, we will control it by
'Code available here: httppp///ggtthaalccco/////o/eues
3

---

bounding how far it diverges from its empirical counterpart Rs(h) := Biss (h), which we term the empirical risk vector. Note that ES-D... (h) (p( and that, for simple hypothesis E yi² (h) is the vector of proportions of the sample on which h makes an error of type E Since the Ej partition ) Ro(h) and Rs(h) are elements of the M-dimensional simplex Ars == {u E [0, 1] un +... + UM 1). Thus can choose our divergence measure to be (b)]l where for q.P E M we define kl(g) =- - 91 In 21 When M = 2 we abbreviate kl((g. 1 2) 1 p)) to kl(glpp). which is then the conventional definition of kl(-ll-) found in the PAC-Bayes literature [as in Seeger 2002 for example]. We define the risk and empirical risk of Q (Q == Rn-oRD( (h) and Rs (2) := (g respectively, and seek bound on kI R for sample S of size m, we have that R2(Q) = K /m where K ~ Mult(m, M, RD(Q)). Recall that for m, .M E N and r E AM, the multinomial distribution Mult(m, M, r)
(Q)). Note we still have Es Rss = (Q) this time using Fubini. Moreover,
has probability mass ml for &, where (e, m knd) IT hzt
function Mult( (;; m, M, r) == (e. k2 kNd) 11 r
E Sm,M == { (KI,.... ..a))....... E ND : ki .... ky = mm. and zero otherwise. As a final piece of notation, we let A == Ass n (0, 1)M and S. == Sm, n NM denote the vector elements of MM and Sm.M, respectively, that have no zero components.
3 Main result
We now state our main result, which bounds the KL-divergence between the true and empirical risk vectors RQ( and (Q()), interpreted probability distributions. As is conventional in the PAC-Bayes literature, we refer to sample independent and dependent distributions on M(H) (i.e. stochastic hypotheses) as priors (denoted P) and posteriors (denoted Q) respectively, even if they not related by Bayes' theorem.
Theorem 1. Let X and y be arbitrary sets and U, Ey be disjoint partition of y2 into M error
types. Let D E M(X x y) be data- geau--gneratinng distribution and H be simple (H C yd ) or soft (H E & hypothesis class. For any prior P E MMH)), 5 E (0, 1] and sample size 2 M, with probability at least 1 - over the random draw S ~ Dn,, we have that simultaneously for all posteriors Q E MMH), the divergence kl (1(R((Q) [D
(Q)) is upper bounded by
((m,M)
KL(QIIP) + In
where
8
E(m, M) == (122l
(m)
M-1
MM-1 (M) (2) 82 T (M--))* E0 (M (0mM))
The fact that the logarithmic term is of order O(M lm(M) means the bound is linear in M up to logarithmic terms, while this may seem excessive, one should note that the quantity that our theorem bounds also depends on M. Further, the bound has been successfully used in by Biggs and Guedj 2023 to improve on state of the art PAC-Bayes bounds.
To see how our bound compares to existing PAC-Bayes bounds for binary classification, take [-1,11,, .M- = 2, E1 = {(-y, y) y E }}} and Eg (v. y }}. The argument of the logarithm then reduces to _ (/13m) (2 + 2 < 1.25./m when m is large. The corresponding term in Maurer (2004) is 2/m which is only larger because he relaxes the term for aesthetics. Therefore our bound gracefully reduces to Maurer's in the case of binary classification.
Suppose after use of Theorem D we have a bound of the form kl can then derive bounds on the individual j-risks Ry (Q) or, more generally, linear combinations thereof. While one could obtain such bounds perhaps more directly with existing PAC-Bayes bounds, the significance of our bound is that all such derived bounds hold with high probability simultaneously. Existing PAC-Bayes bounds would require the use of a union bound in order to bound multiple combinations simultaneously, whereas ours bounds all uncountably many combinations simultaneously, as a package. As for the individual j-risks RE (Q), the following proposition
s B. We
2 ((R)) R2' (h) = P (((())) v) E E2) 1 - Eiawes 1 [lb(=),)) Ez]- We follow the usual convention that 0 _ = 0 for x 2 0 and in 30 for 0.

---

then yields the bounds L; v Rb(Q) & US, where L, == inf E [0,1] kI k (Q)lp)) - B} and U, = suptp E [0 (Q)ll) I B). Moreover, since in the worst case have kl (Q) (Q))) = B, the proposition shows that the lower and upper bounds Lj and
U, are the rightest possible, since if (Q) & [T. Uj] then (Q) (Q)) >
B implying
kl (I)Rs(Q)) (Q)) > B. For a more precise version of this argument and a proof of Proposition | see Appendix C.4
Proposition 1. Let q.P E Av. Then kl(g; l1pp)) S kl(alp)) for all j E [M], with equality when L- I- q: for all + j.
More generally, suppose we can quantify how costly an error of each type is by means of loss vector L E [0, , where Ej is the loss we attribute to an error of type Ej. We may then be interested in bounding the total risk R. (Q) = l. RD((). Then, given bound kl R&s (Q))) < B from
Theorem 1 we can deduce
(Q) S sup (l. (f.r:re E Ars (()ss(Q)ll)) S B)= = l. (Rs()
(2)
where we define klp (ule) E 4M as follows. To see that it is indeed well-defined (at least when u E A ) see the discussion at the beginning of Appendix C.5
Definition 1. For u E AM,C E x0) and l E [0, )O)M, define klp (1(((()) to be an element
AM solving the constrained optimisation problem
Maximise:
fe(v) = l.v,
Subject to: kl(ull v) S c.
This motivates the following training procedure: search for posterior Q for which the bound L klp" (Rs(Q) on the total risk (Q) is minimised. While this requires a particular choice of loss vector f, we emphasise that at the end of training. Theorem I bounds kl (Rx{(() (Q)) and so can be used to bound any linear combination of the j-risks, not just the one given the loss vector l chosen for training. is this flexibility which is the main advantage of our bound; changes in the severity of different error types over time do not require union bounds or retraining.
In the next section we provide a theorem for calculating kl, 1 (u/e c) and its derivatives so that the training procedure can be executed.
4 Construction of a Differentiable Training Objective
We now state and prove Theorem which provides speedy method for approximating (ulc) and its derivatives to arbitrary precision, provided
and Vj Uj > 0. The only approximation step required is that of approximating the unique root of a continuous and strictly increasing scalar function. Thus, provided the u, themselves are differentiable, Theorem combined with Theorem 2 shows that the upper bound on the total risk can be used as a tractable and fully differentiable training objective. See Appendix A for more details, including a pseudocode algorithm and an implementation. Since the proof of Theorem 2 is rather long and technical, we defer it to Appendix
The requirement that the l are not all equal only rules out trivial cases where (Q) is independent of (Q).).
C.5
Theorem 2. Fix [0, :O) such that not all E are equal, and define Se : A. - 10, xx) by fe(u) = الاe For all ū = c) E M x (0, co). define o² (ū) == kl, (u|c) E AM and let (r" E (-x., maxx Ej) be the unique solution to = &be(1)), where the (-oc,- maxj Eÿ) TR. given by Φe(u)= == In(- EM ) ΣØ uj In(- + (2)), which is continuous and strictly increasing, Then v² (ū) ² is given by
(ū)uz
M
v" (ū);
n² (ū) + +lj for E [M]. where X((ū)= =
Σ
(5)
+2
Further, defining fi A x (0, 20) + (0) by fj( = ((((((ū)) we have that
:=
0fi ( X²) 1++h In -
U and
0fi
(i) = (ū))
(6)
Juj
dc
5

---

A final wrinkle in evaluating our bound is that while the empirical risk vector Rs(Q) Ra-Q Rs does not depend on the data-generating distribution D. the expectation over Q may still be in- tractable. This would be the default case when Q is a Gaussian over the weights of a multi- layer perceptron, for example. In such cases, we can estimate (Q( via a Monte Carlo sample (Q( :- Φ En Rs(ha) (where the hi are drawn i.i.d. from Q) and use the following two results. Proposition 2 shows that the kl
(Q)) can be simultaneously bounded, whence Proposition 3 can be used to obtain a bound on (I(Rs(Q) [D())).
Proposition Let X ~ Multinomial(N, M. p). Then for any (0. with probability at least In 2M
1 8 we have that for all j [M] simultaneously kl ( [p)) <
Proof. Each bound holds separately with probability at least 1 8/M by Theorem 2.5 in Langford and Caruana (200T]. They then hold simultaneously by application of union bound.
Proposition 3. Suppose q, P, q E AM are such that (1 (p) < Bi and (( S B2 for all
j E [M]. For each j. define y ir E [0, 1] kl(; ([)) S B2). Then
M
kl(@lp)) S MB2
Σ ==1
(1
In
1- 91 + B1 max
41 + B1 as B2 +
1 9
93
Proof. Deferred C.I
The fact that the bound on kl(()lp) - B1 as B2 + 0 ensures that as we increase the size of our Monte Carlo sample for estimating (Q) the bound on kl (I)R (Q)) approaches that of kl (Q)] (Q)), meaning in the limit we pay arbitrarily small price in the bound for the approximation.
5 Proof of the main bound
We split the proof of Theorem T into three parts. First, we prove Proposition a bound on d(Rs(Q) (Q), (Q)) for arbitrary convex function d, which may be of independent interest. Second,
we prove Corollary| [ by specialising Proposition to the case d(. ) = I.) Finally, we show that
the bound in Theorem [ is loosened version of the bound in Corollary [
Proposition 4. Let d A
R be jointly convex. In the setting of Theorem 7
S KL(QIIP) Ia(m, 5
where
(8)
Im 3) = supreAM EbESm.. Mult(k; m. M, r) exp (Bd ( (nrr))-
This is a generalisation of the unifying PAC-Bayes bound given in Bégin et al. the scalar risk quantities Rs(Q) and (Q( with their vector counterparts Rs(Q) and RD()). To
2016
where we replace
see this, note that we can recover it by setting y = (-1,1), M 2, E, = ((-..)) y E )}
and E2_ = ((. v) : y Jj. Then, for any convex function d [0, 10 + R. apply Theorem
4 with the convex function d' A3 + IR defined by d' ((u,, u2), (VI, 02)) = d(ui, v1) so that
Theorem bounds d' (Q).). (n) = (Q), (Q)) which equals di ((Rs(Q), (Q))
le in the notation of Bégin et al. [2016]. Further, EkESm.. Mult(k; (; m, 2, exp (ddd (tx (rrr))
so that the supremum over [0, 1] of the right hand side equals the supremum over r E Ag of the left hand side, which, when substituted into (8) yields the
m Σ Bin(k; m)) exp Bd
m ri)
bound given in Bégin et al. [2016].
To prove Proposition 4 we require the following two lemmas. The first is the well-known change of measure in equality (Csiszár 1975 Donsker and Varadhan 1975). The second is generalisation from Binomial to Multinomial distributions result found Maurer (2004), the proof of which
we defer to Appendix C.2

---

Lemma 1. For any set H, any P.Q E (M(H) and any measurable function o : H - R, E o(h) - h~Q
P)(Q]))) + In E exp(((h))) hwP
Lemma 2. Let XI...., Xm be i.idd Axr-vlledd random vectors with mean I and suppose that f AM 7 is convex. X Xi...., X are i.i.d. Mult(1, M. random vectors, then [ Xm) - _B] m.
The consequence of Lemma is that the worst case (in terms of bounding di Rs(Q), Ro(Q))) occurs when ((z,))) (h) is one-hot vector for all (æ, E S and h E H. namely when H E M()))* only contains hypotheses that, when labelling S. put all their mass on elements Ó E y that incur the same error type In particular, this is the case for hypotheses that put all their mass
single element of V. equivalent to the simpler case H C )x as discussed in Section 2 Thus, Lemma Lemma[[show, shows that the bound given in Proposition cannot be made tighter only by restricting such hypotheses.
Proof. (of Proposition 4) The case H. C yx follows directly from the more general case by taking H'' = {h' (M())** 3h E H. such that Var X' h'(z) ōn(m)) } where ōλ(a) E .M())) denotes
point mass on hx:). For the general case H. S M()) using Jensen's is inequality with the convex function -) and Lemma | with 6(h) = (h)), (h(h)), we see that for all Q E M(H)
(o( 3d
E Rs(h), E Ro(h)) h~Q
hnQ
s E 3d h~a
3d(Bd Rs (Rs(), Ry(h))
s KL(Q1IP) + In
E exp [Bd (R((),, Ro((i))
haP
= KL(QIIP) + (n(2(
where Zp(S) EN~P exp (Bs(Rs RD(h)) Note that Zp(S) non-negative random 7pp(S) S Re (r(8")
- Thus, since In(.) strictly increasing, with probability at least 8 over S ~ Dm, we have that simultaneously for all Q E MMH)
variable, so that by Markov's inequality p
SmDm
E Bd (d(Rs(Q), RD(()) S KL(QIIP) + SmDm
Zr(S')
To bound ES Zpp'') let X; == R(( y3 (h) E AM for i E [m], where (I,, (x,, is the i'th element of the dummy sample S' Noting that each X; has mean (h),), define the random vectors X Mult(1, M, (h))) and Y == Σn X Mult(m, M, (h))... Finally let f AN E be defined by f( Tm. == exp (3d m EE Iú, RD(h)) which is convex since the average is linear, is convex and the exponential is non-decreasing and convex. Then, by swapping expectations (which is permitted by Fubini's 's theorem since the argument is non-negative) and applying Lemma we have that Eg (S")
(L
can be written as
Eg Zr(S")
E
E exp (dd(Rs: (R), RD(()) h~P
S'mDm
= E
E
cxp
Rs (h), RD()))
h>P
S/m
= E
B
exp
Bd
X, (D)
h-P
X
X
<
E
E
exp
3d
X Rn(h))
hsP
X
K!...
= E
E
exp
Bd
Y. RD (D(())
h-
'More precisely, when 4h E H ((o.)) E S 3j E [M] such that A(z) y. (0.v) E EJH =

---

Mult(k; M, RD()) exp (Bd( RD(h))
E hnuP
M
Mult(k;,,M,, exp (Bd( th .))
s sup rEAM
kES
which is the definition of [m (3). Inequality Zp("") into (9) and dividing by 3.
then follows by substituting this bound
L
We now specialise Proposition to the case d(.,)) kI(-Il-) obtain Corollary Corollary 1. In the setting of Theorem !
((RR(Q))|R((()) - 1
P) + In 7(m, M)
where
(10)
5
me!
M
K
q(m, M)
Σ
(11)
m
f=1 ky!
KESm.
Proof. Applying Proposition 4 with d(::.) kl(-Il-) and B m gives that with probability at least over S ~ Dm, simultaneously for all posteriors Q E EM(H.
1
KL( + In Ia(m, m)
kl (Rs(QQ)(R((()) - m
where Ial (m, m) == SuPrEAM EEKS Mult(k; m, M, r) exp (mkl( r)]]. Thus it suffices to show that [m, m) I (m, M).
To prove this, for each fixed Mult(k; m, M, r) O for any & Sm,as such that k, * for some j Jr. For the other k E Sm.M, namely those such that ky 0 for all j E Jr. the probability term can be written as M 1==
(ri,..., (M) E AM let J. e M 0}. Then
Mult(k: k; m, M,,) I RyT
MT EyT IL ry and (recalling the convention that
0 8
0) the term exp(mkl( r) can be written
M
ky exp
exp
m
Σ ki j
In
ly mey
k YIr,
mI
JEJ,
JEJ,
where the last equality is obtained by recalling that the ky sum to m. Substituting these two expressions into the definition of Tai (m, m) and only summing over those & Sm.M with non-zero probability, we obtain
Mult(k; m, M, r) exp (mkl r))
Σ A VjEJ, ky=0
Mult(k; m, M, r) exp (mkl (+ r)
KES
kj
Σ
m!
k
Ilier, ki!
mm
Fg.
KCS Ms VjeJ, ky
ig
m!
Σ
k
m
ky
KE5 k2=
JZJ+
kjEJ,
M ki
m!
Σ
(because Of 1)
m
ky!
keSm vjEJ- k2=
j=1
m!
Σ
m
ky!'
kc
8

---

which is 17(m, M). Since this is independent of it also holds after taking the supremum over A M of the left hand side, showing that (m, m) $ (mm
The final step in obtaining Theorem | is to loosen the bound given in Corollary | (which is intractable when m large) to the tractable form given in Theorem For this we require the following technical lemma, the proof of which we defer to Appendix C.3
M r(
Lemma 3. For integers M Z and m 2 M, Enesp
I1 Vky
Proof. (Of Theorem It suffices to show that for all m 2 M 2 1 we have n/m, M) S {(m, M). We achieve this by applying Stirling's s approximation V2Tn for n 2 1) to the factorials in ry(m, M) and then using Lemma
nl 22 (2) e (valid
Since Stirling's approximation requires that all the h are least one, we partition the sum in nm,, MM according to the number of coordinates of k at which ky
= 0. Let index the number of such coordinates. Defining f UM= Sm.M M + R by fik) = [Ml k /ky! and noting that f is symmetric under permutations of its arguments, we then have
n/m, M)
m!! m
Σ
f(k)
m!
M
Σ
f(k).
(12)
m
&
kE m. M-
ki
Stirling's approximation can now be applied to each & E S f(k) S II,
j=1
2 R
I 2
M
An application of Lemma 3 now gives
(2x)a/3
j=1
S(K)s
e
M -
m
π
M-=
770
E m
M---2
(2Tr)
(2
M
-
M 2
kg8 M
AES30 m.M
1=1
Substituting this into equation (22 and bounding m! using Stirling's approximation, we have
n(,, M) < //rme 1/(2mm)
EnO M
M
((m+))) E(m, M), which completes the proof of
the bound. As for the order of the bound, it is sufficient to bound In (m,, using the crude approximations (a S MM, (2/m)a/2 < 1 and T((M - =)/2) 2 1.
Numerical experiments
We use binarised versions of MNIST, and HAM10000 y² into E, = {00, 0), 1)}, E = (0, 1)} and Eg = [110)], and take & = (0, 1,3). Each dataset is split into prior and certification sets. We take H. to be two-layer MLPs. As is common in the PAC-Bayes literature, we restrict P and Q to be isotropic and diagonal Gaussian distributions over the parameter space, respectively. The means of P and Q are set the parameters of MLP trained on the prior set. The mean and variances of Q and the variance of P are tuned via Theorem 2 to minimize the bound the total risk R7 (Q). See Appendix A for pseudocode, Appendix B for full experimental details and https:tt////... //gi htt//ggttubbb.. thub. wtt http://www...eeeeeeoooooooaaaaaa ContsoC for code. The results for MNIST can be seen Figure [
2018). In both cases we partition
We estimate Rs(Q) with a Monte Carlo and obtaín a PAC-Bayes bound on RT, (Q) by combining
Proposition 2 (with 8 0.01 and N = 100000) and Proposition] We obtain (Q) I 0.2640 for MNIST and (Q) < 0.8379 for HAM10000, where both bounds hold with probability at least 1 - 0.05- - 0.01 = 0.94. While these bounds are far from vacuous-th maximum possible value of QB) is for our choice of t-one might wonder whether one can do better by bounding each error probability individually using Maurer's inequality Maurer [2004), and then unioning these bounds. As with our Theorem I this would also constrain the entire distribution of error types since for any l, one could then calculate the maximimum value of RT (Q) that satisfies all of these constraints. Both

---

Dataset
Volume Our Region
Volume Maurer Region
MNIST
0.0025 (0.002496 0.002504)
0.0028 (0.002793, 0.002800)
HAM10000
0.0012 (0.001207, 0.001211)
0.0011 (0.001 142, 0.001146)
Table 1: Point estimates and 95% confidence intervals for the volumes of the confidence regions for (Q) given by Theorem and union over M individual Maurer bounds, respectively. Our method is superior for MNIST and inferior for HAM100000.
Bound Total Risk
Empirical Error Probabilities
Bound kl|R_ [|R__[@]||R_DO)
0.01
0.3
0.008
0.29
0.6
0.006
0.26
0.4
0.004
0.24
0.2
0.002
0.22
Epoch
0
0
100
(a)
(b)
(c)
Figure Experimental results for binarised MNIST. (a) The PAC-Bayes bound on the total risk decreases when tuning the posterior via Theorem 2 (b) This is achieved by shift in the empirical
error probabilities. (c) The bound on (s (Q) RD (Q) is not substantially increased, meaning we still retain good control of RD(Q) after optimizing for this particular choice of L.
methods constrain the region of the simplex in which (D( can lie (with high probability), and reasonable metric by which to compare them is the volumes of these regions. This can be estimated via a MC sample by uniformly sampling points r from A. and counting how samples are legal values of RD(Q according to each method. The 95% confidence intervals for the volumes of the two regions are given in Table A more comprehensive table for synthetic values of RQ(Q) can be found in Appendix
Perspectives
We introduce the framework of error types, considering the vectors (c) and (D(Q) of empirical and true probabilities of errors of different types. We prove a PAC- bound (Theorem I on (I)R((Q)]] [Q)))) which controls the entire distribution of error probabilities, and hence can be used to derive bounds on arbitrary linear combinations of the error probabilities, all which hold simultaneously with high probability; this cannot be achieved with any existing PAC-Bayes bound.
We construct a differential training objective based on our bound by introducing the the vectorised kl inverse, providing recipe for quickly computing its value and derivatives (Theorem ( Our framework flexible enough to encompass multiclass classification or discretised regression, but also structured output prediction, multi-task learning and learning-to-lear..
Another potential application of our work is to the excess risk, since under a misclassification loss there are three different етrоr types, corresponding to excess losses of {-1, O, 1}. Biggs and Guedj 2023) adapted Theorems [ and this setting, leading an empirically tighter PAC-Bayes bound for certain classification tasks.
We require i.i.d. data, which in practice is frequently not the case is hard verify. Further, the number eтror types M must be finite. In continuous scenarios would preferable to able to control the entire distribution of loss values without having to discretise into finitely many error types. We leave this direction to future work.
10

---

Acknowledgments and Disclosure of Funding
We warmly thank reviewers and the Area Chair who provided insigthful comments and suggestions which greatl helped us improve manuscript. R.A. was supported by the UKRI grant number EP/S021 and gratefully thanks Felix Biggs for his insights. J.S-T gratefully acknowledges the European Union's Horizon 2020 Research and Innovation Program through the grant numbers 951847 (European learning intelligence, HluaanE-AI-Ner
and intelligent systems excellence, ELISE) and 952026 (Human-centre) artificial
B.G. acknowledges partial support by the U.S. Army Research Laboratory and the U.S. Army Research Office, and by the U.K. Ministry Defence and the U.K. Engincering and Physical Sciences Research Council (EPSRC) under grant number EP/R013616/ B.G. acknowledges partial support from the French National Agency for Research, through grants ANR-18 ANR-18-8 18--E-400000--0000 and ANR-18- CE23-0015-00 and through the programme "France 2030" and PEPR IA on grant SHARP ANR-23 -NR-233PEIA--008.
References
Pierre Alquier. User-friendly introduction to PAC-Baaes bounds. arXiv preprint
2021.
Amiran Ambroladze, Emilio Barrado-Hernández and John Shawe-Taylor Tighter PAC-Bayes bounds. In Bernhard Schölkopf, John C. Platt, and Thomas Hofmann, editors, Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems. Vancouver, British Columbia, Canada, December 4-7, 2006. pages 9-. MIT Press, 2006.
www.diiinnnnnnninn....e. nwwriperrrcccmm cc/ wttps/cccppppe/////////// Abstract .ttmtrract.ttt.ll
Felix Biggs and Benjamin Guedj. On margins and derandomisation in pac-bayes. In International Conference on Artificial Intelligence and Statistics, pages 3709-3731. PMLR, 2022a.
Felix Biggs and Benjamin Guedj. Non-vacuous generalisation bounds for shallow neural networks. In International Conference on Machine Learning, pages 1963-1981. PMLR, 2022b.
Felix Biggs and Benjamin Guedj. Tighter pac-bayes generalisation bounds by leveraging example difficulty. In International Conference on Artificial Intelligence and Statistics, pages 8165-8182. PMLR, 2023.
Luc Bégin, Pascal Germain, François Laviolette, and Jean-Francis Roy. PAC-Bayesian Bounds based on the Rényi Divergence. In Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages
Cadiz. Spain, 09-11 May 2016. PMLR. URL httll
https://proceeddnng.. mlr pttp.a........//////gggiiaa.
Olivier Catoni. A PAC-Bayesian approach to adaptive classification, preprint, 840, 2003.
Olivier Catoni. Statistical Learning Theory and Stochastic Optimization: Ecole d' Etéé de Probabilités de Faint-Flour XXXI-2001. Springer, 2004.
Olivier Catoni. PAC-Bayesian Supervised Classification: The Thermodynamics Statistical Learning, volume 56 of Institute of Mathematical Statistics (IMS) Lecture Notes Monograph Series. Institute of Mathematical Statistics, 2007. ISBN 9780940600720. URL https: httpps:///booo..o google fr/
books?1d
Eugenio Clerico, George Deligiannidis, and Arnaud Doucet. Conditionally gaussian pac-bayes. In International Conference on Artificial Intelligence and Statistics, pages 2311-2329. PMLR, 2022.
Imre Csiszár. I-divergence geometry of probability distributions and minimization problems. The Annals of Probability, pages 146-158, 1975.
MD Donsker and SRS Varadhan. Large deviations for Markov processes and the asymptotic evaluation of certain markov process expectations for large times. In Probabilistic Methods in Differential Equations, pages 82-88. Springer, 1975.

---

Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Conference on Uncertainty in Artificial Intelligence [UAI], 2017.
Gintare Karolina Dziugaite and Daniel M. Roy. Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of entropy-SGD and data-dependent priors. Jennifer G. Machine
Dy and Andreas Krause, editors. Proceedings of the 35th International Conference Learning, ICML 2018, Stockholmsmüssann Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 1375-1385, PMLR, 2018. URL http mlr
//proceedings mlr press/v800 dz http://iuugaataaa... html
Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, and Daniel Roy. On the role of data in pac-bayes bounds. In International Conference on Artificial Intelligence and Statistics, pages 604-612. PMLR, 2021.
Pascal Germain, Alexandre Lacasse, Francois Laviolette, Mario Marchand, and Jean-Francis Roy. Risk bounds for the majority vote: From pac-bayesian analysis learning algorithm. arXiv preprint arXiv:I503. 000..5000300333 0839,, 2015.
Benjamin Guedj. A Primer on PAC- MAC-Bayesian Learning. In Proceedings of the second congress of the abs 1901 05353
French Mathematical Society, 2019. URL
Sokol Koço and Cécile Capponi. On multi-class classification through the minimization of the confusion matrix norm. In Asian Conference on Machine Learning, pages 277-292. PMLR, 2013.
Alexandre Lacasse, François Laviolette, Mario Marchand, Pascal Germain, and Nicolas Usunier. Pac-bayes bounds for the risk of the majority vote and the variance of the gibbs classifier. Advances in Neural information processing systems, 19, 2006.
John Langford and Rich Caruana. (not) bounding the true error. Advances in Neural Information Processing Systems, 14, 2001.
François Laviolette, Emilie Morvant, Liva Ralaivola, and Francir Roy. Risk upper bounds for general ensemble methods with an application to multiclass classification. Neurocomputing, 219:15-25, 2017. ISSN 0925-2312. doi: http:///hi.aaoo//llooooo.ennnnon https://www htt.a/acccccacccc.ooo///ooaaaaaa
2016.09..16 URL
Yunwen Lei, Ürün Dogan, Ding-Xuan Zhou, and Marius Kloft. Data-dependent generalization bounds for multi- classification. IEEE Transactions on Information Theory, 65(5):2995-302 2019. doi: 10.1109/T1.2019.2225 28939916.
Gaël Letarte, Pascal Germain, Benjamin Guedj, and Francois Laviolette. Dichotomize and generalize: PAC-Bayesian binary activated deep neural networks. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. dAlché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 6872-6882. Curran Associates, Inc., 2019.
Guy Lever, François Laviolette, and John Shywe-Taylor. distribution-dependder PAC-Bayes priors. In International Conference on Algorithmic Learning Theory, pages 119-133. Springer, 2010.
Guy Lever, François Laviolette, and John Shawe-Taylor. Tighter PAC-Bayes bounds through distribution-dependeent priors. Theoretical Computer Science, 473:4-28, February 2013. ISSN 0304-3975. doi: 10. 10.100666..ss200 (Bor:eere/p11//3343377/12222
URL.
elsevier. com/
Andreas Maurer. A note the PAC-Bayesian theorem. arXiv preprint cx/041 2004.
David A McAllester. Some PAC-Bayesian theorems. In Proceedings of the eleventh annual conference on Computational Learning Theory, pages 230-234. ACM, 1998.
David A McAllester, PAC-Bayesian model averaging, In Proceedings of the twelfth annual conference on Computational Learning Theory, pages 164-170. ACM, 1999.
Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte carlo gradient estimation in machine learning. J. Mach. Learn. Res., 21(132):1-62, 2020.
12

---

Emilie Morvant, Sokol Koço, and Liva Ralaivola. PAC-Bayesian generalization bound on confusion matrix for multi-class classification. In Proceedings of the 29th International Conference on Machine Learning, ICMI. 2012, Edinburgh, Scotland, UK, June 26 July 1, 2012. icml.cc / Omnipress, 2012.
pttttp://iem..c////e 2e1/2//////a////////2 papers/433 ../../44........ pdf)
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-Bayesian approach to opectrally-normalle margin bounds for neural networks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC. Canada, April 30 May 3, 2018. Conference net net/forumiid-Stt
Track Proceedings. OpenReview.net, 2018. URL (ttppttts///ppeereviiii htw.:/pewwweeee.e.eeoooerrrrreee
WfbCZ
Emilio Parrado-Heernnddzz, Amiran Ambroladze, John Shawe-Taylor, and Shiliang Sun. PAC- Bayes bounds with data dependent priors. J. Mach. Learn. Res., 13:3507-3531, 2012. URL
http://al. acm. org/citation.
María Pérez-Ortiz, Omar Rivasplata, Benjamin Guedj, Matthew Gleeson, Jingyu Zhang, John Shawe- Taylor, Miroslaw Bober, and Josef Kittler. Learning pac-bayes priors for probabilistic neural networks. arXiv preprini arXiv: 10022000000040 10304, 2021.
Maria Perez-Ortiz, Omar Rivasplata, John Shawe-Taylor, and Csaba Szepesvari. Tighter risk cer- tificates for neural networks. Journal of Machine Learning Research, 22(227):1-40) 2021. URL http://jmlr www.orgg.geeeeeeeeoooooooo pwtppp/ppp2/222.-.. 879. html
Bernardo Avila Pires, Csaba Szepesvari, and Mohammad Ghavamzadeh. Cost-sensitive multiclass classification risk bounds. In International Conference on Machine Learning, pages 1391-1399,
PMLR, 2013.
Omar Rivasplata, Csaba Szepesvári, John Shawe-Taylor, Emilio Hhrrado-Heránnder and Shiliang Sun. PAC-Bayes bounds for stable algorithms with instance-dependent priors. In Samy Ben- gio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- desa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréul, Canadu, pages 9234 9244, 2018. URL httpttp::/pppocceeeeeee Abstracttttrttr.... html
Matthias Seeger. PAC-Bayesian generalisation error bounds for Gaussian process classification. Journal of Machine Learning Research, ((Oct):233-266) 2002.
Akira Takayama and Takayama Akira. Mathematical economics. Cambridge university press, 1985.
Philipp Tschandl. The HAM10000 dataset, large collection of multi- source dermatoscopic images of common pigmented skin lesions, 2018. HRLLhttps://aat org/10. 791//////D0000
Yi-Shan Wu and Yevgeny Seldin. Split-kl and pac-bayes-split-kl inequalities for ternary random variables. Advances Neural Information Processing Systems, 35:1 1369-11381, 2022.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Non-vacuous generalization bounds at the ImageNet scale: a PPC-Bayesian compression approach. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL http::///pppmeeeeeeeeeeeer/rrttr
13

---

A Recipe for implementing Theorems 1 and 2
We here outline more explicitly how Theorem I and Theorem may be used to formulate fully differentiable objective by which model may be trained.
surrogate First, if one wishes make hard labels, namely H S D it will first be necessary
class of soft hypotheses H' C M()) during training, before reverting to hard labels for example by taking the mean label the one with highest probability. Using soft hypotheses during training necessary to ensure that the empirical j-risks (Q) are differentiable with respect the model parameters. Since how one chooses to do this will depend on the specific use case, we restrict our attention here the case of soft hypotheses. Specifically, we consider class of soft hypotheses H = (he 0 E [IN S M())) parameterised by the weights 0 E IN of some neural network of a given architecture with N parameters in such a way that the R'g (ha) are differentiable in 0. A concrete example would be multiclass classification using a fully connected neural network with output being softmax probabilities on the classes so that the Rig (ha) are differentiable.
Second, it is necessary to restrict the prior and posterior P. P.Q E M(H) to parameterised subset of (MH in which PL) has closed form which is differentiable the parameterisation. A simple choice for our case of a neural network with N parameters is P. Q E (W(w, diag(s)) dia,(s))))))))))))))))))))))))) we have R.N. : RRNy For prior Per (n, diag(r)) and posterior Qun, the closed form
KL(Qw,xl|Pam (o.,)
Σ
Sn
(wn, )n In TT 8T
N
I'
In
which is indeed differentiable in v, r, w and 8. While Qw.s and Per are technically distributions on RDD rather than H. the KI--divergence between the distributions they induce on H will be most as large as the expression above. Thus, substituting the expression above into the bounds we prove in Section 3 only increase the value of the bounds, meaning the enlarged bounds certainly still hold with probability at least 8.
Third, in all but the simplest cases (Q will not have a closed form, much less one that is differentiable in and 8. A common solution to this is to the so-called pathwise gradient estimator. In our case, this corresponds to drawing 6 ~ (O, I),, where is the N x N identity matrix, and estimating
u. R'gs (Qw,s) V =. [e R2 (w Vw, Rig (hww+
where he denotes the function expressed by the neural network with parameters For proof that this is an unbiased estimator, and for other methods for estimating the gradients of expectations, see the survey Mohamed al. [2020].
Fourth, one must choose the prior. Designing priors which are optimal in some sense (i.e., minimising the Kullback-Leibler term in the right-hand side of generalisation bounds) has been at the core of an active line of work in the PAC-Bayesian literature. For the sake of simplicity, and since it out the scope of our contributions, we assume here that the prior is given beforehand, although we stress that practitioners should pay great attention to its tuning. For our purposes, it suffices to say that if one using a data-dependent prior then it is necessary to partition the sample into S = Sprior U Sgound. where Sprior is used to train the prior and SBound is used to evaluate the bound. Since our bound holds uniformly over posteriors Q .(H),, the entire sample S is free to be used to train the posterior Q. For a more in-depth discussion on the choice of prior, we refer to the following body of work:
Ambroladze et al. (2006), Lever al. [2010] 2013), PParaad-Herránneee
al. [0012] Dziugaite and Roy 2011 2018]. Rivasplata et al. (2018] Letarte et al. 2019] Pérez-Ortiz et al. 2021 Dziugaite
al.] 2021 Biggs and Guedj] 2022a
Finally, given a confidence level 8 e (0, 1]. one may use Algorithm to obtain a posterior Q with minimal upper bound the total risk. Note we take the pointwise logarithm of the variances r and to obtain unbounded parameters on which to perform stochastic gradient descent or some other minimisation algorithm. We use @ denote vector concatenation. The algorithm can be straightforwardly adapted to permit mini-batches by, for each epoch, sequentially repeating the steps with S equal to each mini-batch
14

---

Input:
X, / Arbitrary imput and output spaces
U E3= / A finite partition into error types
L [0, (0,00)
vector of losses, not all equal S = Sprioe U Bound E (X' x 3
th /* A partitioned i.i.d. sample model parameters
N E N /* The number
Po.r, (SSriar) E IR,, rSSprie)) E 1R /* (data-dependent) prior
Q Quo.sa: wo E RN, E R2 /+ An initial posterior
E (0, 1] A confidence level >> /* learning rate
T /* The number of epochs to train for
Output:
Qu w E R.,, 8 E IN /* trained posterior 20
Procedure:
So - log 80 /* Transform to unbounded scale parameters p wo Ço /* Collect mean and scale parameters for f + to 7 do
Draw e 10,1))
- Rs h (expcc
B
KL (Q (ow. + in $ &VTe
m
M-1
Σ ==
M-1
(1)
(
+- (u1,..., uM, B)
G (2Nx(M+1) /* Initialise gradient matrix
F - 0Mr+1 /* Initialise gradient vector for j < M + 11
Fj - 8f2
8ü, (ū) /* Gradients of total loss from Theorem 2
for 1 to 2N do 8ü,
(p) /* Gradients of empirical risks and bound Gi,j + dp
end
end
H - GF /* Gradients total loss w.r.t. parameters t p XH /* Gradient step
end
(p1, (p:.... PN)
8 (exp(pN=1)...., return w, s
Algorithm 1: Calculating a posterior with minimal bound on the total risk.
B Additional Experimental Details
For MNIST map labels {0. 2, 4) to 0 and (5, 7, to 1. For HAM10000 map the cancerous or pre-cancerous labels [Melanoma, Basal Cell Carcinoma, Actinic Keratosis] to and the other labels to 0. In both cases we partition )22 into Es {0, 0), (1, 1)), E₁ = {0, 1)]
and Eg = ((1, (1,0),, and take t= (0, 1,3). For HAM10000, E₁ and Ez then refer to Type and Type Il errors, respectively, and l reflects the greater severity of false negatives.
Each dataset is split into prior and certification sets Sprie S respectively. For MNIST, we use the conventional training set of size 60000 as the prior set, and the conventional test set of size 10000 the certification set. For HAM10000 we pool the conventional train, validation and test sets together and then split 50-50 to obtain prior and certification sets each of size 5860. For HAM00000
15

---

we resize the images to (28, 28) and use just the first channel so that the data dimension is the same for both datasets.
We take H to be two-layer MLPs with 784, 100 and 2 units in the input, hidden and output layers, respectively. As is common in the PAC-Bayes literature, we restrict P to be isotropic Gaussian N (e, and Q to be diagonal Gaussian N (w, diag(s)). Further, as in Dziugaite and Roy [2017] we restrict À be of the form X eexp(-j/b) for some j E N, taking Since, at the end of training, we will then have one prior P3 for each j E N, we can choose the j that 66 minimizes the PAC-Bayes bound provided we take a union over all of them, taking 6, = .スッュ so that
0.1 and
100.
Σ 1 and all the bounds hold simultaneously with probability at least 1 8. After applying Algorithm D we round À to discrete Ay. either up down depending on which gives the smaller bound.
For both datasets we set the prior mean v to be the parameters of an MLP trained on the prior set. In both cases we use SGD with learning rate 0.01 to minimise the cross-entropy loss, using portion of the prior set validation set. For MNIST we train the MLP for 20 epochs to get an error rate of 14%, for HAM10000 we train the MLP for 5 epochs to get an error rate of 22%. We then apply Algorithm T By combining Proposition (with 6 = 0.01 and N 100000) and Proposition 3 We obtain Rs ()) (0.8879, 0.0919, 0. 0.0203) and R (Q) < 0.2644 for MNIST and (y) = (0.7860, 0.0146, 0. 0.1995) and [T[(1 - 0.8379 for HAM10000, where both bounds hold
with probability at least - 0.05 - 0.01 = 0.94.
The full results shown in Figure 2 Figures 2a
the same as Figures la 1b and Tcl and are repeated here for easier comparison with the HAM 0000 results. Figure 2b shows that Algorithm
2c and Ze
[ has failed to reduce the bound on the total risk beyond the initialisation of Q P. with the small variation being explained by different MC samples being drawn from Q during training rather than Q changing substantially. Indeed, Figure Figure2hh]soone shoss that Q does not appreciably move from its initialisation at P- remains below 0.1 whereas in the MNNIST experiment, which has the same number of parameters, exceeds 30. It is therefore unsurprising that Figures 2d and 21 show negligible change in the empirical error probabilities and the bound on (.R R)(() respectively. The divergence in the results is likely due to the difference in sample size; the certification set for the MNIST experiment contains 10000 samples, whereas for the HAM10000 dataset there are only 5000, which, all else equal, makes an increase [I] twice as expensive.
Recall from Section 6 that while (D( can be effectively constrained to a sub-region of the simple Ass using our Theorem T this can also be achieved by unioning M Maurer bounds, one for each error probability. Table I gave the 95% confidence intervals for the volumes of the confidence regions in which (Q) was likely to lie for experiments on MNIST and HAM10000, but neither region was uniformly smaller, making it unclear which method should be preferred.
Table provides additional data by taking synthetic values for (Q(Q) and [L()|P), for different values of m (the size of the certification set) and M (the number of error types). 'Individual' denotes unioning individual Maurer bounds, 'Ours' is method, 'Intersection' is the intersection of the confidence regions given by the previous two methods (but loosened so that they now both hold simultaneously with probability at least 0.95), and 'Morv.' is the confidence region produced by Morvant's s bound Morvant et al. [2012). The 95% confidence intervals for the volumes of all the regions have been produced by Monte Carlo samples. We see that our confidence region is tighter than the individual one in 4/9 cases (green), worse in 3/9 cases (red) and ties in 2/9 cases (orange). Interestingly, union bounding the naive CR and our CR and intersecting often beats both of these (bold). Morvant's 's result is either not applicable or their confidence region is much larger than ours and essentially takes up the entire simplex, hence the volume estimate of 1.000. The reason their bound is sometimes inapplicable is because it requires every class to contain at least 8L instances, where T. is the number of labels in the I, 5, M 25, m 100 case this would require each class to contain at least 5 8 = 40 instances which is impossible with m = 100 samples.
16

---

PAC-Bayes Bound on Total Risk
PAC-Bayes Bound on Total Risk
0.723
0.3
0.7225
0.28
0.722
0.26
0.7215
0.721
0.22
Epoch
20
40
60
80
100
40
80
100
(a)
(b)
Empirical Probabilities
Empirical Probabilities
0.8
0.8
0.4
0.4
100
(c)
(d)
PAC: PAC-Bayes Bound on [||R_S[Q][[R____
PAC Bay-s Bound on [IRR_S[Q]||R_D[Q)
0.01
0.01
0.006
0.006
0.002
0.002
Epoch
Epoch
0
20
40
60
80
100
20
40
60
80
100
(e)
KL(Q]IP)
KL/Q/IP)
Muhm.
0.04
0.02
Epoch
Epoch
0
(g)
(h)
Figure MNIST (first column) and HAM10000 (second column) experiments.
17

---

M
m
Vol. Individual
Vol. Ours
Vol. Intersection
Vol. Morv.
100
(0.1195, 0.1196)
(0.1165, 0.1166)
(0.1160, 0.1161)
(1.0, 1.0)
2
300
(0.02920, 0.02926)
(0.03071, 0.03078)
(0.02893, 0.02900)
(1.0, 1.0)
1000
(5.635e-3, 5.664e-3)
(6.475e-3, 6.507e-3)
(5.706c-3, 5.735e-3)
(1.0, 1.0)
100
(0.3190, 0.3192)
(0.1757, 0.1758)
(0.1582, 0.1584)
N/A
5²
300
(1.306e-3, 1.320e-3)
(3.672e-4, 3.748e-4)
(2.515e-4, 2.578e-4)
(1.0, 1.0)
1000
(1.990--8,, 1.024-07)
(2.422e-09, 7.225e-08)
(0.000, 3.689e-08)
(1.0, 1.0)
100
(0.9990, 0,9990)
(1.000, 1.000)
(0. (0.9995, 0.9995)
N/A
10a
300
(0.3534, 0.3536)
(0.1688, 0.1689)
(0.1306, 0.1307)
N/A
1000
(3.454e-8, 1.5763e-7)
(0.000, 3.688c-8)
(0.000, 3.688c-8)
(1.0, 1.0)
Table 2: 95% confidence intervals for the volumes of the confidence regions for RD()). We set KL = 0, = 0.05, Rs(Q) = (L/M, ..., 1/M) and use 10 Monte Carlo samples.
C
Proofs
C.1 Proof of Proposition
Write kl as
M
Σ 1
4
+
qj Pj
(13)
4
j=1
j=1
The result then follows by bounding the two by
M
M
1
dj
1-
Σ
In
)((golla)) - (1
In
M MB,
Σ
(1
In
(14)
40
1- 9z
1=1
j=1
and
M
M
M
Σ j=1
In
4i
Σ
4
In
9i
max
4
Σ
43
In
4i
<
B max
(15)
P5
Pj
2
Pj
2
1=1
Putting these together we obtain the bound on kl(gllp). The limit follows because each 93 + G3 as
B2 + 0.
C.2 Proof of Lemma 2
Let Ess (e eM). namely the set of M M-dimensional basis vectors. We will denote typical element of EM by r7 (m)) (M....., mm). For any (m)) (II..... Im) A straightforward
induction on m yields
Σ
II a; m7
=1
(16)
mpmme E
To see this, for m = we have E = ((e1) ),er,),... ..... (eM. }}, where we have been pedantic in using
1-tuples to maintain consistency with larger values of m. Thus, for any (11) = (æ1,) E A1, the left hand side of equation (16) can be written
E,
(xi); = 1.
j=1
18

---

Now suppose that equation (16) holds for any x(!)) E A M and let (m++1) = (#1..... Im+1)
A m+1 Then the left hand side of equation 16) can be written as
M
m++1
Σ
II
πI Y=1
(Im+1.e))
EE
i=1
n
j=1
M
Σ
II c; Th
Σ j=1
(am+1 Cÿ) =
m)
We now show that any ((() = elements of Ex in the following way
(#1......
Tm)
E A can be written as convex combination of the
(m)
Σ
πI
x 7h 1 (m))
(17)
We have already shown that the weights sum to one, and they are clearly elements of [0, 1], so the right hand side of equation [77p is indeed convex combination of the elements of Ex- We now show that equation [7) holds, again by induction.
For m = and any (1) = (I1,) AMr the right hand side of equation 17 can be written as
Σ (x1 e,) = (x1,) = z.
For the inductive hypothesis, suppose equation
I7 holds for some arbitrary m 2 1, and denote
elements of Em++1 by (m)) @ (e,) for some v (mn) E Ex and e EM, where @ denotes vector concatenation. Then for any (m=+1) x (m) (xm+1.) = tii...,,,m+t.
AM m++1 the right
hand side of equation (17) can be written
m++1
M
II
9h (m+1)
Σ
II a; m (0m+1 ( ① (ej.)
gmii
(m) Eug j=1
M
(Im+1 - ez)m (m)
I; 77:
7 (m) E Ey j=1
(Øm+1 :e))(eg))
mm M
J=l EE
1=1
m
Fmm+1
es)
Σ
II
x; . Mi
n (m)
M
Σ
II
amm+1 e,,(),,
pm
(m)
(Im+1.) (m+1)
where in the penultimate equality we have used the inductive hypothesis and (twice) the result of the previous induction.
We can now prove the statement of the Lemma. Applying Jensen's 's inequality to equation with the convex function f, we have that
f Im =
Σ
II Am
x m7
17 (m)
(m()) e E
Σ
(n)(m))
xp ni
(m() Em
1=1
19

---

Let f = E[X1] denote the mean of the i..d. random vectors X,. Then the above inequality implies
(I((X,,....
Xm)] S
Σ
II 1 ni / (n!m))
m
m)m) E Eyg
Σ
II P(X: = mi) =m)) f (m)m))
mm)) E
E X
C.3 Proof of Lemma
The proof of Lemma itself requires two technical helping lemmas which we now state and prove. Lemma 4, For any integers n 2 and 2 -1,
(n k)p/2 n
(' (1
x/002
1+1
dx.
Vk
00
V
Proof. The case of -1, namely
Σ
dx,
k(n k)
V /x(1 x)
has already been demonstrated in Maurer 2004 For p > -1, let
fx(2) = (1 2/p/2
V
We will show that each f-()) is monotonically decreasing on (0, 1). Indeed,
df (अ)
x) (px + 1 x)
< (1 x//
2/33/2 0,
dx
2/3/2
where for the inequalities we have used the fact that p 11 and x E (0, 1). We therefore that
k)p/2
nl/2
3p/2
n
V
k=1
vT
1
(1
1/12
n
k
n
Sn
fa(x)dr
n t4a
fa(rddr
p+1 < n fp(a)da.
Intuitively, the proof of the above lemma works by bounding the integral below by a Riemann sum. In the following lemma we actually calculate this integral, yielding a more explicit bound on the sum in Lemma 4 We found it is easier to calculate a slightly more general integral, where the in the limit and the integrand is replaced by positive constant a.
20

---

Lemma 5. For any real number a >> 0 and integgr n 2 -1
(a
12/2
[( [+
V
dr VT
2 T[
a
n+1
Proof. Define
[a) / (a x2)n/2 dr
T(
and
fa(a)
VT
T(
2+3
We proceed by induction, increasing n by 2 each time. This means we need two base cases. First, for 1, we have
L1(a)= 1/ Vi(a - x)) dr aaresn
1 f-1(a),
V a
since l'()) = VT and [(1) = 1. Second, for n
lo(a) / 1 de [2V=] 2 = Sola),
since r(2) = v 2
Now, by the Leibniz integral rule, we have
da (n+2(a)
ai
d
/-"
0 (a x)
dx
n
(a - r)
dr
12 + 2
1, (a).
da
V
2
Vx
2
Thus
n +
1 (t)dt + +n((0)
n n / (t)ddt,
ln+((a)
since (0) = 0.
Now, for the inductive step, suppose In(a) fn(a) for some 2 -1. Then, using the previous calculation, we have
S
fn(t)dt
n 2
T( [++2
dt
n+2
n+2
2
n+3
n+3
2
n+2
+
+
[2+2)+2
2
(n
r
[n+2)+3
fn+2(a).
This completes the proof.
We are now ready to prove Lemma 3 which, for ease of reference, we restate here. For integers M > 1 and m 2 M,
24 2 2
Σ kES>0
11
Vk
T
21

---

Proof. (of Lemma 3) We proceed by induction on M. For M = 1, the set Sm.M contains a single element, namely the mee-dimeniioal vector (k1.) (m,). ). In this case, the left hand side is 1/ym while the right hand side is / (1) = 1//mm since ((1/2) vτ.
Now, the inductive hypothesis, assume the inequality of Lemma holds for some fixed M 2 and all m 2 M. Then for all m 2 M + 1, we have
M
Σ
1
1
E
1
M+1 5===
RES M411
WES by M
j==1 V
K2
1
π 2 (m-
ki)
(by the inductive hypothesis)
I
I
M
2
M
(m - k1) M--
Vhi
m
k1)
2
(enlarging the sum domain)
v /k
#
M-2
x))
m
dx
(by Lemma
π 4
M-1
T(
(by Lemma
M
M+1 2
M+1
2
as required.
C.4 Proof of Proposition] 1
Proof. The case where 9j = 1 or pj = 1 can be dealt with trivially by splitting into the three following subcases
4j = Pj =1 = kl(ai = kI(allp) = 0
9j L,P3 #1 kllgs (lpp)) kl(gllp) = =-logp,
9j + 1,2
((ggsllp)) kl(glpp) = Co.
For qj A and pj # define the distributions q E AM by Tj- = ". 0 and
9i 1 qj
P1 pi
and
Pj
for j.. Then
Σ q. log
41
Σ (1
95)q log
(1 - q;}q;
Pi
(1 P. P
1
ifj
1 - qj
(1 93)
q
log
+ q. log
pi
1 Pj
it
1 Lj
(1 oj kl( + (1 43) log
1 Pj
1- 0j
2 (1 9j) log
1 1-p5 P.
22

---

The final inequality holds since kl(ğl) p) 2 0. Further, note that we have equality if and only if q = P. which, by their definitions, translates to
Pj qj qi Ps
for all i # If we now add qj log ps
to both sides, we obtain
kl(glpp) 2 (1 - qj) log
1 - Oj
+ qs log t kl(gz)lp)).
1 Pj
Pj
with the same condition for equality.
The following proposition makes more precise the argument found at the beginning of Section for how Proposition [ can be used derive the tightest possible lower and upper bounds on each (Q).
Proposition 5. Suppose that q.p E aM are such that kl(gllp) S B, where q is known and is unknown. Then, in the absence of any further information, the tightest bound that can be obtained on each Pj is
Pj S (1; B).
Proof. Suppose Pj (n, B). Then, by definition of kl_ we have that kl(g)llp;) B. By Proposition D this would then imply kl(q pp) > B, contradicting our assumption. Therefore Pj S (g,, B). Now, with the information we have, we cannot rule out that
Pj
P:
qj
for all + j and thus, by Proposition that ((gl)lp)) = (l(g)))) Further, we cannot rule out that
kl(g)))) = B. Thus, is possible that kl( (lp,) = B, in which case Pj = -kI , B). We therefore
see that kl (q,, B) is the tightest possible upper bound on py. for each j E [M].
C.5 Proof of Theorem
Before proving the proposition, we first argue that klp (ulc) given by Definition is well-defined. First, note that Au == (u Aas kl(u/| I c} is compact (boundedness clear and it is closed because it is the preimage of the closed set (0, c] under the continuous map t - ())] and so the continuous function fe achieves its supremum on Au. Further, note that A, is a convex subset of Aas (because the map - kl(ul||>) is convex) and fe is linear, so the supremum of fe over A, is achieved and is located on the boundary of Au This means we can replace the inequality constraint kl(ullv) S in Definition with the equality constraint kl(u[[v) a strictly convex subset of La (because the map v + kl(u]lo) is then strictly convex) and so the supremum of fe occurs at unique point on the boundary of Ag. In other words, if A AM then kl," (u/ (c) is defined uniquely.
c. Finally, if A then A.
We now prove Theorem 2 While our proof technique is somewhat analogous to the technique used in Clerico al. 2022 to obtain derivatives of the one-dimensional kl-inverse, our theorem directly yields derivatives on the total risk by (implicitly) employing the envelope theorem (see for example
Takayama and Akira 1985).
We first derive the expression given for o² vūū (ulc) given line ( of the theorem using the method of Lagrange multipliers. Since we are working on the simplex, we make things easier for ourselves by first making the substitution t, = In by make the ey > 0 constraints unnecessary. The method of Lagrange multipliers yields both the maximum and the minimum (recall that (u)e) is defined as the location of a maximum) for the two values of the Lagrange multiplier μ.. We show that exactly one of these values lies in the interval one corresponds to the maximum. This shows that the value μ Theorem yields v" (ū) kl," (u)c). Finally, we derive the partial derivatives of kl, (ulcc with respect the ü, to obtain the second part of the theorem, namely line (6) by employing the envelope theorem.
Proof Outline:
(-c0, max, (2) and that this 2 instructs us to find indeed
23

---

Proof. (of Theorem 2) We start by deriving the implicit expression for v" = kig (ulc) given in the proposition by solving transformed version of the optimisation problem given by Definition Dusing the method of Lagrange multipliers. We obtain two solutions to the Lagrangian equations, which must correspond kl(u](p) I c} because, as argued in the main text (see the discussion after Definition I Au is compact and so the linear total risk fe(v) attains its maximum and minimum on Au.
the maximum and minimum total risk over the set A, == {o E AM
[1p'(ulc) we know that kl(v" (ū) /u) < Since, by assumption, Wj > 0 for all J. we see that v" (ū)j > O for all j. otherwise we would have kl(v" (ū)llu) = xx,
By definition of o" (ū)
contradiction. Thus (") E M
>0 and we are permitted to instead optimise over the unbounded
variable t E RRM, where lj := Vn With this transformation, the constraint v E A can be
replaced simply by Σ, e = 1 and the optimisation problem becomes
M
Maximise: F(t) := Σ lee
j=1
Subject to: g c. kl(ullee) - 0,
h(t)
e O,
where e¹ E RM is defined by (e"); == e/, Note that F(t) = Se(e"). Following the terminology of mathematical economics, call the i, the optimisation variables, and the ūj (namely the ny and c) the choice variables. The vector l considered fixed-we neither want to optimise over nor differentiate with respect it-hhhch is why we occasionally suppress it from the notation henceforth.
For each ú. let vū) and t (ū) be the solutions to the original and transformed optimisation problems respectively. Since the map v = e" is one-to-one, it is clear that since v' (ū) exists uniquely, so does t* (ū), and that they are related by v" (ū) = e We therefore have the identity fe(v" (ū)) = (ū)).
Recalling that fī(ū)= = fe((" (ū)), see that
Valī(ū) (i)(
(18)
the derivatives of Se(kl, (ulc)) with respect to and are given by V V.,((t(()),
Using the method of Lagrange multipliers, there exist real numbers X (m) and n 1² ( such that (t", X², v²) is a stationary point (with respect to t, X and p) of the Lagrangian function
A(t,A,
F(t) Ag(t; i) + wh(t).
Let Fe(-) and he(-) denote the gradient vectors of F and h respectively, and let ( û) and gu(t; denote the gradient vectors of with respect to t only and ú only, respectively. Simple calculation yields
0g (t: ū),
0g
Gt (t: =
(t; úi) = - and
0ti
Ut
Iu (t: ū) =
0g
(t: i),....
0g
(t:1)) = -1- f1 + log u1,.... t. + log Was, -1).
Oūg
0us+1
(19)
Then, taking the partial derivatives of L with respect to A, i and the ty, have that (t, A, u))
(t* (ū), (u)), (ū)) solves the simultaneous equations
(t) + >te(t; u) + uhe (t) = 0,
(20)
g û) 0, and
h(t)) = 0,
where the last two equations recover the constraints. Substituting the gradients Ft, and he, the first equation reduces to
L e Au + uu t 0,
24

---

which implies that for all j E [M]
Auj u
e
(21)
Substituting this into the constraints = h = 0 yields the following simultaneous equations in À and
f
M Σ j=1
c ==(lll))e = Σ
U
log
Uj e
1 lj U
log
and
> j=1
Uj + Ej
1.
x
5ml
Substituting the second into the first and rearranging the second, this is equivalent to solving
M
Σ ug log
(x+
Σ k=1
uc
and x
Σ uj
(22)
Ex
Ej
has already been established in the discussion after Definition I that fe(v) attains its maximum on the set An := { E A =k((ul/v) S c). Therefore Ftt) also attains its maximum on R and one the solutions to these simultaneous equations corresponds to this maximum. We first show that there is single solution to the first equation in the set (-o0, maxy fy), referred to as j (ū) in the proposition. Second, we show that any other solution corresponds to a smaller total risk, so that μ² (ū) corresponds the maximum total risk and yields (ti) = kt (ulcc when μ (ū) and the associated X (i)) are substituted into Equation 21
For the first step, note that since the e are probabilities, Ej > for all j (in the case that À > O), or fz + Ej < 0 for all j (in the case that X < 0). Thus any solutions y to the first equation must be in (-o0, - max, Eg) or f-miny Ez. Dc). If (-o0,- max, Eÿ) then the first equation can be written as Φe(μ), with de as defined in the statement of the proposition. We now show that Φe is strictly increasing in μ. and that Φe(p) - 0 as + -o and (H) + oo as + max, Lj. so that δe(μ) does indeed have single solution the set (-o0, max, 22). Straightforward differentiation and algebra shows that
see from Equation 21 that either
M Σ
M
de(m)
Uj
uk
(m+
Σ
Wh (1 + lx
(n
Σ
M
uk 1ot
1 +
Ess
==1
k=
E/ M
M
uy
ptte
===1 (m+te)²
E
uk ptfe
Jensen's 's inequality demonstrates that the numerator strictly negative, where strictness is due to the assumption that the l, are not all equal. Further, since the denominator is strictly negative (since we are dealing with the case where μ (-o0, - max, &,) f,)), we see that Φe is strictly increasing for Js (-o0, max, (,) Turning to the limits, we first show that Φe(μ)) - ao as J - max, by-
We now determine the left hand limit. Define J = {j E [M] Eg = max, lx ). noting that this is strict subset of [M] since by assumption the E, are not all equal. We then have that for
'Incidentally, this argument also shows that there is at most one solution to the first equation in 22 in the range (- min, E, oo). There indeed exists unique solution, which corresponds to the minimum total risk, but we do not prove this.
25

---

E ( (-00, max, Eÿ)
M
)
M
(delm)=
Σ
Uj
II ( (x -(++ (x)) (w++)))
F + Es)
1=1
Σ
U
E Uj
II KEJ
(1- (u+++))) 22
II kgJ
(- (a + [w
jEJ 11 + li
PEa 1 + lij
Uj JEJ p M e
II (1- (p 6x)) uk
II (- (a + Ex:1)
KEJ
k'qJ
Ejer us) (Ilwegs (- (1 + (x) "x
(++ maxy (z))
-
The first term in the numerator is positive constant, independent of μ. The second term in the numerator tends to a finite positive limit as μ 1 - max, E,. Since [M]] \ J is non-empty, the power in the denominator is positive and the term in the outer brackets is positive and tends to zero as f max, lj. Thus ed)(4) + 0 as μ 1 max; fj and, by the continuity of the logarithm, the (1) as μ t max; Ej.
We now determine limp--oo (e(U)) by sandwiching x(μ) between two functions that both tend to zero as μ + -c. First, since lj for all j. for μ E (-00,- max, Eÿ) we have
M
M
M
log
Uj
2 log
Uj
- -loog(-1) = Σ
u log( -1),
lj
1=1
j=1
j=1
and
M
M
M
Pj 1
<e(u)) 2-
Uj log( - 11) +
Ug log (-(x+
Σ j=1
Uj log
1
+0
as
1 -x.
1=1
Similarly,
M
M
Σ Ug log ( - (u + [-)g -
új log( -p) = log(-14))
5=1
j=l
and so
M
M
δe(m)= S log
# j=1
Uj
= log
Σ
U
+ 0
as 1 + -00
+
E
j=1
This completes the first step, namely showing that there does indeed exist a unique solution je (ū) in the set (-é1, oc) to the first equation in line (22).
We now turn to the second step, namely showing that this solution corresponds to the maximum total risk. Given a value of the Lagrange multiplier μu, substitution into Equation 21 gives
(4)
ntt
Σ k m1 p+t
and therefore total risk
M nyly
D ptty
R(u)
Ek=1 p4tt
us.
To prove that the solution 1²" (ū) E (-o0,- max, (G) is the solution to the first equation in line 22
that maximises R, it suffices to show that R(n) + Σ Uzly as |n| -> oo and R'(H)) 2 for all
c E (-oo, - max, (G) U (- ming Cy, 00), so that
inf
R(p) >
sup
R(p).
=E(-oc,- max, 42 ME( - ming E0)
26

---

This suffices as we have already proved that μ² (ū) is the only solution in (-00; max, {ÿ) to the
first equation in line (22). and that no solutions exists in the set |- max, lz. - miny Ey].
The limit can be easily evaluated by first rewriting R(μ)) and then taking the limit as |p| + oc as follows
Σ
n j=l
M
R(O)
Σ Ugty
Ws
-= Uk
To show that (p)) 2 0, let (() denote the j smallest component of & (breaking ties arbitrarily),
so that {1)) S S (ary, and use the quotient rule to that
us p ptle
)
EE (
j=1
M a,ey mtbs
Ek=1 (p+t))))
(1()) 20
2 20
Up Eper
wutte) )
M
M
upukly
1
1 - m
1
( bu + (x)
11 Ek
ujlll()
1
+ ( + ((x))
((x)
a xt
j.kEIM kCJ
1 (p+ (G)) ((x
Σ M
2 0,
1 u
where in the final line we have dropped the summands where k: = j since they equal zero as the terms in the bracket cancel. This final inequality holds since the first sum can be bounded below by the negative of the second sum as follows
(a + M6)) (ut liss u u utel =t(n))
ujuxl()
Σ A.EE(M) bCj
ujunl(s)
Σ
(since (p)) S Euy for h: < j)
re EG) (n + (G)) N1t ((K)
J.EE[M kej
(1t)) (n (u+ +os) l(t) (u+ ls) 1 los) J.MEM k>j
Σ
uxu(l()
1 )
(swapping dummy variables j. k).
We now turn to finding the partial derivatives of F(tt (ū)) with respect the ūj which in turn will allow us to find the partial derivatives of (l]c) Let Va denote the gradient operator with respect to ú. Then the quantity we are after is V [t (ū) E IR M+1, the j'th component of which is
M+1 OF
0t (ū) = Fe (ū)) Dū,
Øt
(VaF(t = Σ
(t' (ū)
(ū) E R.
aty
0ū,
km
Thus the full gradient vector is
F(t(t(()) at
(23)
where Vat"(ū) is the M x (M + 1) matrix given by
at
(vat(a)),
(i)
Dūj
Finding an expression for this matrix is difficult. Fortunately we can avoid needing to by using a trick from mathematical economics referred to as the envelope theorem, now show.
27

---

First, note that since, for all ét the constraints g = h = 0 are satisfied by t"(2), we have the identities
g(t (u), ú) = 0 and h(tt (ū)) = O.
Differentiating these identities with respect to ūj then yields (e (u). u) As before, write these M pairs of equations as the following pair of matrix equations
0t (u) + gú, (ū), úi) and he(t" (ū))
Ot dū,
④
0ūg
9r (t" (ū), V) + gu (t" (ū), ū) = 0 and (e(("(ū)) (t) (ū) = 0.
Multiplying these identities by X (u) and μ² (ū) respectively, and combining with equation (3 yields
vaF(t(ū)) (a)
w) (i)) (at
+ (t (" ( u)
where the final equality comes from noting that the terms the large bracket vanish due to equation (20). Recalling the expression for (t; ú)) given by Equation 19 and that v" (ū) exp(t" (ū)) we obtain
(ZF(t(z) = (ū) tt((i) + log U1
(ū) + log uM. -1)
U1
UM
(ū)
1 + log
1 + log
2* vr(ū)
2" (r)) M
Finally, recalling Equivalence
18
namely V (u) = V. (t=((t())) we see that the above as; (ü) stated in the proposition, thus completing the de
expression gives the derivatives proof.
37. (ū) and
duj
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our Theorem is PAC-Bayes bound the form we claim to prove in the
abstract. Further, Proposition 2 recipe for the differentiable training objective claim to derive in the abstract.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss these in Section
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
The proof of our main result Theorem I iss found in Section 5 Proposition is
proved in Appendix C.4 Our second main result, Theorem 2 proved Appendix
C.5
Proposition is proved directly after its statement. Proposition 3 is proved Appendix
Proposition 4 is proved in Section 5 Lemmal I doees not require proof it is the classic change measure inequality (Csiszár) 1975 Donsker and Varadhan 1975). Lemma 22 is proved in Appendix C.2 statement.
Finally, Corollar and Lemma proved directly after their
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Appendix A devoted to a detailed explanation of how to implement our training regime, and Appendix B gives the details of the specific experiments we run.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: URL is provided.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: This is outlined Appendix B
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
The paper concerns bounds, meaning the results themselves are confidence regions.
Justification:
29

---

8. Experiments Compute Resourees
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [No]
Justification:
The compute resources required stated as they negligible.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https//ss//aaappp...pppooooaaaaa
Answer: [Yes]
Justification: There are no data-related concerns or societal impact concerns.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The introduction describes a class of concrete real-world problems for which method may have positive impact.
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper uses only the MNIST dataset.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: None required.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: None required.
30


Reviews:
[{"review_id": "S0U03Z3phQ", "reviewer": "Reviewer_R3U1", "summary": "In the standard statistical learning theory control of generalization\nerror typically means studying deviations of the empirical risk from\nthe risk (for instance, with high probability over the sample).  In\nthe language of statistics such control doesn't make a difference\nbetween type I & II errors.  This paper goes beyond as it looks at a\nmulti-objective risk, i.e. 'deviation' of the vector or M empirical\nrisks from the corresponding risks.  In the context of the paper, the\nvector of empirical risks lives on a probability simples and the paper\nshows how to control a KL divergence between such a vector and a risk\nprobability vector.  Then, the paper goes on and studies a PAC-Bayes\nformulation of this problem (Theorem 1).  In section 4 the paper\nproposes how to construct a differentiable objective for this problem.", "questions": "Not a question really, but I'd be interested to hear authors' thoughts\non the weakness against a union bound.  E.g. how would one approach\nthis comparison problem / experiment design.", "limitations": "Seems to be adequate.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is an important problem, especially in the context of\nmultiobjective errors which are commonplace in practice.  To some\nextent these results also extend results of Maurer (2004) (PAC-Bayes\nbounds on little-kl) to simpleces (while original results were shown\nfor Bernoulli case).", "weaknesses": "The price for having such a multiobjective setting is M log(M),\nwhereas the standard union bound would lead to a log(M) cost --- note\nthat there is a (significant) gap.  However, it should be noted that\nthis would give a bound on a different objective (not kl() between\npoints on the simplex).  I think that the paper should argue why such\nkl() is interesting or at least design analytical instances and/or\nsome experiments which would demonstrate that there exist instances\nwhere kl() leads to a better/tigther results (perhaps a performance on\na downstream task?).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and for taking the time to give constructive feedback on our work! We are especially grateful for your insight that it is difficult to compare our bound against the standard union bound since we have bounded a different quantity - the vector rather than scalar kl. The reason we did not initially make a comparison was because it seemed to us that the standard union bound was not suitable for our use-case; we are considering a situation such as outlined in paragraph 3 of the introduction, where one cannot anticipate the future costs of certain error types, such as the type I & type II errors you mention. In such a case, a union bound would simultaneously bound the type I & II errors individually, whereas our bound simultaneously bounds *every linear combination* of these two errors. This gives greater assurance when the costs of different error types may change (for example with better medical knowledge), and may be especially useful when there are more than two ways of mis-classifying data.\n\nYour and the other reviewers' insightful comments however, have helped elucidate the fact that a union bound applying to each error probability individually can indeed be used to bound linear combinations of errors, and thereby also constrains the entire vector of error probabilities. For this reason both our bound and a union bound form confidence regions around the empirical risk vector $\\mathbf{R}_S(Q)$, and these regions can be compared. One way to do this is to compare their volume, where a smaller volume indicates greater control over the true risk vector $\\mathbf{R}_D(Q)$.\n\nAs a quick experiment, we take the number of error types to be $M = 25$ (corresponding to one error type for each entry of a $5 \\times 5$ confusion matrix), $\\delta = 0.05$, and suppose that the empirical risk vector is $\\mathbf{R}_S(Q) = (1/25, \\dots, 1/25) \\in \\mathbb{R}^{25}$ and $KL(Q|P) = 0$. We then sample $10^8$ points $\\mathbf{p}$ uniformly from the simplex. By counting what proportion of the sampled $\\mathbf{p}$ could be values of $\\mathbf{R}_D(Q)$ compatible with the union bound and our bound respectively, we obtain the following estimates (with 95% confidence intervals) for the volumes of the two confidence regions (normalised by the volume of the simplex):\n\n| $M$   | $m$  | Vol. Union CR                      | Vol. Our CR                        |\n|-------|------|--------------------------------|----------------------------------|\n|       | 100  | 0.3191 (0.3190, 0.3192)            | **0.1758** (0.1757, 0.1758)               |\n| $5^2$ | 300  | 1.313e-3 (1.306e-3, 1.320e-3)        | **3.710e-4** (3.672e-4, 3.748e-4)           |\n|       | 1000 | 5.665e-8 (1.090e-8, 1.024e-7)          | **3.7336e-8** (2.422e-9, 7.225e-8)           |\n\nOne can see that our confidence region has a smaller volume in all three cases tested (although in the third case the confidence intervals overlap). We can therefore see that **the cost to the bound of Mlog(M), rather than log(M) for the union bound, can indeed be outweighed by the fact that we are bounding a different quantity.** We thus outperform the union bound method.\n\nThank you again for taking the time to carefully review our work, and giving us feedback we believe has enabled us to strengthen the presentation of our result!\n\nWe hope that our demonstration that our bound on the kl() can lead to tighter bounds than the union bound approach convinces you of the utility of our result, and that if so you will kindly consider raising your score.", "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": "", "extra_scores": {}}, {"review_id": "z7pe37LC5a", "reviewer": "Reviewer_cfTA", "summary": "This paper introduces a novel PAC-Bayes bounds that extend classical kl-based bounds to vector-valued losses that can control several error-types simultaneously. The bound is converted into a differentiable minimization objective and details for the practical implementation of the bound are provided in the Appendix.", "questions": "See weaknesses.", "limitations": "The limitations are properly discussed in Section 6.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1- The paper is clearly written and theoretically solid.\n\n2- The contributions have a potential impact in scenarios where simultaneous control over multiple error types is needed.", "weaknesses": "1- The proof techniques and the main contribution (Proposition 4) are straightforward extensions of scalar kl-bounds to the multidimensional case. I fear this contribution alone might not be significant enough.\n\n2- The experiment in Section 7 is too simple, further empirical evaluation of the bounds (e.g. simultaneous minimization of Type I and Type II errors in more realistic scenarios) would be very beneficial for the impact of the paper.\n\n3- Wu, Y. S., & Seldin, Y. (2022). Split-kl and PAC-Bayes-split-kl inequalities for ternary random variables. Advances in Neural Information Processing Systems, 35, 11369-11381. is significant related work not discussed in the paper.\n\n\nIn general, I don't think this is a bad paper, but the theoretical contributions are not very original and I feel that the paper needs more experimental backup to be a well-rounded contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you kindly for taking the time to carefully review our paper. Thank you especially for pointing out the unfortunate omission of Wu, Y. S., & Seldin, Y. (2022) from our related work section! The paper is indeed very related and we have now incorporated a discussion of it into our paper.\n\nAs for the main contributions of our paper, we emphasise that these are **Theorems 1 and 2**, not Proposition 4. We hope that you take this into consideration with your final score as we feel that Proposition 4 represents a small portion (20%?) of our theoretical contribution. Indeed, as you point out, the proof technique for Proposition 4 is similar to existing results and comes to one page, whereas the techniques required for Theorems 1 and 2 are extensive, novel, and require an additional 12 pages of proof, mostly found in the appendices.\n\nThe meat of our paper is:\n  - **Theorem 1** This specialises Proposition 4 to the $d(\\cdot, \\cdot) = kl(\\cdot∥\\cdot)$ case and then slightly loosens it to a tractable form so that it can be easily evaluated. The proof is in two parts:\n    - Proving Corollary 1 (lines 286 - 299) by specialising Proposition 4 to the $d(\\cdot, \\cdot) = kl(\\cdot∥\\cdot)$ and applying some combinatoric arguments;\n    - Proving Theorem 1 (lines 304 - 316) by loosening the bound to a tractable form. Because we want to keep the bound as tight as possible, we expend some effort in loosening it as little as possible. For this require the technical Lemma 3, which itself requires two helping Lemmas found in Appendix 8.3. These three Lemmas require a further two pages to prove. We split this up into chunks for readability, but appreciate that this might obfuscate what the main contributions are. Hopefully this clears it up with respect to Theorem.\n  - **Theorem 2** This constructs a differentiable training objective from the bound given in Theorem 1. Its proof requires five pages and is found in Appendix 8.5 that does not follow the lines of any existing proof we are aware of.\nWe hope you can agree that altogether this represents a non-trivial contribution!\n\nThank you for highlighting, as we should have realised, that the binarised MNIST dataset we used is not particularly realistic to our stated use-case. On your advice, we conducted an experiment using the HAM10000 dataset, a dataset of images of cancerous and non-cancerous skin marks. We obtain an empirical risk vector $\\mathbf{R}_S(Q) = (0.7718, 0.0548, 0.1735)$ for error types $E_0 = $ correct, $E_1 = $ false negative, and $E_2 = $ false positive, by employing our Theorem 2 to do simultaneous minimisation of the Type I and Type II errors with a loss vector $\\ell = (0, 1, 2)$, weighting Type II errors as twice as bad as Type I errors (more time would allow professional estimates of the loss vector to be obtained). We will be able to write up the experiment in full in the camera-ready version if accepted, but the results are positive; a Monte Carlo estimate shows that the resulting Confidence Region for $\\mathbf{R}_D(Q)$ takes up only $3\\%$ of the simplex, which compares favourably to the Confidence Region formed by taking a union bound. Here is a table of results, showing the volume of the confidence regions normalised by the volume of the simplex (in brackets are the confidence intervals from the MC estimates):\n\n| $M$   | $m$  | Vol. Union CR                      | Vol. Our CR                        |\n|-------|------|--------------------------------|----------------------------------|\n|  3     | 500  | 0.03067 (0.03056, 0.03077)            | **0.02985** (0.02975, 0.02996)|\n\nDo please let us know whether you find the new setting of the HAM10000 dataset to be more realistic, and any further details you would like to know!\n\nThank you again for investing the time to review our paper and provide very helpful feedback which we believe has improved the presentation of the paper and the convincingness of our results.", "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": "", "extra_scores": {}}, {"review_id": "ubHjQUiuqQ", "reviewer": "Reviewer_4oQc", "summary": "The notion of a set of \"error-types\", introduced by this work, is a user-defined partition of the product space of predictions and responses, generalizing well-known summaries of the erring behavior of predictors. This work presents a PAC-Bayes bound on the divergence between and empirical and true distributions over a set of \"error types\" for a choice of posterior prediction scheme. The phrasing of the bound in terms of KL divergence naturally generates bounds on arbitrary linear combinations of the true error type probabilities, which hold simultaneously. The authors present a training objective founded on the minimization of the worst-case value of a pre-defined weighting of error types consistent with the empirical error-type profile of a given choice of posterior over predictors.", "questions": "Is there a quick example of to control a single linear combination of confusion matrix probabilities using a previous bound? \nIn line 331, what is an \"empirically tighter\" bound?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper strikes a good balance between practicality and theory. The problem setting is well-motivated, and the generalization of the confusion matrix through error types allows for the use of the bounds in a variety of non-standard settings. The PAC-Bayes bound is novel.  While PAC-Bayes has been previously used to control the spectral norm between between empirical and true confusion matrices, the bounding distributions over error types in terms of KL divergence straightforwardly generates bounds on the expected cost (over the true distribution over error types) which hold simultaneously, something of notable practical use. The paper is generally well-written.", "weaknesses": "One of the main strengths of this work the simultaneous control of arbitrary linear combinations of the error type probabilities. However, the ability of the previous literature to generate some semblance of these guarantees is not particularly well-exposited. Having not previously read any of this line of work, I think an explicit example of how one can construct a bound on a single linear combination might do the paper some good (and might motivate this work past the simultaneous control of all linear combinations, given that the task seems somewhat tricky given a spectral norm bound).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind review, especially for noting that our approach is much more flexible than that of Morvant et al. (2012), as one is not limited to the confusion matrix and can instead consider arbitrary user-specified error types.\n\nAs for your question on previous results, we have now run an experiment to compare our bound to that of Morvant et al. (2012). Since their result considers the full confusion matrix, a fair comparison requires requires choosing $M = L^2$ error types, where $L$ is the number of labels. To compare, we estimated the volume of our confidence region, which is a kl-ball, against the volume of Morvant's confidence region, which is a spectral-norm-ball. Our Monte Carlo estimates show that Morvant's result is either not applicable or their confidence region is much larger than ours and essentially takes up the entire simplex, hence the volume estimate of 1.000 in the below table. The reason their bound is sometimes inapplicable is because it requires every class to contain at least $8L$ instances (in the $L=5, M=25, m=100$ case this would require each class to contain at least $5 \\times 8 = 40$ instances which is impossible with $m=100$ samples). Here the table of the results:\n\n| $M$   | $m$  | Vol. Morvant CR                 | Vol. Our CR                        |\n|-------|------|--------------------------------|----------------------------------|\n|       | 100  | NA ($m$ too small)            | **0.1758** (0.1757, 0.1758)               |\n| $5^2$ | 300  | 1.00  (1.000, 1.000)        | **3.710e-4** (3.672e-4, 3.748e-4)           |\n|       | 1000 | 1.00 (1.000, 1.000)          | **3.7336e-8** (2.422e-9, 7.225e-8)           |\n\nThis comparison of the volumes of our confidence region and Morvant's clearly shows that bounds on *linear combinations* of error probabilities derived from our bound will be much tighter that Morvant's, which will be almost as large as they theoretically can be and therefore provide no utility. We were surprised to see that Morvant's highly interesting theoretical bound unfortunately performs so poorly empirically. It is certainly a comparison we will add to the final paper if it is accepted, and we thank you for the very excellent advice which we believe improves the exposition of our result.\n\nOn your advice, we are in the process of adding an explicit example of how to calculate a bound on a linear combination using our Theorem 2 and using Morvant's bound. We agree with your observation that this would clarify the import of our quite technical theorem.\n\nOnce again we kindly thank you for taking the time to carefully read our paper and give highly constructive and helpful feedback! We believe this has improved the exposition of our paper and helped elucidate our contributions.", "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": "", "extra_scores": {}}, {"review_id": "OSMXab0a0f", "reviewer": "Reviewer_fvxp", "summary": "The authors suggest an approach for controlling errors of various types (simultaneously) within a PAC-Bayes framework. They derive a high probability bound on the KL divergence between the empirical and distribution risk vectors. This generalizes earlier work in the binary case by Maurer, 2004 and Begin et al 2016. The authors propose a method for using this bound as a (differentiable) training objective via considering a linear combination of the elements of the risk vector and inverting the resulting binary KL divergence.", "questions": "- Is it really not possible to upper bound arbitrary linear combinations of different types of risk with a union bound? I would think that bounding finitely many would place linear constraints on other linear combinations, allowing at least some bounds to be derived. It isn’t immediately obvious to me how sharp the resulting bounds would be, or if indeed this approach leads to non-vacuous bounds, but I’d appreciate the authors commenting on this and adding some discussion on the topic if the answer to my question is that it is possible. \n- How would $\\ell$ be chosen in practice when defining the objective function? It seems the whole purpose of the framework is to provide useful bounds simultaneously for many types of predictive errors. But it also seems the choice of $\\ell$ will have a large impact on how well a method trained with proposed approach will perform on tasks that weight certain types of errors heavily.", "limitations": "- The authors acknowledge limited experiments as a limitation of the current work. I agree that this is a limitation. In particular, I wonder whether similar results can be obtained using held-out data, and whether or not the bounds derived this way are competitive with this approach. In the one experiment provided, half of MNIST was used to define the prior, while have was used for optimization of the bound. It seems possible that a similar breakdown of data between a training and validation set (trying directly via cross-entropy loss) might lead to similar model performance and tighter bounds on the risk (as in the cases considered in Foong et al). It isn’t immediately obvious whether it is easy to directly invert the multinomial CDF to derive tight bounds on various datasets as in the binary case using holdout data. But I’m curious to hear the authors’ thoughts on this approach.\n- The authors point out that the bound is limited to discrete cases. This seems reasonable, and there are many discrete problems where the bound might be useful. I think finding a concrete problem (dataset, with a plausible decision depending on balancing error types) where this bound might be useful would be more convincing to address this limitation than extending the work to continuous problems.\n\nMinor points: \n\n- Line 147: $S_{m,n}^{>0}$ isn’t the interior of $S_{m,n}$ in a topological sense, assuming $S_{m,n}$ is considered with the discrete topology, which seems the natural choice. Otherwise, I don’t know what is meant by interior.\n- Line 198: \"Different different\"", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The main result seems to be a creative and potentially useful extension of the PAC-Bayesian framework.\n- Results are generally introduced with some explanation, and given more context after the result, which improves readability.", "weaknesses": "- The framework considered would be better motivated by providing a specific example (ideally with an experiment) indicating the usefulness of the method (and illustrating why existing approaches with a union bound are insufficient).\n- The authors included the NeurIPS checklist from last year (and not from this year). \n- The proof of theorem 2 is very long and either an outline/proof sketch should be provided at the beginning, or the proof should be broken into lemmas/propositions to improve readability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your thorough review and many insightful comments! We are especially glad you find our results creative and the paper well-written.\n\nYou mention the paper would be better motivated by an explicit example showing the utility of our method above existing ones. We did not initially believe a comparison to existing methods could be made, since\n- existing methods bound simply the error rate (lumping all errors together), or (via a union bound), bound each error probability, whereas;\n- our method bounds the whole distribution of errors, allowing us to derive bounds on every linear combination of the error probabilities.\n\nHowever, your (and the other reviewers') insightful comments have clarified that with bounds on the individual error probabilities one can in fact derive bounds on linear combinations of them. Thank you for this astute observation, which enables direct comparison of our result to existing ones! Thus we conducted two quick experiments to demonstrate the utility of our method above existing results.\n\nFirst, as a quick illustration that our method can beat a union bound, we construct a synthetic example. We take the number of error types to be $M = 25$ (corresponding to one error type for each entry of a $5 \\times 5$ confusion matrix), $\\delta = 0.05$, and suppose that the empirical risk vector is $\\mathbf{R}_S(Q) = (1/25, \\dots, 1/25) \\in \\mathbb{R}^{25}$ and $KL(Q|P) = 0$. We then sample $10^8$ points $\\mathbf{p}$ uniformly from the simplex. By counting what proportion of the sampled $\\mathbf{p}$ could be values of $\\mathbf{R}_D(Q)$ compatible with the union bound and our bound respectively, we obtain the following estimates (with 95% confidence intervals) for the volumes of the two confidence regions:\n\n| $M$   | $m$  | Vol. Union CR                      | Vol. Our CR                        |\n|-------|------|--------------------------------|----------------------------------|\n|       | 100  | 0.3191 (0.3190, 0.3192)            | **0.1758** (0.1757, 0.1758)               |\n| $5^2$ | 300  | 1.313e-3 (1.306e-3, 1.320e-3)        | **3.710e-4** (3.672e-4, 3.748e-4)           |\n|       | 1000 | 5.665e-8 (1.090e-8, 1.024e-7)          | **3.7336e-8** (2.422e-9, 7.225e-8)           |\n\nOne can see that our confidence region has a smaller volume in all three cases tested (although in the third case the confidence intervals overlap).\n\nSecond, we conducted a more realistic experiment using the HAM10000 dataset, a dataset of images of cancerous and non-cancerous skin marks. We obtain an empirical risk vector $\\mathbf{R}_S(Q) = (0.7718, 0.0548, 0.1735)$ for error types $E_0 = $ correct, $E_1 = $ false negative, and $E_2 = $ false positive, by employing our Theorem 2 to do simultaneous minimisation of the Type I and Type II errors with a loss vector $\\ell = (0, 1, 2)$, weighting Type II errors as twice as bad as Type I errors (more time would allow professional estimates of the loss vector to be obtained). Again, the results are positive, showing our confidence region to be smaller.\n\n| $M$   | $m$  | Vol. Union CR                      | Vol. Our CR                        |\n|-------|------|--------------------------------|----------------------------------|\n|  3     | 500  | 0.03067 (0.03056, 0.03077)            | **0.02985** (0.02975, 0.02996)|\n\nAnother excellent observation you make is that the choice of the loss vector may have a large impact on the training procedure and thus the types of errors the final classifier is liable to make. Unfortunately the choice of a scalar metric to optimise cannot be avoided, the question is just which one to choose. We chose the scalar metric to be the \"total risk\" $\\ell \\cdot \\mathbf{R}_D(Q)$ for a given $\\ell$ because that seems the most natural; while one might be uncertain about the future cost of different error types (for example new medical knowledge may change the relative severity of a type II error in skin cancer diagnosis), one presumably has a rough idea. Our bound then in essence gives you the most assurance with respect to this loss vector and ones close to it. Nevertheless, one can always default to putting a uniform weighting across all error types (except correct classification, where you should pick 0). Do let us know if this makes sense!\n\nYou raise the point of calculating a bound using held-out data and mention the very interesting work of Foong et al. It is indeed the case that PAC-Bayes bounds in the literature are usually looser than test set bounds. Given more time we will make this comparison; it is an important and frequently neglected one in the PAC-Bayes literature. Nevertheless, PAC-Bayes bounds, including ours, are worth pursuing for two reasons:\n- First, while the optimal test set bound is known (the Binomial tail bound), PAC-Bayes bounds are still an open research direction and the community has seen a dramatic improvement in the tightness of PAC-Bayes bounds. There is a hope that PAC-Bayes bounds will eventually beat test-set bounds, and we hope that our bound is a stepping stone along this path; by showing how to generalise existing results, it may provide a recipe to generalise any future tighter PAC-Bayes bounds.\n- Second, at least half the value of PAC-Bayes bounds lies in shedding light on generalisation rather than getting tight empirical bounds. For example the framework can help answer questions on sample complexity, as in \"Pac-bayes, mac-bayes and conditional mutual information: Fast rate bounds that handle general VC classes\" by (Grunwald, Steinke, Zakynthinou, 2021). Our result makes progress on the sample complexity of bounds on the the kl(), relating it to the number of error types.\n\nFinally, thank you for your two minor points! We are grateful that you read the paper so carefully and took the time to relay even these minor points to us, which we have now corrected. We hope we have managed to address all of your questions and that you may even consider raising your score.", "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": "", "extra_scores": {}}]

Author rebuttal:
We genuinely thank all four reviewers for their many insightful comments, constructive feedback, and astute observations. We have responded to all four reviewers individually. We hope they let us know in the discussion phase if there is anything we should clarify, or any further results they would like to see, and we will do our best to get back to them promptly. Thank you again investing the time to write these thorough reviews.

Meta-review: The paper cleverly extends the PAC-Bayesian theory. Even if it builds on previous works, the theoretical contributions are not straightforward and require several non-trivial steps.

Of note, the reviews have led the authors to commit to further experiments, which will enrich the manuscript. 

The authors should cite Wu and Seldin (2022) as mentioned by Reviewer cfTA.  I also enjoin the authors to mention that the multinomial distribution has been used by Lacasse et al. (2006, Theorem 6) to simultaneously bound the so-called *expected disagreement*, *expected joint success* and *expected joint error* of the C-bound. Even if the latter pursued a different goal and is restricted to a multinomial distribution of solely three events, some proof techniques are similar to the current work. This might be more obvious in the detailed treatment of Germain et al. (2015, Section 5.4).

### References
Lacasse, Laviolette, Marchand, Germain, Usunier. PAC-Bayes Bounds for the Risk of the Majority Vote and the Variance of the Gibbs Classifier. NIPS 2006

Germain, Lacasse, Laviolette, Marchand, Roy. Risk bounds for the majority vote: from a PAC-Bayesian analysis to a learning algorithm. JMLR (2015)
Decision: Accept (poster)