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~MN06, where each label is flipped with probability at most < 1 2, our algorithm achieves a near-optimal label complexity of O(d(1-2)^21) in time O(d^2(1-2)^3). Under the adversarial noise condition~ABL14, KLS09, KKMS08, where at most a () fraction of labels can be flipped, our algorithm achieves a near-optimal label complexity of O(d1) in time O(d^2). 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.

Tasks

Reproductions