Limitations of adversarial robustness: strong No Free Lunch Theorem
By Elvis Dohmatob. 2018
29 citations recorded by the source corpus.
This manuscript presents some new impossibility results on adversarial robustness in machine learning, a very important yet largely open problem. We show that if conditioned on a class label the data distribution satisfies the $W_2$ Talagrand transportation-cost inequality (for example, this condition is satisfied if the conditional distribution has density which is log-concave; is the uniform measure on a compact Riemannian manifold with positive Ricci curvature, any classifier can be adversarially fooled with high probability once the perturbations are slightly greater than the natural noise level in the problem. We call this result The Strong "No Free Lunch" Theorem as some recent results (Tsipras et al. 2018, Fawzi et al. 2018, etc.) on the subject can be immediately recovered as very particular cases. Our theoretical bounds are demonstrated on both simulated and real data (MNIST). We conclude the manuscript with some speculation on possible future research directions.
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
- J. Kolter
- Ekin Dogus Cubuk
- Quoc V. Le
- Nicholas Carlini
- Dong Yin
- Matthias Hein
- Justin Gilmer
- Sergey Levine
Citations in the corpus
- Certified Adversarial Robustness via Randomized Smoothing (2019, background): “Recent theoretical work has taken steps towards addressing this question (Mahloujifar et al., 2019; Gilmer et al., 2018b; Fawzi et al., 2018; Tsipras et al., 2019; Schmidt et al., 2018; Shafahi et al., 2019; Dohma- tob, 2018; Bubeck et al., 2018b).”
- Adversarial Examples Are a Natural Consequence of Test Error in Noise (2019, background): “Several recent papers (Gilmer et al., 2018b; Mahloujifar et al., 2018; Dohmatob, 2018; Fawzi et al., 2018a) use concentation of measure to prove rigorous upper bounds on adversarial robustness for certain distributions in terms of test error, suggesting non-zero test error may imply the existence of”
- The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure (2018, background): “2 Other concurrent works have also demonstrated the role of concentration of measure in guaranteeing the existence of adversarial examples in certain metric probability spaces (Dohmatob 2018; Shafahi et al. 2018).”
- Rademacher Complexity for Adversarially Robust Generalization (2018, background): “A few other lines of work have conducted theoretical analysis of adversarial examples (Wang et al., 2017; Bubeck et al., 2018; Gilmer et al., 2018b; Dohmatob, 2018; Mahloujifar et al., 2018).”