# Randomized Smoothing of All Shapes and Sizes

Source: [Randomized Smoothing of All Shapes and Sizes](<https://www.sota2.com/research/paper/68fa680d1e209131cea19df0>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-27T06:03:45.482Z

Authors: Greg Yang, Tony Duan, J. Edward Hu, Hadi Salman, Ilya Razenshteyn, Jerry Li

Published: 2020-02-19T11:41:09.000Z

## 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Certified Robustness on CIFAR-10 (L1 Certified Accuracy Profile)](<https://www.sota2.com/research/sota/certified-robustness-on-cifar-10-l1-certified-accuracy-profile.md>): Certified Robustness; CIFAR-10; Certified Accuracy (L1, R=0.5): 69.8.

- [Certified Robustness on ImageNet](<https://www.sota2.com/research/sota/certified-robustness-on-imagenet.md>): Certified Robustness; ImageNet; Certified Accuracy (L1 R=0.5): 53.6.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2002.08118>)

[PDF](<https://arxiv.org/pdf/2002.08118.pdf>)