Chebyshev-Cantelli PAC-Bayes-Bennett Inequality for the Weighted Majority Vote
Authors: Yi-Shan Wu
Andres R Masegosa
Stephan Sloth Lorenzen
Christian Igel
Yevgeny Seldin
Venue: NeurIPS 2021 Poster (2021)
Keywords: Weighted Majority Vote
PAC-Bayes
Learning Theory

Abstract: We present a new second-order oracle bound for the expected risk of a weighted majority vote. The bound is based on a novel parametric form of the Chebyshev-Cantelli inequality (a.k.a. one-sided Chebyshev’s), which is amenable to efficient minimization. The new form resolves the optimization challenge faced by prior oracle bounds based on the Chebyshev-Cantelli inequality, the C-bounds [Germain et al., 2015], and, at the same time, it improves on the oracle bound based on second order Markov’s inequality introduced by Masegosa et al. [2020]. We also derive a new concentration of measure inequality, which we name PAC-Bayes-Bennett, since it combines PAC-Bayesian bounding with Bennett’s inequality. We use it for empirical estimation of the oracle bound. The PAC-Bayes-Bennett inequality improves on the PAC-Bayes-Bernstein inequality of Seldin et al. [2012]. We provide an empirical evaluation demonstrating that the new bounds can improve on the work of Masegosa et al. [2020]. Both the parametric form of the Chebyshev-Cantelli inequality and the PAC-Bayes-Bennett inequality may be of independent interest for the study of concentration of measure in other domains.

