Controlling Confusion via Generalisation Bounds
Authors: Reuben Adams
John Shawe-Taylor
Benjamin Guedj
Venue: NeurIPS 2022 Submitted (2022)
Keywords: PAC-Bayes
Generalisation bounds
Multiclass classification

Abstract: We establish new generalisation bounds for multiclass classification by abstracting to a more general setting of discretised error types. Extending the PAC-Bayes theory, we are hence able to provide fine-grained bounds on performance for multiclass classification, as well as applications to other learning problems including discretisation of regression losses. Tractable training objectives are derived from the bounds. The bounds are uniform over all weightings of the discretised error types and thus can be used to bound weightings not foreseen at training, including the full confusion matrix in the multiclass classification case.

Controlling Confusion via Generalisation Bounds
Anonymous Author(s)
Affiliation Address
email
Abstract
We establish new generalisation bounds for multiclass classification by abstracting more general setting of discretised error types. Extending the PAC-Bayes theory, we are hence able to provide fine-grained bounds on performance for multi- class classification,, as well as applications to other learning problems including discretisation of regression losses. Tractable training objectives are derived from the bounds. The bounds are uniform over all weightings of the discretised error types and thus can be used to bound weightings not foreseen at training, including the full confusion matrix in the multiclass classification case.
2
8
Introduction
component of the theoretical understanding of machine learning 11 algorithms. For over two decades now, the PAC-Bayesian theory has been at the core of studies generalisation abilities of machine learning algorithms. PAC-Bayes originates in the seminal work of [24, 25] and was further developed by citepcatoni2003pacccc aatappacctttmi2200aaaiissaallll among other authors-we refer to the recent surveys [16] and [1] for introduction the field. The outstanding empirical successes of deep neural networks in the past decade call for better theoretical understanding of deep learning, and PAC-Bayes emerged one of the few frameworks allowing the derivation of meaningful (and non-vacuous) generalisation bounds for neural networks: the pioneering work of [13] has been followed by number of contributions. including [28]. [35], [19], [30, 31] and [4, 6, 5], to name but few.
Generalisation bounds
13
14
15
17
18
19
Much of the PAC-Bayes literature focuses on the case of binary classification, of multiclass classification where one only distinguishes whether each classification is correct or incorrect. This is in stark contrast to the complexity of contemporary real-world learning problems. This work aims to
21
23 bridge this gap via generalisation bounds that provide information rich measures of performance at test
24 time by controlling the probabilities of errors of any finite number of types, bounding combinations
25 of these probabilities uniformly over all weightings.
Previous results. We believe our framework of discretised error types to be novel. In the particular 27 case of multiclass classification, little is known from a theoretical perspective and, to the best of our knowledge, only handful of relevant strategies or generalisation bounds can be compared to the 29 present paper. The closest is the work of [27] on a PAC-Bayes generalisation bound on the operator norm of the confusion matrix, train Gibbs classifier. We focus different performance metric, 31 in the broader setting of discretised error types. [17] suggest to minimise the confusion matrix norm with focus the imbalance between classes; their treatment is not done through PAC-Bayes. [18]
33 extend the celebrated C-bound in PAC-Bayes to weighted majority votes of classifiers, to perform
34 multiclass classification. [3] present streamlined version of some of the results from [27] in the
35 case where some examples are voluntarily not classified (e.g., in the case of too large uncertainty).
36 More recently, [15] derive bounds for a majority vote classifier where the confusion matrix serves as an error indicator: they conduct study of the Bayes classifier.
37
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

