Testable Learning of General Halfspaces with Adversarial Label Noise

Diakonikolas, Ilias; Kane, Daniel M; Liu, Sihan; Zarifis, Nikos

Session: 3C-2 (Testing), Tuesday, Jul 02, 14:45-16:00

Abstract: We study the task of testable learning of general --- not necessarily homogeneous --- halfspaces with adversarial label noise with respect to the Gaussian distribution. In the testable learning framework, the goal is to develop 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 main result is the first polynomial time tester-learner for general halfspaces that achieves dimension-independent misclassification error. At the heart of our approach is a new methodology to reduce testable learning of general halfspaces to testable learning of nearly homogeneous halfspaces that may be of broader interest.