论文标题
具有不可知论的噪声的对抗性稳健的适当学习的复杂性适当地学习
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
论文作者
论文摘要
我们研究了独立于分布的不可抗拒的PAC模型中对抗性鲁棒的适当学习的计算复杂性，重点是$ l_p $扰动。我们给出了一种有效的计算学习算法，并为此问题提供了几乎匹配的计算硬度结果。我们发现的一个有趣的含义是，$ l _ {\ infty} $扰动情况在计算上比$ 2 \ leq p <\ infty $要难。
We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent agnostic PAC model, with a focus on $L_p$ perturbations. We give a computationally efficient learning algorithm and a nearly matching computational hardness result for this problem. An interesting implication of our findings is that the $L_{\infty}$ perturbations case is provably computationally harder than the case $2 \leq p < \infty$.
