NeurIPS 2020poster34 citations
Non-Convex SGD Learns Halfspaces with Adversarial Label Noise
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
Abstract
We study the problem of agnostically learning homogeneous halfspaces in the distribution-specific PAC model. For a broad family of structured distributions, including log-concave distributions, we show that non-convex SGD efficiently converges to a solution with misclassification error $O(\opt)+\eps$, where $\opt$ is the misclassification error of the best-fitting halfspace. In sharp contrast, we show that optimizing any convex surrogate inherently leads to misclassification error of $\omega(\opt)$, even under Gaussian marginals.
BibTeX
@inproceedings{NEURIPS2020_d785bf90,
author = {Diakonikolas, Ilias and Kontonis, Vasilis and Tzamos, Christos and Zarifis, Nikos},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {18540--18549},
publisher = {Curran Associates, Inc.},
title = {Non-Convex SGD Learns Halfspaces with Adversarial Label Noise},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/d785bf9067f8af9e078b93cf26de2b54-Paper.pdf},
volume = {33},
year = {2020}
}