Provable Robustness against Wasserstein Distribution Shifts via Input Randomization

Aounon Kumar, Alexander Levine, Tom Goldstein, Soheil FeiziICLR 2023 · OpenReview

Overview

This paper introduces a framework to certify the accuracy of machine learning models under distributional shifts. By applying a simple input randomization (smoothing) procedure within a transformation space, the authors provide a mathematical guarantee that a model's performance will remain above a specific threshold for any shift within a bounded Wasserstein distance.

The Challenge of Distributional Shifts

Machine learning models are notoriously brittle. A model trained on clear daytime images might fail when faced with fog, different lighting, or subtle adversarial perturbations. While "empirical" defenses like data augmentation help, they often fail against new, unseen types of shifts—a classic cat-and-mouse game.

The field of certified robustness aims to provide mathematical guarantees that a model will remain accurate. However, most existing work focuses on "instance-wise" robustness (e.g., proving a specific image is robust to a small change in pixels). This paper tackles distributional robustness: how do we guarantee the performance of a model over an entire dataset when the whole distribution shifts (e.g., the average brightness of all test images changes)? Specifically, the authors use the Wasserstein distance to measure these shifts, which is more flexible than traditional metrics because it allows the perturbation size to vary across different samples in the distribution.

Methods: Population-Level Randomized Smoothing

The core idea relies on Randomized Smoothing applied at the population level.

  1. Input Randomization: Instead of a standard model $\mu$, the authors define a robust model $\bar{\mu}$. For any input $x$, the robust model samples a randomized version $x'$ from a "smoothing distribution" $S(x)$ (like adding Gaussian noise in a specific transformation space) and passes that to the base model.
  2. Transformation Spaces: Rather than just adding noise to pixels, they apply randomization to parameters of transformations, such as color balance (RGB scaling), hue, saturation, and brightness.
  3. The Certificate: The authors mathematically prove that the difference in expected performance between the original distribution $D$ and a shifted distribution $\tilde{D}$ is bounded by a concave function $\psi(\epsilon)$, where $\epsilon$ is the Wasserstein distance between the two distributions.
  4. Efficiency: Unlike standard randomized smoothing, which requires thousands of samples to certify a single image, this method can certify the entire distribution using only one sample per input during inference, making it significantly more scalable.

Key Insights and Ideas

  • Lifting Instance-wise to Population-level: The key breakthrough is using Jensen's inequality to show that if you can bound the change in smoothing distributions for any two points, you can bound the change for the entire distribution shift.
  • Non-Vacuous Certificates: In many cases, the certified lower bound of the robust model is actually higher than the empirical accuracy of a standard, undefended model under the same shift. This proves the certificate is practically useful, not just a theoretical curiosity.
Certified accuracy bounds compared to empirical performance under various Wasserstein shifts.
  • Limits of Data Poisoning: The paper applies this framework to "unlearnable" datasets (data poisoned with adversarial noise to prevent models from learning useful features). They show that a robust model is guaranteed to maintain a certain level of accuracy even if the training data is poisoned, revealing a fundamental limitation for researchers trying to create "unlearnable" data for privacy reasons.

Key Results

The authors evaluated their approach on standard benchmarks like CIFAR-10 and SVHN (Street View House Numbers).

  • Natural Transformations: On CIFAR-10, the method achieved a certified accuracy of 78.5% under a color shift ($\epsilon=0.5$) and 87.6% for hue shifts (up to $90^\circ$).
Visual examples of transformations alongside their corresponding Wasserstein distances and certified accuracies.
  • Adversarial Robustness: The framework successfully certified population-level robustness against strategic adversarial attackers, significantly outperforming undefended models.
  • Speed: Computing the distribution-level certificate for $10^5$ samples takes only about 25 seconds on a modern GPU, making it highly practical for large-scale evaluation.

Limitations and Future Work

  • Predefined Metrics: The current certificates rely on predefined distance functions (like $\ell_1$ or $\ell_2$ in the transformation parameter space). These might not perfectly capture "perceptual" shifts that humans find natural but are mathematically complex.
  • Base Model Training: The performance of the robust model depends heavily on the base model being trained with the same type of noise used for smoothing.
  • Future Directions: The authors suggest extending this work to learnable transformations, which would allow certifying robustness against more complex, data-driven distribution shifts used in domain generalization and adaptation.

Summary updated

Abstract

Certified robustness in machine learning has primarily focused on adversarial perturbations with a fixed attack budget for each sample in the input distribution. In this work, we present provable robustness guarantees on the accuracy of a model under bounded Wasserstein shifts of the data distribution. We show that a simple procedure that randomizes the input of the model within a transformation space is provably robust to distributional shifts under that transformation. Our framework allows the datum-specific perturbation size to vary across different points in the input distribution and is general enough to include fixed-sized perturbations as well. Our certificates produce guaranteed lower bounds on the performance of the model for any shift (natural or adversarial) of the input distribution within a Wasserstein ball around the original distribution. We apply our technique to certify robustness against natural (non-adversarial) transformations of images such as color shifts, hue shifts, and changes in brightness and saturation. We obtain strong performance guarantees for the robust model under clearly visible shifts in the input images. Our experiments establish the non-vacuousness of our certificates by showing that the certified lower bound on a robust model's accuracy is higher than the empirical accuracy of an undefended model under a distribution shift. Moreover, our results also imply guaranteed lower bounds (hardness result) on the performance of models trained on so-called "unlearnable" datasets that have been poisoned to interfere with model training. We show that the performance of a robust model is guaranteed to remain above a certain threshold on the test distribution even when the base model is trained on the poisoned dataset.
BibTeX
@inproceedings{kumar2023provable,
  author = {Aounon Kumar and Alexander Levine and Tom Goldstein and Soheil Feizi},
  title = {{Provable Robustness against Wasserstein Distribution Shifts via Input Randomization}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=HJFVrpCaGE},
}
Figure