Agnostic Proper Learning of Halfspaces under Gaussian Marginals

Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1522-1551, 2021.

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 this Paper

BibTeX
@InProceedings{pmlr-v134-diakonikolas21b, 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 = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {1522--1551}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/diakonikolas21b/diakonikolas21b.pdf}, url = {https://proceedings.mlr.press/v134/diakonikolas21b.html}, 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.} }
Endnote
%0 Conference Paper %T Agnostic Proper Learning of Halfspaces under Gaussian Marginals %A Ilias Diakonikolas %A Daniel M Kane %A Vasilis Kontonis %A Christos Tzamos %A Nikos Zarifis %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-diakonikolas21b %I PMLR %P 1522--1551 %U https://proceedings.mlr.press/v134/diakonikolas21b.html %V 134 %X 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.
APA
Diakonikolas, I., Kane, D.M., Kontonis, V., Tzamos, C. & Zarifis, N.. (2021). Agnostic Proper Learning of Halfspaces under Gaussian Marginals. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:1522-1551 Available from https://proceedings.mlr.press/v134/diakonikolas21b.html.

Related Material