The paper gives a PAC learning algorithm for the basic problem of halfspaces in a model of learning with noise. The algorithm uses ideas from previous related results in the simpler model of random classification noise, with important new ideas. Learning with noise is a basic topic in learning theory. It can be argued that the most studied models (random misclassification noise and malicious noise) are unrealistically benign (even though the related SQ model is very important) or malicious, and there is a great need for the study of more realistic models. The Massart noise model is a candidate for such a model.

This is a very strong paper that makes impressive progress on the long-standing open problem of efficiently PAC learning halfspaces under the Massart noise model. While resolving the problem would involve getting within epsilon of the optimal error, achieving eta epsilon is a breakthrough and likely will fuel future results in learning theory.

We study the problem of {\em distribution-independent} PAC learning of halfspaces in the presence of Massart noise. Specifically, we are given a set of labeled examples (\bx, y) drawn from a distribution \D on \R {d 1} such that the marginal distribution on the unlabeled points \bx is arbitrary and the labels y are generated by an unknown halfspace corrupted with Massart noise at noise rate \eta 1/2 . We give a \poly\left(d, 1/\eps\right) time algorithm for this problem with misclassification error \eta \eps . We also provide evidence that improving on the error guarantee of our algorithm might be computationally hard. Prior to our work, no efficient weak (distribution-independent) learner was known in this model, even for the class of disjunctions. The existence of such an algorithm for halfspaces (or even disjunctions) has been posed as an open question in various works, starting with Sloan (1988), Cohen (1997), and was most recently highlighted in Avrim Blum's FOCS 2003 tutorial.

We study the problem of {\em distribution-independent} PAC learning of halfspaces in the presence of Massart noise. Specifically, we are given a set of labeled examples $(\bx, y)$ drawn from a distribution $\D$ on $\R {d 1}$ such that the marginal distribution on the unlabeled points $\bx$ is arbitrary and the labels $y$ are generated by an unknown halfspace corrupted with Massart noise at noise rate $\eta 1/2$. We give a $\poly\left(d, 1/\eps\right)$ time algorithm for this problem with misclassification error $\eta \eps$. We also provide evidence that improving on the error guarantee of our algorithm might be computationally hard. Prior to our work, no efficient weak (distribution-independent) learner was known in this model, even for the class of disjunctions.