A
The Power of Localization
for Efficiently Learning Linear Separators with Noise
Pranjal Awasthi, Rutgers University
Maria Florina Balcan, Carnegie Mellon University
Philip M. Long, Sentient Technologies

We introduce a new approach for designing computationally efficient learning algorithms that are tolerant to noise, anddemonstrate its effectiveness by designing algorithms with improved noise tolerance guarantees for learning linear separators.
We consider both the malicious noise model of Valiant [Valiant 1985; Kearns and Li 1988] and the adversarial label noisemodel of Kearns, Schapire, and Sellie [1994]. For malicious noise, where the adversary can corrupt both the label and thefeatures, we provide a polynomial-time algorithm for learning linear separators in <d under isotropic log-concave
 distribu
3
tions that can tolerate a nearly information-theoretically optimal noise rate of η = Ω(), improving on the Ω log2(d/)noise-toleranceof [Klivans et al. 2009a]. In the case that thedistribution
 is uniform over the unit ball, this improves on the2
of [Klivans et al. 2009a]. For the adversarial label
noise-tolerance of [Kalai et al. 2005] and the Ω log(d/)Ω 1/4
dnoise model, where the distribution over the feature vectors is unchanged, and the overall probability of a noisy label isconstrained to be at most η, we also give a polynomial-time algorithm for learning linear separators in <d under isotropic
log-concave distributions that can handle a noise rate of η = Ω (). In the case of the uniform distribution, this improves
over the results of [Kalai et al. 2005] which either required runtime super-exponential in 1/ (ours is polynomial in 1/) or
tolerated less noise.1
Our algorithms are also efficient in the active learning setting, where learning algorithms only receive the classificationsof examples when they ask for them. We show that, in this model, our algorithms achieve a label complexity whose dependence on the error parameter  is polylogarithmic (and thus exponentially better than that of any passive algorithm). This
provides the first polynomial-time active learning algorithm for learning linear separators in the presence of malicious noiseor adversarial label noise.
Our algorithms and analysis combine several ingredients including aggressive localization, minimization of a progressively rescaled hinge loss, and a novel localized and soft outlier removal procedure. We use localization techniques (previously used for obtaining better sample complexity results) in order to obtain better noise-tolerant polynomial-time algorithms.
Categories and Subject Descriptors: F.2 [Theory of Computation]: Analysis of Algorithms and Problem Complexity
General Terms: Algorithms,Theory
ACM Reference Format:
Pranjal Awasthi, Maria Florina Balcan and Philip M. Long, 2016. The Power of Localization for Efficiently Learning Linear
Separators with Noise. J. ACM V, N, Article A (January YYYY), 26 pages.
DOI:http://dx.doi.org/10.1145/0000000.0000000

1. INTRODUCTION

Overview. Dealing with noisy data is one of the main challenges in machine learning and is anactive area of research. In this work we study the noise-tolerant learning of linear separators, arguably the most popular class of functions used in practice [Cristianini and Shawe-Taylor 2000].
Learning linear separators from correctly labeled (non-noisy) examples is a very well understood
problem with simple efficient algorithms that are effective both in the classical passive learning
Author’s email addresses: P. Awasthi, pranjal.awasthi@rutgers.edu; M. F. Balcan, ninamf@cs.cmu.edu; P. M. Long,
phil.long@sentient.ai.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee
provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on thefirst page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others
than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, toredistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee.
Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701
USA, fax +1 (212) 869-0481, or permissions@acm.org.
c YYYY ACM 0004-5411/YYYY/01-ARTA $15.00
DOI:http://dx.doi.org/10.1145/0000000.0000000

Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:2

Awasthi, Balcan and Long

setting [Kearns and Vazirani 1994; Vapnik 1998] and in the more modern active learning framework [Dasgupta 2011]. However, for noisy settings, except for the special case of uniform random
noise, very few positive algorithmic results exist even for passive learning. In the context of theoretical computer science more broadly, problems of noisy learning are related to seminal results
in approximation-hardness [Arora et al. 1993; Guruswami and Raghavendra 2006], cryptographic
assumptions [Blum et al. 1994; Regev 2005], and are connected to other classical questions in learning theory (e.g., learning DNF formulas [Kearns et al. 1994]), and appear as barriers in differential
privacy [Gupta et al. 2011].
In this paper we present new techniques for designing efficient algorithms for learning linear separators in the presence of malicious noise and adversarial label noise. These models were originallyproposed for a setting in which the algorithm must work for an arbitrary, unknown distribution. As
we will see, bounds on the amount of noise tolerated for this distribution-free setting were weak,and no significant progress was made for many years. This motivated research investigating the roleof the distribution generating the data on the tolerable level of noise: a breakthrough result of [Kalai
et al. 2005] and subsequent work of [Klivans et al. 2009a] showed that indeed better bounds can beobtained for the uniform and isotropic log-concave distributions. In this paper, we continue this lineof research. For the malicious noise case, where the adversary can corrupt both the label and the features of the observation (and it has unbounded computational power and access to the entire historyof the learning algorithm’s computation), we design an efficient algorithm that can learn with accuracy 1 −  while tolerating an Ω() noise rate. This is within a constant factor of the statistical limit
even in the case of the uniform distribution. In particular, unlike previous works, our noise tolerance
limit has no dependence on the dimension d of the space. We also show similar improvements foradversarial label noise, and furthermore show that our algorithms can naturally exploit the power ofactive learning. Active learning is a widely studied modern learning paradigm, where the learningalgorithm only receives the class labels of examples when it asks for them. We show that in thismodel, our algorithms achieve a label complexity whose dependence on the error parameter  is exponentially better than that of any passive algorithm. This provides the first polynomial-time active
learning algorithm for learning linear separators in the presence of adversarial label noise, solving
an open problem posed in [Balcan et al. 2006; Monteleoni 2006]. It also provides the first analysis
showing the benefits of active learning over passive learning under the challenging malicious noisemodel.
Our work brings a new set of algorithmic and analysis techniques including localization (previously used for obtaining better sample complexity results) and soft outlier removal that we believe
will have other applications in learning theory and optimization. Localization [Bartlett et al. 2005;
Boucheron et al. 2005; Zhang 2006; Balcan et al. 2007; Bshouty et al. 2009; Koltchinskii 2010;
Hanneke 2011; Balcan and Long 2013] refers to the practice of progressively narrowing the focus
of a learning algorithm to an increasingly restricted range of possibilities (which are known to besafe given the information up to a certain point in time), thereby improving the stability of estimatesof the quality of these possibilities based on random data.
In the following we start by formally defining the learning models we consider. We then present
the most relevant prior work, and then our main results and techniques.
Passive and Active Learning. Noise Models. In this work we consider the problem of learning linear separators in two learning paradigms: the classical passive learning setting and the more
modern active learning scenario. As is typical [Kearns and Vazirani 1994; Vapnik 1998], we assume that there exists a distribution D over <d and a fixed unknown target function whose parameter vector is w∗ . In the noise-free case, in the passive supervised learning model the algorithm is given access to a distribution oracle EX(D, w∗ ) from which it can get training samples(x, sign(w∗ · x)) where x ∼ D. The goal of the algorithm is to output a hypothesis w such that
errD (w) = Prx∼D [sign(w∗ · x) 6= sign(w · x)] ≤ . In the active learning model [Cohn et al. 1994;
Dasgupta 2011] the learning algorithm is given as input a pool of unlabeled examples drawn fromthe distribution oracle. The algorithm can then query for the labels of examples of its choice from
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Learning Linear Separators with Noise

A:3

