Learning Halfspaces with Massart Noise Under Structured Distributions
This solves a fundamental problem in robust machine learning for researchers and practitioners dealing with noisy data, though it is incremental in advancing prior theoretical work.
The paper tackles the problem of learning halfspaces with Massart noise under structured distributions, such as log-concave ones, by providing the first computationally efficient algorithm that resolves a long-standing open question.
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. Given this structural result, we can use SGD to solve the underlying learning problem.