Learning Halfspaces with Massart Noise Under Structured Distributions

02/13/2020
by   Ilias Diakonikolas, et al.
0

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 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. Given this structural result, we can use SGD to solve the underlying learning problem.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset