While "randomized smoothing" has become a gold standard for certifying the robustness of classifiers, it has historically struggled to support models that output complex structures like images, sets, or bounding boxes. This paper introduces Center Smoothing, a novel framework that provides provable robustness guarantees for structured output models. By finding the "center" of a model's predictions under noise, it ensures that adversarial tweaks to an input won't drastically change the resulting output.
The Challenge of Structured Outputs
Adversarial attacks are infamous for making classifiers misidentify a panda as a gibbon using only an imperceptible layer of noise. However, these attacks are just as devastating for "structured" tasks: they can make a face detector miss a person entirely, cause a super-resolution model to hallucinate artifacts, or force a speech-to-text system to output a specific malicious phrase.
The core challenge is that "robustness" is hard to define and certify for these complex tasks. In standard classification, robustness simply means the predicted label doesn't change. But if a model outputs an image or a set of coordinates, what does it mean to be robust? We need a way to prove that if an input changes slightly, the output stays "close" according to a meaningful metric—such as Intersection-over-Union (IoU) for object detection or perceptual similarity for images. Existing certification methods were largely restricted to one-dimensional, real-valued outputs, leaving a massive gap for the complex models used in modern computer vision and NLP.
Methodology: Center Smoothing
The authors build upon Randomized Smoothing, a technique where random noise (usually Gaussian) is added to an input to observe the distribution of the outputs. For a standard classifier, one would take a "majority vote" of these noisy outputs. For structured outputs, the authors propose Center Smoothing:
- Sampling: For a given input $x$, sample multiple points in its neighborhood by adding Gaussian noise.
- Mapping: Pass these noisy inputs through the base model $f$ to get a collection of outputs in the output space.
- Finding the Center: Find the center of the smallest ball in the output space that encloses at least half of these predicted points. This is known as the 1-center problem with outliers.
- Certification: Because finding the absolute smallest ball is NP-hard for general metrics, the authors use a 2-approximation: they find the point in their sample that has the smallest median distance to all other points.
By leveraging the properties of the "minimum enclosing ball," the authors mathematically prove that for any adversarial perturbation within a certain $\ell_2$ radius, the output of this "smoothed" model won't move further than a certified distance $R$ in the output metric space.
Key Insights and Flexibility
- Robustness as a Metric: The core breakthrough is treating the output space as a metric space. Robustness is no longer a binary "correct/incorrect" state; it is a mathematical guarantee on the maximum possible "drift" of the output.
- The Power of Medians: The "center" approach is naturally resistant to outliers. If an adversary manages to make the model produce a wild, nonsensical output for a few noisy samples, those samples fall outside the smallest enclosing ball and do not affect the final smoothed prediction.
- Metric Flexibility: The underlying math applies to any distance function that satisfies (or approximately satisfies) the triangle inequality. This includes IoU for sets, perceptual metrics for images, and Total Variation (TV) distance.
Experimental Validation and Results
The authors evaluated their method across several disparate tasks and datasets, proving that Center Smoothing yields meaningful certificates without significantly degrading the performance of the base model.
- Face Detection (CelebA): The authors certified a face detection model (MTCNN) using the Jaccard distance (1 - IoU) to measure how much a bounding box shifts under attack. They guaranteed that for an input perturbation of $\epsilon = 0.2$, the Jaccard distance remains less than 0.2. In practical terms, the predicted bounding box is guaranteed to maintain at least an 80% overlap with the original, regardless of the attacker's strategy.
- Generative Models (ImageNet): Using BigGAN, they certified generative models under perceptual distance (LPIPS). The smoothed version produces images visually consistent with the original model's output while providing a safety net against latent space attacks.
- Image Reconstruction (MNIST & CIFAR-10): The framework successfully certified autoencoders for dimensionality reduction and reconstruction under Total Variation (TV) distance.
Crucially, the "smoothing error"—the difference in utility between the original model and the robust smoothed model—remained low across all tests.
Limitations and Future Work
While Center Smoothing is a significant step forward, it has limitations. The current work focuses primarily on $\ell_2$-norm bounded adversaries and Gaussian noise; future research could explore other noise distributions to defend against $\ell_\infty$ attacks or geometric transformations like rotations. Additionally, like all randomized smoothing methods, it requires hundreds or thousands of forward passes to compute a single certificate, which can be computationally expensive for massive networks. Finally, because the method relies on a 2-approximation for the 1-center problem, the certified radius might be more conservative than the model's actual robustness, leaving room for tighter bounds in future work.
Summary updated