On Robustness to Adversarial Examples and Polynomial Optimization
On Robustness to Adversarial Examples and Polynomial Optimization
复制标题
DOI：
--
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Pranjal Awasthi;Abhratanu Dutta;Aravindan Vijayaraghavan
中科院分区：
文献类型：
--
作者：
Pranjal Awasthi;Abhratanu Dutta;Aravindan Vijayaraghavan
我们研究具有可证明保证的计算有效算法的设计，这些算法对对抗性（测试时间）扰动非常可靠。尽管由于它与深层网络的时间稳健性的联系，最近关于该主题的作品发生了爆炸，但理论上对几个基本问题（例如（i）何时以及如何设计出可证明强大的学习算法的理论理解有限？ （ii）以计算有效的方式实现对对抗性示例的鲁棒性的价格是多少？这项工作的主要贡献是在实现对抗性实例的鲁棒性与一系列多项式优化问题之间表现出牢固的联系，从而在上述问题上取得了进展。特别是，我们利用了（a）设计计算高效的鲁棒算法，可证明对大量假设的可证明保证，即线性分类器和2级多项式阈值函数〜（ptfs），（b）具有精确的表征以计算有效的方式实现鲁棒性的价格，（c）设计有效的算法，以证明鲁棒性并以有原则的方式为2层神经网络产生对抗性攻击。我们从经验上证明了这些攻击对真实数据的有效性。
We study the design of computationally efficient algorithms with provable guarantees, that are robust to adversarial (test time) perturbations. While there has been an explosion of recent work on this topic due to its connections to test time robustness of deep networks, there is limited theoretical understanding of several basic questions like (i) when and how can one design provably robust learning algorithms? (ii) what is the price of achieving robustness to adversarial examples in a computationally efficient manner? The main contribution of this work is to exhibit a strong connection between achieving robustness to adversarial examples, and a rich class of polynomial optimization problems, thereby making progress on the above questions. In particular, we leverage this connection to (a) design computationally efficient robust algorithms with provable guarantees for a large class of hypothesis, namely linear classifiers and degree-2 polynomial threshold functions~(PTFs), (b) give a precise characterization of the price of achieving robustness in a computationally efficient manner for these classes, (c) design efficient algorithms to certify robustness and generate adversarial attacks in a principled manner for 2-layer neural networks. We empirically demonstrate the effectiveness of these attacks on real data.