# Randomized Smoothing of All Shapes and Sizes

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

## Key facts

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

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

- [SmoothLLM: Defending Large Language Models Against Jailbreaking Attacks](https://mlsanity.com/paper/2310.03684/) (2023)
- [Invisible for both Camera and LiDAR: Security of Multi-Sensor Fusion based Perception in Autonomous Driving Under Physical-World Attacks](https://mlsanity.com/paper/2106.09249/) (2021)
- [Defending Large Language Models against Jailbreak Attacks via Semantic Smoothing](https://mlsanity.com/paper/2402.16192/) (2024)
- [A Dynamical System Perspective for Lipschitz Neural Networks](https://mlsanity.com/paper/2110.12690/) (2021)
- [A Unified Algebraic Perspective on Lipschitz Neural Networks](https://mlsanity.com/paper/2303.03169/) (2023)
- [Relating Adversarially Robust Generalization to Flat Minima](https://mlsanity.com/paper/2104.04448/) (2021)
- [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)
- [SmoothMix: Training Confidence-calibrated Smoothed Classifiers for Certified Robustness](https://mlsanity.com/paper/2111.09277/) (2021)
- [Boosting Randomized Smoothing with Variance Reduced Classifiers](https://mlsanity.com/paper/2106.06946/) (2021)
- [Fast Certified Robust Training with Short Warmup](https://mlsanity.com/paper/2103.17268/) (2021)
- [Certified Patch Robustness via Smoothed Vision Transformers](https://mlsanity.com/paper/2110.07719/) (2021)
- [CROP: Certifying Robust Policies for Reinforcement Learning through Functional Smoothing](https://mlsanity.com/paper/2106.09292/) (2021)
- [Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neurons](https://mlsanity.com/paper/2102.05363/) (2021)
- [On the Certified Robustness for Ensemble Models and Beyond](https://mlsanity.com/paper/2107.10873/) (2021)
- [Improved, Deterministic Smoothing for L_1 Certified Robustness](https://mlsanity.com/paper/2103.10834/) (2021)
- [Scalable Certified Segmentation via Randomized Smoothing](https://mlsanity.com/paper/2107.00228/) (2021)
- [Knowledge Enhanced Machine Learning Pipeline against Diverse Adversarial Attacks](https://mlsanity.com/paper/2106.06235/) (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)
- [Learning Physics-Informed Neural Networks without Stacked Back-propagation](https://mlsanity.com/paper/2202.09340/) (2022)
- [GSmooth: Certified Robustness against Semantic Transformations via Generalized Randomized Smoothing](https://mlsanity.com/paper/2206.04310/) (2022)
- [Double Sampling Randomized Smoothing](https://mlsanity.com/paper/2206.07912/) (2022)
- [Robust Models Are More Interpretable Because Attributions Look Normal](https://mlsanity.com/paper/2103.11257/) (2021)
- [Denoising Masked AutoEncoders Help Robust Classification](https://mlsanity.com/paper/2210.06983/) (2022)
- [Adversarial Training is Not Ready for Robot Learning](https://mlsanity.com/paper/2103.08187/) (2021)
- [StyleFool: Fooling Video Classification Systems via Style Transfer](https://mlsanity.com/paper/2203.16000/) (2022)
- [Provably Unlearnable Data Examples](https://mlsanity.com/paper/2405.03316/) (2024)

## Abstract (arXiv)

Randomized smoothing is the current state-of-the-art defense with provable robustness against ℓ2 adversarial attacks. Many works have devised new randomized smoothing schemes for other metrics, such as ℓ1 or ℓ_∞; 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 ℓ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 ℓp-norm Omega(min(1, d^frac1p - frac12)), when the input dimension d is large. We provide code in github.com/tonyduan/rs4a.