# consistency_of_weighted_majority_votes__37346034.pdf

Consistency of weighted majority votes

Daniel Berend Computer Science Department and Mathematics Department Ben Gurion University Beer Sheva, Israel berend@cs.bgu.ac.il

Aryeh Kontorovich Computer Science Department Ben Gurion University Beer Sheva, Israel karyeh@cs.bgu.ac.il

We revisit from a statistical learning perspective the classical decision-theoretic problem of weighted expert voting. In particular, we examine the consistency (both asymptotic and finitary) of the optimal Nitzan-Paroush weighted majority and related rules. In the case of known expert competence levels, we give sharp error estimates for the optimal rule. When the competence levels are unknown, they must be empirically estimated. We provide frequentist and Bayesian analyses for this situation. Some of our proof techniques are non-standard and may be of independent interest. The bounds we derive are nearly optimal, and several challenging open problems are posed.

1 Introduction

Imagine independently consulting a small set of medical experts for the purpose of reaching a binary decision (e.g., whether to perform some operation). Each doctor has some reputation , which can be modeled as his probability of giving the right advice. The problem of weighting the input of several experts arises in many situations and is of considerable theoretical and practical importance. The rigorous study of majority vote has its roots in the work of Condorcet [1]. By the 70s, the field of decision theory was actively exploring various voting rules (see [2] and the references therein). A typical setting is as follows. An agent is tasked with predicting some random variable Y { 1} based on input Xi { 1} from each of n experts. Each expert Xi has a competence level pi (0, 1), which is the probability of making a correct prediction: P(Xi = Y ) = pi. Two simplifying assumptions are commonly made:

(i) Independence: The random variables {Xi : i [n]} are mutually independent conditioned on the truth Y . (ii) Unbiased truth: P(Y = +1) = P(Y = 1) = 1/2.

We will discuss these assumptions below in greater detail; for now, let us just take them as given. (Since the bias of Y can be easily estimated from data, only the independence assumption is truly restrictive.) A decision rule is a mapping f : { 1}n { 1} from the n expert inputs to the agent s final decision. Our quantity of interest throughout the paper will be the agent s probability of error, P(f(X) = Y ). (1) A decision rule f is optimal if it minimizes the quantity in (1) over all possible decision rules. It was shown in [2] that, when Assumptions (i) (ii) hold and the true competences pi are known, the optimal decision rule is obtained by an appropriately weighted majority vote:

f OPT(x) = sign

where the weights wi are given by

wi = log pi 1 pi , i [n]. (3)

Thus, wi is the log-odds of expert i being correct and the voting rule in (2), also known as naive Bayes [3], may be seen as a simple consequence of the Neyman-Pearson lemma [4].

Main results. The formula in (2) raises immediate questions, which apparently have not previously been addressed. The first one has to do with the consistency of the Nitzan-Paroush optimal rule: under what conditions does the probability of error decay to zero and at what rate? In Section 3, we show that the probability of error is controlled by the committee potential Φ, defined by

2) log pi 1 pi . (4)

More precisely, we prove in Theorem 1 that log P(f OPT(X) = Y ) Φ, where denotes equivalence up to universal multiplicative constants.

Another issue not addressed by the Nitzan-Paroush result is how to handle the case where the competences pi are not known exactly but rather estimated empirically by ˆpi. We present two solutions to this problem: a frequentist and a Bayesian one. As we show in Section 4, the frequentist approach does not admit an optimal empirical decision rule. Instead, we analyze empirical decision rules in various settings: high-confidence (i.e., |ˆpi pi| 1) vs. low-confidence, adaptive vs. nonadaptive. The low-confidence regime requires no additional assumptions, but gives weaker guarantees (Theorem 5). In the high-confidence regime, the adaptive approach produces error estimates in terms of the empirical ˆpis (Theorem 7), while the nonadaptive approach yields a bound in terms of the unknown pis, which still leads to useful asymptotics (Theorem 6). The Bayesian solution sidesteps the various cases above, as it admits a simple, provably optimal empirical decision rule (Section 5). Unfortunately, we are unable to compute (or even nontrivially estimate) the probability of error induced by this rule; this is posed as a challenging open problem.

