Revisiting Perceptron: Efficient and Label-Optimal Learning of Halfspaces

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}}_{}(\frac{d/}{(1-2\eta {)^}_{2 }}ln\frac{1/}{\epsilon })\) in time \tilde{\({O}}_{}\)\((\frac{{d^}_{2 /}}{\epsilon (1-2\eta {)^}_3})\). 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}}_{}(dln\frac{1/}{\epsilon })\) in time \tilde{\({O}}_{}(\frac{{d^2/}_{}}{\epsilon })\). 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\).