Machine Learning manuscript No.
(will be inserted by the editor)

Random Classification Noise
Defeats All Convex Potential Boosters

Philip M. Long · Rocco A. Servedio

Received: date / Accepted: date

Abstract A broad class of boosting algorithms can be interpreted as performing
coordinate-wise gradient descent to minimize some potential function of the margins
of a data set. This class includes AdaBoost, LogitBoost, and other widely used andwell-studied boosters. In this paper we show that for a broad class of convex potentialfunctions, any such boosting algorithm is highly susceptible to random classificationnoise. We do this by showing that for any such booster and any nonzero random classification noise rate η, there is a simple data set of examples which is efficiently learnableby such a booster if there is no noise, but which cannot be learned to accuracy better
than 1/2 if there is random classification noise at rate η. This holds even if the booster
regularizes using early stopping or a bound on the L1 norm of the voting weights. This
negative result is in contrast with known branching program based boosters which do
not fall into the convex potential function framework and which can provably learn tohigh accuracy in the presence of random classification noise.
Keywords boosting · learning theory · noise-tolerant learning · misclassificationnoise · convex loss · potential boosting
Mathematics Subject Classification (2000) 68Q32 · 68T05

1 Introduction
1.1 Background
Much work has been done on viewing boosting algorithms as greedy iterative algorithms
that perform a coordinate-wise gradient descent to minimize a potential function of
the margin of the examples, see e.g. [3, 13, 22, 8, 21, 2]. In this framework every potential
Philip M. Long
Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043
E-mail: plong@google.com
Rocco A. Servedio
Computer Science Department, Columbia University, New York, NY 10027
E-mail: rocco@cs.columbia.edu

