Learning Halfspaces with Massart Noise Under Structured Distributions

Understand

We study the problem of learning halfspaces with Massart noise in the distribution-specific PAC model.

• We give the first computationally efficient algorithm for this problem with respect to a broad family of distributions, including log-concave distributions.
• This resolves an open question posed in a number of prior works.
• Our approach is extremely simple: We identify a smooth {\em non-convex} surrogate loss with the property that any approximate stationary point of this loss defines a halfspace that is close to the target halfspace.