Learning Halfspaces with Massart Noise Under Structured Distributions
Abstract
We study the problem of learning halfspaces with Massart noise in the distribution-specific PAC model. We give the first computationally efficient algorithm for this problem with respect to a broad family of distributions, including log-concave distributions. This resolves an open question posed in a number of prior works. Our approach is extremely simple: We identify a smooth {\em non-convex} surrogate loss with the property that any approximate stationary point of this loss defines a halfspace that is close to the target halfspace. Given this structural result, we can use SGD to solve the underlying learning problem.
Cite
Text
Diakonikolas et al. "Learning Halfspaces with Massart Noise Under Structured Distributions." Conference on Learning Theory, 2020.Markdown
[Diakonikolas et al. "Learning Halfspaces with Massart Noise Under Structured Distributions." Conference on Learning Theory, 2020.](https://mlanthology.org/colt/2020/diakonikolas2020colt-learning/)BibTeX
@inproceedings{diakonikolas2020colt-learning,
title = {{Learning Halfspaces with Massart Noise Under Structured Distributions}},
author = {Diakonikolas, Ilias and Kontonis, Vasilis and Tzamos, Christos and Zarifis, Nikos},
booktitle = {Conference on Learning Theory},
year = {2020},
pages = {1486-1513},
volume = {125},
url = {https://mlanthology.org/colt/2020/diakonikolas2020colt-learning/}
}