TY - JOUR
T1 - Revisiting perceptron
T2 - 31st Annual Conference on Neural Information Processing Systems, NIPS 2017
AU - Yan, Songbai
AU - Zhang, Chicheng
N1 - Funding Information:
Acknowledgments. The authors thank Kamalika Chaudhuri for help and support, Hongyang Zhang for thought-provoking initial conversations, Jiapeng Zhang for helpful discussions, and the anonymous reviewers for their insightful feedback. Much of this work is supported by NSF IIS-1167157 and 1162581.
Publisher Copyright:
© 2017 Neural information processing systems foundation. All rights reserved.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85047008664&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85047008664&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85047008664
SN - 1049-5258
VL - 2017-December
SP - 1057
EP - 1067
JO - Advances in Neural Information Processing Systems
JF - Advances in Neural Information Processing Systems
Y2 - 4 December 2017 through 9 December 2017
ER -