Randomized Smoothing of All Shapes and Sizes

Abstract

Randomized smoothing is the current state-of-the-art defense with provable robustness against ${\ell }_2$ adversarial attacks. Many works have devised new randomized smoothing schemes for other metrics, such as ${\ell }_1$ or ${\ell }_{\infty }$; however, substantial effort was needed to derive such new guarantees. This begs the question: can we find a general theory for randomized smoothing? We propose a novel framework for devising and analyzing randomized smoothing schemes, and validate its effectiveness in practice. Our theoretical contributions are: (1) we show that for an appropriate notion of "optimal", the optimal smoothing distributions for any "nice" norms have level sets given by the norm's *Wulff Crystal*; (2) we propose two novel and complementary methods for deriving provably robust radii for any smoothing distribution; and, (3) we show fundamental limits to current randomized smoothing techniques via the theory of *Banach space cotypes*. By combining (1) and (2), we significantly improve the state-of-the-art certified accuracy in ${\ell }_1$ on standard datasets. Meanwhile, we show using (3) that with only label statistics under random input perturbations, randomized smoothing cannot achieve nontrivial certified accuracy against perturbations of ${\ell }_p$-norm $\Omega (\min (1,d^{\frac{1}{p}-\frac{1}{2}}))$, when the input dimension $d$ is large. We provide code in github.com/tonyduan/rs4a.

arXiv comment9 pages main text, 49 pages total

References in corpus (24)

• Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples
• Provable defenses against adversarial examples via the convex outer adversarial polytope
• Certified Adversarial Robustness via Randomized Smoothing
• Certified Defenses against Adversarial Examples
• Using Pre-Training Can Improve Model Robustness and Uncertainty
• Adversarial Risk and the Dangers of Evaluating Against Weak Attacks
• A Downsampled Variant of ImageNet as an Alternative to the CIFAR datasets
• Efficient Neural Network Robustness Certification with General Activation Functions
• Evaluating Robustness of Neural Networks with Mixed Integer Programming
• On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models
• Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
• An approach to reachability analysis for feed-forward ReLU neural networks
• Semidefinite relaxations for certifying robustness to adversarial examples
• Efficient Formal Safety Analysis of Neural Networks
• A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks
• On the Robustness of the CVPR 2018 White-Box Adversarial Example Defenses
• Training verified learners with learned verifiers
• Functional Adversarial Attacks
• Random matrices: Law of the determinant
• MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius
• Provable Robustness of ReLU networks via Maximization of Linear Regions
• Deep Neural Networks as 0-1 Mixed Integer Linear Programs: A Feasibility Study
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness
• Improved Image Wasserstein Attacks and Defenses

Cited by in corpus (15)

• Do Adversarially Robust ImageNet Models Transfer Better?
• A Closer Look at Accuracy vs. Robustness
• (De)Randomized Smoothing for Certifiable Defense against Patch Attacks
• RAB: Provable Robustness Against Backdoor Attacks
• Learning perturbation sets for robust machine learning
• Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework
• Deep Partition Aggregation: Provable Defense against General Poisoning Attacks
• Robust Models Are More Interpretable Because Attributions Look Normal
• Enhancing Certified Robustness via Smoothed Weighted Ensembling
• Higher-Order Certification for Randomized Smoothing
• Adversarial robustness via robust low rank representations
• Adversarial Training Makes Weight Loss Landscape Sharper in Logistic Regression
• Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neurons
• Smoothed Inference for Adversarially-Trained Models
• Adversarial Boot Camp: label free certified robustness in one epoch