Martingale Boosting∗
Rocco A. Servedio†
Columbia University
New York, NY
rocco@cs.columbia.edu

Philip M. Long
GoogleMountain View, CA
plong@google.com

September 15, 2008

Abstract
Martingale boosting is a simple and easily understood technique with a simple and easily understood analysis. A slight variant of the approach provably achieves optimal accuracy in the presence of
misclassification noise.

1 Introduction
Boosting [15, 8] has been an overwhelming practical success. In many applied domains, the best known
algorithms use boosting. Nevertheless, some time ago, sensitivity to noise was identified as a weakness ofthe standard boosting techniques [7, 11, 5].
Heuristics have been proposed to combat this [14, 13]. The heuristics are based on an implicit viewthat noisy examples tend to be borderline cases: they penalize noisy examples roughly in proportion to howmuch they deviate from the norm. This view has been seen to be useful, but there are applications in which
many examples are not borderline.
Some boosting algorithms have been shown to be provably noise-tolerant [16, 2, 3, 9, 10]. As in classification in general, the main approaches to theory for noise-tolerant boosting can be divided into agnostic/malicious and independent models. In the agnostic/malicious case, essentially nothing is assumed about
the noise, except a limit on its rate. This may appear to be more realistic than the alternative in which thelabels are assumed to be flipped independently of the sample. However, analysis of agnostic or malicious
noise models is by necessity focused on the worst case; typically, in this case, noisy examples are the mostextreme elements of the opposite class. Sources involving independent misclassification resemble applied
problems more than this. Thus, analysis of learning with independent misclassification noise may be themost effective way to use theory to guide the design of boosting algorithms that are robust to noisy data
other than borderline cases.
1.1 Our contribution This paper is about an approach that we call martingale boosting. We concentrateon the problem of predicting binary classifications, say 0 and 1. As in many earlier boosting algorithms,
learning proceeds incrementally in stages. In each stage, examples are partitioned into bins, and a separatebase classifier is chosen for each bin. An example is assigned a bin by counting the number of 1 predictions
made by the appropriate base classifiers from earlier rounds.
The analysis is very simple: it proceeds by thinking of an object to be classified as taking a random walkon the number of base classifiers that predict 1. If the error rates are balanced between false positives and∗†This is a full version which contains some proofs omitted from the conference version because of space.
Supported in part by NSF CAREER award CCF-0347282

1

false negatives and are slightly better than random guessing, it is easy to see that, after a few rounds, it isoverwhelmingly likely that more than half the steps are in the correct direction: such examples are classified
correctly by the boosted classifier.
In some cases, one can promote balanced error rates directly; for example, if decision stumps are usedas base classifiers, one can easily adjust the threshold to balance the error rates on the training data. We also
show that it is possible to force a standard weak learner to produce a classifier with balanced error rates in
the cases that we need.
Martingale boosting facilitates noise tolerance by the fact that the probability of reaching a given bin
depends on the predictions made by the earlier base classifiers, and not on the label of an example. (Inparticular, it does not depend on the number that are correct or incorrect, as does Boost-by-Majority [6].)The most technical aspect of the paper is to show that the reweighting to force balanced errors can be done
while preserving noise-tolerance. Ideas from earlier work by Kalai and Servedio [10] are useful there.
Because it is a simple and easily understood technique that generates highly noise-tolerant algorithms,
ideas from martingale boosting appear likely to be practically useful.
1.2 Organization Section 3 gives a high-level description of the architecture of our boosting algorithmand compares it with the three previous boosting algorithms which seem most closely related, namely the
Boost-by-Majority algorithm of Freund [6], the branching program booster of Mansour and McAllester [12]and the noise-tolerant booster of Kalai and Servedio [10].
In Section 4 we consider a learning scenario in which the weak learning algorithm is assumed to satisfy
a somewhat stronger guarantee than the usual weak learning assumption: the base classifier produced by
the weak learner is assumed to achieve accuracy significantly greater than 1/2 on both positive and negative
examples. Working in this scenario lets us highlight the main idea of our new boosting method; we givea very simple proof in Section 4 that our algorithm successfully boosts such a weak learner to arbitrary
accuracy.
In Section 5, we show how a slight modification of the algorithm from Section 4 can be used to boost
a standard weak learning algorithm, which only meets the usual weak learning criterion, to arbitrarily highaccuracy. We discuss computational issues and give an implementation of this algorithm in a framework
where the learner has access to an example oracle EX(c, D) in Section 6.
In Section 7, we show how the algorithm of Section 5 can be used to boost a random classification noise
tolerant weak learning algorithm to achieve final accuracy 1 − ǫ, where ǫ is any value greater than the noise
rate η. The modification described in this section is similar to that of Kalai and Servedio [10] who showed
how the boosting algorithm of McAllester and Mansour could be modified to achieve tolerance to randomclassification noise.

2 Preliminaries
Given a target concept c : X → {0, 1} and a distribution D over X, we write D + to denote the distribution
D restricted to the positive examples {x ∈ X : c(x) = 1}. Thus, for any event S ⊆ {x ∈ X : c(x) = 1}
we have PrD+ [x ∈ S] = PrD [x ∈ S]/PrD [c(x) = 1]. Similarly, we write D − to denote D restricted to thenegative examples {x ∈ X : c(x) = 0}.

3 High-level structure of the boosting algorithm
The boosting algorithm works in a series of T stages. The hypothesis of the boosting algorithm is a layered
branching program with T + 1 layers in a grid graph structure, where layer t has t + 1 nodes (see Figure 1);
we refer to the i-th node from the left in layer t as vi,t , where i ranges from 0 to t. For 0 ≤ t ≤ T − 1, eachnode vi,t in layer t has two outgoing edges, one left edge (which is labeled with a 0) to node vi,t+1 and one
right edge (labeled with a 1) to node vi+1,t+1 . Nodes vi,T in layer T have no outgoing edges.
2

v0,0
v1,1

v0,1
v0,2

v1,2
v1,3

v0,3

v2,T

v3,T

.....

z

vT −3,T

.....

v1,T

{

v3,3

.....

v0,T

output 0
}|

v2,3

.....

.....

z

v2,2

output 1}|

