Adversarially Robust Learning Could Leverage Computational Hardness
Adversarially Robust Learning Could Leverage Computational Hardness
复制标题
DOI：
--
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Sanjam Garg;S. Jha;Saeed Mahloujifar;Mohammad Mahmoody
中科院分区：
文献类型：
--
作者：
Sanjam Garg;S. Jha;Saeed Mahloujifar;Mohammad Mahmoody
近年来，设计出对对抗性扰动的强大分类算法已成为一个具有挑战性的问题。特别是，深神经网（DNN）似乎在测试实例上不可察觉地不可察觉。但是，到目前为止，可证明的鲁棒性的工作一直集中在信息理论的鲁棒性上，甚至排除了任何对抗性例子的存在。在这项工作中，我们研究是否希望从攻击者的算法性质中受益，该攻击者搜索对抗性示例，并询问是否有任何学习任务，是否有可能设计出仅适用于对对手的强大的分类器。实际上，众多的加密任务只能与计算界面的对手相抵触，而对于计算无限的攻击者来说，确实是不可能的。因此，自然要问相同的策略是否可以帮助强大的学习。我们表明，攻击者的计算局限性确实可以通过证明分类器的可能性来进行某些学习任务，而这些任务的计算和信息理论对手具有非常不同的能力。也就是说，尽管计算无限的对手可以成功攻击并找到具有小扰动的对抗示例，但多项式时间对手除非能够打破标准的加密硬度假设，否则多项式时间对手是无法做到的。因此，我们的结果表明，可能采用类似的加密方法（依赖计算硬度）具有实现计算稳健机器学习的希望。在反向方向上，我们还表明，这种学习任务的存在，其中计算鲁棒性比信息理论鲁棒性击败信息需要通过暗示NP的（平均案例）硬度来计算硬度。
Over recent years, devising classification algorithms that are robust to adversarial perturbations has emerged as a challenging problem. In particular, deep neural nets (DNNs) seem to be susceptible to small imperceptible changes over test instances. However, the line of work in provable robustness, so far, has been focused on information-theoretic robustness, ruling out even the existence of any adversarial examples. In this work, we study whether there is a hope to benefit from algorithmic nature of an attacker that searches for adversarial examples, and ask whether there is any learning task for which it is possible to design classifiers that are only robust against polynomial-time adversaries. Indeed, numerous cryptographic tasks can only be secure against computationally bounded adversaries, and are indeed impossible for computationally unbounded attackers. Thus, it is natural to ask if the same strategy could help robust learning. We show that computational limitation of attackers can indeed be useful in robust learning by demonstrating the possibility of a classifier for some learning task for which computational and information theoretic adversaries of bounded perturbations have very different power. Namely, while computationally unbounded adversaries can attack successfully and find adversarial examples with small perturbation, polynomial time adversaries are unable to do so unless they can break standard cryptographic hardness assumptions. Our results, therefore, indicate that perhaps a similar approach to cryptography (relying on computational hardness) holds promise for achieving computationally robust machine learning. On the reverse directions, we also show that the existence of such learning task in which computational robustness beats information theoretic robustness requires computational hardness by implying (average-case) hardness of NP.