Random Smoothing Might be Unable to Certify 𝓁∞ Robustness for High-Dimensional Images

Avrim Blum, Travis Dick, Naren Manoj, Hongyang Zhang

Abstract: 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 $\eta\sim\mathcal{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.

The Quest for Certified Robustness

In the ongoing "arms race" of adversarial machine learning, researchers have increasingly prioritized certified robustness. Unlike empirical defenses, which may be bypassed by novel or adaptive attacks, certified defenses provide a rigorous mathematical guarantee: no perturbation within a specified radius $\epsilon$ can alter the classifier's prediction.

Random smoothing has emerged as a leading technique for providing these guarantees. The process involves taking a standard base classifier, adding random noise (typically Gaussian) to an input image multiple times, and determining the final prediction via a majority vote. This creates a "smoothed" classifier that is inherently resistant to small input variations. While this approach has proven highly effective for $\ell_2$ (Euclidean distance) attacks, its efficacy for $\ell_\infty$ attacks—where an attacker can slightly modify every single pixel—has remained a significant open question in the field.

The Scaling Problem for $\ell_\infty$ Attacks

This research investigates whether any noise distribution exists that can efficiently certify $\ell_\infty$ robustness in high dimensions. The findings suggest a theoretical dead end for the technique as it is currently applied. The authors prove that as image resolution (dimension $d$) increases, the amount of noise required to guarantee $\ell_\infty$ robustness becomes so massive that it eventually drowns out the original image data, rendering the resulting classifier useless.

Theoretical Lower Bounds

Using a framework rooted in Total Variation (TV) distance, the authors derive a lower bound on the expected magnitude of the noise. They demonstrate that for any $\ell_p$ norm where $p > 2$ (which includes the critical $\ell_\infty$ case), the noise variance must grow as a function of the dimension $d$. Specifically, for a smoothed classifier to be robust against a perturbation $v$, the noise distribution must be "approximately translation-invariant," meaning the distribution of the noise must look nearly identical to the distribution of the noise plus the perturbation.

To ensure this result isn't driven by a few extreme pixels, the authors employ a "peeling argument." This technique shows that the high-variance requirement is not an average, but a necessity for at least 99% of the features (pixels) in an image. Furthermore, if one attempts to use independent noise for each pixel, the distribution must be heavy-tailed to provide the necessary certification, which only further increases the likelihood of extreme, image-distorting noise.

The Geometry of High Dimensions

The fundamental issue lies in the geometry of high-dimensional space. In high dimensions, an $\ell_\infty$ ball (essentially a hypercube) has "corners" that are extremely far from the center in terms of Euclidean distance.

As shown in the figure above, the radius required to cover the $\ell_p$ ball grows by a factor of $d^{1/2 - 1/p}$ relative to the $\ell_2$ radius. To protect against a tiny change in every pixel, random smoothing requires a "blur" so large that the underlying semantic information of the image disappears. This identifies a sharp phase transition at $p=2$: for $\ell_1$ and $\ell_2$ attacks, the noise needed for certification can remain constant regardless of image size. However, the moment $p$ exceeds 2, the required noise begins to scale with the dimension $d$.

Empirical Validation

The authors validated these theoretical findings using CIFAR-10 (32x32 images) and upsampled versions of the dataset (48x48 and 64x64). These experiments specifically tested how the "curse of dimensionality" affects certified robustness as the number of pixels increases.

  • Dimensionality Scaling: When testing across different image sizes, the certified accuracy curves collapsed onto each other when scaled by $1/\sqrt{d}$. This perfectly matched the theoretical prediction that the certifiable radius shrinks as the number of pixels grows.
  • Performance Ceiling: On standard CIFAR-10, using state-of-the-art training (TRADES + Smoothing), the authors achieved 62.6% certified $\ell_\infty$ accuracy, but only at a very small radius of 2/255.

Conclusion and Future Directions

This work provides a "hardness result" specifically for random smoothing. It suggests that current "hacks"—such as certifying $\ell_2$ robustness and using mathematical conversion to $\ell_\infty$—are likely near-optimal.

While this doesn't prove $\ell_\infty$ robustness is impossible for all methods, it indicates that random smoothing is likely the wrong tool for high-dimensional $\ell_\infty$ problems. One potential path forward to save the technique may be dimensionality reduction (e.g., using PCA or auto-encoders) before adding noise. By reducing the effective dimension $d$, the noise requirement for certification could be significantly lowered.

Summary updated

Abstract

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 $\eta\sim\mathcal{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.
BibTeX
@article{blum2020random,
  author = {Avrim Blum and Travis Dick and Naren Manoj and Hongyang Zhang},
  title = {{Random Smoothing Might be Unable to Certify 𝓁∞ Robustness for High-Dimensional Images}},
  journal = {J. Mach. Learn. Res.},
  year = {2020},
  url = {https://openreview.net/forum?id=Ee8Qj6cddic},
}
Figure