Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables
Authors: Yi-Shan Wu
Yevgeny Seldin
Venue: NeurIPS 2022 Accept (2022)
Keywords: Concentration Inequalities
Ternary Random Variables
PAC-Bayes Analysis
Learning Theory

Abstract: We present a new concentration of measure inequality for sums of independent bounded random variables, which we name a split-kl inequality. The inequality combines the combinatorial power of the kl inequality with ability to exploit low variance. While for Bernoulli random variables the kl inequality is tighter than the Empirical Bernstein, for random variables taking values inside a bounded interval and having low variance the Empirical Bernstein inequality is tighter than the kl. The proposed split-kl inequality yields the best of both worlds. We discuss an application of the split-kl inequality to bounding excess losses. We also derive a PAC-Bayes-split-kl inequality and use a synthetic example and several UCI datasets to compare it with the PAC-Bayes-kl, PAC-Bayes Empirical Bernstein, PAC-Bayes Unexpected Bernstein, and PAC-Bayes Empirical Bennett inequalities.

Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables
Yi-Shan Wu
Yevgeny Seldin University of Copenhagen seldin@di. ku dk
University of Copenhagen yswu@di. ku.
Abstract
We present new concentration of measure inequality for sums of independent bounded random variables, which we name a split-kl inequality. The inequality is particularly well-suited for ternary random variables, which naturally show up in variety of problems, including analysis of excess losses in classification, analysis of weighted majority votes, and learning with abstention. We demonstrate that for terary random variables the inequality is simultaneously competitive with the kl inequality, the Empirical Bernstein inequality, and the Unexpected Bernstein inequality, and in certain regimes outperforms all of them. It resolves an open question by Tolstikhin and Seldin [2013] and Mhammedi to match simultaneously the combinatorial power of the kl inequality when the distribution happens be close to binary and the power of Bersntein inequalities to exploit low variance when the probability mass is concentrated on the middle value. We also derive PAC- BACC-BBye--splt--i inequality and compare it with the PAC- kl, PAC-Bayes Emprrrcal Empirrcal-Bennett Bennett, and PAC-Bayes- Saayes-Uneppetee treeppected-Bernstein inequalities an analysis of excess losses and in an analysis of weighted majority vote for several UCI datasets. Last, but not least, our study provides the first direct comparison of the Empirical Bernstein and Unexpected Bernstein inequalities and their PAC-Bayes extensions.
[2019) how
Bernstein
Introduction
Concentration of measure inequalities for sums of independent random variables are the most fundamental analysis tools in statistics and many other domains [Boucheron et al. 2013]. Their history stretches almost century back, and inequalities such as Hoeffding'ss 's [Heffding 1963 and Bernstein's 's [Bernstein 1946) are the main work horses of learning theory.
For binary random variables, one of the tightest concentration of measure inequalities the kl inequality [Maurer 2004 [angford] 2005 Foong al.) 2021 2022), which is based on combinatorial properties sum n independent random variables However, while being extremely tight for binary random variables and applicable any bounded random variables, the kl inequality is not necessarily a good choice for sums of bounded random variables that can take more than two values. In the latter case, the Empirical Bernstein [Mnih et al.) 2008 Audibert et al. 2009 Maurer and Pontil 2009] and the Unexpected Bernstein Cesa-Bianchi et al. 20077 Mhammedh et al. (0019] inequalities be significantly tighter due to their ability to exploit low variance, as shown by Tolstikhin and Seldin 2013). However, the Empirical and Unexpected Bernstein incqualities are loose for binary random variables [Tolstikhin and Seldin 2013)
'The Binomial tail bound is slightly tighter, but it does not extend to the PAC-Bayes setting I Langford 2005 Our split-kl approach can be directly applied to obtain "inimiaiiomall-ai" inequality.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The challenge of exploiting low variance and, at the same time, matching the tightness of the kl inequality if a distribution happens to be close to binary, was faced by multiple prior works [Tolstikhin and Seldin 2013, Mhammedi et al. 2019 Wu et al.] [021], J. but remained an open question. We resolve this question for the case of ternary random variables. Such random variables appear in a variety of applications, and we illustrate two of them. One is a study of excess losses, which are differences between the zero-one losses of a prediction rule h and a reference prediction rule ht, Z ((((X), Y) L(h (X) E {-1, 1, O, 1}. Mhhameei et al. (2019) have applied the PAC- Bayes-Unexpected-Beeee Bernsstei bound to excess losses in order to improve generalization bounds for classification. Another example of ternar random variables is the tandem loss with an offset, defined by La (,) ())) Y)= = (e(h(X), Y) (E(h' (X), a) E {a² -a(1 - a²) (1 a)²}. Wu et al. [021] have applied the PAC-Bayes Eoaeyess-mirriaal--- Emmirical-Bennett inequality the tandem loss with an offset to obtain a generalization bound for the weighted majority vote. Yet another potential applica-
tion, which we leave for future work, is learning with abstention [Cortes et al. 2018 Thulasidasan
et al. 2019].
We present the split-kl inequality, which simultaneously matches the tightness of the Empiri- cal/Unexpected Bernstein and the kl, and outperforms both for certain distributions. It works for sums of any bounded random variables Zi...., Zn. not only the ternary ones, but it is best suited for ternary random variables, for which it is almost tight (in the same sense, as the kl is tight for binary random variables). The idea behind the split-ki inequality is to write a random variable Z as Z = # + Z+ Z_ where μ is a constant, Z max(0, Z - 11), and Z = max(0, μ 2}. Then E [ μ + E [ E [ and. given i.i.d. sample Zi...., Zn, we bound the distance between 1 - Z4 and E [Z] by using kl upper and lower bounds on the distances between n
EE Z and E [. and E Z and E [2-], respectively. For ternary random variables Z {a. b, ef with a S b < the best split is to take μ 6, then both 2 and z are binary and the kl upper and lower bounds for their rescaled versions are tight and, therefore, the split-kl inequality for Z is also tight. Thus, this approach provides the best of both worlds: the combinatorial tightness of the kl bound and exploitation of low variance when the probability mass on the middle value happens to be large, as in Empirical Bernstein inequalities. We further elevate the idea to the PAC-Bayes domain and derive a PAC-Bayes-split-- inequality.
We present an extensive set of experiments, where we first compare the kl, Empirical Bernstein, Unexpected Bernstein, and split-kl inequalities applied to (individual) sums of independent random variables in simulated data, and then compare the PAC-Bayes-ko kl. AAC-Bayes-split-ae and, in some of the setups. models on several UCI datasets. In particular, we evaluate the bounds in the linear classification setup studied by Mhammedi et al. [2019] and in the weighted majority prediction setup studied by Wu et al.) (202T). To the best of our knowledge, this is also the first time when the Empirical Bernstein and the Unexpected Bernstein inequalities are directly compared, with and without the PAC-Bayesian extension. In Appendix A.2 we also show that an inequality introduced by Bianchi et al. [2007] yields a relaxation of the Unexpected Bernstein inequality by Mhammedi et al. 2219
Bersssstennnnnnnn for several prediction
2 Concentration of Measure Inequalities for Sums of Independent Random Variables
We start with the most basic question in probability theory and statistics: how far can an average of an i. sample Z,.... Z, deviate from its expectation? We cite the major existing inequalities, the kl, Empirical Bernstein, and Unexpected Bernstein, then derive the new split-kl inequality, and then provide a numerical comparison.
2.1 Background
We use (L(pllz) to denote the Kullback-Leibler divergence between two probability distributions,
p and x [Cover and Thomas 2006). We further use <l(plg) as shorthand for the Kullback-
Leibler divergence between two Bernoulli distributions with biases and q. namely kl(pllg) = KL((1- p1 q, 9)). For e E [0, I] and 2 0 we define the upper and lower inverse of kl, respectively, as 1l-1,+ (t,e)) E) = max {p: p E [0, 1] and kl(lllp) S e) and -1- (p,e) =
min {p p e [0 and kl(lllp) S E).
2

---

The first inequality that we cite is the kl inequality.
Theorem 1 (k1 Inequality [Langford 2005 Foong et al. 2021
2022 ). Let Z1 ..... .Zn be i.i.d.
random variables bounded in the [0, 1 interval and with E Z for all i. Let p = = Zi be their empirical mean. Then, for any 8 E (0, 1):
In 1
PP kl(pllp)
and, by inversion of the kl,
p. In 1 ) s 8,
1
P p 2 kl 1,
(1)
n
P p kl
In 5 s 8.
(2)
We note that the PAC-Bayes-Ht inequality (Theorem
below) is based on the inequality
E [enkt((llp)]
< 2 Maurer 2004], which gives P kl(plp) In 2ye
8. Foong et al. [2021
2022 reduce the logarithmic factor down to In by basing the proof on Chernoff's 's inequality, but this proof technique cannot combined with PAC-Bayes. Therefore, when we move on to -Ayes we pay the extra In 2 / factor in the bounds. It is a long-standing open question whether this factor can be reduced in the PAC-Bayesian setting (Foong et al., 202T].
-
Next we cite two versions of the Empirical Bernstein incquality. Theorem 2 (Empirical Bernstein Inequality (Maurer and Pontil 2009]). ). Let Zi, Zn be i.i.d. random variables bounded in a [a, b) interval for some a, b E R. and with E [2,] for all i. Let a
I = + Zi be the empirical mean and let â - Σ - 2) be the empirical variance.
Then for any 5 E (0. 1):
26 In 2 5 7(b a) In
P p P2
5.
(3)
n 3(n - 1)
Theorem 3 (Unexpected Bernstein Incquality Fan al. 2015 Mhammedi et al. 2019 Let
Zz.... Zn be i.i.d. random variables bounded from above by for some b > O, and with E Z for all i. -er-= Σi= Zg be the empirical mean and let Σ Z3 be the empirical mean of the second moments. Let (u)) == u - Inn1 + for ò E (0, 1):
11 Then, for any E 10,1/b) and any
(1-)b) 762
+ In 1
(4)
To facilitate a comparison with other bounds, Theorem 3 provides a slightly different form of the Unexpected Bernstein inequality than the one used by Mhammedi al. [2019]. We provide a proof of the theorem in Appendix A.I which is based on the Unexpected Bernstein Lemma [Fan et al., 2015). We note that an inequality proposed by Cesa-Bianchi al. [2007] can be used to derive relaxed version of the Unexpected Bernstein inequality, as discussed in Appendix A.2
2.2 The Split-kl Inequality
Let Z be random variable bounded in [a, b] interval for some a, E R and let μ E Ja, bj be a constant. We decompose Z = μ + Z
where Z max(0, Z - 11) and Z max(0, / Z). Let p E [Z], pt E [Z 1. and p- E I ]. For an i.i.d. sample Zi...., Zn let
5+ Σn Z, and 5- Σ 2,-
With these definitions we present the split-kl inequality. Theorem 4 (Split-kl inequality). Let Zi...., Zn be i.i.d. random variables in a (a, bj interval for some a, be R, thenfor any p [a, and 8 E (0, 1):
p+
1 2
- (μ - a) 11 ( ( 1
2) s
IP p 2 + (b 11) 1,+
1,
In
(5)
n
3

---

Proof.
(
1 2
( p 1
2
p 4 (b- p) (b-)bb
( b- ji n 8)
In
(w a))
- In
8
11 1- a n
$ P p* 2 (b 1.
k1 1,
p
2 2))) w'
im
P p s (w a) -1
p 2
11 4- a n
where the last inequality follows by application of the kl upper and lower bounds from Theorem the first and second terms in the middle line, respectively.
For ternary random variables the best choice is to take to be the middle value, then the resulting Z and Z are binary and the corresponding kl upper and lower bounds on pt and y are tight, and the resulting split-kl bound is tight. The inequality can be applied to any bounded random variables, but same way as the inequality not necessarily a good choice for bounded random variables, if the distribution is not binary, the split-kl in not necessarily good choice if the distribution is not ternary.
2.3 Empirical Comparison
We present an empirical comparison of the tightness of the above four concentration incqualities: the kl, the Empirical Bernstein, the Unexpected Bernstein, and the split-kl. We take i.i.d samples 71,-... Zn taking values in {-1, 0, 13. The choice is motivated both by instructiveness of presenta- tion and by subsequent applications to excess losses. We let p-1 PP 1),, Po P 0), and
P1 = ( = 1), where p-1 + po + P1 = 1. Then p = E [Z] = P1 - p-1- We also let 1 = i= Zz
In Figure D we plot the difference between the bounds on given by the inequalities
and (5) and p. Lower values in the plot correspond to tighter bounds. To compute the ki bound we first rescale the losses to the [0, 1] interval, and then rescale the bound back to the [-1, interval. For the Empirical Bernstein bound we take a = -1 and b = 1. For the Unexpected Bernstein bound we take for & = [log2( /n/ In lm(1/6)/2) and a union bound over the grid, as proposed by Mhammedi et al. [0119]. For the split-kl bound we take j to be the middle value, 0, of the ternary random variable. In the experiments we take 5 = 0.05, and truncate the bounds at 1.
a grid of 7 E (1/(2b), .................
1/)2=b) ..(.......6)))))
In the first experiment, presented in Figure Ia we take p-1 Pi = (1 po)/2 and plot the difference between the values of the bounds and p as a function of pn- For po = the random variable Z is Bernoulli and, as expected, the kl inequality performs the best, followed by split-kl, and then Unexpected Bernstein. As po grows closer to 1, the variance of Z decreases and, also as expected, the kl inequality falls behind, whereas split-kl and Unexpected Bernstein go closely together. Empirical Bernstein falls behind all other bounds throughout most of the range, except slightly outperforming kl when po gets very close to 1.
In the second experiment, presented in Figure 1b we take a skewed random variable with p1 0.99(1 - Po) and p-1 = 0.01 Po), and again plot the difference between the values of the bounds and P as function of Po- This time the kl also starts well for Pu close to zero, but then falls behind due to its inability of properly handling the values inside the interval. Unexpected Bernstein exhibits the opposite trend due to being based on uncentered second moment, which is high when po is close to zero, even though the variance is small in this case. Empirical Bernstein lags behind all other bounds for most of the range due to poor constants, whereas split-kl matches the tightest bounds, the kl and Unexpected Bernstein, at the endpoints of the range of Po. and outperforms all other bounds in the middle of the range, around po = 0.6, due to being able to exploit the combinatorics of the problem.
The experiments demonstrate that for ternary random variables the split-kl a powerful alternative to existing concentration of measure inequalities. To the best of our knowledge, this is also the first empirical evaluation of the Unexpected Bernstein inequality, and it shows that in many cases it also a powerful inequality. We also observe that in most settings the Empirical Bernstein is weaker than the other three inequalities we consider. Numerical evaluations in additional settings are provided in Appendix D

