Abstract
Randomized smoothing has been successfully applied to classification tasks on high-dimensional inputs, such as images, to obtain models that are provably robust against adversarial perturbations of the input. We extend this technique to produce provable robustness for functions that map inputs into an arbitrary metric space rather than discrete classes. Such functions are used in many machine learning problems like image reconstruction, dimensionality reduction, facial recognition, etc. Our robustness certificates guarantee that the change in the output of the smoothed model as measured by the distance metric remains small for any norm-bounded perturbation of the input. We can certify robustness under a variety of different output metrics, such as total variation distance, Jaccard distance, perceptual metrics, etc. In our experiments, we apply our procedure to create certifiably robust models with disparate output spaces -- from sets to images -- and show that it yields meaningful certificates without significantly degrading the performance of the base model.
Introduction
Adversarial attacks—tiny, often imperceptible changes to an input that cause a model to fail—are a well-documented threat to machine learning. While robust defenses exist for classification tasks where the output is a discrete label, many critical real-world applications involve complex, continuous outputs. For instance, an adversarial attack on an MRI reconstruction model might add a non-existent tumor, or a perturbation to a face detection system might cause a bounding box to disappear.
Existing provable defenses like randomized smoothing typically rely on a "majority vote" mechanism, which does not naturally translate to continuous spaces. If a model outputs an image, there is no "most frequent" image to select. This paper addresses this gap by introducing Center Smoothing, a framework to certify the robustness of functions mapping inputs into arbitrary metric spaces where distances between outputs can be measured.
Methodology: The Center Smoothing Procedure
The core innovation of this work is the generalization of randomized smoothing through geometric centering. The process follows three main steps:
- Randomized Sampling: For a given input $x$, the method samples multiple points from a Gaussian distribution around it ($x + \delta$).
- Geometric Centering: Instead of a majority vote, the method computes the function $f$ on all sampled points and identifies the "center" of the output distribution. Specifically, it finds the center of the smallest ball in the output metric space that encloses at least half of the output points.
- Certification: The authors prove that if the input is perturbed by a small amount (measured by an $\ell_2$ norm), the distance between the original smoothed output and the perturbed smoothed output is bounded by a constant factor of the radius of that enclosing ball.
To handle high-dimensional outputs like high-resolution images, the authors introduce Smooth-HD. Since finding the exact 1-center of a set of points is computationally expensive, this variant uses a "median distance" approach among a small set of candidate centers. This makes the computation feasible and memory-efficient while maintaining the robustness guarantees. Furthermore, the framework is flexible enough to support pseudometrics and distances that satisfy a relaxed triangle inequality, such as cosine distance or perceptual metrics.
Experiments and Datasets
The authors evaluated Center Smoothing across several tasks and datasets to demonstrate its versatility:
- CelebA: Used for certifying face detection (MTCNN model) using Jaccard distance (1 - Intersection over Union) for bounding boxes.
- ImageNet: Used for certifying generative models (BigGAN) using the LPIPS perceptual metric.
- MNIST & CIFAR-10: Used for dimensionality reduction (autoencoders) and image reconstruction tasks, evaluated using Total Variation (TV) distance.
Key Results
The experimental results confirm that Center Smoothing provides meaningful certificates across disparate output spaces. For face detection, at a perturbation level of $\epsilon = 0.2$, the method could certify that a bounding box would maintain at least an 80% overlap (IoU) with the original. In the realm of image generation, the authors provided the first perceptual robustness certificates for BigGAN, proving that the visual "look and feel" of a generated image remains stable under attack.
On reconstruction tasks using MNIST and CIFAR-10, the "smoothing error" (the distance between the base model and the smoothed version) remained significantly lower than the certified bound. This suggests that the safety guarantees provided by center smoothing do not come at the cost of total utility, as the smoothed model's output remains very close to the original clean model's output.
Discussion and Limitations
While Center Smoothing represents a significant step forward, several challenges remain. The computational overhead is notable; certifying a single example can take several minutes on a high-end GPU. Additionally, the certificates are inherently conservative; the actual error observed in practice is often much smaller than the certified radius, suggesting the bounds might be loose.
Current work is also limited to $\ell_2$-norm bounded adversarial perturbations. Extending these guarantees to $\ell_\infty$ norms or non-norm-based attacks, such as rotations or translations, remains an open area for future research. Finally, the quality of the certificate is heavily dependent on the chosen output metric, highlighting the ongoing need for task-specific metrics that accurately capture human-perceived similarity.
Summary updated