Agnostic Proper Learning of Halfspaces under Gaussian Marginals
Agnostic Proper Learning of Halfspaces under Gaussian Marginals
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Ilias Diakonikolas;D. Kane;Vasilis Kontonis;Christos Tzamos;Nikos Zarifis
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;D. Kane;Vasilis Kontonis;Christos Tzamos;Nikos Zarifis
我们研究了高斯分布下不稳定学习半空间的问题。我们的主要结果是该问题的第一个适当的学习算法，其样本复杂性和计算复杂性在定性上与最知名的不当知识学习者相匹配。在此结果的基础上，我们还获得了第一个适当的多项式时间近似方案（PTA），用于不可知的同质半空间。我们的技术自然地扩展到不可知的线性模型，相对于其他非线性激活，尤其是第一种适当的不可知算法，用于恢复回归。
We study the problem of agnostically learning halfspaces under the Gaussian distribution. Our main result is the first proper learning algorithm for this problem whose sample complexity and computational complexity qualitatively match those of the best known improper agnostic learner. Building on this result, we also obtain the first proper polynomial-time approximation scheme (PTAS) for agnostically learning homogeneous halfspaces. Our techniques naturally extend to agnostically learning linear models with respect to other non-linear activations, yielding in particular the first proper agnostic algorithm for ReLU regression.