# Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness

arXiv: https://arxiv.org/abs/2002.03239 · HTML: https://mlsanity.com/paper/2002.03239/

## Key facts

- Cited by 56 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 8 Feb 2020.

## Built on by (most cited first, 30 of 56)

- [Skew Orthogonal Convolutions](https://mlsanity.com/paper/2105.11417/) (2021)
- [A Unified Algebraic Perspective on Lipschitz Neural Networks](https://mlsanity.com/paper/2303.03169/) (2023)
- [Certified Training: Small Boxes are All You Need](https://mlsanity.com/paper/2210.04871/) (2022)
- [Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspective](https://mlsanity.com/paper/2210.01787/) (2022)
- [Boosting Randomized Smoothing with Variance Reduced Classifiers](https://mlsanity.com/paper/2106.06946/) (2021)
- [Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100](https://mlsanity.com/paper/2108.04062/) (2021)
- [Fast Certified Robust Training with Short Warmup](https://mlsanity.com/paper/2103.17268/) (2021)
- [Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neurons](https://mlsanity.com/paper/2102.05363/) (2021)
- [Adversarial Robustness with Semi-Infinite Constrained Learning](https://mlsanity.com/paper/2110.15767/) (2021)
- [Intriguing Properties of Input-dependent Randomized Smoothing](https://mlsanity.com/paper/2110.05365/) (2021)
- [Boosting the Certified Robustness of L-infinity Distance Nets](https://mlsanity.com/paper/2110.06850/) (2021)
- [Your Diffusion Model is Secretly a Certifiably Robust Classifier](https://mlsanity.com/paper/2402.02316/) (2024)
- [ANCER: Anisotropic Certification via Sample-wise Volume Maximization](https://mlsanity.com/paper/2107.04570/) (2021)
- [Double Sampling Randomized Smoothing](https://mlsanity.com/paper/2206.07912/) (2022)
- [Denoising Masked AutoEncoders Help Robust Classification](https://mlsanity.com/paper/2210.06983/) (2022)
- [StyleFool: Fooling Video Classification Systems via Style Transfer](https://mlsanity.com/paper/2203.16000/) (2022)
- [BagFlip: A Certified Defense against Data Poisoning](https://mlsanity.com/paper/2205.13634/) (2022)
- [Provably Unlearnable Data Examples](https://mlsanity.com/paper/2405.03316/) (2024)
- [DeformRS: Certifying Input Deformations with Randomized Smoothing](https://mlsanity.com/paper/2107.00996/) (2021)
- [Run-Off Election: Improved Provable Defense against Data Poisoning Attacks](https://mlsanity.com/paper/2302.02300/) (2023)
- [RetrievalGuard: Provably Robust 1-Nearest Neighbor Image Retrieval](https://mlsanity.com/paper/2206.11225/) (2022)
- [Mitigating the Curse of Dimensionality for Certified Robustness via Dual Randomized Smoothing](https://mlsanity.com/paper/2404.09586/) (2024)
- [Attention! Your Vision Language Model Could Be Maliciously Manipulated](https://mlsanity.com/paper/2505.19911/) (2025)
- [Projected Randomized Smoothing for Certified Adversarial Robustness](https://mlsanity.com/paper/2309.13794/) (2023)
- [A Law of Robustness beyond Isoperimetry](https://mlsanity.com/paper/2202.11592/) (2022)
- [Improved techniques for deterministic l2 robustness](https://mlsanity.com/paper/2211.08453/) (2022)
- [Confidence-aware Training of Smoothed Classifiers for Certified Robustness](https://mlsanity.com/paper/2212.09000/) (2022)
- [It Is All About Data: A Survey on the Effects of Data on Adversarial Robustness](https://mlsanity.com/paper/2303.09767/) (2023)
- [Adaptive Randomized Smoothing: Certified Adversarial Robustness for Multi-Step Defences](https://mlsanity.com/paper/2406.10427/) (2024)
- [ε-weakened Robustness of Deep Neural Networks](https://mlsanity.com/paper/2110.15764/) (2021)

## Abstract (arXiv)

Randomized smoothing, using just a simple isotropic Gaussian distribution, has been shown to produce good robustness guarantees against ℓ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 ℓp-radius that can be certified decreases as O(1/d^frac12 - frac1p) with dimension d for p > 2. Notably, for p ≥ 2, this dependence on d is no better than that of the ℓ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 ≥ 2. We present experimental results on CIFAR to validate our theory. For other smoothing distributions, such as, a uniform distribution within an ℓ1 or an ℓ_∞-norm ball, we show upper bounds of the form O(1 / d) and O(1 / d^1 - frac1p) respectively, which have an even worse dependence on d.