Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound
Authors: Valentina Zantedeschi
Paul Viallard
Emilie Morvant
Rémi Emonet
Amaury Habrard
Pascal Germain
Benjamin Guedj
Venue: NeurIPS 2021 Poster (2021)
Keywords: majority vote
ensemble method
generalization bound
bound-driven algorithm
PAC-Bayes

Abstract: We investigate a stochastic counterpart of majority votes over finite ensembles of classifiers, and study its generalization properties. While our approach holds for arbitrary distributions, we instantiate it with Dirichlet distributions: this allows for a closed-form and differentiable expression for the expected risk, which then turns the generalization bound into a tractable training objective.
The resulting stochastic majority vote learning algorithm achieves state-of-the-art accuracy and benefits from (non-vacuous) tight generalization bounds, in a series of numerical experiments when compared to competing algorithms which also minimize PAC-Bayes objectives -- both with uninformed (data-independent) and informed (data-dependent) priors.

Learning Stochastic Majority Votes by Minimizing a PAC-Bayes Generalization Bound
Valentina Zantedeschi 123
Paul Viallard
Emilie Morvant
Rémi Emonet'
Amaury Habrard
Pascal Germain
Benjamin Guedj
Inria, Lille Nord Europe research centre, France 2 The Inria London Programme, France and UK
3 University College London, Department of Computer Science, Centre for Artificial Intelligence, UK CNRS, Institut d Optique Graduate School, Laboratoire Hubert Curien UMR 5516, F-42023, Saint-Etienne, France
Univ Lyon, UIM-Saint-
5 Département d' l'informatiquee de génie logiciel, Université Laval, Québec, Canada
Abstract
We investigate stochastic counterpart majority votes over finite ensembles of classifiers, and study its generalization properties. While our approach holds for arbitrary distributions, we instantiate with Dirichlet distributions: this allows for closed-form and differentiable expression for the expected risk, which then turns the generalization bound into a tractable training objective. The resulting stochastic majority vote learning algorithm achieves state-of- the-arr art accuracy and benefits from (non-vacuous) tight generalization bounds, in series of numerical experiments when compared to competing algorithms which also minimize PAC- Bayes objectives both with uninformed (data-independent) and informed (data- dependent) priors.
Introduction
By combining the outcomes of several predictors, ensemble methods (Dietterich] 2000) have been shown to provide models that are more accurate and more robust than each predictor taken singularly. The key to their success lies harnessing the diversity of the set of predictors [Kuncheva] [004]]. Among ensemble methods, weighted Majority Votes (MV) classifiers assign score each base classifier (a.k.a. voter) and output the most common prediction, given by the weighted majority. When voters have known probabilities of making error and make independent predictions, the optimal weighting is given by the so-called Naive Bayes rule [Berend and Kontorovich (013).. However, in most situations these assumptions the optimal combination of voter predictions from the data.
satisfied, giving rise the need for techniques that estimate
Among them, PAC-Bayesian based methods are well-grounded approaches for optimizing the voter weighting. Indeed, PAC-Bayes theory (introduced by [Shawe-Taylor and Williamson 1997
McAllester [999]- we refer to Guedj 2019 for recent survey and references therein) provides not only bounds on the true error of a MV through Probably Approximately Correct (PAC) generalization
bounds (see e.g. Catoni 2007 Seeger [2002]. Maurer [2004] Langford and Shawe- Taylor (202))
Germain et al. [2055] but is also suited to derive theoretically grounded learning algorithms (see [
e.g. Germain et al. 22099] Roy al. (001 Parrado-eemánder et al. [2012]. Alquier et al. (2016)).
Contrary to the most classical PAC bounds [aliiant 1984]. as VC-dimension [Vapnik] 2000 or
bounds [Mohri et al. 2012). PAC PAC-Bayesian guarantees do not stand for all hy- potheses (i.e. are not expressed as a worst-case analysis) but stand in expectation over the hypothesis set. They involve hypothesis space (formed by the base predictors), prior distribution a priori weighting) and a posterior distribution (i.e. an a posteriori weighting) evaluated on a learning sample. The prior brings some prior knowledge the combination of predictors, and the posterior
Rademacher-haste
it (i.e. an
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

distribution is learned (adjusted) to lead to good generalization guarantees; the deviation between the prior and the posterior distributions plays a role in generalization guarantee and is usually captured by (KI.) divergence. In their essence, PAC-Bayesiag results do not bound directly
the Kullback-Leeibe the risk of the deterministic MV, but bound the expected risk of one (or several) base voters randomly drawn according to the weight distribution of the MV [Langford and Shawe- Taylor] 2002 Lacasse ict al., 2006 2010 Germain et al. 2013 Masegosa et al. 2020]. This randomization schemn leads to upper bounds on the true risk of the MV that are then used as proxy to derive PAC-Bayesian generalization bounds. However, the obtained risk certificates are generally not tight, as they depend on irreducible constant factors, and when optimized they can lead to sub-optimal weightings. Indeed, by considering a random subset of base predictors, fatte-of-thh-ar methods do not fully leverage the diversity of the whole set of voters. This is especially a problem when the voters weak, and learning to combine their predictions is critical for good performance.
Our contributions. In this paper, we propose new randomization scheme. We consider the voter weighting associated to a MV as a realization of a distribution of voter weightings. More precisely, we analyze with the PAC-Bayesian framework the expected risk of a MV drawn from the posterior distribution of MVs. The main difference with the literature is that we propose a stochastic MV, while previous works aim at studying randomized evaluations of the true risk of the deterministic MV. Doing so, we are able to derive tight empirical PPAC-Bayesia bounds for our model directly on its expected risk, in Section 4 We further propose, in Section 3 two approaches for optimizing the generalization bounds, hence learning the optimal posterior: the first optimizes an analytical and differentiable form of the empirical risk that can be derived when considering Dirichlet distributions; the second optimizes a Monte Carlo approximation of the expected risk and can be employed with any form of posterior. In experiments, reported in Section 5 first compare these two approaches, highlighting in which regimes one is preferable to the other. Finally, we assess method's performance on real benchmarks w.r.f. the performance of PAC- MMC-Bayesian approaches also learning MV classifiers. These results indicate that our models enjoy generalization bounds that are consistently tight and non-vacuous both when studying ensembles of data-independent predictors and when studying ensembles of data-dependent ones.
Societal impact. Our work abides by the ethical guidelines enforced in contemporary research in machine learning. Given the theoretical nature of our contributions we do not foresee immediate potentially negative societal impact.
2
Notation and background
In this section, we formally define weighted Majority Vote (MV) classifiers and review the principal PAC-Bayesian approaches for learning them.
2.1 Weighted majority vote classifiers
Consider the data random variable (X, Y), taking values in X'x) with X C. Rd a d-dimensional representation space and y the set of labels. We denote P the (unknown) data distribution of (X, Y).
We define a set (dictionary) of base classifiers D= X - V)M The weighted majority vote classifier is a convex combination of the hase classifiers from D. Formally, a MV is parameterized by a weight vector 0 E [0, 1j such that EM 0z = hence lying in the (M-I)-simplex A M-1 as follows:
M
fo(x) = argmaa nEY
Σ 0, 1(h((x) = y),
(1)
where 11() is the indicator function. Let Wo Y) be the random variable corresponding to the total weight assigned to base classifiers that predict an incorrect label on (X, Y), that is
Wo(X,Y) Σ 0,1(h;(X) xY).
2

---

0 = [0.25, 0.50, 0.25)
100t 9.5)
2W
6
6
6
0.2 0.4 0. 8.6
(0.99,
(2.00, 2.00,
[2.00, 1.50, 5.00)
Figure 2: Visualization of the density measure p 2 R. taking the form of a Dirichlet distribution, with concentration parameters a. The darker the color, the higher p(0). Each 0 on the simplex corresponds to majority vote classifier fa and has an associated probability depending on a.
Figure 1: Oracle upper bounds for the true risk. The risks are the areas under the respective curves, for arbitrary distribution of Wa (typi- cally different from the uniform).
In binary classification with 2 the MV errs whenever Wo(X, 0.5 Masegosa et al. 2020]. Hence the true risk (w.rt. 01-loss) of the MV classifier can be expressed as
Lacasse al. 2010
R(Jo) Ep (X, Y) 2 0.5) = P(W, > 0.5).
Similarly, the empirical risk of fo on a n-sample 5=((x;, vi) ~ is given by
R((6) Σ (Wo( vi) > 0.5).
Note that the results introduce in the following are stated for binary classification, but are valid also in the multi-class setting ([)|>2). Indeed, in this context Equation (3) becomes surrogate
of the risk: we have R R() P(Wo > 0.5) (see the notion of w-margin with 0.5 proposed
by Laviolette et al. 2017).
2.2 A PAC-Bayesian perspective on the majority vote
The current paper stands in the context of PAC-Bayesian MV learning. The PAC-Bayesian framework has been employed to study the generalization guarantees of randomized classifiers. It is known to provide tight risk certificates that can used to derive self-bounding learning algorithms [e.g.
Germain al. 2009 Dziugaite and Roy 2017 Pérez-Ortiz et al. [2020]. In the PAC-Bayes literature of the analysis of MV, is interpreted as the parameter of a categorical distribution C(#) over the set of base classifiers D [e.g. Germain et al. 2015 Lorenzen et al. 2019 Masegosa al. 2020). In this sense, So corresponds to the MV predictor Jo(x) argmax yey ()--((0 II (h(r) y) and W corresponds to the expected ratio of wrong predictors Wo(X, Y) = En-c(o) ((((X) * Y). The PAC-Bayesian analysis provides sensible way to find such categorical distribution, called posterior distribution, that leads to a model with low true risk R(fe). However, an important caveat that the PAC-Bayesian generalization bounds cannot be derived directly on the true risk R(Ja), without making assumptions on the distribution of W, and raising fidelity problems. Thus, a common approach is to consider oracle! upper bounds
the true risk in terms of quantities from which PAC-Bayesian bounds can be derived, that are typically related to the statistical moments of W.. By doing so, oracle bounds act as a proxy for estimating the cumulative density function for We > 0.5 Langford and Shawe-Taylor Taylor] 2002 Germain et al.) 22066] Lacasse et al. 2010 Masegosa et al. 2020). Generalization guarantees for R(fa) are hence derived. involving the empirical counterpart of the oracle bound, the KL-divergence between the posterior categorical distribution C(0) and prior one. overview of the existing oracle bounds described below represented in Figure
First order bound. The most classical "factor two" oracle bound [Langford and Shawe- Taylor 2002] is derived considering the relation between MV's risk and the first moment of Wa, a.k.a, the expected risk of the randomized classifier:
R1 (0) + En-c(o) 1(h())+ = Ep We.
'Oracle bounds expressed terms of the unknown data distribution; their exact value cannot computed.
3

---

By applying Markov's inequality. we have R(fa) < (R) This "factor two" bound is close to zero only if the expectation of the risk of a single base classifier drawn according to C(0) is itself close to zero. Therefore, it does not take into account the correlation between base predictors, which is key to characterize how a MV classifier can achieve strong predictions even when its base classifiers are individually weak (as observed when performing e.g. Boosting (Schapire and Singer) I999). This explains why R2 (0) can be a very loose estimate of R{ffa) when the base classifiers are adequately decorrelated.
Binomial bound. A generalization of the first order approach was proposed in Shawe-Taylor and Hardoon 2009 Lacasse et al. [2010), where the true risk of the MV is estimated by drawing multiple (N) base hypotheses and computing the probability that at least N make an error (which given by the binomial with parameter Wo):
2
N (M)
Wan (X + Σ
W (N)
The higher N, the better Was (X,Y) Y) approximates the true risk, but the looser the bound, the KL term worsens by a factor of N. Moreover, with this approach it is not possible to derive generalization bounds directly the true risk, and the corresponding oracle bound still presents factor two: R(Jo) & 2 EpWaa.
Second order bound. A parallel line of works focuses on improving the bounds by accounting for voter correlations, iee. considering the agreement and/or disagreement of two random voters. Masegosa et al. [2020] recently proposed new upper bound for the true risk depending on the second moment of Wo, a.k.a. tandem loss or joint error, the risk that two predictors make a mistake on the
same point:
R2(0) Epp R=--C(0), (M(X)* A - W
By applying the second order Markov's inequality, we have R &(fa)=4R2(00 Masegosa et al. 2020 show that the worst case (i.e. when the base classifiers are identical) the second order bound could be twice worse than the first order bound (R2 2 (f)), while in the best case (i.e. the M base classifiers are perfectly decorrelated), the second order bound could be an order of magnitude tighter (0) M (0)).
C-bound. Originally proposed by Breiman [001 in the context of Random Forest, bound known as the C-Bound in the PAC- CC--Byysinn literature Lacasse et al., 2006 Roy et al., 2011 Germain et al., 2015 Laviolette et al. 2017 Viallard al. 2021b] is derived by considering explicitly the joint error and disagreement between two base predictors. Using
Canttelll'' inequality, the C-Bound
can be written in terms of the first and second moments of Wa:
R2(0) - - (h # Y))²
R(fe)
(2) R1 (0) +
This bound is tighter than the second order one if the disagreement Es Ep((((()) # N(())) is greater than (0) [Masegosa et al. 2020].
From a practical point of view, one could minimize the generalization bounds of one of the above methods to learn weight distribution over an ensemble of predictors. However, this could lead sub- optimal MV classifiers. To illustrate this behavior we plot in Figure 3 decision surfaces learnt by the minimization of PAC-Bayesian bound each of the aforementioned oracle bounds. These plots provide evidence that, when the base classifiers are weak, state-of-the-arr PAC-Bayesian methods do not necessarily build powerful ensembles (failing improve upon a Naive Bayes approach [Berend and Kontorovich 2015). First Order concentrates on few base classifiers, as previously observed by Lorenzen al. 2019 and Masegosa al. 22020], while Second Order and C-Bound fail to leverage the diversity in the whole set of classifiers. Indeed, in this setting the base classifiers are weak, but diverse enough so that there exists an optimal combination of them that perfectly splits the two classes without error. However, the optimization of the FAC-Bayes guarantees over Second Order and C-Bound are shown to select a small subset of base classifiers which is not enough to achieve good performance. On the contrary, Binomial is able to fit the problem by drawing more than 2 voters, but it provides generalization bounds that are loose even when the learned model exhibits good generalization capabilities, in this case.

---

M-128 1--1
Bayesian NB (h) First Order (c) Second Order
(d) C-Bound
(c) Binomial
(f) ours
Figure 3: Decision surface for Bayesian Naive Bayes, the PAC-Bayesian methods First Order, Second Order, C-Bound and Binomial (with N 100) and our method on the two-moons dataset (where each half-circle is class and inputs lie in X' = ( with 16 (top) and 128 (bottom) decision stumps as base classifiers (axis-aligned and evenly distributed over the input space). Predicted labels are plotted with different colors, and training points are marked in black. When available, the value of the generalization bound marked in the hight-hand-side side-to corner.
3 Our approach: stochastic weighted majority vote
In our framework for deriving generalization bound for Majority Vote classifiers, consider fo realization of a distribution of majority vote classifiers, with parameter 0 @ = RM and probability measure p. represented in Figure The main advantage of considering stochastic majority vote that it allows to derive and optimize PAC-Bayesian generalization bounds directly on its true risk and to fully leverage the set of base classifiers. The true risk of the proposed stochastic weighted majority vote takes into account the whole distribution of MVs p(0), as follows:
[ [(fa)p(d0) Ep 1(Wa(X,)) > 0.5) = Epp [ 1(Wo(X,Y) 2 (.5)p (4)
Je
Given its stochastic nature, order to evaluate and/or minimize Equation we can either (i) compute its closed form or (ii) approximate it (e.g. through Monte Carlo methods). In both cases, assumptions have to made on the form of p. As the components one, # lies in the -M-1)-simplex: are e.g. the Dirichlet or the Logit Normal distributions. In the following, we show that under Dirichlet assumptions, we can derive an analytical and differentiable form of the risk stochastic MV.
are constrained to sum AM-1), hence natural choices for its probability measure
3.1 Exact risk under Dirichlet assumptions
First of all, we recall that the probability density function of the Dirichlet distribution is defined by:
a.). p(0) B(a) Il 10))011
(5)
with a = [ay R+IM" the vector of concentration parameters and B(a) normalization factor (see App A its definition). Notice that by taking as the vector of all ones, the distribution corresponds uniform distribution over the (M--I-simplex A M-1
Under these assumptions for the MV distribution, a closed form can be derived for the expected risk:
Lemma For a given (x, y) ~ P. let w = (x) + y) be the set of indices of the base classifiers that misclassify (x. y) and c (ilh,(x)) y) be the set of indices of the base classifiers that correctly classify (æ, y). The expected error (or 01-loss) for (x,, y) of the stochastic majority vote under D(a aM) is equal to
[ (Wo(r,y) > 0.5)p(d0) To.s
(6)
JEC
jEW
with 1o.5(.) the regularized incomplete beta function evaluated at 0.5.
5

---

jew Gy. and use the aggregation property of Dirichlet distributions to show that Wa follows a bivariate Dirichlet distribution (a.k.a. Beta distribution):
Proof. We rewrite We as Wo(z.v) 1
0,1(h;(z) * v) EeEw
Lemma 2. 1f0 Dia ass), then for any j [M] and j'd [1, MM the variable 8' formed by dropping 8 and By and adding their sum also follows a Dirichlet distribution
(0 (0.....,00l M 02 0y) D(a 0j azy).
proof of this property be found in https btttps//vaaite //aanneva DoccmentssUWEETTR
http://eehsssttppppppeeee Hence Wo follows a Beta distribution over the two sets of
UWEETR- 2010-0006, 11.-0006..p00 pdf wrong and correct base classifiers:
P(Wo(a,y) w|
Σ JEM
0j
P
Σの
1
jEc
Wo(x,
Σ
ajo
Σas aj
by aggregation.
JEW
Finally, notice that the expected error is related to the cumulative probability function of Wo, the incomplete beta function Ip TR+ x IR+ - [0, 1]:
[ PldWo(x,y)]
I(We(x,)) 0.5)p(d0)
0.5
=1 To.5
Σ
aaj
To.s
Σ
ajj Σ 0g
(9)
JEW
jEC
jEC
JEW
Equation ( follows by symmetry of the incomplete beta function: I,(a, b)
I
11-p(b,0).
The expected risk R(p) can be then expressed follows:
R(p) Ep (Wo(,, > 0.5)p(d0) Ep Ea, Σ
(10)
jEW
Importantly, this exact form of the risk differentiable, hence can be directly optimized by gradient-
based methods.
3.2 Monte Carlo approximated risk
We now propose a relaxed Monte Carlo (MC) optimization scheme for those distributions that do admit analytical form of the expected risk, unlike the Dirichlet one. This second strategy is also suited to speed up training, in some cases, as the derivatives of the exact risk depend on the hyper-geometry function and can be slow to evaluate (see App. A.3). With the approximated scheme, in order to update a by gradient descent we need to relax the true risk as the gradients of the 01-loss are always null for discrete Wo. In practice, we make use of a tempered sigmoid loss (z(z)) T+exp(-ca) with slope parameter E R+ De facto this corresponds to solving a relaxation
of the problem and not its exact form [Nesterov algorithm we perform:
2005
At each iteration of the MC optimization
1. Draw sample (0, ~ p(a)) using the implicit reparameterization trick Figurnov et al. 2018 Jankowiak and Obermeyer 2018);
2. Compute the relaxed empirical risk ΣT_ Ro. (0) E (Wo, 0.5):
3. Update a by gradient descent.

---

Notice that when considering Dirichlet distributions for the posterior and the prior, at inference time the empirical PAC-Bayesian bounds can still be evaluated using the exact form of Lemma
drawback of the approximated scheme is that it has a complexity linear in the number of MC draws T, but also linear in the number of predictors M, as sampling over the simplex requires sampling from O(M) distributions, one per base classifier. As an example, sampling from Dirichlet over the (M-I)-simplex is usually implemented as sampling from M Gamma distributions and normalizing the samples so that they lie on the simplex. In contrast, the exact formulation's 's complexity is constant in M as it depends only on the sets of wrong and of correct predictors, hence on a constant number of variables (2) no matter the number of predictors M. In Section [3.1 we empirically study the trade-off between training time and accuracy, showing in which regimes is more convenient optimize the relaxed MC risk than optimizing the exact one, and viceversa.
4 PAC-Bayesian generalization guarantees
We now derive PAC-Bayesian generalization upper bounds for the proposed stochastic MV. In our context, upper bounds can be derived for studying the gap between true and empirical risk considering a prior distribution æ over the hypothesis space O In this paper, we make use of one of the tightest classical PAC- -ayysiann bound (Seeger] 2002 Maurer 2004]:
Theorem (Seeger's bound). For any v over O and e (0, 1) with probability at least 1-5 5 over samples S ((r): v.) PP] of size we have simultaneously for any posterior p over θ:
[ R(fo)p(dD) =1 (1. [RLO))odd)
KL(p, TT) In
(11)
n
with R((f)) = -. 1(Wo(=;, v.) E 0.5) the empirical risk on sample S, KL(p,T) = Se p(0) log p(0) do the KI. divergeee and kl as kl (g. max(pe E [0,1] kl(g. p) & c).
(q. c) the inverse of the binary Kl. divergence defined
=(0)
proof of Theorem I can be found in Seeger 2002]. The kl= function can be evaluated via the bisection method and optimized by gradient descent, as proposed in Reeb et al. [2018). Note that our contributions do not restrict the choice of generalization bound.
Importantly, Theorem iss valid when the prior π is independent from the data. Thus it cannot be evaluated with base classifiers learned from the training sample. However, it is known that considering a data-dependent prior can lead to tighter PAC-Bayes bounds (Dziugaite et al., 2021 Following recent works on PAC-Bayesian bounds with data-dependent priors [Thiemann et al. [017]] Mhammedi et al. 2019], we derive cross- gross-bounding certificate that allows us to learn and evaluate the set of base classifiers without held-out data. More precisely, we split the training data S into two subsets (S (S'mm= (5 [(,, Mi)) E 5) and 5-m=((z, y:) E S) 1) and we learn a set of base classifiers on each data split independently (determining the hypothesis spaces O and 2zm) We refer to the prior distribution over θ as т gm and to the prior distribution over Ozm m as T>m- In the same way, we can then define a posterior distribution per hypothesis space: Psm and p>m- The following theorem shows that we can bound the expected risk of any convex combination of the two posteriors, as long as their empirical risks are evaluated on the data split that was not used for learning their respective priors.
Theorem (Seeger's bound with informed priors). Let gm and Pem be the prior and posterior distributions on ④ gms and T=m and pam the prior and posterior distributions on O xm For any (0 1) and 8 E (0, 1) with probability at least 1 1- over samples S S=((Fi, yi) >p)_ we have
kll (pA( (p + (1 (1-p)B ()pp))(( p( (Remm(Psm) p + (1 (1-))>mm(pm))
4y im(-nmm
p KK(pp=m; TSm) (1 p) K KL(psm: Tgg) In
m
1- m
n
with R(pam) = SS R R())) and R R((pm) = Se p(d)), and Regm (Pam) = Se... p(()))(dd)) and Rem (pam) -e,. Rt p())))
7

---

train-error
test-error
Seeger's bound
time (5)
0.25
0.25
400
T=1
MC T-10
0.6
0.35
MC T-500
0.35
0.30
0.30
100
0.05
0.00
0.00
0.0
train-error
test-error
Seeger's bound
time (s)
0.6
0.6
1.0
MC T=1
250
0.4
MC Tw10
T-1
0.4
200
0.2
0.2
0.4
1.00
0.2
0.0
0.0
0.0
30
1.0
10a
1.0
M 30 10a
1.07
10"
1.0
301
M
M
Figure 4: Average performance for 10 trials of exact and MC variants of method as function of the number training points n (top, M fixed to 16) or of decision stumps M (bottom, n 1000), both represented in logarithmic scale, for different number of MC draws T.
The result follows by kl's convexity. The complete proof is reported in App. B In practice, follow- ing Mhammedi et al. (0099 we set m and m and we learn the base classifiers by empirical risk minimization.
Comparison with existing bounds. Until now, considered bounds for the expected risk the space of MVs but not for single realization fg. unlike state-of-the-art methods. Under Dirichlet assumptions,
can bound the risk of the expected MV få by twice the expected risk (see App A.4): R(fg) = R E, po & p0; (0) R((f)). The obtained oracle bound would comprise an irreducible factor, but its KL term would correlation [Lacasse et al., 2006 2010, Masegosa et al., 2020]. Indeed, the empirical bound does not introduce additional factors on the KL term, such as Second Order which has a KL() term and Binomial which has a N K KL() term. The empirical bound on the deterministic MV could be also refined leveraging works on the disintegration of PAC-Bayesian guarantees (Blanchard and Fleuret 2007 Catoni 2007 Rivasplata et al.) 2020 Viallard et al. 2021a
degrade, unlike state-of-the-art bounds that account for voter
A downside of our method is that the complexity of the KL term grows with the number of base classifiers M, unlike the KL on categoricals that tends to 0 in its limit. This results in making the generalization bounds increasingly looser and conservative with growing M, even for low empirical risks. From a generalization perspective, our guarantees are hence able to reflect the complexity of the model, expressed as the size of the hypothesis space M. However, our risk certificates do not account for redundancy in the voter set. For instance, they are not able to distinguish scenarios where base classifiers are highly correlated (hence less complex hypothesis space) from scenarios where base classifiers are independent (more complex). An expedient for ensuring that generalization bounds are tight consists in learning the hypothesis space: the number of base predictors can then be limited without degrading the performance of the majority vote.
Experiments
In this section, we empirically evaluate STOCMV, and we compare its generalization bounds and test emror to those obtained with PAC-Bayesian methods learning majority votes. We show that our method allows to derive generalization bounds that are consistently tight (i.e. close to the test errors) and vacuuuu (i.e. smaller than 1) both when studying ensembles of weak predictors and when studying ensembles of strong ones.
8

---

In the following, we consider Dirichlet distributions for the prior and the posterior of our method, and refer to the model obtained by optimizing the exact risk as exact and the one obtained by optimizing the approximated one as MC. We consider as baselines the PAC-Bayesian methods described in Section 2.T We refer to the methods optimizing the First Order, Second Order and Binomial empirical bound as FO, SO and Bün respectively. We do not compare with the C-Bound, as it is hard to optimize on large-scale datasets and existing algorithms are suited only for binary classification. All generalization bounds are evaluated with probability 1 1-6=0.95 and all prior distributions are set to the uniform (we provide a study for different priors in App. C.2 The posterior parameters (a for our method, 0 for the others) are initialized uniformly in [0.01,2] (and normalized to sum to for SO, FO and Bin). Finally, for MC the sigmoid's 's slope parameter is set to 100 and for Bin the number of voters drawn at each iteration is set to N=100. Code, available at https: / / thub. com/ /tt////eettteccceeeee /StocMy was implemented in pytorch [Paszke et al. 2019 and all experiments were on virtual machine with 8 vCPUs and 1 128Gb of RAM.
5.1
Comparison of exact and MC variants
For this set of experiments, we optimize Seeger's Bound (Equation ( by (batch) Gradient Descent, for 1, 000 iterations and with learning rate equal to 0.1. We study the performance of our method on the binary classification two-moons dataset, with 2 features. 2 classes and (0, 0.05) Gaussian noise, for which we draw n points for training, and 1, 000 points for testing. Figure reports a comparison of exact and MC variants in terms of error, generalization bound and training time (in seconds). Increasing the number of MC draws T unsurprisingly allows to recover exacr's ' performance, and at lower computational cost for reasonable values of M and T. In general, MC is easily parallelizable, its training time has better dependence on n than exact's 's one, however it increases with M at worse rate. When the training sample is large enough (here for n > 10²), MC achieves exact's errors and bounds even for T = 1. We also observe that the error rates and bounds gradually degrade for higher values of M for both methods. This is due to the KL term increasing with MI, as highlighted in Section becoming too strong regularization during training and making the bound looser.
5.2 Experiments on real benchmarks
We now compare the considered methods on real datasets and on two different scenarios, depending on the type of PAC-Bayesian bounds that evaluated: When making use of data-independent priors, we chose as voters axis-aligned decision stumps, with thresholds evenly spread over the input space (10 per feature); When making use of data-dependent priors, we build Random Forests [Breiman] 2001] as set of voters, each with M 1100 trees learned bagging z points and sampling v random Teatures to ensure voter diversity, optimizing Gini impurity score and, unless stated otherwise, without bounding their maximal depth.
We consider several classification datasets from UCI [Dua and Graff 2017 LIBSVM and Za- lando [Xiao et al. 2017]. of different number of features and of instances. Their descriptions and details on any pre- pre-processing are provided in App. C.2 We train the models by Stochastic Gradient Descent (SGD) using Adam (Kingma and Ba 2015 with (0.9, 0.999) running average coefficients, batch size equal to 1024 and learning rate equal to 0.1 with a scheduler reducing this parameter of a factor of 10 with 2 epochs patience. We fix the maximal number of epochs to 100 and patience equal to 25 for early stopping, and for MC we fix T = 10 to increase randomness.
We report the test errors and generalization bounds in Figure 5 (additional results are reported in the appendix. in Tables I and 2 and Figure 14]: We compare the different methods on binary datasets and with
priors in Figure Sa and on multi-class datasets and with data-dependent priors in Figure 5b] First we notice that the bounds obtained by our method are consistently non vacuous and tighter than those obtained by the baselines on all datasets. Regarding the error rates, method's performance is generally aligned with the baselines, while it achieved error rates significantly lower than FO and SO on the perfectly separable two-moons dataset. Sensitivity to noise could explain why our method does not outperform the baselines on the studied real problems, as these usually present label and input noise. Indeed our learning algorithm optimizes the 01-loss, which does not distinguish points with margins close or far from 0.5 because of its discontinuity in Wa = 0.5. Preliminary results reported in App C. seem to confirm this supposition.
httpps:/www.. www.:ntt.eeceeeeeeeeeoomm edu. ceddu.t//""]]ll tt//://i///iis/mmm

---

MUSHROOMS TICTACTOE
SVMGUIDE
HABERMAN
PHISHING
CODRNA
ADULT
bound
0.4
0.2
Bin
exaet
MCC
50 Bin
MC
FD
So
Bin
MC
50
Bin
exa
MC
So
Bin
Mc
Fo
50
Bin
MC
MC
(a) Binary- data independent prior
PROTEIN
FASHION-MNIST
PENDIGITS
SENSORLESS
1.0
bound
0.20
bound
0.15
test enorr
0.6
0.30
0.4
Bin
MC
FO
Sin
exnct
MC
Fo
50
Bin
MC
50
Bin
exact
MC
Fo
50
Bio
exect
MC
(b) Multi-class data dependent prior
Figure 5: Comparison in terms test eπror rates and PAC-Bayesiie bound values.
We report the
means (bars) and standard deviations (vertical, magenta lines) over 10 different runs.
TICTACTOE
1.0
exact
0.3
0.8
t02 eree
SO
020
Sccoers
Sangor's
0.5
0.4
0.0
0.2
0.0
19
2
maximal depth
depth
maximal depth
tree maximal depth
Figure 6: Test eπrо rates and PAC-Bayesian bound values function of the maximal depth of the voters (decision trees here). We report the means and standard deviations over 4 different runs, and mark with red horizontal line the threshold above which Seeger's bounds vacuous. Additional results are available in the appendix.
Finally, gain better understanding of the relation between base classifier strength and perfor- mance of the models obtained with the different methods, we further study their performance and generalization guarantees with varying voter strength. As hypothesis set, learn Random Forests with 200 decision trees in total, as before, but for this experiment we bound their maximal depth between and 10. Constraining the tree depth allows indirectly control how well the voters fit the training set (as shown in Appendix, Figure 13). Following Lorenzen et al. 2019), we assess the voter strength by computing the expected accuracy of random voter. All methods' results improve overall when voters get stronger, even though FO at a slower pace. Notice that on the considered datasets SO the most sensitive method, particularly suffering from weak base predictors. Our method generally provides test errors comparable with the best baselines and consistently tighter bounds.
Future work
We propose a stochastic version the classical majority vote classifier, and we directly analyze and optimize its expected risk through the PAC-Bayesian framework. The benefits on the model accuracy of this direct optimization are however reduced in presence of input noise, and fostering robustness in noisy contexts is the subject of future work. Another potential improvement would consist in tackling the discussed looseness of our generalization bounds with increasing number of base predictors, by accounting for redundancy in the hypothesis space.
10

---

Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their constructive feedback and support. This work was partially funded by the French Project APRIORI ANR-18-CE23-00155 Experiments presented in this paper were carried out using the Grid' 5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities well as other organizations (see httpps:/ /typ:://www grw.g000..... fr). Pascal Germain is supported by the Canada CIFAR Al Chair Benjamin Guedj acknowledgee
Program, and the NSERC Discovery grant SCGPIN-2020-0722 partial support by the U.S. Army Research Laboratory and the U.S. Army Research Office, and by the U.K. Ministry of Defence and the U.K. Engineering and Physical Sciences Research Council (EPSRC) under grant number EP/R013616/1 Benjamin Guedj acknowledges partial support from the French National Agency for Research, grants ANR-18-CE40-0016-40 and ANR-18 18-CCE230001--2.
References
Pierre Alquier, James Ridgway, and Nicolas Chopin. On the properties of variational approximations of Gibbs posteriors. The Journal of Machine Learning Research, 17(1):8374-4414 2016.
Daniel Berend and Aryeh Kontorovich. A finite sample analysis of the naive Bayes classifier. JMLR, 2015.
Gilles Blanchard and François Fleuret. Occam's 's Hammer. In COLT, 2007.
Leo Breiman. Random forests. Machine Learning, 2001.
Olivier Catoni. PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learn- ing. Institute of Mathematical Statistics Lecture Notes, 2007.
Thomas G. Dietterich. Ensemble Methods in Machine Learning. In Multiple Classifier Systems, Lecture Notes in Computer Science. Springer, 2000.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://arcciive..cc. uci eduummdmm
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. AUAI Press, 2017.
Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, and Daniel Roy. On the role of data in PAC-Bayes. In International Conference on Artificial Intelligence and Statistics, pages 604 612. PMLR, 2021.
Mikhail Figurnov, Shakir Mohamed, and Andriy Mnih. Implicit Reparameterization Gradients. In NeurlPS, 2018.
Pascal Germain, Alexandre Lacasse, François Laviolette, and Mario Marchand. A PAC-Bayes risk bound for general loss functions. NIPS. MIT Press, 2006.
Pascal Germain, Alexandre Lacasse, François Laviolette, and Mario Marchand. VAC-Bayesian learning of linear classifiers. In ICML, pages 353-360, 2009.
Pascal Germain, Alexandre Lacasse, François Laviolette, Mario Marchand, and Jean-Francis Roy. Risk bounds for the majority vote: from PAC-Bayesian analysis to a learning algorithm. JMLR, 2015.
Benjamin Guedj. A Primer on PAC-Bayesian Learning. In Proceedings of the second congress of the French Mathematical Society, 2019. URL htttps/////axx org/ abs 1901/991110 05353
Martin Jankowiak and Fritz Obermeyer. Pathwise Derivatives Beyond the Reparameterization Trick. In ICML, 2018.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Ludmila I. Kuncheva. Combining Pattern Classifiers: Methods and Algorithms. Wiley, 2004.

---

Alexandre Lacasse, François Laviolette, Mario Marchand, Pascal Germain, and Nicolas Usunier. PAC-Bayes bounds for the risk of the majority vote and the variance of the gibbs classifier. In NIPS. MIT Press, 2006.
Alexandre Lacasse, François Laviolette, Mario Marchand, and Francis Burgeon-Boutin Learning with Randomized Majority Votes. In ECMI//KDD (2). Springer, 2010.
John Langford and John Shave-Taylor. PAC-Bayes & margins. In NIPS. MIT Press, 2002.
François Laviolette, Emilie Morvant, Liva Ralaivola, and Jean-Francis Roy. Risk upper bounds for general ensemble methods with an application to multiclass classification. Neurocomputing, 2017.
Stephan Sloth Lorenzen, Christian Igel, and Yevgeny Seldin. On PAC-Bayesian bounds for random forests. Machine Learning, 2019.
Andrés R. Masegosa, Stephan Sloth Lorenzen, Christian Igel, and Yevgeny Seldin. Second order PAC-Bayesian bounds for the weighted majority vote. In NeurIPS, 2020.
Andreas Maurer. note on the PAC Bayesian theorem. CoRR, cs. cs.LG//41109, 2004.
David A. McAllester. Some PAC-Bayesian theorems. Machine Learning, 1999.
Zakaria Mhammedi, Peter Grünwald, and Benjamin Guedj. PAC-Bayes un-expected bernstein inequality. NeurIPS, 2019.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, 2012. ISBN 100-00262--1822555
Yurii E. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 2005.
Emilio Barrado-Heránnde Amiran Ambroladze, John Shawe-Taylor, and Shiliang Sun. PAC-Bayes bounds with data dependent priors. The Journal of Machine Learning Research, 13(1)3507-3531, 2012.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, High- High-Perffrmance Deep Learning Library. In NeurIPS, 2019.
María Pérez-Ortiz Omar Rivasplata, John Shawe-Taylor, and Csaba Szepesvári. Tighter risk certifi- cates for neural networks. CoRR, abs/2007.129 2020.
David Reeb, Andreas Doerr. Sebastian Gerwinn, and Barbara Rakitsch. Learning Gaussian Processes by Minimizing PAC-Bayesian Generalization Bounds. In NeurIPS, 2018.
Omar Rivasplata, IIja Kuzborskij, Csaba Szepesvári, and John Thylor PAC-Bayes analysis beyond the usual bounds. In NeurIPS, 2020.
Jean-Francis Roy, François Laviolette, and Mario Marchand. From PAC-Bayes bounds quadratic programs for majority votes. In /CML. Omnipress, 2011.
Robert E. Schapire and Yoram Singer. Improved Boosting Algorithms Using Confidence-rateed Predictions. Machine Learning. 37, 1999.
Matthias W. Seeger. PAC-Bayesian generalisation error bounds for gaussian process classification. JMLR, 2002.
John Shawe-Tayee Taylor and David R. Hardoon. PAC-Bayes Analysis Of Maximum Entropy Classification. In AISTATS, 2009.
John Shawe-Taylo and Robert C. Williamson. A PAC analysis of bayesian estimator. COLT, 1997.
12

---

Niklas Thiemann, Christian Igel, Olivier Wintenberger, and Yevgeny Seldin. A strongly quasiconvex PAC-Bayesian bound. ALT, Proceedings of Machine Learning Research. PMLR, 2017.
Leslie Valiant. A theory of the learnable. Communications of the ACM, 27 1984.
Vladimir Naumovich Vapnik. The Nature of Statistical Learning Theory, Second Edition. Statistics for Engineering and Information Science. Springer, 2000. ISBN 978-0-387-98780-4.
Paul Viallard, Paseal Germain, Amaury Habrard, and Emilie Morvant. A General Framework for the Disintegration of PAC-Bayesian Bounds. CoRR, abs/2102.08649, 2021a.
Paul Viallard, Pascal Germain, Amaury Habrard, and Emilie Morvant. Self-bounding Majority
Vote Learning Algorithms by the Direct Minimization of Tight PAC-Bayesian C-Bound. In ECML-PKDD 2021, pages 167-183, 2021b.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: Novel Image Dataset for Bench- marking Machine Learning Algorithms. CoRR, cs.LG//108.007477, 2017.
13


Reviews:
[{"review_id": "voxVLtfNo7-", "reviewer": "Reviewer_t4tj", "summary": "The paper gives a tighter bound on the generalization of majority voting classifier by using a form of stochastic majority vote classifier. Using minimization of this bound, they are able to get better accuracy for the classifier as well as tighter generalization guarantees.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper uses PAC Bayesian bounds on stochastic majority voting scheme to get tighter generalization bounds on its performance. The paper is interesting and they are able to achieve good results experimentally. But, my main concern is that the main contribution of the paper is to get tighter generalization bounds by using stochastic majority votes. However, it is not clear to me why the bound is tighter when going from the error of one classifier to the expected majority vote classifier. On line 240, this conversion still introduces a factor of 2. So, it is not clear why this bound is tighter. The statement made in the paragraph is vague and hard to understand.\n\nCan the authors clarify the statement made in line 141 that second order and C-bounds fail to leverage the diversity in the whole set of classifiers?\n\nThe paper seems interesting to me. However, I feel that the paper is not well written and many claims are vague without proper explanation and thus, hard to understand. The writing of the paper can be improved.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "_S0r0ySJI2Y", "reviewer": "Reviewer_4Cot", "summary": "The paper proposes a novel majority-vote learning algorithm for finite hypothesis classes based on minimizing a PAC-Bayes bound. The paper also reports experimental results that the theoretical generalization bound is close to the observed held-out error i.e., the generalization bound is tight, when the base hypothesis class is a collection of decision trees.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality. Existing PAC-Bayes learning algorithms are designed to a) find a probability distribution Q over base hypotheses H and b) define the final majority-vote classifier as the one outputting the average prediction under Q. For finite hypothesis classes H, the paper’s learning algorithm modifies a) by implicitly redefining the base hypothesis class to be H’, where each element h’ is a convex combination of all the elements of H (Equation 4). With this H’, the paper returns to the standard methodology, by searching for Q’ by minimizing a generalization bound (either Theorem 1 or Theorem 2), and derandomizing to return the final majority-vote classifier. Section 3.1 and Section 3.2 explain that the generalization bound as a function of the parameters defining the distribution Q’ is differentiable. Therefore, first-order methods such as gradient descent can be used to reach (at least) local minima. More importantly, since the bounds hold for arbitrary Q’, it is always possible to evaluate performance even if training is not perfect (reaching global optima).\n\nQuality. The claims in the paper are well-supported by evidence. I have some questions if time permits/for future work. First, can we inspect how different the final majority vote classifier in Figure 5 for exact is from the baselines? I am puzzled by how the different methods have similar test errors, but the generalization bounds are so different. Since the majority votes are defined by the convex combination with respect to the base hypotheses, this should be simple visualization. Second, is there a concrete, synthetic situation that gives intuition why the paper’s approach of first implicitly defining H’ and then computing Q’ gives better bounds then the standard PAC-Bayes approach? As an analog, section 2.2 lists some ideas of why a second order bound is better than a first-order one (because of correlation among the base hypotheses). Is there something like that for StocMC? Third, what do the different components of the generalization bounds before the de-randomization stage look like? This is related to my first question. All the PAC-Bayes bounds balance a trade off between empirical fit (the Rhat term) with complexity (the KL term). Since the different methods in Figure 5 have similar test error, I am tempted to think that the difference in generalization bounds come from the complexity term. In any case it would be good to check!\n \nClarity. The paper is clear and well-written. One suggestion is putting the datasets where both the test error and the generalization bounds are too small (like sensorless, mushrooms) to the appendix. \n\nSignificance. The consistent ability of the generalization bound to approximate the test error from above (Figure 5) is very encouraging evidence that this kind of majority-vote algorithm can explain how ensemble methods generalize on unseen data.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is at least one other work also involving PAC-Bayes majority vote and decision trees that might be relevant to your work https://papers.nips.cc/paper/2018/hash/1819020b02e926785cf3be594d957696-Abstract.html. This paper aims to derive classifiers whose excess risk (risk of classifier minus Bayes risk) goes to zero if the hypothesis class is allowed to grow with the dataset size (like decision trees of increasing depth). The tightness here is a different sense than the tightness in your paper, however. \n\nOn another note, are extensions to continuous hypotheses spaces possible? For instance, neural networks. These are the hypothesis classes where most of the interesting work in statistical learning is being done currently. \n\nThe societal impact has been addressed well.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ZCLNMrEO-F", "reviewer": "Reviewer_pW3i", "summary": "The authors propose an algorithm for learning a *stochastic* weighted majority vote classifier, by optimizing a (PAC-Bayesian) generalization bound. They consider Dirichlet distributions over classifiers as well as general measures, and derive analytical and numerical schemes, respectively, for optimizing both. They empirically evaluate the algorithm for several datasets and model classes (decision stumps and random forest). They also compare against deterministic weighted majority vote classifiers learned by optimizing Gibbs classifiers via existing PAC-Bayes bounds (first order, secord order, C-bounds, etc). The resulting stochastic predictor achieves competitive performance and bound tightness compared to ones obtained by minimizing alternative bounds.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In my opinion, the paper presents fairly incremental ideas, combining data-dependent priors, a few other existing tricks in PAC-Bayes, like splitting the datasets in half, etc. From the technical perspective, the authors work out a closed form for stochastic Dirichlet predictors. This is a nice contribution, but appears to be relatively straightforward. Since the non-Dirichlet approach is competitive, it is not clear to me how useful the derived analytical expressions are. As the authors report, the MC variant seems to be fast and accurate with a range of base predictors.\n\nHowever, the empirical results are positive and the empirical evaluation is, I believe, novel. The clarity and quality are both good. Overall, I am leaning towards acceptance but would like to see authors’ responses to a few questions listed below (especially about the advantage of stochastic majority vote classifiers over non-stochastic counterparts).\n\nWhat are SOTA algorithms for optimizing standard (deterministic) weighted majority vote classifiers? The comparisons here are all to PAC-Bayes bound optimization, but are these algorithms at all competitive? And how about the same question but with stochastic majority vote classifiers? I would like the authors to provide references and report their (test) performance in the same cases as tested in Figure 5. How do they compare in error? If these other algorithms do better, what is the advantage of adding stochasticity? How do PAC-Bayes bounds on error of stochastic majority vote compare to held-out set bounds for non-stochastic majority vote achieved by these alternative algorithms?\n\nTo what extent does the empirical evaluation replicate what has already been reported in previous papers (e.g., on first and second order bounds)? That is: is the empirical evaluation performed here to be considered a novel contribution?\n\nWhen trained on the datasets used in Fig 5 (so not just the moon dataset), did you also observe that Dirichlet had high entropy/higher than for classifiers trained with alternative algorithms?\n\nThe authors also present a hypothesis why their algorithm’s performance (or tightness of the bound?) decreases (relative to other algorithms tested) under input noise (using 0-1 vs loss with margin information). While a theoretical analysis might be challenging, it would be nice to see some empirical evidence evaluating their hypothesis.\n\nAlso, what is the (approximate, perhaps) Bayes error for the noise levels used in Figure 12? What should we compare the performance against? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the following limitations of the proposed algorithm: the algorithm seems to underperform under input noise; the obtained guarantees get looser with an increasing number of base predictors. These seem to be fair limitations.\n\nThe authors do not foresee any negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "This work does not raise any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "NkThBigyX8", "reviewer": "Reviewer_62DW", "summary": "This paper studies the generalization properties of the stochastic weighted majority vote (MV) classifiers, where the weight of the MV follows another distribution over MVs. The proposal allows a direct analysis of the risk of the stochastic MV instead of analyzing through other empirical quantities, which leads to tighter bounds. By taking the distribution over MVs to be Dirichlet distributions, the authors also provide an exact and an approximation method to optimize the parameters of the distribution.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Most of the previous results for weighted majority vote (MV) considered the performance of a deterministic MV. To the best of my knowledge, this is the first investigation of stochastic MVs. The idea might open a new path to investigate the performance of the ensembled classifiers. However, some refinement in the paper might be required.\n\nMajor points:\n\n1) Equation (7) in the proof is incorrect, although the conclusion holds. The probability follows the distribution, but the equality doesn't hold. Also, Lemma 2 is important for the idea to work, but the reference or the proof of Lemma 2 is missing.\n\n2) The reported generalization bounds for the new methods are perhaps not very comparable to the others in the sense that it is the generalization bound for the stochastic MV, which is different from the deterministic MVs. If we consider the deterministic MV induced by the stochastic MV, for example, the expected MV, the bound would be 2 times larger.\n\n\nMinor points:\n\n1) The notation of the vectors is not consistent throughout the paper. It would be better to use (), instead of [] or {} to denote a vector. \"unit vector\" in line 161 should be \"all-ones vector.\" In the statement of Lemma 2, [1, M] should be [M]. The definition of R(\\rho) in line 175 is missing. \\hat{R}_{\\leq m} (\\hat{R}_{> m}), and their definitions in Line 233 are missing. \\mathcal{D} in line 224 should be D. Also, some references in the appendix are not properly handled, for instance, the captions of Figure 9 and Table 1.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. The authors have discussed the potentially large KL increasing with M. The runtime of the exact method could be large, while the runtime of the approximation method is small for smaller M but increases with M. On the other hand, I don't see any negative societal impact in this work so far.", "review_text": "", "extra_scores": {"ethical_concerns": "I don't see any so far.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers like the approach proposed in the paper and recommend acceptance. There were several clarity issues raised during the discussion and I hope they will be addressed in the final revision. In particular, the fixes to benchmark experiments that were discussed and revision of the two-moon experiment.
Decision: Accept (Poster)