Learning large-margin halfspaces
with more malicious noise
Rocco A. Servedio
Columbia University
rocco@cs.columbia.edu

Philip M. Long
Googleplong@google.com

Abstract
We describe a simple algorithm that runs in time poly(n, 1/γ, 1/ε) and learns an
unknown n-dimensional γ-margin halfspace to accuracy 1 − ε in theppresence ofmalicious noise, when the noise rate is allowed to be as high as Θ(εγ log(1/γ)).
Previous efficient algorithms could only learn to accuracy ε in the presence ofmalicious noise of rate at most Θ(εγ).
Our algorithm does not work by optimizing a convex loss function. We show thatno algorithm for learning γ-margin halfspaces that minimizes a convex proxy for
misclassification error can tolerate malicious noise at a rate greater than Θ(εγ);
this may partially explain why previous algorithms could not achieve the higher
noise tolerance of our new algorithm.

1

Introduction

Learning an unknown halfspace from labeled examples that satisfy a margin constraint (meaning thatno example may lie too close to the separating hyperplane) is one of the oldest and most intensively
studied problems in machine learning, with research going back at least five decades to early seminal
work on the Perceptron algorithm [5, 26, 27].
In this paper we study the problem of learning an unknown γ-margin halfspace in the model ofProbably Approximately Correct (PAC) learning with malicious noise at rate η. More precisely, inthis learning scenario the target function is an unknown origin-centered halfspace f (x) = sign(w ·x) over the domain Rn (we may assume w.l.o.g. that w is a unit vector). There is an unknown
distribution D over the unit ball Bn = {x ∈ Rn : kxk2 ≤ 1} which is guaranteed to put zeroprobability mass on examples x that lie within Euclidean distance at most γ from the separating
hyperplane w · x = 0; in other words, every point x in the support of D satisfies |w · x| ≥ γ. The
learner has access to a noisy example oracle EX η (f, D) which works as follows: when invoked,
with probability 1 − η the oracle draws x from D and outputs the labeled example (x, f (x)) andwith probability η the oracle outputs a “noisy” labeled example which may be an arbitrary element(x0 , y) of Bn ×{−1, 1}. (It may be helpful to think of the noisy examples as being constructed by anomniscient and malevolent adversary who has full knowledge of the state of the learning algorithm
and previous draws from the oracle. In particular, note that noisy examples need not satisfy themargin constraint and can lie arbitrarily close to, or on, the hyperplane w · x = 0.) The goal of
the learner is to output a hypothesis h : Rn → {−1, 1} which has high accuracy with respect to
D: more precisely, with probability at least 1/2 (over the draws from D used to run the learner andany internal randomness of the learner) the hypothesis h must satisfy Prx∼D [h(x) 6= f (x)] ≤ ε.
(Because a success probability can be improved efficiently using standard repeat-and-test techniques[19], we follow the common practice of excluding this success probability from our analysis.) In
particular, we are interested in computationally efficient learning algorithms which have running
time poly(n, 1/γ, 1/ε).
1Introduced by Valiant in 1985 [30], the malicious noise model is a challenging one, as witnessed by
the fact that learning algorithms can typically only withstand relatively low levels of malicious noise.
Indeed, it is well known that for essentially all PAC learning problems it is information-theoreticallypossible to learn to accuracy 1 − ε only if the malicious noise rate η is at most ε/(1 + ε) [20],and most computationally efficient algorithms for learning even simple classes of functions can only
tolerate significantly lower malicious noise rates (see e.g. [1, 2, 8, 20, 24, 28]).
Interestingly, the original Perceptron algorithm [5, 26, 27] for learning a γ-margin halfspace can beshown to have relatively high tolerance to malicious noise. Several researchers [14, 17] have established upper bounds on the number of mistakes that the Perceptron algorithm will make when run ona sequence of examples that are linearly separable with a margin except for some limited number of“noisy” data points. Servedio [28] observed that combining these upper bounds with Theorem 6.2of Auer and Cesa-Bianchi [3] yields a straightforward “PAC version” of the online Perceptron algorithm that can learn γ-margin halfspaces to accuracy 1 − ε in the presence of malicious noiseprovided that the malicious noise rate η is at most some value Θ(εγ). Servedio [28] also describes
a different PAC learning algorithm which uses a “smooth” booster together with a simple geometricreal-valued weak learner and achieves essentially the same result: it also learns a γ-margin halfspace
to accuracy 1 − ε in the presence of malicious noise at rate at most Θ(εγ). Both the boosting-basedalgorithm of [28] and the Perceptron-based approach run in time poly(n, 1/γ, 1/ε).
Our results. We give a simple new algorithm for learning γ-margin halfspaces in the presence ofmalicious noise. Like the earlier approaches, our algorithm runs in time poly(n, 1/γ, 1/ε); however,it goes beyond the Θ(εγ) malicious noise tolerance of previous approaches. Our first main result is:
Theorem 1 There is a poly(n, 1/γ, 1/ε)-time algorithm that can learn an unknown
γ-margin halfp
space to accuracy 1 − ε in the presence of malicious noise at any rate η ≤ cεγ log(1/γ) wheneverγ < 1/7, where c > 0 is a universal constant.
p
While our Θ( log(1/γ)) improvement is not large, it is interesting to go beyond the “naturallooking” Θ(εγ) bound of Perceptron and other simple approaches. The algorithm of Theorem 1 is
not based on convex optimization, and this is not a coincidence: our second main result is, roughly
stated, the following.
Informal paraphrase of Theorem 2 Let A be any learning algorithm that chooses a hypothesis
vector v so as to minimize a convex proxy for the binary misclassification error. Then A cannot
learn γ-margin halfspaces to accuracy 1 − ε in the presence of malicious noise at rate η ≥ cεγ,
where c > 0 is a universal constant.
Our approach. The algorithm of Theorem 1 is a modification of a boosting-based approach tolearning halfspaces that is due to Balcan and Blum [7] (see also [6]). [7] considers a weak learner
which simply generates a random origin-centered halfspace sign(v · x) by taking v to be a uniform
random unit vector. The analysis of [7], which is for a noise-free setting, shows that such a random
halfspace has probability Ω(γ) of having accuracy at least 1/2 + Ω(γ) with respect to D. Given
this, any boosting algorithm can be used to get a PAC algorithm for learning γ-margin halfspaces toaccuracy 1 − ε.
Our algorithm is based on a modified weak learner which generates a collection of k = dlog(1/γ)e
independent random origin-centered halfspaces h1 = sign(v1 · x), . . . , hk = sign(vk · x) and takes
the majority vote H = Maj(h1 , . . . , hk ). The crux of our analysis is to show that if there is√no noise,then with probability at least (roughly) γ 2 the function H has accuracy at least 1/2 + Ω(γ k) withrespect to D (see Section 2, in particular Lemma 1). By using this weak learner in conjunction witha “smooth” boosting algorithm as in [28], we get the overall malicious-noise-tolerant PAC learningalgorithm of Theorem 1 (see Section 3).
For Theorem 2 we consider any algorithm that draws some number m of samples and minimizes
a convex proxy for misclassification error. If m is too small then well-known sample complexity
bounds imply that the algorithm cannot learn γ-margin halfspaces to high accuracy, so we may
assume that m is large; but together with the assumption that the noise rate is high, this meansthat with overwhelmingly high probability the sample will contain many noisy examples. The heartof our analysis deals with this situation; we describe a simple γ-margin data source and adversary
2strategy which ensures that the convex proxy for misclassification error will achieve its minimum
on a hypothesis vector that has accuracy less than 1 − ε with respect to the underlying noiseless
distribution of examples. We also establish the same fact about algorithms that use a regularizer
from a class that includes the most popular regularizers based on p-norms.
Related work. As mentioned above, Servedio [28] gave a boosting-based algorithm that learns
γ-margin halfspaces with malicious noise at rates up to η = Θ(εγ). Khardon and Wachman [21]empirically studied the noise tolerance of variants of the Perceptron algorithm. Klivans et al. [22]showed that an algorithm that combines PCA-like techniques with smooth boosting can tolerate relatively high levels of malicious noise provided that the distribution D is sufficiently “nice” (uniform
over the unit sphere or isotropic log-concave). We note that γ-margin distributions are significantly
less restrictive and can be very far from having the “nice” properties required by [22].
We previously [23] showed that any boosting algorithm that works by stagewise minimization of aconvex “potential function” cannot tolerate random classification noise – this is a type of “benign”
rather than malicious noise, which independently flips the label of each example with probability η.
A natural question is whether Theorem 2 follows from [23] by having the malicious noise simply
simulate random classification noise; the answer is no, essentially because the ordering of quantifiers
is reversed in the two results. The construction and analysis from [23] crucially relies on the factthat in the setting of that paper, first the random misclassification noise rate η is chosen to take someparticular value in (0, 1/2), and then the margin parameter γ is selected in a way that depends on
η. In contrast, in this paper the situation is reversed: in our setting first the margin parameter γ isselected, and then given this value we study how high a malicious noise rate η can be tolerated.

