Loading [MathJax]/jax/output/CommonHTML/jax.js

Revisiting Perceptron: Efficient and Label-Optimal Learning of Halfspaces

Part of Advances in Neural Information Processing Systems 30 (NIPS 2017)

Bibtex Metadata Paper Reviews Supplemental

Authors

Songbai Yan, Chicheng Zhang

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 η<12, our algorithm achieves a near-optimal label complexity of ˜O(d(12η)2ln1ϵ) in time ˜O(d2ϵ(12η)3). Under the adversarial noise condition~\cite{ABL14, KLS09, KKMS08}, where at most a ˜Ω(ϵ) fraction of labels can be flipped, our algorithm achieves a near-optimal label complexity of ˜O(dln1ϵ) in time ˜O(d2ϵ). 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.