Efficiently learning halfspaces with Tsybakov noise
Efficiently learning halfspaces with Tsybakov noise
复制标题
DOI：
10.1145/3406325.3450998
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Ilias Diakonikolas;D. Kane;Vasilis Kontonis;Christos Tzamos;Nikos Zarifis
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;D. Kane;Vasilis Kontonis;Christos Tzamos;Nikos Zarifis
研究了带Tsybakov噪声的PAC学习齐次半空间的问题。在Tsybakov噪声模型中，每个例子的标签被独立地以相反的控制概率翻转，对于一小部分例子来说，该概率可以任意接近1/2。我们给出了这个基本学习问题的第一个多项式时间算法。我们的算法在任何期望的精度下学习真实的半空间，并在包括对数凹分布在内的广泛的良好分布下成功。这篇扩展摘要是两篇论文的结合体。在以前的工作中，作者的一个子集发展了从学习到证明候选半空间的非最优性的有效归约，并给出了一个准多项式时间证书算法。在后续工作中，本文作者提出了一种多项式时间证书算法。
We study the problem of PAC learning homogeneous halfspaces with Tsybakov noise. In the Tsybakov noise model, the label of every example is independently flipped with an adversarially controlled probability that can be arbitrarily close to 1/2 for a fraction of the examples. We give the first polynomial-time algorithm for this fundamental learning problem. Our algorithm learns the true halfspace within any desired accuracy and succeeds under a broad family of well-behaved distributions including log-concave distributions. This extended abstract is a merge of two papers. In an earlier work, a subset of the authors developed an efficient reduction from learning to certifying the non-optimality of a candidate halfspace and gave a quasi-polynomial time certificate algorithm. In a subsequent work, the authors of the this paper developed a polynomial-time certificate algorithm.