Center Smoothing for Certifiably Robust Vector-Valued Functions

Aounon Kumar, Tom Goldstein

Abstract

The study of provable adversarial robustness has mostly been limited to classification tasks and models with one-dimensional real-valued outputs. We extend the scope of certifiable robustness to problems with more general and structured outputs like sets, images, language, etc. We model the output space as a metric space under a distance/similarity function, such as intersection-over-union, perceptual similarity, total variation distance, etc. Such models are used in many machine learning problems like image segmentation, object detection, generative models, image/audio-to-text systems, etc. Based on a robustness technique called randomized smoothing, our $\textit{center smoothing}$ procedure can produce models with the guarantee that the change in the output, as measured by the distance metric, remains small for any norm-bounded adversarial perturbation of the input. We apply our method 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. Code for our experiments is available at: https://github.com/aounon/center-smoothing.

Introduction: Robustness Beyond Labels

While adversarial robustness research has traditionally focused on classification—ensuring a predicted label remains constant under small input perturbations—many real-world AI tasks involve complex, structured outputs. Face detectors output bounding boxes, generative models produce high-resolution images, and translation systems generate sequences of text. In these scenarios, an adversary's goal may not be to flip a discrete label, but to distort the output in a way that degrades performance or introduces dangerous hallucinations.

Until recently, we lacked a general framework to provide mathematical guarantees (certificates) for such models. Center Smoothing addresses this gap by providing a way to certify that the output of a model will remain within a specific distance of its original prediction, even when the input is subjected to a bounded adversarial attack.

The Center Smoothing Framework

Center Smoothing builds upon the established technique of Randomized Smoothing. In standard classification smoothing, one takes an input, adds random Gaussian noise multiple times, and selects the most frequent output class. However, for structured outputs like images, every noisy sample might be unique, making "most frequent" an inapplicable criterion.

Center Smoothing generalizes this by treating the output space as a metric space. The process involves:

  1. Sampling: Generating multiple noisy versions of an input $x$.
  2. Mapping: Passing these noisy inputs through the base model $f$ to obtain a set of outputs in the metric space.
  3. Finding the Center: Identifying the "center" of the smallest ball that contains at least 50% of these output points.
  4. Certification: Leveraging the properties of Gaussian distributions to prove that if the input is perturbed by $\epsilon$, the smoothed output $\bar{f}(x)$ will not move further than a certified radius $R$.
Conceptual overview of Center Smoothing: mapping noisy inputs to a metric output space and finding the smoothed center.

To overcome the NP-completeness of finding the absolute smallest ball (the 1-center problem), the authors utilize a 2-approximation algorithm: selecting the sample point with the smallest median distance to all other points in the set.

Empirical Evaluation

The effectiveness of Center Smoothing was evaluated across several diverse tasks:

  • Face Detection (CelebA): Using the MTCNN model to certify the stability of bounding boxes under Jaccard distance (Intersection over Union).
  • Generative Modeling (ImageNet): Using BigGAN to certify the perceptual similarity of generated images using the LPIPS metric.
  • Image Reconstruction (MNIST & CIFAR-10): Using autoencoders to certify stability under Total Variation distance.
Certifying Jaccard Distance for face detection and examples of smoothed bounding box outputs.

In the face detection task, for example, the method could guarantee that under an $L_2$ attack of $\epsilon = 0.2$, the resulting bounding box would maintain at least an 80% overlap (IoU) with the original prediction. Crucially, the "smoothing error" remained low, indicating that robustness does not come at the cost of significant performance degradation.

Key Insights and Future Directions

Center Smoothing introduces several critical concepts to the field of robustness:

  • Proximity over Constancy: It shifts the goal from certifying that an output never changes to certifying that it remains close to the original.
  • Metric Agnosticism: The framework is flexible enough to work with almost any distance function, including non-standard pseudometrics.
  • Robustness to Outliers: By focusing on the 50% mass of predictions, the model is naturally resistant to outlier predictions that an attacker might attempt to induce.

Despite its strengths, challenges remain. Like other randomized smoothing methods, it is computationally intensive, requiring thousands of forward passes per certificate. Future work may explore extending the theory beyond $L_2$-norm perturbations to include rotations or $L_\infty$ attacks.

Summary updated

Abstract

The study of provable adversarial robustness has mostly been limited to classification tasks and models with one-dimensional real-valued outputs. We extend the scope of certifiable robustness to problems with more general and structured outputs like sets, images, language, etc. We model the output space as a metric space under a distance/similarity function, such as intersection-over-union, perceptual similarity, total variation distance, etc. Such models are used in many machine learning problems like image segmentation, object detection, generative models, image/audio-to-text systems, etc. Based on a robustness technique called randomized smoothing, our $\textit{center smoothing}$ procedure can produce models with the guarantee that the change in the output, as measured by the distance metric, remains small for any norm-bounded adversarial perturbation of the input. We apply our method 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. Code for our experiments is available at: https://github.com/aounon/center-smoothing.
BibTeX
@inproceedings{kumar2021center,
  author = {Aounon Kumar and Tom Goldstein},
  title = {{Center Smoothing for Certifiably Robust Vector-Valued Functions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=sxjpM-kvVv_},
}
Figure