TY - JOUR
T1 - PAC Learning of Halfspaces with Malicious Noise in Nearly Linear Time
AU - Shen, Jie
N1 - Publisher Copyright:
Copyright © 2023 by the author(s)
PY - 2023
Y1 - 2023
N2 - We study the problem of efficient PAC learning of halfspaces in Rd in the presence of the malicious noise, where a fraction of the training samples are adversarially corrupted. A series of recent works have developed polynomial-time algorithms that enjoy near-optimal sample complexity and noise tolerance, yet leaving open whether a linear-time algorithm exists and matches these appealing statistical performance guarantees. In this work, we give an affirmative answer by developing an algorithm that runs in time Õ(md), where m = Õ(d ε ) is the sample size and ε ∈ (0, 1) is the target error rate. Notably, the computational complexity of all prior algorithms suffer either a high order dependence on the problem size, or is implicitly proportional to ε 1/2 through the sample size. Our key idea is to combine localization and an approximate version of matrix multiplicative weights update method to progressively downweight the contribution of the corrupted samples while refining the learned halfspace.
AB - We study the problem of efficient PAC learning of halfspaces in Rd in the presence of the malicious noise, where a fraction of the training samples are adversarially corrupted. A series of recent works have developed polynomial-time algorithms that enjoy near-optimal sample complexity and noise tolerance, yet leaving open whether a linear-time algorithm exists and matches these appealing statistical performance guarantees. In this work, we give an affirmative answer by developing an algorithm that runs in time Õ(md), where m = Õ(d ε ) is the sample size and ε ∈ (0, 1) is the target error rate. Notably, the computational complexity of all prior algorithms suffer either a high order dependence on the problem size, or is implicitly proportional to ε 1/2 through the sample size. Our key idea is to combine localization and an approximate version of matrix multiplicative weights update method to progressively downweight the contribution of the corrupted samples while refining the learned halfspace.
UR - http://www.scopus.com/inward/record.url?scp=85163869618&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85163869618&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85163869618
VL - 206
SP - 30
EP - 46
JO - Proceedings of Machine Learning Research
JF - Proceedings of Machine Learning Research
T2 - 26th International Conference on Artificial Intelligence and Statistics, AISTATS 2023
Y2 - 25 April 2023 through 27 April 2023
ER -