2 Related work

Machine learning theory typically clusters weighted majority [5, 6] within the framework of online algorithms; see [7] for a modern treatment. Since the online setting is considerably more adversarial than ours, we obtain very different weighted majority rules and consistency guarantees. The weights wi in (2) bear a striking similarity to the Adaboost update rule [8, 9]. However, the latter assumes weak learners with access to labeled examples, while in our setting the experts are static . Still, we do not rule out a possible deeper connection between the Nitzan-Paroush decision rule and boosting.

In what began as the influential Dawid-Skene model [10] and is now known as crowdsourcing, one attempts to extract accurate predictions by pooling a large number of experts, typically without the benefit of being able to test any given expert s competence level. Still, under mild assumptions it is possible to efficiently recover the expert competences to a high accuracy and to aggregate them effectively [11]. Error bounds for the oracle MAP rule were obtained in this model by [12] and minimax rates were given in [13].

In a recent line of work [14, 15, 16] have developed a PAC-Bayesian theory for the majority vote of simple classifiers. This approach facilitates data-dependent bounds and is even flexible enough to capture some simple dependencies among the classifiers though, again, the latter are learners as opposed to our experts. Even more recently, experts with adversarial noise have been considered [17], and efficient algorithms for computing optimal expert weights (without error analysis) were given [18]. More directly related to the present work are the papers of [19], which characterizes the consistency of the simple majority rule, and [20, 21, 22] which analyze various models of dependence among the experts.

3 Known competences

In this section we assume that the expert competences pi are known and analyze the consistency of the Nitzan-Paroush optimal decision rule (2). Our main result here is that the probability of error P(f OPT(X) = Y ) is small if and only if the committee potential Φ is large.

Theorem 1. Suppose that the experts X = (X1, . . . , Xn) satisfy Assumptions (i)-(ii) and f OPT : { 1}n { 1} is the Nitzan-Paroush optimal decision rule. Then

(i) P(f OPT(X) = Y ) exp 1

