Adversarial Examples from Cryptographic Pseudo-Random Generators
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). First posted on arXiv 15 Nov 2018.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 6; 2022: 2; 2023: 2.
10 papers.
- 2023Cross-Entropy Loss Functions: Theoretical Analysis and Applicationscited by 210
- 2021Detecting Adversarial Examples Is (Nearly) As Hard As Classifying Themcited by 48
- 2021Calibration and Consistency of Adversarial Surrogate Lossescited by 47
- 2021On the Existence of the Adversarial Bayes Classifier (Extended Version)cited by 25
- 2021Understanding Generalization in Adversarial Training via the Bias-Variance Decompositioncited by 10
- 2022The Consistency of Adversarial Training for Binary Classificationcited by 3
- 2023Computational Asymmetries in Robust Classificationcited by 2
- 2021Provable Adversarial Robustness in the Quantum Modelcited by 1
- 2021Identifying and Exploiting Structures for Reliable Deep Learningcited by 0
- 2022mathscrH-Consistency Estimation Error of Surrogate Loss Minimizerscited by 0
- 2023Computational Asymmetries in Robust Classification25 Jun 2023
- 2023Cross-Entropy Loss Functions: Theoretical Analysis and Applications14 Apr 2023
- 2022The Consistency of Adversarial Training for Binary Classification18 Jun 2022
- 2022mathscrH-Consistency Estimation Error of Surrogate Loss Minimizers16 May 2022
- 2021Provable Adversarial Robustness in the Quantum Model17 Dec 2021
- 2021On the Existence of the Adversarial Bayes Classifier (Extended Version)3 Dec 2021
- 2021Identifying and Exploiting Structures for Reliable Deep Learning16 Aug 2021
- 2021Detecting Adversarial Examples Is (Nearly) As Hard As Classifying Them24 Jul 2021
- 2021Calibration and Consistency of Adversarial Surrogate Losses19 Apr 2021
- 2021Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition17 Mar 2021