Efficient Testable Learning of General Halfspaces with Adversarial Label Noise
<|reference_start|>Efficient Testable Learning of General Halfspaces with Adversarial Label Noise: 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.<|reference_end|>
@article{diakonikolas2024efficient,
    title={Efficient Testable Learning of General Halfspaces with Adversarial Label
  Noise},
    author={Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Nikos Zarifis},
    journal={"Testable Learning of General Halfspaces with Adversarial Label
  Noise." In The Thirty Seventh Annual Conference on Learning Theory, pp.
  1308-1335. PMLR, 2024},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.17165},
    primaryClass={cs.LG cs.DS stat.ML}
}