(ii) P(f OPT(X) = Y ) 3 8[1 + exp(2Φ + 4

As we show in the full paper [27], the upper and lower bounds are both asymptotically tight. The remainder of this section is devoted to proving Theorem 1.

3.1 Proof of Theorem 1(i)

Define the {0, 1}-indicator variables

ξi = 1{Xi=Y }, (5)

corresponding to the event that the ith expert is correct. A mistake f OPT(X) = Y occurs precisely when1 the sum of the correct experts weights fails to exceed half the total mass:

P(f OPT(X) = Y ) = P

Since Eξi = pi, we may rewrite the probability in (6) as

A standard tool for estimating such sum deviation probabilities is Hoeffding s inequality. Applied to (7), it yields the bound

P(f OPT(X) = Y ) exp

which is far too crude for our purposes. Indeed, consider a finite committee of highly competent experts with pi s arbitrarily close to 1 and X1 the most competent of all. Raising X1 s competence sufficiently far above his peers will cause both the numerator and the denominator in the exponent to be dominated by w2 1, making the right-hand-side of (8) bounded away from zero. The inability of Hoeffding s inequality to guarantee consistency even in such a felicitous setting is an instance of its generally poor applicability to highly heterogeneous sums, a phenomenon explored in some depth in [23]. Bernstein s and Bennett s inequalities suffer from a similar weakness (see ibid.). Fortunately, an inequality of Kearns and Saul [24] is sufficiently sharp to yield the desired estimate: For all p [0, 1] and all t R,

(1 p)e tp + pet(1 p) exp 1 2p 4 log((1 p)/p)t2 . (9)

Remark. The Kearns-Saul inequality (9) may be seen as a distribution-dependent refinement of Hoeffding s (which bounds the left-hand-side of (9) by et2/8), and is not nearly as straightforward to prove. An elementary rigorous proof is given in [25]. Following up, [26] gave a soft proof based on transportation and information-theoretic techniques.

1 Without loss of generality, ties are considered to be errors.

Put θi = ξi pi, substitute into (6), and apply Markov s inequality:

P(f OPT(X) = Y ) = P

Ee twiθi = pie (1 pi)wit + (1 pi)epiwit

exp 1 + 2pi 4 log(pi/(1 pi))w2 i t2 = exp 1

2)wit2 , (11)

where the inequality follows from (9). By independence,

i Ee twiθi exp

and hence P(f OPT(X) = Y ) exp 1

2Φt2 Φt . Choosing t = 1 yields the bound in Theorem 1(i).

3.2 Proof of Theorem 1(ii)

Define the { 1}-indicator variables

ηi = 2 1{Xi=Y } 1, (12)

corresponding to the event that the ith expert is correct and put qi = 1 pi. The shorthand w η = Pn i=1 wiηi will be convenient. We will need some simple lemmata, whose proofs are deferred to the journal version [27]. Lemma 2.

P(f OPT(X) = Y ) = 1

η { 1}n max {P(η), P( η)}

P(f OPT(X) = Y ) = 1

η { 1}n min {P(η), P( η)} ,

where P(η) = Q

i:ηi=1 pi Q

i:ηi= 1 qi.

Lemma 3. Suppose that s, s (0, )m satisfy Pm i=1(si + s i) a and R 1 si/s i R, i [m], for some R < . Then Pm i=1 min {si, s i} a/(1 + R). Lemma 4. Define the function F : (0, 1) R by

F(x) = x(1 x) log(x/(1 x))

Then sup0<x<1 F(x) = 1

Continuing with the main proof, observe that

i=1 (pi qi)wi = 2Φ (13)

and Var [w η] = 4 Pn i=1 piqiw2 i . By Lemma 4, piqiw2 i 1

2(pi qi)wi, and hence

Var [w η] 4Φ. (14)

Define the segment I R by

Chebyshev s inequality together with (13) and (14) implies that

P (w η I) 3 4. (16)

Consider an atom η { 1}n for which w η I. The proof of Lemma 2 shows that

P(η) P( η) = exp (w η) exp(2Φ + 4

where the inequality follows from (15). Lemma 2 further implies that

P(f OPT(X) = Y ) 1

η { 1}n:w η I min {P(η), P( η)} 3/4 1 + exp(2Φ + 4

where the second inequality follows from Lemma 3, (16) and (17). This completes the proof.

4 Unknown competences: frequentist

Our goal in this section is to obtain, insofar as possible, analogues of Theorem 1 for unknown expert competences. When the pis are unknown, they must be estimated empirically before any useful weighted majority vote can be applied. There are various ways to model partial knowledge of expert competences [28, 29]. Perhaps the simplest scenario for estimating the pis is to assume that the ith expert has been queried independently mi times, out of which he gave the correct prediction ki times. Taking the {mi} to be fixed, define the committee profile by k = (k1, . . . , kn); this is the aggregate of the agent s empirical knowledge of the experts performance. An empirical decision rule ˆf : (x, k) 7 { 1} makes a final decision based on the expert inputs x together with the committee profile. Analogously to (1), the probability of a mistake is

P( ˆf(X, K) = Y ). (18)

Note that now the committee profile is an additional source of randomness. Here we run into our first difficulty: unlike the probability in (1), which is minimized by the Nitzan-Paroush rule, the agent cannot formulate an optimal decision rule ˆf in advance without knowing the pis. This is because no decision rule is optimal uniformly over the range of possible pis. Our approach will be to consider weighted majority decision rules of the form

ˆf(x, k) = sign

i=1 ˆw(ki)xi

and to analyze their consistency properties under two different regimes: low-confidence and highconfidence. These refer to the confidence intervals of the frequentist estimate of pi, given by

4.1 Low-confidence regime

In the low-confidence regime, the sample sizes mi may be as small as 1, and we define2

ˆw(ki) = ˆw LC i := ˆpi 1

2, i [n], (21)

which induces the empirical decision rule ˆf LC. It remains to analyze ˆf LC s probability of error. Recall the definition of ξi from (5) and observe that

E ˆw LC i ξi = E[(ˆpi 1

2)ξi] = (pi 1

since ˆpi and ξi are independent. As in (6), the probability of error (18) is

i=1 ˆw LC i ξi 1

i=1 ˆw LC i

2 For mi min {pi, qi} 1, the estimated competences ˆpi may well take values in {0, 1}, in which case log(ˆpi/ˆqi) = . The rule in (21) is essentially a first-order Taylor approximation to w( ) about p = 1

where Zi = ˆw LC i (ξi 1

2). Now the {Zi} are independent random variables, EZi = (pi 1

2)2 (by (22)), and each Zi takes values in an interval of length 1

2. Hence, the standard Hoeffding bound applies:

P( ˆf LC(X, K) = Y ) exp

We summarize these calculations in

Theorem 5. A sufficient condition for P( ˆf LC(X, K) = Y ) 0 is 1 n Pn i=1(pi 1

Several remarks are in order. First, notice that the error bound in (24) is stated in terms of the unknown {pi}, providing the agent with large-committee asymptotics but giving no finitary information; this limitation is inherent in the low-confidence regime. Secondly, the condition in Theorem 5 is considerably more restrictive than the consistency condition Φ implicit in Theorem 1. Indeed, the empirical decision rule ˆf LC is incapable of exploiting a single highly competent expert in the way that f OPT from (2) does. Our analysis could be sharpened somewhat for moderate sample sizes {mi} by using Bernstein s inequality to take advantage of the low variance of the ˆpis. For sufficiently large sample sizes, however, the high-confidence regime (discussed below) begins to take over. Finally, there is one sense in which this case is easier to analyze than that of known {pi}: since the summands in (23) are bounded, Hoeffding s inequality gives nontrivial results and there is no need for more advanced tools such as the Kearns-Saul inequality (9) (which is actually inapplicable in this case).

4.2 High-confidence regime

In the high-confidence regime, each estimated competence ˆpi is close to the true value pi with high probability. To formalize this, fix some 0 < δ < 1, 0 < ε 5, and put qi = 1 pi, ˆqi = 1 ˆpi. We will set the empirical weights according to the plug-in Nitzan-Paroush rule

ˆw HC i := log ˆpi

ˆqi , i [n], (25)

which induces the empirical decision rule ˆf HC and raises immediate concerns about ˆw HC i = . We give two kinds of bounds on P( ˆf HC = Y ): nonadaptive and adaptive. In the nonadaptive analysis, we show that for mi min {pi, qi} 1, with high probability |wi ˆw HC i | 1, and thus a perturbed version of Theorem 1(i) holds (and in particular, w HC i will be finite with high probability). In the adaptive analysis, we allow ˆw HC i to take on infinite values3 and show (perhaps surprisingly) that this decision rule also asymptotically achieves the rate of Theorem 1(i).

Nonadaptive analysis. The following result captures our analysis of the nonadaptive agent:

Theorem 6. Let 0 < δ < 1 and 0 < ε < min {5, 2Φ/n}. If

mi min {pi, qi} 3 4ε + 1 1

δ , i [n], (26)

P ˆf HC(X, K) = Y δ + exp (2Φ εn)2

Remark. For fixed {pi} and mini [n] mi , we may take δ and ε arbitrarily small and in this limiting case, the bound of Theorem 1(i) is recovered.

3 When the decision rule is faced with evaluating sums involving , we automatically count this as an error.

Adaptive analysis. Theorem 6 has the drawback of being nonadaptive, in that its assumptions (26) and conclusions (27) depend on the unknown {pi} and hence cannot be evaluated by the agent (the bound in (24) is also nonadaptive4). In the adaptive (fully empirical) approach, all results are stated in terms of empirically observed quantities: Theorem 7. Choose any5 δ Pn i=1 1 mi and let R be the event where

2 Pn i=1(ˆpi 1

2) ˆw HC i δ

2. Then P R n ˆf HC(X, K) = Y o δ.

Remark 1. Our interpretation for Theorem 7 is as follows. The agent observes the committee profile K, which determines the {ˆpi, ˆw HC i }, and then checks whether the event R has occurred. If not, the adaptive agent refrains from making a decision (and may choose to fall back on the low-confidence approach described previously). If R does hold, however, the agent predicts Y according to ˆf HC. Observe that the event R will only occur if the empirical committee potential ˆΦ = Pn i=1(ˆpi 1

2) ˆw HC i is sufficiently large i.e., if enough of the experts competences are sufficiently far from 1

2. But if this is not the case, little is lost by refraining from a high-confidence decision and defaulting to a low-confidence one, since near 1

2, the two decision procedures are very similar.

As explained above, there does not exist a nontrivial a priori upper bound on P( ˆf HC(X, K) = Y ) absent any knowledge of the pis. Instead, Theorem 7 bounds the probability of the agent being fooled by an unrepresentative committee profile.6 Note that we have done nothing to prevent ˆw HC i = , and this may indeed happen. Intuitively, there are two reasons for infinite ˆw HC i : (a) noisy ˆpi due to mi being too small, or (b) the ith expert is actually highly (in)competent, which causes ˆpi {0, 1} to be likely even for large mi. The 1/ mi term in the bound insures against case (a), while in case (b), choosing infinite ˆw HC i causes no harm (as we show in the proof).

Proof of Theorem 7. We will write the probability and expectation operators with subscripts (such as K) to indicate the random variable(s) being summed over. Thus,

PK,X,Y R n ˆf HC(X, K) = Y o = PK,η R ˆw HC η 0

= EK 1R Pη ˆw HC η 0 | K .

Recall that the random variable η { 1}n, with probability mass function P(η) = Q

i:ηi=1 pi Q

i:ηi= 1 qi, is independent of K, and hence

Pη ˆw HC η 0 | K = Pη ˆw HC η 0 . (28)

Define the random variable ˆη { 1}n (conditioned on K) by the probability mass function P(ˆη) = Q i:ηi=1 ˆpi Q i:ηi= 1 ˆqi, and the set A { 1}n by A = x : ˆw HC x 0 . Now Pη ˆw HC η 0 Pˆη ˆw HC ˆη 0 = |Pη (A) Pˆη (A)| max A { 1}n |Pη (A) Pˆη (A)|

= Pη Pˆη TV

i=1 |pi ˆpi| =: M,

where the last inequality follows from a standard tensorization property of the total variation norm TV, see e.g. [33, Lemma 2.2]. By Theorem 1(i), we have Pˆη ˆw HC ˆη 0 exp 1

2 Pn i=1(ˆpi 1

2) ˆw HC i , and hence Pη ˆw HC η 0 M + exp 1

2 Pn i=1(ˆpi 1

2) ˆw HC i . Invoking (28), we substitute the right-hand side above into (28) to obtain

PK,X,Y R n ˆf HC(X, K) = Y o EK

4The term oracle was suggested by a referee for this setting. 5 Actually, as the proof will show, we may take δ to be a smaller value, but with a more complex dependence on {mi}, which simplifies to 2[1 (1 (2 m) 1)n] for mi m. 6These adaptive bounds are similar in spirit to empirical Bernstein methods, [30, 31, 32], where the agent s confidence depends on the empirical variance.

By the definition of R, the second term on the last right-hand side is upper-bounded by δ/2. To estimate M, we invoke a simple mean absolute deviation bound (cf. [34]):

EK |pi ˆpi|

mi 1 2 mi ,

which finishes the proof.

Remark. The improvement mentioned in Footnote 5 is achieved via a refinement of the bound Pη Pˆη TV Pn i=1 |pi ˆpi| to Pη Pˆη TV α ({|pi ˆpi| : i [n]}), where α( ) is the function defined in [33, Lemma 4.2].

Open problem. As argued in Remark 1, Theorem 7 achieves the optimal asymptotic rate in {pi}. Can the dependence on {mi} be improved, perhaps through a better choice of ˆw HC?

5 Unknown competences: Bayesian

A shortcoming of Theorem 7 is that when condition R fails, the agent is left with no estimate of the error probability. An alternative (and in some sense cleaner) approach to handling unknown expert competences pi is to assume a known prior distribution over the competence levels pi. The natural choice of prior for a Bernoulli parameter is the Beta distribution, namely pi Beta(αi, βi) with

density p αi 1 i q βi 1 i B(αi,βi) , where αi, βi > 0, qi = 1 pi and B(x, y) = Γ(x)Γ(y)/Γ(x + y). Our full probabilistic model is as follows. Each of the n expert competences pi is drawn independently from a Beta distribution with known parameters αi, βi. Then the ith expert, i [n], is queried independently mi times, with ki correct predictions and mi ki incorrect ones. As before, K = (k1, . . . , kn) is the (random) committee profile. Absent direct knowledge of the pis, the agent relies on an empirical decision rule ˆf : (x, k) 7 { 1} to produce a final decision based on the expert inputs x together with the committee profile k. A decision rule ˆf Ba is Bayes-optimal if it minimizes P( ˆf(X, K) = Y ), which is formally identical to (18) but semantically there is a difference: the former is over the pi in addition to (X, Y, K). Unlike the frequentist approach, where no optimal empirical decision rule was possible, the Bayesian approach readily admits one: ˆf Ba(x, k) = sign (Pn i=1 ˆw Ba i xi), where

ˆw Ba i = log αi + ki βi + mi ki . (29)

Notice that for 0 < pi < 1, we have ˆw Ba i mi wi, almost surely, both in the frequentist and

the Bayesian interpretations. Unfortunately, although P( ˆf Ba(X, K) = Y ) = P( ˆw Ba η 0) is a deterministic function of {αi, βi, mi}, we are unable to compute it at this point, or even give a non-trivial bound. The main source of difficulty is the coupling between ˆw Ba and η.

Open problem. Give a non-trivial estimate for P( ˆf Ba(X, K) = Y ).

6 Discussion

The classic and seemingly well-understood problem of the consistency of weighted majority votes continues to reveal untapped depth and suggest challenging unresolved questions. We hope that the results and open problems presented here will stimulate future research.

[1] J.A.N. de Caritat marquis de Condorcet. Essai sur l application de l analyse a la probabilit e des d ecisions rendues a la pluralit e des voix. AMS Chelsea Publishing Series. Chelsea Publishing Company, 1785.

[2] S. Nitzan, J. Paroush. Optimal decision rules in uncertain dichotomous choice situations. International Economic Review, 23(2):289 297, 1982.

[3] T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2009.

[4] J. Neyman, E. S. Pearson. On the problem of the most efficient tests of statistical hypotheses. Phil. Trans. Royal Soc. A: Math., Physi. Eng. Sci., 231(694-706):289 337, 1933.

[5] N. Littlestone, M. K. Warmuth. The weighted majority algorithm. In FOCS, 1989.

[6] N. Littlestone, M. K. Warmuth. The weighted majority algorithm. Inf. Comput., 108(2):212 261, 1994.

[7] N. Cesa-Bianchi, G. Lugosi. Prediction, learning, and games. 2006.

[8] Y. Freund, R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci., 55(1):119 139, 1997.

[9] R. E. Schapire, Y. Freund. Boosting. Foundations and algorithms. 2012.

[10] A. P. Dawid and A. M. Skene. Maximum likelihood estimation of observer error-rates using the EM algorithm. Applied Statistics, 28(1):20 28, 1979.

[11] F. Parisi, F. Strino, B. Nadler, Y. Kluger. Ranking and combining multiple predictors without labeled data. Proc. Nat. Acad. Sci., 2014+.

[12] H. Li, B. Yu, D. Zhou. Error rate bounds in crowdsourcing models. Co RR, abs/1307.2674, 2013.

[13] C. Gao, D. Zhou. Minimax Optimal Convergence Rates for Estimating Ground Truth from Crowdsourced Labels (ar Xiv:1310.5764), 2014.

[14] A. Lacasse, F. Laviolette, M. Marchand, P. Germain, N. Usunier. PAC-Bayes bounds for the risk of the majority vote and the variance of the gibbs classifier. In NIPS, 2006.

[15] F. Laviolette, M. Marchand. PAC-Bayes risk bounds for stochastic averages and majority votes of samplecompressed classifiers. JMLR, 8:1461 1487, 2007.

[16] J.-F. Roy, F. Laviolette, M. Marchand. From PAC-Bayes bounds to quadratic programs for majority votes. In ICML, 2011.

[17] Y. Mansour, A. Rubinstein, M. Tennenholtz. Robust aggregation of experts signals, preprint 2013.

[18] E. Eban, E. Mezuman, A. Globerson. Discrete chebyshev classifiers. In ICML (2), 2014.

[19] D. Berend, J. Paroush. When is Condorcet s jury theorem valid? Soc. Choice Welfare, 15(4):481 488, 1998.

[20] P. J. Boland, F. Proschan, Y. L. Tong. Modelling dependence in simple and indirect majority systems. J. Appl. Probab., 26(1):81 88, 1989.

[21] D. Berend, L. Sapir. Monotonicity in Condorcet s jury theorem with dependent voters. Social Choice and Welfare, 28(3):507 528, 2007.

[22] D. P. Helmbold and P. M. Long. On the necessity of irrelevant variables. JMLR, 13:2145 2170, 2012.

[23] D. A. Mc Allester, L. E. Ortiz. Concentration inequalities for the missing mass and for histogram rule error. JMLR, 4:895 911, 2003.

[24] M. J. Kearns, L. K. Saul. Large deviation methods for approximate probabilistic inference. In UAI, 1998.

[25] D. Berend, A. Kontorovich. On the concentration of the missing mass. Electron. Commun. Probab., 18(3), 1 7, 2013.

[26] M. Raginsky, I. Sason. Concentration of measure inequalities in information theory, communications and coding. Foundations and Trends in Communications and Information Theory, 10(1-2):1 247, 2013.

[27] D. Berend, A. Kontorovich. A finite-sample analysis of the naive Bayes classifier. Preprint, 2014.

[28] E. Baharad, J. Goldberger, M. Koppel, S. Nitzan. Distilling the wisdom of crowds: weighted aggregation of decisions on multiple issues. Autonomous Agents and Multi-Agent Systems, 22(1):31 42, 2011.

[29] E. Baharad, J. Goldberger, M. Koppel, S. Nitzan. Beyond condorcet: optimal aggregation rules using voting records. Theory and Decision, 72(1):113 130, 2012.

[30] J.-Y. Audibert, R. Munos, C. Szepesv ari. Tuning bandit algorithms in stochastic environments. In ALT, 2007.

[31] V. Mnih, C. Szepesv ari, J.-Y. Audibert. Empirical Bernstein stopping. In ICML, 2008.

[32] A. Maurer, M. Pontil. Empirical Bernstein bounds and sample-variance penalization. In COLT, 2009.

[33] A. Kontorovich. Obtaining measure concentration from Markov contraction. Markov Proc. Rel. Fields, 4:613 638, 2012.

[34] D. Berend, A. Kontorovich. A sharp estimate of the binomial mean absolute deviation with applications. Statistics & Probability Letters, 83(4):1254 1259, 2013.