Towards Evading the Limits of Randomized Smoothing: A Theoretical Analysis
Not on the map. Why?
Abstract (arXiv)
Randomized smoothing is the dominant standard for provable defenses against adversarial examples. Nevertheless, this method has recently been proven to suffer from important information theoretic limitations. In this paper, we argue that these limitations are not intrinsic, but merely a byproduct of current certification methods. We first show that these certificates use too little information about the classifier, and are in particular blind to the local curvature of the decision boundary. This leads to severely sub-optimal robustness guarantees as the dimension of the problem increases. We then show that it is theoretically possible to bypass this issue by collecting more information about the classifier. More precisely, we show that it is possible to approximate the optimal certificate with arbitrary precision, by probing the decision boundary with several noise distributions. Since this process is executed at certification time rather than at test time, it entails no loss in natural accuracy while enhancing the quality of the certificates. This result fosters further research on classifier-specific certification and demonstrates that randomized smoothing is still worth investigating. Although classifier-specific certification may induce more computational cost, we also provide some theoretical insight on how to mitigate it.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 33 of its 50 references that are in the map. First posted on arXiv 3 Jun 2022.
Builds on
33 of 50 references.
References · 33
- 2014Explaining and Harnessing Adversarial Examplescited by 7,287
- 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
- 2013Intriguing properties of neural networkscited by 5,114
- 2016Towards Evaluating the Robustness of Neural Networkscited by 2,976
- 2016Adversarial examples in the physical worldcited by 1,762
- 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
- 2018Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examplescited by 1,259
- 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
- 2020On Adaptive Attacks to Adversarial Example Defensescited by 547
- 2018Certified Robustness to Adversarial Examples with Differential Privacycited by 462
- 2019On Evaluating Adversarial Robustnesscited by 442
- 2019Provably Robust Deep Learning via Adversarially Trained Smoothed Classifierscited by 328
21 more
- 2018Certified Defenses against Adversarial Examplescited by 305
- 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 254
- 2018Certified Adversarial Robustness with Additive Noisecited by 178
- 2018Semidefinite relaxations for certifying robustness to adversarial examplescited by 178
- 2020Randomized Smoothing of All Shapes and Sizescited by 146
- 2020MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radiuscited by 114
- 2021Orthogonalizing Convolutional Layers with the Cayley Transformcited by 105
- 2019Preventing Gradient Attenuation in Lipschitz Constrained Convolutional Networkscited by 86
- 2020Consistency Regularization for Certified Robustness of Smoothed Classifierscited by 73
- 2021Skew Orthogonal Convolutionscited by 67
- 2021A Dynamical System Perspective for Lipschitz Neural Networkscited by 59
- 2020Curse of Dimensionality on Randomized Smoothing for Certifiable Robustnesscited by 56
- 2020Randomization matters. How to defend against strong adversarial attackscited by 37
- 2020Higher-Order Certification for Randomized Smoothingcited by 36
- 2020Random Smoothing Might be Unable to Certify ℓ_∞ Robustness for High-Dimensional Imagescited by 35
- 2021Scalable Certified Segmentation via Randomized Smoothingcited by 35
- 2019Theoretical evidence for adversarial robustness through randomizationcited by 33
- 2020Extensions and limitations of randomized smoothing for robustness guaranteescited by 15
- 2020Advocating for Multiple Defense Strategies against Adversarial Examplescited by 11
- 2020Tight Second-Order Certificates for Randomized Smoothingcited by 10
- 2021Simpler Certified Radius Maximization by Propagating Covariancescited by 2
Built on by
Citing papers per year: 2023: 2.
2 papers.