Random Smoothing Might be Unable to Certify ℓ_∞ Robustness for High-Dimensional Images
share
We show a hardness result for random smoothing to achieve certified adversarial robustness against attacks in the ℓ_p ball of radius ϵ when p>2. Although random smoothing has been well understood for the ℓ_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 ℓ_∞ threat model. In this work, we show that under certain regularity conditions, any noise distribution D over R^d that provides ℓ_p robustness with p>2 must satisfy Eη_i^2=Ω(d^1-2/pϵ^2/δ^2) for 99 features (pixels) of vector η drawn from D, where ϵ is the robust radius and δ measures the score gap between the highest score 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.
READ FULL TEXT