38
From binary to multiclass classification. A number of PAC- Bayessann bounds have been unified by single general bound, found in [7]. Stated as Theorem 1 below, it applies to binary classification. We use it as a basis to prove our Theorem 3, more general bound that can be applied to, amongst other things, multiclass classification and discretised regression. While the proof of Theorem 3 follows similar lines to that given in [7], our generalisation to 'soft' hypotheses incurring any finite number of error types requires a non-trivial extension of a result found in [22]. This extension (Lemma 5), along with its corollary (Corollary 6) may be of independent interest. The generalisation bound in [22], stated below as Corollary 2, is shown in [7] to be a corollary of their bound. In similar manner, we derive Corollary 7 from Theorem 3. Obtaining this corollary is significantly more involved than the analogous derivation in [7] or the original proof in [22], requiring a number of technical results found
39
40
41
42
43
44
45
46
47
in Appendix B.
Briefly, the results in [7] and [22] consider an arbitrary input set X, output set y = (-1,1),
49
hypothesis space H C )xx and i.i.d. sample S E (X' x ymm They then establish high probability bounds on the discrepancy between the risk (probability of error an a new datapoint) of any stochastic classifier Q (namely, distribution on H) and its empirical counterpart (the fraction of the sample Q misclassifies). The bounds hold uniformly over all Q and contain a complexity term involving the Kullback-Leibler (KL) divergence between Q and a reference distribution P on H. (often referred to as a prior by analogy with Bayesian inference- see the discussion in 16).
50
51
53
54
55
58
There are two ways in which the results in [7] and [22] can be described as binary. First, as y contains two elements, this obviously an instance of binary classification. But a more interesting and subtle way to look at this is that only two cases are distinguished- correct classification and incorrect classification. Specifically, since the two different directions in which misclassification can be made are counted together, the bound gives no information on which direction is more likely.
57
58
59
60
61
More generally, the aforementioned bounds can be applied in the context of multiclass classification provided one maintains the second binary characteristic by only distinguishing correct and incorrect classifications rather than considering the entire confusion matrix. However, note that these bounds will not give information on the relative likelihood of the different errors. In contrast, our new results can consider the entire confusion matrix, bounding how far the true (read "expected over the generrting distribution")) confusion matrix differs from the empirical one, according to some metric In fact, our results extend to the case of arbitrary label set V, provided the number of different errors one distinguishes is finite.
62
63
64
65
86
67
68
69 Formally, we let U E, be a user-specified disjoint partition of )²2 into finite number of M error types, where we say that hypothesis h E H. makes an error of type j on datapoint (x, y) 71 if (h(r), y) E E₁ (by convention, every pair (0.v) E y² is interpreted as a predicted value 9
72 followed by true value y. in that order). It should be stressed that some Ej need not correspond to mislabellings-indeee -iddeed, some of the E, may distinguish different correct labellings. We then
73
74 count up the number of errors of each type that hypothesis makes on sample, and bound how
75 far this empirical distribution of errors is from the expected distribution under the data- eatta-enerating distribution (Theorem 3). Thus, in generalisation, the (scalar) risk and empirical risk (R((Q) and (Q), defined in the next section) are replaced by M-dimensional vectors (RD (Q) and Rs())) and our discrepancy measure d is divergence between discrete distributions on M elements. Our
76
77
78
79 generalisation therefore allows us to bound how far the true distribution of errors can be from the
80 observed distribution of errors. If we then associate loss value lj E [0, oo) to each E, we can derive
81 a bound on the total risk, defined as the sum of the true error probabilities weighted by the loss values.
82 In fact, the total risk bounded with high probability uniformly over all such weightings. The loss
83 values need not be distinct; we may wish to understand the distribution of error types even across error types that incur the same loss.
94
85
For example, in the case of binary classification with y = (-1, we can take the usual partition into F, ((-1, -1) -)
11) and Fez (), (1) and loss values & 0, f2 = 1, or the ((, 0)) U ((1,1)) ( 1)3 ((10)) and the loss values E = &g- = 0, ls 1, l4 2. More generally, for multiclass classification with N classes and y [N] one may
86
fine-grained partition y²2 (
87
88
take the usual coarse partition into Ei = ((..)) y) E y² 9 = 5} and Eg = { {(0 4) E y²= ú # y} (with é 0 and lg = 1), or the fully refined partition into Eig- = ((i,j)) for i,j [N] (with
89
90
31 correspondingly greater choice of the associated loss values), or something in-between. Note that we 92 still refer to Ej as an "error type" even if it contains elements that correspond to correct classification,
93 namely if there exists E y such that (y. E Ey. As we will see later, a more fine-grained
2

---

94
partition will allow more error types to be distinguished and bounded, at the expense of a looser
95
bound. As final example, for regression with ) = R. we may fix M strictly increasing thresholds
96
0
A1 < X2 <... < AM and partition ) into F. = [(v1, V2) E e²== : >3 S Iyn
y2l < } for
j E [M 1], and Σ' = {(VI, v2) E )²² : 1: - y/2 2 Am3.
87
98
Outline. We set our notation in Section 2. In Section 3 we state and prove generalisation bounds in the setting of discretised error types: this significantly expands the previously known results from [7] by allowing for generie output sets Y/. Our main results are Theorem 3 and Corollary 7. To make
99
100
101
our findings profitable to the broader machine learning community we then discuss how these new bounds can be turned into tractable training objectives in Section 4 (with general recipe described
102
103
in greater detail in Appendix A). The paper closes with perspectives for follow-up work in Section 5
104
and we defer to Appendix B the proofs of technical results.
2
Notation
105
106
For any set A, let ((4) be the set of probability measures on A. For any M E Zsn. define
[M] (,,2,... M). the M/ddimensional simplex A& == {u E [0, 1j u1 +... + UM = 1}
107
and its interior A 30
M ;= A n (0, 1)M For m, M E Zzo. define the integer counterparts Sm,M {Ka...... ................................ Kas) 2 11 +.... + KM = m] and S
Sm.M n 2% The set Sm,ar is the domain of the multinomial distribution with parameters m, M and some AM, which is denoted Mult(m, M, r) and has probability mass function for & E Sm,M given by
109
110
111
M
Mult(k: m. M.r) = -(1
m
1 j=1
II
where
m!!
k1 K2
KM
k1 h2 ... ky
[ M
ky!
112
For q.p e 4,, let kl (qllq denote the KL-divergence of Mult(1, M, q) from Mu, p)). namely
(l(gp)))= == Σソ= 9j In 2, with the convention that 0ln 0 = 0 for x 2 0 and x: In 0 = co for x > 0. pj For M 2 we abuse notation and abbreviate kl((q, 1 - 4) [p. 1 - p)) to kl(gllp). which is then the
113
114
115
conventional definition of kI(-Il-): : [o, 1]2 - [0, oo] found in the MAC-Bayes literature [as in 33, for
116
example].
M Let X and y be arbitrary imput (e.g., feature) and output (e.g., label) sets respectively. Let U E, be a partition of y into a finite sequence of M error types, and to each E, associate a loss value lj E [0, oc). The only restriction we place on the loss values L, is that they are not all equal. This is not a strong assumption, since if they were all equal then all hypotheses would incur equal loss and there would be no learning problem: we are effectively ruling out trivial cases.
117
118
120
Let H C yd denote hypothesis class, D E M(X' x Y) a data- generattnn distribution and S ~ Dm an i..d. sample of size m drawn from D. For h E H and j E [M] we define the empirical j-risk and true j-risk of h to be (h) := 1 ((.yes 1[(h(z), w) E Eş] and R2 := [(1()))))) E Eý]], respectively, namely, the proportion of the sample S on which makes [A ()
122
123
m
125
126
an error of type E, and the probability that h makes error of type Ej on new (I.
D.
127
More generally, suppose H. C. {M())* is class of soft hypotheses of the form H : X + MO)) where, for any A C V. H(x) [A] is interpreted as the probability according to H that the label of is in A. It is worth stressing that soft hypothesis is still deterministic since prediction is not drawn from the distribution it returns. We then define the empirical j-risk of H to be (H)
128
129
E wases [xx E y (ū.v) E E. namely the mean-over the elements (x. v) of S- probability mass H assigns to predictions ÿ E y incurring an error of type E, when labelling each x. Further, we define the true j-risk of H to be R3, (H) := Err.y)-D [H (x) E y: (0. v) E E,}]] (I,z) D p-oroaabilliyy mass /l assigns to predictions á E y incurring an error of type E, when labelling each x. We will see in Section 4 that the more general hypothesis
132
133
134
namely the
135
class H C M()))** is necessary for constructing a differentiable training objective.
136
To each ordinary hypothesis h E ) there corresponds soft hypothesis H E &M())**' that, for each X, returns a point mass on h(x). In this case, it is straightforward to show that R R (H) and (h) = R², (H) for all j E [M], where we have used the corresponding definitions above for ordinary and soft hypotheses. Since, in addition, our results hold identically for both ordinary and
137
138
139
3

