Efficient Testable Learning of Halfspaces with Adversarial Label Noise
This addresses the challenge of robust learning in noisy environments for machine learning practitioners, though it is incremental as it builds on the testable learning model.
The paper tackles the problem of learning halfspaces with adversarial label noise by introducing the first polynomial-time algorithm for testable learning under the Gaussian distribution, achieving misclassification error O(opt) + ε where opt is the error of the best fitting halfspace.
We give the first polynomial-time algorithm for the testable learning of halfspaces in the presence of adversarial label noise under the Gaussian distribution. In the recently introduced testable learning model, one is required to produce a tester-learner such that if the data passes the tester, then one can trust the output of the robust learner on the data. Our tester-learner runs in time $\poly(d/\eps)$ and outputs a halfspace with misclassification error $O(\opt)+\eps$, where $\opt$ is the 0-1 error of the best fitting halfspace. At a technical level, our algorithm employs an iterative soft localization technique enhanced with appropriate testers to ensure that the data distribution is sufficiently similar to a Gaussian.