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

Avrim Blum, Travis Dick, Naren Manoj, Hongyang Zhang

TL;DR

This paper proves a fundamental hardness result for random smoothing, a popular technique for certifying adversarial robustness. It shows that for high-dimensional images and $p > 2$ norms, the required noise for certification grows with dimension, eventually overwhelming the image signal and rendering the method ineffective. This implies that current random smoothing approaches may be fundamentally limited for common threat models like $L_\infty$.

What Problem Does This Paper Address?

Adversarial robustness is a critical area in machine learning, aiming to make models resilient to small, malicious perturbations of input data. Certified robustness provides provable guarantees against such attacks. Random smoothing is a leading technique that achieves state-of-the-art certified $L_2$ robustness by adding Gaussian noise and classifying based on the most probable outcome. However, its effectiveness for other norms, particularly the $L_\infty$ norm (which is common in image attacks), remains an open question. This paper addresses the theoretical limitations of random smoothing for certifying robustness in $L_p$ norms when $p > 2$, especially in high-dimensional settings like images.

Methods

The core of the paper's contribution lies in deriving lower bounds on the noise magnitude required for random smoothing to provide certified $L_p$ robustness for $p > 2$. The authors establish a connection between certified robustness and the total variation distance between a distribution and its shifted versions. They prove that for $p > 2$, the expected squared $L_2$ norm of the noise sample must grow with the dimension $d$ of the input space. This is achieved through a series of lemmas and theorems, including:

  • Lemma 2: Relates certified robustness to the total variation distance of the noise distribution.
  • Theorem 3: Provides a lower bound on the expected squared $L_2$ noise magnitude for distributions that are approximately invariant to $L_p$ translations.
  • Theorem 4: Extends this to show that for $p > 2$, at least 99% of the noise components must have a variance that grows with $d^{1-2/p}$, indicating heavy-tailed distributions are required.

The proofs involve techniques like Chebyshev's inequality, Markov's inequality, and a "peeling argument" to analyze the variance of noise components.

Datasets

The paper's theoretical results are general and do not rely on specific datasets. However, the experimental section evaluates certified $L_\infty$ robustness on the CIFAR-10 dataset.

Key Insights and Ideas

  • Phase Transition at p=2: The paper reveals a critical phase transition at $p=2$. For $p < 2$, the required noise magnitude is constant or grows slowly with dimension. However, for $p > 2$, the noise magnitude grows significantly with dimension, making certification increasingly difficult.
  • High-Dimensionality is the Enemy: For high-dimensional data (like images with bounded pixel values), the required noise for $p > 2$ certification can eventually dominate the actual image signal, leading to trivial smoothed classifiers. This means random smoothing might be fundamentally incapable of certifying robustness for common threat models in high dimensions.
  • Heavy-Tailed Noise Required: To achieve any level of robustness for $p > 2$, the noise distribution must be "heavy-tailed," meaning it has a higher probability of generating extreme values. This is in contrast to the Gaussian noise typically used for $L_2$ robustness.
  • $L_p$ Robustness is Harder than $L_2$: The paper shows that defending against $L_p$ attacks (for $p > 2$) using random smoothing is almost as hard as defending against $L_2$ attacks with a radius that scales with $d^{1/2 - 1/p}$.

Key Results

  • Theorem 4: For $p > 2$, any noise distribution $D$ providing $L_p$ robustness must satisfy $E[\eta_i^2] = \Omega(d^{1-2/p} \epsilon^2 (1-\delta)/\delta^2)$ for 99% of the noise components $\eta_i$, where $d$ is the score gap and $\epsilon$ is the robust radius.
  • Experimental Verification: Experiments on CIFAR-10 with a ResNet-110 model show that while TRADES + random smoothing achieves state-of-the-art certified $L_\infty$ robustness (62.6% accuracy at $\epsilon=2/255$), there's still a significant gap to desired robust accuracy. The experiments also empirically support the theoretical finding that the certified $L_\infty$ radius scales with $\sigma/\sqrt{d}$.

Limitations and Future Work

  • Optimality of Bounds: The paper provides lower bounds on the noise magnitude. It is an open question whether these bounds are tight or if they can be improved.
  • Practical Implications for $L_\infty$: The theoretical hardness results suggest that random smoothing might not be the ideal approach for certifying $L_\infty$ robustness in high-dimensional settings.
  • Future Work: The authors suggest combining random smoothing with dimensionality reduction techniques (like PCA or auto-encoders) as a potential avenue to circumvent these hardness results. They also pose the question of whether existing lower bounds can be improved.

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 L∞ Robustness for High-Dimensional Images}},
  journal = {J. Mach. Learn. Res.},
  year = {2020},
  url = {https://openreview.net/forum?id=Ee8Qj6cddic},
}
Figure