【NeurIPS2019 论文】带有Massart噪声的半空间分布无关PAC学习（Distribution-Independent PAC Learning of Halfspaces with Massart Noise）

题目： Distribution-Independent PAC Learning of Halfspaces with Massart Noise

摘要： 研究了存在Massart噪声的半空间{em分布无关}PAC学习问题。具体地说，我们给出了一组从\R~d+1上的\D分布中提取的标记示例(\b_x,y)，使得未标记点\b_x上的边缘分布是任意的，并且标签y是由以噪声率ŋ<1/2被Massart噪声污染的未知半空间生成的。我们的目标是找到一个可以最小化错误分类\P~r(\b_x,y)~\D~[h(\bx)≠y]的假设h。我们给出了一个有误分类错误的时间算法\poly(d,1/\eps)。我们还证明了改进算法的误差保证在计算上可能是困难的。在我们的研究之前，在这个模型中，没有一个有效的弱（分布独立）学习者是已知的，即使是对于析取类。在Sulon（1988），科恩（1997）中，半空间（甚至间断）的这种算法的存在已经作为一个开放的问题提出，并且最近在Avrim Blum的FoCS 2003教程中被高亮显示。

作者简介： Ilias Diakonikolas，是威斯康星大学麦迪逊分校 (WISC)计算机系的一名教员。在加入威斯康星州大学之前，他是安德鲁和埃娜·维特比（Erna Viterbi）在南加州大学（USC）担任计算机科学早期职业主席，在爱丁堡大学（University of Edinburgh）任教员。在此之前，他在加州大学伯克利分校读了两年的博士后，在理论计算机科学研究员。他在哥伦比亚大学获得了计算机科学博士学位。个人主页：http://www.iliasdiakonikolas.org/

Themis Gouleakis，于2018年完成了麻省理工学院的博士学位，隶属于CSAIL的计算理论小组,现在是Max普朗克信息研究所算法与复杂性系的博士后研究员。