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 [49], where each label is fiipped with probability at most , our algorithm achieves near-optimal label complexity of . Under the adversarial noise condition [6, 45, 42], where at most a fraction of  labels  can be fiipped,  our algorithm achieves a near-optimal label complexity of  in time . 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.