the pool. The goal is to produce a hypothesis of low error while also optimizing for the number oflabel queries (also known as label complexity). The hope is that in the active learning setting we
can output a classifier of small error by using many fewer label requests than in the passive learning setting by actively directing the queries to informative examples (while keeping the number of
unlabeled examples polynomial).
In this work we focus on two noise models. The first one is the malicious noise model of [Valiant
1985; Kearns and Li 1988] where samples are generated as follows: with probability (1 − η) a
random pair (x, y) is output where x ∼ D and y = sign(w∗ · x); with probability η the adversary
can output an arbitrary pair (x, y) ∈ <d × {−1, 1}. We will call η the noise rate. Each of theadversary’s examples can depend on the state of the learning algorithm and also the previous drawsof the adversary. We will denote the malicious oracle as EXη (D, w∗ ). The goal remains, however,to output a hypothesis w such that Prx∼D [sign(w∗ · x) 6= sign(w · x)] ≤ .
In this paper, we consider an extension of the malicious noise model to the the active learningmodel as follows. There are two oracles, an example generation oracle and a label revealing oracle.
The example generation oracle works as usual in the malicious noise model: with probability (1−η)
a random pair (x, y) is generated where x ∼ D and y = sign(w∗ · x); with probability η theadversary can output an arbitrary pair (x, y) ∈ <d ×{−1, 1}. In the active learning setting, unlike thestandard malicious noise model, when an example (x, y) is generated, the algorithm only receives
x, and must make a separate call to the label revealing oracle to get y. The goal of the algorithm isstill to output a hypothesis w such that Prx∼D [sign(w∗ · x) 6= sign(w · x)] ≤ .
In the adversarial label noise model, before any examples are generated, the adversary may choosea joint distribution P over <d × {−1, 1} whose marginal distribution over <d is D and such thatPr(x,y)∼P (sign(w∗ · x) 6= y) ≤ η. In the active learning version of this model, once again we will
have two oracles, an example generation oracle and a label revealing oracle. We note that the resultsfrom our theorems in this model translate immediately into similar guarantees for the agnostic modelof [Kearns et al. 1994] (used commonly both in passive and active learning (e.g., [Kalai et al. 2005;
Balcan et al. 2006; Hanneke 2007]) – see Appendix C for details.
We will be interested in algorithms that run in time poly(d, 1/) and use poly(d, 1/) examples.
In addition, for the active learning scenario we want our algorithms to also optimize for the numberof label requests. In particular, we want the number of labeled examples to depend only polylogarithmically in 1/. The goal then is to quantify for a given value of , the tolerable noise rate η()which would allow us to design an efficient (passive or active) learning algorithm.
Previous Work. In the context of passive learning, Kearns and Li’s analysis [1988] implies thathalfspaces can be efficiently learned withrespect to arbitrary distributions in polynomial time while
tolerating a malicious noise rate of Ω̃ d . Kearns and Li [1988] also showed that malicious noisecannot be tolerated (and a slight variant of their construction shows thatat a rate greater than 1+
this remains true even when the distribution is uniform over the unit sphere). The Ω̃ d bound forthe distribution-free case was not improved for many years. Kalai et al. [2005] showed that,2 when
the distribution√ is uniform, the poly(d, 1/)-time averaging algorithm tolerates malicious noise at
a rate Ω(/ d). They also described an improvement to Ω̃(/d1/4 ) based on the observation thatuniform examples will tend to be well-separated, so that pairs of examples that are too close to one
another can be removed, and this limits an adversary’s ability to coordinate the effects of its noisy
examples. [Klivans et al. 2009a] analyzed another approach to limiting the coordination of the noisy
examples: they proposed an outlier removal procedure that used PCA to find any direction u onto
which projecting the training data led to suspiciously high variance, and removing examples withthe most extreme values after projecting onto any such u. Their algorithm tolerates malicious noise
at a rate Ω(2 / log(d/)) under the uniform distribution.
2 These results from [Kalai et al. 2005] are most closely related to our work. We describe some of their other results, more

prominently featured in their paper, later.

Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:4

Awasthi, Balcan and Long

Motivated by the fact that many modern machine learning applications have massive amounts
of unannotated or unlabeled data, there has been significant interest in designing active learningalgorithms that most efficiently utilize the available data, while minimizing the need for human intervention. Over the past decade there has been substantial progress on understanding the underlying
statistical principles of active learning, and several general characterizations have been developed
for describing when active learning could have an advantage over the classical passive supervised
learning paradigm both in the noise free settings and in the agnostic case [Freund et al. 1997; Dasgupta 2005; Balcan et al. 2006; Balcan et al. 2007; Hanneke 2007; Dasgupta et al. 2007; Castro
and Nowak 2007; Balcan et al. 2008; Koltchinskii 2010; Beygelzimer et al. 2010; Wang 2011; Dasgupta 2011; Raginsky and Rakhlin 2011; Balcan and Hanneke 2012; Hanneke 2014]. However,despite many efforts, except for very simple noise models (random classification noise [Balcan andFeldman 2013] and linear noise [Dekel et al. 2012]), to date there are no known computationallyefficient algorithms with provable guarantees in the presence of noise. In particular, there are nocomputationally efficient algorithms for the agnostic case, and furthermore no result exists showing the benefits of active learning over passive learning in the malicious noise model, where theadversary may also corrupt the features.
We discuss additional related work in Appendix A.
1.1. Our Results

The following are our main results.
T HEOREM 1.1. There is a polynomial-time algorithm A1 for learning linear separators withrespect to isotropic log-concave distributions in <d in the presence of adversarial label noise, andpositive constants C and 0 such that, for all 0 <  < 0 , and all δ > 0, if η < C, then the output
w of A1 satisfies Pr(x,y)∼D [sign(w · x) 6= sign(w∗ · x)] ≤  with probability at least 1 − δ.
Further, A1 uses at most poly(d, log(1/), log(1/δ)) labeled examples.
T HEOREM 1.2. There is a polynomial-time algorithm A2 for learning linear separators withrespect to isotropic log-concave distributions in <d in the presence of malicious noise, and positive
constants C and 0 such that, for all 0 <  < 0 , and all δ > 0, if η < C, then the output w of A2
satisfies Pr(x,y)∼D [sign(w · x) 6= sign(w∗ · x)] ≤  with probability at least 1 − δ.
A2 uses at most poly(d, log(1/), log(1/δ)) labeled examples.
As a restatement of Theorem 1.1, in the agnostic setting considered in [Kalai et al. 2005], we
can output a halfspace of error at most O(η + α) in time poly(d, 1/α). In the case of the uniform
distribution, Kalai, et al, achieved error η + α by learning a low degree polynomial in time whose
dependence on the inverse accuracy is super-exponential. On the other hand, this result of [Kalai
et al. 2005] applies when the target halfspace does not necessarily go through the origin.
Our algorithms naturally exploit the power of active learning. (Indeed, as we will see, an active
learning algorithm proposed in [Balcan et al. 2007] provided the springboard for our work.) We
show that in this model, the label complexity of both algorithms is polylogarithmic in 1/. Our
efficient algorithm that tolerates adversarial label noise solves an open problem posed in [Balcan
et al. 2006; Monteleoni 2006]. Furthermore, our paper provides the first active learning algorithm
for learning linear separators in the presence of non-trivial amount of adversarial noise that canaffect not only the label, but also the features.
Our work exploits the power of localization for designing noise-tolerant polynomial-time algorithms. Such localization techniques have been used for analyzing sample complexity for passive
learning (see [Bartlett et al. 2005; Boucheron et al. 2005; Zhang 2006; Bshouty et al. 2009; Balcan
and Long 2013]) or for designing active learning algorithms (see [Balcan et al. 2007; Koltchinskii
2010; Hanneke 2011; Balcan and Long 2013]). Ideas useful for making such a localization strategy
computationally efficient, and tolerating malicious noise, are described in Section 1.2.
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Learning Linear Separators with Noise

A:5

We note that all our algorithms are proper in that they return a linear separator. (Linear models
can be evaluated efficiently, and are otherwise easy to work with.) We summarize our results, andthe most closely related previous work, in Tables I and II.
Table I: Comparison with previous poly(d, 1/)-time algs. for uniform distribution

Passive Learning
malicious

η =Ω

η=Ω

adversarial



Prior
 work [Kalai et al. 2005]

d1/4
2



log(d/)η=Ω √ [Klivans et al. 2009a][Kalai et al. 2005]

η = Ω ()NA

η = Ω ()log(1/)Active Learning(malicious and adversarial)

Our workη = Ω ()Table II: Comparison with previous poly (d, 1/)-time algorithms isotropic log-concave distributions

Passive Learning
malicious
adversarial
Active Learning(malicious and adversarial)Prior work3
η = Ω log2(d/) [Klivans et al. 2009a]



η=Ω

3


log(1/)[Klivans et al. 2009a]NA

Our workη = Ω ()η = Ω ()η = Ω ()1.2. Techniques

Hinge Loss Minimization As minimizing the 0-1 loss in the presence of noise is NP-hard [Johnson
and Preparata 1978; Garey and Johnson 1990], a natural approach is to minimize a surrogate convex
loss that acts as a proxy for the 0-1 loss. A common choice in machine learning is to use thehingeloss: max (0,1 − y(w · x)) . In this paper, we use the slightly more general `τ (w, x, y) =P
, and, for a set T of examples, we let `τ (w, T ) = |T1 | (x,y)∈T `τ (w, x, y).
max 0, 1 − y(w·x)τ
Here τ is a parameter that changes during training. It can be shown that√minimizing hinge loss
with an appropriate normalization factor can tolerate a noise rate of Ω(2 / d) under isotropic logconcave distributions in <d . This is also the limit for such a strategy since a more powerful malicious
adversary can concentrate all the noise directly opposite to the target vector w∗ and make sure thatthe hinge-loss is no longer a faithful proxy for the 0-1 loss.
Localization in the instance and concept space Our first key insight is that by using an iterative
localization technique, we can limit the harm caused by an adversary at each stage and hence can still
do hinge-loss minimization despite significantly more noise. In particular, the iterative algorithm we
propose proceeds in stages and at stage k, we have a hypothesis vector wk of a certain error rate.
The goal in stage k is to produce a new vector wk+1 with error rate a constant factor smaller than
wk ’s. In order to reduce the error rate, we focus on a band of size bk = e−ck around the boundaryof the linear classifier whose normal vector is wk , i.e. Swk ,bk = {x : |wk · x| < bk }. For the restof the paper, we will repeatedly refer to this key region of borderline examples as “the band”. The
key observation made in [Balcan et al. 2007] is that outside the band, all the classifiers still underconsideration (namely those hypotheses within radius rk of the previous weight vector wk ) will
have very small error. Furthermore, the probability mass of this band under the original distribution
is small enough, so that in order to make the desired progress we only need to find a hypothesis ofconstant error rate over the data distribution conditioned on being within margin bk of wk . This idea
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:6

Awasthi, Balcan and Long

was used in [Balcan et al. 2007] to obtain active learning algorithms with improved label complexity
ignoring computational complexity considerations3 .
In this work, we build on this idea to produce polynomial time algorithms with improved noise
tolerance. To obtain our results, we exploit several new ideas: (1) the performance of the rescaled
hinge loss minimization in smaller and smaller bands, (2) an analysis of properties of the distribution
obtained after conditioning on the band that enables us to more sensitively identify cases in which
the adversary concentrates the effects of noisy examples, (3) another type of localization — a novelsoft outlier removal procedure.
We first show that if we minimize a variant of the hinge loss that is rescaled depending on thewidth of the band, it remains a faithful enough proxy for the 0-1 error even when there is significantly more noise. As a first step towards this goal, consider the setting where we pick τk proportionally to bk , the size of the band, and rk is proportional to the error rate of wk , and then minimize
a normalized hinge loss function `τk (w, x, y) = max(0, 1 − y(w·x)τk ) over vectors w in B(wk , rk ),the ball of radius rk centered at wk . We first show that w∗ has small hinge loss within the band.
Furthermore, within the band the adversarial examples cannot hurt the hinge loss of w∗ by a lot.
To see this notice that if the malicious noise rate is η, within Swk−1 ,bk the effective noise rate is√O(η/bk ). Also, with high probability, the hinge loss for vectors w ∈ B(wk , rk ) is at√most Õ( d).
Hence the maximum amount by which the adversary
can affect the hinge loss is Õ(η d/bk ). Using√
this approach we get a noise tolerance of Ω̃(/ d).
In order to get better tolerance in the adversarial, or agnostic, setting, we note that examples x
for which |w · x| is large for w close to wk−1 are the most harmful, and, by analyzing the varianceof w · x for such directions w, we can more effectively limit the amount by which an adversary can“hurt” the hinge loss. This then leads to an improved noise tolerance of Ω().
Our algorithm that tolerates adversarial label noise does not work for the malicious noise model:
it can be foiled by an algorithm that concentrates η measure on an incorrectly labeled example
within Θ() of the separating hyperplane of the target, but with a very large norm. If the norm of
this noisy example is large enough, its hinge loss can overwhelm the hinge losses of clean examples.
We cope with this using a soft localized outlier removal procedure at each stage (described next).
This procedure assigns a weight to each data point indicating the algorithm’s confidence that the
point is not “noisy”. We then minimize the weighted hinge loss. Combining this with the varianceanalysis mentioned above leads to a noise of tolerance of Ω() in the malicious case.
Soft Localized Outlier Removal Outlier removal has been used for learning linear classifiers before[Blum et al. 1997; Klivans et al. 2009a]. In [Klivans et al. 2009a], the goal of outlier removal was tolimit the ability of the adversary to coordinate the effects of noisy examples – excessive such coordination was detected and removed. Our outlier removal procedure (Algorithm 3) is similar in spirit tothat of [Klivans et al. 2009a] with two key differences. First, as in [Klivans et al. 2009a], we will use
the variance of the examples in a particular direction to measure their coordination. However, due tothe fact that in round k, we are minimizing the hinge loss only with respect to vectors that are close
to wk−1 , we only need to limit the variance in these directions. As training proceeds, the band isincreasingly shaped like a pancake, with wk−1 pointing in its flattest direction. Hypotheses that areclose to wk−1 also point in flat directions; the variance in those directions is Θ(b2k ) which is muchsmaller than variance found in a generic direction. This allows us to limit the harm of the adversary
to a greater extent than was possible in the analysis of [Klivans et al. 2009a]. The second difference is that, unlike previous outlier removal techniques, rather than making discrete remove-or-not
decisions, we instead weigh the examples and then minimize the weighted hinge loss. Each weightindicates the algorithm’s confidence that an example is not noisy. We show that these weights canbe computed by solving a linear program with infinitely many constraints. We then show how to de3 We note that the localization considered by [Balcan et al. 2007] is a more aggressive one than those considered in disagree-

ment based active learning literature [Balcan et al. 2006; Hanneke 2007; Koltchinskii 2010; Hanneke 2011; Wang 2011] andearlier in passive learning [Bartlett et al. 2005; Boucheron et al. 2005; Zhang 2006].

Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Learning Linear Separators with Noise

A:7

sign an efficient separation oracle for the linear program using recent general-purpose optimization
techniques [Sturm and Zhang 2003; Bienstock and Michalka 2014].
1.3. Recent developments

Subsequent to the publication of this work in preliminary form [Awasthi et al. 2014], Daniely [2015]
combined the techniques of this paper with the polynomial-separation technique of [Kalai et al.
2005] to achieve a PTAS for agnostic learning of halfspaces with respect to the uniform distribution. (Recall that agnostic learning is essentially equivalent to learning with adversarial label noise,as outlined in Appendix C.) Awasthi et al. [2015] provided efficient (active and passive) learning algorithms for learning linear separators in the presence of (sufficiently benign) bounded noise (a.k. a.
Massart noise)4 to arbitrarily small excess error under the uniform distribution over the unit spherein Rd . Awasthi et al. [2016] improved on this algorithm (to allow for any constant bounded noise),and extended the technique to apply to the related problems of attribute efficient learning of linear separators and the popular signal processing problem of 1-bit compressed sensing (both in thepassive learning model). The soft outlier technique introduced in our work has also been recently
applied successfully in agnostically learning mixtures of distributions [Diakonikolas et al. 2016].
2. PRELIMINARIESP
Recall that `τ (w, x, y) = max 0, 1 − y(w·x)
and `τ (w, T ) = |T1 | (x,y)∈T `τ (w, x, y). Simiτ
larly, the expected hinge loss w.r.t. D is defined as Lτ (w, D) = Ex∼D (`τ (w, x, sign(w∗ · x))). Our
analysis will also consider the distribution Dw,γ obtained by conditioning D on membership in theband, i.e. the set {x : |w · x| ≤ γ}.
We present our algorithms in the active learning model. Since we will prove that our active algorithm only uses a polynomial number of unlabeled samples, this will imply a guarantee for passive
learning setting. At a high level, our algorithms are iterative learning algorithms that operate inrounds. In each round k we focus on points that fall near the decision boundary of the current hypothesis wk−1 and use them in order to obtain a new vector wk of lower error. In the malicious
noise case, in round k we first do a soft outlier removal and then minimize hinge loss normalized
appropriately by τk .
When analyzing the malicious noise model, we will refer to the examples generated by the adversary as the noisy examples, and the other examples as the clean examples.
For vectors u and v, denote the angle between them by θ(u, v). Let B(u, r) be the ball of radiusr centered at u.
The description of the algorithms and their analysis is simplified if we assume that it starts with apreliminary weight vector w0 whose angle with the target w∗ is acute, i.e. that satisfies θ(w0 , w∗ ) <π/2. We show in Appendix B that this is without loss of generality for the types of problems weconsider.
A probability distribution is isotropic log-concave if its density can be written as exp(−ψ(x)) fora convex function ψ, its mean is 0, and its covariance matrix is I.
3. ADVERSARIAL LABEL NOISE

