Revisiting Perceptron: Efficient and Label-Optimal Learning of Halfspaces

Abstract

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~\cite{MN06}, where each label is flipped with probability at most $\eta <\frac{1}{2}$, our algorithm achieves a near-optimal label complexity of $\tilde{O}\left(\frac{d}{(1-2\eta {)}^2}\ln \frac{1}{\epsilon }\right)$ in time $\tilde{O}\left(\frac{d^2}{\epsilon (1-2\eta {)}^3}\right)$. Under the adversarial noise condition~\cite{ABL14, KLS09, KKMS08}, where at most a $\tilde{\Omega }(\epsilon )$ fraction of labels can be flipped, our algorithm achieves a near-optimal label complexity of $\tilde{O}\left(d\ln \frac{1}{\epsilon }\right)$ in time $\tilde{O}\left(\frac{d^2}{\epsilon }\right)$. 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 $\epsilon$ and $d$.

NIPS 2017

Cited by in corpus (17)

• Deep Active Learning for Named Entity Recognition
• Distribution-Independent PAC Learning of Halfspaces with Massart Noise
• Learning with Bounded Instance- and Label-dependent Label Noise
• Exploring Connections Between Active Learning and Model Extraction
• Efficient active learning of sparse halfspaces with arbitrary bounded noise
• Effectiveness of Tree-based Ensembles for Anomaly Discovery: Insights, Batch and Streaming Active Learning
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability
• Learning Halfspaces with Massart Noise Under Structured Distributions
• Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance
• Agnostic learning with unknown utilities
• Teaching an Active Learner with Contrastive Examples
• Forster Decomposition and Learning Halfspaces with Noise
• One-Bit Compressed Sensing via One-Shot Hard Thresholding
• On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise
• Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise
• Robust Learning under Strong Noise via SQs