#### Distribution-Independent PAC Learning of Halfspaces with Massart Noise

Part of Advances in Neural Information Processing Systems 32 (NeurIPS 2019)

#### Authors

*Ilias Diakonikolas, Themis Gouleakis, Christos Tzamos*

#### Abstract

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$. The goal is to find
a hypothesis $h$ that minimizes the misclassification error $\pr_{(\bx, y) \sim \D} \left[ h(\bx) \neq y \right]$.
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.