Abstract

1. Introduction
A halfspace is a Boolean-valued function of the form f = sign(∑ i = 1 v i x i − θ). Learning half- spaces in the presence of noisy data is a fundamental problem in machine learning. In addition ①???? Adam R. Klivans, Philip M. Long and Rocco A. Servedio. to its practical relevance, the problem has connections to many well-studied topics such as kernel methods (Shawe-Taylor and Cristianini, 2000), cryptographic hardness of learning (Klivans and Sherstov, 2006), hardness of approximation (Feldman et al., 2006; Guruswami and Raghavendra, 2006), learning Boolean circuits (Blum et al., 1997), and additive/multiplicative update learning algorithms (Littlestone, 1991; Freund and Schapire, 1999). Learning an unknown halfspace from correctly labeled (non-noisy) examples is one of the best- understood problems in learning theory, with work dating back to the famous Perceptron algorithm of the 1950s (Rosenblatt, 1958) and a range of efficient algorithms known for different settings (Novikoff, 1962; Littlestone, 1987; Blumer et al., 1989; Maass and Turan, 1994).  Much less is known, however, about the more difficult problem of learning halfspaces in the presence of noise. Important progress was made by Blum et al. (Blum et al., 1997) who gave a polynomial-time algorithm for learning a halfspace under classification noise . In this model each label is flipped independently with some fixed probability; the noise does not affect the actual example points themselves, which are generated according to an arbitrary probability distribution over R n . In the current paper we consider a much more challenging malicious noise model. In this model, introduced by Valiant (1985) (see also (Kearns and Li, 1993)), there is an unknown target function f and distribution D over examples. Each time the learner receives an example, independently with probability 1 – η it is drawn from D and labeled correctly according to f , but with probability η it is an arbitrary pair ( x, y ) which may be generated by an omniscient adversary. The parameter η is known as the "noise rate." Malicious noise is a notoriously difficult model with few positive results. It was already shown by Kearns and Li (1993) that for essentially all concept classes, it is information-theoretically im- possible to learn to accuracy 1 − ε if the noise rate η is greater than ε/(1 + ε). Indeed, known algorithms for learning halfspaces (Servedio, 2003; Kalai et al., 2008) or even simpler target func- tions (Mansour and Parnas, 1998) with malicious noise typically make strong assumptions about the underlying distribution D , and can learn to accuracy 1 − ε only for noise rates η much smaller than ε . We describe the most closely related work that we know of in Section 1.2. In this paper we consider learning under the uniform distribution on the unit ball in R n , and more generally under any isotropic log-concave distribution. The latter is a fairly broad class of dis- tributions that includes spherical Gaussians and uniform distributions over a wide range of convex sets. Our algorithms can learn from malicious noise rates that are quite high, as we now describe.
1.1  Main Results
Our first result is an algorithm for learning halfspaces in the malicious noise model with respect to the uniform distribution on the n -dimensional unit ball: Theorem 1 There is a poly( n , 1/ ε )-time algorithm that learns origin-centered halfspaces to accu- racy 1 – ϵ with respect to the uniform distribution on the unit ball in n dimensions in the presence of malicious noise at rate η = Ω(ε 2 / log( n/ε )). The condition on η is expressed using Ω and not O because we are showing that a weak upper bound on the noise rate suffices to achieve accuracy 1 – ε . Via a more sophisticated algorithm, we can learn in the presence of malicious noise under any isotropic log-concave distribution: Theorem 2 There is a poly( n , 1/ ε )-time algorithm that learns origin-centered halfspaces to accu- racy 1 – ϵ with respect to any isotropic log-concave distribution over R n and can tolerate malicious noise at rate η = Ω(ε 3 / log 2 (n/ε)). We are not aware of any previous polynomial-time algorithms for learning under isotropic log- concave distributions in the presence of malicious noise. Finally, we also consider a related noise model known as adversarial label noise . In this model there is a fixed probability distribution P over R n × {−1, 1} (i.e., over labeled examples) for which a 1 – η fraction of draws are labeled according to an unknown halfspace. The marginal distribution over R n is assumed to be isotropic log-concave; so the idea is that an "adversary" chooses an η fraction of examples to mislabel, but unlike the malicious noise model she cannot change the (isotropic log-concave) distribution of the actual example points in R n . Learning with adversarial label noise is clearly harder than with independent misclassification noise – the ability to choose which labels to corrupt allows the adversary to coordinate their effects to an extent. For the adversarial label noise model we prove: Theorem 3 There is a poly( n , 1/ ε )-time algorithm that learns origin-centered halfspaces to accu- racy 1 — ϵ with respect to any isotropic log-concave distribution over R n and can tolerate adver- sarial label noise at rate η = Ω(ε 3 / log(1/ε)).
1.2  Previous Work
Malicious noise. General-purpose tools developed by Kearns and Li (1993) (see also (Kearns et al., 1994)) directly imply that halfspaces can be learned for any distribution over the domain in ran- domized poly( n ,1 / ε ) time with malicious noise at a rate Ω( ε / n ); the algorithm repeatedly picks a random subsample of the training data, hoping to miss all the noisy examples. Kannan (see Arora et al. (1993)) devised a deterministic algorithm with a Ω(ε/π) bound that repeatedly exploits Helly's Theorem to find a group of n + 1 examples that includes a noisy example, then removes the group. Kalai et al. (2008) showed that the poly( n ,1 / ε )-time averaging algorithm (Servedio, 2001) tolerates noise at a rate Ω(ε/ √π) when the distribution is uniform. They also described an improvement to Î( ε/ n 1/4 ) based on the observation that uniform examples will tend to be well-separated, so that pairs of examples that are too close to one another can be removed. Adversarial label noise. Kalai, et al. showed that if the distribution over the instances is uniform over the unit ball, the averaging algorithm tolerates adversarial label noise at a rate Ω( ε / λ /log(1/ε )) in poly( n,1/ε ) time. (In that paper, learning in the presence of adversarial label noise was called "ag- nostic learning".) They also described an algorithm that fits low-degree polynomials that tolerates noise at a rate within an additive ϵ of the accuracy, but in poly( n 1/c 4 ) time; for log-concave distri- butions, their algorithm took poly ( n d (1/c) ) time, for an unspecified function d. The latter algorithm does not require that the distribution is isotropic, as ours does. Robust PCA. Independently of this work, Xu et al. (2009) designed and analyzed an algorithm that performs principal component analysis when some of the examples are corrupted arbitrarily, as in the malicious noise model studied here.  Also, the thesis of Brubaker (2009) presents a "Robust PCA" algorithm which is a PCA variant aimed at ameliorating the effects of noisy examples.
1.3 Techniques
Outlier Removal.  Consider first the simplest problem of learning an origin-centered halfspace with respect to the uniform distribution on the n -dimensional ball. A natural idea is to use a simple "averaging" algorithm that takes the vector average of the positive examples it receives and uses this as the normal vector of its hypothesis halfspace.  Servedio (2001) analyzed this algorithm for the random classification noise model, and Kalai et al. (2008) extended the analysis to the adversarial label noise model. Intuitively the "averaging" algorithm can only tolerate low malicious noise rates because the adversary can generate noisy examples which "pull" the average vector far from its true location. Our main insight is that the adversary does this most effectively when the noisy examples are coor- dinated to pull in roughly the same direction. We use a form of outlier detection based on Principal Component Analysis to detect such coordination. This is done by computing the direction w of maximal variance of the data set; if the variance in direction w is suspiciously large, we remove from the sample all points x for which (w · x)² is large. Our analysis shows that this causes many noisy examples, and only a few non-noisy examples, to be removed. We repeat this process until the variance in every direction is not too large. (This cannot take too many stages since many noisy examples are removed in each stage.) While some noisy examples may remain, we show that their scattered effects cannot hurt the algorithm much. Thus, in a nutshell, our overall algorithm for the uniform distribution is to first do outlier re- moval 1 by an iterated PCA-type procedure, and then simply run the averaging algorithm on the remaining “cleaned-up” data set. Extending to Log-Concave Distributions via Smooth Boosting.  We are able to show that the iterative outlier removal procedure described above is useful for isotropic log-concave distributions as well as the uniform distribution:  if examples are removed in a given stage, then many of the removed examples are noisy and only a few are non-noisy (the analysis here uses concentration bounds for isotropic log-concave distributions). However, even if there were no noise in the data, the average of the positive examples under an isotropic log-concave distribution need not give a high-accuracy hypothesis. Thus the averaging algorithm alone will not suffice after outlier removal. To get around this, we show that after outlier removal the average of the positive examples gives a (real-valued) weak hypothesis that has some nontrivial predictive accuracy.  (Interestingly, the proof of this relies heavily on anti-concentration properties of isotropic log-concave distributions!) A natural approach is then to use a boosting algorithm to convert this weak learner into a strong learner. This is not entirely straightforward because boosting "skews" the distribution of examples; this has the undesirable effects of both increasing the effective malicious noise rate, and causing the distribution to no longer be isotropic log-concave.  However, by using a "smooth" boosting algorithm (Servedio, 2003) that skews the distribution as little as possible, we are able to control these undesirable effects and make the analysis go through. (The extra factor of ε in the bound of Theorem 2 compared with Theorem 1 comes from the fact that the boosting algorithm constructs “1/ε-skewed” distributions.) We note that our approach of using smooth boosting is reminiscent of earlier work (Servedio, 2002, 2003), but the current algorithm goes well beyond that. Servedio (2002) did not consider a noisy scenario, and Servedio (2003) only considered the averaging algorithm without any outlier removal as the weak learner (and thus could only handle quite low rates of malicious noise in our isotropic log-concave setting). Tolerating adversarial label noise. Finally, our results for learning under isotropic log-concave distributions with adversarial label noise are obtained using a similar approach. The algorithm here is in fact simpler than the malicious noise algorithm: since the adversarial label noise model does not allow the adversary to alter the distribution of the examples in R n , we can dispense with the outlier removal and simply use smooth boosting with the averaging algorithm as the weak learner. (This is why we get a slightly better quantitative bound in Theorem 3 than Theorem 2). Organization. For completeness we review the precise definitions of isotropic log-concave dis- tributions and the various learning models in Section 2. We present the simpler and more easily understood uniform distribution analysis in Section 3. We extend the algorithm and analysis to isotropic log-concave distributions in Section 4. Learning with adversarial label noise is treated in Section 5. We conclude in Section 6.
2. Definitions and Preliminaries
2.1  Learning with Malicious Noise
Given a probability distribution D over R n , and a target function f : R n → {−1,1}, we define the oracle EX n ( f , D ) as follows: ● with probability 1 − η the oracle draws x according to D , and outputs ( x, f ( x )), and ● with probability η the oracle outputs an arbitrary ( x, y ) pair. This "noisy" example can be thought of as being generated adversarially and can depend on the state of the learning algo- rithm and previous draws from the oracle. Given a data set drawn from EX n ( f, D ), we often refer to the examples ( x, f ( x )) (that came from D ) as "clean" examples and the remaining examples ( x, y ) as "dirty" examples. For a set S of probability distributions and a set F of possible target functions, we say that a learning algorithm A learns F to accuracy 1 − ε with respect to S in the presence of malicious noise at a rate η if the following holds:  for any f ∈ F , and D ∈ S , given access to EX η ( f, D ), with probability at least 1/2, the output hypothesis h generated by A satisfies Prx~D[h(x) ≠ f(x)] ≤ ϵ. (The probability of success may be amplified arbitrarily close to 1 using standard techniques (Haussler et al., 1991).) Since scaling x by a positive constant does not affect its classification by a linear classifier, drawing examples uniformly from the unit ball is equivalent to drawing them uniformly from the surface S n−1 of the unit sphere. When this is the distribution, we may also assume w.l.o.g. that even noisy examples ( x, y ) have x ∈ S n−1 − this is simply because a learning algorithm can trivially identify and ignore any noisy example ( x, y ) that has ‖ x ‖̸≠ 1.
2.2  Log-concave distributions
A probability distribution over R n is said to be log-concave if its density function is exp( − ψ ( x )) for a convex function ψ . A probability distribution over R n is isotropic if the mean of the distribution is 0 and the co- variance matrix is the identity, i.e., E[ x i x j ] = 1 for i = j and 0 otherwise. Isotropic log-concave (henceforth abbreviated i.l.c.) distributions are a fairly broad class of distributions. It is well known that any distribution induced by taking a uniform distribution over an arbitrary convex set and applying a suitable linear transformation to make it isotropic is then isotropic and log-concave. For an excellent treatment on basic properties of log-concave distribu- tions, see Lovász and Vempala (2007). We will use the following facts: Lemma 4 ((Lovász and Vempala, 2007))  Let D be an isotropic log-concave distribution over R n and a ∈ S n−1 any direction. Then for x drawn according to D, the distribution of a · x is an isotropic log-concave distribution over R. Lemma 5 ((Lovász and Vempala, 2007))  Any isotropic log-concave distribution D over R n has light tails, Pr [||x|| > β√n] < e−β+1 If n = 1, the density of D is bounded:
3. The uniform distribution and malicious noise
In this section we prove Theorem 1. As described above, our algorithm first does outlier removal using PCA and then applies the "averaging algorithm." We may assume throughout that the noise rate η is smaller than some absolute constant, and that the dimension n is larger than some absolute constant.
3.1  The Algorithm: Removing Outliers and Averaging
Consider the following Algorithm Amu: Algorithm Amu 1. Draw a sample S of m = poly( n / ε ) many examples from the malicious oracle. 2. Identify the direction w ∈ S n−1 that maximizes If σ 2  <  10m log m  then go to Step 4 otherwise go to Step 3. 3. Remove from S every example that has (w · x) 2 ≥ 10 log m . Go to Step 2. 4. For the examples S that remain let ν = 151 ∑ (x,y)∈ S U × and output the linear classifier h ν defined by h v (x) = sgn(v · x). We first observe that Step 2 can be carried out in polynomial time: Lemma 6 There is a polynomial-time algorithm that, given a finite collection S of points in R n , outputs w ∈ Sn−1 that maximizes Ex∈ S (w · x)². Proof. By applying Lagrange multipliers, we can see that the optimal w is an eigenvector of A = E XES XXT . Further, if λ is the eigenvalue of w, then ∑ xES (w · x) 2 = wTAw = wT (λw) = λ. The eigenvector w with the largest eigenvalue can be found in polynomial time (see, e.g., (Jolliffe, 2002)). Before embarking on the analysis we establish a terminological convention. Much of our analy- sis deals with high-probability statements over the draw of the m -element sample S ; it is straightfor- ward but quite cumbersome to explicitly keep track of all of the failure probabilities. Thus we write "with high probability" (or "w.h.p.") in various places below as a shorthand for "with probability at least 1 − 1/poly( n/ε )." The interested reader can easily verify that an appropriate poly( n/ε ) choice of m makes all the failure probabilities small enough so that the entire algorithm succeeds with probability at least 1/2 as required.
3.2  Properties of the clean examples
In this subsection we establish properties of the clean examples that were sampled in Step 1 of Amu- The first says that no direction has much more variance than the expected variance of 1/n: Lemma 7  W.h.p. over a random draw of ℓ clean examples Sclean, Proof. The proof uses standard tools from VC theory and is in Appendix A. The next lemma says that in fact no direction has too many clean examples lying far out in that direction: clean examples Lemma 8  For any β > 0 and κ > 1, if Sclean is a random set of ℓ ≥ then w.h.p. we have Proof. In Appendix B.
3.3  What is removed
In this section, we provide bounds on the number of clean and dirty examples removed in Step 3. The first bound is a Corollary of Lemma 8. Corollary 9  W.h.p. over the random draw of the m-element sample S, the number of clean exam- ples removed during any one execution of Step 3 in Amu is at most 6n log m. Proof. Since the noise rate η is sufficiently small, w.h.p. the number ℓ of clean examples is at least (say) m/2. We would like to apply Lemma 8 with κ = 5ℓ 4 n log ℓ and β we may do this because we have for n sufficiently large. Since clean points are only removed if they have (a · x) ² > β 2 , Lemma 8 gives us that the number of clean points removed is at most
■ The counterpart to Corollary 9 is the following lemma. It tells us that if examples are removed in Step 3, then there must be many dirty examples removed. It exploits the fact that Lemma 7 bounds the variance in all directions a, so that it can be reused to reason about what happens in different executions of step 3. Lemma 10  W.h.p. over the random draw of S, whenever Amu executes step 3, it removes at least 4mlogm  noisy examples from Sdirty, the set of dirty examples in S. Proof.  As stated earlier we may assume that η ≤ 1/4.  This implies that w.h.p. the fraction介of noisy examples in the initial set S is at most 1/2. Finally, Lemma 7 implies that m = Ω( n 3 ) suffices for it to be the case that w.h.p., for all a ∈ S n− 1 , for the original multiset Sclean of clean examples drawn in step 1, we have
We shall say that a random sample S that satisfies all these requirements is "reasonable". We will show that for any reasonable dataset, the number of noisy examples removed during the execution of step 3 of Amu is at least  4m log m If we remove examples using direction w then it means ∑ (x,y)∈ S (w · x) 2 ≥ 10m log m . Since S is reasonable, by (1) the contribution to the sum from the clean examples that survived to the current stage is at most 2m/n so we must have
Let us decompose Sdirty into N ∪ F where N ( ' near ' ) consists of those points x s.t. (w · x) 2 ≤ 10 log( m ) /n and F ( " far " ) is the remaining points for which ( w · x ) 2 > 10 log( m ) /n . Since | Sdirty | ≤ îîm , (any dirty examples removed in earlier rounds will only reduce the size of Sdirty) we have
and so
(the last line used the fact that ˆ ı ⁄ < 1/2). Since the points in F are removed in Step 3, the lemma is proved. ■
3.4  Exploiting limited variance in any direction
In this section, we show that if all directional variances are small, then the algorithm's final hypoth- esis will have high accuracy. We first recall a simple lemma which shows that a sample of "clean" examples results in a high-accuracy hypothesis for the averaging algorithm: Lemma 11 ((Servedio, 2001))  Suppose x 1 , …, x m are chosen uniformly at random from S n−1 , and a target weight vector u ∈ S n − 1 produces labels y 1 = sign(u · x 1 ), …, Y m = sign(u · x m ). Let =1 YtXt. Then w.h.p. u · v = Ω( f n ), while ||v − (u · v)u|| = O( √ log(n)/m). Now we can state Lemma 12. Lemma 12  Let S =  Sclean U Sdirty be the sample of m examples drawn from the noisy oracle EXn(f,U). Let be those clean examples that were never removed during step 3 of Amus be those dirty examples that were never removed during step 3 of Amu, , i.e., the fraction of dirty examples among the examples that survive step 3, the ratio of the number of clean points that were erroneously removed to size of the final surviving data set. clean ∪ S ′ dirty ·  Suppose that | S ′ | ≥ m/2 (i.e., fewer than half the total points were removed) and that, for every direction w ∈ Sn−1 we have Then w.h.p. over the draw of S, the halfspace with normal vector rate
Proof. The claimed bound is trivial unless η ′ ≤ σ (1) / log m and α ≤ σ (1) / √ π , so we shall freely use these bounds in what follows. Let u be the unit length normal vector for the target halfspace. Let Vclean be the average of all the clean examples, v dirty be the average of the dirty (noisy) examples that were not deleted (i.e., the examples in S ′ dirty ), and ∨ del be the average of the clean examples that were deleted. Then
Let us begin by exploiting the bound on the variance in every direction to bound the length of V'dirty. For any w ∈ S n−1 we know that
since S ′ dirty ⊆ S ′ . Since | S ′ dirty | ≤ η ′ m , the fact that || r || 1 ≤ √ k || r || 2 for any vector r ∈ R k gives
Taking w to be the unit vector in the direction of V dirty , we have || V
v and u, in particular,
where we have used the triangle inequality and the fact that α , η are "small." Lemma 11 lets us bound the first term in the sum by O( \ /log( n ) /m ), and the fact that v del is an average of vectors of length 1 lets us bound the third by α . For the second term, Equation (3) gives us
η′ + α)(u · Vclean) + η′ u · V′ dirty Similar to the above analysis, we again use Lemma 11 (but now the lower bound u · ν ≥ Ω(1/ √ n )), Equation (3), and the fact that ||v del|| ≤ 1. Since α and η ′ are "small," we get that there is an absolute constant c such that u · v ≥ c/√π − √ 20η ′ log(m)/π − α . Combining this with (5) and (4), we get

3.5  Proof of Theorem 1
By Corollary 9, w.h.p. each outlier removal stage removes at most 6n log m clean points. Since, by Lemma 10, each outlier removal stage removes at least 4m log m noisy examples, there must be at most O(n/(log m)) such stages.  Consequently the total number of clean examples removed across all stages is O ( n 2 ). Since w.h.p. the initial number of clean examples is at least 3m/4, this means that the final data set (on which the averaging algorithm is run) contains at least 3m/4 − O(n 2 ) clean examples, and hence at least 3m/4 − O(n 2 ) examples in total. The condition m ≫ n ² means that the number of surviving examples will be at least m/2. Consequently the value of α from Lemma 12 after the final outlier removal stage (the ratio of the total number of clean examples deleted, to the total number of surviving examples) is at most O( n 2 ). The standard Hoeffding bound implies that w.h.p. the actual fraction of noisy examples in the original sample S is at most η + √ O (log m)/m. It is easy to see that w.h.p. the fraction of dirty examples does not increase (since each stage of outlier removal removes more dirty points than clean points, for a suitably large poly( n / ε ) value of m ), and thus the fraction η ′ of dirty examples among the remaining examples after the final outlier removal stage is at most η + √ O (log m) /m. Applying Lemma 12, for a suitably large value m = poly( n/e ), we obtain Pr[hv ≠ f] ≤ O ( √ η log m ) . Rearranging this bound, we can learn to accuracy ε even for η = Ω( ε 2 / log( n / ε )). This completes the proof of the theorem.
4. Isotropic log-concave distributions and malicious noise
Our algorithm A mlc that works for arbitrary isotropic log-concave distributions uses smooth boost- ing.
4.1  Smooth Boosting
A boosting algorithm uses a subroutine, called a weak learner , that is only guaranteed to output hypotheses with a non-negligible advantage over random guessing. 2  The boosting algorithm that we consider uses a confidence-rated weak learner (Schapire and Singer, 1999), which predicts {−1,1}. labels using continuous values in [−1,1]. Formally, the advantage of a hypothesis λ ′ with respect to a distribution D ′ is defined to be E τ~D ′ [ h ′ ( x ) f ( x )] , where f is the target function. For the purposes of this paper, a boosting algorithm makes use of the weak learner, an example oracle (possibly corrupted with noise), a desired accuracy ε , and a bound γ on the advantage of the hypothesis output by the weak learner. A boosting algorithm that is trying to learn an unknown target function f with respect to some distribution D repeatedly simulates a (possibly noisy) example oracle for f with respect to some other distribution D ′ and calls a subroutine Aweak with respect to this oracle, receiving a weak hypothesis , which maps R n to the continuous interval [−1, 1]. After repeating this for some number of stages, the boosting algorithm combines the weak hypotheses generated during its various calls to the weak learner into a final aggregate hypothesis which it outputs. Let D , D ′ be two distributions over R n . We say that D ′ is (1 /ε)-smooth with respect to D if D'(E) ≤ (1/ε)D(E) for all events E . The following lemma from (Servedio, 2003) (similar results can be readily found elsewhere, see, e.g., (Gavinsky, 2003)) identifies the properties that we need from a boosting algorithm for our analysis. Lemma 13 ((Servedio, 2003))  There is a boosting algorithm B and a polynomial p such that, for any ε, γ > 0, the following properties hold. When learning a target function f using EX n ( f, D), we have:  (a) If each call to Aweak takes time t, then B takes time p(t, 1/ γ, 1/ ε ).  (b) The weak learner is always called with an oracle EX η (f,D ′ ) where D ′ is (1 ⁄ c)-smooth with respect to D and η ′ ≤ η ⁄ ε. (c) Suppose that for each distribution EX η ′ ( f , D ′ ) passed to Aweak by B, the output of Aweak has advantage γ. Then the final output h of B satisfies Pr x∈𝑠𝑠𝑗 [h(x)̸= f(x)] ≤ ε.
4.2  The Algorithm
Our algorithm for learning under isotropic log-concave distributions with malicious noise, Algo- rithm A mlc , applies the smooth booster from Lemma 13 with the following weak learner, which we call Algorithm A mlcw. (The value c 0 is an absolute constant that will emerge from our analysis.)
4.3  The key claim: the weak learner is effective
Our main task is to analyze the weak learner. Given the following Lemma, Theorem 2 will be an immediate consequence of Lemma 13. Lemma 14 Suppose Algorithm Amlcw is run using EX η ( f , D ′ ) where f is an origin-centered half- space, D' is (1/c)-smooth w.r.t.  an isotropic log-concave distribution D, η ′ ≤ η ⁄ ε, and η Ω(ε 3 / log 2 (n /ε)). Then w.h.p. the hypothesis h returned by Amlcw has advantage Ω ( Before proving Lemma 14, we need to prove some uniformity results on non-noisy examples drawn from an isotropic, log-concave distribution. This will enable us to use outlier removal and averaging to find a weak learner.
4.4  Lemmas in support of Lemma 14
In this section, let us consider a single call to the weak learner with an oracle E X π ( f, D ′ ) where D ′ is (1/ c )-smooth with respect to an isotropic log-concave distribution D and η / ≤ η / c . Our analysis will follow the same basic steps as Section 3. A preliminary observation is that w.h.p. all clean examples drawn in Step 1 of Algorithm Amlcw have ||x|| ≤ √3n log m ; indeed, for any given draw of x from D ′ , the probability that ||x|| > √3n log m is at most ε m 3 by Lemma 5 together with the fact that D ′ is 1 /ε-smooth with respect to an i.l.c. distribution. Therefore, w.h.p., only noisy examples are removed in Step 2 of the algorithm, and we shall assume that the distributions D and D ′ are in fact supported entirely on {x : ||x|| ≤ √3n log m} . This assumption affects us in two ways: first, it costs us an additional ε ε π x  in the failure probability analysis below (which is not a problem and is in fact swallowed up by our "w.h.p." notation). Second, it means that the overall 1 − ε accuracy bound we establish for the entire learning algorithm may be slightly worse than the true value. This is because our final hypothesis may always be wrong on the examples x that have ‖×‖ > √3n log m and are ignored in our analysis; however such examples have probability mass at most  m 3 under the isotropic log-concave distribution D (again by Lemma 5), and thus the additional accuracy cost is at most , , , Since ε ≫ , , , this does not affect the overall correctness of our analysis. Note that a consequence of this assumption is that we can just take h(x) =    v x The remarks about high-probability statements and failure probabilities from Section 3.1 ap- ply here as well, and as in Section 3 we write "w.h.p." as shorthand for "with probability 1 – 1/poly(n/e)." We first show that the variance of D ′ in every direction is not too large: Lemma 15  For any a ∈ S n−1 we have E x~D r [(a · x) 2 ] = O (log 2 (1/ε)). Proof. For x chosen according to D , the distribution of a · x is a unit variance log-concave distribu- tion by Lemma 4. Thus, for any positive integer k , where the first inequality in the last line uses Lemmas 4 and 5. Setting k = ln(1/ε) completes the proof. The following anticoncentration bound will be useful for proving that clean examples drawn from D ′ tend to be classified correctly with a large margin. Lemma 16  Let u ∈ Sn−1. Then Proof. Clearly
13 But by Lemma 5, The next two lemmas are isotropic log-concave analogues of the uniform distribution Lemmas 7 and 8 respectively. The first one says that w.h.p. no direction a has much more variance than the expected variance in any direction: Lemma 17  W.h.p. over a random draw of ℓ clean examples Sclean from D ′ , we have Proof. By Lemma 15, for any a ∈ Sn−1
Since as remarked earlier we may assume D ′ is supported on {x : ||x|| In log m}, we may apply Lemmas 25 and 27 (see Appendix A) with functions fa defined by completes the proof. The second lemma says that for a sufficiently large clean data set, w.h.p. no direction has too many examples lying too far out in that direction: Lemma 18 For any β > 0 and κ > 1, if Sclean is a set of l examples drawn from D', then w.h.p. we k
Proof. Lemma 5 implies that for the original isotropic log-concave distribution D , we have Since D ′ is (1 ⁄ ε )-smooth with respect to D , this implies that
In the proof of Lemma 8, we observed that the VC-dimension of {{x : |a · x| > β}  :  a ∈ R n , β ∈ R} is O(n) , so applying Lemma 28 with (6) completes the proof of this lemma. ■ The following is an isotropic log-concave analogue of Corollary 9, establishing that not too many clean examples are removed in the outlier removal step: Corollary 19 W.h.p. over the random draw of the m-element sample S from EX η ( f,D'), the number of clean examples removed during any one execution of the outlier removal step (final substep of Step 2) in Algorithm Amlcw is at most 6mc3/n 4 . Proof. Since the true noise rate η is assumed sufficiently small, the value η ′ ≤ η / ε is at most ε /4, and thus w.h.p. the number ℓ of clean examples in S is at least (say) m/2. We would like to apply Lemma 18 with κ = ( n / ε ) co− 4 and β = c 0 log( n / ε ), and we may do this since we have
for a suitable fixed poly ( n / ε ) choice of m . Since clean points are only removed if they have | a · x | ≥ β , Lemma 18 gives us that the number of clean points removed is at most The following lemma is an analogue of Lemma 10; it lower bounds the number of dirty examples that are removed in the outlier removal step. Lemma 20 W.h.p. over the random draw of S, any time Algorithm Amlcw executes the outlier removal step it removes at least  T(n) noisy examples. Proof. Since our ultimate goal is only to prove that the algorithm succeeds for some η which is o ( ε ), we may assume without loss of generality that the original noise rate η is less than ε /4. This means that η ′ < 1 /4, and consequently a Chernoff bound gives that w.h.p. the fraction γ ′ of noisy examples in S at the beginning of the weak learner's training is at most 1/2. And Lemma 17 implies that for a sufficiently large polynomial choice of m , we have that w.h.p. for all a ∈ S n − 1 , the following holds for all the clean examples in the data before any examples were removed:
where c is an absolute constant. We say that a random sample that meets all these requirements is "reasonable." We now set the constant c 0 that is used in the specification of Amlcw to be √ 2(c + 1). We will now show that, for any reasonable sample S , the number of noisy examples removed during the first execution of the outlier removal step of Amlcw is at least  m If we remove examples using direction w then it means ∑ x ∈ S ( W · x ) 2 ≥ c ∂ m log 2 ( n / ε ). Since S is reasonable, by (7) the contribution to the sum from the clean examples that have survived until this point is at most cm log 2 (1/ ε ) so we must have Let Sdirty = N ∪ F where N is the examples ( x, y ) for which x satisfies ( w · x ) 2 ≤ c 2 log 2 ( n/e ) and F is the other points. We have and so, since ||x|| ≤ √3n log m implies that (w · x) 2 ≤ 3n log m for all unit length w, we have O(n) where the next-to-last inequality uses η ′ ≤ 1 / 2 and c 0 = √ 2 (c + 1), and the final one uses m = O(poly( n/ε )). The points in F are precisely the ones that are removed, and thus the lemma is proved.
4.5  Proof of Lemma 14
We first note that Lemma 20 implies that w.h.p. the weak learner must terminate after at most O ( n ) iterations of outlier removal. Let u be the unit length normal vector of the separating halfspace for the target function f . Recall that we have assumed without loss of generality that ||x|| ≤ √3n log m for all x in the training set, so that ||v|| ≤ √3n log m , and thus the advantage of h with respect to D ′ can be expressed as
and so we shall work on lower bounding E x~D ′ [(v · x) As in the proof of Lemma 12, let ● Sclean be all of the clean examples in the initial sample S , and S clean be those that are not removed in any stage of outlier removal; ● S dirty be all of the dirty examples in the initial sample S , and S dirty be those that are not removed in any stage of outlier removal; , i.e., the noise rate among the examples that survive until the end of training clean US$ of the weak learner, and , the ratio of the number of clean points that were erroneously removed to the size of the final surviving data set. As before we write S ′ for S ′ lean ∪ S ′ dirty · Also as before, let V clean be the average of all the clean examples, V dirty be the average of the dirty (noisy) examples that were not deleted, and V del be the average of the clean examples that were deleted. Then arguing exactly as before, we have
The expectation of Vclean will play a special role in the analysis: Once again, we will demonstrate the limited effect of v dirty by bounding its length. This time, the outlier removal enforces the fact that, for any w ∈ S n− 1 , we have
Applying this for the unit vector w in the direction of V dirty as was done in Lemma 12, this implies Next, let us apply this to bound an expression that captures the average harm done by V dirty:
To show that Vclean plays a relatively large role, it is helpful to lower bound the length of Vclean's We do this by lower bounding the length of its projection onto the unit normal vector u of the target as follows:
by Lemma 16. Since u is unit length, this implies
Armed with this bound, we can now lower bound the benefit imparted by Vclean- Since E[(yx) · V* clean] In log m , 3n log m], a Hoeffding bound id (yx) · V clear implies that w.h.p.
Since the noise rate η ′ is at most η / ε and η certainly less than ε /4 as discussed above, another Hoeffding bound gives that w.h.p. | Sclean | is at least m /2; thus for a suitably large polynomial choice of m , using (11) we have
17 Now we are ready to put our bounds together and lower bound the advantage of v. We have
We bound each of the three contributions in turn. First, using 1 – η ′ ≥ 1/2 and (12), we have (1 − η′ + α)E[f(x)(vclean · x)] ≥ ∥ vclean||² Next, by (10), we have
Since we may assume that η ≤ c ′ ε 3 ′ log 2 ( n / ε ) for as small a fixed constant c ′ as we like (recall the overall bound of Theorem 2), we get
(for a suitably small constant choice of c ′ ), and this is less than Finally Corollary 19, together with the fact that there are at most O ( n ) iterations of outlier removal and the final surviving data set is of size at least m/4, gives us that α ≤ Oln in which (recalling that both Vde1 and all x in the support of D ′ have norm at most √ 3n log m ) means that | α E [ f (x)( vdel · x)]| = o ( ε ² ). Combining all these bounds, we get by (11). Together with (8), the proof of Lemma 14 is completed
5. Learning under isotropic log-concave distributions with adversarial label noise
5.1  The Model
We now define the model of learning with adversarial label noise under isotropic log-concave dis- tributions. In this model the learning algorithm has access to an oracle that provides independent random examples drawn according to a fixed distribution P on R n × {−1,1}, where ● the marginal distribution over R n is isotropic log-concave, and ●  there is a halfspace f such that Pr(x,y)~P[f(x) ≠ y] = η. The parameter η is the noise rate . As usual, the goal of the learner is to output a hypothesis h such that Pr(x,v)~D[h(x)̸= y] ≤ ε ; if an algorithm achieves this goal, we say it learns to accuracy 1 − ε in the presence of adversarial label noise at rate η .
5.2  The Algorithm
Like the algorithm Amlc considered in the last section, the algorithm Aalc studied in this section applies the smooth boosting algorithm of Lemma 13 to a weak learner that performs averaging. The weak learner Aalcw behaves as follows: Algorithm Aalcw by the boosting algorithm). 2. Remove all examples ( x, y ) such that ||×|| > √3n log m from S . ST L(x,y)ES Yx.  Return the confidence-rated classifier h defined by h(x) if | v · x | ≤ 3n log m , and h ( x ) = sgn( v · x ) otherwise.
5.3  Claim about the weak learner
As in the previous section, the heart of our analysis will be to analyze the weak learner. We omit discussing the application of the smooth boosting algorithm here, as it is nearly identical to Section 4. Lemma 21 Suppose Algorithm Aalcw is run using P ′ as the source of labeled examples, where P ′ is a distribution that is (1/c)-smooth with respect to a joint distribution P on R n × {−1,1} whose marginal D' on R n is isotropic and log-concave. Further, assume there exists a linear threshold function f such that Pr(x,y)~p'[f(x) ≠ y] ≤ η/ε and η ≤ Ω( Γο g(τηεη). Then with high probability, Aalcw outputs a hypothesis with advantage Ω( n log(n/c)
5.4  Lemmas in support of Lemma 21
During this section, let us focus our attention on a single call to the weak learner. Let P ′ be a distribution as in Lemma 21 and let D ′ be the marginal on R n . We observe that since P ′ is (1 / ε )- smooth with respect to P , the marginal D ′ of P ′ is (1 / ε )-smooth with respect to the marginal D of P. As in Section 4, we may assume that the support of D ′ lies entirely on x such that ||x|| ≤ ✓3n log m (this negligibly affects the final bounds obtained in our analyses). The following technical lemma will be used to limit the extent to which the distribution P ′ can concentrate a lot of noise in one direction. Lemma 22  Let E be any event with positive probability under D ′ , and let κ = D ′ ( E ). For any unit length a ∈ R n , E x ~ D ′ [|a · x| | E] = O (log ) ∈ ) · Proof. Let β be such that Pr x ~ D ′ [|a · x | > β] = κ . By Lemmas 4 and 5, together with the fact that D ′ is (1/ε) smooth with respect to D , we have which implies β ≤ 1 + ln ( ≒ ) Let F be the event that | a · x | > β . We will show that E x ~ D ′ [|a · x | | E ] ≤ E x ~ D ′ [|a · x | | F ], and then bound E x~D ′ [|a · x | | F ]. If Pr [ ( E − F )∪ ( F − E )] = 0, then, obviously, E x~D ′ [|a · x | | E ] = E x~D'[|a · x| | F]. Suppose Pr[( E − F ) ∪ ( F − E )] > 0. Then
because for every x ∈ E − F and every x' ∈ F − E ,
But E x~D' [|a · x| | E ∩ F] Pr[ E ∩ F] + E x~D' [|a · x| | F − E ] Pr[ F − E ] = E x~D' [|a · x| | F], SO
Now, setting b = [β] , we have
since D'(F) = Θ(e− b /ε). Combining with (13) completes the proof.
5.5  Proof of Lemma 21
Fix some halfspace f such that Pr(x,y)~p[f(x) ≠ y] = η, and let u be the unit normal vector of its separating hyperplane. Let P ′ be the joint distribution given to Aalcw and let D ′ be its marginal on R n . As noted in the previous subsection, D ′ is (1 / c )-smooth with respect to the original marginal distribution D of P . First, we bound the advantage of the hypothesis h with respect to P ′ in terms of the tendency of h to agree with the best linear function f :
Furthermore, as we have assumed without loss of generality that ||x|| ≤ √3nlogm for all examples in the training set, and therefore that ||v|| ≤ √3n log m , we have
20

so we will work on bounding E x~D' [f(x)(x · v)]. Define P dirty analogously, and let D clean and D dirty be the corresponding marginals on R n . Let
Note that the linearity of expectation implies that
Equation (16) expresses E x~ D ′ [ f ( x )( x · v )], which is closely related to the advantage of h through (15) and (14), as a sum of independent random variables, one for each example. We will bound E x~D' [f (x)(x · v)] by bounding the expected effect of a random example on its value, and applying a Hoeffding bound. Let η ′ = P r (x,y)~p ′ [ f (x)̸= y ]. Since P ′ is 1 ⁄ ε -smooth with respect to P , we have η ′ ≤ η ⁄ ε . We can rearrange the effect of a random example as follows
Since
= η ′ E (x,y)~p′ [v*orrect ˙ ( f (x)x)|y̸= f (x)] + (1 − η ′ ) E (x,y)~p′ [v*orrect ˙ ( f (x)x)|y = f (x)], by replacing the first two terms of (17) with E(x,y)~P'[V*orrect · (f(x)x)], we get
Twice applying the linearity of expectation, we get
The last line follows from the fact that q 2 - - qr ≥ (q 2 − r 2 )/2 for all real q , r . So now our goals are a lower bound on || V correct || and an upper bound on || V dirty We can lower bound ‖V correct‖ essentially the same way we did before, by lower bounding its projection onto the “target” normal vector u:
by Lemma 16. We upper bound by Lemma 22. Thus ||V dirty|| ≤ O (lo Combining this with (18) and (16) we have that if for a suitably small constant c , then E x~D ′ [f(x)(x · v)] is a sum of m i.i.d. random variables, each with mean at least Ω( ε 2 ), and coming from an interval of length O ( n log m ). Applying the standard Hoeffding bound, polynomially many examples suffice for E x~D ′ [f(x)(x · v)] ≥ Ω(e 2 ). Combining with (15) and (14) completes the proof.
6. Conclusion
Our algorithms use boosting together with a confidence-rated weak learner that perform a simple averaging of labeled examples. As shown in earlier work (Servedio, 2002, 2003) there are close connections between such an approach and the Perceptron algorithm. It seems likely that the Per- ceptron could be used as an alternative to boosting and averaging in our algorithms; it would be interesting to see if a Perceptron-based approach has any theoretical or empirical advantages over the algorithms we give in this paper. More generally, there are relatively few algorithms for learning interesting classes of functions in the presence of malicious noise.  We hope that our results will help lead to the development of more efficient algorithms for this challenging noise model. As a challenge for future work, we pose the following question: do there exist computationally efficient algorithms for learning halfspaces under arbitrary distributions in the presence of mali- cious noise?  As of now no better results are known for this problem than the generic conversions of (Kearns and Li, 1993), which can be applied to any concept class. We feel that even a small im- provement in the malicious noise rate that can be handled for halfspaces would be a very interesting result.
Acknowledgement
We are grateful to the anonymous reviewers for their comments. S. Arora, L. Babai, J. Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations.  Proceedings of the 34th Annual Symposium on Foundations of Computer Science , pages 724–733, 1993. A. Blum, A. Frieze, R. Kannan, and S. Vempala.  A polynomial time algorithm for learning noisy linear threshold functions. Algorithmica , 22(1/2):35–52, 1997. A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Learnability and the Vapnik- Chervonenkis dimension. Journal of the ACM , 36(4):929–965, 1989. S. C. Brubaker.  Extensions of Principle Components Analysis .  PhD thesis, Georgia Institute of Technology, 2009. N. H. Bshouty, Y. Li, and P. M. Long. Using the doubling dimension to analyze the generalization of learning algorithms. Journal of Computer & System Sciences , 75(6):323–335, 2009. J. Dunagan and S. Vempala.  Optimal outlier removal in high-dimensional spaces.  J. Computer & System Sciences , 68(2):335–373, 2004. V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami.  New results for learning noisy parities and halfspaces. In Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 563–576, 2006. Yoav Freund and Robert E. Schapire.  Large margin classification using the perceptron algorithm. Machine Learning, 37(3):277–296, 1999. Dmitry Gavinsky. Optimally-smooth adaptive boosting and application to agnostic learning. Journal of Machine Learning Research , 4:101–117, 2003. V. Guruswami and P. Raghavendra.  Hardness of learning halfspaces with noise.  In Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 543–552. IEEE Computer Society, 2006. D. Haussler, M. Kearns, N. Littlestone, and M. Warmuth.  Equivalence of models for polynomial learnability. Information and Computation , 95(2):129–161, 1991. I.T. Jolliffe.  Principal Component Analysis .  Springer Series in Statistics, 2002. A. Kalai, A. Klivans, Y. Mansour, and R. Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 37(6):1777–1805, 2008. M. Kearns and M. Li. Learning in the presence of malicious errors. SIAM Journal on Computing , 22(4):807–837, 1993. M. Kearns, R. Schapire, and L. Sellie. Toward Efficient Agnostic Learning. Machine Learning , 17 (2/3):115–141, 1994. A. Klivans and A. Sherstov.  Cryptographic hardness for learning intersections of halfspaces.  In Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS), pages 553–562, 2006. N. Littlestone. Learning quickly when irrelevant attributes abound: a new linear-threshold algo- rithm. Machine Learning, 2:285–318, 1987. N. Littlestone. Redundant noisy attributes, attribute errors, and linear-threshold learning using Win- now. In Proceedings of the Fourth Annual Workshop on Computational Learning Theory , pages 147–156, 1991. L. Lovász and S. Vempala. The geometry of logconcave functions and sampling algorithms. Ran- dom Structures and Algorithms , 30(3):307–358, 2007. W. Maass and G. Turan.  How fast can a threshold gate learn?  In Computational Learning Theory and Natural Learning Systems: Volume I: Constraints and Prospects , pages 381–414. MIT Press, 1994. Y. Mansour and M. Parnas. Learning conjunctions with noise under product distributions. Informa- tion Processing Letters , 68(4):189–196, 1998. A. Novikoff. On convergence proofs on perceptrons. In Proceedings of the Symposium on Mathe- matical Theory of Automata , volume XII, pages 615–622, 1962. D. Pollard. Convergence of Stochastic Processes. Springer Verlag, 1984. F. Rosenblatt. The Perceptron: a probabilistic model for information storage and organization in the brain. Psychological Review , 65:386–407, 1958. R. Schapire and Y. Singer. Improved boosting algorithms using confidence-rated predictions. Ma- chine Learning, 37:297–336, 1999. R. Servedio. Efficient Algorithms in Computational Learning Theory . PhD thesis, Harvard Univer- sity, 2001. R. Servedio. PAC analogues of Perceptron and Winnow via boosting the margin. Machine Learning , 47(2/3):133–151, 2002. R. Servedio.  Smooth boosting and learning with malicious noise.  Journal of Machine Learning Research , 4:633–648, 2003. J. Shawe-Taylor and N. Cristianini. An introduction to support vector machines . Cambridge Uni- versity Press, 2000. M. Talagrand.  Sharper bounds for Gaussian and empirical processes.  Annals of Probability , 22: 28–76, 1994. L. Valiant. Learning disjunctions of conjunctions. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence , pages 560–566, 1985. H. Xu, C. Caramanis, and S. Mannor. Principal component analysis with contaminated data: The high dimensional case. Journal of Machine Learning Research , 2009. To appear. Let us start with a couple of definitions and a couple of bounds from the literature. Definition 23 (VC-dimension) A set F of {−1,1}-valued functions defined on a common domain X shatters x 1 , …, x d if every sequence y 1 , …, y d ∈ {−1, 1} of function values has a function f such that f ( x 1 ) = Y 1 , …, f ( x d ) = Y d . The VC-dimension of F is the size of the largest set shattered by F. Definition 24 (pseudo-dimension)  For a set F of real-valued functions defined on a common do- main X , the pseudo-dimension of F is the VC-dimension of {sign( f ( ) − θ) : f ∈ F,θ ∈ R}. Lemma 25 ((Pollard, 1984; Talagrand, 1994))  Let F be a set of real-valued functions defined on a common domain X taking values in [0,1], and let d be the pseudo-dimension of F . Let D be a probability distribution over X . Then if x 1 , …, x m are obtained by drawing m times independently according to D, for any δ > 0,
where c > 0 is an absolute constant. Lemma 26 (see Blumer et al. (1989))  The VC-dimension of unions of two halfspaces is O(n). Now, let us bound the pseudo-dimension of the class of functions that we need. Lemma 27  Let F n consist of the functions  from R n to R which can be defined by f (x) = (a · x) 2 for some a ∈ R n . The pseudo-dimension of F n is at most O(n). Proof. According to the definition, the pseudo dimension of F n is the VC-dimension of the set G n of {−1,1}-valued functions ga,θ defined by ga,θ(x) = sign((a · x)² − θ). Each ga,θ is equivalent to an OR of two halfspaces: Thus the VC-dimension of G n is at most the VC-dimension of the class of all ORs of two halfspaces. Applying Lemma 26 completes the proof. ■ Applying Lemmas 25 and 27, we obtain Lemma 7. We will use the following, which strengthens bounds like Lemma 25 when the expectations being estimated are small. It differs from most bounds of this type by providing an especially strong bound on the probability that the estimates are much larger than the true expectations. Lemma 28 ((Bshouty et al., 2009))  Suppose F is a set of {0,1}-valued functions with a common domain X . Let d be the VC-dimension of F . Let D be a probability distribution over X . Choose α > 0 and K ≥ 4. Then if
where c is an absolute constant, then
m ∑ i=1 f(u i ) where Ëu(ƒ) = To prove Lemma 8, we first use the fact that, for any fixed a ∈ S n− 1 and β > 0, it is known (see (Kalai et al., 2008)) that
Further, as in the proof of Lemma 7, we have that |a · x | > β so that the set of events whose probabilities we need to estimate is contained in the set of unions of pairs of halfspaces. Applying Lemma 26 and Lemma 28 completes the proof.