Revisiting Perceptron: Efficient and Label-Optimal Learning of Halfspaces
This work addresses the long-standing challenge of label-efficient learning for halfspaces, which is incremental as it builds on existing Perceptron methods to improve noise robustness.
The paper tackles the problem of efficiently learning halfspaces with minimal labels under noise, proposing a Perceptron-based algorithm that achieves near-optimal label complexities of Õ(d/(1-2η)² ln(1/ε)) under bounded noise and Õ(d ln(1/ε)) under adversarial noise.
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 $η< \frac 1 2$, our algorithm achieves a near-optimal label complexity of $\tilde{O}\left(\frac{d}{(1-2η)^2}\ln\frac{1}ε\right)$ in time $\tilde{O}\left(\frac{d^2}{ε(1-2η)^3}\right)$. Under the adversarial noise condition~\cite{ABL14, KLS09, KKMS08}, where at most a $\tilde Ω(ε)$ fraction of labels can be flipped, our algorithm achieves a near-optimal label complexity of $\tilde{O}\left(d\ln\frac{1}ε\right)$ in time $\tilde{O}\left(\frac{d^2}ε\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 $ε$ and $d$.