%0 Journal Article %1 yang2020randomized %A Yang, Greg %A Duan, Tony %A Hu, J. Edward %A Salman, Hadi %A Razenshteyn, Ilya %A Li, Jerry %D 2020 %K adversarial noise randomized readings robustness %T Randomized Smoothing of All Shapes and Sizes %U http://arxiv.org/abs/2002.08118 %X Randomized smoothing is a recently proposed defense against adversarial attacks that has achieved state-of-the-art provable robustness against $\ell_2$ perturbations. Soon after, a number of works devised new randomized smoothing schemes for other metrics, such as $\ell_1$ or $\ell_ınfty$; however, for each geometry, substantial effort was needed to derive new robustness guarantees. This begs the question: can we find a general theory for randomized smoothing? In this work we propose a novel framework for devising and analyzing randomized smoothing schemes, and validate its effectiveness in practice. Our theoretical contributions are as follows: (1) We show that for an appropriate notion of öptimal", the optimal smoothing distributions for any "nice" norm have level sets given by the *Wulff Crystal* of that norm. (2) We propose two novel and complementary methods for deriving provably robust radii for any smoothing distribution. Finally, (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. On the other hand, using (3), we show that, without more information than label statistics under random input perturbations, randomized smoothing cannot achieve nontrivial certified accuracy against perturbations of $\ell_p$-norm $Ømega(\min(1, d^1p-12))$, when the input dimension $d$ is large. We provide code in github.com/tonyduan/rs4a.

@article{yang2020randomized, abstract = {Randomized smoothing is a recently proposed defense against adversarial attacks that has achieved state-of-the-art provable robustness against $\ell_2$ perturbations. Soon after, a number of works devised new randomized smoothing schemes for other metrics, such as $\ell_1$ or $\ell_\infty$; however, for each geometry, substantial effort was needed to derive new robustness guarantees. This begs the question: can we find a general theory for randomized smoothing? In this work we propose a novel framework for devising and analyzing randomized smoothing schemes, and validate its effectiveness in practice. Our theoretical contributions are as follows: (1) We show that for an appropriate notion of "optimal", the optimal smoothing distributions for any "nice" norm have level sets given by the *Wulff Crystal* of that norm. (2) We propose two novel and complementary methods for deriving provably robust radii for any smoothing distribution. Finally, (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. On the other hand, using (3), we show that, without more information than 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.}, added-at = {2020-03-09T18:26:21.000+0100}, author = {Yang, Greg and Duan, Tony and Hu, J. Edward and Salman, Hadi and Razenshteyn, Ilya and Li, Jerry}, biburl = {https://www.bibsonomy.org/bibtex/276564cff9c94e51484db90d7b92baaf8/kirk86}, description = {[2002.08118] Randomized Smoothing of All Shapes and Sizes}, interhash = {1b31ad1c5f893c72e455d863a7e8fcd9}, intrahash = {76564cff9c94e51484db90d7b92baaf8}, keywords = {adversarial noise randomized readings robustness}, note = {cite arxiv:2002.08118Comment: 9 pages main text, 47 pages total}, timestamp = {2020-06-02T03:57:46.000+0200}, title = {Randomized Smoothing of All Shapes and Sizes}, url = {http://arxiv.org/abs/2002.08118}, year = 2020 }