PAC Learning of Halfspaces with Malicious Noise in Nearly Linear Time

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

SN - 2640-3498

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 -