Chebyshev-Cantelit PAC-Bayes-Bennett Inequality for the Weighted Majority Vote
Yi-Shan Wu University of Copenhagen yswuōdi ku.
Andrés R. Masegosa
Stephan Lorenzen University of Copenhagen lorenzen@di. ku. dk
University of Aalborg arma@cs aau.
Christian Igel University of Copenhagen igel@di. ku.dk
Yevgeny Seldin University of Copenhagen seldin&di ku. dk
Abstract
We present a new second-orde oracle bound for the expected risk of a weighted majority vote. The bound is based on novel parametric form of the Chebyshey- Cantelli inequality (a.k.a. one-sided Chebyshev's s), which is amenable to efficient minimization. The new form resolves the optimization challenge faced by prior oracle bounds based on the Chebyshev-Canter et al. 2015), and, the same time, it improves the oracle bound based on second order Markov's inequality introduced by Masegosa et al. [020]. We also derive new concentration measure inequality, which we name PAC-Bayes-Bent Bennett,, since it combines PAC-Bayesiee bounding with Bennett's 's inequality. We use it for empirical estimation of the oracle bound. The BLCC--Byes-BBnneee
inequality, the C-bounds [Germain
inequality
improves on the PAC-Bayes-Bernen Bernstein inequality of [Seldin et al.) [2012]. We provide an empirical evaluation demonstrating that the new bounds can improve on the work of Masegosa et al. [2020). Both the parametric form of the Chebyshev- Cantelli inequality and the PAC-Bayes-Bern -Benett inequality may be of independent interest for the study of concentration of measure in other domains.
Introduction
Weighted majority vote is a central technique for combining predictions of multiple classifiers. an integral part of random forests [Breiman] 1996 200T], boosting [Freund and Schapire 1996), gradient boosting [Friedman 1999 2001 Mason et al. 1999 Chen and Guestrin|[0166] and it also used combine predictions of heterogeneous classifiers. is part of the winning strategies in many machine learning competitions. The power of the majority vote is in the cancellation of errors effect: when the errors of individual classifiers are independent anticorrelated and the error probability of individual classifiers is smaller than 0.5, then the errors average out and the majority vote tends to outperform the individual classifiers.
Generalization bounds for weighted majority vote and theoretically searetically-grouneeedd approaches to weight- tuning decades-old research topics. [Berend and Kontorovich (2016) derived an optimal solution under the assumption of known error rates and independence of errors of individual classifiers, but neither of the two assumptions is typically satisfied in practice.
In absence of the independence assumption, the most basic result the first order oracle bound, which is based Markov's 's inequality and bounds the expected loss of p-weighted majority vote by twice the p-weighted average of expected losses of the individual classifiers. This finding so old and basic that Langford and Shawe- Taylor (202 call it "the folk theorem". The p-weigtted average
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

of the expected losses is then bounded using PAC- MaC--Baesian bounds, turning the oracle bound into an
empirical bound [McAllester, 1998, Seeger 2002 Langford and Shawe-Taay Taylor 2002]. While the translation from oracle to empirical bound is quite tight [Germain et al. 2009 Thiemann et al. 2017]. the first order oracle bound ignores the correlation of errors, which is the main power of the majority vote. As a result, its minimization overconcentraaes the weights on the best-performing classifiers, effectively reducing the majority vote to a very few or even juenjust a single best classifier, which leads to significant deterioration of the test error on held-out data [Lorenzen et al. 2019 Masegosa et al. 2020].
In order to take correlation of errors into account, Lacasse et al. 2007] derived second order oracle inequality. The ideas were further developed by Laviolette et al. [20TT. Germain et al. (2013), and Laviolette et al.] [2017). However, they were only able to optimize the bounds in the highly restrictive setting of binary classification with self-commlemmented sets of classifiers and aligned priors and posteriors [Germain et al.) 2015). Several follow-up works resorted minimization of heuristic surrogates rather than the bound itself [Bauvin] al., 2020 Viallard et al. 2021]. Furthermore, second order oracle quantities in the denominator of
bounds, the C-bounds, which are based on the Meeeysshe--Cante
the oracle bounds lead to looseness in their translation to empirical bounds [Lorenzen et al. 2019
Masegosa et al. [2020] proposed an alternative second-order oracle bound, the tandem bound, based on second order Markov's inequality. While the second order Markov's ' inequality weaker than the Chebyshev- Chebyshev-Cantelli inequality, the resulting bound has no oracle quantities in the denominator, which allows tight translation to an empirical bound. Additionally, Masegosa et al.) proposed an efficient procedure for minimization of their empirical bound. They have shown that minimization of the empirical bound does not lead to deterioration of the test error.
Our work can be seen as a bridge between the tandem bound and the C-bounds, and as an improvement inequality, which preserves
of both. The key novelty a new parametric form of Chebyshev-Canter but avoids oracle quantities in the denominator. This allows both
the tightness of Chebyshev-Cantell efficient translation to empirical bounds and efficient minimization. We derive two new second order oracle bounds based on the new inequality, one using the tandem loss and the other using the tandem loss with an offset. For empirical estimation of the latter we derive PAC-Bayes-Booe Beneett inequality. The overall contributions can be summarized as follows:
1. We propose new parametric form of the Chebyshey- Cantelll inequality. which has no variance in the denominator and preserves tightness of the original bound. The new form allows efficient minimization and empirical estimation.
2. We propose two new second order oracle bounds for the weighted majority vote based on the new form of the Chebyshev-Came -aantelll inequality. The bounds have two advantages: (1) they are amenable tight translation to empirical bounds; and (2) the resulting empirical bounds are amenable to efficient minimization.
3. We derive new concentration of measure inequality, which name the SCC--Byes-BBenen inequality. It improves on the PAC-Bayes -Bressennnnntinn inequality of Seeldin et al. (0012). We use the inequality for bounding the tandem loss with an offset.
2 Problem setup
The problem setup and notations are borrowed from Masegosa et al. 2020
Multiclass classification. We let S {(X1, Yi)...., (X,,, Y.)) be an independent identically distributed sample from X' x y, drawn according to an unknown distribution D, where 3 is finite and X' is arbitrary. A hypothesis is function h X - y, and H denotes a space of hypotheses. We evaluate the quality of h using the zero-one loss ((h(X), Y) = 1(((X) * Y), where 1(-) is the indicator function. The expected loss of is denoted by L(h) = (EXXY) (((h(X), Y)] and the
empirical loss of h on a sample S of size n is denoted by [h,, S) = - ((h(X,), Y!).
Randomized classifiers. A randomized classifier (a. Gibbs classifier) associated with distri- bution p on H. for each input randomly draws a hypothesis h E H according to p and predicts h(X). The expected loss of a randomized classifier is given by Ex (h)) and the empirical loss by

---

Masegosa al. have shown the (h,,, S)]. To simplify the notation we use Ep[-] as shorthand for E(x,y)-ml and Epp.] as shorthand for -.
Ensemble classifiers and majority vote. Ensemble classifiers predict by taking a weighted ag- gregation of predictions by hypotheses from H. The p-weighted majority vote MV, predicts MV,(X8 arg maxyey (k(()) = y)], where ties can be resolved arbitrarily.
3 A review of prior first and second order oracle bounds
If majority voting makes an error, we know that at least p-weighted half of the classifiers have made an error and, therefore, {(MV (MVVV(X) (X),Y) S (E, (((() + Y)] > 0.5). This observation leads to the well-known first order oracle bound for the loss of weighted majority vote.
Theorem (First Order Oracle Bound). L(MV,) S 2T.(T(()).
Proof. We have L(MV2) = ED[ ( (X), Y)] < (I + Y)] 2 0.5). By applying
Markov's inequality to random variable Z = E, (h(() + Y)] we have:
L(MV,) S P(E,[ # Y)] 2 0.5) [E (1)()) + Y)]] 2E, (L()]]
PAC- BAC-Bayesian analysis can be used to bound [p[[(() in Theorem in terms of E, (L S)], thus turning the oracle bound into empirical one. The disadvantage of the first order approach is that [p]] ignores correlations of predictions, which the main power of the majority vote.
Masegosa et al. [2220] have used second order Markov's 's inequality, by which for non-negative random variable and
2
PPZ =)= =)
For pairs of hypotheses h and h' they have defined the tandem loss ((X),) ( * (X) + ((((X) # Y))( # Y). also termed joint error by Lacasse al. 2007], which counts an error only if both and h err on sample (X, Y). The corresponding expected tandem loss defined by
L(h, = [M[[(((() # Y))(M(()) Y)).
Lacasse al. 2007 and Masegosa et al. 2020 have shown that expectation second moment of the weighted loss equals expectation of the tandem loss. Using o² as a shorthand for the product distribution p x over H. H and E,, [T, k()) as a shorthand for E [L(h, 1/),, the result is the following.
Lemma Masegosa et al. 2020). In multiclass classification
Ep (A(X)) # Y)
By combining second order Markov's inequality with Lemma following result.
Theorem (Masegosa et al. 2020). In multiclass classification
L(MV,) - (C,,,)((hhh)))
Lacasse et al. (2007) have used the Chehyshev-Cantelly inequality to derive a different form of second order oracle bound. We use V [2) to denote the variance of random variable in the statement of Brebyshev-Cantelle inequality.
Theorem 4 (Chebyshev-Camm) inequality). For
LZ
P(Z - 2
Theorem 4 together with Lemma leads to the following result, known the C-bound.

---

Theorem 5 Lacasse et al. 2007 Masegosa et al. 2020 Ef -
then
L(MV)) ,) s 2 (L -
E,
B [L (1,,)))))))))))) E,((A))
Masegosa et al. have shown that the Chebyshev- Canttelll inequality always at least as tight as second order Markov's inequality (below provide alternative and more intuitive proof of this fact) and. therefore, the oracle bound in Theorem 5 is always at least as tight as the oracle bound in Theorem 3 However, the presence of E (L, h') and E, [4)]] in the denominator make empirical estimation and optimization the bound in Theorem impractical, and Theorem 3 was the only practically applicable second order bound far.
4 Main Contributions
We present three main contributions: (1) a new form of the Geebyshev-Cantell. inequality, which is convenient for optimization; (2) an application of the inequality to the analysis of weighted majority vote; and (3) JACC-Baye--Bentnn Bennett inequality, which is used to bound the risk with an offset in the bound for weighted majority vote. We start with the new form of Chebyshev-Cante which can be seen as refinement of second order Markov's inequality or as an intermediate step in the proof of the Seabysshe-Canntelee inequality.
inequality,
Theorem 6. For any E > 0 and all μ
E (Z 2)²
PP 2 E)
(5 11)2
Proof.
(Z 11)
P(Z = P(Z - 22 - S P((Z - 4)2 2 (s =1)) S
(8 11)2
The inequality can also be written as
E (Z 1)2
E 2
2pIEE [2] + p.²
PZZZ 2 E) <
(I)
(5 11)2
(e 12)
The bound is minimized by 1 E |Z|
E-B which can be verified by taking a derivative of the bound with respect to μ.. Note that дt can take negative values. Substitution of μ² into the bound and simple algebraic manipulations recover the Seobysshe--anntell inequality, whereas
= 0 recovers second order Markov's 's inequality. The main advantage of Theorem 6 over the Seooyshev-Cantelle inequality is ease of estimation and optimization due absence of the variance term in the denominator.
Equation 1 leads two new second order oracle bounds for the weighted majority vote, given in
Theorems 7 and g
Theorem 7. In multiclass classification, for all and all < 0.5
L(MV,) < Ex [E, h²)] - 2nd [Lh)] + (0.5 1r)²
Proof. As in the previous section, we take - [h((X + Y)], so that L(MV,) P 2 0.5). The result follows by (T) and the calculations of [za] and E [Z] from the previous section. Note that the result is deterministic statement.
For = 0, Theorem recovers Theorem 3 but if 1== [() - B (LAA)))
0.5-E,[((A) + 0, then substitution of n² into the theorem yields fighter oracle bound. At the same time, substitution of μ² recovers Theorem 5 but the great advantage of TheoremmZis that the bound allows easy empirical
estimation and optimization with respect to p. due to absence of Ex [L At') and [b))( in the

---

denominator. Thus, Theorem has the oracle tightness of Theorem 5 and the case of estimation and optimization of Theorem 3 The oracle quantities LL, h') h\) and [p]L(h) can be bounded using PAC-Bayes-kl or PAC-Bayes-X inequalities, as discussed in the next section.
In order to present the second oracle bound we introduce a new quantity. For pair of hypotheses h and h' and a constant μ4, we define tandem loss with p-offsstt for brevity p-tandem loss, as ('))))
(1(h(X) * Y) (1 (X) # Y) pt).
(2)
Note that it can take negative values. We denote expectation by
1 (h) = ( (X), Y]] = (D((1(h(X) # Y) (1 * p1].
With Z E, (1((1)(())))))))))))) * Y) before, we have
E (Z - / ED (EE #Y) - =)))
[EppEE(((((C)) * ()(1 * m)]] 14214
Now present our second oracle bound. Theorem 8. In multiclass classification, for all p and all μ < 0.5
L(MV,) S E2 (b,
(0.5 nn)
Proof. The result follows by Theorem 6 and the calculation above. Note that the inequality is deterministic statement.
In order to discuss the advantage of Theorem g
define the variance of the fı-tandem loss
Vu h²)= Ed ((((((((X)) * Y) () Y - μ1) (h, h²))²
If the variance of the j-tanddmm loss is small, we can use Bernstein-type inequalities to obtain tighter
estimates compared to kl-rype inequalities.
We bound the y-tandem loss using our next contribution, the PAC-Bayes Ne--Bayy--Benettt Bennett inequality, which improves the PAC-Bayes- BeCBBayes-Bernttei inequality derived by (Seldin et al. (2012) and may be of independent interest. The inequality holds for any loss function with bounded length of the range, we use and matching milke- quantities to distinguish it from the zero-one loss f. We let [hh) = Ep (E]((((()) Y)] and V(h) = [(((((()
[ be the expected tilde-loss of and its variance and let Lh, S) = ET ((h(X,,, Y;) be the empirical tilde-loss of on a sample S.
Theorem (PAC-Bayes Bayes-Bennettt Bennett inequality). Let E(-.-) be an arbitrary loss function taking values an interval of length b, and assume that (l) is finite for all h. Let (b()) =
Then for any distribution a on H that is independent of S and any >> 0 and 8 (0. 1), with probability at least 1 - over a random draw of S. for all distributions p on H. simultaneously:
((7)) E. VAN) KL(pl(T) Im
Bp(ī((N)] S (. $) +
702
yn
The proof is based on change of measure argument combined with Bennett's inequality. the details are provided in Appendix A Note that the result holds for a fixed (but arbitrary) > >> 0. In case of optimization with respect to y union bound has to be applied. For a fixed p the bound is convex in y and for fixed y it is convex in p. although it is not necessarily jointly convex in p and inequality is identical to the PAC-Bayes-Bernsteen inequality of Seldin et al. 20122 Theorem 7]. except that in the latter the coefficient in front of E.P [h]] is (e 2)y instead of @(xb)
See Appendix D for optimization details. The CC--Baes-Bennee
76 The result improves on the result of
Seldin et al. in two ways. First, in the result of Seldin et al. y is restricted to the (0, 1/b] interval, whereas in result is unrestricted from above. And second, we can rewrite the coefficient in front of the variance as
Φ(>6) Φ(>b)
7 ? where .(pb)
728e is a monotonically increasing function of 7, which in d(>b)
700
the interval 7 E (0, 1/b satisfies lim,-s y2 2 and for 7 1/b / it gives d(*b) = (e - 2). Thus,
7*b2
and, at the same time, for < 1/b it improves the constant coefficient in front of the variance from (e - 2) ~ 0.72 down to 0.5 for 7 + O. For y > 1/b PAC-Bayes-Benn Bennett also improves on PAC-Bayes- CCC--Byys-Beensttee Bernstein, because PAC-Bayes Bernsteei uses the suboptimal value 7 1/b dictated by its restricted range of 7.
PAC- PAC-Bayes-Bennets is always at least as tight as CCC-Bayes-Bernsterr
5

---

From oracle to empirical bounds
We obtain empirical bounds on the oracle quantities Egp (L,, k(] and [p][(h)] in Theorem 7 and Eg² (e,[L, I[] Theorem by using PAC-Bayesian inequalities. The empirical counterpart of the expected tandem loss is the empirical tandem loss
L(,,
( (X)) (X))
For bounding E,a (h, h²)] and [n]]( we use either PAC-Bayes-kl or PAC-Bayes-A inequalities, both cited below. We use (pl(T( to denote the Kullback-Leibler divergence between distribu- tions and π on H and kl(pl]q) to denote the Kullback-Leibe divergence between two Bernoulli distributions with biases p and q.
Theorem 10 (PAC-Bayes-kl Inequality, Seeger 2002 Maurer 2004). For any probability distribution on H that is independent of S and any ò E (0, 1), with probability at least 1 5 over random
draw of a sample S. for all distributions p on H simuhaaneousl:
KL(p]()) In(2/n/6)
kl E (E, S)
Ep ( [L(()))) <
(3)
n
Theorem 11 (PAC-Bayes-X Inequality, Thiemann et al. 2017 Masegosa et al., 2020). For any
probability distribution π on H. that is independent of S and any E (0. 1), with probability at least 1 over random draw of a sample S, for all distributions p on H and all X E (0, 2) and y simultaneously:
Ep(i(h, 8)]
KT(p](=) ln(2v775))
Ep [b(1))
+
(4)
1 1-
A A 2)
Ep [L(h)] 2 (1- 2) Ep(i(h, kL(pI(T) +
(S)
7m
(The upper bound (4) is due to Thiemann et al. [017 and the lower bound (5) is due to Masegosa et al. [2020), and the two bounds hold simultaneously.) The PAC-Bayes-X inequality an optimization- friendly relaxation of the PAC-Bayes-kl inequality. Therefore, for optimization of we use the PAC- Bayes-A inequality, the upper bound for E,- [L h(]] and the lower or upper bound for E [b)). depending on the positiveness of but once we have converged to a solution we use PAC-Bayes-ki to compute the final bound. The kl form provides both an upper and a lower bound through the upper and lower inverse of the kl Taking the oracle bound from Theorem 7 and bounding the oracle quantities using Theorem I1 we obtain the following result.
Theorem 12. For any distribution x on H that is independent of S, and any E (0,1), with probability least - ô over a random draw of S, for all distributions p H. and all μ. X and ? in the ranges specified below simultaneously, we have:
For [0,0.5), XE (0, and O:
E [L Ni, S)] 2 (KI((p|(T) + In(4/n/8)
L(MV,) 5 (0.5 - 22
A ((1 (1-22) 2)) n 24 ((1 RD)REol [.(, KL(p + In(4 +n(Av//)))
1-
+ +123
y
provide alternative ways of direct minimization the upper bound on E,, L (1) given by the upper inverse of kl in the PAC- MAC-Bayes-kl bound. We use the MAC-Bayes-A relaxation due to its simplicity, and because it provides an easy way of simultaneous optimization of an upper bound on E (h, (h,h') h')] and lower upper bound on E [h)) (depending on μ).
Reeb al. 2018 and Letarte et al.
2019

---

. For < 0, E (0, and y E (0,
p [h, N.S)
2KL(p + In(4v7/6)
L(MV,) < (0.5 n1)
X1 - })) n
[h,
KL [T) + Im(4/7/6) 7 (1 - n
2p 1
n²²
Proof. The result follows by substitution of the upper bound (4) on Bpa (h, h²)] and the lower bound (5) on [p[L(h)] in the case of positive μ.. or the upper bound 4 E, (h)) in the case of negative μu, into Theorem 7 We note that (L(p²(x>?) 814], which gives the factor 2 in front of the first KL term. The factor 4 the logarithms comes from union bound over the bounds on E,p (h, h')] and [p[L(h)].
2 (L(pl Germain al. 2015 Page
We note that both the loss and the tandem loss are Bernoulli random variables, and for Bernoulli random variables the PAC-Bayes-kl inequality is tighter than the PAC-Bayes-Benner (Tolstikhin and Seldin 2013). However, the empirical counterpart of the expected j-tandem loss is the empirical ju-tandem loss
1 n = 72 Σ (1(x).) -1) Y,) 11),
and the je-tandem losses are not Bernoulli. Therefore, we use the BLC-BByes-Bennceee inequality, which provides an advantage if the variance of the j-ttandem losses happens to be small. The expected and empirical variance of the y-tandem losses of a pair of hypotheses h and h are, respectively, defined by
+Y) Vn(,, ED((([(((X)) * - -) * - -4) - (,,,,
V (h, n (1()(x))) * Y;) ()(1 # Vi) - 14) [, N, ss)
The empirical variance V, (h, h', S) is an unbiased estimate of V h²).
Since the PAC- BLC--Baes-BBern inequality is stated in terms of the oracle variance E, [V(),, we use the result by Tolstikhin and Seldin [2013] Equation (15)] to bound it in terms of the empirical variance. For general loss function ((. (not necessarily within [0, 1)) we define the empirical variance of the loss of h by (h, S) - Σm (((((X)) Y)) =(h))². We recall that L, V. and i were defined above Theorem 9 We note that the result Tolstikhinn and Seldin assumes that the losses are bounded the [0, interval. Rescaling to general range introduces the squared range factor e² in front of the last term in the inequality below, since scaling a random variable by scales the variance by c².
Theorem 13 Tolsstikhn and Seldin 2013). Let E(..)) be an arbitrary bounded loss function and let be the length of the loss range. Then for any distribution on H that is independent of S, any
X E (0, 2(n-1)), and any ê E (0, 1), with probability at least 1 - 5 over random draw of the sample 5, for all distributions p on H simultaneously:
E. S,, 2 (KL(pl(T) + In
(V()
2
nd
1)
We note that, similar to the Se--Bayy--Beneeee inequality, but in contrast to the PAC-Bayes-X inequality, the inequality above holds for a fixed value of X and in case optimization over a union bound has be applied.
The last thing that is left is to bound the length of the range of y-tandem losses defined in equation
7

---

Lemma 14. For < 0.5 we have that the length of the range of (x(s))))) is K2 = max 1 2p}.
proof is provided in Appendix we obtain the following result.
[ 'Taking together the results of Theorems 8 and Lemma 14
Theorem 15. For any parameter grid (71--.., The) and (Ai,-... Aka where i 0 for all and
A (0. (012()))) for all i, any distribution a on H that is independent of S, and any E (0, with probability at least 1 8 over a random draw of for all values of 0.5, all distributions on H. and all values of y and X in the parameter grid simultaneously:
(h, (KI(p + 22
1
L(MV,) -
(0.5 11)2
m
K (KL(OllTT) + In k2
k()Kμ) TK3
E
(1, (R,,
+
An
nd (1
An I(n-1)
2(p-1
Proof. The result follows by reverse substitution of the result of Lemma 14 into Theorem 13 then into Theorem 9 and finally into Theorem 8 Since KL(p²1|>²) = 2 (L((TTT) we have factor 2 in
front of the KL. terms. The factor Ax comes from union bound over the parameter grid and the bounds in Theorems [nand]3)
Experiments
We start with a simulated comparison of the oracle bounds and then present an empirical evaluation on real data, The python source code for replicating the experiments available Githut 2
Comparison of the oracle bounds
Figure [ depicts a comparison of the second order oracle bound based on the Chebyshev- Cantelli inequality (Theorems 5 7 and which, oracle bounds, are equivalent) and the second order oracle bound based on the second order Markov's inequality (Theorem We plot the ratio of the right hand side of the bound in Theorem (,
7 for the optimal value μ¹ = [h)](h)]
RHS- Thm? Thm33
0.96
to the value of the right hand side of the bound in Theorem 3 A simple calculation shows that if E,a (h,, WO] = ( then μ¹" 0,
RylLih, NCJ (5
0.5- (.6-F.IA.()))
0.1
0.72
which recovers the bound in Theorem 3 The line E,2 [.(h, = (..E,(((()) is shown in black in Fig- ure 1 We also note that [L(]2 < [L, h')] < E, [h)]. which defines the feasible region in Figure Whenever E,2 (Lh, k²) 0.5
0.46
0.2
0.74
the Chebyshev- Cantelli inequality provides an improvement over second order Markov's inequality. The region above the black line, where E,a [T. > 0.5 (T.h), ]. is the region of majority vote
0.1
0.2
0.3 [,(L()
0.4
0.00
Figure Theorem
vs. Theorem
3
high correlation of errors and in this yields little improvement over individual classifiers. In this region the first order oracle bound is tighter than the second order oracle bounds (see Appendix C.. The region below the black line, where E,2 [h, N')] < (L5), is the region low correlation of errors. In this region the second order oracle bounds are tighter than the first order oracle bound. Note that the potential for improvement below the black line is much higher than above it.
Empirical evaluation on real datasets
We studied the empirical performance of the bounds using standard random forest [Beimmnn 2001 and a combination of heterogeneous classifiers on subset of data sets from UCI and LibSVM

---

repositories (Dua and Grafi 2019 Chang and Lin 2011]. An overview of the data sets is given in Appendix E. The number of points varied from 3000 to 70000 with dimensions d < 1000. For each data set, we set aside 20% of the data for the test set Stest and used the remaining data S for ensemble construction, weight optimization and bound evaluation. We evaluate the classifiers and bounds obtained by minimizing the tandem bound TND [Masegosa et al. 2020, Theorem 9], which is the empirical bound on the oracle tandem bound in Theorem 3, the Chebyshev-Canted bound with TND empirical loss estimate bound CCTND (Theorem 12 and the Chebyshev-Canted Canteellll bound with Ce--Bayys-Bennetl loss estimate bound CCPBB (Theorem 15). We made 10 repetitions of each experiment.
Ensemble construction and minimization of the bounds. We follow the construction used by Masegosa et al. 2020]. The idea is to generate multiple random splits of the data set S into pairs of subsets 5 = Th U.. such that Tà, n S, = 0. Each hypothesis is trained on Th, and the empirical loss on St. provides an unbiased estimate of its expected loss. Note that the splits cannot depend on the data. For our experiments, we generate these splits by bagging, where out-of-bag (OOB) samples Sh, provide unbiased estimates of expected losses of individual hypotheses h. The resulting set of hypotheses produces an ensemble. As in the work of Masegosa et al.) two modifications are required to apply the bounds: the empirical losses (h, 5) in the bounds replaced by the validation losses Lhh, Sy), and the sample size n is replaced by the minimal validation size min; [S%] For pairs of hypotheses (h, h²), we take the overlaps of their validation sets S₁, n Sy to calculate an unbiased estimate of their tandem loss L(h, , h², Sp. (.Sw), ju-tandem loss (h, h², Sr n.S)), and the variance of the y-tandem loss (h, h', Sh. n Siz), which replaces the corresponding empirical losses in the bounds. The sample size is then replaced by ming,M [S), n S The details on bound minimization are provided in Appendix D
Optimizing weighted random forest. In the first experiment we compare TND, CCTND, and CCPBB bounds in the setting studied by Masegosa et al. (2020). We take 100 fully grown trees, use the Gini criterion for splitting, and consider vd features in each split. Figure 2a compares the loss of the random forest on Sueat using either uniform weighting Pu or optimized weighting pa found by minimization of the three bounds (we exclude the first order bound from the comparison, since it was shown by Masegosa et al.] that significantly deteriorates the test error of the ensemble). While CCTND often performs similar to TND, we find that optimizing using CCPBB often improves accuracy. Figure 2b compares the tightness of the optimized CCTND and CCPBB bounds to the optimized TND bound. The CCTND is generally comparable to TND, while CCPBB is consistently looser than TND, mainly due to the union bounds. The numerical values for the losses and the bounds can be found in Tables 2 and 3 in Appendix E.2
Ensembles with heterogeneous classifiers. In the second experiment, we consider ensembles of heterogeneous classifiers (Linear Discriminant Analysis, k-Nearest Neighbors, Decision Tree, Logistic Regression, and Gaussian Naive Bayes). A detailed description is provided in Appendix
Compared to random forests, the variation in performance of ensemble members larger here. Figure 2ggure2c/comee compares the ratio of the loss of the majority vote with optimized weighting to the loss of majority vote with uniform weighting on Stest for p² found by minimization of the first order bound (FO), TND, CCTND, and CCPBB. The numerical values are given in Table Appendix E.3 We observed that optimizing the FO tends to improve the ensemble accuracy in some cases but degrade in others. However, TND, CCTND, and CCPBB almost always improve the performance w.r.t. the uniform weighting. Table 5 also shows that choosing the best single hypothesis gives almost identical results as optimizing FO. Figure 2d compares the tightness of the CCTND and CCPBB bounds relative to the TND bound. The numerical values are given in Table in Appendix [.3 In this case, we have that CCTND is usually tighter than TND, while CCPBB is usually looser than TND due to the union bounds.
E.3
7 Discussion
We derived an optimization-frient form of the Chebyshev-Canter inequality and applied it to derive two new forms of second order oracle bounds for the weighted majority vote. The new oracle bounds
bridge between the C-bounds [Germain et al. 2015) and the tandem bound [Masegosa et al. 2020

---

Binary
Multiclass
Binary
Multiclase
L(MV S..l Saa)
1.2
BOUNDEP /NND
Ix OCTNDMPECTTD CCPBBMPGPPRR)
155
0.
1.2
0.8
BPiND POCTND in PCCPBB
SU Miniee
Phillang
Spiiee
ela
Aduli
Connectd
Slattl
Teacippa
Letter
Saltange
Scnsvrion
Usps
'MN
Falhon
Phisking
Spllie
la
Adall
Counei- 1-1
Shardle
Tendliit
Lotter
Sathwage
Senorrin
USPS
MNNTT
Fustion
(a)
(b)
Binary
Multiclss
Binary
Multieless
DoNy SLa//L Suu!
i OCTND
0.5
Pap pp Pep Re
Spdee
God-BtNA
Proedea
Dounect-
Shortle
Lottee
Baa bos
Usps
Mttter
SV Mauber
Phosiaun
Salter
Cork-
Muuls
Proliin
Coundrt
Shattle
Proeligts
Latter
Sptlowie
Smatcz
pry
Eathira
(c)
(d)
Figure 2: (a,b) Optimized weighted random forest. (c,d) Ensembles with heterogeneous clas- sifiers. The median, 25%, and 75% quantiles of: (a,c) the ratio ,(MV /LMV u. Stest) of the test loss of the majority vote with optimized weighting p² generated by TND, CCTND and CCPBB to the test loss of majority vote with uniform weighting, and (b.d) the ratio BOUND(p")) TND(PtND) of the CCTND and CCPBB bounds to the TND bound with the cor- responding optimized weighting. The plots are on a logarithmic seale. Values above represent degradation and values below represent improvement. Data sets with L(MV us Stest) 0 are left out (a,c).
and take the best of both: the tightness of the Chebyshev-Cantel Cantelll inequality and the optimization and estimation convenience of the tandem bound. We also derived the PAC-Bayee Bayes- Bayes-Bennettt Bennett inequality, Bernstein incquality of Seldin et al. [2012]
improving on the PAC- PAC-Bayes- B---as--rrntttiinn
Our paper opens several directions for future research. One of them is better treatment of parameter search in parametric bounds that would give tighter bounds than a union bound over grid. It would also be interesting to find other applications for the new form of Chebyshev- Cantelli inequality and the Be---ByyyeBBneeee inequality.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers, as well as Tim van Erven, Wouter Koolen, and Peter Grünwald for their constructive feedback, references, and for pointing out that there is no need in union
bound over a grid of μ in Thcorems 12 and 15 and that negative a in Theorem I2 requires a separate treatment.
This project has received funding from European Union's Horizon 2020 research and innovation pro- gramme under the Marie Sklodowska- Curie grant agreement No 199. YW and YS acknowledge support by the Independent Research Fund Denmark, grant number 0135-00259B. SSL acknowledges funding by the Danish Ministry of Education and Science, Digital Pilot Hub and Skylab Digital. CI acknowledges support by the Villum Foundation through the project Deep Learning and Remote Sens- ing for Unlocking Global Ecosystem Resource Dynamics (DeReFcc). AM is funded by the Spanish Ministry of Science, Innovation and Universities and by the regional government of Andalucía, grant numbers DID2019-106758GBBB0 and P20-00091, respectively, and by FEDER funds.
10

---

References
Baptiste Bauvin, Cécile Capponi, Sean-FFaacci Roy, and François Laviolette. Fast greedy c-bound minimization with guarantees. 2020.
Daniel Berend and Aryeh Kontorovich. A finite sample analysis of the naive Bayes classifier. Journal of Machine Learning Research, 2016.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymp- totic Theory of Independence. Oxford University Press, 2013.
Leo Breiman. Bagging predictors. Machine learning, 24(2), 1996.
Lco Breiman. Random forests. Machine learning, 45(1), 2001.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions Intelligent Systems and Technology, 2, 2011.
Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the International Conference on Knowledge Discovery and Data Mining (ACM SIGKDD), pages 785-794, 2016.
Robert M Corless, Gaston H Gonnet, David EG Hare, David Jeffrey, and Donald E Knuth, On the lambertw function. Advances in Computational mathematics, 5(1), 1996.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2019. http:////// uci. sccieddumll
Ciprian Florescu and Christian Igel. Resilient backpropagation (rprop) for batch-learning in tensorflow. In International Conference on Learning Representations (ICLR) Workshop. 2018.
Yoav Freund and Robert Schapire. Experiments with new boosting algorithm. In Proceedings of the International Conference on Machine Learning (ICML), 1996.
Jerome H. Friedman. Stochastic gradient boosting. Computational Statistics and Data Analysis, 38, 1999.
Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of Statistics, pages 1189-1232, 2001.
Pascal Germain, Alexandre Lacasse, François Laviolette, and Mario Marchand. PAC-Bayesian learning of linear classifiers. In Proceedings of the International Conference on Machine Learning (ICML), 2009.
Pascal Germain, Alexandre Lacasse, François Laviolette, Mario Marchand, and Jean-Francis Roy. Risk bounds for the majority vote: From a PAC-Bayesian analysis to a learning algorithm. Journal of Machine Learning Research, 16, 2015.
Christian Igel and Michael Hüsken. Empirical evaluation of the improved rprop learning algorithms. Neurocomputing, 50, 2003.
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. In Advances in Neural Information Processing Systems (NeurIPS), 2007.
John Langford and John Shawe-Taylor. PAC-Bayes & margins. In Advances in Neural Information Processing Systems (NeurIPS), 2002.
François Laviolette. Mario Marchand, and programs for majority votes. In Proceedings of the International Conference on Machine Learning (ICML), 2011.
Roy. From PAC-Bayes bounds to quadratic
François Laviolette, Emilie Morvant, Liva Ralaivola, and Jean-Francis Roy. Risk upper bounds for general ensemble methods with an application to multiclass classification. Neurocomputing, 219, 2017.

---

Gaël Letarte, Pascal Germain, Benjamin Guedj. and François Laviolette. Dichotomize and gener- alize: PAC-Bayesian binary activated deep neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Stephan Sloth Lorenzen, Christian Igel, and Yevgeny Seldin. On PAC-Bayesian bounds for random forests. Machine Learning. 2019.
Andrés R. Masegosa, Stephan S. Lorenzen, Christian Igel, and Yevgeny Seldin. Second order PAC- Bayesian bounds for the weighted majority vote. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean. Boosting algorithms as gradient descent. In Advances in Neural Information Processing Systems (NeurIPS), 1999.
Andreas Maurer. note on the PAC-Bayesian theorem. www.arxiv.org. 2004.
David McAllester. Some PAC-Bayesian theorems. In Proceedings of the Conference on Learning Theory (COLT), 1998.
David Reeb, Andreas Doerr, Sebastian Gerwinn, and Barbara Rakitsch. Learning gaussian pro- cesses by minimizing PAC- MAC-Bayesian generalization bounds. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Matthias Seeger. PAC-Bayesian generalization error bounds for Gaussian process classification. Journal of Machine Learning Research, 3, 2002.
Yevgeny Seldin, François Laviolette, Nicolò Cesa-Bianchi, John Shawe-Taylor, and Peter Auer. PAC-Bayesian inequalities for martingales. IEEE Transactions on Information Theory, 58, 2012.
Niklas Thiemann, Christian Igel, and Yevgeny Seldin. PAC-Bayesian aggregation without cross- 05610 2016.
validation. http://aazzi.oog/bbb////ee
Niklas Thiemann, Christian Igel, Olivier Wintenberger, and Yevgeny Seldin. A strongly quasiconvex PAC-Bayesian bound. In Proceedings of the International Conference on Algorithmic Learning Theory (ALT), 2017.
Ilya Tolstikhin and Yevgeny Seldin. PAC-Baye-EEmpirrca-Bennnn Bernsstein inequality, In Advances in Neural Information Processing Systems (NeurIPS), 2013.
Paul Viallard, Pascal Germain, Amaury Habrard, and Emilie Morvant. Self-bounding majority vote learning algorithms by the direct minimization of tight PAC-Bayesian C-bound. Proceedings of the European Conference Machine Learning and Principles and Practice of Knowledge Discovery Databases (ECML PKDD), 2021.
12


Reviews:
[{"review_id": "vSTewFcpWzE", "reviewer": "Reviewer_hg22", "summary": "This paper addresses the problem of bounding the generalization error of weighted majority vote classifiers.  They begin with oracle-inequalities, and show how to convert them to inequalities in terms of fully empirical quantities, without substantially weakening the bounds. In particular, to bound to the 0-1 loss, they introduce an alternative to the Chebyshev-Cantelli inequality, which promises to be easier to optimize and apply than the $C$-bound.  Furthermore, to bound tandem losses they introduce a PAC-Bayes-Bennett inequality, which improves over the PAC-Bayes-Bernstein inequality in the manner one would expect.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThis paper addresses several concerns in the computation and optimization of bounds of this nature, in particular the Chebyshev-Cantelli bound. An issue I have is that, while the oracle-based PAC-Bayes inequalities operate nonuniformly over the entire space of possible reweightings in a manner that seems quite competitive with a union bound approach, once the oracles are dropped and fully empirical bounds are adopted, it seems that they do not beat a union-bound approach, except in very particular circumstances, which are not clearly outlined and do not seem reasonable to this reviewer. Furthermore, much of the work seems quite incremental; e.g., simply replacing Chebyshev-Cantelli with Chebyshev and Bernstein with Bennett.  Overall, while there are some interesting ideas and nice results, these issues detract from the work as a whole and don't leave me convinced of its utility. If the empirical bounds could be improved, and particularly if the grid over possible parameters could be removed with an argument that centers the grid over some true optimal parameterization, I would be inclined to change my opinion of this work.\n\n\nMy major issue is with the fully empirical inequalities 10 and 11.  The elegance, beauty, and utility of the PAC-Bayes inequalities is that they give a bound for all possible re-weighting simultaneously, without paying a union-bound type price in the numerator of $\\ln(1/\\delta)$.  An obvious (and obviously flawed) alternative would be to upper-bound all $d^2$ tandem losses simultaneously via the union bound, introducing $\\ln \\frac{d^{2}}{\\delta}$ terms.  Unfortunately in section 5, theorems 10 and 11, the lovely $\\ln \\frac{1}{\\delta}$ terms become $\\ln \\frac{\\sqrt{n}}{\\delta}$ terms. Direct comparison to the union bound is a bit difficult, since everything is still in terms of $\\lambda$ and $\\gamma$ variables, which must be optimized over, but with these sub-gamma and sub-Poisson inequalities, we should expect to see these logarithmic terms appear fast decaying range-based (non-square root) and slow decaying variance-based (square root) terms.\n\nI thus remain unconvinced that the results of this section beat the obvious union bound strategy, unless $n \\leq d^{4}$.  This analysis holds, even not accounting for the KL divergence terms, or the need to establish a grid, so it does tell us the size of the grid $k$ clearly must obey $k \\in o(d^{2}/\\sqrt{n})$.  Furthermore, since everything is inside a logarithm and presumably $n$ grows faster than $d$, it really seems like the benefit is negligible, and the cost is $O(\\log(n))$.\n\nIt would be very interesting to see a comparison to [1], which treats a similar problem with such a union bound approach, in particular comparing to their suggestion of using uniform convergence methods, i.e., Rademacher averages, to estimate appropriate statistics. \n\nSpecifics:\n\n\n\n\nAs I understand it, binary weighted majority vote is a type of linear classification, so why are methods for linear classification not compared against or discussed?\n\n35 Isn't it the lack of correlation of errors that gives the majority vote its power?\n\n75/76: Often $L$ is called risk, written $R$ to distinguish from $\\ell$, also called loss.\n\n89: Is $\\leq$ here just due to ties?\n\n104: $h$ on LHS is a weighted combination, $h$ on RHS is a random variable?\n\n165: Please specify that $\\pi$ is a distribution over voters (unless I’m wrong)?\n\n190: PAC-Bayes-kl -> PAC-Bayes-KL?\n\n196: I'm not sure it matters, but I feel like the $\\forall \\lambda, \\gamma$ should be before the “for all distributions simultaneously”. Also, do (4) and (5) hold individually with probability $1 - \\delta$, or simultaneously?\n\n202: $\\rho^{2}, \\pi^{2}$ are independent product distributions?\n\n\n\nTheorem 13 does appear to be based on a sub-gamma bound on the variance. I wonder if it would be possible to get a sub-Poisson bound on the variance? This would compose nicely with the sub-Poisson of the Bennett inequality; otherwise it seems to be a bottleneck?\n\n\nReferences:\n\n“Adversarial Multi Class Learning under Weak Supervision with Performance Guarantees,” Mazzetto, Alessio and Cousins, Cyrus and Sam, Dylan and Bach, Stephen H and Upfal, Eli\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "tatrylWgkj", "reviewer": "Reviewer_ViFo", "summary": "This paper worked on the analysis of the majority vote based on a second-order bound. The proposed analysis is based on the extension of the Chebyshev-Cantelli inequality, which uses the offset. The new bound is tighter or more optimization-friendly than the existing bound. With this new bound, the authors proposed a new majority vote algorithm and applied it to the random forest and heterogeneous classifiers. The numerical experiments support the usefulness of the proposed method especially when heterogeneous classifiers are used.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper provides a practical and rigorous extension for the analysis of the majority vote. I think this is good enough to publish.\n\n# Pros\n- The motivation and goal of this work are explicitly written in Section 1 and one can quickly understand why this work is important. Also, section 3 is well written concisely, and easy to follow for a non-expert. \n\n# Cons\n-  The algorithm for deriving the optimal $\\rho$,  which is required for numerical experiments,  is not shown even in Appendix. I thought the authors should summarize Appendix D into the algorithm.\n\n# Comments and Questions:\n- In Figure 1, around the area of $E_{\\rho}L(h) \\approx 0.5$ and $E_{\\rho ^2}L(h,h')  \\approx 0.5$, theorem 7 is tighter than theorem 3. I would like to know an intuition about this. That area means the high correlation of errors and each hypothesis does not work well since $E_{\\rho}L(h)\\approx 0.5$. Also, on the area, $E_{\\rho}L(h) = E_{\\rho ^2}L(h,h')$, theorem 7 seems tightest because it means the numerator of Theorem 5 is zero. What is the intuition of this case?\n\n- In Figure 2, in experiments a) and b), using the optimized $\\rho$ for a random forest model seems not to work well in all the methods (TND, C$\\mu$TND, COTND). On the other hand, the application to heterogeneous classifiers worked well. Why this happened and is this explainable from any existing or proposed bound ? Is this caused by the low correlations of errors of heterogeneous classifiers ?\n\n- In Figure 2, especially, c) and d), there are gaps regarding the behavior of loss and bound. For example, in splice experiments, in Fig c) COTND shows the smallest loss, while in Fig d) COTND shows the largest bound. The authors argued that this is caused by the union bound in the derivation. I would like to know the reason why this gap is caused in more detail.\n\n- This is just a minor comment, why author named the bound in Theorem 12 as C$\\mu$TND and the bound in Theorem 15 as COTND ? (abbreviation ?)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, they are shown in the checklist.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4  hours"}, "extra_text": {}}, {"review_id": "nBydXFyIRVQ", "reviewer": "Reviewer_AxQU", "summary": "This submission is about bounding the risk of the weighted majority vote classifier formed by aggregating the predictions of a set of base classifiers according to a certain weighting scheme (a distribution over hypotheses). It is motivated by the observation that previous bounds were loose or based on restrictive assumptions, and may not be convenient for optimization when they cannot be converted to empirical bounds that could be used as learning objectives in view of the fact that they depend on inaccessible oracle quantities.\n\nSpecifically, the submission proves a parametric version of the Chebyshev-Cantelly inequality (Theorem 6), which is used as the basis to develop bounds on the risk of the $\\rho$-weighted majority vote (Theorem 7, Theorem 8), where the upper bounds depend on the expected tandem loss of pairs of hypotheses chosen randomly according to $\\rho$ (case of Theorem 8) and additionally the expected loss of the randomized classifier that chooses single hypotheses randomly according to $\\rho$ (case of Theorem 7), besides depending on an optimizable parameter $\\mu$. The latter two expected losses (tandem and single) are then controlled by using PAC-Bayesian inequalities in order to convert the oracle bounds into empirical bounds. One such empirical bound (on the expected risk of the weighted majority vote),  given in Theorem 12, is developed from Theorem 7 when bounding the $\\rho$-expected losses (tandem and single) in terms of their empirical counterparts by means of the PAC-Bayes-$\\lambda$ inequalities. Another such empirical bound, given in Theorem 15, is developed from Theorem 8 when bounding the $\\rho$-expected loss (single) by a careful combination of building blocks, one key of which is a new inequality (Theorem 9) called PAC-Bayes-Bennett inequality, which is novel to the best of my knowledge, and is one of the main contributions of this submission.\n\nA very interesting feature of these new empirical bounds (Theorem 12 and Theorem 15) is that, besides being valid simultaneously for all \"posterior\" distributions $\\rho$ (as is typical in PAC-Bayes inequalities), they hold simultaneously (i.e. uniformly) over possible values of their parameters, which implies that the parameters can be selected by optimization without paying the classical union bound price. A set of experimental results then show the benefits of using the new bounds for learning weighted majority votes as well as computing bounds on their risk. The experiments also give comparisons of the new bounds to previous bounds in the relevant literature.", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "ORIGINALITY\n\nThe contributions of this submission are novel, to the best of my knowledge. The \"parametric Chebyshev-Cantelly\" (Theorem 6) has a surprisingly simple proof, I would be surprised if nobody had come across this inequality in any area of probability or mathematics (though it is possible), but in any case this inequality is used as the basis for deriving two novel oracle bounds for the risk of the weighted majority vote, hence there is novelty in its use, regardless of the inequality itself. Another novel contribution of this submission, as pointed above in my summary (and visibly emphasized in the abstract and other places) is the \"PAC-Bayes-Bennett\" inequality, which is an improvement on the \"PAC-Bayes-Bernstein\" inequality (and detailed analytical comparison between the two is given) and is the basis for converting an oracle bound into an empirical bound, besides possibly being interesting by itself.\n\nSIGNIFICANCE\n\nThe theoretical sections are interesting for the machine/statistical learning theory community, and the experimental demonstrations are additionally interesting for practitioners and anyone interested in machine learning with guarantees. There is sufficient informative discussion of the analytical properties of the contributed inequalities and the convenient properties of the new empirical bounds. The relevant literature is discussed and the previous works are cited with fair attributions. The section on experimental results demonstrates the improved tightness of the computed bounds with respect to previous related results (without compromising the test set errors as far as I understood), and the presentation of the experimental setting and discussion of results is overall a positive example that I would love to see followed by other works.\n\nCLARITY / QUALITY / READABILITY\n\nReading this paper was a pleasure. No exaggeration. I consider this submission to be a positive example of good scientific writing: the narrative is clear and grammatically correct mostly (minor blemishes pointed below), the material is organized in a coherent way so that following it required no unreasonable efforts, and the choice of mathematical presentation (notations, derivations) is likewise so that one can follow/verify the arguments without requiring unreasonable efforts; my compliments for this. The proofs look correct. Overall, this submission is high quality in my opinion.\n\nEDITORIAL FEEDBACK\n\nL.8: \"derive a new inequality that we call PAC-Bayes-Bennett inequality\"\nL.10: Replace \"by\" with \"of\"\nL.11: Replace \"by\" with \"of\"\n\nL.24-25: Replace \"weight tuning\" with \"tuning the weights\" (or with a hyphen \"weight-tuning\" I think?)\n\nL.38: \"held-out\"\n\nL.43: Is is possible to mention what are the restrictive settings? Say writing \"restrictive settings (e.g. [restriction 1] and [restriction 2])\" if space allows to mention them briefly.\nL.44: \"in their translation to\" (i.e. insert \"their\")\n\nL.66: \"We derive a new inequality that we name the PAC-Bayes-Bennet inequality, which [...]\"\nL.67: Replace \"by\" with \"of\"\n\nL.96: \"defined the \\emph{tandem loss}\" (i.e. insert \"the\")\n\nL.97: Preferably write \\emph{joint error} or \"joint error\" (in quotations) for emphasis\n\nL.109: \"the variance of a random variable $Z$\"\n\nL.137 (Theorem 7):  Should say \"In multiclass classification, for any $\\mu < 0.5$\" (I think)\n\nL.152 (Theorem 8): Same comment.\n\nL.155-156: \"we can use Bernstein-type inequalities [Seldin et al. 2012] to obtain tighter estimates compared to kl-type inequalities [Seeger 2002, see Theorem 10 below].\"\n\nL.168: \"fixed (but arbitrary) $\\gamma>0$\"\n\nL.172: Replace \"by\" with \"of\" (and same in L.173 and in L.175)\n\nL.197: Perhaps clarify after the theorem that the upper bound (4) is due to Thiemann et al. (2017), while the lower bound (5) follows by a similar argument as noted by Masegosa et al. (2020).\n\nTheorem 12: Should the $\\mu$ values in the grid be all $\\leq 0.5$? since the argument is based on Theorem 7, which requires $\\mu \\leq 0.5$ I think. Also, in the upper bound, replace the outermost parenthesis with square brackets for better visibility. The first KL in the upper bound has a factor of 2 that I am not sure where it comes from. If this is a typo, it's easy to correct (delete the factor 2). If this is no typo, it calls for commenting in the proof outline (L.208-210) why the factor 2 is present. The proof outline could me explicit saying that the \"result follows by substitution of the upper bound on E_{ρ^2} [L(h, h′)] and the lower bound on E_{ρ}[L(h)] given by Theorem 11 (namely, by (4) and (5), respectively) into Theorem 7\"\n\nL.212: Replace \"the\" with \"their\" and for clarity specify the possible range, for instance write \n\"their range (e.g. $0, 1$ vs. $-1, 1$) and expectation\"\n\nL.225-226: I suggest to reduce the last sentence to \"Rescaling to a general range introduces a new factor.\"\nThen state Theorem 13 and after the theorem statement comment on the new factor $c^2$.\n\nTheorem 13: \"with range c\" is ambiguous --- please clarify according to the intended meaning. By \"range\" I understand the set of possible values that this loss may take, but clarify if you mean something different.\n\nL.231: Since the PAC-Bayes-kl inequality does not involve any $\\gamma$ parameter, the meaning of \"in contrast to the PAC-Bayes-kl inequality\" is unclear.\n\nL.235: This use of the word \"range\" is unusual, could you clarify? \nThe set of possible values of the $\\mu$-tandem loss is { $\\mu^2$, $\\mu^2-\\mu$, $(1-\\mu)^2$ } and this is what I understand as range. These values are according to whether the losses of $h$ and $h'$ are both 0, or one is 0 while the other is 1, or both are 1.\nOn a quick look at Appendix B, it looks that you are conflating \"range\" (as I understand it) with \"length of the range\" so this needs to be sorted out. For instance, say if a function's range (in mathematical meaning) is the interval [1, 5], then this range has length 5-1 = 4. I think the quantity $K_{\\mu}$ in your Lemma 14 corresponds to \"length\" as just described.\n\nL.239 (Theorem 15): Give explicitly the restrictions (if any) on the $\\mu$'s and the $\\gamma$'s and the $\\lambda$'s. At least the $\\mu$'s should be restricted to be $\\leq 0.5$ I think.\n\nL.242-245: Please also comment on the factor 2 in front of the two KL terms in the bound. It is not clear to me why these factors 2 should be present, but feel free to convince me that these factors are correct. In case if these factors should not be present, I would request that the experimental results that rely on Theorem 15 should be revised. [Similarly, any experimental results relying on Theorem 12 should be revised if the factor 2 on the first KL should be removed. Double check to be sure.]\n\nL.311: Replace \"supplementary material\" with \"Appendix E\" (and do the same in L.316)\n\nL.324: Replace \"by\" with \"of\"\n\nL.326: \"search in parametric bounds, which would be cleaner and could give tighter values than a union bound over a grid\"\n\nOnly skimmed the appendices but am willing to look at the details in the appendices when we get there.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sure.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "V8rTCtoTXof", "reviewer": "Reviewer_Am83", "summary": " The paper aims at developing tools for analyzing majority-based  learners. It does this through the idea of oracle bounds. The central  and known idea, is to bound the error using the oracle error and then  bound the oracle error by a function of the empirical error. The authors  introduce new bounds for the two stages of the process, thereby  improving the known bounds in the field. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The article is well written. It is clear and well-organized. The results are presented in a sequential and properly constructed manner. In addition, the results are compared to previous results along the way, providing context and perspective. The practical implications of the theoretical results are also properly explained, and the experiments adequately illustrate this.\nOverall, the results appear effective and interesting. The improvement that these results achieve beyond those already known, is limited, but it exists. Additionally, the authors present tools that may be useful in other contexts or may produce additional results in the current field of research.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors indeed explain the limitations of the results and the regimes on which they do and do not obtain improvement over the current result in the area.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "QbQFJ3vz_x", "reviewer": "Reviewer_WkCd", "summary": "This paper provides new second order oracle bounds for the weighted majority vote classifier. The classical second order bounds (C-bound) has a variance term in the denominator which makes it harder to estimate and optimize the term empirically. Recently, a different second order bound was proposed which did not have these issues and was thus, easier to optimize and estimate but is somewhat looser compared to the C-bound. This paper gives an intermediate bound which is tighter than the recent bound but also easier to optimize and estimate. This paper also provides a new concentration bound in the PAC Bayesian setting - PAC-Bayes-Bennett inequality to relate the term in the oracle bound to its empirical value.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The weighted majority vote is a very well used classifier and getting tight generalization bounds which can also be used to get better weighting schemes is important and would be relevant to other members of the community as well. \nThe bounds are the application of a different second order bound which in my opinion is novel. Although the application does not seem technically challenging, the results look promising to me and also lead to better performance experimentally which is interesting. \n\nThe paper is very well written and easy to follow. The comparison to previous works is very clear. \n\nI see that the optimized weightings are not compared to the C-bounds. The paper mentions that the optimization of that bound is hard but are there existing works which try to optimize based on these bounds and did the paper try to compare using those methods?\n\nOne thing is that the authors have not discussed the comparison of their two bounds. The authors note on line 300 that one of their bounds leads to better accuracy when the weights are optimized whereas the other bound leads to tighter generalization bound. This seems puzzling. Can the authors comment more on this observation? Also, do the authors have insight into which one of their bounds is better or worse under what conditions? I think it would be good to mention this in the paper to get a better understanding.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The referees are in agreement that this submission provides novel techniques for analyzing majority-based learners. It is very much within the conference scope and of sufficient interest and novelty. All of the referee objections have been addressed during the discussion phase.
Decision: Accept (Poster)