Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness

Abstract

Randomized smoothing, using just a simple isotropic Gaussian distribution, has been shown to produce good robustness guarantees against ${\ell }_2$-norm bounded adversaries. In this work, we show that extending the smoothing technique to defend against other attack models can be challenging, especially in the high-dimensional regime. In particular, for a vast class of i.i.d.~smoothing distributions, we prove that the largest ${\ell }_p$-radius that can be certified decreases as $O(1/d^{\frac{1}{2}-\frac{1}{p}})$ with dimension $d$ for $p>2$. Notably, for $p\ge 2$, this dependence on $d$ is no better than that of the ${\ell }_p$-radius that can be certified using isotropic Gaussian smoothing, essentially putting a matching lower bound on the robustness radius. When restricted to {\it generalized} Gaussian smoothing, these two bounds can be shown to be within a constant factor of each other in an asymptotic sense, establishing that Gaussian smoothing provides the best possible results, up to a constant factor, when $p\ge 2$. We present experimental results on CIFAR to validate our theory. For other smoothing distributions, such as, a uniform distribution within an ${\ell }_1$ or an ${\ell }_{\infty }$-norm ball, we show upper bounds of the form $O(1/d)$ and $O(1/d^{1-\frac{1}{p}})$ respectively, which have an even worse dependence on $d$.

References in corpus (12)

• Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples
• Provable defenses against adversarial examples via the convex outer adversarial polytope
• Adversarial Risk and the Dangers of Evaluating Against Weak Attacks
• On the (Statistical) Detection of Adversarial Examples
• Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
• Semidefinite relaxations for certifying robustness to adversarial examples
• Certified Adversarial Robustness with Additive Noise
• Functional Adversarial Attacks
• Certified Defenses for Adversarial Patches
• (De)Randomized Smoothing for Certifiable Defense against Patch Attacks
• Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers
• Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework

Cited by in corpus (19)

• (De)Randomized Smoothing for Certifiable Defense against Patch Attacks
• Randomized Smoothing of All Shapes and Sizes
• Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework
• Deep Partition Aggregation: Provable Defense against General Poisoning Attacks
• Certifying Confidence via Randomized Smoothing
• Boosting the Certified Robustness of L-infinity Distance Nets
• TSS: Transformation-Specific Smoothing for Robustness Certification
• Fast Certified Robust Training with Short Warmup
• Higher-Order Certification for Randomized Smoothing
• Adversarial robustness via robust low rank representations
• Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations
• Enhancing Certified Robustness via Smoothed Weighted Ensembling
• Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neurons
• Provable Robust Classification via Learned Smoothed Densities
• ANCER: Anisotropic Certification via Sample-wise Volume Maximization
• A Framework of Randomized Selection Based Certified Defenses Against Data Poisoning Attacks
• Building Compact and Robust Deep Neural Networks with Toeplitz Matrices
• Deterministic Certification to Adversarial Attacks via Bernstein Polynomial Approximation
• Hidden Cost of Randomized Smoothing