Center Smoothing: Certified Robustness for Networks with Structured Outputs

Aounon Kumar, Tom Goldstein

TL;DR

This paper introduces "center smoothing," a novel technique to provide provable adversarial robustness for machine learning models with complex, structured outputs (like images or sets), not just simple class labels. It extends the popular randomized smoothing method to a broader range of problems, offering guarantees that outputs remain consistent under adversarial attacks, measured by various distance metrics.

What Problem Does This Paper Address?

Adversarial attacks, where tiny input perturbations cause drastic output changes, are a significant threat to the reliability of machine learning systems, especially in critical applications. While much research has focused on defending image classifiers, many real-world ML tasks involve more complex outputs like object bounding boxes, image segmentations, or generated text. Existing robustness guarantees are often limited to these simpler classification scenarios, leaving a gap for more general structured output problems. This paper aims to bridge that gap by providing a method for certifying robustness in these more complex output spaces.

Methods

The core contribution is center smoothing, an extension of randomized smoothing. Standard randomized smoothing involves adding noise to the input and averaging the outputs to get a robust prediction. Center smoothing adapts this by:

  • Modeling the Output Space as a Metric Space: It treats the model's output as a point in a metric space, where distances are defined by relevant similarity measures (e.g., Jaccard distance for sets, total variation for images).
  • Center of the Minimum Enclosing Ball: Instead of averaging, center smoothing finds the "center" of the smallest ball that encloses at least half of the noisy outputs. This "center" is the robust prediction. This is inspired by the 1-center problem with outliers.
  • Provable Guarantees: The method provides theoretical guarantees that for a given input perturbation size ($\epsilon_1$), the output change, measured by the chosen distance metric, will be bounded by a certain value ($\epsilon_2$). This guarantee holds with high probability.
  • Relaxed Metric Requirements: The technique is flexible and can work with pseudometrics (which might not satisfy the identity of indiscernibles property), broadening its applicability.

Datasets

The paper uses standard datasets for evaluation, including:

  • CelebA: For face detection (Jaccard distance).
  • ImageNet: For generative models (perceptual distance).
  • MNIST: For dimensionality reduction and image reconstruction (total variation distance, angular distance).
  • CIFAR-10: For dimensionality reduction and image reconstruction (total variation distance, angular distance).

Key Insights and Ideas

  • Robustness Beyond Classification: The most significant insight is that provable adversarial robustness can be extended beyond simple classification to a wide array of structured output tasks, which are more representative of real-world ML applications.
  • Center Smoothing as a Generalization: By framing the problem in terms of metric spaces and using the minimum enclosing ball concept, center smoothing offers a unified approach for certifying robustness across diverse output types.
  • Flexibility of Distance Metrics: The method's ability to work with various distance metrics (Jaccard, total variation, perceptual, angular) is crucial. It shows that the choice of metric directly influences the type of robustness guarantee obtained.
  • Trade-off Between Robustness and Performance: While the goal is robustness, the paper demonstrates that center smoothing can achieve this without significantly degrading the performance of the base model, as evidenced by low smoothing errors.

Key Results

The paper demonstrates the effectiveness of center smoothing across several applications:

  • Face Detection: Certified robustness for bounding box predictions using Jaccard distance (1-IoU). For an input perturbation of $\epsilon_1=0.2$, the output Jaccard distance is bounded by 0.2, meaning the predicted bounding box maintains at least 80% overlap with the clean output.
  • Generative Models: Certified perceptual distance for generated images. While the certified output radius can be larger for high-dimensional outputs, the smoothing error remains low.
  • Dimensionality Reduction & Image Reconstruction: Achieved certified robustness using total variation and angular distances on MNIST and CIFAR-10 datasets. The certified output radii were consistently below theoretical bounds, indicating meaningful certificates.
  • Efficiency: The paper introduces a "Smooth-HD" variant for high-dimensional outputs that significantly reduces computational and memory requirements.

Limitations and Future Work

  • Metric Requirements: While relaxed, the method still relies on properties like symmetry and approximate triangle inequality for the distance metric.
  • Threat Models: The current work focuses on $\ell_2$-norm bounded adversaries and Gaussian smoothing. Future work could explore generalizing to other threat models (e.g., total variation, perceptual distance) and smoothing distributions.
  • High-Dimensional Outputs: While Smooth-HD addresses some challenges, certifying very high-dimensional outputs remains computationally intensive.
  • Training with Noise: The paper notes that training models with noise can improve robustness certificates, suggesting further investigation into optimal training strategies.

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: Certified Robustness for Networks with Structured Outputs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=sxjpM-kvVv_},
}
Figure