---

141
soft hypotheses, we henceforth use the same notation h for both ordinary and soft hypotheses and (h). It will always be clear from the context whether we are their associated values R'g (h) and Ry (h). dealing with ordinary or soft hypotheses and thus which of the above definitions of the empirical and true j-risks is being used.
142
143
145
We define the empirical risk and true risk of (ordinary or soft) hypothesis h to be (h)h) := ( (h),..., R (h)) and RD(h)= =- (R2) (h)..... R2 (h)), respectively. It is straightforward to show that Rs and (h) are elements of AM. Since S is drawn i.i.d. from D, the expectation of the empirical risk is equal to the true risk, namely Es[ARs(()) = H'p (h) for all j and thus Es [R(()) (h). Finally, we generalise to stochastic hypotheses Q E M(H), which predict by first drawing deterministic hypothesis ~ Q and then predicting according to h, where a new h is drawn for each prediction. Thus, we define the empirical j-risk and true j-risk of Q to be
146
147
148
150
the scalars R' (Q) := En [R2 and Ry (Q) == E (h)]. for [M], and simply the empirical risk and true risk of Q to be the elements of AM defined by (Q( == En-Q Rssh)) and RD(Q Q)= == Bn-oo RD [R)] As before, since S is i.i.d.,
152
153
154
have (using Fubini this time) that M,
Es R. (Q) = (Q) Finally, given a loss vector& L E [0, )o)M, we define the total risk of Q by the scalar RQ( == Σne R (Q). 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 are not related by Bayes' theorem.
155
156
157
158
159
3
Inspiration and Main Results
160
We first state the existing results in [7] and [22] that we will generalise from just two error types (correct and incorrect) to any finite number of error types. These results are stated in terms of
the scalars (Q) == I Danies 11 [xxx) # y] and (Q) == BEEW) 1 (a(x)) o v] and, as we
162
163
demonstrate, correspond to the case M = 2 of our generalisations.
164
Theorem 1. (7, Theorem 4) Let X be an arbitrary set and y = {-1,1)- Let D E M(X x y) distribution and H C yd be hypothesis class. For any prior P E M(H), ô E (0, 11, convex function d : [0, 1]2 + R. sample size m and B E (0, x)). with probability at least
165
be a
166
1 å over the random draw S ~ Dmm, we have that simultaneously for all posteriors Q E M(H)
1 S 3
[K(QIIP) +In 3)
8
168
EE (k; m. r) exp [d (m:+))) nomial probability mass function mi,(k; (*)r*(1 r)m-
with Ia B) = supre[o.1]
}. where Bin(k; r) is the bi-
170
Note the original statement in [7] is for positive integer m', but the proof trivially generalises to any (0, oo). One of the bounds that Theorem I umifies-whicl we also generalise- that of [33]. later tightened in [22], which we now state. can be recovered from Theorem 1 by setting 3 = m
171
172
and d'g. = kl(gllp) == q In 2 + (1 ( l-g.
173
174
Corollary 2. (22, Theorem 5) Let X be an arbitrary set and y (-1, Let D E M(X x y)
be a data- seatttggenerinnngg distribution and H C yy² be hypothesis class. For any prior P E M(H), dE E (0, 1] and sample size m, with probability at least 8 over the random draw S Dmm, we
175
178
have that simultaneously for all posteriors Q E M(H)
177
1 (I(Rs(Q), < KL(QIIP) + In 8
2/m
178
We wish to bound the deviation of the empirical vector (Q) from the unknown vector RD (Q). Since in general the stochastic hypothesis Q we learn will depend on the sample S, it is useful to obtain bounds on the deviation of Rs(Q) from RD( that are uniform over Q, just as in Theorem 1 and Corollary 2. In Theorem 1, the deviation d( (Q)(Q). (Q)) between the scalars
179
180
(s( (Q) E [0. 1] is measured by some convex function d [0. 1|2 - R. In our case, the deviation d( (Q),)). RR between the vectors Rs(Q), RQ( E A is measured by some convex function d A22 M - RR. In Section 3.2 we will derive Corollary from Theorem 3 by selecting
182
184
3 m and d(q.p) p) := kl(g]la [())) analogous to how Corollary 2 is obtained from Theorem 1.
4

---

186
3.1
Statement and proof of the generalised bound
187
We now state and prove our generalisation of Theorem The proof follows identical lines to that of Theorem I given in [7], but with additional non-trivial steps to account for the greater number of error types and the possibility of soft hypotheses.
188
189
Theorem 3. Let X and y be arbitrary sets and Uرر Fg be a disjoint partition of y². Let D e
190
M(X x Y) be a cettranne distribution and H C MM)))² be hypothesis class. For any prior E (H)) 8 E (0, 1,, jointly convex function d : A + R. sample size m and 3 (0, oo), with probability at least 1 ó over the random draw S ~ Dm,, we have that simultaneously for all
192
194
posteriors Q E (MH
KL(QIIP) + In [m(m, d( (Q), S 3
(1)
5
where Ia B) SuPrE [Enes... Mult(k; m, M, r) exp (Bd (mm r)) Further, the bounds are unchanged if one restricts to ordinary hypothesis class, namely if C yxx
195
196
197
The proof begins on the following page after a discussion and some auxiliary results. One can derive multiple bounds from this theorem, all of which then hold simultaneously with probability at least 1 -. 6. For example, one can derive bounds on the individual error probabilities It,, (Q) or combinations thereof. It is this flexibility that allows Theorem 3 to provide far richer information on the performance of the posterior Q on unseen data. For more in depth discussion of how such bounds can be derived, including a recipe for transforming the bound into a differentiable training objective, see Section 4 and Appendix A.
198
200
202
204
To see that Theorem 3 is a generalisation of Theorem 1, note that we can recover it by setting
205
y (-,,1), M = 2. Eg ((-y. y. y) y }/} and E2 ((.v) : y E )). Then, for any
convex funetion d : 1] - IR, apply Theorem 3 with the convex function d' A M + R
206
defined by d' d'(uu, ug). 22)) == d(u1, U1) so that Theorem 3 bounds d' (Rs (Q), (Q), (Q)) =
207
((B)(Q)) RT(()) which equals (()s(Q)) (Q)) in the notation of Theorem 1, Further,
208
m
Σ Mult(k;m, 2) exp Bdd ( r))
Σ
Bin(k; m. r1) exp (3d (m.m)).
S
A==
209
so that the supremum over rı E [0, 1] of the right hand side equals the supremum over r E 42 of the left hand side, which, when substituted into (1), yields the bound given in Theorem 1.
210
211
Our proof of Theorem follows the lines of the proof of Theorem in [7], making use of the change of measure inequality Lemma 4. However, complication arises from the use of soft classifiers E M()) A similar problem dealt with in [22] when proving Corollary by means of a Lemma permitting the replacement of [0, 1]-valued random variables by corresponding (0. 1 --valued
212
213
214
215
random variables with the same mean. We use a generalisation of this, stated as Lemma 5 (Lemma
3 in 22 corresponds to the case M 22), the proof of which is not insightful for our purposes and thus deferred to Appendix B. I. An immediate consequence of Lemma 5 is Corollary 6, which is a generalisation of the first half of Theorem 1 in [22]. While we only use it implicitly in the remainder of the paper, we state it as it may be of broader interest.
217
218
219
The consequence of Lemma 5 is that the worst case (in terms of bounding di Rs((), Rn(Q))) occurs when R(())))) (h) is a one-hot vector for all (x, y) E and h E H. namely when H C ((O) only contains hypotheses that, when labelling S. put all their mass on elements ÿ E ) that incur the same error type'. In partieular, this the case for hypotheses that put all their mass on a single element of D equivalent to the simpler case H C )d as discussed in Section 2. Thus, Lemma 5 shows that the bound given in Theorem cannot be made tighter only by restricting to such hypotheses.
221
223
225
Lemma 4. (Change of measure, 10, 11) For any set H. any P, Q E (M(H) and any measurable
E. exp(o(h)). function ò : H R E h-Q ( I KL(Q[PP) + In hwp
227
228
Lemma 5. (Generalisation of Lemma 3 in 22) Let XI...., X,m be i.i.d valued random vectors with mean le and suppose that f A m + R. is convex. If X ( X are i..dd Mult(1, M, p))
229
random vectors, then E X mm) < B[f(X1,.... X
More precisely, when Wh H V(z E S Ej E [M] such that M(x)((E y: (0.1) E E,) =1
5

---

Corollary 6. (Generalisation of Theorem 1 in 22) Let Xi..... Xm be i.. as-vuueed random
"i....,,,,, X,, be i..d. Mult(1, M, p.). Define X 232 vectors with mean p. and Xi....,
m == X; and
X - X Then [lexp(mkI(X [|]]] S [lexp(mkl(X [1]]]].
233
234
Proof. (of Corollary 6) This is immediate from Lemma since the average linear, the ki-divergence is convex and the exponential is non-decreasing and convex.
Proof. (of Theorem 3) The case H. S ) follows directly from the more general case by taking
236
237 H' = (M E EM))) 3h E H such that Va X 1((r) = Ók(z)), where Ōk(x) E M()) denotes
point mass on h(xx). For the general case H. S M()) using Jensen's 's inequality with the convex
238
function :( and Lemma 4 with @(h) 3d Rs (h), RD(h)), see that for all Q M(H)
Bd(Rs(Q), Rn) 3d Rs),,, E Ro(h))
h-Q h~Q
s E h~Q
3d (ss(Rs)))) RD(h))
KL(Q]IP) + in
E exp R (d), Ro())) A~P
=II(QIIP) + In(2r(5)),
240 where 7p( = Ex-Peep
Rn(h))). Note that 7p(S) non-negative random (Zp(S) & Re (8()
241 variable, so that by Markov's s inequality P
2 1- Thus, since In(-)
S~Dm
242 is strictly increasing, with probability at least 8 lovr S D we have that simultancously for
all Q E MMHH)
(RR((Q),R((0)) S KL(QIIP) In S'm Zp(S")
To bound ES let X; == (1)) E AM for i E [m]. where (I,, W) is the 245 i'th element of the dummy sample S'. Noting that each X; has mean (h),), define the random Mult(m, M, (h).)). Finally let S AT + E be defined by f Tm) == exp (3d ( Σn i= Ij RD(h))) which is convex since 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 5, we have that ES (S") can be written as
244
vectors X Mult(1, M, (h)))) and Y = E X
248
the average is linear,
250
ED Zp(S") =
E
exp (1)) (D)()) (Bd(Rs.(() Rs: (h), RD(()))
SmmD m h~P
E
E
exp
h~P
Smm
m Σ
E
exp
3d
X RD(h)
hss Xm.....m
m
i=1
m
<
E
exp
3d
Σ
X RD(
hsP
X
XI
m
Y. BD(())
= E.
exp
3d
h>P Y
= E h>P
Mult(k; (, m, M, RD(h) exp (Bd(#, Ro(h))
RESm.
Mult(k, (, exp (Bd th ())
< sup TEAM
Σ
251 Which the definition of Ia(m, Inequality (1) then follows by substituting this bound on D Dp(S" into (2) and dividing by B.
D

---

253
3.2
Statement and proof of the generalised corollary
254
We now apply our generalised theorem with = m and d p) = kl(glp)). This results in the following corollary, analogous to Corollary 2 (although the cuuli-dimensionality makes the proof much more involved, requiring multiple lemmas and extra arguments make the main idea go through). We give two forms of the bound since, while the second is looser, the first is not practical to calculate except when m is very small.
255
256
258
Corollary 7. Let X' and y be arbitrary sets and U Ej be a disjoint partition of y2. Let D E M(X x 3) be a data- gentrrtnnnn distribution and H S &(y) be a hypothesis class. For any prior P E _MHH), 8 E (0, 1] and sample size m, with probability at least 1 - 8 over the random draw S D we have that simultaneously for all posteriors Q M(H))
259
260
281
262
1 KL(Q
m!
[[Rs(Q)|RR(Q))
+n
(3)
òm
ky!
ke Ar
j=1
(L(QUI)) + in V Vire 1/(2m) m
1
m
M
M
(4)
(Tm)² /122 2
m/220 M
(M=2)
263
where the second inequality holds provided m 2 M. Further, the bounds are unchanged if one restricts to an ordinary hypothesis class, namely if C y*
264
265
While analogous corollaries can be obtained from Theorem 3 by other choices of convex function d. the kl-divergence leads to convenient cancellations that remove the dependence of Ia r) on making Ia(m, B) == supreAm Ia (m, 3,r) simple to evaluate. Note (4) is logarithmic in 1/6 (typical of PAC-Bayes bounds) and thus the confidence can be increased very cheaply. Ignoring logarithmic terms, (4) is Ol1/m), also expected. As for M, simple analysis shows that (4) grows only sublinearly in M, meaning M can be made quite large provided one has a reasonable amount of data. To prove Corollary 7 we require Lemma 8, the proof of which is deferred to Appendix B.2.
266
268
270
272
Lemma 8. For integers M 2 1 and m 2 M. EKESPO M. 11, Vk,
m
Proof. (of Corollary 7) Applying Theorem 3 with d(g.p) kl(gllp) (defined in Section 2) and 274 = m gives that with probability at least - 8 over S ~ D. simultancously for all pos- teriors Q E M(H),, (I RD())) < m [L + In Zafm.m)), where Im(mm, m) ==
275
suPreA [EKESm,.. Mult(k k; m, M, r) exp (mkl( & r)]. Thus, establish the first inequality of m
277 the corollary, it suffices show that
Ia(m, m) S m!! m
Σ KESm, M j=1 kyy
(5)
278
To see this, for each fixed r (rI,...,TM) E AM let Jr = {j E [M] : Ty 0}. Then
279 Mult(k; m, M, O for any k E Sm.as such that k, + for some j E Jr. For the other
280 & E Sm,M, namely those such that k, = 0 for all j E Jr. the probability term can be written as
K Mult(k; m, M,, TT. 11 " nl K, lls r, and (recalling the convention that
281
On 0 0 = 0) the term exp(mkl( & r)) can be written as
k exp
k
Σ jEJ
exp
Tj
mr,
mry
m
jæJr
jgJ,
283
where the last equality is obtained by recalling that the k; sum to m. Substituting these two expressions into the definition of Ia(mm, m) and only summing over those & E Sm,y with non-zero probability, we obtain
284
285
Σ
Mult(k; m, M,r) exp (mkl ( r)))
Σ
Mult(k; M, exp (mkl ( r)
KESm.M
M VjEJ, ky=
7

---

E
m!!
kg
R2
1 ky
m
F3
kC k se VjEJ, Ny =0
JEJ.
j4Jr
m!
Σ
m
MESm VjEJ, ky=
JEJt
k ky!
m!
Σ
(because O" 1)
m
MESm. Md vjeJ, Ry=0
j=
M
m!!
171
SESm,M
J=1
Since this is independent of r, it also holds after taking the supremum r AM of the left hand side. We have thus established (5) and hence (3). Now, defining S UM= Sm. + R by
287
288
f(k) =
Mul k /kyl. we see that establish inequality (4) suffices to show that
m!!
f(k) S VTE 1/12m
m
Σ 2=0
M
(6)
2
(am) 2 M==
RES
289 We show this by upper bounding each flk) individually using Stirling's formula: Vn 2
v 22 (2) < n! < V2Tn (=) e Since we cannot use this to upper bound 1/ky! when
290
kj O, we partition the sum above according to the number of coordinates of k at which k, 0. Let
292
2 index the number of such coordinates. Since f is symmetric under permutations of its arguments,
-1-1
Σ
f(k)
Σ
Σ
flk)..
lE k
==0
kES M.Sm.
293
For E 5,,s Stirling's formula yields f(k)
I
2
2xk
11 Tog. An application of Lemma 8 now gives
(2n)aryz
S(k) <
e
Σ
II
M
e m
M-2
M2
ki
(2m))
2 (Tm)
3/2 r (M=2)
kES m.
j=1
295
Substituting this into equation (7) and bounding m!! using Stirling's formula, we have
m!!
Σ s(k)
22
Σ
M
e m
m
277
21/ (Tr))² /2 r M-z
KESm,
M-1
M
M
1
me
1/12m
(Tm)=/² M-2
which is (6), establishing (4) and therefore completing the proof.
4 Implied Bounds and Construction of Differentiable Training Objective
298 As already discussed, a multitude of bounds can be derived from Theorem 3 and Corollary 7, all of which then hold simultaneously with high probability. For example, suppose after use of Corollary
300
7 we have a bound of the form kl( Rs (Q]]
< B. The following proposition then yields the
bounds Lj < (Q) < U3. where L; == inf E [o, 1] (Q) (pp) < B) and Uj= := sup(p e
301
[0, 1] (I
B}. Moreover, since in the worst case have kl R (Q) RD B,

---

303
the proposition shows that the lower and upper bounds Lj and U, are the tightest possible, since if > B implying ki(Rs(Q)) RD(Q)) > B. For more (Q) & μ Uy] then (l(R'(() (Q) R2
304
305
precise version of this argument and a proof of Proposition 9, see Appendix B.3.
Proposition 9. Let q.P E AM. Then kl(g; (!nz)) I kl(glpp) for all j E [M], with equality when
306
11 T- qi- for all + j. P:
307
As second much more interesting example, suppose we can quantify how bad error of each type is by means of a loss vector & [0, oo) where E is the loss we attribute to an error type Ej. We may then be interested in bounding the total risk (Q) E [0, oo) of Q which, recall, is defined by R (Q) = プド E (Q). Indeed, given a bound of the form kl (Rss(( ((Rs(Q))RR(Q)) S B, we can derive (Q) S Sup( bry : E AM, kl (Q)lr( < B). This motivates the following definition of 2 (w)c). To see that this is indeed well-defined (at least when u E 7 see the discussion at the beginning of Appendix B.4.
309
310
312
313
314
Definition 10. For u E A, E [0, o0) and l E [0, MM) define kl (ulc)) = sup(E; M Egyy
315
318 E AM. kI(zul|v) S c).
317 Can we calculate k (ulc) and hence fe (kl, (ulc)) in order to evaluate the bound on the total risk? Additionally, if we wish to use the bound on the total risk as a training objective, can we calculate the partial derivatives of fč (u. c) == Se(klz
318
(ulc)) (x/c)) with respect to the My and e so that we can use gradient descent? Our Proposition 11 answers both of these questions in the affirmative, at least in the sense that it provides a speedy method for approximating these quantities to arbitrary precision provided uj > 0 for all; j E [M] and e > O. Indeed, the only approximation step required is that of approximating the unique root of a continuous and strictly increasing scalar function. Thus, provided the N themselves are differentiable, Corollary combined with Proposition 11 yields tractable
319
320
321
322
323
324
325
and fully differentiable objective that can be used for training. More details on how this can be done, including an algorithm written in pseudocode, can be found in Appendix A. While somewhat analogous to the technique used in [9] to obtain derivatives of the one- one-dimensional kl-inverse, our proposition directly yields derivatives on the total risk by (implicitly) employing the envelope theorem (see for example 34). Since the proof of Proposition 11 is rather long and technical, we defer it to Appendix B.4.
326
327
328
329
330
Proposition 11. Fix E [0, )o) such that not all Ej are equal, and define Se : AAM - [0, oc) by fe(v) Σド= Ezug. For all u (u, c) E A (0, oo), define o² (") == kl, (ulc) A and let = (be(1)), where de : (-xc, maxj fj) TR is given by Φe(u)= == -In(- Σ/= w+(e)) + Σ/= ug In(- + (z)), which is continuous and strictly increasing. Then (ū) = kl (ulc) is given by
331
332
1 (ū) (-xx,-maxx, Eÿ) be the unique solution
338
334
335
(ū)jf
M
0' (ū)
for j E [M]. where X(ū)= =
Σ
Uj
11" (ū) + +
④ +
336
Further, defining fē 4/ x (0, xo) + 10, by fū == fe(v" (ū)), we have that
0fž (ū) = (a) Juj
[1+h In 0² (ū),
Uj
and
0fi (5² = - (ū))
dc
337
5 Perspectives
338
By abstracting to general setting of discretised error types, we established novel type of generalisa- tion bound (Theorem 3) providing far richer information than existing PAC-Bayes bounds. Through our Corollary 7 and Proposition 11, our bound inspires training algorithm (see Appendix A) suitable
339
3/0
341
for many different learning problems, including structured output prediction [as investigated by 8, in the PAC- Bay-Bayes setting], multi-task learning and learning-to-lest [see e.g. 23]. We will demonstrate these applications and our bound's 's utility for real-world learning problems in an empirical follow-up up study. Note we require i.i.d. data, which in practice is frequently not the case or is hard to verify. Further, the number of error types M must be finite. While in continuous scenarios it would be preferable to be able to quantify the entire distribution of loss values without having to discretise into finitely many error types, in the multiclass setting our framework is entirely suitable.
342
343
344
346
9

---

References
348
349
[1] Alquier, P. (2021). User-friendly introduction to PAC-Bayes bounds. arXiv:2110.11216.
arXiv preprint
350
351
[2] Ambroladze. A.. Parrado-Hemándder E., and Shawe-Taylor, J. (2006). Tighter PAC-Bayee bounds. In Schölkopf. B., Platt, J. C., and Hofmann, T., 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-16. MIT Press.
352
353
354
355
356
[3] Benabbou, L. and Lang, (2017). PAC-Bayesian generalization bound for multi-class learning. In NIPS 2017 Workshop. (Almost) 50 Shades of Buyesian Learning: PAC-Bayesian trends and insights.
358
[4] Biggs, F. and Guedj. B. (2021). Differentiable PAC-Bayes objectives with partially aggregated neural networks. Entropy. 23(10):1280.
380
[5] Biggs, F. and Guedj. B. (2022a). Non-vacuous generalisation bounds for shallow neural networks arXiv preprint arXiv:2202.01627.
382
[6] Biggs, F. and Guedj, B. (2022b). On margins and derandomisation in PAC-Bayes. In AISTATS.
364
[7] Bégin, L... Germain, P., Laviolette, F., and Roy, J.FF. (2016). PAC-Bayesian Bounds based on the Rényi Divergence. In Gretton, A. and Robert, C. C., editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 435-444, Cadiz, Spain. PMLR.
365
366
388
[8] Cantelobre, T., Guedj. B.. Pérez-Ortiz, M., and Shawe-Taylon J. (2020). A pac-bayesian perspec- tive on structured prediction with implicit loss embeddings. arXiv preprint arXiv:2012.03770.
389
370
[9] Clerico, E., Deligiannidis, G., and Doucet, A. (2021). Conditional Gaussian PAC-Bayes. arXiv preprint arXiv:2110.11880
371
372
[10] Csiszár, I. (1975). 1-divergence geometry of probability distributions and minimization problems. The Annals of Probability, pages 146-158.
373
374
[1I] Donsker, M. and Varadhan, S. (1975). 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.
375
377
[12] Dziugaite, G. K., Hsu, K., Gharbich, W., Arpino, G., and Roy, D. (2021). On the role of data in PAC-Bayes. In Banerjee, A. and Fukumizu, K., editors, The 24th International Conference Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 004-612. PMLR.
379
381
[13] Dziugaite, G. K. and Roy, D. M. (2017). Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Conference on Uncertainty in Artificial Intelligence [UÁI].
382
383
384
[14] Dziugaite, G. K. and Roy, D. M. (2018). Entropy-SGD optimizes the prior of PAC-Bayes bound: Generalization properties of entropy-SGD and data-dependent priors. In Dy, J. G. and Krause, A., editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmssmsssan Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 1376-1385. PMLR.
385
386
387
388
389
[15] Feofanov, V., Devijver, E., and Amini, M.-R. (2019). Transductive bounds for the multi- class majority vote classifier. Proceedings of the AAAI Conference on Artificial Intelligence, 33:3566-351 3573.
390
382
[16] Guedj, B. (2019). A Primer on PAC-Bayesian Learning. In Proceedings of the second congress of the French Mathematical Society.
10

---

394
[17] Koço, S. and Capponi, C. (2013). On multi class classification through the minimization of the confusion matrix norn. In Ong, C. S. and Ho, T. B., editors, Proceedings of the 5th Asian Conference on Machine Learning, volume 29 of Proceedings of Machine Learning Research, pages 277-292, Australian National University, Canberra, Australia. PMLR.
395
397
398
[18] Laviolette, F., Morvant, E., Ralaivola, L.,, and Roy, J.-F. (2017). Risk upper bounds for general ensemble methods with an application multiclass classification. Neurocomputing. 219:15-25.
399
400
[19] Letarte, G., Germain, P., Guedj. B., and Laviolette, F. (2019). Dichotomize and generalize: PAC-Bayesinn binary activated deep neural networks. In Wallach, H., Larochelle, H.. Beygelzimer, A., dAlché Buc, F., Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems 32, pages 1887268822 Curran Associates, Inc.
402
404
[00] Lever, G., Laviolette, F., and Shawe-Taylor, J. (2010). Distributtoon-dependeet PAC-Bayes priors. In International Conference on Algorithmic Learning Theory, pages 119-133. Springer.
406
[21] Lever, G., Laviolette, F., and Shawe-Taylor, J. (2013). Tighter PAC-Bayes bounds through distributiondeependen priors. Theoretical Computer Science, 473:4-28.
407
408
[22]
Maurer, A. (2004). A note on the PAC-Bayesian theorem. arXiv preprint cx/041109)
409
[23] Maurer, A., Pontil, M., and Romera-Paredes, B. (2016). The benefit of multitask representation learning, J. Mach. Learn. Res., 17:81:1
411
[24] McAllester, D. A. (1998). Some PAC- PAC-Bayesian theorems. In Proceedings of the eleventh annual conference on Computational Learning Theory, pages 230-234. ACM.
412
[25] McAllester, D. A. (1999). PAC-Bayesian model averaging. In Proceedings of the twelfth annual conference on Computational Learning Theory, pages 164-170. ACM.
414
[26] Mohamed, S., Rosca, M., Figurnov, M., and Mnih, A. (2020). Monte carlo gradient estimation in machine learning. J. Mach. Learn. Res., 21(132):1-62
416
417
[27] Morvant, E., Kogo, S., and Ralaivola, L.. (2012). PAC-Bayesian generalization bound on confusion matrix for multi-class classification. Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 - July 1, 2012. icml.cc / Omnipress.
418
419
420
421
[28] Neyshabur, B., Bhojanapalli, S., and Srebro, N. (2018). A PAC-Bayesian approach to spectrally- normalized margin bounds for neural networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net.
422
423
424
425
[29]
E.,, Ambroladze, A., Shawe-Taylor, J., and Sun, S. (2012). PAC-Bayes bounds with data dependent priors. Mach. Learn. Res., 13:3507-3531.
427
[30] Pérez-Ortin M., Rivasplata, O., Guedj, B., Gleeson, M., Zhang. J., Shawe- Taylor J., Bober, M., and Kittler, J. (2021). Learning pac-bayes priors for probabilistic neural networks. arXiv preprint 10Xv:21099.1304.
429
430
[31] Perez-Ortiz, M., Rivasplata, O., Shawe-Taylor, J., and Szepesvari, C. (2021). Tighter risk certificates for neural networks. Journal of Machine Learning Research, 22(227):1
431
432
[32] Rivasplata, O., Szepesvári, C., Shawe-Taylor, J., Parrado-Hernándezz F.,, and Sun, S. (2018). PAC-Bayes bounds for stable algorithms with instance-dependent priors. In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R., editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages
433
434
435
436
[33] Seeger, M. (2002). PAC-Bayesian generalisation error bounds for Gaussian process classification. Journal of Machine Learning Research, (3c2))233-
438
[34] Takayama, A. and Akira, T. (1985). Mathematical economics. Cambridge university press.

---

440
[35] Zhou, W., Veitch, V.. Austern M., Adams, R. P., and Orbanz, P. (2019). Non-vacuous general-
441
ization bounds the ImageNet scale: a PAC-Bayesian compression approach. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, IA, USA, May 6-9, 2019. OpenReview.net.
442
443
Checklist
444
1. For all authors...
446
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope? [Yes]
447
448
(b) Did you describe the limitations of your work? [Yes] We touch upon limitations in Section 5.
450
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Due to the theoretical nature of our contributions, we do not foresee any immediate societal impacts of our work. However, we very much hope that a better understanding of how algorithms generalise in the multiclass setting can inspire more informed utilisation of these algorithms,, and eventually benefit the many people impacted by the deployment of these methods, ultimately leading to a positive societal impact.
452
453
454
456
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
457
458
2. If you are including theoretical results...
459
(a) you you state the full set of assumptions of all theoretical results? [Yes] All assumptions present in the statements of the theoretical results.
480
461
(b) Did you include complete proofs of all theoretical results? [Yes] As follows:
462
i. Theorem is not proved here as it is due to 7, where it appears as Theorem 4.
463
ii Corollary 2 is not proved here as it is due to 22, where it appears as Theorem 5,
464
iii. Theorem is proved in Section 3.1 after the statement of the necessary Lemmas and 5 and Corollary 6. The proof starts on page 6.
465
486
iv. Lemma 4 is not proved here as it is a known result. See the given references (10, 11).
467
468
The proof of Lemma 5 is not insightful for our purposes and is thus deferred to Appendix B.1 of the supplementary material.
469
470
vi. The proof of Corollary 6 in Section 3.1 can be found directly after the corollary statement.
vii. The proof of Corollary is found in the same section as the statement (3.2), starting on the same page after stating the helping Lemma 8.
473
474
viii. The proof of Lemma 8 can be found Appendix B.2 of the supplementary material.
475
ix. The proof of Proposition 9 can be found in Appendix B.3 of the supplementary material.
478
477
x. The proof of Proposition 11 can be found in Appendix B.4 of the supplementary material.
478
3. If you ran experiments...
480
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [N/A]
481
482
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
483
484
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
485
486
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
487
488
4. If you are using existing assets (e.g., code, data, models) or curating/releasnng new assets...
489
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
12

---

(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
492
498
(d) Did you discuss whether and how consent was obtained from people whose data you' 're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
496
information or offensive content? [N/A]
497
5. If you used crowdsourcing or conducted research with human subjects...
498
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
501
502
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
503
13


Reviews:
[{"review_id": "YU6xPyqafRP", "reviewer": "Reviewer_x9gX", "summary": "This paper sets out to extend the PAC-Bayes framework to establish new generalization bounds for multi-class classification with M classes of errors extending the 0-1 risk. The main results appear to be Theorem 3 and Corollary 7, which generalize previously known results in this space, and can recover those existing results. My biggest concern about this paper is that I don't find the problem setup inspiring. In particular, the only worked out examples are in Section 4. The novel and interesting piece seems to be the definition of kl^-1, but I find the study to be thin. To sum everything up, I think the derived results appear to be correct; there is some novelty in proofs; but the setup of the problem is not well motivated and it is not clear how these results may be used to derive intuition or practical algorithms. ", "questions": "* As one example I can think of: can you say anything about balancing false positive rate and false negative rate in a binary classification? \n\n* In particular, can you probably make any connections with the fairness literature where the goal might be to equalize false positive rate and false negative rate?", "limitations": "As it currently stands, the impact of the paper is not well quantifiable.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n* The paper is clearly written and the theoretical derivations are clearly discussed\n\n* Theorem 3 extends the existing results in the literature, and the proof requires some nice extension of existing results including Lemma 5.\n\n* Corollary 7 is also a nice extension of the existing results. While I did not follow its proof closely, the form of the result appears to be meaningful.\n\n* The new results motivate some new study, including a new definition of kl^-1 that seems to be interesting.\n\nWeaknesses:\n\n* The setup of the problem is not well motivated, and the study has not resulted in deriving new intuitions.\n\n* The new definition of kl^-1 is not well motivated and the details around it are thin.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QyLgW4_I7BF", "reviewer": "Reviewer_pSUq", "summary": "The paper deals with multi-class classification with a vector of $M$ possible error types. The paper establishes a PAC-Bayes bound for the convergence of the empirical error vector to the expected one,  under some convex distance measure (Thm. 3), and gives a more explicit bound for the kl-measure between the Multininomial distributions parametrized by those two corresponding vectors (Cor. 7). Finally, the paper discusses how the result of Cor.7 can yield a bound for the individual error types, and how to derive a gradient-based algorithm that minimizes the bound.\n", "questions": "1. \nLine 170 -  I didn’t understand the comment about $m’$. How is the formulation with $\\beta$ more general?\n", "limitations": "No further limitations ", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n1. The problem of multi-class generalization bounds for the confusion matrix is interesting.\n2. The main results (Thm. 3, Cor. 7) seem elegant and non-trivial to derive. \n\n### Weaknesses\n\n1. The writing can be improved - for example - paragraph 38-48 is hard to follow, The structure of the paper can be improved, currently, the main contributions are hard to discern from smaller details.\n\n2. Classical PAC-Bayes bounds (e.g. Maurer ‘04) can account for non-zero-one losses.  An alternative route to deriving bounds on the divergence of the empirical confusion matrix from the expected one, under some matrix norm, can be using those classical bounds for each error type and then using the union bound. How does this simple approach compares to the results in the paper?  I think the paper lacks comparisons to possible simpler approaches.\n\n3. In the introduction, the authors describe a problem where each error type is associated with a different loss value $\\ell_j \\in [0, \\infty)$. However, if am not mistaken, the bound presented in Thm 3. and Cor. 7 seem to only deal with $\\ell_j \\in {0,1}$.\n\n4. There are also no explicit results for the convergence of the confusion matrix under some matrix norms.\nI may have not understood correctly the results, in that case, I suggest the authors improve the clarity of these issues, by emphasizing the corresponding formulations and results. \n\n5. There is no experimental validation for the suggested algorithm and for the bounds.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4erNs1LSu0w", "reviewer": "Reviewer_9zyv", "summary": "The paper studies the PAC-Bayes generalization bound, which is an important topic and has been successfully applied to produce non-vacuous generalization bounds for neural network. The authors extend the existing results to the multiclass setting by introducing the discretized error types, which is a disjoint partition of the assembly of model prediction and ground truth labels. Based on the results, the authors further provide an abstract implementation of the method which can be applied to the real tasks.", "questions": "Although the discretized error types can be arbitrary in the theorem, are there any suggestions to set this parameter in the real tasks?\n\nCan you make more detailed discussion about your results that whether they are vacuous or not?\n", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1.The derived theorems hold for multiclass problem and soft labels, which has a wide range of applications to the real learning tasks. Such results in the PAC-Bayes literature have not been well-studied yet.\n\n2.Although there are no empirical studies to validate the results, the authors provide abstract implementation of the algorithm for better understanding the applications of the theorems.\n\n3.The paper is well presented and easy to understand. Detailed proofs are provided in the paper and supplementary material. \n\nWeakness:\n\n1.The technical contribution is somewhat weak in my view. The authors leverage the discretized error types to incorporate the entire confusion matrix, but many steps of the proofs mainly follow existing results.\n\n2.For the minor problems, there are some flaws in the paper, e.g., incorrect citations in L13 in the paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject