@incollection{icml2020_3044,
abstract = {Randomized smoothing, using just a simple isotropic Gaussian distribution, has been shown to produce good robustness guarantees against \textdollar \textbackslash ell\_2\textdollar -norm bounded adversaries. In this work, we show that extending the smoothing technique to defend against other attack models can be challenging, especially in the high-dimensional regime. In particular, for a vast class of i.i.d.\textasciitilde smoothing distributions, we prove that the largest \textdollar \textbackslash ell\_p\textdollar -radius that can be certified decreases as \textdollar O(1/d\^{}\lbrace \textbackslash frac\lbrace 1\rbrace \lbrace 2\rbrace - \textbackslash frac\lbrace 1\rbrace \lbrace p\rbrace \rbrace )\textdollar with dimension \textdollar d\textdollar for \textdollar p > 2\textdollar . Notably, for \textdollar p \textbackslash geq 2\textdollar , this dependence on \textdollar d\textdollar is no better than that of the \textdollar \textbackslash ell\_p\textdollar -radius that can be certified using isotropic Gaussian smoothing, essentially putting a matching lower bound on the robustness radius.
When restricted to \lbrace \textbackslash it generalized\rbrace Gaussian smoothing, these two bounds can be shown to be within a constant factor of each other in an asymptotic sense, establishing that Gaussian smoothing provides the best possible results, up to a constant factor, when \textdollar p \textbackslash geq 2\textdollar . We present experimental results on CIFAR to validate our theory.
For other smoothing distributions, such as, a uniform distribution within an \textdollar \textbackslash ell\_1\textdollar or an \textdollar \textbackslash ell\_\textbackslash infty\textdollar -norm ball, we show upper bounds of the form \textdollar O(1 / d)\textdollar and \textdollar O(1 / d\^{}\lbrace 1 - \textbackslash frac\lbrace 1\rbrace \lbrace p\rbrace \rbrace )\textdollar respectively, which have an even worse dependence on \textdollar d\textdollar .
},
author = {Kumar, Aounon and Levine, Alexander and Goldstein, Tom and Feizi, Soheil},
booktitle = {Proceedings of Machine Learning and Systems 2020},
pages = {5567--5576},
title = {Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness},
year = {2020}
}