Agnostic Proper Learning of Halfspaces Under Gaussian Marginals
Abstract
We study the problem of agnostically learning halfspaces under the Gaussian distribution. Our main result is the {\em first proper} learning algorithm for this problem whose running time qualitatively matches that of the best known improper agnostic learner. Building on this result, we also obtain the first proper polynomial time approximation scheme (PTAS) for agnostically learning homogeneous halfspaces. Our techniques naturally extend to agnostically learning linear models with respect to other activation functions, yielding the first proper agnostic algorithm for ReLU regression.
Cite
Text
Diakonikolas et al. "Agnostic Proper Learning of Halfspaces Under Gaussian Marginals." Conference on Learning Theory, 2021.Markdown
[Diakonikolas et al. "Agnostic Proper Learning of Halfspaces Under Gaussian Marginals." Conference on Learning Theory, 2021.](https://mlanthology.org/colt/2021/diakonikolas2021colt-agnostic/)BibTeX
@inproceedings{diakonikolas2021colt-agnostic,
title = {{Agnostic Proper Learning of Halfspaces Under Gaussian Marginals}},
author = {Diakonikolas, Ilias and Kane, Daniel M and Kontonis, Vasilis and Tzamos, Christos and Zarifis, Nikos},
booktitle = {Conference on Learning Theory},
year = {2021},
pages = {1522-1551},
volume = {134},
url = {https://mlanthology.org/colt/2021/diakonikolas2021colt-agnostic/}
}