---

=100, p p1-0.99 po)
n =000 pi=0.5(1 pm)
0.30
941
0.25
0.20
0.3
Bound
0.15
Bound
0.2
0.100
Emp
Emp Bern
0.35
Unexpp
0.1
Unexp Bern
Split-ki
Spit-kl
0.0
0.
Pn
(b) Comparison of the concentration bounds with 100. 8 0.05, pi 0.99(1 po). and p-1 0.01 po).
(a) Comparison of the concentration bounds with 100, 0.05 and p-1 1 = pi 0.5(1 po).
v
Figure 1: Empirical comparison of the concentration bounds.
3 PAC-Bayesian Inequalities
Now we elevate the basic concentration of measure inequalities the PAC-Bayesian domain. We start with the supervised learning problem setup, then provide a background on existing PAC-Bayesian inequalities, and finish with presentation of the PAC-Bayes-split-kl inequality.
3.1 Supervised Learning Problem Setup and Notations
Let X' be a sample space, y be label space, and S {(X,, v.)),- be an i.i.d. sample drawn according an unknown distribution D on the product-space X' containing hypotheses : X + V. The quality of a hypothesis Let Let H be a hypothesis space measured using the zero-one 1(h(X)+ + Y), where 1()) is the indicator function. The expected loss of h is
loss (()(X), denoted by L(h) = EX [e(h(X, Y)], and the empirical loss of on sample S is denoted by ihh [ST Exxyjes ((((X), Y). We use Ep|-] [-] shorthand for Exxy))=Dl+.
PAC-Bayesian bounds bound the generalization error of Gibbs prediction rules. For each input X X. Gibbs prediction rule associated with a distribution p on H. randomly draws a hypothesis h E H. according p and predicts h(X). The expected loss of the Gibbs prediction rule is Sa>p!((h) and the empirical loss is Bn-pL S)]. We E,[:] as a shorthand for En~plT]
3.2 PAC-Bayesian Analysis Background
Now we present a brief background on the relevant results from the PAC-Bayesian analysis.
PAC-Bayes-kl Inequality The PAC-Bayes-kl inequality cited below is one of the tightest known generalization bounds on the expected loss of the Gibbs prediction rule.
Theorem 5 H that is independent and any 8 E
Inequality, SSeger 2002
Maurer 2004). For any probability distribution
(0, 1):
P P(3pEP: (EpLi(h, S)]
E. [L(h)) KL(p](m) In(2
<
(6)
n
where P the set of all possible probability distributions on H that can depend S.
The following relaxation of the PAC-Bayes-kl inequality based on Refined Pinsker's relaxation the kl divergence helps getting some intuition about the bound [McAllester 2003). With probability at least 1 8, for all p E we have
E, [Th)] (,,, 1 (t,,, (L(p)(T) + In(2/7/8) (KL(pl))) + ln(2v7/6))
n
5

---

E,,, .)] is close to zero, the middle term in the inequality above vanishes, leading to so-called "fast convergence rates" (convergence of [p) to Ep[L(h) the rate of 1/n). However, achieving low E,p (h, S)] is not always possible |Dziugaite and Roy, 2017 Zhou et al., 2019]. Subsequent research in PAC-Bayesian analysis has focused on two goals: (T) achieving fast conver- gence rates when the variance of prediction errors is low (and not necessarily the errors themselves), and (2) reducing the KL(p term, which may be quite large for large hypothesis spaces. For the first goal Tolstikhin and Seldin [2013] developed the PAC-Bayes- Ba--aayy--EEiiicallll -ericcall--eseeinn incquality and Mhammedi et al. 2019 proposed to use excess losses and also derived the alternative PAC- Mayes-Unexpectedd Bernstein inequality. For the second goal Ambroladze et al. (2007) suggested to use informed priors and Mhammedi et al. [2019) perfected the idea by proposing to average over "forward" and "backward" construction with informed prior. Next we explain the ideas behind the excess losses and informed priors in more details.
Excess Losses Let ht be a reference prediction rule that is independent of S. We define the excess loss of prediction rule h with respect to the reference he by
( h" (X)), Y) = ((h((),
(X),
If is the zero-one loss, the excess loss naturally gives rise to ternary random variables, but it is well-defined for any real-valued loss function. We use (,( (X)) (x),) = I(h) I(hh)) to denote the expected excess loss of h relative h" and (h, N IST Ex. (r(h(X), (x),, = [(h)- - L(h*) to denote the empirical excess loss of relative to ht. The expected loss of a Gibbs prediction rule can then be written as
(p] (h, + L(h").
A bound on [b]] can thus be decomposed into a summation of a PAC-Bayes bound on EpIA2 (h, h²) } and bound on Lhh)). When the variance of the excess loss small, we can use tools that exploit small variance, such as the
Bernstein, or PAC-Bayes-Split-kl inequalities proposed below, to achieve fast convergence rates for the excess loss. Bounding L(h") involves just single prediction rule and does not depend on the value of () We note that it is essential that the variance and not just the magnitude of the excess loss is small. For example, if the excess losses primarily take values in (-,, and average out to zero, fast convergence rates are impossible.
Informed Priors The idea behind informed priors is to split the data into two subsets, S₁ US, and to use Si to learn a prior TS,, and then use learn posterior on S. [mmbrllddze et al. [2007). Note that since the size of Sg is smaller than the size of S, this approach gains in having potentially smaller [L(p but loses in having a smaller sample size in the denominator of the PAC-Bayes bounds. The balance between the advantage and disadvantage depends on the data: for some data sets strengthens the bounds, but for some it weakens them. MMhammedi et al. [2099] perfected the approach by proposing to use it in the "forward" and "backward" direction and average over the two. Let S1 and S2 be of equal size. The "forward" part uses S₁ to train Ts, and then computes posterior posterior on Sj. Finally, the two posteriors are averaged with equal weight and the KL term becomes (KL(P))TT,) + (L(pp) (p((T)))))))))))){)()))) )). See MMhammedi et al. 2019) for the derivation.
S2, while the "backward" part uses Sq to train ITy and then computes
Excess Losses and Informed Priors Excess losses and informed priors make an ideal combination. If we split S into two equal parts, S = S₁ U Sz. we can use S₁ to train both reference prediction rule hs, and a prior R.,, and then learn a PAC-Bayes posterior on Sg. and the other way around. By combining the "forward" and "backward" approaches we can write
(b)) 1 I hs 1 15,
1 +2 (L L(hs.)),
(8) and we can use PAC-Bayes to bound the first term using the prior TS, and the data in Sz, and to bound the second term using the prior TS, and the data in S,, and we can bound L(hs,) and L(hs,) using the "complementary" data in S2 and Sr, respectively.
Caaaaes-Emmpriial-BBeeerttttttte Inequalities The excess losses are ternary random variables taking values in {-1,0, 0, 1) and, as we have already discussed, the kl incquality is not well-suited

---

for them. PAC-Ba -ay-Bsyei inequalities tailored for non-binary random variables were derived by
Seldin et
2012
Tolstikhin and Seldin 2013), Wu al. [02T], and Mhammedi et al. (2019). oracle bound, which assumes knowledge of
Seldin et al.
2012 derived the PAC- BayeB-ayyysseeeee
variance. Tolstikhin and Seldin 2013) made into an empirical bound by deriving the PAC-
Bayes-Empirical Bernsteen bound for the variance and plugging it into the PAC-Bayes-Bernsteel bound of [Seldin et al.) WWu et al. [2021] derived an oracle PAC- BACCBByee-Aa B-C-Bayys-Bennet inequality, which again assumes oracle knowledge of the variance, and showed that it is always at least tight as the JAC-Bayes-Bernster
bound on the variance. MMhammedi al. [209]] derived the PAC-Bayes- Unexpected-eeeeeeeee -erippeeeeed-eennteeinn inequality, which directly uses the empirical second moment. Since we have already shown that the Unexpected Bernstein inequality is tighter than the Empirical Bernstein, and since the approach of Wu al.] requires a combination of two inequalities, PAC- (Baaye---miiricl---eeeee
and then also plugged in the BAC-Bayes-Unexpeetee
for the variance and PAC-Bayes-Bennge Bennett for the loss, whereas the approach of Mhammedi et al.. only makes single application of PAC-Bayes-Uness Unexpected UnexpecteddBermsteen Bernstein, we only compare our work to the latter.
We cite the inequality of Mhammedi et al. [2019], which applies to arbitrary loss function. We use i and matching tilde-marked quantities distinguish it from the zero-one loss l. For any h E H. let Lhh) = Eple(h Y) be the expected tilde-loss of h, and let L(h,S) = Exxy)es ((N(X), Y) be the empirical tilde-loss of h on sample S.
Theorem PPCCBaays-Unexppeetee Bernstein inequality [Mhammedi et al. 2019 Let E(::)) be an arbitrary loss function bounded from above by b for some b > and assume that (h, S) = [8] Exxyyes (lh(X), y)² is finite for all h. Let vb(u) := u - In(1 + u) for -1. Then for any distribution ι on H that is independent of S, any 7 E (0, 1/b), and any 5 E (0,
P E P. :EEILO)) 2 (RIi(h, S)] *b(-b)
702 S)) KT(pl(=) + In
IP 3p
5.
7/1
where P is the set of all possible probability distributions on H. that can depend on S.
In optimization of the bound, we take the same grid of y E (1/(2b), ... (nss((///n((1/55/// and union bound over the grid, as we did for Theorem
.1((2b)) for k
3.3 PAC-Bayes-Split-kl Inequality
Now we present our ACC-Bayes-Split--e inequality. For an arbitrary loss function ? takinn values in [a, bj interval for some a, E R, let /+ : max(0, e - μ} and e = max (0, f - - for some E [a, b). For any h E H. let L (h) = (M((),))))))))))))) and - (h) = ED le- (h(X), Y)]. The corresponding empirical losses are denoted by i = 1 Σ (b(X)), Yi) and L S) =
E. -- (h(X.), Y.).
Theorem 7 BEAC-Bayes-Sppe a (a, b) interval for some a, E RR Then for any distribution a on H that is independent of S, any (a, b), and any ö E (0, 1):
Inequality). Let E(..-) ) be an arbitrary loss function taking values in
E (h, (L(p](T
AVT TT) + In
P ppp P: E,(i(h) 2 + (b (()-k) 11+
b
[E, (h, (L(pl] + In 4VT
(u a) kl-
S 8,
where P the set of all possible probability distributions on H that can depend on S.
Proof. We have E,(L(()) = + E, (h)] E, (h)). Similar to the proof of Theorem 4 we take a union bound of PAC-Bayes-kl upper bound on E,,LL(A)) (h)] and PAC-Bayes-kl lower bound on E, (h)]-
7

---

3,4 PAC--ayes-spli--kl with Excess Loss and Informed Prior
Looking back at the expected loss decomposition in equation (8) we can use PAC-Bayes-split-
kl to bound the first two terms and a bound on the binomial tail distribution to bound the
last term. For n i.i.d Bernoulli random variables Zi....: Zn with bias p E (0, 1), we define the binomial tail distribution (in k. p) P X; S k) and its inverse Bin (n, k 6)
max {p= : E [0, 1] and Bin k. 2 83. The following theorem relates p = Di= Zi and p. Theorem 8 (Test Set Bound [Langford 2005). Lel Zi,..., Zn be i..dd Bernoulli random variables with bias E (0, 1) and let > i=1 Zi be the empirical mean. Then for any á E (0, 1):
IP Bin (n, np. 6) <
By applying Theorems 7 and to equation
S we obtain the following result.
Theorem 9. For any μ [-1,1] and any 8 (0,
P3DEE E,(((h) 2 u -1-11-1000
(x++ (1+1)(()) 2(0) So.
(1 m)(a)
where P is the set of all possible probability distributions on H that can depend on S.
Ep
A
(h, hSi, S2)]
1 (h, hsz St) KL(p](T) + In 8/a/2
(a) 11
+
2 1 1
1 14
n//2
A A (h, US. S2)
A i, (h, 1122, Si)] KL(pI| TT) + In
8yn/2
( = 11-
+ 2
u+1
1 + 1
nl/2
in which π = T. + T2 and
8) n n1 i S2), 2)
11(1 11 (hs,. S1), o)
(c) Bin 11
+ Bin
2'2
2
The proof is postponed to Appendix
C
4 Experiments
We evaluate the performance of the PAC-Bayes-split-Be inequality in linear classification and in weighted majority vote using several data sets from UCI and LibSVM repositories [Dua and Graff 2019 Chang and Lin [011]] An overview of the data sets is provided in Appendix E. For linear classification we reproduce the experimental setup of Mhammedi et al. [2019], and for the weighted majority vote we reproduce the experimental setup of Wu et al. 2021]
4.1 The Experimental Setup of Mhammedi et al. 2019| Linear Classifiers
In the first experiment follow the experimental setup of Mhammedi et al. [2019], who con- sider binary classification problems with linear classifiers in Ik" and Gaussian priors and poste- riors. A classifier hw associated with vector w E Rd makes a prediction on an input by (X) = 1 (w X > 0). The posteriors have the form of Gaussian distributions centered at Wg Rdd with covariance Es that depends priors Ts, = N(ws,, Ds,) and Ts, = NNws, Es,)) are also taken to be Gaussian distributions centered Ws, and Wsz. with covariance Lss, and Lg,, respectively. We take the classifier associ- ated with Ws, as the reference classifier hg, and the classifier associated with Ws, as the reference classifier hs,- More details on the construction are provided in Appendix
sample S, p N(ws, Es). The informed
Figure compares the PAC- MAC-Bayes-Be See--ByysUUnnxeeee Ueee--nnee-eeeeeeeeeeeeee Bernstein bound PBUB and the PAC-Bayes-split-l bound PBSkl with excess losses and informed priors. The ternary random variables in this setup take values in {-1, 0, 1}, and we select j to be the middle value Since the PAC-Bayes-ki bound (PBkl) one of the tightest known generalization bounds, we take PBkl with informed priors baseline.
8

---

HABERMAN BREAST-C TICTACTOR BANKNOTES
KR-VS-KP
0.20
0.2
0.10
0.4
0.15
0.10
0.2
0.10
0.1
0.05
0.05
0.05
0.0
0.00
0.0
0.00
0.00
SPAM
SVMGUIDEL MUSHROOM
ADULTS
0.3
0.20
0.2
0.02
0.15
PBkl IO PBUBEX Ex
0.2
0.1
0.1
0.01
0.10
I PBSKLEx
0.05
0.0
0.0
0.00
0.00
Figure 2: Comparison of the bounds and the test losses of the optimized Gaussian posterior p² generated by PBkl with informed priors, PBUB with excess losses and informed priors, and PBSkl with excess losses and informed priors. The test losses of the corresponding bounds are shown in black. We report the mean and the standard deviation over 20 runs of the experiments.
The details on bound calculation and optimization are provided Appendix E.2 In this experiment all the three bounds, PBk1, PBUB, and PBSk1 performed comparably. We believe that the reason that with informed priors the (L. x)) term is small. From the relaxation of the PBk1 bound in equation 7 we observe that small [L(p][T] term implies smaller difference between fast and slow convergence rates, and thus smaller advantage to bounding the excess loss instead of the raw loss. In other words, we believe that the effect of using informed priors dominates the effect of using excess losses. We note that order to use excess losses we need to train the reference hypothesis ht on part of the data and, therefore, training informed prior on the same data comes at extra cost.
4.2 The Experimental Setup of Wu et al. [2021]: Weighted Majority Vote
In the second experiment we reproduce the experimental setup of Wu al.) [2021] J. who con- sider multiclass classification by a weighted majority vote. Given an input X E X, a hypothesis space H. and distribution p on H. a p-weighted majority vote classifier predicts MV, arg wey E,p (h(X) v)]- One of the tightest bound for the majority vote is the tandem bound (TND) proposed by Masegosa al. [2020), which is based on tandem losses for pairs of hypotheses. ((h(X), h' (X), Y = I(h(X) # (X) * Y). and the second order Markov's 's inequality. Wu al. [2021] proposed two improved forms of the bound. both based on a parametrie form of the Chebyshey-Cantel inequality. The first, CCTND, using Chebyshev-Cantee with the tandem losses and the PAC-Bayes-kd bound for bounding the tandem losses. The second, CCPBB, using tandem losses with an offset, defined by la (h(X). for < 0.5, and PAC-Bayes- Baayes-Emprrical--Bee Bennett inequality for bounding the tandem losses with an offset. We note that while the tandem losses are binary random variables, tandem losses with an offset are ternary random variables taking values in {a? -a(1 - ax), (1 - a))) and, therefore, application of Empirical Bernstein type inequalities makes sense. However, in the experiments of Wu ctt al. CCPBB lagged behind TND and CCTND. We replaced Berteeeee--eennnnneee (CCPBUB) and PAC-Baycs-spli--a (CCPBSkI) and showed that the weakness of CCPBB was caused by looseness of PAC-Bayes-Enie Baapeee-mpiriaal----- Seerrcaal-Berstein.. and that CCPBUB and CCPBSkl lead to tighter bounds that are competitive and sometimes outper- forming TND and CCTND. For the CCC-Bayes-splitaee bound we took μ to be the middle value of the tandem loss with offset, namely, for a 0 we took μ a² and for == -1= a.).
Y) (1(A(X)) + Y) () + Y) - a)
with
0 we took
In Figure 3 we present a comparison of the TND, CCTND, CCPBB, CCPBUB, and CCPBSkI
bounds on weighted majority vote of heterogeneous classifiers (Linear Discriminant Analysis, Nearest Neighbors, Decision Tree, Logistic Regression, and Gaussian Naive Bayes), which adds the

