Revisiting perceptron: Efficient and label-optimal learning of halfspaces

Songbai Yan, Chicheng Zhang

Research output: Contribution to journalConference articlepeer-review

15 Scopus citations


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 flipped with probability at most η < 1/2, our algorithm achieves a near-optimal label complexity of Õ(d/(1-2n2) ln 1/ϵ)2in time Õ(D2/ϵ(1-2N)3). Under the adversarial noise condition [6,45,42] where at most a Ω(e) fraction of labels can be flipped, our algorithm achieves a near-optimal label complexity of Õ (d ln 1/π) in time Õ(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 e and d.

Original languageEnglish (US)
Pages (from-to)1057-1067
Number of pages11
JournalAdvances in Neural Information Processing Systems
StatePublished - 2017
Externally publishedYes
Event31st Annual Conference on Neural Information Processing Systems, NIPS 2017 - Long Beach, United States
Duration: Dec 4 2017Dec 9 2017

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing


Dive into the research topics of 'Revisiting perceptron: Efficient and label-optimal learning of halfspaces'. Together they form a unique fingerprint.

Cite this