Learning Halfspaces with Massart Noise Under Structured Distributions

2020/02/13 by Ilias Diakonikolas, Vasilis Kontonis, Diakonikolas, Ilias +5 · 4 citations
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Statistical Methods and Inference #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2002.05632

openalex publication_date 2020/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• The perceptron: A probabilistic model for information storage and organization in the brain.
• Decision theoretic generalizations of the PAC model for neural net and other learning applications

Cited by

• Smoothed Agnostic Learning of Halfspaces over the Hypercube
• Personalized Prediction By Learning Halfspace Reference Classes Under Well-Behaved Distribution
• On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise
• The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination

Related

• Distribution-Independent PAC Learning of Halfspaces with Massart Noise
• Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
• Non-Convex SGD Learns Halfspaces with Adversarial Label Noise
• Learning General Halfspaces with General Massart Noise under the Gaussian Distribution
• Learning Halfspaces with Tsybakov Noise