---

ADULT
COD-RNA
MUSHROOM
PHISHING
0.3
0.6
0.2
0.10
0.4
0.2
0.1
0.05
0.2
0.0
0.0
0.00
0.0
CONNECT-4
LETTER
MNIST
0.8
TND I CCTND I CCPBB I CCPBUB In CCPBSKK
0.3
0.15
0.6
0.2
0.10
0.4
0.2
0.1
0.05
0.0
0.0
0.00
Figure 3: Comparison of the bounds and the test losses of the weighted majority vote ensembles of heterogeneous classifiers with optimized posterior p² generated by TND, CCTND, CCPBB, CCPBUB, and CCPBSkl. The test losses of the corresponding bounds are shown in black. We report the mean and the standard deviation over 10 runs of the experiments.
Iwo new bounds, CCPBUB and CCPBSKI to the experiment done by Wu al. 20221] more detailed description of the experiment and results for additional data sets are provided in Appendix E. We note that CCPBUB and CCPBSkI consistently outperform CCPBB, demonstrating that they are more appropriate for tandem losses with an offset. The former two bounds perform comparably TND and CCTND, which operate on tandem losses without an offset. In Appendix [E.4 we replicate another experiment of Wu et al.) where we use the bounds to reweigh trees in random forest classifier. The results are similar the results for heterogeneous classifiers.
Discussion
We have presented the split-kl and PAC-Bayes- AAC-Bayes-split-kk inveessipiii-kiiinnnttiieieee The inequalities answer long- standing open question on how to exploit the structure of ternary random variables in order to provide tight concentration bounds. The proposed split-kl and PAC-Bayes-split-k inequalities are tight for ternary random variables, as the and PAC-Bayes-kl inequalities are tight for binary random variables.
In our empirical evaluation the split-kl inequality was always competitive with the kl and Unexpected Bernstein inequalities and outperformed both in certain regimes, whereas Empirical Bernstein typically lagged behind. In our experiments in the PAC-Bayesian setting the PAC-Bayes-split-K was always comparable to PAC-Bayes AACCBayes-Unnxpecteee Ihexpected-Beemstein.. Bernstein, whereas PAC-Bayee Bayes-Empiricall Bennett most often lagged behind. The first two inequalities were usually comparable to PAC- JAC-Bayes-kll although in cases the attempt to exploit low variance did not pay off and PAC-Bayes-kl outperformed, which is also the trend observed earlier by Mhammedi et al. [2019]. To the best of knowledge, this is the first time when the various approaches to exploitation of low variance were directly compared, and the proposed split-kl emerged as a clear winner in the basic setting, whereas in the PAC-Bayes setting in our experiments the -Bayes-Unxxpected Bernsstei and PAC-Bayes-split-kl were comparable, and preferable over PAC-Bayes-Emprricl-Berre PAC--Baee-Emppircal-Beeeen Bennettt
and
Acknowledgments and Disclosure of Funding
This project has received funding from European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska- Curie grant agreement No 801 199. The authors also acknowledge partial support by the Independent Research Fund Denmark, grant number 0135- 00259B.
10

