We introduce a new approach for designing computationally efficient learning algorithms that are tolerant to noise. We demonstrate the effectiveness of our approach by designing algorithms with improved noise tolerance guarantees for learning linear separators. We consider the malicious noise model of Valiant and the adversarial label noise model of Kearns, Schapire, and Sellie. For malicious noise, where the adversary can corrupt an @math of fraction both the label part and the feature part, we provide a polynomial-time algorithm for learning linear separators in @math under the uniform distribution with near information-theoretic optimal noise tolerance of @math . We also get similar improvements for the adversarial label noise model. We obtain similar results for more general classes of distributions including isotropic log-concave distributions. In addition, our algorithms achieve a label complexity whose dependence on the error parameter @math 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, as well as the first analysis of active learning under the malicious noise model.
@cite_27 considered noise-tolerant learning of halfspaces under a more idealized noise model, known as the random noise model, in which the label of each example is flipped with a certain probability, independently of the feature vector. Some other, less closely related, work on efficient noise-tolerant learning of halfspaces includes @cite_0 @cite_27 @cite_37 @cite_9 @cite_11 @cite_6 @cite_19 @cite_42 .
@cite_37 @cite_9 @cite_42 @cite_6 @cite_0 @cite_19 @cite_27 @cite_11
2026103826 2065923584 2159376838 1591252468 2098278064 2143362693 1548189207
We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise. Learning of parities under the uniform distribution with random classification noise, also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding learning under the uniform distribution to learning of noisy parities. We show that under the uniform distribution, learning parities with adversarial classification noise reduces to learning parities with random classification noise. Together with the parity learning algorithm of [5], this gives the first nontrivial algorithm for learning parities with adversarial noise. We show that learning of DNF expressions reduces to learning noisy parities of just logarithmic number of variables. We show that learning of k-juntas reduces to learning noisy parities of k variables. These reductions work even in the presence of random classification noise in the original DNF or junta. We then consider the problem of learning halfspaces over Q ^n with adversarial noise or finding a halfspace that maximizes the agreement rate with a given set of examples. We prove an essentially optimal hardness factor of 2- , improving the factor of 85 84 - due to Bshouty and Burroughs [8]. Finally, we show that majorities of halfspaces are hard to PAC-learn using any representation, based on the cryptographic assumption underlying the Ajtai-Dwork cryptosystem. Learning an unknown halfspace (also called a perceptron) from labeled examples is one of the classic problems in machine learning. In the noise-free case, when a halfspace consistent with all the training examples exists, the problem can be solved in polynomial time using linear programming. However, under the promise that a halfspace consistent with a fraction @math of the examples exists (for some small constant @math ), it was not known how to efficiently find a halfspace that is correct on even 51 of the examples. Nor was a hardness result that ruled out getting agreement on more than 99.9 of the examples known. In this work, we close this gap in our understanding and prove that even a tiny amount of worst-case noise makes the problem of learning halfspaces intractable in a strong sense. Specifically, for arbitrary @math , we prove that given a set of examples-label pairs from the hypercube, a fraction @math of which can be explained by a halfspace, it is NP-hard to find a halfspace that correctly labels a fraction @math of the examples. The hardness result is tight since it is trivial to get agreement on @math the examples. In learning theory parlance, we prove that weak proper agnostic learning of halfspaces is hard. This settles a question that was raised by , in their work on learning halfspaces in the presence of random classification noise [Algorithmica, 22 (1998), pp. 35-52], and raised by authors of some more recent works as well. Along the way, we also obtain a strong hardness result for another basic computational problem: solving a linear system over the rationals. Given α, e, we study the time complexity required to improperly learn a halfs-pace with misclassification error rate of at most (1 + α) L*γ + e, where L*γ is the optimal γ-margin error rate. For α = 1 γ, polynomial time and sample complexity is achievable using the hinge-loss. For α = 0, Shalev- [2011] showed that poly(1 γ) time is impossible, while learning is possible in time exp(O(1 γ)). An immediate question, which this paper tackles, is what is achievable if α e (0, 1 γ). We derive positive results interpolating between the polynomial time for α = 1 γ and the exponential time for α = 0. In particular, we show that there are cases in which α = o(1 γ) but the problem is still solvable in polynomial time. Our results naturally extend to the adversarial online learning model and to the PAC learning with malicious noise model. Given some arbitrary distribution D over 0, 1 n and arbitrary target function c∗, the problem of agnostic learning of disjunctions is to achieve an error rate comparable to the error OPTdisj of the best disjunction with respect to (D, c∗). Achieving error O(n · OPTdisj) + ǫ is trivial, and Winnow [13] achieves error O(r ·OPTdisj) + ǫ, where r is the number of relevant variables in the best disjunction. In recent work, Peleg [14] shows how to achieve a bound of O( √ n ·OPTdisj)+ ǫ in polynomial time. In this paper we improve on Peleg’s bound, giving a polynomial-time algorithm achieving a bound of O(n ·OPTdisj) + ǫ for any constant α > 0. The heart of the algorithm is a method for weak-learning when OPTdisj = O(1 n), which can then be fed into existing agnostic boosting procedures to achieve the desired guarantee. We describe a simple algorithm that runs in time poly(n, 1 γ, 1 e) and learns an unknown n-dimensional γ-margin halfspace to accuracy 1 – e in the presence of malicious noise, when the noise rate is allowed to be as high as Θ(eγ√log(1 γ)). Previous efficient algorithms could only learn to accuracy e in the presence of malicious noise of rate at most Θ(eγ). Our algorithm does not work by optimizing a convex loss function. We show that no algorithm for learning γ-margin halfspaces that minimizes a convex proxy for misclassification error can tolerate malicious noise at a rate greater than Θ(eγ); this may partially explain why previous algorithms could not achieve the higher noise tolerance of our new algorithm. The authors consider the problem of learning a linear threshold function (a halfspace in n dimensions, also called a "perceptron"). Methods for solving this problem generally fall into two categories. In the absence of noise, this problem can be formulated as a linear program and solved in polynomial time with the ellipsoid algorithm (or interior point methods). On the other hand, simple greedy algorithms such as the perceptron algorithm seem to work well in practice and can be made noise tolerant; but, their running time depends on a separation parameter (which quantifies the amount of "wiggle room" available) and can be exponential in the description length of the input. They show how simple greedy methods can be used to find weak hypotheses (hypotheses that classify noticeably more than half of the examples) in polynomial time, without dependence on any separation parameter. This results in a polynomial-time algorithm for learning linear threshold functions in the PAC model in the presence of random classification noise. The algorithm is based on a new method for removing outliers in data. Specifically, for any set S of points in R sup n , each given to b bits of precision, they show that one can remove only a small fraction of S so that in the remaining set T, for every vector v, max sub x spl epsiv T (v spl middot x) sup 2 spl les poly(n,b)|T| sup -1 spl Sigma sub x spl epsiv T (v spl middot x) sup 2 . After removing these outliers, they are able to show that a modified version of the perceptron learning algorithm works in polynomial time, even in the presence of random classification noise. We describe a new boosting algorithm which generates only smooth distributions which do not assign too much weight to any single example. We show that this new boosting algorithm can be used to construct efficient PAC learning algorithms which tolerate relatively high rates of malicious noise. In particular, we use the new smooth boosting algorithm to construct malicious noise tolerant versions of the PAC-model p-norm linear threshold learning algorithms described by Servedio (2002). The bounds on sample complexity and malicious noise tolerance of these new PAC algorithms closely correspond to known bounds for the online p-norm algorithms of Grove, Littlestone and Schuurmans (1997) and Gentile and Littlestone (1999). As special cases of our new algorithms we obtain linear threshold learning algorithms which match the sample complexity and malicious noise tolerance of the online Perceptron and Winnow algorithms. Our analysis reveals an interesting connection between boosting and noise tolerance in the PAC setting.