2function φ defines an algorithm that may possibly be a boosting algorithm; we denotethe algorithm corresponding to φ by Bφ . For example, AdaBoost [12] and its confidencerated generalization [23] may be viewed as the algorithm Bφ corresponding to thepotential function φ(z) = e−z . The MadaBoost algorithm of Domingo and Watanabe[6] may be viewed as the algorithm Bφ corresponding toφ(z) =(

1−z

if z ≤ 0−z

if z > 0.

e(1)(We give a more detailed description of exactly what the algorithm Bφ is for a given
potential function φ in Section 2.)

1.2 Motivation: noise-tolerant boosters?
It has been widely observed that AdaBoost can suffer poor performance when run on
noisy data, see e.g. [11, 18, 5]. The most commonly given explanation for this is that theexponential reweighting of examples which it performs (a consequence of the exponential potential function) can cause the algorithm to invest too much “effort” on correctlyclassifying noisy examples. Boosting algorithms such as MadaBoost [6] and LogitBoost[13] based on a range of other potential functions have subsequently been provided,
sometimes with an explicitly stated motivation of rectifying AdaBoost’s poor noise
tolerance. However, we are not aware of rigorous results establishing provable noise
tolerance for any boosting algorithms that fit into the potential functions framework,
even for mild forms of noise such as random classification noise (henceforth abbreviated RCN) at low noise rates. This motivates the following question: are Adaboost’s
difficulties in dealing with noise due solely to its exponential weighting scheme, or arethese difficulties inherent in the potential function approach to boosting?

1.3 Our results: convex potential boosters cannot withstand random classification
noiseThis paper shows that the potential function boosting approach provably cannot yieldlearning algorithms that tolerate even low levels of random classification noise whenconvex potential functions are used. More precisely, we exhibit a fixed natural set ofbase classifiers h1 , . . . , hn and show that for every convex function φ satisfying somevery mild conditions and every noise rate η > 0, there is a multiset S of labeled
examples such that the following holds:– There is a linear separator sgn(α1 h1 +· · ·+αn hn ) over the base classifiers h1 , . . . , hnthat correctly labels every example in S with margin γ > 0 (and hence it is easy fora boosting algorithm trained on S to efficiently construct a final hypothesis that
correctly classifies all examples in S). However,– When the algorithm Bφ is run on the distribution Dη,S , it constructs a classifierthat has error rate 1/2 on the examples in S. Here Dη,S is the uniform distribution
over S but where examples are corrupted with random classification noise at rate
η, i.e. labels are independently flipped with probability η.

3We also show that convex potential boosters are not saved by regularization throughearly stopping [20, 26] or a bound on the L1 norm of the voting weights (see [22, 17]).
These results show that random classification noise can cause convex potentialfunction boosters to fail in a rather strong sense. We note that as discussed in Section 9,
there do exist known boosting algorithms [14, 15] that can tolerate random classificationnoise, and in particular can efficiently achieve perfect accuracy on S, after at mostpoly(1/γ) stages of boosting, when run on Dη,S in the scenario described above.
A number of recent results have established the statistical consistency of boostingalgorithms [4, 19, 25, 17, 26, 1] under various assumptions on a random source generating
the data. Our analysis does not contradict theirs roughly for the following reason. The
output of a boosting classifier takes the form sign(f (x)), where the unthresholded f (x)can be thought of as incorporating a confidence rating – usually, this is how much moreweight votes for one class than the other. The analyses that establish the consistencyof boosting algorithms typically require a linear f to have “potential” as good as any f(see e.g. Condition 1 from [1]). In this paper, we exploit the fact that convex potential
boosters choose linear hypotheses to force the choice between many “cheap” errors andfew “expensive” ones. If any f is allowed, then an algorithm can make all errors equallycheap by making all classifications with equally low confidence.
Though the analysis required to establish our main result is somewhat delicate,
the actual construction is quite simple and admits an intuitive explanation (see Section 4.2). For every convex potential function φ we use the same set of only n = 2
base classifiers (these are confidence-rated base classifiers which output real values in
the range [−1, 1]), and the multiset S contains only three distinct labeled examples;one of these occurs twice in S, for a total multiset size of four. We expect that manyother constructions which similarly show the brittleness of convex potential boosters to
random classification noise can be given. We describe experiments with one such construction that uses Boolean-valued weak classifiers rather than confidence-rated onesin Section 8.

2 Background and Notation
Throughout the paper X will denote the instance space. H = {h1 , . . . , hn } will denote a fixed finite collection of base classifiers over X, where each base classifier isa function hi : X → [−1, 1]; i.e. we shall work with confidence-rated base classifiers.
S = (x1 , y 1 ), . . . , (xm , y m ) ∈ (X × {−1, 1})m will denote a multiset of m examples
with binary labels.
For each convex potential function φ, we will consider three kinds of convex potential boosters: global-minimizing convex potential boosters, L1 -regularized convex
potential boosters, and early-stopping convex potential boosters. First, we will definea convex potential function, then each kind of boosting algorithm in turn.

2.1 Convex potential functions
We adopt the following natural definition which, as we discuss in Section 7, capturesa broad range of different potential functions that have been studied.
Definition 1 We say that φ : R → R is a convex potential function if φ satisfies thefollowing properties:

4

1. φ is convex and nonincreasing and φ ∈ C 1 (i.e. φ is differentiable and φ′ is continuous);
2. φ′ (0) < 0 and limx→+∞ φ(x) = 0.

2.2 Convex potential boosters
Let φ be a convex potential function, H = {h1 , . . . , hn } a fixed set of base classifiers,
and S = (x1 , y 1 ), . . . , (xm , y m ) a multiset of labeled examples.
All the boosting algorithms will choose voting weights α1 , ..., αn and output theclassifier
!
n
X
sign
αi hi (x)i=1

obtained by taking the resulting vote over the base classifier predictions. Let
F (x; α1 , ..., αn ) =nXαi hi (x)i=1denote the quantity whose sign is the outcome of the vote, and whose magnitude reflects
how close the vote was.

2.3 Global-minimizing convex potential boosters
The most basic kind of convex potential booster is the idealized algorithm that chooses
voting weights α1 , ..., αn to minimize the “global” potential function over S:
Pφ,S (α1 , ..., αn ) =mXφ(y i F (xi ; α1 , ..., αn )).

(2)

i=1

It is easy to check that this is a convex function from Rn (the space of all possible(α1 , . . . , αn ) coefficient vectors for F ) to R. We will denote this booster by Bφideal .

2.4 L1 -regularized boosters
For any C > 0, the L1 -regularized booster minimizes Pφ,S subject to the constraintP
L1
that ni=1 |αi | ≤ C. We will denote this booster by Bφ,C ; see [22, 17] for algorithms ofthis sort.
2.5 Early-stopping regularized boosters
To analyze regularization by early stopping, we must consider how the optimization is
performed. Similarly to Duffy and Helmbold [7, 8], we consider an iterative algorithm
which we denote Bφ . The algorithm performs a coordinatewise gradient descent throughthe space of all possible coefficient vectors for the weak hypotheses, in an attempt tominimize the convex potential function of the margins of the examples. We now give amore precise description of how Bφ works when run with H on S.

5

Algorithm Bφ maintains a vector (α1 , ..., αn ) of voting weights for the base classifiers h1 , ..., hn . The weights are initialized to 0. In a given round T , the algorithmchooses an index iT of a base classifier, and modifies the value of αiT . If αiT had
previously been zero, this can be thought of as adding base classifier number iT to apool of voters, and choosing a voting weight.
P
Let F (x; α1 , ..., αn ) = ni=1 αi hi (x) be the master hypothesis that the algorithm
has constructed prior to stage T (so at stage T = 1 the hypothesis F is identicallyzero).
In stage T the algorithm Bφ first chooses a base classifier by chooses iT to be theindex i ∈ [n] which maximizes−∂
P (α1 , ..., αn ),∂αi φ,Sand then choosing a new value of αiT in order to minimize Pφ,S (α1 , ..., αn ) for the
resulting α1 , ..., αn . Thus, in the terminology of [7] we consider “un-normalized” algorithms which preserve the original weighting factors α1 , α2 , etc. The AdaBoost algorithm is an example of an algorithm that falls into this framework, as are the otheralgorithms we discuss in Section 7. Note that the fact that Bφ can determine the exactly optimal weak classifier to add in each round errs on the side of pessimism in our
analysis.
early
For each K, let Bφ,K
be the algorithm that performs K iterations of Bφ , and thenhalts and outputs the resulting classifier.

2.6 Distributions with noise
In our analysis, we will consider the case in which the boosters are being run on a
distribution Dη,S obtained by starting with a finite multiset of examples, and adding
independent misclassification noise. One can naturally extend the definition of eachtype of booster to apply to probability distributions over X × {−1, 1} by extending thedefinition of potential in (2) as follows:
Pφ,D (α1 , ..., αn ) = E(x,y)∼D (φ(yF (x; α1 , ..., αn ))).

(3)

For rational values of η, running Bφ on (3) for D = Dη,S is equivalent to running Bφover a finite multiset in which each element of S occurs a number of times proportional
to its weight under D.

2.7 BoostingFix a classifier c : X → {−1, 1} and a multiset S = (x1 , y 1 ), . . . , (xm , y m ) of examples
labeled according to c. We say that a set of base classifiers H = {h1 , . . . , hn } is boostablewith respect to c and S if there is a vector α ∈ Rn such that for all i = 1, . . . , m, wehavesgn[α1 h1 (xi ) + · · · + αn hn (xi )] = y i .
If γ > 0 is such that“”y i · α1 h1 (xi ) + · · · + αn hn (xi )|α1 | + · · · + |αn |≥γ

6for all i, we say that H is boostable w.r.t. c and S with margin γ.
It is well known that if H is boostable w.r.t. c and S with margin γ, then a range ofdifferent boosting algorithms (such as AdaBoost) can be run on the noise-free data set S
to efficiently construct a final classifier that correctly labels every example in S. As onemconcrete example, after O( log
γ 2 ) stages of boosting AdaBoost will construct a linear
Pn
combination F (x) = i=1 γi hi (x) of the base classifiers such that sgn(F (xi )) = y i for
all i = 1, . . . , m; see [12, 23] for details.
2.8 Random classification noise and noise-tolerant boosting
Random classification noise is a simple, natural, and well-studied model of how benign(nonadversarial) noise can affect data. Given a multiset S of labeled examples and avalue 0 < η < 12 , we write Dη,S to denote the distribution corresponding to S corrupted
with random classification noise at rate η. A draw from Dη,S is obtained by drawing(x, y) uniformly at random from S and independently flipping the binary label y withprobability η.
We say that an algorithm B is a boosting algorithm which tolerates RCN at rateη if B has the following property. Let c be a target classifier, S be a multiset of m
examples, and H be a set of base classifiers such that H is boostable w.r.t. c and S.
Then for any ǫ > 0, if B is run with H as the set of base classifiers on Dη,S , at somestage of boosting B constructs a classifier g which has accuracy|{(xi , y i ) ∈ S : g(xi ) = y i }|≥ 1 − η − ǫ.
m
The accuracy rate above is in some sense optimal, since known results [14] showthat no “black-box” boosting algorithm can be guaranteed to construct a classifier
g whose accuracy exceeds 1 − η in the presence of RCN at rate η. As we discuss in
Section 9, there are known boosting algorithms [14, 15] which can tolerate RCN at rate
η for any 0 < η < 1/2. These algorithms, which do not follow the convex potentialfunction approach but instead build a branching program over the base classifiers, usepoly(1/γ, log(1/ǫ)) stages to achieve accuracy 1 − η − ǫ in the presence of RCN at rateη if H is boostable w.r.t. c and S with margin γ.

3 Main Result
As was just noted, there do exist boosting algorithms (based on branching programs)that can tolerate RCN. Our main result is that no convex potential function booster
can have this property:
Theorem 1 Fix any convex potential function φ and any noise rate 0 < η < 1/2.
Then(i) The global-minimizing booster Bφideal does not tolerate RCN at rate η;
early(ii) For any number K of rounds, the early-stopping regularized booster Bφ,K
does nottolerate RCN at rate η; andL1(iii) For any C > 0, the L1 -regularized booster Bφ,C
does not tolerate RCN at rate η.

7

Our first analysis holds for the global optimization and early-stopping convex potential boosters. It establishes parts (i) and (ii) of Theorem 1 through the following
stronger statement, which shows that there is a simple RCN learning problem for whichearly
Bφideal and Bφ,K
will in fact misclassify half the examples in S.
Theorem 2 Fix the instance space X = [−1, 1]2 ⊂ R2 and the set H = {h1 (x) =x1 , h2 (x) = x2 } of confidence-rated base classifiers over X.
There is a target classifier c such that for any noise rate 0 < η < 1/2 and any
convex potential function φ, there is a value γ > 0 and a multiset S of four labeled
examples (three of which are distinct) such that (a) H is boostable w.r.t. c and S withearly
margin γ, but (b) when Bφideal or Bφ,K
is run on the distribution Dη,S , it constructs
a classifier which misclassifies two of the four examples in S.
Our theorem about L1 which establishes part (iii) is as follows.
Theorem 3 Fix the instance space X = [−1, 1]2 ⊂ R2 and the set H = {h1 (x) =x1 , h2 (x) = x2 } of confidence-rated base classifiers over X.
There is a target classifier c such that for any noise rate 0 < η < 1/2 and any
convex potential function φ, any C > 0 and any β > 0, there is a value γ > 0 and amultiset S of examples such that (a) H is boostable w.r.t. c and S with margin γ, but
L1(b) when the L1 -regularized potential booster Bφ,Cis run on the distribution Dη,S , itconstructs a classifier which misclassifies 21 − β fraction of the examples in S.

Section 4 contains our analysis for the global optimization booster Bφideal ; the early
stopping and L1 regularization boosters are dealt with in Sections 5 and 6 respectively.

4 Analysis of the global optimization booster
We are given an RCN noise rate 0 < η < 1/2 and a convex potential function φ.

4.1 The basic idea
Before specifying the sample S we explain the high-level structure of our argument.
Recall from (3) that Pφ,D is defined as
Pφ,D (α1 , α2 ) =X

Dη,S (x, y)φ(y(α1x1 + α2 x2 )).

(4)

(x,y)

As noted in Section 2.2 the function Pφ,D (α1 , α2 ) is convex. It follows immediately fromthe definition of a convex potential function that Pφ,D (α1 , α2 ) ≥ 0 for all (α1 , α2 ) ∈R2 .
The high-level idea of our proof is as follows. We shall construct a multiset S offour labeled examples in [−1, 1]2 (actually in the unit disc {x : kxk ≤ 1} ⊂ R2 ) suchthat there is a global minimum (α∗1 , α∗2 ) of the corresponding Pφ,D (α1 , α2 ) for which
the corresponding classifier g(x) = sgn(α∗1 x1 + α∗2 x2 ) misclassifies two of the points in
S (and thus has error rate 1/2).

8“puller”(γ, 5γ)“penalizers”(γ, −γ)“large margin” example(1, 0)

Fig. 1 The sample S. All four examples are positive. We show that for a suitable 0 < γ < 1/6(based on the convex potential function φ), the “puller” example at (γ, 5γ) causes the optimal
hypothesis vector to incorrectly label the two “penalizer” examples as negative.

4.2 The sample S
Now let us define the multiset S of examples. S consists of three distinct examples,one of which is repeated twice. (We shall specify the value of γ later and show that
0 < γ < 61 .)– S contains one copy of the example x = (1, 0) with label y = +1. (We call this the“large margin” example.)– S contains two copies of the example x = (γ, −γ) with label y = +1. (We call theseexamples the “penalizers” since they are the points that Bφ will misclassify.)– S contains one copy of the example x = (γ, 5γ) with label y = +1. (We call thisexample the “puller” for reasons described below.)Thus all examples in S are positive. It is immediately clear that the classifier c(x) =sgn(x1 ) correctly classifies all examples in S with margin γ > 0, so the set H ={h1 (x) = x1 , h2 (x) = x2 } of base classifiers is boostable w.r.t. c and S with margin γ.
We further note that since γ < 61 , each example in S does indeed lie in the unit disc{x : kxk ≤ 1}.
Let us give some intuition. The halfspace whose normal vector is (1, 0) classifies
all examples correctly, but the noisy (negative labeled) version of the “large margin”
example causes a convex potential function to incur a very large cost for this hypothesis
vector. Consequently a lower cost hypothesis can be obtained with a vector that points
rather far away from (1, 0). The “puller” example (whose y-coordinate is 5γ) outweights
the two “penalizer” examples (whose y-coordinates are −γ), so it “pulls” the minimum
cost hypothesis vector to point up into the first quadrant – in fact, so far up that thetwo “penalizer” examples are misclassified by the optimal hypothesis vector for the
potential function φ. See Figure 1.

4.3 Proof of Theorem 2 for the Bφideal booster
Let 1 < N < ∞ be such that η = N 1+1 , so 1 − η = NN+1 .

9We have that
Pφ,D (α1 , α2 ) =X

Dη,S (x, y)φ(y(α1 x1 + α2 x2 ))

(x,y)

=

1
4

X

[(1 − η)φ(α1 x1 + α2 x2 ) + ηφ(−α1 x1 − α2 x2 )] .

(x,y)∈S

It is clear that minimizing 4(N + 1)Pφ,D is the same as minimizing Pφ,D so we shallhenceforth work with 4(N + 1)Pφ,D since it gives rise to cleaner expressions. We havethat 4(N + 1)Pφ,D (α1 , α2 ) equalsX[N φ(α1 x1 + α2 x2 ) + φ(−α1 x1 − α2 x2 )](x,y)∈S= N φ(α1 ) + φ(−α1 )+2N φ(α1 γ − α2 γ) + 2φ(−α1 γ + α2 γ)+N φ(α1 γ + 5α2 γ) + φ(−α1 γ − 5α2 γ).

(5)

Let P1 (α1 , α2 ) and P2 (α1 , α2 ) be defined as follows:∂4(N + 1)Pφ,D (α1 , α2 ) and
∂α1
def ∂
P2 (α1 , α2 ) =4(N + 1)Pφ,D (α1 , α2 ).
∂α2def

P1 (α1 , α2 ) =Differentiating by α1 and α2 respectively, we have
P1 (α1 , α2 ) = N φ′ (α1 ) − φ′ (−α1 )+2γN φ′ (α1 γ − α2 γ) − 2γφ′ (−α1 γ + α2 γ)+N γφ′ (α1 γ + 5α2 γ) − γφ′ (−α1 γ − 5α2 γ)and
P2 (α1 , α2 ) = −2γN φ′ (α1 γ − α2 γ) + 2γφ′ (−α1 γ + α2 γ)+5γN φ′ (α1 γ + 5α2 γ) − 5γφ′ (−α1 γ − 5α2 γ).
Some expressions will be simplified if we reparameterize by setting α1 = α andα2 = Bα. It is helpful to think of B > 1 as being fixed (its value will be chosen later).
Now, let us write P1 (α) to denote P1 (α, Bα) and similarly write P2 (α) to denote
P2 (α, Bα), so that
P1 (α) = N φ′ (α) − φ′ (−α) + 2γN φ′ (−(B − 1)αγ)−2γφ′ ((B − 1)αγ) + N γφ′ ((5B + 1)αγ)−γφ′ (−(5B + 1)αγ)
andP2 (α) = −2γN φ′ (−(B − 1)αγ) + 2γφ′ ((B − 1)αγ)+5γN φ′ ((5B + 1)αγ) − 5γφ′ (−(5B + 1)αγ).

10We introduce the following function to help in the analysis of P1 (α) and P2 (α):
for α ∈ R,

def

Z(α) = N φ′ (α) − φ′ (−α).

Let us establish some basic properties of this function. Since φ is differentiable andconvex, we have that φ′ is a non-decreasing function. Since N > 1, this implies that
Z(·) is a non-decreasing function. We moreover have Z(0) = φ′ (0)(N − 1) < 0. The
definition of a convex potential function implies that as α → +∞ we have φ′ (α) → 0− ,and consequently we havelim Z(α) = 0 +α→+∞lim −φ′ (−α) > 0,α→+∞where the inequality holds since φ′ (α) is a nondecreasing function and φ′ (0) < 0. Sinceφ′ and hence Z is continuous, we have that over the interval [0, +∞) the function Z(α)
assumes every value in the range [φ′ (0)(N − 1), −φ′ (0)).
Next observe that we may rewrite P1 (α) and P2 (α) as
P1 (α) = Z(α) + 2γZ(−(B − 1)αγ) + γZ((5B + 1)γα)(6)P2 (α) = −2γZ(−(B − 1)αγ) + 5γZ((5B + 1)γα).

(7)

and
In the rest of this section we shall show that there are values α > 0, 0 < γ < 1/6,
B > 1 such that P1 (α) = P2 (α) = 0. Since Pφ,D is convex, this will imply thatdef

(α∗1 , α∗2 ) = (α, Bα) is a global minimum for the dataset constructed using this γ, as
required.
Let us begin with the following claim which will be useful in establishing P2 (α) = 0.
Proposition 1 For any B ≥ 1 there is a finite value ǫ(B) > 0 such that2Z(−(B − 1)ǫ(B)) = 5Z((5B + 1)ǫ(B)) < 0(8)

Proof Fix any value B ≥ 1. Recalling that Z(0) = φ′ (0)(N − 1) < 0, at ǫ = 0 thequantity 2Z(−(B − 1)ǫ) equals 2φ′ (0)(N − 1) < 0, and as ǫ increases this quantity
does not increase. On the other hand, at ǫ = 0 the quantity 5Z((5B + 1)ǫ) equals
5φ′ (0)(N − 1) < 2φ′ (0)(N − 1), and as ǫ increases this quantity increases to a limit, asǫ → +∞, which is at least 5(−φ′ (0)). Since Z is continuous, there must be some ǫ > 0
at which the two quantities are equal and are each at most 2φ′ (0)(N − 1) < 0.
⊔⊓
Observation 4 The function ǫ(B) is a continuous and nonincreasing function of B
for B ∈ [1, ∞).
Proof The larger B ≥ 1 is, the faster −(B − 1)ǫ decreases as a function of ǫ and thefaster (5B + 1)ǫ increases as a function of ǫ. Continuity of ǫ(·) follows from continuityof Z(·).
⊔⊓def

We now fix the value of B to be B = 1 + γ, where the parameter γ will be fixedlater. We shall only consider settings of α, γ > 0 such that αγ = ǫ(B) = ǫ(1 + γ); i.e.
ǫ(1+γ)
given a setting of γ, we shall take α =. For any such α, γ we haveγ
P2 (α) = (7) = γ[−2Z(−(B − 1)ǫ(1 + γ)) + 5Z((5B + 1)ǫ(1 + γ))] = 0

11LHS(γ)
RHS(γ)−φ′ (0)φ′ (0)(N − 1)

Fig. 2 The LHS of (9) (solid line) and RHS of (9) (dotted line), plotted as a function of γ.
As γ ranges through (0, ∞) the LHS decreases through all values between −φ′ (0) (a positive
value) and φ′ (0)(N − 1) (a negative value). The RHS is 0 at γ = 0 and is positive for all γ > 0.
Since both LHS and RHS are continuous, there must be some value of γ > 0 at which the LHS
and RHS are equal.

where the last equality is by Proposition 1. Now let us consider (6); our goal is to showthat for some γ > 0 it is also 0. For any (α, γ) pair with αγ = ǫ(1 + γ), we have by
Proposition 1 that2γZ(−(B − 1)γα) + γZ((5B + 1)γα)= 2γZ(−(B − 1)ǫ(1 + γ)) + γZ((5B + 1)ǫ(1 + γ))= 6γZ((5B + 1)ǫ(1 + γ))
where the second equality is by Proposition 1. Plugging this into (6), we have that forǫ(1+γ), the quantity P1 (α) equals 0 if and only if
α=
γ
Z

„

ǫ(1 + γ)γ«

= −6γZ((5B + 1)ǫ(1 + γ))= 6γ · (−Z((6 + 5γ) · ǫ(1 + γ))).

(9)Let us analyze (9). We first note that Observation 4 implies that ǫ(1 + γ) is aǫ(1+γ)
is a decreasing function
nonincreasing function of γ for γ ∈ [0, ∞). Consequently γ
of γ, and since Z is a nondecreasing function, the LHS is a nonincreasing function ofγ. Recall that at γ = 0 we have ǫ(1 + γ) = ǫ(1) which is some fixed finite positive value
by Proposition 1. So we have limγ→0+ LHS = limx→+∞ Z(x) ≥ −φ′ (0). On the otherextreme, since ǫ(·) is nonincreasing, we have„«ǫ(1)lim LHS ≤ lim Z= Z(0) = φ′ (0)(N − 1) < 0.
γ→+∞
γ→+∞
γ
So as γ varies through (0, ∞), the LHS decreases through all values between −φ′ (0)and 0.
On the other hand, at γ = 0 the RHS of (9) is clearly 0. Moreover the RHS isalways positive for γ > 0 by Proposition 1. Since the RHS is continuous (by continuityof Z(·) and ǫ(·)), this together with the previous paragraph implies that there must
be some γ > 0 for which the LHS and RHS of (9) are the same positive value. (SeeFigure 2.) So we have shown that there are values α > 0, γ > 0, B = 1 + γ such that
P1 (α) = P2 (α) = 0.

12

We close this section by showing that the value of γ > 0 obtained above is indeed
at most 1/6 (and hence every example in S lies in the unit disc as required). To see
this,“ note ”that we have shown that for this γ, we have Z((6 + 5γ)ǫ(1 + γ)) < 0 andZ

ǫ(1+γ)
γ> 0. Since Z is a nondecreasing function this implies 6 + 5γ < γ1 whichclearly implies γ < 1/6 as desired.
This concludes the proof of Theorem 2 for the Bφideal booster.

5 Early stopping
In this section, we show that early stopping cannot save a boosting algorithm: it ispossible that the global optimum analyzed in the preceding section can be reachedafter the first iteration.
Since Pφ,D (α1 , α2 ) depends only on the inner product between (α1 , α2 ) and the(normalized) example vectors (yx1 , yx2 ), it follows that rotating the set S around theorigin by any fixed angle induces a corresponding rotation of the function Pφ,D , andin particular of its minima. (Note that we have used here the fact that every example
point in S lies within the unit disc; this ensures that for any rotation of S each weak
hypothesis xi will always give outputs in [−1, 1] as required.) Consequently a suitablerotation of S to S ′ will result in the corresponding rotated function Pφ,D having a global
minimum at a vector which lies on one of the two coordinate axes (say a vector of theform (0, τ )). The weight vector (1, 0) achieved a margin γ for the original construction:
since rotating this weight vector can only increase its L1 norm, the rotated weightvector also achieves a margin γ.
earlyNow, all that remains is to show that Bφ,K
will choose the ultimately optimal
direction during the first round of boosting. For this to be the case after rotating,
all we need before rotating is that at the point (0, 0), the directional derivative ofPφ,D (α1 , α2 ) in any direction orthogonal to (α∗1 , α∗2 ) is not as steep as the directional
derivative toward (α∗1 , α∗2 ), which we will now prove.
In Section 4, we established that (α, Bα) = (α, (1 + γ)α) is a global minimum forthe data set as constructed there. The directional derivative at (0, 0) in the direction
P (0)+BP2 (0)of this optimum is 1 √.
2
1+B

Since φ′ (0) < 0, by (6) and (7) we haveP1 (0) = (1 + 3γ)φ′ (0)(N − 1) < 0
P2 (0) = 3γφ′ (0)(N − 1) < 0.
This implies that P1 (0) < P2 (0) < 0, which, since B > 1, implies BP1 (0) − P2 (0) < 0.
This means that (B, −1) rather than (−B, 1) is the direction orthogonal to the optimal(1, B) which has negative slope.
Recalling that B = 1 + γ, we have the following inequalities:(1 + 3γ) + 3γ
(1 + 3γ) − 3γ
−P1 (0) − P2 (0)B<−P1 (0) + P2 (0)B(−P1 (0) + P2 (0)) < −P1 (0) − P2 (0)B < 1 + 6γ =P1 (0) + BP2 (0) < BP1 (0) − P2 (0) < 0,

(10)
(11)
(12)

13

where (11) follows from (10) using P1 (0) < P2 (0) < 0. So the directional derivative inthe optimal direction (1, B) is steeper than in (B, −1)⊔⊓

6 L1 regularization
Our treatment of L1 regularization relies on the following intuition. One way to thinkof the beneficial effect of regularizing a convex potential booster is that regularization
controls the impact of the convexity – limiting the weights limits the size of the margins,
and thus the extremity of the losses on large-margin errors. But the trouble withregularization is that the convexity is sometimes needed to encourage the boostingalgorithm to classify examples correctly: if the potential function is effectively a linear
function of the margin, then the booster “cares” as much about enlarging the margins
of already correctly classified examples as it does about correcting examples that areclassified incorrectly.
In the absence of noise, our construction for regularized boosters concentrates theweight on two examples:– one positive example at (2γ, −γ) with weight 1 + ǫ (where ǫ > 0), and– one positive example at (−γ, 2γ) with weight 1.
As in Section 2.3, when there is noise, for N > 1, each clean example will haveweight N , and each noisy example weight 1. (Note once again that if N and ǫ are rational, these can be realized with a finite multiset of examples.) Thus, the L1 -regularized
convex potential boosting algorithm will solve the following optimization problem:
minα1 ,α2 Q(α1 , α2 ), s.t. |α1 | + |α2 | ≤ C,
where Q(α1 , α2 ) = (1 + ǫ)N φ(2α1 γ − α2 γ) + N φ(−α1 γ + 2α2 γ)+(1 + ǫ)φ(−2α1 γ + α2 γ) + φ(α1 γ − 2α2 γ).

(13)

Let us redefine P1 (α1 , α2 ) and P2 (α1 , α2 ) to be the partial derivatives with respect
to Q:∂Q(α1 , α2 )= 2γ(1 + ǫ)N φ′ (2α1 γ − α2 γ) − γN φ′ (−α1 γ + 2α2 γ)∂α1−2γ(1 + ǫ)φ′ (−2α1 γ + α2 γ) + γφ′ (α1 γ − 2α2 γ)∂Q(α1 , α2 )= −γ(1 + ǫ)N φ′ (2α1 γ − α2 γ) + 2γN φ′ (−α1 γ + 2α2 γ)
P2 (α1 , α2 ) =∂α2+γ(1 + ǫ)φ′ (−2α1 γ + α2 γ) − 2γφ′ (α1 γ − 2α2 γ).

P1 (α1 , α2 ) =The following key lemma characterizes the consequences of changing the weights
when γ is small enough.
Lemma 1 For all C > 0, N > 1, 1 > ǫ > 0, there is a γ > 0 such that, for all α1 , α2for which|α1 | + |α2 | ≤ C,
we have
P1 (α1 , α2 ) < P2 (α1 , α2 ) < 0.

14

Proof If |α1 | + |α2 | ≤ C, then |2α1 − α2 | ≤ 3C and |2α2 − α1 | ≤ 3C. Thus, by making
γ > 0 arbitrarily small, we can make |2α1 γ − α2 γ| and |2α2 γ − α1 γ| arbitrarily close
to 0. Since φ′ is continuous, this means that for any τ > 0, there is a γ > 0 such that,whenever |α1 | + |α2 | ≤ C, we have|φ′ (2α1 γ − α2 γ) − φ′ (0)| < τ|φ′ (2α2 γ − α1 γ) − φ′ (0)| < τ|φ′ (−2α1 γ + α2 γ) − φ′ (0)| < τ|φ′ (−2α2 γ + α1 γ) − φ′ (0)| < τ.
For such a γ, we have
P1 (α1 , α2 ) − P2 (α1 , α2 )= 3(1 + ǫ)N φ′ (2α1 γ − α2 γ) − 3N φ′ (−α1 γ + 2α2 γ)γ−3(1 + ǫ)φ′ (−2α1 γ + α2 γ) + 3φ′ (−2α2 γ + α1 γ)< 3((1 + ǫ)N + 1)(φ′ (0) + τ ) − 3(1 + ǫ + N )(φ′ (0) − τ )= 3ǫ(N − 1)φ′ (0) + 3(2(N + 1) + ǫ(N + 1))τ.
Since φ′ (0) < 0, ǫ > 0, and N > 1, for sufficiently small τ , we have
P1 (α1 , α2 ) − P2 (α1 , α2 )<0γand since γ > 0, this means
P1 (α1 , α2 ) < P2 (α1 , α2 ).
Furthermore
P2 (α1 , α2 ) < −γ(1 + ǫ)N (φ′ (0) − τ ) + 2γN (φ′ (0) + τ )+γ(1 + ǫ)(φ′ (0) + τ ) − 2γ(φ′ (0) − τ )= γ(1 − ǫ)(N − 1)φ′ (0) + γ(3 + ǫ)(N + 1)τ
so

P2 (α1 , α2 )< (1 − ǫ)(N − 1)φ′ (0) + (3 + ǫ)(N + 1)τ.
γ

Again, since φ′ (0) < 0, 1 > ǫ > 0, and N > 0, this means that when τ gets smallenoughP2 (α1 , α2 )<0γand thus P2 (α1 , α2 ) < 0.

⊔⊓Lemma 2 For all C > 0, N > 1, and 1 > ǫ > 0 there is a γ > 0 such that the output(α∗1 , α∗2 ) of the L1 -regularized potential booster for φ satisfies α∗1 > 0, α∗2 = 0.
Proof By Lemma 1, there is a γ > 0 such that whenever |α1 | + |α2 | ≤ C,
P1 (α1 , α2 ) < P2 (α1 , α2 ) < 0.
For such a γ, if either of the coordinates of the optimal solution were negative, we
could improve the solution while reducing the L1 norm of the solution by making the15negative component less so, a contradiction. Also, if α∗2 were strictly positive, then we
could improve the solution without affecting the L1 norm of the solution by transferring
a small amount of the weight from α∗2 to α∗1 , again, a contradiction.
⊔⊓
Looking at the proof of Lemma 1 it is easy to see that the lemma actually holds
for all sufficiently small γ > 0, and thus we may suppose that the instances (2γ, −γ)and (−γ, 2γ) lie in the unit square [−1, 1]2 . Lemma 2 thus implies Theorem 3 because
if α∗1 > 0 and α∗2 = 0, the positive example (−γ, 2γ) is classified incorrectly.

7 Consequences for Known Boosting Algorithms
A wide range of well-studied boosting algorithms are based on potential functions φthat satisfy our Definition 1. Theorem 1 thus implies that each of the corresponding
convex potential function boosters as defined in Section 2.2 cannot tolerate randomclassification noise at any noise rate 0 < η < 12 . (In some cases the original versionsof the algorithms discussed below are not exactly the same as the Bφ algorithm as
described in Section 2.2 because of small differences such as the way the step size
is chosen at each update. Thus we do not claim that Theorem 1 applies directly toeach of the original boosting algorithms; however we feel that our analysis strongly
suggests that the original boosters may, like the corresponding Bφ algorithms, be highly
susceptible to random classification noise.)
AdaBoost and MadaBoost. As discussed in the Introduction and in [7, 21] theAdaboost algorithm [12] is the algorithm Bφ obtained by taking the convex potentialfunction to be φ(x) = exp(−x). Similarly the MadaBoost algorithm [6] is based on thepotential function φ(x) defined in Equation (1). Each of these functions clearly satisfies
Definition 1.
LogitBoost and FilterBoost. As described in [7, 21, 2], the LogitBoost algorithmof [13] is based on the logistic potential function ln(1+exp(−x)), which is easily seen to
fit our Definition 1. Roughly, FilterBoost [2] combines a variation on the rejection sampling of MadaBoost with the reweighting scheme, and therefore the potential function,of LogitBoost.

8 Experiments with Binary-valued Weak Learners
The analysis of this paper leaves open the possibility that a convex potential booster
could still tolerate noise if the base classifiers were restricted to be binary-valued. In
this section we describe empirical evidence that this is not the case. We generated 100
datasets, applied three convex potential boosters to each, and calculated the training
error.
Data. Each dataset consisted of 4000 examples, divided into three groups, 1000
large margin examples, 1000 pullers, and 2000 penalizers. The large margin examples
corresponded to the example (1, 0) in Section 4.2, the pullers play the role of (γ, 5γ),
and the penalizers collectively play the role of (γ, −γ).
Each labeled example (x, y) in our dataset is generated as follows. First the label
y is chosen randomly from {−1, 1}. There are 21 features x1 , . . . , x21 that take valuesin {−1, 1}. Each large margin example sets x1 = · · · = x21 = y. Each puller assigns
x1 = · · · = x11 = y and x12 = · · · = x21 = −y. Each penalizer is chosen at random
in three stages: (1) the values of a random subset of five of the first eleven features16

x1 , . . . , x11 are set equal to y, (2) the values of a random subset of six of the last ten
features x12 , . . . , x21 are set equal to y, and (3) the remaining ten features are set to−y.
At this stage, if we associate a base classifier with each feature xi , then each of the4000 examples is classified correctly by a majority vote over these 21 base classifiers.
Intuitively, when an algorithm responds to the pressure exerted by the noisy large
margin examples and the pullers to move toward a hypothesis that is a majority voteover the first 11 features only, then it tends to incorrectly classify the penalizers, because
in the penalizers only 5 of those first 11 features agree with the class.
Finally, each class designation y is corrupted with classification noise with probability 0.1.
Boosters. We experimented with three boosters: AdaBoost, MadaBoost (whichis arguably, loosely speaking, the least convex of the convex potential boosters), andLogitBoost. Each booster was run for 100 rounds.
Results. The average training error of AdaBoost over the 100 datasets was 33%.
The average for LogitBoost was 30%, and for MadaBoost, 27%.

9 Discussion
We have shown that a range of different types of boosting algorithms that optimize aconvex potential function satisfying mild conditions cannot tolerate random classification noise. While our results imply strong limits on the noise-tolerance of algorithms
that fit this framework, they do not apply to other boosting algorithms such as Freund’s
Boost-By-Majority algorithm [9] and BrownBoost [10] for which the corresponding potential function is non-convex. An interesting direction for future work is to extend ournegative results to a broader class of potential functions.
The L1 regularized boosting algorithms considered here fix a bound on the normof the voting weights before seeing any data. This leaves open the possibility that analgorithm that adapts this bound to the data may still tolerate random misclassificationnoise. We suspect that this type of adaptiveness in fact cannot confer noise-tolerance;
it would be interesting to show this.
There are efficient boosting algorithms (which do not follow the potential function
approach) that can provably tolerate random classification noise [14, 15]. These noisetolerant boosters work by constructing a branching program over the weak classifiers;
the original algorithms of [14, 15] were presented only for binary-valued weak classifiers,
but recent work [16] extends the algorithm from [15] to work with confidence-rated
base classifiers. A standard analysis shows that this boosting algorithm for confidencerated base classifiers can tolerate random classification noise at any rate 0 < η < 1/2
according to our definition from Section 2.8. In particular, for any noise rate η bounded
below 1/4, if this booster is run on the data sets considered in this paper, it canlog 1/ǫ
construct a final classifier with accuracy 1 − η − ǫ > 3/4 after O( γ 2 ) stages ofboosting. Since our set of examples S is of size four, though, this means that the
booster’s final hypothesis will in fact have perfect accuracy on these data sets which
thwart convex potential boosters.
This work thus points out a natural attractive property that some branching program boosters have, but all convex potential boosters do not. It would be interesting
to further explore the relative capabilities of these classes of algorithms; some concretegoals along these lines include investigating under what conditions branching program

17

boosters can be shown to be consistent, and working toward a characterization of thesources for which one kind of method or another is to be preferred. The fact thatconvex potential boosters have been shown to be consistent when applied with weaklearners that use rich hypothesis spaces suggests that branching program boosters havethe most promise to improve accuracy for applications in which the number of featuresis large enough that, for example, boosting a decision tree learner is impractical. Also,
because branching program boosters divide data into disjoint bins during training, they
are likely to be best suited to applications in which training data is plentiful.
The parameter γ used in our constructions is associated with the quality of the weak
hypotheses available to the booster. The known noise-tolerant boosting algorithms
tolerate noise at rates that do not depend on γ, and the analysis of this paper showsthat potential boosters cannot achieve such a guarantee. The still leaves open thepossibility that noise at rates depending on γ may still be tolerated. In fact, “smooth”
boosting algorithms can tolerate even “malicious” noise at rates that depend on γ [24].
The construction using binary classifiers as weak learners that we used for theexperiments in Section 8 is patterned after the simpler construction using confidencerated weak learners that we analyzed theoretically. It may be possible to perform atheoretical analysis for a related problem with binary weak learners. The main outstanding task appears to be to get a handle on the unattractiveness of the penalizers tothe boosting algorithm (for example, to prove nearly matching upper and lower bounds
on their contribution to the total potential).

References
1. P. L. Bartlett and M. Traskin. Adaboost is consistent. Journal of Machine Learning
Research, 8:2347–2368, 2007.
2. J. Bradley and R. Schapire. Filterboost: Regression and classification on large datasets.
In Proceedings of the Twenty-First Annual Conference on Neural Information Processing
Systems (NIPS), 2007.
3. L. Breiman. Arcing the edge. Technical report 486, Department of Statistics, Universityof California, Berkeley, 1997.
4. L. Breiman. Some infinity theory for predictor ensembles. Annals of Statistics, 32(1):1–11,
2004.
5. T.G. Dietterich. An experimental comparison of three methods for constructing ensemblesof decision trees: bagging, boosting, and randomization. Machine Learning, 40(2):139–158,
2000.
6. C. Domingo and O. Watanabe. MadaBoost: a modified version of AdaBoost. In Proceedingsof the Thirteenth Annual Conference on Computational Learning Theory (COLT), pages
180–189, 2000.
7. N. Duffy and D. Helmbold. Potential boosters? In Advances in Neural Information
Processing Systems (NIPS), pages 258–264, 1999.
8. N. Duffy and D. Helmbold. A geometric approach to leveraging weak learners. TheoreticalComputer Science, 284:67–108, 2002.
9. Y. Freund. Boosting a weak learning algorithm by majority. Information and Computation, 121(2):256–285, 1995.
10. Y. Freund. An adaptive version of the boost-by-majority algorithm. Machine Learning,
43(3):293–318, 2001.
11. Y. Freund and R. Schapire. Experiments with a new boosting algorithm. In Proceedingsof the Thirteenth International Conference on Machine Learning, pages 148–156, 1996.
12. 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.
13. J. Friedman, T. Hastie, and R. Tibshirani. Additive logistic regression: a statistical viewof boosting. Annals of Statistics, 28(2):337–407, 1998.

18
14. A. Kalai and R. Servedio. Boosting in the presence of noise. Journal of Computer &System Sciences, 71(3):266–290, 2005.
15. P. Long and R. Servedio. Martingale boosting. In Proc. 18th Annual Conference on
Learning Theory (COLT), pages 79–94, 2005.
16. P. Long and R. Servedio. Adaptive martingale boosting. In Proc. 22nd Annual Conference
on Neural Information Processing Systems (NIPS), pages 977–984, 2008.
17. G. Lugosi and N. Vayatis. On the bayes-risk consistency of regularized boosting methods.
Annals of Statistics, 32(1):30–55, 2004.
18. R. Maclin and D. Opitz. An empirical evaluation of bagging and boosting. In Proceedingsof the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative
Applications of Artificial Intelligence Conference (AAAI/IAAI), pages 546–551, 1997.
19. S. Mannor, R. Meir, and T. Zhang. The consistency of greedy algorithms for classification.
Journal of Machine Learning Research, 4:713–741, 2003.
20. Dragos D. Margineantu and Thomas G. Dietterich. Pruning adaptive boosting. In Proc.
14th International Conference on Machine Learning, pages 211–218. Morgan Kaufmann,
1997.
21. L. Mason, J. Baxter, P. Bartlett, and M. Frean. Boosting algorithms as gradient descent.
In Advances in Neural Information Processing Systems (NIPS), pages 512–518, 1999.
22. G. R atsch, T. Onoda, and K.-R. M uller. Soft margins for AdaBoost. Machine Learning,
42(3):287–320, 2001.
23. R. Schapire and Y. Singer. Improved boosting algorithms using confidence-rated predictions. Machine Learning, 37:297–336, 1999.
24. R. Servedio. Smooth boosting and learning with malicious noise. Journal of Machine
Learning Research, 4:633–648, 2003.
25. T. Zhang. Statistical behavior and consistency of classification methods based on convex
risk minimization. Annals of Statistics, 32(1):56–85, 2004.
26. T. Zhang and B. Yu. Boosting with early stopping: Convergence and consistency. Annalsof Statistics, 33(4):1538–1579, 2005.
Acknowledgements We thank Shai Shalev-Shwartz, Yoram Singer, Nati Srebro and Liwei
Wang for stimulating conversations.