Learning Halfspaces with Massart Noise Under Structured Distributions

Abstract

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.

References in corpus (4)

• Risk bounds for statistical learning
• Revisiting Perceptron: Efficient and Label-Optimal Learning of Halfspaces
• The Complexity of Finding Stationary Points with Stochastic Gradient Descent
• Sample and Computationally Efficient Learning Algorithms under S-Concave Distributions

Cited by in corpus (3)

• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability
• On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise
• Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise