We study the problem of distribution-independent PAC learning of
halfspaces in the presence of Massart noise. Specifically, we are given a set
of labeled examples $(x, y)$ drawn from a distribution $D$
on $R^d+1$ such that the marginal distribution on the unlabeled
points $x$ is arbitrary and the labels $y$ are generated by an unknown
halfspace corrupted with Massart noise at noise rate $\eta<1/2$. The goal is to
find a hypothesis $h$ that minimizes the misclassification error
$Pr_(x, y) D łeft h(x) y
\right$.
We give a $polyłeft(d, 1/\right)$ time algorithm for this
problem with misclassification error $\eta+\epsilon$. We also provide evidence
that improving on the error guarantee of our algorithm might be computationally
hard. Prior to our work, no efficient weak (distribution-independent) learner
was known in this model, even for the class of disjunctions. The existence of
such an algorithm for halfspaces (or even disjunctions) has been posed as an
open question in various works, starting with Sloan (1988), Cohen (1997), and
was most recently highlighted in Avrim Blum's FOCS 2003 tutorial.
Description
[1906.10075] Distribution-Independent PAC Learning of Halfspaces with Massart Noise
%0 Journal Article
%1 diakonikolas2019distributionindependent
%A Diakonikolas, Ilias
%A Gouleakis, Themis
%A Tzamos, Christos
%D 2019
%K bounds learning
%T Distribution-Independent PAC Learning of Halfspaces with Massart Noise
%U http://arxiv.org/abs/1906.10075
%X We study the problem of distribution-independent PAC learning of
halfspaces in the presence of Massart noise. Specifically, we are given a set
of labeled examples $(x, y)$ drawn from a distribution $D$
on $R^d+1$ such that the marginal distribution on the unlabeled
points $x$ is arbitrary and the labels $y$ are generated by an unknown
halfspace corrupted with Massart noise at noise rate $\eta<1/2$. The goal is to
find a hypothesis $h$ that minimizes the misclassification error
$Pr_(x, y) D łeft h(x) y
\right$.
We give a $polyłeft(d, 1/\right)$ time algorithm for this
problem with misclassification error $\eta+\epsilon$. We also provide evidence
that improving on the error guarantee of our algorithm might be computationally
hard. Prior to our work, no efficient weak (distribution-independent) learner
was known in this model, even for the class of disjunctions. The existence of
such an algorithm for halfspaces (or even disjunctions) has been posed as an
open question in various works, starting with Sloan (1988), Cohen (1997), and
was most recently highlighted in Avrim Blum's FOCS 2003 tutorial.
@article{diakonikolas2019distributionindependent,
abstract = {We study the problem of {\em distribution-independent} PAC learning of
halfspaces in the presence of Massart noise. Specifically, we are given a set
of labeled examples $(\mathbf{x}, y)$ drawn from a distribution $\mathcal{D}$
on $\mathbb{R}^{d+1}$ such that the marginal distribution on the unlabeled
points $\mathbf{x}$ is arbitrary and the labels $y$ are generated by an unknown
halfspace corrupted with Massart noise at noise rate $\eta<1/2$. The goal is to
find a hypothesis $h$ that minimizes the misclassification error
$\mathbf{Pr}_{(\mathbf{x}, y) \sim \mathcal{D}} \left[ h(\mathbf{x}) \neq y
\right]$.
We give a $\mathrm{poly}\left(d, 1/\epsilon \right)$ time algorithm for this
problem with misclassification error $\eta+\epsilon$. We also provide evidence
that improving on the error guarantee of our algorithm might be computationally
hard. Prior to our work, no efficient weak (distribution-independent) learner
was known in this model, even for the class of disjunctions. The existence of
such an algorithm for halfspaces (or even disjunctions) has been posed as an
open question in various works, starting with Sloan (1988), Cohen (1997), and
was most recently highlighted in Avrim Blum's FOCS 2003 tutorial.},
added-at = {2020-02-26T13:37:20.000+0100},
author = {Diakonikolas, Ilias and Gouleakis, Themis and Tzamos, Christos},
biburl = {https://www.bibsonomy.org/bibtex/239cfb4550018ed2f61e040282e9851b4/kirk86},
description = {[1906.10075] Distribution-Independent PAC Learning of Halfspaces with Massart Noise},
interhash = {2c647e61b649635c9b189ce17af0ccf6},
intrahash = {39cfb4550018ed2f61e040282e9851b4},
keywords = {bounds learning},
note = {cite arxiv:1906.10075},
timestamp = {2020-02-26T13:37:20.000+0100},
title = {Distribution-Independent PAC Learning of Halfspaces with Massart Noise},
url = {http://arxiv.org/abs/1906.10075},
year = 2019
}