On Margins and Generalisation for Voting Classifiers
Authors: Felix Biggs
Valentina Zantedeschi
Benjamin Guedj
Venue: NeurIPS 2022 Accept (2022)
Keywords: PAC-Bayes
Generalisation bounds
Ensemble learning
Margins
Majority votes
Aggregation of experts

Abstract: We study the generalisation properties of majority voting on finite ensembles of classifiers, proving margin-based generalisation bounds via the PAC-Bayes theory. These provide state-of-the-art guarantees on a number of classification tasks. Our central results leverage the Dirichlet posteriors studied recently by Zantedeschi et al. (2021) for training voting classifiers; in contrast to that work our bounds apply to non-randomised votes via the use of margins. Our contributions add perspective to the debate on the ``margins theory'' proposed by Schapire et al. (1998) for the generalisation of ensemble classifiers.

On Margins and Generalisation for Voting Classifiers
Felix Biggs
Valentina Zantedeschi ServiceNow Research, University College London and Inria London Shantedeschi@gmail.. com
Department of Computer Science University College London and Inria London contact@felixbiggs.co
Benjamin Guedj
Department of Computer Science
University College London and Inria London b. au.l.ac.c.k..
Abstract
We study the generalisation properties of majority voting finite ensembles of classifiers, proving margin-based generalisation bounds via the PAC-Bayes theory. These provide state-of-the-arr guarantees on number of classification tasks. Our central results leverage the Dirichlet posteriors studied recently by Zantedeschi et al. (2021) for training voting classifiers; in contrast to that work our bounds apply to mon-randomised votes via the use of margins. Our contributions add perspective to the debate on the "margins theory" proposed by Schapire al. (1998) for the generalisation of ensemble classifiers.
Introduction
Weighted ensemble methods are among the most widely-used and effective algorithms known in machine learning. Variants of boosting (Freund and Schapire, 1997; Chen and Guestrin, 2016)
state-of-thed of-the-art in a wide variety of tasks (Shwartz-Ziv and Armon, 2022; Nielsen, 2016) and methods such random forest (Breiman, 2001) are among the most commonly in machine learning competitions (see, e.g., Bell and Koren, 2007; Uriot et al., 2021), valued both for their excellent results and interpretabilityy Even when these algorithms do not directly produce the best learners for task, the best performance competitions often obtained by an ensemble of "strong learners"- the output of a collection of different algorithms trained the dota-ecot the weak learners usually considered in the ensemble learning literature.
Among the oldest ideas explain the performance of ensemble classifiers, and machine learning methods in general, is the concept of margins. First introduced to analyse the Perceptron algo- rithm (Novikoff, 1962), margins relate closely the idea of confidence in predictions in ensemble learning, with large margin implying that a considerable weighted fraction of voters chose the same answer. This first leveraged to obtain early margin-based generalisation bounds for ensembles by Schapire et al. (1998), in an attempt to understand the excellent generalisation surprising result given classical Sappik-Chervoneeee further in a number of works (Wang et al., 2008; Gao and Zhou, 2013; Grønlund et al., 2020) and is among the leading explanations for the success of such methods and boosting in particular.
boosting, a theory. This "margins theory" was explored
The same thread of margin bounds for ensemble methods has also been taken up in parallel in PAC-Bayes theory by Langford and Seeger (2001); Biggs and Guedj (2022b). PAC-Bayes provides a natural framework both for deriving margin bounds, and for considering ensemble methods in general, particularly majority votes where the trggestweeighter ensemble prediction is taken. Within
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the framework, the weightings are typically considered as the parameter of categorical distribution over individual voters. PAC-Bayes theorems (see the comprehensive surveys of Guedj, 2019; Alquier, 2021) then directly provide generalisation bounds for the performance of this "randomised" proxy for the majority vote, a.k.a. Gibbs classifier. These can then he de-randomised by such margin- techniques, or through a variety of oracle bounds (Langford and Shawe- Taylor, 2003; Shawe- Taylor and Hardoon, 2009; Lacasse al., 2010; Masegosa et al., 2020), motivating new learning algorithms (Lacasse et al., 2006; Roy et al., 2011; Germain et al., 2015; Laviolette et al., 2017; Lorenzen et al., 2019; Viallard et al., 2021; Wu et al., 2021).
Uniquely among PAC-Bayesian approaches, Zantedeschi et al. (2021) instead consider Dirichlet distributions over the voters. Any sample from this distribution already implies a vector of voting weights, and it is on the performance and optimisation of these "stochastic majority votes" they primarily focus. As an aside, they provide an oracle result which allows their bounds to be de- randomised, but this introduces an irreducible factor such that the bound on the true fixed vote can never be less than double that of the stochastic version. It also neglects to leverage the generally high confidence of predictions obtained by their algorithm.
Our contribution. By combining tools from margin bounds and the use of Dirichlet majority votes, we provide a new margin bound for non-randomised majority votes. This is in contrast to Zantedeschi et al. (2021) which primarily considers stochastic majority votes. Our bound empirically compares very favourably to existing margin bounds and in contrast to them are applicable to multi-class classification. Remarkably, our empirical results are also sharper than existing PAC- BaCyasaaa ones, even when the algorithm optimising those bounds is used.
Our primary tool is new result relating the margin loss of these stochastic votes the misclassifi- cation loss of the non-randomised ones in a surprisingly sharp way. This tool can additionally be utilised alongside a further idea from Zantedeschi al. (2021) to obtain an alternative form of the bound which is more amenable to optimisation. Through this work we provide further support to the margins theory for ensembles, showing that near-sharp bounds based on margins alone can be obtained on a variety of real-world tasks.
Outline. The rest of this section introduces the problem setup, notation and summarises main results. Section provides background on PAC-Bayes, Dirichlet majority votes and margin bounds, relating them to our new results. Section 3 states and summarises our new theoretical results, giving the most relevant proofs (all remaining proofs are deferred to appendices). Section 4 empirically evaluates these new results before we conclude with an overall discussion in Section 5.
1.1 Notation and setting
Majority voting algorithms combine the predictions of a finite set of "base" classifiers, H. from X' to y'= [c] = {1, .1.....c.. c}. The classifiers h2 E H. take the form h; : X' + y for i E [d] so that [7d] d. Majority votes consider set of weightings 0 in Ad, the simplex, and return the highest-weighted overall prediction. Using the indicator function IA of a set A, this is expressed as
fo( argmax
Σ (c)n EE|d]
KEY
We are primarily interested in learning a weighting O with small misclassification risk (and guarantees of this) based on a sample S ~ DDM, where D E MM (X' x )) is the data-generating distribution and m E N+ the sample size. We let M (.A) denote the set of probability measures on set A.
For h E H the misclassification loss is Eu (h, x2, y) := In( the misclassification oft-lee risk is [n( = (eo,)>/Co(h,,,, y) and a hat denotes the in-sample estimate of this quantity, (h)h) == [ne.e))- (0, x, v.). In a slight abuse of notation we will also often write the risk of the majority vote (0) = To (fo) and similarly for its empirical counterpart.
The margin of majority vote fo on example (xr, v) is derived from the minimal gap between the total weight assigned to the true class y and to any other predicted class:
M I, v) = 2
Σ
0
max KED
Σ O..
2
8sh, (x),
(b)(

---

The corresponding margin loss is (0,,,))) := Ias(O.a.9) for margin 2 0, with the correspond- ing in-sa and out-of-sample risks notated as [, and (0) respectively.
1.2
Overview of results
Our main result is a margin bound of the following form: with high probability 2 1 8 over the sample, simultaneously for any 0 A and K O,
L( so (L,, + teee Ky² e-K + DDO 1) log
(I)
m
where (a,, is the KL divergence between Dirichlet random vectors with parameters and B3 with 1 vector of ones implying a uniform Dirichlet prior distribution on the simplex. The term --Kn is de-randomisation penalty, The parameter is chosen freely in an arbitrary data-dependent way to balance the requirements of the different terms: it must be large enough to decrease this exponential term, while too-large parameter increases the KL divergence from the uniform prior. This result is surprisingly strong; in particular there is dependence on the dimensionality (i.e., number voters d) in the exponential term, an advantage discussed further in Section 3.2.
In Equation (I), L, (0) is the 0-1 valued y-margin loss which enables comparison with existing margin bounds for trained weighted ensembles. We further consider second scenario, where the generalization bound is also used to train the model itself. We note that the 7-margin loss L,, (0) appearing in Equation (1) has null gradients, so the bound cannot be directly optimised by gradient descent. To rectify this we also prove variation of the bound, replacing the above loss by its expectation under Dirichlet stochastic vote, Eg-Dir( (e)) L,, which is bounded in differentiable closed form to give an alternative, optimisationn-fiennlly bound.
In our evaluations we focus on these two complementary scenarios, obtaining state-of-the-arr em- pirical results. Across different scenarios and tasks our results outperform both existing margin bounds (including sharpened version of the result from Biggs and Guedj (2022b) which may be of independent interest), and PAC-Bayes bounds, even when it is not used as the objective. Further, in contrast to existing margin bounds our results also hold for multi-class majority votes.
2 Background
2.1 PAC-Bayes bounds
PAC-Bayes bounds are among the tightest known generalisation bounds, as for example the only framework in which non-vacuous generalisation bounds for neural networks have been obtained (see e.g. Dziugaite and Roy, 2017, 2018; Zhou et al., 2019; Letarte et al., 2019; Dziugaite et al., 2021; Perez-Ortiz et al., 2021; Biggs and Guedj, 2021, 2022a). However, unlike many other such bounds they usually apply to randomised Gibbs(-like) prediction functions rather than deterministic ones. These are typically re-drawn for every new test evaluation. Thus a high-probability bound is obtained on the expectation of the risk w.r.t the PAC-Bayes posterior Q, with the complexity of Q M (H) appearing in the bound in terms of a Kullback-Leibhe prior P E .M (H) (which is not required be true prior in the Bayesian sense see the discussion in Guedj, 2019). A particularly sharp (as discussed in Foong et al., 2021) and widely-used result is given in Theorem 1, valid for any bounded loss function l with values in [0, 1].
(KL) divergence from a pre-chosen Bayes
Theorem 1 (Seeger et al. (2001); Maurer (2004)). For any D MM (X' x 3²), m E N4. prior P. Mt (H) and 8 E (0, 1), with probability 2 ò over S ~ D", simultaneously for all Q Q{M)(H)
En~oL(h) < -1 (EnnQ((h),
1 [K(QQ,)) log 2/m m
where the generalised inverse kl kl (u, sup(u E [0, kl(u,v) S c) and kl(u, v) == u log _ + (1 u) log --y is a KL divergence between Bernoulli random variables.
The above bound uses the inverse small-kl function which will be seen in our later results and number of pre-existing ones. To lend intuition we note that kl (u,c) c) Olu + c), giving
3

---

Equation (1) from Theorem 2 when using a uniform prior. The following upper bounds are also usefuul kl kl (u, c) S u + cc2 giving "slow-rates" and ki (2, (u, & u + V2eu + 2c. From this we can see that when the loss i - 0 then the overall rate improves ((1/m)) so the small-kl formulation interpolates between the traditional fast and slow rate regimes of learning theory.
2.2 Margin bounds
In the learning theory literature there exists rich tradition of using the concept of margin, which quantifies the confidence of predictions, to explain generalisation. This is particularly evident the case of voting algorithms such as boosting, where traditional Sapnik-Chervonenkis based techniques predict classical overfitting which is not ultimately observed. The "margins theory" was developed by Schapire al. (1998) explain this discrepancy. By considering the weightings O as the parameter of a categorical distribution, they proved a bound of the form (holding with probability greater than
- å over the sample, as for all bounds this section) (0) S (0) + Ô 7 Although there was initially some debate about the validity of the theory (Breiman, 1999), eventually Gao and Zhou (2013, Theorem 4) provided the following improved bound which further supported that a large-margin voting classifier could generalise: simultancously for any y > /2/d and Ad,
1 (2log(2d)) (o < k1'' (L) m 72
(2logp/ log
log d 8 )) log
2m2
dm
+ log
(2)
More recently, similar bound (proved through PAC-Bayesian method based on Seeger al. (2001)) was proved in Biggs and Guedj (2022b, Theorem 8). Here we give a bound provided as an intermediate step their proof that strictly (and empirically considerably) sharper than their final result: for any fixed margin >> O, simultaneously for any O E A
(o) < kl
(,
(127 log ml log d + log
2/m
))+
1 m71
Since 7 E (0, ( for non-vacuous results, union bound argument can be used to extend the above fixed-precision y, and this result has the advantage of being valid for small ry as are often observed empirically.
Our contributions. Firstly we mention the smaller contribution of the improved form of the bound from Biggs and Guedj (2022b) given in Equation (3); proof is given in Appendix B alongside further refinements and evaluation. However we show that in many cases even this improved version and Equation (2) give weak vacuous results. As result of this weakness (and thus perhaps null result for the margins theory applied to voting classifiers) we present a new margin bound in Theorem based on Dirichlet distributions
theoretical intermediate step. This is also valid in the multi-class case, unlike the above results which are only for binary classification. Empirically the bound is observed to give enormous improvement in tightness than the existing margin bounds and in some cases is near-sharp.
2.3 Dirichlet stochastic majority votes
In most results from the PAC-Bayes framework, and in the proof of the existing results given in Section 2.2, the majority vote weightings 0 are considered the parameters of a categorical distribution over voters. Zantedeschi et al. (2021) instead consider PAC-Bayesian bounds (specifically, Theorem applied to a hypothesis class of majority votes of the form Je- where & ~ Dir(a)) is drawn from Dirichlet distribution with parameter a. This distribution has mean Eę a Σd ag with larger sum Σ a; giving more concentrated or peaked distribution (see Appendix A for more details).
Since g is randomised, the bounds from Zantedeschi et al. (2021) apply to "stochastic majority votes" rather than the more typical deterministic ones we consider here. However, the use of such Dirichlet distributions over voters in the PAC-Bayes bounds rather than the more usual categorical ones is major step forward as it allows the correlation between voters to be more carefully considered. This is because with categorical distribution, the expected Gibbs risk is simply average of the losses of individual predictors, without taking into account how well the combination of their predictions performs. Conversely, the Dirichlet distribution gives a (stochastic) majority vote of predictors, so if

---

the errors of base voters are de-correlated, the better performance that results from their combination can be accounted for in the bound. We will utilise and de-randomise these stochastic majority votes as stepping stone to bounds for deterministic predictors fo directly.
As is common in the PAC-Bayes literature, Zantedeschi al. (2021) use their new bound as an optimisation objective to obtain a new algorithm, here using stochastic gradient descent. The bound with Dirichlet posterior obtained directly from Theorem includes the expected misclassification loss with respect to the Dirichlet parameters, Diria) {[e, I, y). which has null gradient for any sampled &. They therefore additionally upper bound this term by the differentiable closed form
Σ CS Σ 04
())
(chx())=v
where (a b) is the regularised incomplete beta function, which has sigmoidal shape. The inequality is sharp in the binary classification case, and is used in the training objective and final evaluation of their method. As an aside, Zantedeschi et al. (2021) also proved an oracle bound which allows their result to be de-randomised, but this introduces a irreducible factor of two. This bound, which holds with probability least 1-5 over the sample for any Ad, K > is given by
Lo(O) S 2k11 Lo(E)) Di (KD, () + log 2
m
margin bound for majority vote algorithms utilising Dirichlet posteriors as a theoretical stepping stone. We show that this bound gives sharper bounds on the misclassification loss than the bound from Zantedeschi et al. (2021), doing better than the irreducible factor, even when applied to the output of their algorithm. We show further that the bound is also tighter when applied to the outputs of other PAC-Bayes algorithms derived from "categorical"" type posteriors. Finally, we give an altered form of the bound involving the expectation of the margin loss ( ( x. y) and result analogous to Equation (4) for this case. Through this able to obtain a new PAC-Bayes objective which is compared to existing PAC-Bayes optimisation methods.
Our contributions. Firstly, we provide
3
Main results
Our main results use the idea of Dirichlet stochastic majority votes from Zantedeschi et al. (2021) as an intermediate step to prove new margin bounds for deterministic majority votes. In this section, first we give our main result in Theorem 2 and discuss further. In Section 3.1 we give an alternative bound obtained by a very similar method which more amenable optimisation, and we provide proofs for these results in Section 3.2.
The central step in these proofs is in constructing proxy Dirichlet distribution & ~ Dir( (ir(K)) over ers, the loss of which is bounded à la PAC-Bayes, and de-randomised using margins to obtain bounds directly for fe. The primary complexity term appearing in our bounds is therefore Dir (K0, ,3), the KL divergence between Dirichlet distributions with parameters K0 and / respectively. As with PAC-Bayes priors, 3 can be chosen arbitrary cample-independent fashion, but we typically choose it as a vector of ones, giving a uniform distribution on the simplex as prior as in Equation (1). The bounds also involve a de-randomisation penalty of Oee-Kr²) where 7 is the margin appearing in the loss: this term upper bounds the difference between our randomised proxy & and its mean 0 and gets smaller with K as the distribution concentrates tightly around its mean. This parameter K can be optimised in any data-dependent way to obtain the tightest final bound.
Theorem 2. For any DD E MI (X x Y), m N+, margin 7 > 0, 5 (0, and prior B Rd. DD simultaneously for every O E A and K
with probability at least 1 8 over the sample
(,( + ee (K++)) [DD, 3) + log
(o) S -1
+ te- (K++))?
Theorem 2 differs from the existing margin bounds of Equations (2) and (3), and Schapire et al. (1998) in specific and significant way, with 0 appearing not only in the loss function (,) but also
5

---

in the KL complexity term. Empirically we find our bound to be an improvement but it is possible generate scenarios where the pre-existing bounds are vacuous while ours not, since the KL divergence is unbounded for certain choices of 0, for example when one of the components is exactly zero. This difference arises because the existing bounds all use the idea of categorical distribution with parameter & in their proofs (which has KI. divergence from a uniform prior upper bounded by log d), while we use Dirichlet. This gains us the surprisingly tight de-randomisation result (Theorem 4) used in all proofs.
3.1 PAC-Bayes bound as objective
We note here that it is non-trivial directly obtain training objective for optimisation from Theorem 2, due the non-differentiabiiiy of the margin loss (0). Therefore, in order compare results with a wide variety of methods that optimise PAC-Bayes bounds (including those used by Zantedeschi et al., 2021, as baselines), obtain relaxed and differentiable formulation in Theorem for direct optimisation.
Theorem 3. Under the conditions of Theorem 2 the following bound also holds
(E,),, Diir (K0,
log"
2y/m
(0) S <k1-1
4(K+1)>
m
Using the incomplete Beta function 1 (a, b) we also have the following result, which is sharp in the binary classification case,
E 1+
Σ
Qity
02
(h:(z)mg
(1)
Theorem has a stronger PAC-Bayesian flavour than Theorem 2, with an expected loss under some distribution appearing (complicating the final optimisation of K), while Theorem takes form much closer to that of a classical margin bound. The second part of the result is analogous to Equation (4) used by Zantedeschi et al. (2021). We combine both parts to calculate the overall bound in closed form and obtain gradients for optimisation.
3.2 Proof of main results
The proof of Theorems 2 and essentially follow from applying a simple PAC-Bayesial bound in combination with the key Theorem below. In some sense this is our most important and novel result. Our whole approach is largely motivated by its surprising tightness; in particular there is no dependence on the dimension, which is avoided by careful use of the aggregation property of the Dirichlet distribution. This surprise arises because obtain tightly concentrated Dirichlet distribution on & Dir(a), the concentration parameter K Di= Og must grow linearly with the dimension. In fact, even uniform distribution (which will be less peaked than final posterior) has Een ai d, so the de-randomisation step is effectively very cheap higher dimensions.
Theorem 4. Let A and K > Then for any 7 0 and (ar, v).
Eo 3) Ee Dir(Ko C, (E, E EgD
e- 1(++))?
v, (5. < ez, (0, 3) + {(++))
For our proofs we first recall the aggregation property of the Dirichlet distribution: if (EI....,Ea) Ea) ~ Dir((ai,...,.a.) aa)). then (EI...., Ea) Dir((a1,.... Qd-1 (42
az)). We further note the result. The aforementioned lack of dimensionality in Theorem 4 is possible because Theorem 5 depends only Σd ag and this value is unchanged by aggregation, which avoids the dimension dependence that would otherwise be introduced by the requirement |ull2 below.
following crucial dottentraaiion-o-mmaass
Theorem 5 (Marchal and Arbel, 2017). Let X Dir(a)), t O, and IRd with ||u||2 1. Then
d ai 1) (2)
Px {u (X - EX)= f S exp -2
Σ i=1

---

Proof of Theorem 2 and Theorem 3. The proof of our main results is completed by applying the PAC- Bayes bound Theorem 1 with the y-margin loss Dirichlet prior and posterior with parameters / and K' respectively. Substituting the first part of Theorem 4 gives the first part of Theorem 3, and additionally substituting the second part and re-scaling 7 - 7/22 gives Theorem
For the second part of Theorem 3, define w = {i: (₂(2)) = y} for fixed (I, v) so W := Eiew Ei ~ Beta (Eiew at Eigur ai) by the aggregation property of the Dirichlet distribution. Then
(g, S Be W
1 7) 2 2
-7
4--
Σ JEW
ajj
Σ
ojj
1 ++4
Σ aj. oj
Σ
iEW
using La max-ma 52y S La.-E - Dn 2,22y 1 Ln classes), and that (a, 6) is the CDF of a Beta distribution with parameters (a, b).
for a E A (with equality for
Proof of Theorem 4. Define 7/2 > 71 such that y == 72- - n, and a = KO. From the trivial inequality LEAA LEEB I L we derive
= ln (0, x. y) - De To (5, = ( - INEeawss
$ EE-Din(a) [M S (M( S (M
= (e-Dir(a)
Σ
E
max 1'
Σ &
Σ
0 + max
Σ
8 > 24
iskelx)=y
ich((r)=k/
ich((=)=y
idh(())=k
S PE-Dir(a)
Σ &
Σ (
&
Σ
> 27
(
ishu (x)=k
where in the last inequality we set k: = k (n Os, and use that maxy Een,(n)= 0, max, Ean(())= & I max, Ean,(()- 0: Emm(())= & for any k. We rewrite the above in vector form (with inner product denoted u -v) as
Σ (x) & (2) Ei (o) Et.
Σ (o) O, E Eandtr O, 1) V2T }
A < (E-Dir(a)
(00 2
V2
BE
= PF -PE-Di(())
u (é- -E)== > v
where by the aggregation property of the Dirichlet distribution E ~ Dir(ā) with
ā = Σ ais
Σ ais
Σ
( k
Applying Theorem 5 we obtain A < e EE 1) = 4( +1 This gives the first
inequality by setting 71 = 0, 72 = 7. Setting 71 72 = 2y and swapping and & gives an almost identical proof (with some signs reversed) of the second inequality.
4 Empirical evaluation
In this section we empirically validate our results against existing PAC-Bayesian and margin bounds on several classification datasets from UCI (Dua and Graff, 2017), LIBSVM and Za- lando (Xiao et al., 2017). Since our main result in Theorem 2 is not associated with any par- ticular algorithm, we use O outputted from PAC-Bayes-derived algorithms to evaluate this result
'nttps://www csie. ntu, edu. tw/ ww/"cjiin/libvv
7

---

against other margin bounds (Figure 1) and PAC-Bayer bounds (Figure 2). We then compare op- timisation of our secondary result Theorem 3 with optimising those PAC-Bayes bounds directly (Figure 3), All generalisation bounds given are evaluated with probability 1-8=0.95. Further details not provided here including tabulated results, description of datasets, training mechanisms and compute are provided in Appendix C. The code for reproducing the results is available at https: thub. wooo///aatteeschi/iiiiiiee httrrrrirrrecrrerrr..ee -boudd
Strong and weak voters. Similarly to Zantedeschi et al. (2021) we consider both using data- independent and data-dependent voters. This brings our experimental setup in line with common workflow for machine learning practicioners: the training set is sub-divided into set for training several different strong algorithms, and a second set on which the weightings of these are optimised. More specifically, the weak voter setting, used only for binary classification, uses axis axis-aligned decision stumps (denoted stumps), with thresholds evenly spread over the input space (6 per feature and per class). The stronger voters (denoted rz') are learned from half of the training data, while the other half used for evaluating and optimising the different generalisation bounds (note this reduces m). These take the form of random forests (Breiman, 2001) of M=10 trees optimising Gini impurity score on 2 bagged samples and vdl drawn features for each tree, with unbounded maximal depth.
Optimising y and K in bounds. In reporting margin bounds we optimise over a grid of margin y values in (0, 2), and additionally over K for Theorem 2. Since Theorem 2 and Equation (3) as stated require a fixed margin, we apply a union bound over the values in the grid, replacing 0 in these bounds with 5/N where N is the number of grid points.
Existing PAC-Bayes bounds. We compare offte-of-the-art PAC-Bayesian bounds (and derived algorithms) for weighted majority vote classifiers: the First Order (Langford and Shawe- Shawe-Taylor 2003), the Second Order (Masegosa et al., 2020), Binomial (Lacasse et al., 2010) (with the number of voters set to 100) and the two Seebyshev-Cantelli--ee categorical-type Gibbs classifiers with parameter O. and we refer to these as FO, SO, Bin, CCPBB and CCTND respectively (more details are given in Appendix C). We denote by f2 the factor two bound derived in Zantedeschi et al. (2021, Annex A.4) from Dirichlet majority votes. All prior distributions for PAC-Bayes bounds, including ours, are set to uniform. We also refer by the same names to the outputs of optimising these bounds with stochastic gradient descent; details on training and initialisation are given in Appendix C.
(Wu et al., 2021) empirical bounds from
Description of figures. In Figure 1 we compare Theorem 2 with the existing margin bound of Equation (2) and the improved Biggs and Guedj (2022b) bound given in Equation (3). Since Equation (3) is strictly better than the original result and the latter was vacuous in almost all cases considered (see Appendix B), we do not include it. All datasets are for binary classification as the existing results only cover this case, and the 0 values considered are the outputs of either the FO- or 12- 12-optimisation using either the weak or the strong voters described above. Figure 2 extends this evaluation of Theorem 2 to improve generalisation results, by applying it to the models optimised with the PAC-Bayes bounds FO, SO, Bin and f2 as objective. In this case, we consider both binary and multiclass datasets. In Figure 3 we directly compare the outputs of optimising state-of-the-ee PAC- AAC-Bayesian bounds with our optimisation-reat
variant result Theorem 3. These experiments were carried out on strong voters, as standard in the literature (e.g. Lorenzen et al., 2019; Masegosa et al., 2020; Wu et al., 2021).
5 Discussion and conclusion
We observe overall that in many cases the existing margin and PAC-Bayes bounds are insufficient to explain the generalisation observed, while our new bound is consistently tight, and sometimes sharp (i.e. it approaches the true test error).
Figure demonstrates that existing margin bounds can be insufficient to explain the generalisation observed, which could be construed as null result for the "margins theory". However, our new bound obtains empirically very sharp results in almost all cases, reaffirming to the theory. Note that due to the non-convexity of our bound, the reported values are local minima and can potentially be improved by applying a thorougher search for the optimal K, still giving a similarly valid bound. For instance, simply by enlarging the search space for K our bound drops to 0.36 + 00 on ADULT with decision stumps as voters, beating existing bounds also in this setting. Unlike the existing results, also arises in the complexity (KL divergence) term and so the bound is not equally tight for every 0 at
8

---

HABERMAN
TICTACTOE
ADULT
CODRNA
MUSHROOMS
Decision Soumps Random Forest
1.00
0.75
0.50
025
025
0.00
G2
8G
ours
test-er
GZ
BG+
ours
best-er
G2
8G
ours
test-err
GZ
BG+
ours
test-er
G2
8G+
outs
test-er
GZ
8G
ours
test-err
G2
8G+
ours
test-or er
G2
8G4
ours
test-er
8G+
aurs
best-r
GZ
8G+
ours
test-er
Figure I: Theorem 2 (ours) compared with the margin bounds of Equation (3) (BG+), Equation (2)
(GZ), and the test error. Settings are rf (first row) and stamps (second row) on the given datasets, with 0 output by optimising either FO or f2 (first and second column groupings respectively).
PROTEIN
FASHION-MNIST
HABERMAN
TICTACTOE
ADULT
0.50
0.25
0.00
MNIST
CODRNA
PENDIGITS
SENSORLESS
MUSHROOMS
original
ours bound test-arror
Bin
2
PD
12
PD
5D
Bin
12
Figure 2: Theorem (our bound) compared with the bounds of FO,SO, Bin or f2 (original bound), and test errors. For each column grouping, is the output from optimising the corresponding PAC- Bayes bound (as named underneath) for rf the given dataset. The blue column is the final value of the bound used as objective, the green is the test error, and the orange is the value of our bound when 0 is plugged into it (so that our bound is not used as objective here).
fixed margin loss. Further examination of this property could add additional nuance and perspective to the theory.
When comparing to existing PAC-Bayes bounds in Figure 2, remarkably Theorem 2 is always tighter than just using the bound which is being optimised. We speculate that this arises partially due the irreducible factors appearing in those bounds; for example the FO or f2 bounds can never be tighter than twice the train loss of the associated Gibbs classifier, while ours has such limitation. This result is quite valuable as it demonstrates that Theorem 2 can be readily used in an algorithm-free manner: the choice of learning algorithm up to the practitioner, but the bound will then often provide an excellent guarantee on the obtained weights O.
Finally, in Figure 3, our optimisation- frienndlrri variant bound Theorem 3 is seen to be competitive in terms of test error while giving an improved-or-equal final bound on all datasets. When considering the less-common setting of binary stumps (see Appendix C) we found that sometimes this objective converged to a sub-optimal local minimum. We speculate that this arises due to the highly non-convex nature of the objective combined with strong K-inflating gradient signal from the O K term. Thus future work to improve these results even further could start with the use the quasi-convex small-kl -l relaxation from Thiemann al. (2017). We note however that this is overall less important than our main results, as both our bounds are still extremely tight when used in an algorithm- free way and applied to the output of another algorithm as discussed above.

---

PROTEIN
FASHION-MNEN
HABERMAN
TICTACTOE
ADULT
0.25
0.00
MNIST
CODRNA
PENDIGITS
SENSORLESS
MUSHROOMS
Fest
emrr
0.2
0.0
80
Bin
CCPBB
CCTND
f2
ours
PD
so
Bin
CCpa8
CCTNO
f2
ours
FO
50
Bin
CCPBB CCTMD
f2
ours
Fo
so
Bin
CCPBs CCTND
aurs
Fo
CCPBB CCTMD f2
ours
Figure 3: Theorem 3 (ours) as optimisation objective compared to other PAC-Bayes results (FO, SO,
Bin, CCPBB and CCTND) as objectives in the rf setting. For each objective the test error and bound associated with the objective is shown.
Overall, we note that in many cases (a majority in Figure 2) our main bound of Theorem 2 is very close the test set bound and thus cannot actually be improved any further, with the problem of providing sharp guarantees based on the training data alone effectively solved in many cases.
Conclusion. We obtain empirically very strong generalisation bounds for voting classifiers using margins. We believe these are highly relevant to the community, since voting- based classifiers and margin-maximising algorithms among the most popular and influential in machine learning. Dirichlet majority votes have already obtained excellent results in the stochastic setting (Zantedeschi al., 2021), but our result in Theorem showing they well-approximated by their mean should open new directions in the more conventional deterministic setting.
Our results also have practical relevance: for example, in the strong voter machine learning workflow described above, instead of setting data aside as test set, this data can be freed up to learn even stronger voters, since strong out-of-sample ensemble guarantee still be provided even without test set.
In future work we hope to expand these results further to other (non-majority) voting schemes like those with score-output voters (as in e.g. Schapire et al., 1998), and ensembles of voters with finite VC dimension.
Acknowledgements
The experiments presented in this paper were carried out using the Grid 5500 testbed, supported by scientific interest group hosted by Inria and including CNRS. RENATER and several Universities as well as other organizations (see http:://www.rrd550000.. the EPSRC grant 5P//022166/11 French National Agency for Research, grant ANR-18-CES W1R-18-CFF2-0015--02 B.G. acknowledges partial support by the U.S. Army Research Laboratory, U.S. Army Research Office, U.K. Ministry of Defence and the U.K. Engineering and Physical Sciences Research Council (EPSRC) under grant number EP/R0136161 Research, grants A NNR-18-CE440-001600 and ANR-18-CE23-001550
F.B. acknowledges the support of V.Z. contributed to this work while being supported from the
B.G. also acknowledges partial support from the French National Agency for
References
Pierre Alquier. User-friendly introduction PAC-Bayes bounds. CoRR, abs/2110.11216. 2021. URL https:
//arxiv. wwwxii.org//aa...e...oooo aaaaab//2111 22100 11216.
Robert M. Bell and Yehuda Koren. Lessons from the netflix prize challenge. SIGKDD Explor. Newsl., 9(2): 75-79, dec 2007. ISSN 1931-0145. doi: 10.11455/145444.144554 URL https://// otg./............ 1145/ 1345448. 1345465.
Felix Biggs and Benjamin Guedj. Differentiable PAC-Bayes objectives with partially aggregated neural networks. Entropy, 23(10):1280 202.. doi: 10.3390/e23101280. URL https://doi. http:://dooooooo////// 10t///1..300 3390/ e3900/22000
10

---

Felix Biggs and Benjamin Guedj. Non-vacuous generalisation bounds for shallow neural networks. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 1963-1981, PMLR, 2022a. htt.htpp::/prrceeennggs mlr. pwwss/veevvveeeee /ttess//vv///////// wtv////b/aaa//// biggg22........o html.
Felix Biggs and Benjamin Guedj. On margins and derandomisation in PAC-Bayes. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valcra, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statisties, volume 151 of Pruceedings of Machine Learning Reseurch, pages 3709-3731. PMLR. 28-30 Mar 2022b. URL //tp://///p/ccecgps... mwm. wtt..mmwsm././me.eee....e..e..te
wwwpppressvviiee arress/vi5//ta wwwl///ggg2//aa....//// html.
Leo Breiman. Prediction Games and Arcing Algorithms. Neural Computation, 1((7):1493-1517, 10 1999. ISSN 0899-7667. doi: 10.1 10.11620099966993000166666
URL https://doi..rg// 1162/
089976699300066006
Leo Breiman. Random forests. Mach. Learn., 45(1):5-32, 2001. doi: 10.1023/A.101099344050 URL https://dol.oog//0...o00 http://o.0rrr/0..00001::11111100 10111323244111009344444449
Olivier Catoni. PAC-Bayesian Supervised Classification: The Thermodynamicr of Statistical Learning. Institute of Mathematical Statistics lecture notes-monograph series. Institute of Mathematical Statisties, 2007. ISBN
9780940600720, URL https: //bokks. google.
Tianqi Chen and Carlos Guestrin. Xgboost: scalable tree boosting system. Balaji Krishnapuram, Mohak Shah, Alexander J. Smola, Charu C. Aggarwal, Dou Shen, and Rajeev Rastogi, editors, Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pages 785-794. ACM, 2016. doi: 10. 00.11455/93997222933738 URL https:
//doi. org/ 10. 1 1145/ 4444/999972.... 2939785.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. http:///:/ar ict. ml.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochas- tie) neural networks with many more parameters than training data. Conference on Uncertainty in Artificial Intelligence 33., 2017.
Gintare Karolina Dziugaite and Daniel M Roy. Data-dependent PAC-Bayes priors via dif- ferential privacy. In Advances in Neural Information Processing Systems 31. pages 8430-8441. Curran Associates, Inc., 2018. 8063 depea-dependnnt--o pac- pawprddett--p--bb---------e pariios-viaddifeeeettee
URL
wtppp.ccpppper/ -df..
Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino. and Daniel Roy. On the role of data in PAC-Baaes. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 604-612, PMLR, 2021. URL. http:/t:://proceedii mlr. presspesssssee w1100/kkrrrra/ htt///arolllaaaaaaaeaaaaaaaaaaaa wewiinadddiiggeieeeeee html.
Andrew Y. K. Foong, Wessel Bruinsma, David R. Burt, and Richard E. Turner. How tight can PAC- Bayes be in the small data regime? In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 0093-4105. 2021. URL https: pettss://pue http://///oe/......//oo//r/ wewpodiiinnnnuuiippp..ee.e httpppppp//2221///2/p -wt.t---ab.............a.aaaa... html.
Yoav Freund and Robert E. Schapire. A
generalization of on- learning and application to boosting. J. Comput. Syst. Sei., 55(1):119 1399, 1997. doi: 10.1006/jcss.1997, 1997.1154, URL https:
//doi. ttt//...100//eee...eeoo
1997. 1504.
Wei Gao and Zhi-Hua Zhou. On the doubt about margin explanation of boosting. Artif. Intell., 203:1-18, 2013. doi: 10.1016/j.artim wrt.:ijaartinnt113.....o URL https: / http///ti.oo/o///////// 1016/ tortiitt.2111 00022...........
Pascal Germain, Alexandre Lacasse, François Laviolette, and Mario Marchand. PAC-Bayesian learning of linear classifiers. In Proceedings of the 26th Annual International Conference on Machine Learning ICML '09, pages 1-8, Montreal, Quebec, Canada, 2009. ACM Press. ISBN 978-1-60558-516-1. doi: 10. 00.1145/153334415554499
Pascal Germain, Alexandre Lacasse, François Laviolette, Mario Marchand, and Jean-Francis Roy. Risk bounds for the majority vote: from a BACC-Bayesia analysis to learning algorithm. J. Mach. Learn. Res., 16:787 860. 2015. doi: 10.5555/78822222883111 22311111 URL https:/ //d1. acm. org/ http://....55/////222222222 2831144
11

---

Allan Grönlund, Lior Kamma, and Kasper Green Larsen. Margins are insufficient for explaining gradient boost- ing. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balean, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Procexsing Systems 2020, NeurlPS 2020, December 6-, 2020, virtual, 2020, URL https: //pp/cceeedde..... Abstract.html
neurips- cc/ cc/paper/ 2020/ ha/00//aa//////// http//hhhhhhhhaaaae
Benjamin Guedj. A primer on PAC-Bayesian learning. CoRR, abs/i/aa.//11555551111 2019. URL http://arxxi.
org/abs, hts//90/110..... 19901.5353.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors. 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http:///rxiv... org/ 1412. 6980.
Alexandre Lacasse, François Laviolette, Mario Marchand, Pascal Germain, and Nicolas Usumier. PAC-Bayes bounds for the risk of the majority vote and the variance of the Gibbs classifier. In Bernhard Schölkopf. John C. Platt, and Thomas Hofmann, editors, Advances Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Procexsing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006, pages 769-776. MIT Press, 2006. URL httpt://pppppe sttttps:/prooeedingg: neurips. www.rbats.tttte.........aae
cc/paper/ hateer/200//aaaeee 7799efbd24d577e377 cedcee777773332777745555
Alexandre Lacasse, François Laviolette, Mario Marchand, and Francis Turgeon-Boutin Learning with randomized majority votes. In José L. Balcázar, Francesco Bonchi, Aristides Gionis. and Michèle Se- bag, editors, Machine Learning and Knowledge Discovery in Dutabases, European Conference, ECML PKDD 2010, Barcelona, Spain, September 20-24, 2010, Proceedings, Part II, volume 6322 of Lecture Notes in Computer Science, pages 162-177. Springer, 2010, doi: 10, (0007/99--3-64-1111 111-111883-4111111 11. URL https://doi. org/10. 10/g/10.110 10070000799990 /978// 3- 642 15883-4_11
John Langford and Matthias Seeger. Bounds for averaging classifiers, 2001. URL httpt:t//////t //wp:///wwwwwaaee/ cs. cmu, cmu.edu/
jcl/papers/ / wwwwaginggga//aaa/ hwtp://aaerraaggeeieieeee tech. pdf.
John Langford and John Shawe-Taylon PAC-Bayes & margins. In Advances in Neurol Information Processing Systems, pages 039-446,226 2003.
François Laviolette, Emilie Morvant, Liva Ralaivola, and Jean-Francis Roy. Risk upper bounds for general ensemble methods with an application to multiclass classification. Neurccopuuting 2017.
Gaël Letarte, Pascal Germain, Benjamin Guedj, and Francois Laviolette. Dichotomize and generalize: PAC- Bayesian binary activated deep neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 6872-6882. Curran Associates, Inc., 2019.
Stephan Sloth Lorenzen, Christian Igel, and Yevgeny Seldin. On PAC-Bayesian bounds for random forests. Mach, Learn., 108(8-9)) 90:189999953---- 1522. 2019. doi: 10.1007/5109940019 (101009999--1-----0 05800-44 URL https: org/10 1007/s10994 019 -10-0800----00000----4400 05803-4.
Olivier Marchal and Julyan Arbel. On the sub- Sub-Gaussiantty the Beta and Dirichlet distributions. Electronic Communications in Probubilit, 22:1-14, 2017.
Andrés R. Masegosa, Stephan Sloth Lorenzen, Christian Igel, and Yevgeny Seldin. Second order PAC- Bayesian bounds for the weighted majority vote. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neurul Information Process- ing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL abstract.htar
neuripa www.ipp.cc/paper/// haaaper/2020/aahhh
Andreas Maurer. A note on the PAC-Bayesian theorem. CoRR, cs. 2004. URL https://aaxi. org/abs/ abs/ / cs LG/ 0411999.
Didrik Nielsen.
Tree boosting with XGBoost: why does XGBoost win "every" machine learning competition? Master's 's thesis, NTNU, 2016.
A. B. Novikoff. On convergence proofs on perceptrons. In Proceedings of the Symposium on the Mathematical Theory of Automata, volume 12, pages 615-622, New York, NY, USA. 1962. Polytechnic Institute of Brooklyn.
Maria Perez-Ortiz, Omar Rivasplata, John Shawe-Taylon and Csaba Szepesvari. Tighter risk certificates for neural networks. Journal of Machine Learning Research, 22(227):1 40, 2021. URL http: //jmrr///////////// //tgg//r/////////////////// papers/v22/22 200r2222/2022 879. html.
12

---

Dean-FFancis Roy, François Laviolette, and Mario Marchand. From PAC-Bayes bounds to quadratic programs for majority votes. In Lisc Gctoor and Tobias Scheffer, editors, Proceedings of the 28th International Conference on Machine Learning, ICML 2011, Bellevue, Washington, USA, June 28 July 2, 2011, pages 649-656, Omnipress, 2011. URL https: //ce:////mmmm///// http:/2011/pppere///// wawp:p.rrpppppr.pppppp
Robert Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee. Boosting the margin: explanation for the effectiveness of voting methods. The Annals of Statistics, (665):151-16886 October 1998, doi: Te..2214/as/1024450 132469332..
Matthias Seeger. John Langford, and Nimrod Megiddo. An improved predictive accuracy bound for averaging classifiers. In Proceedings of the 18th International Conference on Machine Learning, number CONF, pages 290, 2001.
John Shawe- Taylor and David R. Hardoon, PAC-Bayes analysis of maximum entropy classification. In AISTATS, 2009.
Ravid Shwartz-Ziv and Amitai Armon. Tabular data: Deep learning is not you need. Inf. Fusion, 81:84-90. 2022. doi: 10. ia..016..ifffuus2222222 2022.11.111111111111111111111101 URL httpp:://oi. http://////oo/////////// 0t///10.111.6 1016/ j infffuu.... 2021 111.111111..11 0111
Niklas Thiemann, Christian Igel. Olivier Wintenberger, Yevgeny Seldin. strongly quasiconvex PAC- Bayesian bound. In Steve Hanneke and Lev Reyzin, editors, International Conference on Algorithmic Learning Theory, ALT 2017, 15-17 October 2017, Kyoto University, Kyoto, Japan, volume 76 of Proceedings of Machine Learning Research, pages 466-492 PMLR, 2017. URL http::ttpp::/eeeeee v76 htt/thhemmann1/ html.
.lr. pprss//
Thomas Uriot, Dario Izzo, Luis F Simões, Rasit Abay, Nils Einecke, Sven Rebhan, Jose Martinez- Heras, Francesca Letizia. Jan Siminski, and Klaus Merz. Spacecraft collision avoidance challenge: design and results of machine learning competition. Astrodynamics, pages 1-20, 2021.
Paul Viallard, Pascal Germain, Amaury Habrard, and Emilic Morvant.
Self-bounding majority vote learning algorithms by the direct minimization of a tight MAC-Bayesian C-bound. In ECML-PKDD 2021, pages 167-183, 2021.
Liwei Wang, Masashi Sugiyama, Cheng Yang, Zhi-IHua Zhou, and Jufu Feng. On the margin explanation of boosting algorithms. In Rocco A. Servedio and Tong Zhang, editors. 21st Annual Conference on Learning Theory COLT 2008, Helsinki, Finland, July 9-12, 2008, pages 479-490. Omnipress, 2008 URL http: //co1t2008.0 cs hewsinki...........m....w....iia fiieea.ff/paaae httpapprs//Oet/ Wang pdf.
Yi-Shan Wu, Andrés R. Masegosa, Stephan Sloth Lorenzen, Christian Igel, and Yevgeny Seldin. Chebyshev- Cantelli PAC-Bayes-Bennee Bennett inequality for the weighted majority vote. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 12625-12636, 2021. URL ptttps://proceeeingg httpa//aaaaa/////bbbbbbbbbb
neuripa cc/ cc/paper/2021 hhahh///aaaaaaaa/aaa/aaa 69386f6bb1ddetee.. 1tt.::6.....20666622228888866889 Aaee-r-btttt.......... html.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Rashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms. CORR, C5...G/1708.07747,, 2017.
Valentina Zantedeschi, Paul Viallard, Emilie Morvant, Rémi Emonet, Amaury Habrard, Pascal Ger- main, and Benjamin Guedj. Learning stochastic majority votes by minimizing PAC-Bayes gen- eralization bound. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan. editors. Advances in Neural Information Processing Systems 34: An- nual Conference on Neural Information Processing Systems 2021. NeurIPS 2021, December 6-14, 2021, virtual, pages 455-467, 2021, URL https:/ h prroceddings.neure. 44455740eaa4499eccccea00000
Abstract html.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orhanz. Non-vacuous generalization bounds at imagenet scale: a Bay--Ba compression approach. 7th International Conference on Learning Representations, ICI. 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https: wtwpearrrriioo.eet/ruoru//aaaaae http://oooorm///sssgggascccii
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]
13

---

(b) Did you describe the limitations of your work? [Yes] See, e.g. discussion in Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work of primarily theoretical nature and therefore no negative societal impact is foreseen.
All data is from publicly-availan datasets.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? Yes]]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Included the theorem statements and setting introduction in Section 1.1
(b) Did you include complete proofs of all theoretical results? [Yes] Included primarily in the main paper with some extra result in the appendices.
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 as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section and Appendix C
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] In Appendix C
(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] In Appendix C
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] In Appendix C
(b) Did you mention the license of the assets? [Yes] In Appendix
(c) Did you include any new assets either in the supplemental material or as URL? [Yes]
We include links in Appendix
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] All data was publicly available.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
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] We did not conduct any such research.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A] We did not conduct any such research.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] We did conduct any such research.
14


Reviews:
[{"review_id": "vaPHJxQNAom", "reviewer": "Reviewer_uYQj", "summary": "The paper \"On Margins and Generalisation for Voting Classifiers\" proposes a novel generalization bound for voting classifiers (i.e. ensembles) using a Dirichlet posterior over the ensemble members. The novel bound explores a new direction for generalization bounds for ensembles and also seems to have decent results in practice. The paper is generally well-written and easy to follow. The theoretical contribution is clearly stated and the experimental evaluation seems decent. ", "questions": "1) In the appendix you write that you initialize $\\theta$ uniformly in $[0.01, 1]$ and then optimize over it. I assumed that one would initialize $\\theta$ as the weight of each ensemble member for random forests, i.e. $\\theta_i = 1/|\\mathcal H|$ in the case of random forest. Why do you use different values here? Did I miss something?\n2) The results in Fig 1. / 2. are comparably bad to e.g. classic RF. For example, a vanilla RF has a performance around $> 97 $% on mnist whereas you report errors in the range of $10-20 $%. I understand that raw performance is not the main focus of this paper (and hence I dont really care), but I am curios why there is this large performance gap. Do you think this is because $\\theta$ is optimized afterwards?\n3) I expected a generalization bound to be used as a \"plug in\" explanation for any voting classifier, e.g. as in Theorem 2. Now I wonder what the impact of $\\theta$ is here. From my point of view, $\\theta$ are simply the weights of the individual classifiers (e.g. equal for Random Forests or (normalized) floats for boosting). Is there any harm in using Theorem 2 to compute the error of, e.g. AdaBoost and if not, did you try that?", "limitations": "There might be some limitations wrt. to $\\theta$, but I am not sure about this. Please see my question above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I like to paper and I do not have much to discuss about it to be honest. The paper combines different aspects from theory into a non-trivial, novel bound. It is well-written and easy to follow. The quality of the math seems sound, although I admit that I did only skimmed the appendix. I believe the use of the Dirichlet posterior is an interesting idea and can be used to as a starting point for future research. I have some minor remarks regarding the references that can easily be fixed for a camera ready and some question wrt. to the weights of each member in the ensemble (see below). In short: \n\n- (+) Novel and non-trivial combination of different results from literature\n- (+) Generally well-written and comparably easy to follow\n- (+) Decent empirical evaluation \n- (-) High test error in the empirical evaluation (see my question below)\n- (-) The citations should be improved for more consistency. I suggest to double-check references {1,14,16,17,23,24,26,36,47} via https://dblp.uni-trier.de/ and copy/paste the extended Bibkeys", "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": "v6QZpr6ZQ2K", "reviewer": "Reviewer_KkjL", "summary": "On Margins and Generalisation for Voting Classifiers\n\nIn this paper, the authors take a generalization bound for stochastic majority votes from prior work and show how to derive a new margin bound for majority vote algorithms using Dirichlet priors. As stepping stone they prove a new result relating the misclassification loss to the stochastic voting loss. This bound is empirically verified to have better characteristics in that it comes closer to accurately predicting test set error than related work. The authors also derive an optimizable target version of their bound which appears to yield good results compared to other similar approaches in the literature on a variety of datasets.", "questions": "Two minor points: I would have liked to see a precise statement of Zantedeschi et al's bound in section 2.3. In particular, I missed the intuition behind \"the use of such Dirichlet distributions...allows the correlation between voters to be more carefully considered.\" \nSecond, I missed why in figure 2 the \"our bound\" results change for every baseline.", "limitations": "There is no specific limitations section, but the authors do describe gaps between their results and empirical results as well as cases when their bounds may not be accurate (albeit very briefly)", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper, although very dense, is making important contributions to the understanding of ensemble classifiers, in particular to the margin argument of why such classifiers generalize. It struck me as very insightful to be able to use the stochastic voting bound to prove the majority voting result. That the result also turns out to tighter than prior work as well as empirically perform well makes it very strong (and cool!). \nOn the whole, I think this is a strong paper that is using very insightful connections from recent prior work to improve the state of the art generalization bounds on voting classifiers. ", "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": "R1BFkTfGPui", "reviewer": "Reviewer_hEGP", "summary": "This paper deals with the theory of (multi-category) pattern classification. The authors introduce a new PAC-Bayes bound for majority voting of finite ensembles of classifiers. It is based on Dirichlet posteriors. A variant is proposed to serve as the objective function of a training algorithm (train the model itself). Those two bounds are compared with the state-of-the-art ones in the framework of an empirical study.", "questions": "A few typos should be corrected. Two examples :\n-line 93 : complimentary -> complementary\n-line 470 : pac-bayesian -> PAC-Bayesian", "limitations": "Not applicable", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The contribution appears to bring a significant improvement compared to the state of the art, even though it is not that original, since it is close to a result by Zantedeschi et al. (2021). I found it technically sound. It is noticeable that the paper is very well written (clear).", "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