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