Is nasty noise actually harder than malicious noise?
Guy Blanc, Yizhi Huang, Tal Malkin, Rocco A. Servedio
我们考虑了计算效率算法在噪声存在下学习的相对能力和局限性,在两个研究良好且具有挑战性的对抗性噪声模型下用于学习布尔函数:恶意噪声,其中对手可以任意损坏给学习者的示例的随机子集;以及讨厌的噪声,其中对手可以任意损坏给学习者的示例的对抗性选择子集。 我们考虑独立于分布和固定分布的设置。 我们的主要结果突出了这两种设置之间的巨大差异:对于独立于分布的学习,我们证明了两种噪声模型之间的强烈等价性:如果一个类函数在η速率恶意噪声的存在下可以有效地学习,那么它在η速率讨厌噪声的存在下也可以有效地学习。 与此形成鲜明对比的是,对于固定分发设置,我们显示了一个任意大分离:在标准加密假设下,对于任何任意大值r,存在一个概念类,其中多项式时间学习算法可以容忍的恶意噪声速率η_恶意与此类学习算法可以容忍的恶劣噪声的速率η_nasty之间存在r的比例。 为了抵消固定分布设置的负结果,我们定义了一个广泛而自然的算法类别,即那些忽略矛盾示例(ICE)的算法。 我们表明,对于这些算法,恶意噪声和讨厌的噪声在噪声率中相当于两个因素:任何使用η速率恶意噪声成功的高效ICE学习者都可以转换为具有η/2速率讨厌噪声的高效学习者。 我们进一步证明,上述两个因素是必要的,再次在一个标准的加密假设下。
We consider the relative abilities and limitations of computationally efficient algorithms for learning in the presence of noise, under two well-studied and challenging adversarial noise models for learning Boolean functions: malicious noise, in which an adversary can arbitrarily corrupt a random subset of examples given to the learner; and nasty noise, in which an adversary can arbitrarily corrupt an adversarially chosen subset of examples given to the learner. We consider both the distribution...
