Adversarial Examples from Cryptographic Pseudo-Random Generators
By Sébastien Bubeck, Yin Tat Lee, Eric Price, Ilya P. Razenshteyn. 2018
33 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Akshay Degwekar
- Vinod Vaikuntanathan
- J. Kolter
- Elan Rosenfeld
- Jeremy M. Cohen
- Mehryar Mohri
- Anqi Mao
- Yutao Zhong
Citations in the corpus
- Certified Adversarial Robustness via Randomized Smoothing (2019, background): “Of particular relevance, Bubeck et al. (2018a); Degwekar & Vaikuntanathan (2019) show that for certain classification problems, there exists a robust classifier that is not efficiently computable (like randomized smoothing) but there does not exist any robust classifier that is efficiently…”
- Adversarial Robustness May Be at Odds With Simplicity (2019, background): “[2, 3] propose Hypothesis (B), and give a theoretical example of a learning task where learning a robust classifier is not possible in polynomial time (under standard cryptographic assumptions).”
- Computational Limitations in Robust Classification and Win-Win Results (2019, background): “On the other hand, for natural learning tasks, humans seem to be robust classifiers that tolerate non-zero error rate , indeed even efficient robust classifiers; see Bubeck et al. (2018b) for a more detailed discussion. World 2. Robust classifiers exist, but they are computationally inefficient. We ”
- Cross-Entropy Loss Functions: Theoretical Analysis and Applications (2023, background): “…et al., 2020; Attias et al., 2022b; Xiao et al., 2022; Viallard et al., 2021; Bubeck & Sellke, 2021; Li & Telgarsky, 2023), adversarial examples (Bubeck et al., 2018; 2019; Bartlett et al., 2021; Bubeck et al., 2021), consistency guarantees and optimal adversarial classifiers (Bao et al., 2020;…”