PAC Learning of Halfspaces with Malicious Noise in Nearly Linear Time

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)30-46
Number of pages17
JournalProceedings of Machine Learning Research
Volume206
StatePublished - 2023
Event26th International Conference on Artificial Intelligence and Statistics, AISTATS 2023 - Valencia, Spain
Duration: 25 Apr 202327 Apr 2023

Fingerprint

Dive into the research topics of 'PAC Learning of Halfspaces with Malicious Noise in Nearly Linear Time'. Together they form a unique fingerprint.

Cite this