Adversarial Examples from Cryptographic Pseudo-Random Generators

Authors: Sébastien Bubeck, Yin Tat Lee, Eric Price, Ilya Razenshteyn
Published: 2018-11-15

Source: https://arxiv.org/abs/1811.06418

PDF: https://arxiv.org/pdf/1811.06418

Labels Predicted by AI

ロバスト性向上 統計的検定 統計的仮説検定

Please note that these labels were automatically added by AI. Therefore, they may not be entirely accurate.
For more details, please see the About the Literature Database page.

Abstract

In our recent work (Bubeck, Price, Razenshteyn, arXiv:1805.10204) we argued that adversarial examples in machine learning might be due to an inherent computational hardness of the problem. More precisely, we constructed a binary classification task for which (i) a robust classifier exists; yet no non-trivial accuracy can be obtained with an efficient algorithm in (ii) the statistical query model. In the present paper we significantly strengthen both (i) and (ii): we now construct a task which admits (i’) a maximally robust classifier (that is it can tolerate perturbations of size comparable to the size of the examples themselves); and moreover we prove computational hardness of learning this task under (ii’) a standard cryptographic assumption.