@incollection{icml2020_3289,
abstract = {Randomized smoothing is the current state-of-the-art defense with provable robustness against \textdollar \textbackslash ell\_2\textdollar adversarial attacks. Many works have devised new randomized smoothing schemes for other metrics, such as \textdollar \textbackslash ell\_1\textdollar or \textdollar \textbackslash ell\_\textbackslash infty\textdollar ; 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\textquotesingle s \ast Wulff Crystal\ast ; (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 \ast Banach space cotypes\ast . By combining (1) and (2), we significantly improve the state-of-the-art certified accuracy in \textdollar \textbackslash ell\_1\textdollar 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 \textdollar \textbackslash ell\_p\textdollar -norm \textdollar \textbackslash Omega(\textbackslash min(1, d\^{}\lbrace \textbackslash frac\lbrace 1\rbrace \lbrace p\rbrace - \textbackslash frac\lbrace 1\rbrace \lbrace 2\rbrace \rbrace ))\textdollar , when the input dimension \textdollar d\textdollar is large. We provide code in github.com/tonyduan/rs4a.},
author = {Yang, Greg and Duan, Tony and Hu, J. Edward and Salman, Hadi and Razenshteyn, Ilya and Li, Jerry},
booktitle = {Proceedings of Machine Learning and Systems 2020},
pages = {6043--6055},
title = {Randomized Smoothing of All Shapes and Sizes},
year = {2020}
}