Efficient Testable Learning of General Halfspaces with Adversarial Label Noise
This addresses a fundamental challenge in robust machine learning for scenarios with noisy labels, though it appears incremental as it builds on prior work for homogeneous halfspaces.
The paper tackles the problem of testable learning of general halfspaces with adversarial label noise under the Gaussian distribution, achieving the first polynomial-time tester-learner with dimension-independent misclassification error.
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.