Algorithm 1 is our algorithm for learning in the presence of adversarial label noise. In the analysis
below, we assume that the algorithm has access to w0 such that θ(w0 , w∗ ) < π/2. This can beshown to be without loss of generality (see Appendix B)).
Theorem 1.1 follows immediately from the following theorem analyzing Algorithm 1.
T HEOREM 3.1. Let a distribution D over Rd be isotropic log-concave. Let w∗ be the (unitlength) target weight vector. There are settings of the parameters of Algorithm 1, and positive con4 The Massart noise is widely studied in statistical learning theory(see e.g. [Boucheron et al. 2005]) and can be thought of as arealistic generalization of the random classification noise, where where the label of each example x is flipped independently
with constant probability η(x) < 1/2.

Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:8

Awasthi, Balcan and Long

Input: allowed error rate , probability of failure δ, an oracle that returns x, for (x, y) sampledfrom EXη (f, D), and an oracle for getting the label from an example; a sequence of sample sizes
mk > 0; a sequence of cut-off values bk > 0; a sequence of hypothesis space radii rk > 0; aprecision value κ > 0(1) Draw m1 labeled examples and put them into a working set W .
(2) For k = 1, . . . , s = dlog2 (1/)e(a) Find vk ∈ B(wk−1 , rk ) to approximately minimize training hinge loss over W s.t. kvk k2 ≤ 1:
`τk (vk , W ) ≤ minw∈B(wk−1 ,rk )∩B(0,1)) `τk (w, W ) + κ/8.
(b) Normalize vk to have unit length, yielding wk = kvvkkk2 .
(c) Clear the working set W .
(d) Until mk+1 additional data points are put in W , given an unlabeled example x for (x, f (x)) obtained
from EXη (f, D), if |wk · x| ≥ bk , then reject x else ask for the label of x and put the example intoW

Output: Weight vector ws of error at most  with probability 1 − δ.
Algorithm 1: C OMPUTATIONALLY E FFICIENT A LGORITHM TOLERATING ADVERSARIAL LABEL
NOISE

stants M , C and 0 , such that, for all  < 0 , for any δ > 0, if the rate η of adversarial noiseksatisfies η < C, a number n
 k = poly(d, M , log(1/δ)) of unlabeled examples in round k and adnumber mk = O d log δ (d + log(k/δ)) of labeled examples in round k ≥ 1, and w0 suchthat θ(w0 , w∗ ) < π/2, after s = O(log(1/)) iterations, finds ws satisfying err(ws ) ≤  withprobability ≥ 1 − δ.
The rest of this section is dedicated to the proof of Theorem 3.1.
3.1. Relevant properties of isotropic log-concave distributions

We start by listing some properties of i.l.c. distributions that we will use in our analysis.
L EMMA 3.2 ([L OV ÁSZ AND V EMPALA 2007; V EMPALA 2010]). Assume that D is isotropic
log-concave in Rd and let f be its density function.
√(a) Prx∼D [||x||2 ≥ α d] ≤ e−α+1 .
(b) Projections of D onto subspaces of Rd are isotropic log-concave.
(c) If d = 1, then Prx∼D [x ∈ [a, b]] ≤ |b − a|.
(d) There is an absolute constant c1 such that, if d = 1, f (x) > c1 for all x ∈ [−1/9, 1/9].
(e) There is an absolute constant c2 such that for any two unit vectors u and v in Rd we havec2 θ(v, u) ≤ Prx∼D (sign(u · x) 6= sign(v · x)).
(f) For any d, there are positive c3 (d) and c4 (d) such that f (x) ≤ c3 (d) exp(−c4 (d)||x||).
Parts (a)-(d) are from [Lovász and Vempala 2007]. Part (e) is implicit in [Vempala 2010], and set
out explicitly in [Balcan and Long 2013]. Part (f) is from [Klivans et al. 2009b].
We will use the following lemma as a tool to analyze the variance in directions close to the
hypothesis at any given time.
L EMMA 3.3. For any C > 0, there exist constants c, c0 such that, for any isotropic log-concave
distribution D, for any a such that, kak2 ≤ 1, and ||u − a||2 ≤ r, for any 0 < γ < C, and for any
K ≥ 4, we have
q


2
p
−c0 K 1+ γr222.
Pr|a · x| > K r + γ ≤ cex∼Du,γP ROOF. W.l.o.g. we may assume that u = (1, 0, 0, · · · , 0).
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Learning Linear Separators with Noise

A:9

Let a0 = (a2 , ..., ad ), and, for a random x = (x1 , x2 , ..., xd ) drawn from Du,γ , let x0 =(x2 , ..., xd ). We may rewrite the probability that we want to bound asp Prx∼D |a · x| > K r2 + γ 2 and |x1 | ≤ γpPr|a · x| > K r2 + γ 2 =.
(1)x∼Du,γPrx∼D (|x1 | ≤ γ)
Lemma 3.2 implies that there is a positive constant c1 such that the denominator satisfies the following lower bound:c1 γ
Pr (|x1 | ≤ γ) ≥ c1 min{γ, 1/9} ≥
.
(2)
x∼D
9C
So now, we just need an upper bound on the numerator. We have




p
p
Pr |a · x| > K r2 + γ 2 and |x1 | ≤ γ ≤ Pr |a0 · x0 | > K r2 + γ 2 − γ and |x1 | ≤ γ
x∼D
x∼D


p
≤ Pr |a0 · x0 | > (K − 1) r2 + γ 2 and |x1 | ≤ γ .
x∼D0Define a00 = kaa0 k . Define random variable Y to be a00 · x and a random variable X to be x1 where
x is drawn from D. Then we have E[X] = E[x1 ] = 0. E[Y ] = E[a00 · x] = 0. Furthermore,E[X 2 ] = 1, E[Y 2 ] = 1 and E[XY ] = 0. Hence, the joint distribution of X and Y is isotropic logconcave. Let f (X, Y ) be the p.d.f. of this distribution. Then the numerator can be upper bounded asfollows:
Z γZ ∞


p
0
0
2
2
4 Pr a · x > (K − 1) r + γ and 0 ≤ x1 ≤ γ ≤ 4f (X, Y )dXdY.
√
2
2
x∼D

0

(K−1) r +γ
ka0 k

Applying Part (f) of Lemma 3.2 with d = 2, there are constants c and c0 such that the numerator is
at mostZ γZ ∞p0
exp(−cc
X 2 + Y 2 )dXdY√22(K−1) r +γ
ka0 k

0

Z γZ ∞≤c√0(K−1) r 2 +γ 2ka0 k

exp(−c0 Y )dXdY

pr2 + γ 2≤ c γ exp(−c
),
ka0 k
√
(K−1) r 2 +γ 2
in part because the fact that ka0 k ≤ r implies that> 3. Hence the numerator of (1)
ka0 k
q
2
γ
is at most ≤ c00 γ exp(−c0 (K − 1) 1 + r2 ), completing the proof.
00

0 (K − 1)Armed with Lemma 3.3, now we are ready for the variance bound. It improves on a bound froman earlier version of this paper [Awasthi et al. 2014], matching what was obtained in that version forthe special case of the uniform distribution. This improvement is what leads to closing a log factor
gap in the tolerable rate of noise for i.l.c. distributions.
L EMMA 3.4. Assume that D is isotropic log-concave.
For any c3 , there is a constant c4 such that, for all 0 < γ ≤ c3 , for all a such that ku − ak2 ≤ r
and kak2 ≤ 1
Ex∼Du,γ ((a · x)2 ) ≤ c4 (r2 + γ 2 ).
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:10

Proof: Let z =Awasthi, Balcan and Longp

r2 + γ 2 . Setting, with foresight, t = 16z 2 , we have
Ex∼Du,γ ((a · x)2 )Z ∞=Pr ((a · x)2 ≥ α) dα
x∼D
u,γ
0
Z ∞
≤t+
Pr ((a · x)2 ≥ α) dα.
t(3)x∼Du,γSince t ≥ 16z 2 , Lemma 3.3 implies that, for absolute constants c and c0 , we have√Z ∞αEx∼Du,γ ((a · x)2 ) ≤ t + c)dα.
exp(−c0rtNow, we want to evaluate the integral. Using a change of variables u2 = α, we get
√

Z ∞
Z ∞
 √ 

√
2r2
t
0
0
exp −c α/r dα = 2 √ u exp (−c u/r) du = 0 2+ 1 exp −c0 t/r .
rctt
Putting it together, we get
2cr2
Ex∼Du,γ ((a · x) ) ≤ t + 0 2
c
2

√

t

r





0

+ 1 exp −c

√



t/r ≤



c
1 + 02
2c


t+



2cr2
0z
exp
−4c
r
c0 2

and, since t = 16z 2 and zr ≥ 1, we get the desired bound.
Finally, we will use a lemma from [Balcan and Long 2013] that generalizes and strengthens a
key lemma from [Balcan et al. 2007]. It is used to show that, during the learning process, mostlarge-margin examples are classified correctly.
L EMMA 3.5 (T HEOREM 4 OF [BALCAN AND L ONG 2013]). For any c5 > 0, there is a c6 >0 such that the following holds. Let u and v be two unit vectors in Rd , and assume that θ(u, v) =α < π/2. If D is isotropic log-concave in Rd , then Prx∼D [sign(u · x) 6= sign(v · x) and |v · x| ≥c6 α] ≤ c5 α.
3.2. Parameters for the algorithm

For easy reference throughout the proof, here we collect together the settings of the parameters of
the algorithm.
Let M = max{ c22π , 2}, where c2 is from Lemma 3.2. Let c01 be the value of c6 in Lemma 3.5
c2
corresponding to the case where c5 is 4M; then let bk = c01 M −k .
0
Let c2 be c1 from Lemma 3.2. Let rk = min{M −(k−1) /c2 , π/2}, where c2 is from Lemma 3.2,1/9}κ
and κ = 4c01M . Let τk = c1 min{bk−1, where c1 is the value from Lemma 3.2.
6
1
Let zk2 = rk2 + b2k−1 .
3.3. The error within a band in each iteration

At each iteration, Algorithm 1 concentrates its attention on examples in the band. Our next theorem
analyzes its error on these examples.
δT HEOREM 3.6. For k ≤ dlogM (1/)e, if errD (wk−1 ) ≤ M −(k−1) , with probability 1 − k+k2(over the random examples in round k), after round k of Algorithm 1, we have errDwk−1 ,bk−1 (wk ) ≤κ.

We will prove Theorem 3.6 using a series of lemmas below. First, we bound the hinge loss of thetarget w∗ within the band Swk−1 ,bk−1 . Since we are analyzing a particular round k, to reduce clutter
in the formulas, for the rest of this section, let us refer to `τk as `, and Lτk (·, Dwk−1 ,bk−1 ) as L(·).
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Learning Linear Separators with Noise

A:11

L EMMA 3.7. L(w∗ ) ≤ κ/6.
P ROOF. Notice that y(w∗ · x) is never negative, so, on any clean example (x, y), we havey(w∗ · x)`(w , x, y) = max 0, 1 −
τk


∗


≤ 1,

and, furthermore, w∗ will pay a non-zero hinge only inside the region where |w∗ · x| < τk . Hence,L(w∗ ) ≤Pr

Dwk−1 ,bk−1(|w∗ · x| ≤ τk ) =Prx∼D (|w∗ · x| ≤ τk & |wk−1 · x| ≤ bk−1 ).
Prx∼D (|wk−1 · x| ≤ bk−1 )Using Part (d) of Lemma 3.2, for the value of c1 in that definition, we can lower bound thedenominator:
Pr (|wk−1 · x| < bk−1 ) ≥ 2c1 min{bk−1 , 1/9}.

x∼DPart (c) of Lemma 3.2 also implies that the numerator is at mostPr (|w∗ · x| ≤ τk ) ≤ 2τk .

x∼DHence, we have
L(w∗ ) ≤2τk= κ/6.
2c1 min{bk−1 , 1/9}

Let P̃ be the joint distribution used by the algorithm, which includes the noisy labels chosen by
the adversary. Let N = {(x, y) : sign(w∗ · x) 6= y} consist of noisy examples, so that P̃ (N ) ≤ η.
Let P be the joint distribution obtained by applying the correct labels. Let P̃k be the distribution on
the examples given to the algorithm in round k (obtained by conditioning P̃ to examples that fallwithin the band), and let Pk be the corresponding joint distribution with clean labels.
The key lemma here is to bound how far the expected loss with respect to the distribution P̃kgiven to the algorithm is from to the expected loss with respect to the distribution Pk with thecleaned labels. Informally, it shows that, to an extent, E(x,y)∈P̃k (`(w, x, y)) is an effective proxyfor E(x,y)∈Pk (`(w, x, y)).
L EMMA 3.8. There is an absolute positive constant c such that, if we define zk =then for any w ∈ B(wk−1 , rk ), we haver|E(x,y)∈Pk `(w, x, y)) − E(x,y)∈P̃k `(w, x, y))| ≤ cJournal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

η zk
.
 τk

q

rk2 + b2k−1

(4)

A:12

Awasthi, Balcan and Long

P ROOF. Fix an arbitrary w ∈ B(wk−1 , rk ). Recalling that N is the set of noisy examples, andthat the marginals of Pk and P̃k on the inputs are the same, we have|E(x,y)∈Pk (`(w, x, y)) − E(x,y)∈P̃k (`(w, x, y))|= |E(x,y)∈P̃k (`(w, x, y) − `(w, x, sign(w∗ · x)))|= |E(x,y)∈P̃k (1(x,y)∈N (`(w, x, y) − `(w, x, −y)))|≤ E(x,y)∈P̃k (1(x,y)∈N |`(w, x, y) − `(w, x, −y)|)|w · x|≤ 2E(x,y)∈P̃k 1(x,y)∈Nτk2= E(x,y)∈P̃k 1(x,y)∈N |w · x|τkq2r
Pr (N ) × E(x,y)∈P̃k ((w · x)2 )≤τk (x,y)∼P̃kby the Cauchy-Schwarz inequality. Lemma 3.2 implies that, for an absolute constant c0 ,(N ) ≤

Pr(x,y)∈P̃k

Pr(x,y)∈P̃ (N )Pr(x,y)∈P̃ (Swk−1 ,bk−1 )≤η
c0 M −k≤ηc0 /M

since k ≤ dlogM (1/)e, and Lemma 3.4 implies E(x,y)∈P̃k ((w · x)2 ) ≤ c0 zk2 .

Finally, we need some bounds about estimates of the hinge loss.

L EMMA 3.9. Let

cleaned(W ) = {(x, sign(w∗ · x)) : (x, y) ∈ W }.

δWith probability 1 − k+k
2 , for all w ∈ B(wk−1 , rk ), we have|E(x,y)∈P̃ (`(w, x, y))−`(w, W )| ≤ κ/16, and |E(x,y)∈P (`(w, x, y))−`(w, cleaned(W ))| ≤ κ/16.
(5)

P ROOF. See Appendix D.
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Learning Linear Separators with Noise

A:13

δP ROOF OF T HEOREM 3.6. With probability 1 − k+k
2 , we have, for absolute constants c1 andc2 , the following:

errDwk−1 ,bk−1 (wk ) = errDwk−1 ,bk−1 (vk )≤ E(x,y)∈Pk (`(vk , x, y)) (since for each error, the hinge loss is at least 1)rη zk
×(by Lemma 3.8)
≤ E(x,y)∈P̃k (`(vk , x, y)) + c1

τk
r
η zk
≤ `(vk , W ) + c1
×+ κ/16 (by Lemma 3.9)

τk
r
η zk
≤ `(w∗ , W ) + c1
×
+ κ/8

τk
r
η zk
≤ E(x,y)∈P̃k (`(w∗ , x, y)) + c1
×+ κ/4 (by Lemma 3.9)

