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 See--Byys--Benneee 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-grouneeddd 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 CCC--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 (h (h,,)))))))))))) E,((A))
Masegosa et al. have shown that the Chebyshev-Canee Canttellll 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-Canntelle 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 [Z] + 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 Theorem(7is 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 (.Ii((h))) $) +
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-Benne
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
Φ(>b) Φ(>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](=) 1n(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 R,)REol [.(, KL(p + In(4 +n(Av//)))
1-
+ +
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) + In(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 PAC-Bayes- Baanett 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) Vw(,, ED((([(((X)) * - -) * - -4) - (,,,,
V (h, n (1(M(X)) * Y;) () # Vi) - 14) [, 1. 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. ((12()))) 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? Thm3
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 [Beimman 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 Cantelllll bound with Ce--Bayys-Bennetl loss estimate bound CCPBB (Theorem 15p. 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 L(h, 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', Sy. 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 2ggure2cccomee 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
Ealhon
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
Lottoe
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-FFaaccs 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/////e
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": "j_tSwswTwv0", "reviewer": "Reviewer_R8qn", "summary": "This paper studies multiclass classification, one of the most elementary supervised PAC learning problems.\nThe main contribution is a new generalization bound for the weighted majority (with weights $\\rho$) which simultaneously:\n(1) leverages the fact that variance / centered 2nd moment of $\\rho$ can be much less than the non-central 2nd moment\n(2) gives a bound which can be readily estimated from samples", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "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": "This paper studies multiclass classification, one of the most elementary supervised PAC learning problems.\nThe learner receives labeled examples $(X_i,y_i)$ drawn from some distribution $D$, where $y$ takes discrete values.\nThe goal is to correctly predict the label $y$ of a freshly drawn sample $X$, according to the $0-1$ loss.\n\nOne of the basic techniques in supervised learning is to combine multiple hypotheses (i.e. classification rules) into a single one, ideally with higher accuracy than the hypotheses one started with.\nThe most basic way to do this is with a (weighted) majority vote.\n\nThis paper studies generalization bounds for weighted majority classifiers.\nThe main contribution is a new generalization bound for the weighted majority (with weights $\\rho$) which simultaneously:\n\n(1) leverages the fact that variance / centered 2nd moment of $\\rho$ can be much less than the non-central 2nd moment\n(2) gives a bound which can be readily estimated from samples\n\nPrior works giving generalization bounds for weighted-majority classifiers either give bounds with so-called \"oracle\" quantities in the denominator (meaning optimize with respect to $\\rho$ and/or to estimate from samples), or don't exploit the advantages of the variance over the raw 2nd moment.\n\nI am not very familiar with this area of learning theory, so my evaluation has very low confidence.\nHowever, it seems to me that this might be a technical follow-up to the paper Masegosa et al. 2020, which is heavily cited by the authors.\nIt is not clear to me if it will be of sufficiently broad interest for the NeurIPS audience.\nAt very least, the writing does not really make clear enough to me, a reasonable proxy for the average theory-literate NeurIPS audience member, why the results are very exciting.\nTheorems 6, 7, and 8 seem to be slight modifications of existing bounds, while the later bounds in the paper (especially in section 5) are quite complex and difficult to absorb.\n\nThat said, the paper seems to make progress on a very basic setting, and they do provide some nice experimental results.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theory paper with limited direct societal impact.\nTreatment of the limitations of the theory results is, however, somewhat slim.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "OUQZmFTFh10", "reviewer": "Reviewer_Paqn", "summary": "The paper proposes a Chebyshev-Cantelli oracle bound for the true error of a majority vote classifier, whose empirical PAC-Bayesian generalization bound is more amenable to optimization than the C-Bounds.\nThe obtained second-order bounds are based on the \\mu-tandem loss (the joint error with a \\mu margin/offset) and do not involve statistical quantities in the denominator which make the minimization of the classical PAC-Bayesian C-bounds unstable and loose. \n\nBy rewriting the oracle bound into two forms, the paper further proposes two different empirical bounds: one involves the variance of the \\mu-tandem loss and leverages an improved PAC-Bayesian-Bernstein inequality that is also derived in the paper (I haven't checked its derivation); the other involves the second and first moments of the error. \nIn practice, the empirical bounds are optimized by relaxing them via Thiemann's PAC-Bayes-\\lambda inequality.\nAn empirical comparison with the first order and [Masegosa]'s second order bounds is provided on several real datasets, using as set of base classifiers either a random forest or a set of heterogeneous classifiers (e.g. k-nn, decision tree).", "questions": "", "limitations": "", "rating": 5, "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": "a. The paper is well written and overall easy to follow. All assumptions are well stated and proofs of the main theorems are provided. \nThe contributions and scope of the paper are clearly provided in the abstract and introduction.\n\nb. An unclear point of the work is its novelty w.r.t. margin-based oracle bounds. As clearly stated, this work builds upon [Masegosa] as it proposes a relaxed form of the tandem loss (or joint error, the parabole upper bounding the 0-1 loss). An additional parameter \\mu is included, which is the margin/offset of the loss that recenters the parabole in \\mu (instead of 0) and adapts its slope, and for which a theoretical optimal value exists. However, the literature on margin/offset losses, such as the work in [Laviolette], is never discussed in the paper, which makes it hard to judge the novelty of the contributions.\n\nc. The empirical evaluation shows no significant difference between [Masegosa]'s test error and the test errors obtained by the two bounds proposed in the paper (see Tables in the appendix and Minors 1 in the review) and in most datasets the generalization bounds degrade (Figure 1 of appendix). Moreover they don't allow to obtain guarantees that are better than the ones obtained through the first order bound (Table E3, E5). \nIn this sense, the paper provides little insight into why the empirical results do not improve at least upon [Masegosa]'s ones.\nIt could be a problem of having to deal with too many hyper-parameters (\\mu, \\lambda, \\gamma) when optimizing the PAC-Bayesian bounds (see Minor 2 for a suggestion of alternative optimization) or also a problem due to the choice of base classifiers.\nIndeed, Figure 1 (on the theoretical improvement of the bound with varying \\mu) is very interesting, and it suggests that the most improvement should be achieved when errors made by the base classifiers are decorrelated. \nHence, it would be interesting to study the obtained performance with varying degree of correlation between classifier predictions. \nFor instance, following [Lorenzen], one could study the tightness of the bounds as a function of the strengths of the voters, e.g. training decision trees with bounded maximal depth. For weaker classifiers, one would expect to obtain better guarantees with the proposed bounds than with the first order and [Masegosa]'s ones.\n\n## Minors\n1. In the tables, standard deviations are reported but are not used to determine the significance of the differences between performance. The best results should not be determined only based on the averages. In the same line, using a log scale in Figure 2 makes it hard to compare the scale of improvement vs degradation, as the former is magnified.\n\n2. A limitation of the work is its dependence on several parameters (\\mu, \\lambda, \\gamma) for the optimization of its empirical bounds, which makes the algorithm heavy and the bounds looser. A suggestion for improving on this point would be to optimize the empirical bound of Theorem 10 directly, by evaluating the kl inverse via the bisection method as done in [Reeb].\n\n3. The paragraph in lines 173-181, about the comparison of the bound of Theorem 9 with the bound of [Seldin 2012], is confusing. Isn't simply (e-2) \\gamma tighter than \\frac{\\phi(\\gamma bi)}{\\gamma b^2}  for \\gamma > 1/b and loser otherwise? Also, it should be explained why Seldin's result is applicable only to upper bounded losses and for gamma < 1/b.\n\n## Recommendation\nI recommend a revision of the paper. I am willing to increase my score if novelty w.r.t. works on margin losses is clarified and more insightful empirical analyses are provided into the reasons why the derived bounds do not improve upon state-of-the-art second order bounds, even though the oracle bound is tighter.\n\n### References\n[Laviolette], et al: Risk upper bounds for general ensemble methods with an application to multiclass classification, Neurocomputing 2017\n\n[Lorenzen], et al:  On PAC-Bayesian bounds for random forests, Machine Learning 2019\n\n[Masegosa], et al: Second order PAC-Bayesian bounds for the weighted majority vote, NeurIPS 2020\n\n[Reeb], et al: Learning Gaussian Processes by Minimizing PAC-Bayesian Generalization Bounds, NeurIPS 2018\n\n### UPDATE\nHaving read the other reviews and rebuttal, I confirm my initial rating. I find the paper well written and its theoretical contributions interesting, but incremental. I think that a stronger empirical analysis would be required for acceptance. I agree with reviewers Mc3o and ZLiP that the paper does not provide really new insights into the differences between optimizing first order or second order bounds, nor into why the proposed bound does not improve upon state-of-the-art results. I believe that the empirical analysis should study in particular settings where base classifiers are weak and have low correlation, at the very least on toy datasets, and that the statistics of Figure 1 for the settings already studied should be reported. This would allow to check whether the lack of improvement is due to the looseness introduced by going from the oracle to the empirical bounds and if there are concrete settings where the proposed bounds would be useful.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "OQo8cp_mkpA", "reviewer": "Reviewer_Mc3o", "summary": "Most majority vote learning algorithms based on the PAC-Bayesian bound minimization focus on a first order bound. That is, the \"factor two\" oracle bound: the majority vote risk is lower than twice the (weighted) expected loss of its voters. The recent work of Masegosa et al. (2020) is a notable exception, and shows that great empirical accuracy and generalization bounds are obtained by taking into account the \"tandem loss\" (or \"joint error,\" as coined by Lacasse et al. 2007). Their approach is surprisingly elegant and simple, using the sole fact that the majority vote risk is lower than four times the tandem loss. But there is a caveat, as the oracle bound of Masegosa et al. (2020) is less tight than the C-bound, that takes into account both the expected loss and the tandem loss thanks to the Chebyshev inequality. Until now, few learning algorithms have successfully optimized the PAC-Bayes C-bound, mainly because its fractional nature is prone to numerical instabilities and causes the associated PAC-Bayes generalization guarantees to degrade. In the current manuscript, the authors study the optimization of a parametric relaxation of the C-bound that does not contain the malign fractional term.", "questions": "", "limitations": "", "rating": 5, "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": "The paper is well written and presents interesting ideas for the PAC-Bayesian community that pursues the objective of providing principled learning algorithms outputting both accurate predictors and tight generalization guarantees.  \n\nFrom a theoretical side, the first contribution (Theorems 7 and 12) is a nice incremental result based on Lacasse et al. (2007); Germain et al. (2015). However, the idea of minimizing a parametric relaxed version of the Cantelli-Chebyshev inequality to alleviate optimization problems does not turn out to provide improved empirical results, which weaken the importance of this first contribution. The theoretical novelty of the second contribution is (in my opinion)  the highlight of the paper. Indeed, Theorems 9 and 15 are obtained by an original analysis that introduce a new (translated) \"\\mu-tandem-loss,\" allowing combining the C-bound inequality and the PAC-Bayes-Bennett result of Tolstikhin and Seldin (2013). \n\n\nUnfortunately, the empirical results based on the minimization of the two new PAC-Bayesian theorems do not turn out to be really successful learning algorithms. The results seem to further confirm the surprising effectiveness of the algorithm proposed by Masegosa et al. (2020), especially in terms of bound values.  Considering this, the current manuscript would be more useful to the PAC-Bayesian community if it were providing a detailed analysis of the results, in order to draw conclusions that can foster future research. Here are some unanswered questions:\n- Why is the first order oracle bound often the best? \n- Can we identify some regime where the proposed algorithms would perform better? (maybe with weaker voters)\n- What are the observed values of the proposed C-bound, the expected loss, the tandem loss, and the selected value of \\mu? \n- What are the values of the original C-bound (Lacasse et al.) for the observed results? (For binary classification, the PAC-Bayes bound value could possibly be improved by bounding simultaneously the expected loss and the tandem loss.) \n- Should we conclude that the C-bound is not the good oracle inequality to minimize, or should we work harder to find tighter PAC-Bayesian inequalities? \n\nIt is also noticeable that the work is heavily based on the PAC-Bayes bound minimization techniques of Thieman et al. (2017). An interesting alternative would be to directly minimize the kl-bound. Although this has been considered as a difficult task, some recent works present simple strategies based on gradient descent (see Reeb et al. 2018, Letarte et al. 2019) \n\n\nOther comments:\n- When it comes to learning algorithms based on the PAC-Bayesian C-bound optimization, the authors should also mention the recent papers of Bauvin et al. (2020) and Viallard et al. (2021)\n- It is worth mentioning than the term \"C-bound\" have been used by the PAC-Bayes community since Lacasse et al. (2007) for the use of the (one-sided) Chebyshev inequality for majority vote learning, this has been discussed previously in the seminal paper of Breiman (2001) on Random Forests.\n- In Theorem 12, I doubt that it is necessary to use the union bound and a parameter grid for the \\mu value, as the expected loss bounds don't rely on \\mu, and Theorems 7 and 11 are uniformly valid for all values of \\mu and \\rho. \n\n\nReferences\n- Bauvin et al. Fast greedy C-bound minimization with guarantees. Machine Learning 2020\n- Letarte et al. Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks. NeurIPS 2019\n- Reeb et al.  Learning Gaussian Processes by Minimizing PAC-Bayesian Generalization Bounds. NeurIPS 2018\n- Viallard et al. Self-Bounding Majority Vote Learning Algorithms by the Direct Minimization of a\nTight PAC-Bayesian C-Bound. ECML/PKDD 2021\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not mention any societal impact in their paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "KmMd80vaKXe", "reviewer": "Reviewer_ZLiP", "summary": "Viewed at a high level, this paper is interested in majority-vote classifiers for binary classification tasks. The authors present both oracle and empirical risk bounds for such classifiers. In particular, since the empirical risk bounds are derived using (empirical) PAC-Bayes inequalities, one obtains high-probability bounds that hold uniformly over the choice of the weighting distribution (or \"posterior\") $\\rho$, meaning that the bounds can in principle be used as objective functions to be minimized with respect to the candidate weighting scheme.\n\nAs I understand it, the main \"take-aways\" from this work are the empirical PAC-Bayes bounds on the risk of MV under $\\rho$, namely Theorems 12 and 15, plus the empirical insights into their tightness and utility as objective functions.\n\nIf my understanding it correct, the main new idea here is to use a looser Chebyshev inequality (with shift parameter $\\mu$ not restricted to its optimal value) in order to get inequalities that have simpler dependence on $\\rho$. This basic idea is summarized in their Theorem 6, from which Theorems 7 and 8 directly follow. Theorems 12 and 15 respectively are based on Theorems 7 and 8, with the key difference being that the former uses the \"tandem loss\" used in the cited literature, whereas the latter uses the \"$\\mu$-tandem loss.\" The authors introduce a PAC-Bayes-Bennett inequality which refines the well-known PAC-Bayes-Bernstein inequality of Seldin et al., and the role of this inequality in their story is to handle their $\\mu$-tandem loss.", "questions": "", "limitations": "", "rating": 5, "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 paper is written clearly, and it takes the reader step-by-step through the chain of inequalities used to obtain their Theorems 12 and 15. As such, the paper is somewhat \"mechanical\" in nature; the various bits and pieces involved in their formal arguments are presented clearly, but it is questionable whether any new real insights have been obtained. While some readers may benefit from the idea of leaving $\\mu$ unspecified to obtain a simpler function of $\\rho$, we pay the price in terms of looser bounds and an extra parameter to set, though I felt this issue was swept under the rug by introducing the grid $\\{\\mu_1,\\ldots,\\mu_k\\}$ out of nowhere (same goes for Theorem 15).\n\nI also felt the authors could have done a better job of linking the empirical section to the theory; the terms C$\\mu$TND and COTND appear for the first time in section 6, and the naming seems wrong; why is Theorem 12's bound called the $\\mu$-tandem bound, despite the fact that it is Theorem 15 in which the $\\mu$-tandem risk appears? The empirical tests seem to be well-done, though the evidence in favor of the new bounds is not particularly strong.\n\nTaking these points together, I believe the paper is well-written and has clear contributions, but the significance of these contributions, and the resulting insights available to the reader are rather limited.\n\n**Update:** I thank the authors for their response, which provided some additional context for their work. Having read the other reviews and the reviewer discussion, I am not opposed to the paper appearing at the conference, but I still remain borderline on this one. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see the main review above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: While some reviewers pointed to merits of the submission, the contributions appear too incremental to deserve a publication at NeurIPS: reviewers expressed concerns about the significance of the results, comparison with earlier works, and the numerical validation of the proposed scheme, which is not deemed conclusive. I would invite the authors to carefully revise their manuscript in accordance with the reviews.
Decision: Accept (Poster)