Agnostically Learning Halfspaces

We give a computationally efficient algorithm that learns (under distributional assumptions) a halfspace in the difficult agnostic framework of Kearns, Schapire, and Sellie [Mach. Learn., 17 (1994), pp. 115–141], where a learner is given access to a distribution on labelled examples but where the labelling may be arbitrary (similar to malicious noise). It constructs a hypothesis whose error rate on future examples is within an additive ε of the optimal halfspace, in time poly$(n)$ for any constant ε>0, for the uniform distribution over \-1,1\ⁿ or unit sphere in Rⁿ, as well as any log-concave distribution in Rⁿ. It also agnostically learns Boolean disjunctions in time 2Õ(√n) with respect to any distribution. Our algorithm, which performs L₁ polynomial regression, is a natural noise-tolerant arbitrary-distribution generalization of the well-known “low-degree” Fourier algorithm of Linial, Mansour, and Nisan. We observe that significant improvements on the running time of our algorithm would yield the fastest known algorithm for learning parity with noise, a challenging open problem in computational learning theory.