τk
r
η zk
≤ E(x,y)∈P (`(w∗ , x, y)) + c2
×+ κ/4 (by Lemma 3.8)

τk
r
η zk
≤ c2
×
+ κ/2,
τksince L(w∗ ) ≤ κ/6. Since zk /τk = Θ(1), there is an constant c3 such that, η ≤ c3  suffices for
errDwk−1 ,bk−1 (wk ) ≤ κ, completing the proof.
3.4. Putting it together

Now we are ready to put everything together. The proof of Theorem 3.1 follows the high levelstructure of the proof of [Balcan et al. 2007]; the new element is the application of Theorem 3.6
which analyzes the performance of the hinge loss minimization algorithm for learning inside theband.
Proof (of Theorem 3.1): We will prove by induction on k that after k ≤ s iterations, we haveerrD (wk ) ≤ M −k with probability 1 − δ(1 − 1/(k + 1))/2.
When k = 0, all that is required is errD (w0 ) ≤ 1.
Assume now the claim is true for k − 1 (k ≥ 1). Then by induction hypothesis, we know that withprobability at least 1−δ(1−1/k)/2, wk−1 has error at most M −(k−1) . Using Part (e) of Lemma 3.2,
this implies that θ(wk−1 , w∗ ) ≤ M −(k−1) /c6 . This in turn implies θ(wk−1 , w∗ ) ≤ π/2. (Whenk = 1, this is by assumption, and otherwise it is implied by Part (e) of Lemma 3.2.)
Let us define Swk−1 ,bk−1 = {x : |wk−1 · x| ≤ bk−1 } and S̄wk−1 ,bk−1 = {x : |wk−1 · x| > bk−1 }.
Since wk−1 has unit length, and vk ∈ B(wk−1 , rk ), we have θ(wk−1 , vk ) ≤ rk which in turnimplies θ(wk−1 , wk ) ≤ min{M −(k−1) /c6 , π/2}.
Applying Lemma 3.5 to bound the error rate outside the band, we have both
 M −kPr (wk−1 · x)(wk · x) < 0, x ∈ S̄wk−1 ,bk−1 ≤x4and M −k
Pr (wk−1 · x)(w∗ · x) < 0, x ∈ S̄wk−1 ,bk−1 ≤
.
x
4


−k
Taking the sum, we obtain Prx (wk · x)(w∗ · x) < 0, x ∈ S̄wk−1 ,bk−1 ≤ M2 . Therefore, we
have
M −k
err(wk ) ≤ (errDwk−1 ,bk−1 (wk )) Pr(Swk−1 ,bk−1 ) +.
2
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:14

Awasthi, Balcan and Long

Input: allowed error rate , probability of failure δ, an oracle that returns x, for (x, y) sampled fromEXη (f, D), and an oracle for getting the label y from an example; a sequence of unlabeled sample
sizes nk > 0, k ∈ Z + ; a sequence of labeled sample sizes mk > 0; a sequence of cut-off values
bk > 0; a sequence of hypothesis space radii rk > 0; a sequence of removal rates ξk ; a sequence ofvariance bounds σk2 ; precision value κ; weight vector w0 .
(1) Draw n1 unlabeled examples and put them into a working set W .
(2) For k = 1, . . . , s = dlog2 (1/)e(a) Apply Algorithm 3 to W with parameters u ← wk−1 , γ ← bk−1 , r ← rk , ξ ← ξk , σ 2 ← σk2 and let
q be the output function q : W → [0, 1] . Normalize q to form a probability distribution p over W .
(b) Choose mk examples from W according to p and reveal their labels. Call this set T .
(c) Find vk ∈ B(wk−1 , rk ) to approximately minimize training hinge loss over T s.t. kvk k2 ≤ 1:
`τk (vk , T ) ≤ minw∈B(wk−1 ,rk )∩B(0,1)) `τk (w, T ) + κ/8.
Normalize vk to have unit length, yielding wk = kvvkkk2 .
(d) Clear the working set W .
(e) Until nk+1 additional data points are put in W , given unlabeled x for (x, f (x)) obtained fromEXη (f, D), if |wk · x| ≥ bk , then reject x else put into W .

Output: weight vector ws of error at most  with probability 1 − δ.
Algorithm 2: C OMPUTATIONALLY E FFICIENT A LGORITHM TOLERATING MALICIOUS NOISE
Since Pr(Swk−1 ,bk−1 ) ≤ 2bk−1 , this implies
err(wk ) ≤ (errDwk−1 ,bk−1 (wk ))2bk−1 +



M −k
≤ M −k (errDwk−1 ,bk−1 (wk ))2c01 M + 1/2 .
2

Recall that Dwk−1 ,bk−1 is the distribution obtained by conditioning D on the event that x ∈Swk−1 ,bk−1 . Combining Theorem 3.6 with the induction hypothesis,
Pr(err(wk ) > 1/M k )≤ Pr(err(wk ) > 1/M k |err(wk−1 ) ≤ 1/M k−1 ) + Pr(err(wk−1 ) > 1/M k−1 )δ+ δ(1 − 1/k)/2≤
2(k + k 2 )= δ(1 − 1/(k + 1))/2.
This completes the proof of the induction, and therefore shows, with probability at least 1 − δ,O(log(1/)) iterations suffice to achieve err(wk ) ≤ .
A polynomial number of unlabeled samples are required
P by the algorithm and the number of labeled examples required by the algorithm is
k mk = O(d(d + log log(1/) +log(1/δ)) log(1/)).
4. LEARNING WITH MALICIOUS NOISE

The intuition in the case of malicious noise is the same as for adversarial noise, except that, because
the adversary can also change the marginal distribution over the instances, it is necessary to perform
an additional outlier removal step at each stage of the algorithm. Furthermore, we need a different
analysis since in this case the marginal distribution over the examples can change.
Theorem 1.2 follows immediately from the following theorem analyzing Algorithm 2.
T HEOREM 4.1. Let a distribution D over Rd be isotropic log-concave. Let w∗ be the (unitlength) target weight vector. There are settings of the parameters of Algorithm 2, and positive constants M , C and 0 , such that, for all  < 0 , for any δ > 0, if the rate η of malicious noiseksatisfies η < C, a number n
 k = poly(d, M , log(1/δ)) of unlabeled examples in round k and adnumber mk = O d log δ (d + log(k/δ)) of labeled examples in round k ≥ 1, and w0 such
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Learning Linear Separators with Noise

A:15

Input: a set S = {(x1 , x2 , . . . , xn )} of samples; the reference unit vector u; desired radius r; aparameter ξ specifying the desired bound on the fraction of clean examples removed; a variancebound σ 2
(1) Find q : S → [0, 1] satisfying the following constraints:(a) for all
P x ∈ S, 0 ≤ q(x) ≤ 11(b) |S|(x,y)∈S q(x) ≥ 1 − ξP221(c) for all w ∈ B(u, r) ∩ B(0, 1), |S|x∈S q(x)(w · x) ≤ σ .

Output: A function q : S → [0, 1].
Algorithm 3: L OCALIZED SOFT OUTLIER REMOVAL PROCEDURE
that θ(w0 , w∗ ) < π/2, after s = O(log(1/)) iterations, finds ws satisfying err(ws ) ≤  withprobability ≥ 1 − δ.
The rest of this section is dedicated to the proof of Theorem 4.1.
4.1. Parameters for the algorithm

With the exception of the parameters σk2 and ξk of the outlier removal procedure, the parameters are
set exactly as in Section 3.2.
The values of σk2 and ξk are determined by our analysis: σk2 is c(rk2 + b2k−1 ), for the value of cin Theorem 4.2 below, that corresponds to the choice, in the statement of Theorem 4.2, of C = c01 .
κ2 τ 2
Finally, ξk = min( 2κ7 , c4 216kz2 ), for the value of c4 in Lemma 3.4 corresponding to the choicekc3 = b0 .
4.2. Analysis of the outlier removal subroutine

The analysis of the learning algorithm uses the following lemma about Algorithm 3.
T HEOREM 4.2. For any C > 0, there is a constant c and a polynomial p such that, for allξ > 2η 0 and all 0 < γ < C, if n ≥ p(1/η 0 , d, 1/ξ, 1/δ, 1/γ, 1/r), then, with probability 1 − δ, theoutput q of Algorithm 3 satisfies the following:P— x∈S q(x) ≥ (1 − ξ)|S| (a fraction 1 − ξ of the weight is retained)— For all unit length w such that kw − uk2 ≤ r,
1 X
q(x)(w · x)2 ≤ c(r2 + γ 2 ).
(6)
|S|
x∈S

Furthermore, the algorithm can be implemented in polynomial time.
Our proof of Theorem 4.2 proceeds through a series of lemmas. Lemma 3.2 implies that we may
assume without loss of generality that the instances x1 , ..., xn from S are distinct. Obviously, afeasible q satisfies the requirements of the lemma. So all we need to show is— there is a feasible solution q, and— we can simulate a separation oracle: given a provisional solution q̂, we can find a linear constraint
violated by q̂ in polynomial time.
We will start by working on proving that there is a feasible q. First of all, a Chernoff boundimplies that n ≥ poly(1/η 0 , 1/δ) suffices for it to be the case that, with probability 1 − δ, at most2η 0 members of S are noisy. Let us assume from now on that this is the case.
We will show that q ∗ which sets q ∗ (x) = 0 for each noisy point, and q ∗ (x) = 1 for each nonnoisy point, is feasible.
First, we use VC tools to show that, if enough examples are chosen, a bound like Lemma 3.4, but
averaged over the clean examples, likely holds for all relevant directions.
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:16

Awasthi, Balcan and Long

L EMMA 4.3. If we draw ` times i.i.d. from D to form XC , with probability 1 − δ, we have thatfor any unit length a,r
1 X
O(d log(`/δ)(d + log(1/δ)))2
2(a · x) ≤ E[(a · x) ] +
.
`
`
x∈XC

Proof: See Appendix D.
Lemma 4.3 and Lemma 3.4 together directly imply that1n = poly d, 1/η 0 , 1/δ,= poly (d, 1/η 0 , 1/δ, 1/γ, 1/r)c(r2 + γ 2 )suffices for it to be the case that, for all w ∈ B(u, r),
1 X ∗q (x)(a · x)2 ≤ 2E[(a · x)2 ] ≤ 2c4 (r2 + γ 2 ),
|S|
(x,y)

where c4 is the value in Lemma 3.4 corresponding to setting c3 = C. If c = 2c4 , we have that q ∗ isfeasible.
So what is left is to prove is that a separation oracle for the convex program can be computed inpolynomial time. Very roughly, there is a linear constraint for each of a set of directions, limiting thevariance in that direction. We can find a violated constraint, if there is one, by finding the direction
with maximum variance, using something like PCA, but taking appropriate account of the fact that
we are only considering directions near u.
In detail, we may compute the separation
oracle as follows. First, it is easy to check whether, forP
all x, 0 ≤ q(x) ≤ 1, and whether x∈S q(x) ≥ (1 − ξ)|S|. An algorithm can first do that. If thesepass, then it needs to check whether there is a w ∈ B(u, r) with ||w||2 ≤ 1 such that
1 X
q(x)(w · x)2 > c(r2 + γ 2 ).
|S|
x∈S
P
This can be done by finding w ∈ B(u, r) with ||w||2 ≤ 1 that maximizes x∈S q(x)(w · x)2 , andchecking it.
pq(x)x. Thenwith a row for each x ∈ S, where the row is
PSuppose X is 2a matrixTTq(x)(w
·
x)
=
w
X
Xw,
and,
maximizing
this
over
w
is
an
equivalent
problemto minx∈S
imizing wT (−X T X)w subject to kw − uk2 ≤ r and ||w|| ≤ 1. Since −X T X is symmetric,
problems of this form are known to be solvable in polynomial time [Sturm and Zhang 2003] (see[Bienstock and Michalka 2014]).
4.3. The error within a band in each iteration

At each iteration, Algorithm 2 concentrates its attention on examples in the band. Our next theorem
analyzes its error on these examples.
δT HEOREM 4.4. For k ≤ dlogM (1/)e, if errD (wk−1 ) ≤ M −(k−1) , with probability 1 − k+k2(over the random examples in round k), after round k of Algorithm 2, we have errDwk−1 ,bk−1 (wk ) ≤κ.

We will prove Theorem 4.4 using a series of lemmas below. First, we bound the hinge loss of thetarget w∗ within the band Swk−1 ,bk−1 . Since we are analyzing a particular round k, to reduce clutter
in the formulas, for the rest of this section, let us refer to `τk as `, and Lτk (·, Dwk−1 ,bk−1 ) as L(·).
First, Lemma 3.7, that L(w∗ ) ≤ κ/6, also applies here, using exactly the same proof.
During round k we can decompose the working set W into the set of “clean” examples WC which
are drawn from Dwk−1 ,bk−1 and the set of “dirty” or malicious examples WD which are output by
the adversary. We will next show that the fraction of dirty examples in round k is not too large.
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Learning Linear Separators with Noise

A:17

δ
L EMMA 4.5. There is an absolute positive constant c such that, with probability 1 − 6(k+k2) ,cM ηnk|WD | ≤ cηnk M k ≤(7)

P ROOF. From Lemma 3.2 and the setting of our parameters, the probability that an example fallsδ
in Swk−1 is at least Ω(M −k ). Therefore, with probability (1 − 12(k+k2 ) ), the number of examples
we must draw before we encounter nk examples that fall within Swk−1 ,bk−1 is at most O(nk M k ).
The probability that each unlabeled example we draw is noisy is at most η. Applying a Chernoff
δkbound, with probability at least 1 − 12(k+k2 ) , we have |WD | ≤ cηnk M . Since k ≤ dlogM (1/)e,this completes the proof.
Recall that the total variation distance between two probability distributions is the maximum
difference between the probabilities that they assign to any event.
We
P can think of q as soft indicator functions for “keeping” examples, and so interpret the inequality x∈W q(x) ≥ (1 − ξ)|W | as roughly akin to saying that most examples are kept. This meansthat distribution p obtained by normalizing q is close to the uniform distribution over W . We makethis precise in the following lemma.
L EMMA 4.6. The total variation distance between p and the uniform distribution over W is at
most ξ.
P ROOF. Lemma 1 of [Long and Servedio 2006] implies that the total variation distance ρ between p and the uniform distribution over W satisfies




X
X
1
1
q(x)
ρ=1−
min p(x),
=1−
,
.
min P
|W |
u∈W q(u) |W |
x∈W

x∈W

Since q(u) ≤ 1 for all u, we havePu∈W q(u) ≤ |W |, so that

ρ≤1−

1 X
min{q(x), 1}.
|W |
x∈W

Again, since q(x) ≤ 1, we haveρ≤1−(1 − ξ)|W |
= ξ.
|W |

Next, we will relate the average hinge loss when examples are weighted according to p, i.e.,`(w, p) to the hinge loss averaged over clean examples WC , i.e., `(w, WC ). Here `(w, WC ) and`(w, p) are defined with respect to the unrevealed labels that the adversary has committed to.
L EMMA 4.7. There areq absolute constants C1 , C2 and C3 such that, with probability 1 −δ
rk2 + b2k−1 , then for any w ∈ B(wk−1 , rk ), we have2(k+k2 ) , if we define zk =C1 η`(w, WC ) ≤ `(w, p) +




zk
1+
τk


+ κ/32(8)

and`(w, p) ≤ 2`(w, WC ) + κ/32 +

C2 η
+ C3


Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

r

η zk
× .

τk

(9)

A:18

Awasthi, Balcan and Long

P ROOF. Assume without loss of generality that each element (x, y) ∈ W is distinct. Fix anarbitrary w ∈ B(wk−1 , rk ). By Theorem 4.2, Lemma 4.5, Lemma 3.2, Lemma 3.4, and Lemma 4.3,
δ
we know that, with probability 1 − 2(k+k2 ) , there are absolute constants K1 , K2 and K3 such that
1 X
q(x)(w · x)2 ≤ K1 zk2
|W |

(10)

x∈W

K2 ηnk(11)(w · x)2 ≤ K3 zk2 .

(12)|WD | ≤
1|WC |X(x,y)∈WC(We will need the value of K3 later: we may use
K3 = 2c4(13)

for the value of c4 in Lemma 3.4 corresponding to c3 = b0 .)AssumePthat (10), (11) and (12) all hold.
Since x∈W q(x) ≥ (1 − ξk )|W | ≥ |W |/2, we have that (10) impliesX

p(x)(w · x)2 ≤ 2K1 zk2 .

(14)

x∈W

First, let us bound the weighted loss on noisy examples in the training set. In particular, we willshow that
 
X
p
zk
p(x)`(w, x, y) ≤ K2 η/ + ξk + 2K1 K2 η/ + ξk
.
(15)
τk
(x,y)∈WD

To see this, notice that,X(x,y)∈WD≤ Pr(WD ) +p(x,y)∈WD1
τk≤ Pr(WD ) +1τk≤ Pr(WD ) +

q

p

p

X

p(x)`(w, x, y) =X
y(w · x)p(x) max 0, 1 −τkp(x)|w · x| = Pr(WD ) +p(x,y)∈WDs X

p(x)1WD (x, y)(x,y)∈W

s X

1
τk

X

p(x)1WD (x, y)|w · x|(x,y)∈W

p(x)(w · x)2 (by the Cauchy-Schwarz inequality)(x,y)∈W


2K1 Pr(WD )
p

zk
τk


≤

p
K2 η
+ ξk + 2K1 K2 η/ + ξk




zk
τk



where the second to last inequality follows by (14) and the last one by Lemma 4.6 and (11).
Similarly, we will show thatX(x,y)∈Wp(x)`(w, x, y) ≤ 1 +

p


2K1

zk
τk


.

(16)

Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Learning Linear Separators with Noise

A:19

To see this notice that,y(w · x)p(x)`(w, x, y) =p(x) max 0, 1 −τk(x,y)∈W(x,y)∈W
s
X
1 X
1
≤1+
p(x)|w · x| ≤ 1 +p(x)(w · x)2τkτk(x,y)∈W(x,y)∈Wpzk,≤ 1 + 2K1
τkX

X

by (14).
Next, we have


1  X
`(w, WC ) =q(x)`(w, x, y) + (1WC (x, y) − q(x))`(w, x, y)
|WC |(x,y)∈W


X
1  X
≤
q(x)`(w, x, y) +(1 − q(x))`(w, x, y)
|WC |(x,y)∈W(x,y)∈WC




X
1  X
|w · x| ≤q(x)`(w, x, y) +(1 − q(x)) 1 +|WC |τk(x,y)∈W(x,y)∈WC


X
1
1  X
q(x)`(w, x, y) + ξk |W | +(1 − q(x))|w · x|
≤
|WC |
τk
(x,y)∈W(x,y)∈WC

s X
s
X
1
1  X
2
q(x)`(w, x, y) + ξk |W | +(1 − q(x))
≤
|WC |
τk
(x,y)∈W(x,y)∈WCby the Cauchy-Schwarz inequality. Recall that 0 ≤ q(x) ≤ 1, and
Thus,

P

(x,y)∈W q(x) ≥ 1 − ξk |W |.

(x,y)∈Wby (12). Since |WC | ≥ |W |/2, we haveq(x)`(w, x, y) + 2ξk +(x,y)∈W

Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

(w · x)2 (x,y)∈WC



s X
1p
1  X
`(w, WC ) ≤q(x)`(w, x, y) + ξk |W | +ξk |W |
(w · x)2 |WC |τk(x,y)∈WC(x,y)∈W


 
p
1  X
zk 
≤
q(x)`(w, x, y) + ξk |W | + ξk |W ||WC |K3
|WC |
τk


1  X
`(w, WC ) ≤
|WC |



p


2ξk K3

zk
τk


.

A:20

Awasthi, Balcan and Long

We have chosen ξk small enough that


1  X
`(w, WC ) ≤q(x)`(w, x, y) + κ/32
|WC |(x,y)∈WPX(x,y)∈W q(x)
p(x)`(w, x, y) + κ/32=
|WC |(x,y)∈W!PX(x,y)∈W q(x)= `(w, p) +−1 
p(x)`(w, x, y) + κ/32
|WC |(x,y)∈W




X
|W |
≤ `(w, p) +−1 
p(x)`(w, x, y) + κ/32
|WC |(x,y)∈W

 

p
zk
|W |
−1
1 + 2K1+ κ/32,≤ `(w, p) +|WC |
τkby (16). Applying (11) yields (8).
Also,
X`(w, p) =p(x)`(w, x, y)(x,y)∈W=

X

p(x)`(w, x, y) +(x,y)∈WCX

p(x)`(w, x, y)(x,y)∈WDzk(by (15)).
τk(x,y)∈WCP pzk(x,y)∈WC q(x)`(w, x, y)P=+ K2 η/ + ξk + 2K1 K2 η/ + ξkτk(x,y)∈WC q(x)
P
 
p
zk
(x,y)∈WC `(w, x, y)≤ P+ K2 η/ + ξk + 2K1 K2 η/ + ξk(since ∀x, q(x) ≤ 1)).
τk(x,y)∈WC q(x)
P
 
p
zk
(x,y)∈WC `(w, x, y)+ K2 η/ + ξk + 2K1 K2 η/ + ξk≤
|WC | − ξ|W |
τk
 
p
zk
≤ 2`(w, WC ) + K2 η/ + ξk + 2K1 K2 η/ + ξk
,
τk
≤

X

p(x)`(w, x, y) + K2 η/ + ξk +p



2K1 K2 η/ + ξkby (11), which in turn implies (9).
ROOF OF T HEOREM
4.4. Exploiting the fact that, with high probability, `(w, x, y) =
Pq


d
O
d log δfor all (x, y) ∈ Swk−1 ,bk−1 and w ∈ B(wk−1 , rk ) as in the proof of Lemma 3.9,δwith probability 1 − 2(k+k2 ) , for all w ∈ B(wk−1 , rk ),|L(w) − `(w, WC )| ≤ κ/32

(17)|`(w, p) − `(w, T )| ≤ κ/32.

(18)

and

Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Learning Linear Separators with Noise

A:21

δ
Also with probability 1 − 2(k+k2 ) , both (8) and (9) hold. Let us assume from here on that all ofthese hold.
Then we haveerrDwk−1 ,bk−1 (wk ) = errDwk−1 ,bk−1 (vk )≤ L(vk ) (since for each error, the hinge loss is at least 1)≤ `(vk , WC ) + κ/16 (by (17))


C1 η
zk
≤ `(vk , p) +1+
+ κ/8 (by (8))

τk


zk
C1 η
≤ `(vk , T ) +1++ κ/4 (by (18))

τk


C1 η
zk
≤ `(w∗ , T ) +1++ κ/4 (since w∗ ∈ B(wk−1 , rk ))

τk


C1 η
zk
∗
≤ `(w , p) +1+
+ κ/3 (by (18)).
τkThis, together with (9) and (17), gives
r
C2 η
η zk
errDwk−1 ,bk−1 (wk ) ≤ 2`(w , WC ) +
+ C3
×


τk


C1 η
zk
+
1+
+ 2κ/5

τk
r


zk
C2 η
η zk
C1 η
∗
+ C3
×
1+
≤ 2L(w ) +
+
+ κ/2


τk

τk
r


η zk
C2 η
C1 η
zk
+ C3
×
≤ κ/3 ++
1+
+ κ/2,


τk

τk
∗

by Lemma 3.7.
Now notice that zk /τk is Θ(1). Hence an Ω() bound on η suffices to imply thatδ
errDwk−1 ,bk−1 (wk ) ≤ κ with probability (1 − k+k
2 ).
The rest of the analysis is exactly the same as for the case of adversarial label noise.
5. DISCUSSION

We note that the idea of localization in the concept space is traditionally used in statistical learning theory both in supervised and active learning for getting sharper rates [Boucheron et al. 2005;
Bshouty et al. 2009; Koltchinskii 2010]. Furthermore, the idea of localization in the instance space
has been used in margin-based analysis of active learning [Balcan et al. 2007; Balcan and Long
2013]. In this work we used localization in both senses in order to get polynomial-time algorithms
with better noise tolerance. It would be interesting to further exploit this idea for other concept
spaces.
Our algorithms run in polynomial time, and therefore use a polynomial number of examples.
Notably, they use only polylogarithmically many class labels. Our bounds on the total number ofexamples used by our algorithms are, however, somewhat worse than the best bounds known for
the noise-free case. In order to find and remove outliers, the precision with which we need statistics
on the training data to match properties of the underlying distribution gets finer as the number ofvariables increases. When combined with the usual effect in VC analyses regarding growth of therichness of behavior with the number of variables (which could be partially mitigated using localized analysis in place of the VC tools that we have used here), this leads to the increased requirement
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:22

Awasthi, Balcan and Longon the number of examples. Substantially improving the sample complexity and finding more computationally efficient noise-tolerant algorithms is a potentially useful topic for future research.
While we have chosen to focus on isotropic log-concave distributions to present our techniques
in a clean setting, it appears that, using tools from [Balcan and Long 2013; Awasthi et al. 2014], ouranalysis can be applied to a broader class of distributions with minor changes, including “nearly logconcave distributions”, defined as in [Applegate and Kannan 1991]. One property of the distributionthat is needed for our analysis is that it is fairly likely that a random example falls fairly close to
the separating hyperplane of the target. While this may not be the case in some applications, suchapplications are typically easier, and might be handled separately. Provably noise-tolerant learningof linear classifiers for natural classes of distributions that include such cases is another important
topic for future work.
Acknowledgments

We thank Steve Hanneke for helpful communications. We also thank anonymous reviewers for theirhelpful comments. This work was supported in part by NSF grants CCF-0953192, CCF-1101283,
and CCF-1422910, AFOSR grant FA9550-09-1-0538, ONR grant N00014-09-1-0751, and a Microsoft Research Faculty Fellowship.
REFERENCES
M. Anthony and P. L. Bartlett. 1999. Neural Network Learning: Theoretical Foundations. Cambridge University Press.
D. Applegate and R. Kannan. 1991. Sampling and integration of near log-concave functions. In STOC.
S. Arora, L. Babai, J. Stern, and Z. Sweedyk. 1993. The hardness of approximate optima in lattices, codes, and systems oflinear equations. In Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science.
P. Awasthi, M. Balcan, and P. M. Long. 2014. The power of localization for efficiently learning linear separators with noise.
In STOC. 449–458. See also Arxiv paper 1307.8371v7.
P. Awasthi, M.-F. Balcan, N. Haghtalab, and R. Urner. 2015. Efficient Learning of Linear Separators under Bounded Noise.
See also Arxiv paper 1503.03594.
P. Awasthi, M.-F. Balcan, N. Haghtalab, and H. Zhang. 2016. Learning and 1-bit Compressed Sensing under Asymmetric
Noise. In COLT.
P. Awasthi, A. Blum, and O. Sheffet. 2010. Improved guarantees for agnostic learning of disjunctions. In COLT.
M.-F. Balcan, A. Beygelzimer, and J. Langford. 2006. Agnostic active learning. In ICML.
M.-F. Balcan, A. Broder, and T. Zhang. 2007. Margin based active learning. In COLT.
M.-F. Balcan and V. Feldman. 2013. Statistical Active Learning Algorithms. In NIPS.
M.-F. Balcan and S. Hanneke. 2012. Robust Interactive Learning. In COLT.
M.-F. Balcan, S. Hanneke, and J. Wortman. 2008. The True Sample Complexity of Active Learning. In COLT.
M.-F. Balcan and P. M. Long. 2013. Active and passive learning of linear separators under log-concave distributions. In
Conference on Learning Theory.
P. L. Bartlett, O. Bousquet, and S. Mendelson. 2005. Local Rademacher complexities. Annals of Statistics 33, 4 (2005),
1497–1537.
A. Beygelzimer, D. Hsu, J. Langford, and T. Zhang. 2010. Agnostic Active Learning Without Constraints. In NIPS.
D. Bienstock and A. Michalka. 2014. Polynomial solvability of variants of the trust-region subproblem. In SODA.
A. Birnbaum and S. Shalev-Shwartz. 2012. Learning Halfspaces with the Zero-One Loss: Time-Accuracy Tradeoffs. In
NIPS.
A. Blum, A. Frieze, R. Kannan, and S. Vempala. 1997. A polynomial time algorithm for learning noisy linear threshold
functions. Algorithmica 22, 1/2 (1997), 35–52.
Avrim Blum, Merrick L. Furst, Michael J. Kearns, and Richard J. Lipton. 1994. Cryptographic Primitives Based on Hard
Learning Problems. In Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology.
S. Boucheron, O. Bousquet, and G. Lugosi. 2005. Theory of Classification: a Survey of Recent Advances. ESAIM: Probability and Statistics 9 (2005), 9:323–375.
N. H. Bshouty, Y. Li, and P. M. Long. 2009. Using the doubling dimension to analyze the generalization of learning algorithms. JCSS (2009).
T. Bylander. 1994. Learning linear threshold functions in the presence of classification noise. In Conference on Computational Learning Theory.
R. Castro and R. Nowak. 2007. Minimax Bounds for Active Learning. In COLT.

Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Learning Linear Separators with Noise

A:23

N. Cesa-Bianchi, C. Gentile, and L. Zaniboni. 2010. Learning noisy linear classifiers via adaptive and selective sampling.
Machine Learning (2010).
D. Cohn, L. Atlas, and R. Ladner. 1994. Improving Generalization with Active Learning. Machine Learning 15, 2 (1994).
N. Cristianini and J. Shawe-Taylor. 2000. An introduction to support vector machines and other kernel-based learning
methods. Cambridge University Press.
A. Daniely. 2015. A PTAS for Agnostically Learning Halfspaces. In COLT. See also Arxiv paper arXiv:1410.7050.
S. Dasgupta. 2005. Coarse sample complexity bounds for active learning. In NIPS.
S. Dasgupta. 2011. Active Learning. Encyclopedia of Machine Learning (2011).
S. Dasgupta, D.J. Hsu, and C. Monteleoni. 2007. A general agnostic active learning algorithm. In NIPS.
O. Dekel, C. Gentile, and K. Sridharan. 2012. Selective Sampling and Active Learning from Single and Multiple Teachers.
JMLR (2012).
I. Diakonikolas, G. Kamath, D. Kane, J. Li, A. Moitra, and A. Stewart. 2016. Robust Estimators in High Dimensions without
the Computational Intractability. ArXiv e-prints (April 2016).
V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami. 2006. New Results for Learning Noisy Parities and Halfspaces. In
FOCS. 563–576.
Y. Freund, H.S. Seung, E. Shamir, and N. Tishby. 1997. Selective sampling using the query by committee algorithm. Machine
Learning 28, 2-3 (1997), 133–168.
Michael R. Garey and David S. Johnson. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness.
A. Gonen, S. Sabato, and S. Shalev-Shwartz. 2013. Efficient Pool-Based Active Learning of Halfspaces. In ICML.
Anupam Gupta, Moritz Hardt, Aaron Roth, and Jonathan Ullman. 2011. Privately releasing conjunctions and the statisticalquery barrier. In Proceedings of the 43rd annual ACM symposium on Theory of computing.
Venkatesan Guruswami and Prasad Raghavendra. 2006. Hardness of Learning Halfspaces with Noise. In Proceedings of the
47th Annual IEEE Symposium on Foundations of Computer Science.
V. Guruswami and P. Raghavendra. 2009. Hardness of Learning Halfspaces with Noise. SIAM J. Comput. 39, 2 (2009),
742–765.
S. Hanneke. 2007. A Bound on the Label Complexity of Agnostic Active Learning. In ICML.
S. Hanneke. 2011. Rates of Convergence in Active Learning. The Annals of Statistics 39, 1 (2011), 333–361.
S. Hanneke. 2014. Theory of Disagreement-Based Active Learning. Foundations and Trends in Machine Learning.
S. Hanneke, V. Kanade, and L. Yang. 2015. Learning with a Drifting Target Concept. In ALT.
D. S. Johnson and F. Preparata. 1978. The densest hemisphere problem. Theoretical Computer Science 6, 1 (1978), 93 – 107.
Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. 2005. Agnostically Learning Halfspaces.
In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science.
Michael Kearns and Ming Li. 1988. Learning in the presence of malicious errors. In Proceedings of the twentieth annual
ACM symposium on Theory of computing.
Michael Kearns, Robert Schapire, and Linda Sellie. 1994. Toward Efficient Agnostic Learning. Mach. Learn. 17, 2-3 (Nov.
1994).
M. Kearns and U. Vazirani. 1994. An introduction to computational learning theory. MIT Press, Cambridge, MA.
A. R. Klivans, P. M. Long, and Rocco A. Servedio. 2009a. Learning Halfspaces with Malicious Noise. Journal of Machine
Learning Research 10 (2009).
A. R. Klivans, P. M. Long, and A. Tang. 2009b. Baum’s Algorithm Learns Intersections of Halfspaces with respect to LogConcave Distributions. In RANDOM.
V. Koltchinskii. 2010. Rademacher Complexities and Bounding the Excess Risk in Active Learning. Journal of Machine
Learning Research 11 (2010), 2457–2485.
P. M. Long and R. A. Servedio. 2006. Attribute-efficient learning of decision lists and linear threshold functions under
unconcentrated distributions. NIPS (2006).
P. M. Long and R. A. Servedio. 2011. Learning large-margin halfspaces with more malicious noise. In NIPS.
L. Lovász and S. Vempala. 2007. The geometry of logconcave functions and sampling algorithms. Random Structures andAlgorithms 30, 3 (2007), 307–358.
Claire Monteleoni. 2006. Efficient algorithms for general active learning. In Proceedings of the 19th annual conference on
Learning Theory.
D. Pollard. 2011. Convergence of Stochastic Processes.
M. Raginsky and A. Rakhlin. 2011. Lower Bounds for Passive and Active Learning. In NIPS.
Oded Regev. 2005. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the thirtyseventh annual ACM symposium on Theory of computing.

Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:24

Awasthi, Balcan and Long

Rocco A. Servedio. 2001. Smooth Boosting and Learning with Malicious Noise. In 14th Annual Conference on Computational Learning Theory and 5th European Conference on Computational Learning Theory.
J. Sturm and S. Zhang. 2003. On cones of nonnegative quadratic functions. Mathematics of Operations Research 28 (2003),
246–267.
L. G. Valiant. 1985. Learning disjunction of conjunctions. In Proceedings of the 9th International Joint Conference on
Artificial intelligence.
V. Vapnik. 1998. Statistical Learning Theory. Wiley-Interscience.
S. Vempala. 2010. A random-sampling-based algorithm for learning intersections of halfspaces. JACM 57, 6 (2010).
L. Wang. 2011. Smoothness, Disagreement Coefficient, and the Label Complexity of Agnostic Active Learning. JMLR
(2011).
C. Zhang and K. Chaudhuri. 2014. Beyond Disagreement-Based Agnostic Active Learning. In NIPS.
T. Zhang. 2006. Information Theoretical Upper and Lower Bounds for Statistical Estimation. IEEE Transactions on Information Theory 52, 4 (2006), 1307–1321.

A. ADDITIONAL RELATED WORK

Passive Learning. Blum et al. [Blum et al. 1997] considered noise-tolerant learning of halfspaces
under a more idealized noise model, known as the random noise model, in which the label of eachexample is flipped with a certain probability, independently of the feature vector. Some other, lessclosely related, work on efficient noise-tolerant learning of halfspaces includes [Bylander 1994;
Blum et al. 1997; Feldman et al. 2006; Guruswami and Raghavendra 2009; Servedio 2001; Awasthi
et al. 2010; Long and Servedio 2011; Birnbaum and Shalev-Shwartz 2012].
Active Learning. As we have mentioned, most prior theoretical work on active learning focuseson either sample complexity bounds (without regard for efficiency) or on providing polynomial timealgorithms in the noiseless case or under simple noise models (random classification noise [Balcan
and Feldman 2013] or linear noise [Cesa-Bianchi et al. 2010; Dekel et al. 2012]).
In [Cesa-Bianchi et al. 2010; Dekel et al. 2012] online learning algorithms in the selective sampling framework are presented, where labels must be actively queried before they are revealed.
Under the assumption that the label conditional distribution is a linear function determined by afixed target vector, they provide bounds on the regret of the algorithm and on the number of labels
it queries when faced with an adaptive adversarial strategy of generating the instances. As pointed
out in [Dekel et al. 2012], these results can also be converted to a distributional PAC setting where
instances xt are drawn i.i.d. In this setting they obtain exponential improvement in label complexity
over passive learning. These interesting results and techniques are not directly comparable to ours.
One important difference is that (as pointed out in [Gonen et al. 2013]) the exponential improvement they give is not possible in the noiseless version of their setting. In other words, the additionof linear noise defined by the target makes the problem easier for active sampling. By contrast RCN
can only make the classification task harder than in the realizable case.
Recently, [Balcan and Feldman 2013] showed the first polynomial time algorithms for actively
learning thresholds, balanced rectangles, and homogenous linear separators under log-concave distributions in the presence of random classification noise. Active learning with respect to isotropic
log-concave distributions in the absence of noise was studied in [Balcan and Long 2013].
An algorithm for active learning with a general hypothesis space was proposed and analyzed byZhang and Chaudhuri [2014]. Efficient algorithms for tracking a drifting linear classifier when the
distribution is uniform were described by Hanneke, Kanade and Yang [2015].
B. ACUTE INITIALIZATION

We will prove that we may assume without loss of generality that the algorithm receives as input a
w0 whose angle with the target w∗ is acute.
Suppose we have an algorithm B as a subroutine that satisfies the guarantee of Theorem 3.1,
given access to such a w0 . Then we can arrive at an algorithm A which works without it as follows.
With probability 1, for a random u, either u or −u has an acute angle with w∗ . We may then run B
with both choices, and with  set to πc4 2 , where c2 is the constant in Part (e) of Lemma 3.2. Then we
Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

Learning Linear Separators with Noise

A:25

can use hypothesis testing on O(log(1/δ)) examples, and, with high probability, find a hypothesis
w0 with error less than πc4 2 . Part (e) of Lemma 3.2 then implies that A may then set w0 = w0 , andcall B again.
C. RELATING ADVERSARIAL LABEL NOISE AND THE AGNOSTIC SETTING

In this section we study the agnostic setting of [Kearns et al. 1994; Kalai et al. 2005] and describe
how our results imply constant factor approximations in that model. In the agnostic model, data(x, y) is generated from a distribution D over <d × {1, −1}. For a given concept class C, let
OP T be the error of the best classifier in C. In other words, OP T = argminf ∈C errD (f ) =argminf ∈C P r(x,y)∼D [f (x) 6= y]. The goal of the learning algorithm is to output a hypothesis hwhich is nearly as good as f , i.e., given  > 0, we want errD (h) ≤ c · OP T + , where c is theapproximation factor. Any result in the adversarial model that we study, translates into a result for
the agnostic setting via the following lemma.
L EMMA C.1. For a given concept class C and distribution D, if there exists an algorithm inthe adversarial noise model which runs in time poly(d, 1/) and tolerates a noise rate of η = Ω(),then there exists an algorithm for (C, D) in the agnostic setting which runs in time poly(d, 1/) andachieves error O(OP T + ).
P ROOF. Let f ∗ be the optimal halfspace with error OP T . In the adversarial setting, w.r.t. f ∗ , thenoise rate η will be exactly OP T . Set 0 = c(OP T + ) as input to the algorithm for the adversarialmodel. By the guarantee of the algorithm we will get a hypothesis h such that P r(x,y)∼D [h(x) 6=f ∗ (x)] ≤ 0 = c(OP T + ). Hence by triangle inequality, we have errD (h) ≤ errD (f ∗ ) +c(OP T + ) = O(OP T + ).
For the case when C is the class of origin centered halfspaces in Rd and the marginal of D is
the uniform distribution over Sd−1 , the above lemma along with Theorem 1.1 implies that we canoutput a halfspace of accuracy O(OP T + ) in time poly(d, 1/). The work of [Kalai et al. 2005]
achieves a guarantee of O(OP T + ) in time exponential in 1/ by doing L2 regression to learn alow degree polynomial, and that L1 regression can achieve a stronger guarantee of OP T + . As
noted above, their approach also does not require that the halfspace to be learned goes through theorigin.
D. PROOF OF VC LEMMAS

In this section, we apply some standard VC tools to establish some lemmas about estimates of
expectations.
Definition D.1. Say that a set F of real-valued functions with a common domain X shatters
x1 , ..., xd ∈ X if there are thresholds t1 , ..., td such that{(sign(f (x1 ) − t1 ), ..., sign(f (xd ) − td )) : f ∈ F } = {−1, 1}d .
The pseudo-dimension of F is the size of the largest set shattered by F .
We will use the following bound.
L EMMA D.2 (SEE [A NTHONY AND BARTLETT 1999]). Let F be a set of functions from acommon domain X to [a, b] and let d be the pseudo-dimension
 of F , and let D be a probability dis2

tribution over X. Then, for m = O (b−a)α2 (d + log(1/δ)) , if x1 , ..., xm are drawn independently
at random according to D, with probability 1 − δ, for all f ∈ F ,m

Ex∼D (f (x)) −1 X
f (xt ) ≤ α.
m t=1

Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.

A:26

Awasthi, Balcan and Long

D.1. Proof of Lemma 3.9

The pseudo-dimension of the set of linear combinations of d variables is known to be d [Pollard
2011]. Since, for any non-increasing function ψ : R → R and any F , the pseudo-dimension of{ψ ◦ f : f ∈ F } is at most that of F (see [Pollard 2011]), the pseudo-dimension of {`(w, ·) : w ∈Rd } is at most d.
Now, to apply Lemma D.2, we want an upper bound on the loss. The first step is a bound in termsof the norm.
L EMMA D.3. There is a constant c such that, for any w ∈ B(wk−1 , rk ), and all x,`(w, x, y) ≤ c(1 + ||x||2 ).
P ROOF.
|w · x||wk−1 · x| + kw − wk−1 k2 ||x||2
≤1+
τk
τk
0
−k
bk−1 + rk ||x||2
c M + min{M −(k−1) /c6 , π/2}||x||2
.
≤1+
=1+ 1
c2 min{c01 M −k ,c1 }κ
τk`(w, x, y) ≤ 1 +6c3

