We show a hardness result for random smoothing to achieve certified adversarial robustness against attacks in the $ell_p$ ball of radius $epsilon$ when $p>2$. Although random smoothing has been well understood for the $ell_2$ case using the Gaussian distribution, much remains unknown concerning the existence of a noise distribution that works for the case of $p>2$. This has been posed as an open problem by Cohen et al. (2019) and includes many significant paradigms such as the $ell_infty$ threat model. In this work, we show that any noise distribution $mathcal{D}$ over $mathbb{R}^d$ that provides $ell_p$ robustness for all base classifiers with $p>2$ must satisfy $mathbb{E}eta_i^2=Omega(d^{1-2/p}epsilon^2(1-delta)/delta^2)$ for 99% of the features (pixels) of vector $etasimmathcal{D}$, where $epsilon$ is the robust radius and $delta$ is the score gap between the highest-scored class and the runner-up. Therefore, for high-dimensional images with pixel values bounded in $[0,255]$, the required noise will eventually dominate the useful information in the images, leading to trivial smoothed classifiers.
Download