Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise

Abstract

We give a computationally-efficient PAC active learning algorithm for $d$-dimensional homogeneous halfspaces that can tolerate Massart noise (Massart and Nédélec, 2006) and Tsybakov noise (Tsybakov, 2004). Specialized to the $\eta$-Massart noise setting, our algorithm achieves an information-theoretically near-optimal label complexity of $\tilde{O}\left(\frac{d}{(1-2\eta {)}^2}\mathrm{polylog}(\frac{1}{\epsilon })\right)$ under a wide range of unlabeled data distributions (specifically, the family of "structured distributions" defined in Diakonikolas et al. (2020)). Under the more challenging Tsybakov noise condition, we identify two subfamilies of noise conditions, under which our efficient algorithm provides label complexity guarantees strictly lower than passive learning algorithms.

arXiv comment32 pages; COLT 2021

References in corpus (13)

• Risk bounds for statistical learning
• Agnostic Active Learning Without Constraints
• Active Learning for Cost-Sensitive Classification
• Beyond Disagreement-based Agnostic Active Learning
• Distribution-Independent PAC Learning of Halfspaces with Massart Noise
• Noise-adaptive Margin-based Active Learning and Lower Bounds under Tsybakov Noise Condition
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability
• Sample and Computationally Efficient Learning Algorithms under S-Concave Distributions
• Learning Halfspaces with Tsybakov Noise
• Learning Halfspaces with Massart Noise Under Structured Distributions
• Efficient Learning of Linear Separators under Bounded Noise