# Random Smoothing Might be Unable to Certify ℓ_∞ Robustness for High-Dimensional Images

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2020.

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

- [Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspective](https://mlsanity.com/paper/2210.01787/) (2022)
- [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)
- [Boosting the Certified Robustness of L-infinity Distance Nets](https://mlsanity.com/paper/2110.06850/) (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)
- [Run-Off Election: Improved Provable Defense against Data Poisoning Attacks](https://mlsanity.com/paper/2302.02300/) (2023)
- [Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Training](https://mlsanity.com/paper/2201.01965/) (2022)
- [RetrievalGuard: Provably Robust 1-Nearest Neighbor Image Retrieval](https://mlsanity.com/paper/2206.11225/) (2022)
- [Input-agnostic Certified Group Fairness via Gaussian Parameter Smoothing](https://mlsanity.com/paper/2206.11423/) (2022)
- [Interpolated Joint Space Adversarial Training for Robust and Generalizable Defenses](https://mlsanity.com/paper/2112.06323/) (2021)
- [A Law of Robustness beyond Isoperimetry](https://mlsanity.com/paper/2202.11592/) (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)
- [Robustness Certificates for Implicit Neural Networks: A Mixed Monotone Contractive Approach](https://mlsanity.com/paper/2112.05310/) (2021)
- [Building Robust Ensembles via Margin Boosting](https://mlsanity.com/paper/2206.03362/) (2022)
- [A Survey on AI Sustainability: Emerging Trends on Learning Algorithms and Research Challenges](https://mlsanity.com/paper/2205.03824/) (2022)
- [Random Smoothing Regularization in Kernel Gradient Descent Learning](https://mlsanity.com/paper/2305.03531/) (2023)
- [Practical Convex Formulation of Robust One-hidden-layer Neural Network Training](https://mlsanity.com/paper/2105.12237/) (2021)
- [Rethinking Randomized Smoothing from the Perspective of Scalability](https://mlsanity.com/paper/2312.12608/) (2023)
- [Persistent Classification: A New Approach to Stability of Data and Adversarial Examples](https://mlsanity.com/paper/2404.08069/) (2024)
- [Towards Evading the Limits of Randomized Smoothing: A Theoretical Analysis](https://mlsanity.com/paper/2206.01715/) (2022)
- [Towards Better Certified Segmentation via Diffusion Models](https://mlsanity.com/paper/2306.09949/) (2023)
- [Merge Now, Regret Later: The Hidden Cost of Model Merging Is Adversarial Transferability](https://mlsanity.com/paper/2509.23689/) (2025)
- [How robust accuracy suffers from certified training with convex relaxations](https://mlsanity.com/paper/2306.06995/) (2023)
- [Accelerated Smoothing: A Scalable Approach to Randomized Smoothing](https://mlsanity.com/paper/2402.07498/) (2024)
- [Effects of Exponential Gaussian Distribution on (Double Sampling) Randomized Smoothing](https://mlsanity.com/paper/2406.02309/) (2024)
- [Adversarial Robustness Overestimation and Instability in TRADES](https://mlsanity.com/paper/2410.07675/) (2024)
- [Adversarial Defenses via Vector Quantization](https://mlsanity.com/paper/2305.13651/) (2023)

## Abstract (arXiv)

We show a hardness result for random smoothing to achieve certified adversarial robustness against attacks in the ℓp ball of radius ε when p>2. Although random smoothing has been well understood for the ℓ2 case using the Gaussian distribution, much remains unknown concerning the existence of a noise distribution that works for the case of p>2. This has been posed as an open problem by Cohen et al. (2019) and includes many significant paradigms such as the ℓ_∞ threat model. In this work, we show that any noise distribution D over ℝd that provides ℓp robustness for all base classifiers with p>2 must satisfy mathbbEηi2=Omega(d1-2/pε2(1-δ)/δ2) for 99% of the features (pixels) of vector η~D, where ε is the robust radius and δ is the score gap between the highest-scored class and the runner-up. Therefore, for high-dimensional images with pixel values bounded in [0,255], the required noise will eventually dominate the useful information in the images, leading to trivial smoothed classifiers.