2017/02/18 by Songbai Yan, Chicheng Zhang, Yan, Songbai +1
Computer Science · #FOS: Computer and information sciences #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification
paper · pdf · doi:10.48550/arxiv.1702.05581
openalex publication_date 2017/02/18 · openalex created_date 2017/03/16 · openalex updated_date 2026/07/28
It has been a long-standing problem to efficiently learn a halfspace using as few labels as possible in the presence of noise. In this work, we propose an efficient Perceptron-based algorithm for actively learning homogeneous halfspaces under the uniform distribution over the unit sphere. Under the bounded noise condition~\citeMN06, where each label is flipped with probability at most η< \frac 1 2, our algorithm achieves a near-optimal label complexity of O((d)/((1-2η)2)ln\frac1ε) in time O((d2)/(ε(1-2η)3)). Under the adversarial noise condition~\citeABL14, KLS09, KKMS08, where at most a Ω(ε) fraction of labels can be flipped, our algorithm achieves a near-optimal label complexity of O(dln\frac1ε) in time O(\fracd2ε). Furthermore, we show that our active learning algorithm can be converted to an efficient passive learning algorithm that has near-optimal sample complexities with respect to ε and d.