Hardness of Learning a Single Neuron with Adversarial Label Noise
Hardness of Learning a Single Neuron with Adversarial Label Noise
复制标题
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ilias Diakonikolas;D. Kane;Pasin Manurangsi;Lisheng Ren
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;D. Kane;Pasin Manurangsi;Lisheng Ren
我们研究了对抗性标签噪声下关于平方损失的无分布PAC学习单个神经元的问题。对于包括ReLU和Sigmoid在内的一系列激活函数，我们证明了在统计查询模型下的学习结果具有很强的计算难度，并且在已有的关于重现XOR公式的复杂性的充分研究的假设下。具体地说，我们证明了任何多项式时间的学习算法，即使是不适当的，也不能在任何常数因子内逼近最优损失值。
We study the problem of distribution-free PAC learning a single neuron under adversarial label noise with respect to the squared loss. For a range of activation functions, including ReLUs and sigmoids, we prove strong computational hardness of learning results in the Statistical Query model and under a well-studied assumption on the complexity of re-futing XOR formulas. Specifically, we establish that no polynomial-time learning algo-rithm, even improper, can approximate the optimal loss value within any constant factor.