If the support of D is bounded, Lemma D.3 gives a useful worst-case bound on the loss. Next,
we give a high-probability bound that holds for all isotropic log-concave distributions.
δ
L EMMA D.4. For an absolute constant c, with probability 1 − 6(k+k
2) ,


√
|WC |kmax ||x||2 ≤ c d ln
.
x∈WC
δ

(19)

P ROOF. Applying Part (a) of Lemma 3.2 together with a union bound, we have√Pr(∃x ∈ WC , ||x|| > α) ≤ c9 |WC | exp(−α/ d),


√
2
δ
C |k
and α = d ln 12c9 |W
makes the RHS at most 6(k+k2) .
δLet D0 be the distribution obtained by conditioning D on the event that ||x|| < R, where R is
the RHS of (19). By Lemma D.4, the total variation distance between drawing the members of WCδ
independently random from D, and drawing them from D0 , it at most 1 − 6(k+k2 ) , so it suffices toprove (5) with respect to D0 . Applying Lemma D.3, and Lemma D.2 then completes the proof of(5).
D.2. Proof of Lemma 4.3

Define fa by fa (x) = (a · x)2 . The pseudo-dimension of the set of all such functions
is O(d)√[Klivans et al. 2009a]. As the proof of Lemma 3.9, w.l.o.g., all x have ||x||2 ≤ O( d log(`/δ)),and applying Lemma D.2 completes the proof.

Journal of the ACM, Vol. V, No. N, Article A, Publication date: January YYYY.