2

The basic weak learner for Theorem 1

Let f (x) = sign(w · x) be an unknown halfspace and D be an unknown distribution over the ndimensional unit ball that has a γ margin with respect to f as described in Section 1. For odd k ≥ 1
we let Ak denote the algorithm that works as follows: Ak generates k independent uniform random
unit vectors v1 , . . . , vk in Rn and outputs the hypothesis H(x) = Maj(sign(v1 · x), . . . , sign(vk ·x)). Note that Ak does not use any examples (and thus malicious noise does not affect its execution).
As the main result of Section 2 we show that if k is not too large then algorithm Ak has a nonnegligible chance of outputting a reasonably good weak hypothesis:√
1
Lemma 1 For odd k ≤ 16γ
k/2k )
2 the hypothesis H generated by Ak has probability at least Ω(γ√γ kof satisfying Prx∼D [H(x) 6= f (x)] ≤ 12 − 100π.

2.1

A useful tail bound

Theh following notation
will be useful in analyzing algorithm Ak : Letvote(γ, k) :=i
PkPr
i=1 Xi < k/2 where X1 , . . . , Xk are i.i.d. Bernoulli (0/1) random variables with E[Xi ] =1/2 + γ for all i. Clearly vote(γ, k) is the lower tail of a Binomial distribution, but for our purposes we need an upper bound on vote(γ, k) when k is very small relative to 1/γ 2 and the valueof vote(γ, k) is close to but – crucially – less than 1/2. Standard Chernoff-type bounds [10] do notseem to be useful here, so we give a simple self-contained proof of the bound we need (no attempt
has been made to optimize constant factors below).
√

γ k
1
Lemma 2 For 0 < γ < 1/2 and odd k ≤ 16γ
2 we have vote(γ, k) ≤ 1/2 − 50 .

Proof: The lemma is easily
1, 3, 5, 7 so we assume k ≥ 9 below. The
 for k =k−i
P verifiedkvalue vote(γ, k) equals
(1/2
−
γ)
(1/2 + γ)i , which is easily seen to equali<k/2 i


P
P
k
1
2 i
k−2i
. Since k is odd 21k i<k/2 ki equals 1/2, so it rei<k/2 i (1 − 4γ ) (1 − 2γ)
2k
√


P
mains to show that 21k i<k/2 ki 1 − (1 − 4γ 2 )i (1 − 2γ)k−2i ≥ γ50k . Consider any integer3i ∈ [0, k/2 −√k]. For such an i we havek−2i

(1 − 2γ)≤ (1 − 2γ)

√
2 k

 √ 
√
2 2 k
1 − (2γ)(2 k) + (2γ)
2√√√
1 − 4γ k + 8γ k(γ k)√√√
1 − 4γ k + 2γ k = 1 − 2γ k

≤
≤
≤

(1)
(2)
(3)
√
2 k

where (1) is obtained by truncating the alternatingbinomial series expansionof (1 − 2γ)
after
√

a positive term, (2) uses the upper bound 2` ≤ `2 /2, and (3) uses γ k ≤ 1/4 which follows
√
1
2 i
k−2i
from the bound k ≤ 16γ≤ 1 − 2γ k and thus we have
2 . So we have (1 − 4γ ) (1 − 2γ)√P
1 − (1 − 4γ 2 )i (1 − 2γ)k−2i ≥ 2γ k. The sum i≤k/2−√k ki is at least 0.01 · 2k for all odd k ≥ 9[13], so we obtain the claimed bound:√ 
X k  √
1 X k 
1
γ k
2 i
k−2i
1 − (1 − 4γ ) (1 − 2γ)≥ k
2γ k ≥
.
i
i
2k
2
50
√
i<k/2

2.2

i<k/2− kProof of Lemma 1

Throughout the following discussion it will be convenient to view angles between vectors as lying
the range [−π, π), so acute angles are in the range (−π/2, π/2).
Recall that sign(w·x) is the unknown target halfspace (we assume w is a unit vector) and v1 , . . . , vk
are the random unit vectors generated by algorithm Ak . For j ∈ {1, . . . , k} let Gj denote the“good” event that the angle between vj and w is acute, i.e. lies in the interval (−π/2, π/2), and
let G denote the event G1 ∧ · · · ∧ Gk . Since the vectors vi are selected independently we have
Qk
Pr[G] = j=1 Pr[Gj ] = 2−k .
The following claim shows that conditioned on G, any γ-margin point has a noticeably-better-than1
2 chance of being classified correctly by H (note that the probability below is over the random
generation of H by Ak ):Claim 3 Fix x ∈ Bn to be
any point such that |w ·x| ≥ γ. Then we have PrH [H(x) 6= f (x) | G] ≤√vote(γ/π, k) ≤ 1/2 − γ50πk .
Proof: Without loss of generality we assume that x is a positive example (an entirely similar analysis
goes through for negative examples), so w · x ≥ γ. Let α denote the angle from w to x in the plane
spanned by w and x; again without loss of generality we may assume that α lies in [0, π/2] (thecase of negative angles is symmetric). In fact since x is a positive example with margin γ, we havethat 0 ≤ α ≤ π/2 − γ.
Fix any j ∈ {1, . . . , k} and let us consider the random unit vector vj . Let vj0 be the projection of
vj onto the plane spanned by x and w. The distribution of vj0 /||vj0 || is uniform on the unit circle
in that plane. We have that sign(vj · x) 6= f (x) if and only if the magnitude of the angle between
vj0 and x is at least π/2. Conditioned on Gj , the angle from v0 to w is uniformly distributed overthe interval (−π/2, π/2). Since the angle from w to x is α, the angle from v0 to x is the sum of
the angle from v0 to w and the angle from w to x, and therefore it is uniformly distributed over theinterval (−π/2 + α, π/2 + α) . Recalling that α ≥ 0, we have that sign(vj · x) 6= f (x) if and only
if angle from v0 to x lies in (π/2, π/2 + α). Since the margin condition implies α ≤ π/2 − γ as
noted above, we have Pr[sign(vj · x) 6= f (x) | Gj ] ≤ π/2−γ= 12 − πγ .
πNow recall that v1 , ..., vk are chosen independently at random, and G = G1 ∧ · · · ∧ Gk . Thus, after
conditioning on G, we have that v1 , ..., vk are still independent and the events sign(v1 · x) 6=
f (x), . . . , sign(vk · x)√ 6= f (x) are independent. It follows that PrH [H(x) 6= f (x) | G] ≤vote πγ , k ≤ 1/2 − γ50πk , where we used Lemma 2 for the final inequality.
Now all the ingredients are in place for us to prove Lemma 1. Since Claim√ 3 may be applied toevery x in the support of D, we have Prx∼D,H [H(x) 6= f (x) | G] ≤ 1/2 − γ50πk . Applying Fubini’s
4√

theorem we get that EH [Prx∼D [H(x) 6= f (x)] | G] ≤ 1/2 − γ50πk . Applying Markov’s inequality
to the nonnegative random variable Prx∼D [H(x) 6= f (x)], we get√√"#
1 − γ50πk2(1/2 − γ50πk )√Pr Pr [H(x) 6= f (x)] >
,
| G ≤
H x∼D
2
1− γ k50πwhich implies√#√
1 − γ50πk
Pr Pr [H(x) 6= f (x)] ≤| G ≥ Ω(γ k).
H x∼D
2

"

Since PrH [G] = 2−k we get"√

1 − γ50πk
Pr Pr [H(x) 6= f (x)] ≤
H x∼D
2

#

√
≥ Ω(γ k/2k ),and Lemma 1 is proved.

3

Proof of Theorem 1: smooth boosting the weak learner to toleratemalicious noise

Our overall algorithm for learning γ-margin halfspaces with malicious noise, which we call Algorithm B, combines a weak learner derived from Section 2 with a “smooth” boosting algorithm.
Recall that boosting algorithms [15, 25] work by repeatedly running a weak learner on a sequence of carefully crafted distributions over labeled examples. Given the initial distribution P
over labeled examples (x, y), a distribution Pi over labeled examples is said to be κ-smooth if
Pi [(x, y)] ≤ κ1 P [(x, y)] for every (x, y) in the support of P. Several boosting algorithms are known[9, 16, 28] that generate only 1/ε-smooth distributions when boosting to final accuracy 1 − ε. For
concreteness we will use the MadaBoost algorithm of [9], which generates a (1 − ε)-accurate final
hypothesis after O( εγ12 ) stages of calling the weak learner and runs in time poly( 1ε , γ1 ).
At a high level our analysis here is related to previous works [28, 22] that used smooth boosting totolerate malicious noise. The basic idea is that since a smooth booster does not increase the weightof any example by more than a 1/ε factor, it cannot “amplify” the malicious noise rate by morethan this factor. In [28] the weak learner only achieved advantage O(γ) so as long as the malicious
noise rate was initially O(εγ), the “amplified” malicious noise rate of O(γ) could not completely“overcome” the advantage and boosting could proceed successfully. Here we have a weak learnerthat achieves a higher advantage, so boosting can proceed successfully in the presence of more
malicious noise. The rest of this section provides details.
The weak learner W that B uses is a slight extension of algorithm Ak from Section 2 with k =dlog(1/γ)e. When invoked with distribution Pt over labeled examples, algorithm W• makes ` (specified later) calls to algorithm Adlog(1/γ)e , generating candidate hypotheses
H1 , ..., H` ; and• evaluates H1 , ..., H` using M (specified later) independent examples drawn from Pt andoutputs the Hj that makes the fewest errors on these examples.
The overall algorithm B• draws a multiset S of m examples (we will argue later that poly(n, 1/γ, 1/ε) many examples suffice) from EXη (f, D);• sets the initial distribution P over labeled examples to be uniform over S; and• uses MadaBoost to boost to accuracy 1 − /4 with respect to P , using W as a weak learner.
p
Recall that we are assuming η ≤ cεγ log(1/γ); we will show that under this assumption, algorithm
B outputs a final hypothesis h that satisfies Prx∼D [h(x) = f (x)] ≥ 1 − ε with probability at least
1/2.
5

First, let SN ⊆ S denote the noisy examples in S. A standard Chernoff bound [10] implies thatwith probability at least 5/6 we have |SN |/|S| ≤ 2η; we henceforth write η 0 to denote |SN |/|S|.
We will show below that with high probability, every time MadaBoost calls the weak learner W
with a distribution Pt , W generates a weak hypothesis (call it ht ) that has Pr(x,y)∼Pt [ht (x) = y] ≥p
1/2 + Θ(γ log(1/γ)). MadaBoost’s boosting guarantee then implies that the final hypothesis (callit h) of Algorithm B satisfies Pr(x,y)∼P [h(x) = y] ≥ 1 − ε/4. Since h is correct on (1 − ε/4) of thepoints in the sample S and η 0 ≤ 2η, h must be correct on at least 1 − ε/4 − 2η of the points in S \SN , which is a noise-free sample of poly(n, 1/γ, 1/ε) labeled examples generated according to D.
Since h belongs to a class of hypotheses with VC dimension at most poly(n, 1/γ, 1/) (because theanalysis of MadaBoost implies that h is a weighted vote over O(1/(εγ 2 )) many weak hypotheses,
and each weak hypothesis is a vote over O(log(1/γ)) n-dimensional halfspaces), by standard sample
complexity bounds [4, 31, 29], with probability 5/6, the accuracy of h with respect to D is at least1 − ε/2 − 4η > 1 − ε, as desired.
Thus it remains to show that with high probability each time W
p is called on a distribution Pt , itindeed generates a weak hypothesis with advantage at least Ω(γ log(1/γ)). Recall the following:
Definition 1 The total variation distance between distributions P and Q over finite domain X isdT V (P, Q) := maxE⊆X P [E] − Q[E].
Suppose R is the uniform distribution over the noisy points SN ⊆ S, and P 0 is the uniform distribution over the remaining points S \ SN (we may view P 0 as the “clean” version of P ). Thenthe distribution P may be written as P = (1 − η 0 )P 0 + η 0 R, and for any event E we have
P [E] − P 0 [E] ≤ η 0 R[E] ≤ η 0 , so dT V (P, P 0 ) ≤ η 0 .
Let Pt denote the distribution generated by MadaBoost during boosting stage t. The smoothness of
MadaBoost implies that Pt [SN ] ≤ 4η 0 /, so the noisy examples have total probability at most 4η 0 /εunder Pt . Arguing as for the original distribution, we have that the clean version Pt0 of Pt satisfies
dT V (Pt0 , Pt ) ≤ 4η 0 /.
By Lemma 1, each call to algorithm Adlog(1/γ)e yields a hypothesis (call it g) that satisfiespPr[errorPt0 (g) ≤ 1/2 − γ log(1/γ)/(100π)] ≥ Ω(γ 2 ),
g

(4)

(5)

def

where for any distribution Q we define errorQ (g) = Pr(x,y)∼Q [g(x) 6= y]. Recalling that η 0 ≤ 2ηpand η < cεγ log(1/γ), for a suitably small absolute constant c > 0 we have thatp4η 0 /ε < γ log(1/γ)/(400π).
(6)pThen (4) and (5) imply that Prg [errorPt (g) ≤ 1/2 − 3γ log(1/γ)/(400π)] ≥ Ω(γ 2 ). This meansthat by taking the parameters ` and M of the weak learner W to be poly(1/γ, log(1/ε)), we can ensure that with overall probability at least 2/3, at each stage t of boosting the weakp hypothesis ht that
W selects from its ` calls to A in that stage will satisfy errorPt (gt ) ≤ 1/2 − γ log(1/γ)/(200π).
This concludes the proof of Theorem 1.

4

Convex optimization algorithms have limited malicious noise tolerance

Given a sample S = {(x1 , y1 ), . . . , (xm , ym )} of labeled examples, the number of examples misclassified by the hypothesis sign(v · x) is a nonconvex function of v, and thus it can be difficult tofind a v that minimizes this error (see [12, 18] for theoretical results that support this intuition invarious settings). In an effort to bring the powerful tools of convex optimization to bear on various
halfspace learning problems, a widely used approach is to instead minimize some convex proxy for
misclassification error.
Definition 2 will define the class of such algorithms analyzed in this section. This definition allows
algorithms to use regularization, but by setting the regularizer ψ to be the all-0 function it also covers
algorithms that do not.
6

Definition 2 A function φ : R → R+ is a convex misclassification proxy if φ is convex, nonincreasing, differentiable,
satisfies φ0 (0) < 0. A function ψ : Rn → [0, ∞) is a componentwisePandnregularizer if ψ(v) = i=1 τ (vi ) for a convex, differentiable τ : R → [0, ∞) for which τ (0) = 0.
Given a sample of labeled examples S = {(x1P, y1 ), . . . , (xm , ym )} ∈ (Rn × {−1, 1})m , the (φ,ψ)mloss of vector v on S is Lφ,ψ,S (v) := ψ(v) + i=1 φ(y(v · xi )). A (φ,ψ)-minimizer is any learningalgorithm that minimizes Lφ,ψ,S (v) whenever the minimum exists.

Our main negative result, shows that for any sample size, algorithms that minimize a regularized
convex proxy for misclassification error will succeed with exponentially small probability for amalicious noise rate that is Θ(εγ), and therefore for any larger malicious noise rate.

Theorem 2 Fix φ to be any convex misclassification proxy and ψ to be any componentwise regularizer, and let algorithm A be a (φ,ψ)-minimizer. Fix ε ∈ (0, 1/8] to be any error parameter,γ ∈ (0, 1/8] to be any margin parameter, and m ≥ 1 to be any sample size. Let the malicious noise
rate η be 16εγ.
Then there is an n, a target halfspace f (x) = sign(w · x) over Rn , a γ-margin distribution D for fw(supported on points x ∈ Bn that have | kwk· x| ≥ γ), and a malicious adversary with the following
property: If Aφ is given m random examples drawn from EXη (f, D) and outputs a vector v, thenthe probability (over the draws from EXη (f, D)) that v satisfies Prx∼D [sign(v · x) 6= f (x)] ≤ ε isat most e−c/γ , where c > 0 is some universal constant.

Proof: The analysis has two cases based on whether or not the number of examples m exceeds
1
m0 := 32γ
2 . (We emphasize that Case 2, in which n is taken to be just 2, is the case that is ofprimary interest, since in Case 1 the algorithm does not have enough examples to reliably learn aγ-margin halfspace even in a noiseless scenario.)
Case 1 (m ≤ m0 ): Let n = b1/γ 2 c and let e(i) ∈ Rn denote the unit vector with a 1 in the ith
component. Then the set of examples E := {e(1) , ..., e(n) } is shattered by the family F which consists of all 2n halfspaces whose weight vectors are in {−γ, γ}n , and any distribution whose support
is E is a γ-margin distribution for any such halfspace. The proof of the well-known informationtheoretic lower bound of [11]1 gives that for any learning algorithm that uses m examples (such as
A), there is a distribution D supported on E and ahalfspacef ∈ F such that the output h of Acsatisfies Pr[Prx∼D [h(x) 6= f (x)] > ] ≥ 1 − exp − γ 2 , where the outer probability is over the
random examples drawn by A. This proves the theorem in Case 1.
Case 2 (m > m0 ): We note that it is well known (see e.g. [31]) that O( εγ12 ) examples suffice tolearn γ-margin n-dimensional halfspaces for any n if there is no noise, so noisy examples will play
an important role in the construction in this case.
p
We take n = 2. The target halfspace is f (x) = sign( 1 − γ 2 x1 + γx2 ). The
 distribution
 D is very
simple and is supported on only two points: it puts weight 2 on the point √ γ 2 , 0 which is a1−γ

positive example for f , and weight 1 − 2 on the point (0, 1) which is also a positive example forf. When the malicious adversary is allowed to corrupt an example, with probability 1/2 it provides
the point (1, 0) and mislabels it as negative, and with probability 1/2 it provides the point (0, 1) andmislabels it as negative.
Let S = ((x˛1n, y1 ), “..., √(xm , ym”o˛)) be a sample of m examples drawn from EXη (f, D). We define pS,1 :=1˛
˛ t:xt = γ/|S|

1−γ 2 ,0˛
˛=(1,0)}|, pS,2 := |{t:xt =(0,1),y=1}|, ηS,1 := |{t:xt|S|, and ηS,2 :=|S|

In particular, see the last displayed equation in the proof of Lemma 3 of [11].

7|{t:xt =(0,1),y=−1}|. Using standard Chernoff bounds (see e.g. [10]) and a union bound we get|S|

Pr[pS,1 = 0 or pS,2 = 0 or pS,1 > 3 or ηS,1 < η/4 or ηS,2 < η/4] ηm  m 
+ 2 exp −≤ (1 − 2ε(1 − η))m + (1 − (1 − 2ε)(1 − η))m + exp −1224
 ηm  m 
+ 2 exp −(since  ≤ 1/4 and η ≤ 1/2)
≤ 2(1 − ε)m + exp −
12
24 




1
1
1
≤ 2 exp −+ exp −
+ 2 exp −
.
32γ 2
96γ 2
48γ
Since the theorem allows for a e−c/γ success probability for A, it suffices to consider the case inwhich pS,1 and pS,2 are both positive, pS,1 ≤ 3, and min{ηS,1 , ηS,2 } ≥ η/4. For v = (v1 , v2 ) ∈R2 the value Lφ,ψ,S (v) is proportional to
!
γv1
ψ(v)
L(v1 , v2 ) := pS,1 φ p+ pS,2 φ(v2 ) + ηS,1 φ(−v1 ) + ηS,2 φ(−v2 ) +
.
2
|S|
1−γ
From the bounds stated above on pS,1 , pS,2 , ηS,1 and ηS,2 we may conclude that Lφ,ψ,S (v) does
achieve a minimum value. This is because for any z ∈ R the set {v : Lφ,ψ,S (v) ≤ z} is bounded,and therefore so is its closure. Since Lφ,ψ,S (v) is bounded below by zero and is continuous, this
implies that it has a minimum. To see that for any z ∈ R the set {v : Lφ,ψ,S (v) ≤ z} is bounded,
observe that if either v1 or v2 is fixed and the other one is allowed to take on arbitrarily large
magnitude values (either positive or negative), this causes Lφ,ψ,S (v) to take on arbitrarily large
positive values (this is an easy consequence of the definition of L, the fact that φ is convex, nonnegative and nonincreasing, φ0 (0) < 0, and the fact that pS,1 , pS,2 , ηS,1 , ηS,2 are all positive).
Taking the derivative with respect to v1 yields∂Lγ= pS,1 p
φ0∂v1
1 − γ2
When v1 = 0, the derivative (7) is pS,1 √ γ

γv1
p

1−γ 2

1 − γ2!
− ηS,1 φ0 (−v1 ) −τ 0 (v1 )
.
|S|

(7)

φ0 (0) − ηS,1 φ0 (0) (recall that τ is minimized at 0 andthus τ 0 (0) = 0). Recall that φ0 (0) < 0 by assumption. If pS,1 √ γ

1−γ 2< ηS,1 then (7) is positive at

0, which means that L(v1 , v2 ) is an increasing function of v1 at v1 = 0 for all v2 . Since L is convex,
this means that for each v2 ∈ R we have that the value v1? that minimizes L(v1? , v2 ) is a negativevalue v1? < 0. So, if pS,1 √ γ 2 < ηS,1 , the linear classifier v output by Aφ has v1 ≤ 0; hence it
1−γ

misclassifies the point ( √ γ1−γ 2, 0), and thus has error rate at least 2 with respect to D.

Combining the fact that γ ≤ 1/8 with the facts that pS,1 ≤ 3 and ηS,1 > η/4, we get pS,1 √ γ

1−γ 2

<

1.01 × pS,1 γ < 4γ = η/4 < ηS,1 which completes the proof.

5

Conclusion

It would be interesting to further improve on the malicious noise tolerance of efficient algorithms
for PAC learning γ-margin halfspaces, or to establish computational hardness results for this problem. Another goal for future work is to develop an algorithm that matches the noise tolerance ofTheorem 1 but uses a single halfspace as its hypothesis representation.

References[1] J. Aslam and S. Decatur. Specification and simulation of statistical query algorithms for efficiency andnoise tolerance. Journal of Computer and System Sciences, 56:191–208, 1998.
[2] P. Auer. Learning nested differences in the presence of malicious noise. Theor. Comp. Sci., 185(1):159–
175, 1997.
[3] P. Auer and N. Cesa-Bianchi. On-line learning with malicious noise and the closure algorithm. Annals of
Mathematics and Artificial Intelligence, 23:83–99, 1998.

8

[4] E. B. Baum and D. Haussler. What size net gives valid generalization? Neural Comput., 1:151–160,
1989.
[5] H. Block. The Perceptron: a model for brain functioning. Reviews of Modern Physics, 34:123–135, 1962.
[6] A. Blum. Random Projection, Margins, Kernels, and Feature-Selection. In LNCS Volume 3940, pages
52–68, 2006.
[7] A. Blum and M.-F. Balcan. A discriminative model for semi-supervised learning. Journal of the ACM,
57(3), 2010.
[8] S. Decatur. Statistical queries and faulty PAC oracles. In Proc. 6th COLT, pages 262–268, 1993.
[9] C. Domingo and O. Watanabe. MadaBoost: a modified version of AdaBoost. In Proc. 13th COLT, pages
180–189, 2000.
[10] D. Dubhashi and A. Panconesi. Concentration of measure for the analysis of randomized algorithms.
Cambridge University Press, Cambridge, 2009.
[11] A. Ehrenfeucht, D. Haussler, M. Kearns, and L. Valiant. A general lower bound on the number of examples needed for learning. Information and Computation, 82(3):247–251, 1989.
[12] V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami. On agnostic learning of parities, monomials, andhalfspaces. SIAM J. Comput., 39(2):606–645, 2009.
[13] W. Feller. Generalization of a probability limit theorem of Cramér. Trans. Am. Math. Soc., 54:361–372,
1943.
[14] Y. Freund and R. Schapire. Large margin classification using the Perceptron algorithm. In Proc. 11th
COLT, pages 209–217., 1998.
[15] Y. Freund and R. Schapire. A short introduction to boosting. J. Japan. Soc. Artif. Intel., 14(5):771–780,
1999.
[16] D. Gavinsky. Optimally-smooth adaptive boosting and application to agnostic learning. JMLR, 4:101–
117, 2003.
[17] C. Gentile and N. Littlestone. The robustness of the p-norm algorithms. In Proc. 12th COLT, pages 1–11,
1999.
[18] V. Guruswami and P. Raghavendra. Hardness of learning halfspaces with noise. SIAM J. Comput.,39(2):742–765, 2009.
[19] D. Haussler, M. Kearns, N. Littlestone, and M. Warmuth. Equivalence of models for polynomial learnability. Information and Computation, 95(2):129–161, 1991.
[20] M. Kearns and M. Li. Learning in the presence of malicious errors. SIAM Journal on Computing,22(4):807–837, 1993.
[21] R. Khardon and G. Wachman. Noise tolerant variants of the perceptron algorithm. JMLR, 8:227–248,
2007.
[22] A. Klivans, P. Long, and R. Servedio. Learning Halfspaces with Malicious Noise. JMLR, 10:2715–2740,
2009.
[23] P. Long and R. Servedio. Random classification noise defeats all convex potential boosters. Machine
Learning, 78(3):287–304, 2010.
[24] Y. Mansour and M. Parnas. Learning conjunctions with noise under product distributions. Information
Processing Letters, 68(4):189–196, 1998.
[25] R. Meir and G. Rätsch. An introduction to boosting and leveraging. In LNAI Advanced Lectures on
Machine Learning, pages 118–183, 2003.
[26] A. Novikoff. On convergence proofs on perceptrons. In Proceedings of the Symposium on Mathematical
Theory of Automata, volume XII, pages 615–622, 1962.
[27] F. Rosenblatt. The Perceptron: a probabilistic model for information storage and organization in the brain.
Psychological Review, 65:386–407, 1958.
[28] R. Servedio. Smooth boosting and learning with malicious noise. JMLR, 4:633–648, 2003.
[29] J. Shawe-Taylor, P. Bartlett, R. Williamson, and M. Anthony. Structural risk minimization over datadependent hierarchies. IEEE Transactions on Information Theory, 44(5):1926–1940, 1998.
[30] L. Valiant. Learning disjunctions of conjunctions. In Proc. 9th IJCAI, pages 560–566, 1985.
[31] V. Vapnik. Statistical Learning Theory. Wiley-Interscience, New York, 1998.

9