vT −2,TvT −1,T{vT,T

Figure 1: The branching program produced by the boosting algorithm. Each node vi,t is labeled with a
0/1-valued function hi,t ; left edges correspond to 0 and right edges to 1.
Before stage t of the boosting algorithm begins, each node at levels 0, . . . , t − 1 has been labeled witha 0/1-valued hypothesis function. We write hi,j to denote the hypothesis function that labels node vi,j .
In the t-th stage, hypothesis functions are assigned to each of the t + 1 nodes v0,t through vt,t at level t.
Given an example x ∈ X in stage t, the branching program routes the example by evaluating h0,1 on x
and then sending the example on the outgoing edge whose label is h0,1 (x), i.e. sending it to node vh0,1 (x),1 .
The example is routed through successive levels in this way until it reaches level t; more precisely, when
example x reaches some node vi,j in level j, it is routed from there via the outgoing edge whose label ishi,j (x) to the node vi+hi,j (x),j+1 . In this fashion the example x eventually reaches the node vℓ,t after being
evaluated on t hypotheses, where ℓ is the number of these t hypotheses which evaluated to 1 on x.
Thus, in the t-th stage of boosting, given an initial distribution D over examples x, the hypotheses
that have been assigned to nodes at levels 0, . . . , t − 1 of the branching program induce t + 1 different
distributions D0,t , . . . , Dt,t corresponding to the t + 1 nodes v0,t , . . . , vt,t in layer t (a random draw x from
distribution Di,t is a draw from D conditioned on x reaching vi,t ). In the following sections, we will
carefully specify just how the hypotheses h0,t , . . . , ht,t are generated to label the nodes v0,t , . . . , vt,t in thet-th stage of boosting; as we will see in Section 5, for the boosting algorithms that work in the standard
model, it is not the case that hi,t is obtained simply by running the weak learner on distribution Di,t andusing the resulting hypothesis as hi,t .
Once all T stages of boosting have been performed, the resulting branching program routes any example
x to some node vℓ,T at level T ; observe that ℓ is the number of hypotheses that evaluated to 1 out of the
T hypotheses that were evaluated on x. The final classifier computed by the branching program is simple:
given an example x to classify, if the final node vℓ,T that x reaches has ℓ ≥ T /2 then the output is 1, andotherwise the output is 0.
3.1 Relation to previous boosting algorithms Readers who are familiar with Freund’s paper on the
Boost-by-Majority algorithm [6] may experience a sense of déjà vu on looking at Figure 1, since a very
similar figure appears in [6]. Indeed, both our current boosting scheme and the Boost-by-Majority algorithm can be viewed as routing an example through a branching program which has the graph structure
shown in Figure 1, and both boosters work by ultimately predicting 1 or 0 according to whether the majority
of T weak hypotheses evaluate to 1 or 0. However, we emphasize that there is a very significant difference
between our boosting approach and that of [6]. In Boost-by-Majority, in stage t the weak learning algorithm3

is only invoked once, using a single distribution Dt that reweights each examples according to which nodevi,t at level t it arrives at. Thus, in Boost-by-Majority there are only T weak hypotheses that are ever generated in the course of boosting, and each node v0,t , . . . , vt,t is labeled with the same weak hypothesis ht ; thefinal output is a majority vote over these T hypotheses h1 , . . . , hT . In contrast, our algorithm invokes the
weak learner t + 1 separate times in stage t, once for each of the t + 1 distinct distributions D0,t , . . . , Dt,tcorresponding to the nodes v0,t , v1,t , . . . , vt,t . (We remind the reader again that as we will see in Section 5,
the hypothesis hi,t is not obtained simply by running the weak learner on Di,t and taking the resulting hypothesis to be hi,t .) A total of T (T + 1)/2 weak hypotheses are constructed, and any single example x only
encounters T of these hypotheses in its path through the branching program.
As we will see, our algorithm has a very simple proof of correctness which seems quite different fromthe Boost-by-Majority proof. Moreover, the fact that our algorithm constructs a different hypothesis hi,tfor each node vi,t seems to play an important role in enabling our boosting algorithm to tolerate randomclassification noise. We will show in Section 7 that a slight variant of our boosting algorithm can learn toany accuracy rate 1 − ǫ < 1 − η in the presence of random classification noise at rate η; no such guarantee
is given for Boost-by-Majority or any variant of it that we are aware of in the literature, and we were unable
to prove such a guarantee for Boost-by-Majority. It is an interesting question for future work to determine
whether Boost-by-Majority actually has (close to) this level of noise tolerance.
Another related algorithm is the “boosting by branching programs” algorithm of Mansour and McAllester[12], which we refer to as the MM algorithm. Kalai and Servedio [10] modified the MM algorithm to obtaina boosting algorithm which is robust in the presence of random classification noise.
Like the Mansour/McAllester boosting algorithm, our booster works by building a branching program.
Also, as mentioned earlier, our modification and analysis of this paper’s boosting algorithm to achieverandom classification noise tolerance will follow the approach of Kalai & Servedio. However, there are
significant differences between our boosting algorithm and this earlier work. The algorithm and analysisof [12] and [10] are based on the notion of “purity gain;” a node v is split into two descendents if each of
the two labels 0 and 1 is achieved by a nonnegligible fraction of the examples that reach v, and two nodesv and w are merged if the ratio of positive to negative examples within v is similar to the ratio within w.
Nodes that are pure (for some b ∈ {0, 1} almost all examples that reach v are labeled with b) are “frozen”(i.e. not split any more) and assigned the label b. In contrast, in our new algorithm the label of a given
terminal node in the branching program depends not on the majority vote label of examples that reach that
node, but on the majority vote label of the hypotheses that are evaluated on the path to the node. In theanalysis of our algorithm, progress is measured not in terms of purity gain achieved by splitting a node, butrather by the amount of “drift” in the right direction that a node imparts to the examples that reach it. (Wewill see, though, that notions of purity do play a role for efficiency reasons in the example oracle model
implementation of the algorithm that we describe in Section 6.)
We note also that the algorithms and analyses of [12, 10] gave little insight into the structure of the
branching programs that they create. In contrast, our algorithm yields a well-structured and easily intelligible
branching program as shown in Figure 1.

4 Boosting a two-sided weak learner
Let c : X → {0, 1} be the target function that we are trying to learn to high accuracy with respect todistribution D over X. Throughout this section the distributions D + and D − are defined with respect to c.
Definition 1. A hypothesis h : X → {0, 1} is said to have two-sided advantage γ with respect to D if itsatisfies both Prx∈D+ [h(x) = 1] ≥ 21 + γ and Prx∈D− [h(x) = 0] ≥ 21 + γ.
Thus such a hypothesis performs noticeably better than random guessing both on positive examples andon negative examples. In this section we will assume that we have access to a two-sided weak learner that,when invoked on target concept c and distribution D, outputs a hypothesis with two-sided advantage.
4

In the next section, we will perform an analysis using the usual assumption of having just a standard
weak learner. That analysis can be viewed as reducing that problem to the two-side model studied here.
However, results in the two-sided model are arguably interesting in their own right for the following reason.
In practice, boosting algorithms are often applied in conjunction with “decision stumps”, classifiers thatbase their predictions on whether individual variables are above or below thresholds. For such classifiers,
the threshold can be adjusted so that the training error is balanced between positive and negative examples,with a modest increase in the overall error rate; this promotes finding base classifiers with reasonably small
error on both kinds of examples, as is required by the definition in the two-sided model.
We now show how the general boosting framework of Section 3 can be used to boost a two-sided weaklearner to high accuracy. This is done very simply: in stage t, at each node vi,t we just run the two-sided
weak learner on examples drawn from Di,t (recall that this is the distribution obtained by filtering D toaccept only those examples that reach node vi,t ), and use the resulting hypothesis, which has two-sided
advantage with respect to Di,t , as the hypothesis function hi,t labeling node vi,t . We refer to this boosting
scheme as Basic MartiBoost.
The idea of the analysis is extremely simple. Let h denote the final branching program that Basic
Martiboost constructs. We will see that a random example x drawn from D + (i.e. a random positive
example) is routed through h according to a random walk that is biased toward the right, and a random
example x drawn from D − is routed through h according to a random walk that is biased toward the left.
Since h classifies example x according to whether x reaches a final node vℓ,T with ℓ ≥ T /2 or ℓ < T /2,
this will imply that h has high accuracy on both random positive examples and random negative examples.
So consider a random positive example x (i.e. x is distributed according to D + ). For any node vi,t ,conditioned on x reaching node vi,t we have that x is distributed according to (Di,t )+ . Consequently, by
the definition of two-sided advantage we have that x goes from node vi,t to node vi+1,t+1 with probability
at least 1/2 + γ, so x does indeed follow a random walk biased to the right. Similarly, for any node vi,t a
random negative example that reaches node vi,t will proceed to node vi,t+1 with probability at least 1/2 + γ,
and thus random negative examples follow a random walk biased to the left. Now standard bounds on), then the probability that a random positive
random walks are easily seen to imply that if T = O( logγ1/ǫ2
example x ends up at a node vℓ,T with ℓ < T /2 is at most ǫ. The same is true for random negative examples,
and thus h has overall accuracy at least 1 − ǫ with respect to D.
In more detail, we have the following theorem:
Theorem 1. Let γ0 , γ1 , . . . , γT −1 be any sequence of values between 0 and 1/2. For each value t =0, . . . , T −1, suppose that each of the t+1 invocations of the weak learner on distributions Di,t (with 0 ≤ i ≤t) yields a hypothesis hi,t which has two-sided advantage γt with respect to Di,t . Then the
output hy-  finalPT −1 2pothesis h that Basic Martiboost computes will satisfy Prx∈D [h(x) 6= c(x)] ≤ exp −( t=0 γt ) /(2T ) .
Proof. As sketched above, we will begin by bounding the error rate on positive examples (a nearly identical
proof will work for the negative examples).
For t = 0, . . . , T we define the integer-valued random variable Xt as follows: given a draw of x fromD + , let i denote the index of the node vi,t that x reaches at level t of the branching program. The value of
Xt is i.
Fix 1 ≤ t ≤ T and let us consider the conditional random variable (Xt |Xt−1 ). Conditioned on Xt−1
taking any particular value (i.e. on x reaching any particular node vi,t−1 ), we have that x is distributed
according to (Di,t−1 )+ , and thus we have
E[Xt |Xt−1 ] = Xt−1 +Prx∈(Di,t−1)+[hi,t−1 (x) = 1] ≥ Xt−1 +where the inequality follows from the two-sided advantage of hi,t−1 .
51+ γt−1 ,
2

(1)

P
1
Now for t = 0, . . . , T define the random variable Yt as Yt = Xt − t−1
i=0 ( 2 + γi ) (so Y0 = X0 = 0.)
Since each possible value of Yt−1 corresponds to a unique value of Xt−1 and vice versa, conditioning on
the value of Yt−1 is the equivalent conditioning on the value of Xt−1 . Using inequality (1) we obtain
"
#
t−1
t−1
X
X
1
1
( + γi )|Yt−1 = E[Xt |Yt−1 ] −E[Yt |Yt−1 ] = E Xt −( + γi )22
i=0≥ Xt−1 +1+ γt−1 −
2

t−1
X
i=0

1
( + γi ) = Xt−1 −
2

i=0
t−2
X
i=0

1
( + γi ) = Yt−1 ,2

so the sequence of random variables Y0 , . . . , YT is a sub-martingale. We have1
|Yt − Yt−1 | = |Xt − Xt−1 − ( + γt−1 )| ≤ 1,
2
so by Azuma’s inequality forP
sub-martingales (Theorem 7 in Appendix A) we get Pr[YT ≤ −λ] ≤−1exp(−λ2 /(2T )). We take λ = Tt=0γt , and observe that Pr[YT ≤ −λ] = Pr[XT ≤ T /2] = Prx∈D+ [h(x) =0] forh. Thus, we indeed have that the error rate on positive P examples is at most thePfinal hypothesis

exp −
done.

(

T −1
2
t=0 γt )2T. The same argument shows that Prx∈D− [h(x) = 1] ≤ exp −(T
2
t=1 γt )2T, and we areNote that if we have γt ≥ γ for all t, then Theorem 1 gives the familiar bound Prx∈D [h(x) 6= c(x)] ≤2exp(− γ 2T ). We further observe that if all the γt values are small and equal to the same value γ, then we
can replace the 1 in the upper bound on |Yt − Yt−1 | with a value close to 1/2; and this gives a final bound inwhich the constant in the exponent is close to 2 (rather than the current value of 1/2), which is optimal.

5 Boosting a standard weak learner
We recall the usual definition of a weak learner.
Definition 2. Given a target function c : X → {0, 1} and a distribution D, a hypothesis h : X → {0, 1} issaid to have advantage γ with respect to D if it satisfies Prx∈D [h(x) = c(x)] ≥ 21 + γ.
In this section we will assume that we have access to a standard weak learning algorithm which, wheninvoked on target concept c and distribution D, outputs a hypothesis h which has advantage γ with respect
to D. This is the usual assumption that is made in the study of boosting, and is clearly less demanding
than the two-sided weak learner we considered in the previous section. We will show how the Basic
Martiboost algorithm of the previous section can be modified to boost a standard weak learner to highaccuracy.
For clarity of exposition, throughout this section we will consider an abstract version of the boostingalgorithm in which all desired probabilities can be obtained exactly (i.e. we do not consider issues ofsampling error, etc. here). We will deal carefully with these issues when we describe an example oracle
model implementation of the algorithm in Section 6.
5.1 Definitions and an easy lemma Let c : X → {0, 1} be a target concept. We say that a distribution D
over X is balanced if D puts equal weight on positive and negative examples, i.e. Prx∈D [c(x) = 0] = 21 .
b to denote the balanced version of D
Given an arbitrary distribution D (not necessarily balanced), we write D
which is an equal average of D + and D − ; i.e. for any S ⊆ X we have PrDb [S] = 12 PrD+ [S] + 21 PrD− [S].
Given a distribution D over X and a hypothesis h : X → {0, 1}, we define bh, the balanced version of h,b
to be the (probabilistic) version of h described below; the key property of h is that it outputs 0 and 1 equally6h(x) = 1h(x) = 0c(x) = 1p
1/2 − pc(x) = 0q
1/2 − qh(x) = 1, b
h(x) = 1bh(x) = 1, h(x) = 0
h(x) = 0, bh(x) = 1bh(x) = 0, h(x) = 0

c(x) = 1c(x) = 0

p
2r

q
2r

1
p(1 − 2r
)
0
1
2 −p

1
q(1 − 2r
)
0
1
2 −q

Table 1: Each table entry gives the probability of the corresponding event under the balanced distributionD.
c(x) = 0c(x) = 1

hi,t (x) = 0
p
1/2 − phi,t (x) = 1
1/2 − pp

Table 2: Each table entry gives the probability of the corresponding event under the balanced distribution
d
D
i,t .

often under D. Let b ∈ {0, 1} be the value that h evaluates to more often, and let r = Prx∈D [h(x) = b]
(so 1/2 ≤ r ≤ 1). Given an input x ∈ X, to evaluate bh on x we toss a biased coin which comes up heads
1. If we get heads we output h(x), and if we get tails we output 1 − b. This ensures thatwith probability 2r1· r = 12 .
Prx∈D [bh(x) = b] = Pr[coin is heads & h(x) = b] = 2r
The following simple lemma shows that if we have a weak hypothesis h that has advantage γ relative toa balanced distribution D, then the balanced hypothesis bh has advantage at least γ/2 relative to D.

h(x) = c(x)] ≥ 12 + γ2 .
Lemma 1. If D is a balanced distribution and PrD [h(x) = c(x)] ≥ 21 + γ then PrD [bProof. We may assume without loss of generality that PrD [h(x) = 1] = r ≥ 12 , i.e. that b = 1 in the above
discussion. If we let p denote PrD [h(x) = 1 & c(x) = 1] and q denote PrD [h(x) = 1 & c(x) = 0], so
p + q = r, then the probabilities for all four possible values of h and c are given in the left side of Table 1.
From the definition of bh it is straightforward to verify that the probabilities of all eight combinations ofbvalues for h, hand c are as given in the right side of Table 1. We thus have that PrD [bh(x) = c(x)] =
p−q
p
1
1
1
1
+
q
1
−
+
−
q
=
+
.
By
assumption
we
have
Pr
[h(x)
=
c(x)]
≥
+
γ,
so from the left
D
2r
2r
2
2
2r
2
side of Table 1 we have p − q ≥ γ. The claim follows since r ≤ 1.
5.2 Boosting a standard weak learner with MartiBoost Our algorithm for boosting a standard weaklearner, which we call MartiBoost, works as follows. In stage t, at each node vi,t we run the weakdlearning algorithm on the balanced version D
i,t of the distribution Di,t ; let gi,t denote the hypothesis that the
weak learner returns. The hypothesis hi,t that is used to label vi,t is hi,t = gc
i,t , namely gi,t balanced withdrespect to the balanced distribution D.
i,t
The following lemma plays a key role in our proof of correctness:
Lemma 2. We have Pr(x∈Di,t )+ [hi,t (x) = 1] ≥ 21 + γ2 and Pr(x∈Di,t )− [hi,t (x) = 0] ≥ 21 + γ2 .

d
Proof. Since the original hypothesis gi,t that the weak learner returns when invoked with D
i,t has accuracy1dat least 2 + γ with respect to D
,
by
Lemma
1
we
have
that
the
balanced
hypothesis
hi,ti,t has accuracyγ1ddat least 2 + 2 with respect to D
[hi,t (x) = c(x) = 0]. Since D
i,t . Let p denote PrDi,t is a balanceddi,tdistribution and hi,t is a balanced hypothesis, it is easy to see that all four table entries must be as given in7

dTable 2, and thus PrDd [hi,t (x) = c(x)] = 2p ≥ 21 + γ2 , i.e. p ≥ 41 + γ4 . But since Di,t is an equal mixturei,tof (Di,t )+ and (Di,t )− , this implies that Prx∈(Di,t )+ [hi,t (x) = 1] ≥ ( 41 + γ4 )/ 21 = 12 + γ2 . We similarly havethat Prx∈(Di,t )− [hi,t (x) = 0] ≥ 21 + γ2 , and the lemma is proved.
With this lemma in hand it is easy to prove correctness of MartiBoost:
Theorem 2. Let γ0 , γ1 , . . . , γT −1 be any sequence of values between 0 and 1/2. For each value t =d0, . . . , T − 1, suppose that each of the t + 1 invocations of the weak learner on distributions D
i,t (with 0 ≤di ≤ t − 1) yields a hypothesis gi,t which has advantage γt with respect to D
.
Then
the
final
branchingproi,t PT( t=1 γt )2.
gram hypothesis h that MartiBoost constructs will satisfy Prx∈D [h(x) 6= c(x)] ≤ exp −8T
Proof. The proof is almost identical to the proof of Theorem 1. We define sequences of random variables
X1 , . . . , XT and Y0 , . . . , YT as before; the only difference is that (i) now we have E[Xt ] ≥ 21 + γ2t (byLemma 2) rather than E[Xt ] ≥ 21 + γt as in the earlier proof, and (ii) the randomness is now taken overboth the draw of x from D + and over the internal randomness of each hypothesis hi,t at each node in the
branching program. This loss of a factor of 2 from (i) in the advantage accounts for the different constant(worse by a factor of 4) in the exponent of the bound.

6 Complexity issues: implementation of MartiBoost that works with an example oracle
Thus far we have described and analyzed an abstract version of MartiBoost without specifying how thedweak learner is actually run on the distribution D
i,t at each node. One approach is to run the boostingalgorithm on a fixed sample. In this case all relevant probabilities can be maintained explicitly in a look-up
table, and then Theorem 2 bounds the training set accuracy of the MartiBoost final hypothesis over this
fixed sample.
In this section we describe and analyze an implementation of the algorithm in which the weak learnerruns given access to an example oracle EX(c, D). As we will see, this version of the algorithm requires
some changes for the sake of efficiency; in particular we will “freeze” the execution of the algorithm atdnodes vi,t where it is too expensive to simulate D
i,t . We give an analysis of the time and sample complexityof the resulting algorithm which shows that it is computationally efficient and can achieve a high accuracy
final hypothesis. Note that the accuracy in this case is measured with respect to the underlying distribution
generating the data (and future test data).
6.1

The model We define weak learning in the example oracle EX(c, D) framework as follows:

Definition 3. Given a target function c : X → {0, 1}, an algorithm A is said to be a weak learningalgorithm with advantage γ if it satisfies the following property: for any δ > 0 and any distribution D overX, if A is given δ and access to EX(c, D) then algorithm A outputs a hypothesis h : X → {0, 1} whichwith probability at least 1 − δ satisfies Prx∈D [h(x) = c(x)] ≥ 21 + γ.
We let mA (δ) denote the running time of algorithm A, where we charge one time step per invocation of
the oracle EX(c, D). Thus, if we must run algorithm A using a simulated oracle EX(c, D ′ ) but we only
have access to EX(c, D), the runtime will be at most mA (δ) times the amount of time it takes to simulate adraw from EX(c, D ′ ) given EX(c, D).
6.2 An idealized version of the oracle algorithm We now describe the version of MartiBoost designed to work with a sampling oracle in more detail; we call this algorithm Sampling Martiboost, or
SMartiBoost. While this algorithm is intended to work with random examples, to keep the focus clear on
the main ideas, let us continue for a while to assume that all required probabilities can be computed exactly.

8In Section 6.3 we will show that the analysis still holds if probabilities are estimated using a polynomial-size
sample.
For convenience, we will use r to denote all of the random bits used by all the hypotheses hi,t . It isconvenient to think of r as an infinite sequence of random bits that is determined before the algorithm starts
and then read off one at a time as needed by the algorithm (though the algorithm will use only polynomiallymany of them).
In stage t of SMartiBoost, all nodes at levels t′ < t have been labeled and the algorithm is labelingnodes v0,t , . . . , vt,t . Let pi,t denote Prx∈D,r [x reaches vi,t ]. For each b ∈ {0, 1}, let pbi,t denote Prx∈D,r [xreaches vi,t and the label of x is b], so pi,t = p0i,t + p1i,t . In stage t, SMartiBoost does the following foreach node vi,t :1. If minb∈{0,1} pbi,t < T (Tǫ+1) , then the algorithm “freezes” node vi,t by labeling it with the bit (1 − b)and making it a terminal node with no outgoing edges (so any example x which reaches vi,t will beassigned label (1 − b) by the branching program hypothesis).
2. Otherwise, we have minb∈{0,1} pbi,t ≥ T (Tǫ+1) . In this case SMartiBoost works just like MartiBoost:d
it runs the weak learning algorithm on the balanced version D
i,t of Di,t to obtain a hypothesis gi,t ,dand it labels vi,t with hi,t = gc
i,t , which is gi,t balanced with respect to Di,t .

The idea is that each node which is “frozen” in step (1) above contributes at most T (Tǫ+1) to the error of
the final branching program hypothesis; since there are at most T (T + 1)/2 many nodes in the branching
program, the total error induced by all frozen nodes is at most 2ǫ . On the other hand, for any node vi,t which
satisfies condition (2) and is not frozen, the expected number of draws from EX(c, D) that are required toT2dsimulate a draw from EX(c, Di,t ) is O( ǫ ), and thus we can indeed run the weak learner efficiently on thedesired distributions. (We discuss computational efficiency in more detail in the next subsection where wetake sampling issues into account.)
The following theorem establishes correctness of SMartiBoost:d. Suppose that each time it is invoked on some distribution D
Theorem 3. Let T = 8 ln(2/ǫ)
i,t , the weakγ2dlearner outputs a hypothesis that has advantage γ with respect to D
i,t . Then the final branching program
hypothesis h that SMartiBoost constructs will satisfy Prx∈D [h(x) 6= c(x)] ≤ ǫ.

Proof. Given an unlabeled instance x ∈ X and a particular setting r of the random bits for each of the(randomized) hypotheses hi,t labeling nodes of the branching program, we say that (x, r) freezes at nodevi,t if the path through the branching program that x takes under randomness r causes it to terminate at anode vi,t with t < T (i.e. at a node vi,t which was frozen by SMartiBoost). We havePr[h(x) 6= c(x)] = Pr[h(x) 6= c(x) & (x, r) freezes] + Pr[h(x) 6= c(x) & (x, r) does not freeze]ǫ+ Pr[h(x) 6= c(x) & (x, r) does not freeze].
≤2where the probabilities, as in the proof of Theorem 2, are taken over the draw of x from D and the choice ofr.
It remains to show that Pr[h(x) 6= c(x) & (x, r) does not freeze] ≤ 2ǫ . As before, we first will show that
Prx∈D+ [h(x) 6= c(x) & (x, r) does not freeze] is at most 2ǫ ; the negative examples can be handled similarly.
To show that Prx∈D+ [h(x) 6= c(x) & (x, r) does not freeze] ≤ 2ǫ , we consider a slightly different
random process than in the proof of Theorem 2. For t = 0, . . . , T we now define integer-valued randomvariables Xt′ as follows. Given a draw of x from D + and a random choice of r,9• If (x, r) does not freeze at any node vj,t′ with t′ < t, then Xt′ takes value i, where i denotes the index
of the node vi,t that x reaches under randomess r at level t of the branching program;• If (x, r) freezes at some node vj,t′ with t′ < t, then let k be the sum of t − t′ many independent 0/1
coin tosses each of which comes up 1 with probability 21 + γ2 . The value of Xt′ is j + k.
(This part of the proof is reminiscent of [3].) It is clear that′′+
E[Xt′ |Xt−1& (x, r) freezes at some node vj,t′ with t′ < t] = Xt−1

1 γ
+ .
2 2

On the other hand, if (x, r) does not freeze at any such node, then conditioned on x reaching any particular
node vi,t−1 under randomness r we have that x is distributed according to (Di,t−1 )+ . It follows from
Lemma 2 that′′+
E[Xt′ |Xt−1& (x, r) freezes at no node vj,t′ with t′ ≤ t] ≥ Xt−1

1 γ
+ ,
2 2

′ ] ≥ 1 + γ.
and thus overall we have E[Xt′ |Xt−1
2
2
Now similar to the proof of Theorem 1, for t = 0, . . . , T let the random variable Yt′ be defined as Yt′ =Xt′ − t( 12 + γ). As in the earlier proof we have that Y0 , . . . , YT is a sub-martingale
 withbounded differences,2

so Azuma’s inequality for sub-martingales gives Pr [YT′ ≤ −γT /2] ≤ exp − γ 8T . Now recall that if(x, r) never freezes, then the prediction h(x) is determined by the majority of the values of hi,t (x) obtained
from hypotheses hi,t encountered in its path through the branching program. Thus, in the particular case of
positive examples, Prx∈D+ ,r [h(x) 6= c(x) & (x, r) does not freeze] ≤ Pr [XT′ ≤ T /2] = Pr[Yt′ ≤ −γT /2].
Applying the inequality from above, bounding negative examples similarly, and recalling our choice of T,
we have that Pr[h(x) 6= c(x) & (x, r) does not freeze] ≤ 2ǫ and the theorem is proved.
6.3 Dealing with sampling error In this section we remove the assumptions that we know all required
probabilities exactly, by showing that sufficiently accurate estimates of them can be obtained efficiently. We
do not belabor details since sampling error analyses such as the one we now present are quite standard.
Consider some node vi,t . While we cannot determine precisely whether pbi,t is greater than T (Tǫ+1) ornot, standard multiplicative Chernoff bounds show that we can compare it up to a constant multiple whichis good enough for our purposes:
Fact 3. With O(
following:T 2 log 1δ
) many draws to EX(c, D), we can obtain an estimate p̃bi,t of pbi,t which satisfies theǫ• If pbi,t < 2T (Tǫ +1) , then with probability 1 − δ, we have that p̃bi,t is at most 4T (T3ǫ+1) ; and• If pbi,t > T (Tǫ+1) , then with probability 1 − δ, we have that p̃bi,t is at least 4T (T3ǫ+1) .
Thus SMartiBoost will actually decide whether or not to freeze a node vi,t by checking whether p̃bi,t3ǫ
d. If minb∈{0,1} pb is not too small then we can efficiently simulate draws from EX(c, Dexceedsi,t )
4T (T +1)i,td(by tossing a coin to decide whether EX(c, Di,t ) will give a positive or negative example, and then drawing
from EX(c, D) until it gives an example with the correct label which reaches vi,t ):Fact 4. If minb∈{0,1} pbi,t ≥ 2T (Tǫ +1) , then given access to EX(c, D) we can with probability 1 − δ perfectlydsimulate a draw from EX(c, Di,t ) by making at most O(
10

T 2 log δ1) many draws from EX(c, D).
ǫdOnce we have run the weak learning algorithm with EX(c, Di,t ) and it has given us its hypothesis gi,t ,dwe need to construct hi,t , the balanced version of this hypothesis with respect to D
i,t . In order to do thisperfectly as in Section 5.1, we would need the exact value of r = Prx∈Dd [gi,t (x) = b] ≥ 21 . While thisi,texact value is not available to us, the following straightforward generalization of Lemma 1 shows that an
approximate value is good enough for our needs:
Lemma 5. Let r ′ ∈ [0, 1] be any value such that |r − r ′ | ≤ γ4 where r is as described above. Let h′i,t denotethe “balanced” hypothesis obtained from gi,t as in Section 5.1 but using r ′ instead of r. If PrDd
[gi,t (x) =i,t[h′i,t (x) = c(x)] ≥ 21 + γ4 .
c(x)] ≥ 21 + γ, then PrDd
i,tStandard bounds on sampling show that we can obtain an estimate r ′ of r which is accurate to within andadditive ± γ4 with probability 1 − δ by making at most O( log(1/δ)) many draws from EX(c, Di,t ). Putting
γ2
all the pieces together, we have the following theorem which shows that SMartiBoost is correct andefficient (we use Õ notation to hide polylogarithmic factors, and ignore the dependences on δ – which are
everywhere polylogarithmic – throughout for the sake of readability):
Theorem 4. Let T = Θ( log(1/ǫ)γ 2 ). If A is a weak learning algorithm that requires sA many examples toconstruct a γ-advantage hypothesis, then SMartiBoost makes O(sA ) · Õ( 1ǫ ) · poly( γ1 ) many calls toEX(c, D) and with probability 1 − δ outputs a final hypothesis h that satisfies Prx∈D [h(x) 6= c(x)] ≤ ǫ.
Proof. A straightforward union bound over all failure probabilities (for each call of the weak learning algorithm and for each sampling-based estimate), together with Theorem 3, establishes correctness. For the
sample complexity bound, consider a single step of the algorithm when it is processing some node vi,t . Es2dtimating pbi,t takes Õ( Tǫ ) many draws by Fact 3, and then running the weak learner with EX(c, Di,t ) takes2Õ( sAǫT ) many draws from EX(c, D) by Fact 4. Estimating r at vi,t to “balance” the hypothesis gi,t that theT2dweak learner returns takes Õ( γ12 ) many draws from EX(c, Di,t ), i.e. Õ( γ 2 ǫ ) many draws from EX(c, D).
22

Thus, dealing with a single node vi,t takes Õ( sAǫT + γT2 ǫ ) many draws from EX(c, D). Since there areO(T 2 ) many nodes in the branching program and T = O( logγ1/ǫ
) we obtain the claimed bound.
2

7 A noise-tolerant version of SMartiBoost
In this section we show how the SMartiBoost algorithm can be modified to withstand random classification noise. We follow the approach of Kalai & Servedio [10], who showed how the MM branching program
boosting algorithm of Mansour and McAllester can be modified to withstand random classification noise.
Given a distribution D and a value 0 < η < 12 , a noisy example oracle is an oracle EX(c, D, η) thatworks as follows: each time EX(c, D, η) is invoked, it returns a labeled example (x, b) ∈ X × {0, 1} wherex ∈ X is drawn from distribution D and b is independently chosen to be c(x) with probability 1 − η and1 − c(x) with probability η.
Recall the definition of noise-tolerant weak learning:
Definition 4. Given a target function c : X → {0, 1}, an algorithm A is said to be a noise-tolerant weaklearning algorithm with advantage γ if it satisfies the following property: for any δ > 0 and any distribution
D over X, if A is given δ and access to a noisy example oracle EX(c, D, η) where 0 ≤ η < 21 , then A
1
1
runs in time poly( 1−2η
, 1δ ) and with probability at least 1 − δ A outputs a poly( 1δ , γ1 , 1−2η)-time evaluable1
hypothesis h such that Prx∈D [h(x) = c(x)] ≥ 2 + γ.
Ideally, we would like a boosting algorithm that can convert any noise-tolerant weak learning algorithm
into a noise-tolerant strong learning algorithm that can achieve any arbitrarily low error rate ǫ > 0. However,11Kalai and Servedio showed that in general it is not possible to boost the error rate ǫ down below the noise rate
η.1 They showed that a modification of the MM boosting algorithm, which they called the MMM (Modified
Mansour-McAllester) algorithm, can achieve any error rate ǫ = η + τ in time polynomial in τ1 and the otherrelevant parameters. We now show that a modification of SMartiBoost has the same property.
Throughout this section we assume that the value of η, the random classification noise rate, is known
in advance to the boosting algorithm. As described in [10] this assumption can be removed via a standard
approach of guessing different values for the noise rate and using the best outcome.
For ease of presentation, in Section 7.1 we give the noise-tolerant martingale boosting algorithm under
the assumption that all required probabilities are obtained exactly. In Section 7.2 we deal with issues of
estimating these probabilities via sampling and bound the sample complexity of the algorithm.
7.1 Boosting a noise-tolerant weak learner Roughly speaking, the reason why SMartiBoost can beeasily modified to withstand random classification noise is because in each stage t of boosting the label bof a labeled example (x, b) plays only a limited role in the reweighting that the example experiences. Since
this role is limited, it is possible for us to efficiently simulate the distributions that the weak learner requires
at each stage of boosting and thus for the overall boosting process to succeed.
More precisely, as a labeled example (x, b) proceeds through levels 0, . . . , t−1 of the branching programin stage t, the path it takes is completely independent of b. Thus, given a source EX(c, D, η) of noisy
examples, the distribution of examples that arrive at a particular node vi,t is precisely EX(c, Di,t , η). Oncea labeled example (x, b) arrives at some node vi,t , though, it is clear that the label b must be consulted in thed“rebalancing” of the distribution Di,t to obtain distribution D
i,t . More precisely, the labeled examples thatreach node vi,t are distributed according to EX(c, Di,t , η), but in order to use SMartiBoost with a noisedtolerant weak learner we must simulate the balanced distribution D
i,t corrupted with random classification′′dnoise, i.e. EX(c, D
,
η
).
(As
we
show
below,
it
turns
out
that
η
need
not necessarily be the same as η; it isi,t′′okay to have a higher noise rate η for the balanced oracle as long as η is not too close to 12 .) The following
lemma from [10] shows that it is possible to do this:Lemma 6. [Lemma 7 of [10]] Let τ > 0 be any value satisfying η + τ2 < 21 . Suppose we have access toEX(c, D, η). Let ρ denote Prx∈D [c(x) = 1]. Suppose that η+ τ2 ≤ ρ ≤ 12 (the case where η+ τ2 ≤ 1−ρ ≤ 12
is completely analogous). Consider the following rejection sampling procedure: given a draw (x, b) fromEX(c, D, η),1−2ρ
ρ−η• if b = 0 then with probability pr = 1−ρ−ηreject (x, b), and with probability 1 − pr = 1−ρ−η
setb′ = b and accept (x, b′ );(1−2ρ)η(1−η)(and set b′ to b with probability• if b = 1 then set b′ to 1 − b with probability pf = (1−ρ−η)(ρ+η−2ρη)
1 − pf ), and accept (x, b′ ).

this procedure rejects, andGiven a draw from EX(c, D, η), with probability prej := (1−2ρ)(ρη+(1−ρ)(1−η))
1−ρ−η
with probability 1 − prej = 2(1−2η)(1−ρ)ρ
the procedure accepts. Moreover, if the procedure accepts, then
1−ρ−η
ρ−η
′
b η ′ ) where η ′ = 1 −the (x, b ) that it accepts is distributed according to EX(c, D,.
22(ρ+η−2ρη)So the noise-tolerant version of SMartiBoost, which we call Noise-Tolerant SMartiBoost,works in the following way. As in Section 6.2 let pi,t denote Prx∈D,r [x reaches vi,t ]. For b = 0, 1 let
1They showed that if cryptographic one-way functions exist, then there is no efficient “black-box” boosting algorithm that canalways achieve a final error rate ǫ < η. A black-box boosting algorithm is a boosting algorithm that can run the weak learningalgorithm in a black-box fashion but cannot “inspect the code” of the weak learner. All known boosting algorithms are black-box
boosters. See [10] for more discussion.

12

b denote q b = Pr01qi,tx∈D,r [c(x) = b | x reaches vi,t ] = Prx∈Di,t ,r [c(x) = b], so qi,t + qi,t = 1. Thei,tboosting algorithm (which takes as input a parameter τ > 0, where η + τ is the desired final accuracy of the
hypothesis; we assume WLOG that η + τ < 21 ) proceeds in stage t as follows: at each node vi,t ,2τ
1. If pi,t < 3T (T+1) , then the algorithm “freezes” node vi,t by labeling it with an arbitrary bit and making
it a terminal node with no outgoing edges.
b < η + τ , then the algorithm “freezes” node v
2. Otherwise, if minb∈{0,1} qi,ti,t by labeling it with the3
bit (1 − b) and making it a terminal node with no outgoing edges.
′d3. Otherwise the algorithm runs the noise-tolerant weak learner using EX(c, D
i,t , η ) as described in
Lemma 6 to obtain a hypothesis gi,t . The balanced version of this hypothesis (balanced with respectdto Di,t ), which we call hi,t , is used to label node vi,t .

)′d. Suppose that each time it is invoked with some oracle EX(c, D
Theorem 5. Let T = 8 ln(3/τi,t , η ),γ2
the weak learner outputs a hypothesis gi,t that satisfies Prx∈Dd[gi,t (x) = c(x)] ≥ 21 + γ. Then thei,tfinal branching program hypothesis h that Noise-Tolerant SMartiBoost constructs will satisfy
Prx∈D [h(x) 6= c(x)] ≤ η + τ.

Proof. As in the proof of Theorem 3, given an unlabeled instance x ∈ X and a particular setting r of therandom bits for each of the (randomized) hypotheses hi,t labeling nodes of the branching program, we saythat (x, r) freezes at node vi,t if the path through the branching program that x takes under randomness r
causes it to terminate at a node vi,t with t < T (i.e. at a node vi,t which was frozen by Noise-Tolerant2τSMartiBoost). We say that a node vi,t is negligible if pi,t < 3T (T+1) . We havePr[h(x) 6= c(x)] = Pr[h(x) 6= c(x) & (x, r) does not freeze] +Pr[h(x) 6= c(x) & (x, r) freezes at a negligible node] +Pr[h(x) 6= c(x) & (x, r) freezes at a non-negligible node].
2τ
Since (x, r) reaches a given negligible node vi,t with probability at most 3T (T+1) and there are at most
T (T + 1)/2 many negligible nodes, Pr[h(x) 6= c(x)& (x, r) freezes at a negligible node] is at most τ3 .
Consequently Pr[h(x) 6= c(x)] is at most τ3 + Pr[h(x) 6= c(x) & (x, r) does not freeze] plusX

Pr[h(x) 6= c(x)| (x, r) freezes at vi,t ] · Pr[(x, r) freezes at vi,t ].

(2)i,t : vi,t is non-negligible

Since Pr[h(x) 6= c(x) | (x, r) freezes at vi,t ] equals Prx∈Di,t ,r [h(x) 6= c(x)], by the fact that the algorithmb < η + τ (case (2) above), we have that (2) is at most η + τ . Thus
freezes vi,t if minb∈{0,1} qi,t33Pr[h(x) 6= c(x)] ≤ Pr[h(x) 6= c(x) & (x, r) does not freeze] + η +2τ
.
3

so it remains to show that Pr[h(x) 6= c(x) & (x, r) does not freeze] is at most τ3 . The proof of this is
identical to the proof that Pr[h(x) 6= c(x) & (x, r) does not freeze] ≤ 2ǫ in the proof of Theorem 3 but now
with τ3 in place of 2ǫ .

13

7.2 Complexity issues for implementation of Noise-Tolerant SMartiBoost In this section weremove the assumptions that we know all required probabilities exactly, by showing that sufficiently accurate estimates of them can be obtained efficiently via a polynomial amount of sampling. (For simplicity,
throughout the discussion we continue to assume that we know the exact value of η as mentioned at the startof Section 7.)2
1/δ
A direct analogue of Fact 3 shows that O( T log) many draws to EX(c, D, η) suffice to give anτestimate p̃i,t of pi,t = Prx∈D,r [x reaches vi,t ] such that
• If pi,t < 3T (Tτ +1) , then with probability 1 − δ, we have that p̃i,t is at most 2T (Tτ +1) ; andτ
2τ• If pi,t > 3T (T+1) , then with probability 1 − δ, we have that p̃i,t is at least 2T (T +1) .

Thus Noise-Tolerant SMartiBoost will decide whether or not to freeze a node vi,t on the groundsof its being negligible (case (1)) by checking whether p̃i,t exceeds 2T (Tτ +1) .
For case (2), if pi,t is not too small then we can efficiently simulate draws from EX(c, Di,t , η), and thusb efficiently:
can estimate qi,t2

log 1/δbbFact 7. If pi,t ≥ 3T (Tτ +1) , then O( τT3 (1−2η)2 ) draws from EX(c, D, η) suffice to give an estimate q̃i,t of qi,tsuch thatb < η + τ , then with probability 1 − δ, we have that q̃ is at most η + τ ; and• If qi,ti,t6
4• If pbi,t > η + τ3 , then with probability 1 − δ, we have that q̃i,t is at most η + τ4 .
Proof. It is easy to see thatbqi,t
= Pr [c(x) = b] =x∈Di,tPr(x,y)∈EX(c,Di,t ,η) [y = b] − η.
1 − 2η

b to within an additive Θ(τ ), we must estimate Pr
Thus in order to estimate qi,t(x,y)∈EX(c,Di,t ,η) [y = b] to1within an additive Θ(τ (1 − 2η)). This requires Θ( τ 2 (1−2η)2 ) many draws from EX(c, Di,t , η), and since2pi,t = Ω( Tτ2 ), there is an overhead of Θ( Tτ ) to simulate each draw from EX(c, Di,t , η) using EX(c, D, η).
Now we consider case (3), which requires us to use the rejection sampling procedure of Lemma 6. We
first note that if the exact value of ρ = Prx∈Di,t [c(x) = 1] were available, then the probability prej of′drejecting would not be too high (so it would indeed be possible to efficiently simulate EX(c, D
i,t , η )):from Lemma 6 satisfies prej ≤ 1−(η+ τ2 ).
Claim 8. The rejection probability prej := (1−2ρ)(ρη+(1−ρ)(1−η))
1−ρ−η

Proof. Recall that η + τ2 ≤ ρ ≤ 12 . ¿From this it is straightforward to verify that we have
η+

τ
τ
τ
2ρ(1 − ρ)(1 − 2η)≤ 2(η + )(1 − η − ) ≤ 2ρ(1 − ρ) ≤
.
2
2
2
1−ρ−η

The claim follows since prej = (1−2ρ)(ρη+(1−ρ)(1−η))equals 1 − 2ρ(1−ρ)(1−2η)
.
1−ρ−η
1−ρ−η
This claim implies that given EX(c, Di,t , η), if ρ were known exactly then we could sample from21′
dEX(c, Di,t , η ) with a slowdown of at most η+τ /2 < τ . Moreover, if the exact value of ρ were available,
then the noise rate η ′ would not be too close to 21 (so it would be possible to efficiently run the weak learnerusing EX(c, Di,t , η)). This is because (as shown in Lemma 7 of [10]) the noise rate η ′ from Lemma 6
14

ρ−η
1
1
satisfies η ′ = 12 − 2(ρ+η−2ρη)≤ 12 − τ4 . Since the weak learner runs in time poly( 1−2η′ , δ ) when invoked
1 1′
don EX(c, D
i,t , η ), the runtime for each invocation of the weak learner would be bounded by poly( τ , δ ).
So if the exact value of ρ = Prx∈Di,t [c(x) = 1] were available, then using EX(c, D, η) we could
T 1′dsimulate EX(c, D
i,t , η ) and run the weak learner at a given node vi,t in poly( τ , δ ) time overall (there is anO( τT2 ) factor because of the overhead to simulate EX(c, Di,t , η) from EX(c, D, η)). But of course, we do
not have the exact value of the probability ρ that Lemma 6 requires; instead we must use an estimate ρ′ of ρthat we obtain by sampling. Since ρ′ is not exactly p, the oracle we simulate may not be exactly balanced,
and it may have slightly different noise rates for positive and negative examples; but as we now show, the′ddeviation from EX(c, D
i,t , η ) can be made so small that the weak learner is unaffected.
ρ̃−ηwhere ρ̃ equals Pr(x,b)∈EX(c,Di,t ,η) [b = 1]. Thus we can estimate ρ to
It is easy to see that ρ = 1−2η
within an additive ±ξ by estimating ρ̃ from EX(c, Di,t , η) to within an additive ±ξ(1 − 2η). As above, we
2 log 1/δ
can obtain such an estimate of ρ̃ (with probability 1 − δ) by making at most O( τTξ 2 (1−2η)2 ) many draws fromEX(c, D, η).
Thus, we may assume that we have an approximation ρ′ that is within an additive ±ξ of ρ. We now use
the following lemma (the proof is a routine but tedious error analysis applied to the proof of Lemma 7 of[10]):

Lemma 9. Consider the rejection sampling procedure defined in Lemma 6 but with ρ′ used in place of ρ in1such that if |ρ′ − ρ| ≤ ξ, thenthe definition of pr and pf . Given any ν > 0, there is a value ξ = poly(1/τ,1/ν)(i) this procedure rejects with probability at most 1 − (η + τ4 ) (and thus the rejection sampling procedure
incurs a slowdown of at most τ4 );(ii) if the procedure accepts, then the (x, b) that it accepts is distributed according to ( 12 −ρ)EX(c, (Di,t )+ , η+ )+1( 2 + ρ)EX(c, (Di,t )− , η− ) where |ρ| is at most ν and η+ , η− each differ from η ′ by at most an additive ±ν.
It is easy to check that since |ρ|, |η ′ − η+ | and |η ′ − η− | are all at most ν, the total variation distance′dbetween ( 21 − ρ)EX(c, (Di,t )+ , η+ ) + ( 21 + ρ)EX(c, (Di,t )− , η− ) and EX(c, D
i,t , η ) is at most 4ν. Since
1 1
the weak learner makes at most poly( τ , δ′ ) draws to the example oracle to achieve confidence 1 − δ′ that itδ′doutputs a satisfactory weak hypothesis when run on EX(c, D
i,t , η ), if we choose ν = poly(1/τ,1/δ′ ) then we
have confidence 1−δ that its behavior when run with ( 12 −ρ)EX(c, (Di,t )+ , η+ )+( 12 +ρ)EX(c, (Di,t )− , η− )′dwill be indistinguishable from its behavior when run with EX(c, D
i,t , η ). This in turn implies that we may
1 1take ξ =poly( τ , δ ), and thus that the overall runtime for each invocation of the weak learner to get gi,t is at1) factor.)
most poly(T, τ1 , 1δ ). (Recall that τ < 21 − η so a poly( τ1 ) factor subsumes a poly( 1−2ηFinally, as in Section 6.3, we must balance the hypothesis gi,t to obtain the hypothesis hi,t that will
actually be used at node vi,t . As in that earlier section, we can only approximately balance the hypothesis
but this is sufficient by an analysis similar to that of the previous section. So all in all, we have that incase (3) of Noise-Tolerant SMartiBoost, the time (and number of calls to EX(c, D, η) required
is poly(T, γ1 , τ1 , 1δ ) =poly( γ1 , τ1 , 1δ ).
Putting all the pieces together, we have the following theorem which establishes correctness and efficiency of the sampling-based version of Noise-Tolerant SMartiBoost:)). If A is a noise-tolerant weak learning
Theorem 6. Given any τ such that η + τ < 21 , let T = Θ( log(1/τγ2algorithm with advantage γ, then Noise-Tolerant SMartiBoost makes poly( γ1 , τ1 , 1δ ) many calls toEX(c, D, η) and with probability 1 − δ outputs a final hypothesis h that satisfies Prx∈D [h(x) 6= c(x)] ≤η + τ.

8 Conclusion
We are working on implementing the algorithm and evaluating its performance and noise tolerance on realworld data.
15

References[1] N. Alon, J. Spencer, and P. Erdos. The Probabilistic Method. Wiley-Interscience, New York, 1992.
[2] Shai Ben-David, Philip M. Long, and Yishay Mansour. Agnostic boosting. In Proceedings of the 14th
Annual Conference on Computational Learning Theory, pages 507–516, 2001.
[3] N. Bshouty and D. Gavinsky. On boosting with optimal poly-bounded distributions. Journal of Machine Learning Research, 3:483–506, 2002.
[4] F. Chung and L. Lu. Concentration inequalities and martingale inequalities. Internet Mathematics,
3(1):79–127, 2006.
[5] T.G. Dietterich. An experimental comparison of three methods for constructing ensembles of decision
trees: bagging, boosting, and randomization. Machine Learning, 40(2):139–158, 2000.
[6] Y. Freund. Boosting a weak learning algorithm by majority.
121(2):256–285, 1995.

Information and Computation,[7] Y. Freund and R. Schapire. Experiments with a new boosting algorithm. In Proceedings of the Thirteenth International Conference on Machine Learning, pages 148–156, 1996.
[8] Y. Freund and R. Schapire. A decision-theoretic generalization of on-line learning and an application
to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997.
[9] Dmitry Gavinsky. Optimally-smooth adaptive boosting and application to agnostic learning. Journalof Machine Learning Research, 4:101–117, 2003.
[10] A. Kalai and R. Servedio. Boosting in the presence of noise. In Proceedings of the 35th Annual
Symposium on Theory of Computing (STOC), pages 196–205, 2003.
[11] R. Maclin and D. Opitz. An empirical evaluation of bagging and boosting. In AAAI/IAAI, pages
546–551, 1997.
[12] Y. Mansour and D. McAllester. Boosting using branching programs. Journal of Computer and System
Sciences, 64(1):103–112, 2002.
[13] Llew Mason, Peter L. Bartlett, and Jonathan Baxter. Improved generalization through explicit optimization of margins. Machine Learning, 38(3):243–255, 2000.
[14] G. R atsch, T. Onoda, and K.-R. M uller. Soft margins for AdaBoost. Machine Learning, 42(3):287–
320, 2001.
[15] R. Schapire. The strength of weak learnability. Machine Learning, 5(2):197–227, 1990.
[16] R. Servedio. Smooth boosting and learning with malicious noise. Journal of Machine Learning Research, 4:633–648, 2003. Preliminary version in Proc. COLT’01.

A

Sub-Martingales and Azuma’s Inequality for Sub-Martingales

A sub-martingale is a sequence X0 , . . . , XT of random variables with finite means such that for 1 ≤ i ≤ T ,we have E[Xi |Xi−1 ] ≥ Xi−1 . (This is the definition given in [1]; the definition in [4] is stronger in that it
requires E[Xi |X1 , . . . , Xi−1 ] = Xi−1 .)The following theorem is well known, but for completeness we give a proof since we could not findprecisely this statement in the literature. The proof is nearly identical to the proof of Theorem 5.2 (Azuma’s
inequality for regular martingales) given in [4].
16Theorem 7. [Azuma’s Inequality for Sub-Martingales] Let 0 = X0 , . . . , XT be a sub-martingale which hasbounded differences, i.e.
|Xi − Xi−1 | ≤ ci for each i = 1, . . . , T .
Then for any λ > 0 we have
λ2
Pr[XT ≤ −λ] ≤ exp − PT2 i=1 c2i!

.

Proof. As in [4], for any fixed θ and |x| ≤ c we have
eθx ≤

1
1 θc
(e − e−θc )x + (eθc + e−θc ).
2c
2

For i = 1, . . . , T let Yi = Xi − Xi−1 , so |Yi | ≤ ci and E[Yi |Xi−1 ] ≥ 0. Then for θ < 0 we have


1 θci
1 θci
θYi
−θci
−θci
E[e |Xi−1 ] ≤ E(e − e)Yi + (e + e) Xi−1
2ci
2
1
1 θci
(e − e−θci )E[Yi |Xi−1 ] + (eθci + e−θci )
=
2ci
2
1 θci
≤
(e + e−θci )2
2 2≤ eθ ci /22where the last line uses the inequality cosh(x) ≤ ex /2 , valid for all x > 0.
Since
E[eθYi |Xi−1 ] = E[eθ(Xi −Xi−1 ) |Xi−1 ] = E[eθXi |Xi−1 ]e−θXi−1 ,we have2 2E[eθXi |Xi−1 ] ≤ eθ ci /2 · eθXi−1 .
So inductively, we have
E[eθXT ] = E[E[eθXT |XT −1 ]]2 2≤ eθ cT /2 E[eθXT −1 ]
..
.
!
T
Y
θ 2 c2i /2E[eθX0 ]
e
≤
i=1

= e

1 2 PT2θ
i=1 ci2.

Consequently for θ < 0 we have
Pr[XT ≤ −λ] = Pr[eθXT ≥ e−θλ ]≤ eθλ E[eθXT ]1 2 PT2
i=1 ci≤ eθλ+ 2 θ
Choose θ = − PTλ2i=1 ci.

to minimize this expression, and we have
λ2
Pr[XT ≤ −λ] ≤ exp − PT2 i=1 c2i17!

.