Distribution-Independent PAC Learning of Halfspaces with Massart Noise

Abstract

We study the problem of {\em distribution-independent} PAC learning of halfspaces in the presence of Massart noise. Specifically, we are given a set of labeled examples $(\mathbf{x},y)$ drawn from a distribution $\mathcal{D}$ on ${\mathbb{R}}^{d+1}$ such that the marginal distribution on the unlabeled points $\mathbf{x}$ is arbitrary and the labels $y$ are generated by an unknown halfspace corrupted with Massart noise at noise rate $\eta <1/2$. The goal is to find a hypothesis $h$ that minimizes the misclassification error ${\mathbf{Pr}}_{(\mathbf{x},y)\sim \mathcal{D}}\left[h(\mathbf{x})\ne y\right]$. We give a $\mathrm{poly}\left(d,1/\epsilon \right)$ time algorithm for this problem with misclassification error $\eta +\epsilon$. We also provide evidence that improving on the error guarantee of our algorithm might be computationally hard. Prior to our work, no efficient weak (distribution-independent) learner was known in this model, even for the class of disjunctions. The existence of such an algorithm for halfspaces (or even disjunctions) has been posed as an open question in various works, starting with Sloan (1988), Cohen (1997), and was most recently highlighted in Avrim Blum's FOCS 2003 tutorial.

References in corpus (3)

• Sever: A Robust Meta-Algorithm for Stochastic Optimization
• Revisiting Perceptron: Efficient and Label-Optimal Learning of Halfspaces
• Efficient Learning of Linear Separators under Bounded Noise

Cited by in corpus (13)

• Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime
• Efficient active learning of sparse halfspaces with arbitrary bounded noise
• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability
• Smoothed Analysis of Online and Differentially Private Learning
• Learnability with Indirect Supervision Signals
• Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance
• Self-Training of Halfspaces with Generalization Guarantees under Massart Mislabeling Noise Model
• Sample-Optimal PAC Learning of Halfspaces with Malicious Noise
• Robust Learning under Strong Noise via SQs
• Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise
• ReLU Regression with Massart Noise
• Robust testing of low-dimensional functions
• Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise