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
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.
Description
[2002.05632] Learning Halfspaces with Massart Noise Under Structured Distributions
%0 Journal Article
%1 diakonikolas2020learning
%A Diakonikolas, Ilias
%A Kontonis, Vasilis
%A Tzamos, Christos
%A Zarifis, Nikos
%D 2020
%K distributed readings robustness
%T Learning Halfspaces with Massart Noise Under Structured Distributions
%U http://arxiv.org/abs/2002.05632
%X 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
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.
@article{diakonikolas2020learning,
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.},
added-at = {2020-02-25T13:23:19.000+0100},
author = {Diakonikolas, Ilias and Kontonis, Vasilis and Tzamos, Christos and Zarifis, Nikos},
biburl = {https://www.bibsonomy.org/bibtex/2647b97d8bd68721af479f2db62acc4f9/kirk86},
description = {[2002.05632] Learning Halfspaces with Massart Noise Under Structured Distributions},
interhash = {dd08eec8021aadd42ee3e13859660845},
intrahash = {647b97d8bd68721af479f2db62acc4f9},
keywords = {distributed readings robustness},
note = {cite arxiv:2002.05632},
timestamp = {2020-02-25T13:23:19.000+0100},
title = {Learning Halfspaces with Massart Noise Under Structured Distributions},
url = {http://arxiv.org/abs/2002.05632},
year = 2020
}