A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise

Understand

We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise.

• In the Tsybakov noise model, the label of every sample is independently flipped with an adversarially controlled probability that can be arbitrarily close to $1/2$ for a fraction of the samples.
• {\em We give the first polynomial-time algorithm for this fundamental learning problem.} Our algorithm learns the true halfspace within any desired accuracy $\epsilon$ and succeeds under a broad family of well-behaved distributions including log-concave distributions.
• Prior to our work, the only previous algorithm for this problem required quasi-polynomial runtime in $1/\epsilon$.