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.