---

References
Amiran Ambroladze, Emilio Parrado- Hemendez, and John Shawe-Taylon Tighter PAC-Bayes bounds. In Advances Neural Information Processing Systems (NeurIPS), 2007.
Jean Yves Audibert, Rémi Munos, and Csaba Szepesvári. Exploration-exploitttii trade-off using variance estimates in multi-armed bandits. Theoretical Computer Science, 2009.
Sergei N. Bernstein. Probability Theory. Moscow-Leningrad, 4th edition, 1946. In Russian.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: Nonasymptotic Theory of Independence. Oxford University Press, 2013.
Nicolò Cesa-Biance Yishay Mansour, Gilles Stoltz. Improved second-order bounds for prediction with expert advice. Machine Learning, 66, 2007.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2, 2011.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Scott Yang. Online learning with abstention. Proceedings of the International Conference on Machine Learning (ICML), 2018
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley Series in Telecommunications and Signal Processing, 2nd edition, 2006.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2019. URL http://archive. ics uci edu/ m1
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep
(stochastic) neural networks with many more parameters than training data. In UAI, 2017.
Xiequan Fan, Ion Grama, and Quansheng Liu. Exponential inequalities for martingales with applications.
Electromic Journal of Probubility, 20:1-22, 2015.
Ciprian Florescu and Christian Igel. Resilient backpropagation (rprop) for batch-learning tensorflow. In International Conference on Learning Representations (ICLR) Workshop, 2018.
Andrew Foong, Wessel Bruinsma. David Burt, and Richard Turner. How tight can pac-bayes in small data regime? In Advances in Neural Information Processing Systems (NewrIPS), 2021.
Andrew Y. K. Foong, Wessel P. Bruinsma, and David Burt. A the chernoff bound for random variables in the unit interval. arXiv preprint 2tt.22005.07880 2022.
W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal the American Statistical Association, 58(301):13-33 30, 1963.
Christian Igel and Michael Hüsken. Empirical evaluation of the improved rprop learning algorithms. Neurocom- puting, 50, 2003.
John Langford. Tutorial on practical prediction theory for classification. Journal of Machine Learning Research. 6, 2005.
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.
Andreas Maurer. A note on the PAC-Bayesian theorem. arXiv preprint cs/041 1099, 2004.
Andreas Maurer and Massimiliano Pontil. Empirical Bernstein bounds and sample variance penalization. In Proceedings of the Conference on Learning Theory (COLT), 2009.
David McAllester. PAC-Bayesian stochastic model selection. Machine Learning, 51, 2003.
Zakaria Mhammedi, Peter Grünwald, and Benjamin Guedj. PAC-Bayes un-expected Bernstein incquality. In Advances Neural Information Processing Systems (NeurIPS), 2019.
Volodymyr Muih, Csaba Szepesvári. and Jean-Yves Audibert. Empirical Bemstein stopping. In Proceedings of the International Conference Machine Learning (ICML), 2008.
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- and Peter Auer. PAC-Bayesian inequalities for martingales. IEEE Trunsactions on Information Theory, 58, 2012.
Niklas Thiemann, Christian Igel, Olivier Wintenberger, and Yevgeny Seldin. A strongly quasiconvex PAC- Bayesian bound. In Proceedings the International Conference Algorithmic Learning Theory (ALT), 2017.
Sunil Thulasidasan, Tanmoy Bhattacharya, Jeff A. Bilmes, Gopinath Chennupati, and Jamal Mohd- Yusof. Combating label noise deep learning using abstention. Proceedings of the International Conference on Machine Learning (ICML), 2019.
Ilya Tolstikhin and Yevgeny Seldin. Se--Bayss-Empircall Berrsseen inequality. In Advances in Neurul Information Processing Systems (NewrIPS), 2013.
Olivier Wintenberger. Optimal learning with Bernstein online aggregation. Machine Learning. 106, 2017.
Yi-Shan Wu, Andres Masegosa, Stephan Lorenzen, Christian Igel, and Yevgeny Seldin. Chebyshev-cantelli pac-bayes-benneu inequality weighted majority vote. Advances Neural Information Processing Systems (NeurIPS), 2021.
Wenda Zhou, Victor Veitch, Morgane Austern Ryan P. Adams, and Peter Orbanz. Non-vacuous generalization bounds at the imagenet scale: a PAC-bayesian compression approach. In ICLR, 2019.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] All assumptions are stated in the statements of the theorems.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The work mainly discussed the fundamental concentration inequalities and the potential applications. The main applications discussed the work are PAC-Bayes analysis on classification problems, and the potential negative societal impacts follow the problems being studied.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See Section
Appendix E
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4 Appendix E
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Appendix E
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] the code and the paper.
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material URL? [Yes]
New code in the supplementary.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No] We use publicly available datasets from the UCI and LibSVM repositories.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [No] We use publicly available datasets from the UCI and LibSVM repositories. The data does not contain personally identifiable information
or offensive content.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "kP0NaxeyLF3", "reviewer": "Reviewer_nL9t", "summary": "The authors introduced a new approach to a concetration inquality for random variables over a bounded interval called \"split kl inequality\", which first decomposes the original random variable into three terms and then applies an existing bound \"kl ineqaulity\" to the decomposed terms. Then the authors proposed to use the split kl inequality for PAC-Bayes bounds of generalisation error of learning alrogrithms as well as to combine it with existing approaches of excess loss and informed prior. The derived PAC Bayes generalisation error bound were compared and examined in a few different experiments.", "questions": "- How much is \"informed prior\" crucial to produce meaningful generalisation bounds in this context? — Would it be possilble to see how much improvement of bounds are done by \"informed prior\"? \n- I was also not familier with how commonly or frequently \"informed prior\" is used in PAC-Bayes domain. It may be helpful to more strongly justify that \"informed prior\" is a reasonable approach to use in practice by additional references.\n- It would be visually helpful to make clear which bound is the proposed one in Figure 2 and 3 e.g. adding \"(Ours)\" or something to the name lavel of the proposed one in Figure 2 and 3.\n- The models in the experiments dealt in this paper seem relatively simple. I understand that proving generalisation bounds of complex models is challenging but I was personally interested in seeing if the generalisation bound still works for more complex models e.g. LeNet for MNIST.", "limitations": "There would not no concern for potential negative societal impact. To me personally, the current limitation is that it is difficult to interprete from experiments or equations if the proposed idea of PAC-Bayes-split-kl inequalities has imporved the generalisation bounds to a fair defree or not. For example, would the difference of number in the figures be significant in the context of PAC-Bayes? The reviewer's position on this paper is neutral and the reviewer is happy to increase the score if the technical or practical impact is well justified.\n", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The reviewer is personally very much fond of the authors' writing in this paper, which explains important matters of this work / other existing works in an intuitive and comprehensive manner. For example, the motivation of this work is nicely lined up with a proper technical level to wide audiences in introduction. In addition, the advantage of split kl inequality has been made clear in Figure 1. Comprehensive presentation and simplicity of the idea is a clear strengh of this work. My main concern is the significance / impact when we combine this idea with PAC-Bayes bounds. The derived new generalisation bound in Figure 2, 3 seemed similar to the other existing bounds at first glance, or it was unclear how to interprete the improvement level. For the first experiment for example, since the authors combined their idea of split kl inequality with existing approaches of \"informed priors\", some might get an impression from these figures that the \"informed prior\" part has already finished the majority of works to lower a bound in each bound and they may wonder about how critical the improvement by the split kl part is.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "H49zjkyUXdk", "reviewer": "Reviewer_eeea", "summary": "The authors present a new concentration of measure inequality for sum of independent bounded random variables namely split-kl inequality. They derive this new inequality by combining kl-inequalities (1 and 2) in a clever way. They provide empirical cmparison of this new inequalities with the existing concentration inequalities such as kl-inequality, Empirical Bernstein inequality and Unexpected Bernstein inequality. They show that their new inequality is tighter than all of these inequalities in some regimes.\n\nThey further extend their contribution to PAC Bayes setting and derive PAC-Bayes-split-kl inequality. Again, they empirically (in synthetic and real world data) identify regimes where their inequality performs better than other existing inequalities such as PAC-Bayes-kl, PAC-Bayes Empirical Bernstein, PAC-Bayes Unexpected Bernstein, and PAC-Bayes Empirical Bennett inequalities.", "questions": "- Can you add some experiments to show the dependency of the bound on choice of $\\mu$?\n- It would also be helpful to discuss the tighntness of various bounds as we increase n.\n", "limitations": "The limitations are discussed adequately.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper is easy to follow and claims stem from logical arguments. The experiments are extensive and support the claims made by authors. Theoretically, the idea is simple but interestingly, it leads to good empirical results.\n\nWeaknesses:\nIt is difficult to understand that how is this new inequality fundamentally different than the kl inequality. Without a careful choice of $\\mu$, I am not sure if this new inequality would always be tighter than kl inequality in all the regimes. My observation comes from the following argument: consider Z $\\in [a, b]$. Take $\\mu = a$, then $Z^+ = Z-a$ and $Z^- = 0$. Similalry, take $\\mu = b$, then $Z^+ = 0$ and $Z^- = b - Z$. In both these cases, we are just translating Z and both kl inequality and kl-split inequality should behave similar for these choices of $\\mu$. Of course, there might be a clever choice of $\\mu$ which makes one perform better than the other but I am not sure how to make that choice.   \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AfiSdGZind", "reviewer": "Reviewer_vwKX", "summary": "The paper introduces a new concentration inequality for the sum of iid bounded random variables.  \nThe paper uses a  technique of splitting the samples with a threshold and then using a kl-inequality on each part.  This splitting allows using both the lower and upper bound kl-inequalities. \nThe resulting bound enjoys both the tightness of the kl-inequality and the ability to exploit the lower variance of r.v. that takes values within a segment.\nThe empirical comparison clearly shows how the tightness of the new split-kl bound in different regimes, compared to the empirical Berenstein and the standard kl inequalities.\n\nThe paper then derives PAC-Bayes-Split-kl inequality\nand applies it to the excess loss of a binary classification problem.\nThe new bound exploits the lowered variance of the excess losses compared to the binary losses, and therefore, the overall split-kl-PB bound can be competitive with the standard kl-PB bound, as demonstrated on synthetic and real-world data.\n", "questions": "No additional questions", "limitations": "No additional limitations", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n### Strengths\n1. I believe the work is original and well-motivated.  \n2. The use of the splitting technique is clever and novel, as far as I know.   \n3. The paper is well-written and clear.\n4. The authors provide an adequate survey of related work.\n5. The empirical evaluation of the split-kl inequality clearly shows its merits.\n\n### Weaknesses\n1. The empirical evaluation of the split-kl-PAC-Bayes bound does not seem to give definitive conclusions, besides the looseness of PAC-Bayes-Empirical-Bennett on certain datasets.  I suggest adding more controlled synthetic experiments, as were done in Fig 1. for the concentration bounds since it can give good intuition to when certain bounds are preferable. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "16VjHPwOpBj", "reviewer": "Reviewer_5fcJ", "summary": "The authors address the question of providing PAC-Bayes bounds for losses when the (empirical) variance is low, as previously addressed by e.g. [1, 2].\n\nA special case of this is finding bounds for ternary losses in {-1,0,1}, which arises in two important ways:\n1. bounds on the excess misclassification loss, which can also be used as per [1] to tighten PAC-Bayes bounds on the non-excess loss\n2. in conjunction with the Cantelli-Chebyshev relaxation given by [3] to provide bounds on the (non-randomized) weighted majority vote via PAC-Bayes.\n\nFor losses in {0, 1} the small-kl PAC-Bayes bound [e.g. 4] is usually the tightest, even when the variance is low, but not for losses in [-1, 1] (after rescaling the bound). In order to leverage this, the authors decompose translate each random variable in the sum before decomposing it into positive and negative parts,\n$$Z_i = \\mu + Z_i^+ Z_i^- = \\mu + \\max(0, Z_i-\\mu) + \\max(0, -Z_i+\\mu)$$\nbefore applying the small-kl bound to the sums of $Z_i^+$ and $Z_i^-$ separately (which are both {0, 1} valued in the ternary untranslated case). This is called the *split-kl* (PAC-Bayes) bound.\n\nThis is used to prove new concentration and PAC-Bayes bounds. These are further combined with the excess risk and informed prior ideas from [1], or the Cantelli-Chebyshev relaxation from [3], and evaluated in experimental setups taken from the above.\n\n\n\n-----\n\n[1] Zakaria Mhammedi, Peter Grünwald, and Benjamin Guedj. PAC-Bayes un-expected Bernstein inequality.\n\n[2] Ilya Tolstikhin and Yevgeny Seldin. PAC-Bayes-Empirical-Bernstein inequality.\n\n[3] Yi-Shan Wu, Andres Masegosa, Stephan Lorenzen, Christian Igel, and Yevgeny Seldin. Chebyshev-cantelli pac-bayes-bennett inequality for the weighted majority vote.\n\n[4] John Langford. Tutorial on practical prediction theory for classification.\n\n\n----\n\nUPDATE:\n\nOverall I am not satisfied with the quite limited evaluation of this bound, which does not show clear improvements from previous results. This weakens the motivation for the paper too because of the limited number of new technical ideas.\n\nTherefore I find myself much more on the borderline than my original review and I do agree with some of the criticisms of reviewer nL9t. However, given that related work has previously appeared at NeurIPS with similarly negligible empirical improvements, I will keep my \"weak accept\" score.", "questions": "1. Is the bound stated in Theorem 3 equivalent to the different form given by [1]? It would be nice to show this.\n2. In the experiments in section 4.2, it seems all of the bounds are based on the Cantelli-Chebyshev relaxation (with the tandem bound being $\\alpha = 0$). Why have you not also compared to other bounds for the weighted majority vote, in particular the first order bound $L(MV) \\le 2 L(\\rho)$ with the small-kl, which is often the tightest?", "limitations": "N/A the results are primarily of a theoretical nature.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n**Clarity and motivation**: the paper is very well written and was a pleasure to read. The relationships to previous works [1, 2] was very well explained and the incorporation of ideas from [1] was well motivated. The alternative form of the main result from [1] is an improvement in clarity to how it is stated therein and the situation of this work within its wider context was reasonably clear. My only minor criticism is that the experiments in section 4.2 do not sufficiently explain the use of the Chebyshev-Cantelli bound and majority votes as used there. This is a shame as I think the use of the split-kl bound for majority votes is a good use case.\n \n**Relevance**: I think that the paper makes a contribution to an important and highly-active area of machine learning, improving PAC-Bayes bounds, which are among the most useful in contemporary learning theory. They bring some ideas from [1] to a wider application which is a valuable contribution.\n\n\n### Weaknesses\n\n**Technical contribution and originality**: here I think the paper falls down a bit. The main technical result is simply a decomposition of a random variable into positive and negative parts, combined with an application of the small-kl PAC-Bayes inequality. This is combined with the excess loss idea from [1] and the experimental setup therein, or the Cantelli-Chebyshev bound from [3] and their experimental setup, all of which is straightforward. Such simple ideas are can be very valuable when they lead to breakthroughs but that does not seem to be the case here, and most of the ideas used in the paper and discussed at length were originated by [1].\n\n**Experimental results**: in the more important PAC-Bayes setting the new results are quite weak, with the new bound giving very similar results to that of [1]. The bound is not shown to be any improvement as optimization objective either. The simpler concentration inequality setting is not particularly interesting except as a motivation, and for the ternary r.v.s used an even better bound would be obtained by applying the test set bound (Th. 8) to the decomposition $Z = Z^+ - Z^-$ (i.e. a \"split-Binomial\" bound).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept