A Framework for robustness Certification of Smoothed Classifiers using F-Divergences.

Krishnamurthy Dj Dvijotham, Jamie Hayes, Borja Balle, Zico Kolter, Chongli Qin, András György, Kai Xiao, Sven Gowal, Pushmeet KohliICLR 2020 · OpenReview

Introduction

Deep learning models are notoriously fragile; tiny, imperceptible "adversarial perturbations" to an input can cause a model to completely flip its prediction. To combat this vulnerability, researchers developed randomized smoothing, a technique that classifies the "average" prediction of a model under random noise centered at a given input. This approach is powerful because it treats the model as a black box, requiring no knowledge of its internal architecture.

However, previous randomized smoothing methods were highly fragmented. This paper introduces a generalized framework that uses the mathematical language of f-divergences to certify robustness for any smoothing distribution and any perturbation. By doing so, it significantly outperforms previous methods in both computational speed and the tightness of its safety guarantees.

The Limitations of Prior Defenses

Historically, randomized smoothing was limited in scope. Most implementations only worked with Gaussian noise to defend against $\ell_2$ (Euclidean) distance attacks. Defending against different types of attacks—such as $\ell_0$ "pixel-flipping" or $\ell_1$ attacks—or using different noise distributions required deriving entirely new mathematical proofs from scratch.

Furthermore, most existing methods were "information-limited." They only looked at the probability of the "winning" class, throwing away valuable information contained in the rest of the model's output distribution (the soft scores).

Comparison of the proposed framework against prior randomized smoothing methods, highlighting its ability to handle arbitrary distributions and norms in O(1) time.

A Unified Method: The f-Divergence Bridge

The authors reframe the robustness certification problem as a convex optimization problem over probability measures. Their key innovation is the use of f-divergences—a family of functions that measure the "distance" between two probability distributions, which includes well-known metrics like KL-divergence and "Hockey-Stick" divergence.

Instead of trying to track how an adversarial perturbation moves a specific point in a high-dimensional space, the framework tracks how the perturbation moves the distribution of the noise. If the distribution of noise around a perturbed point $x'$ is "close enough" (measured via f-divergence) to the noise around the original point $x$, the model's prediction is mathematically guaranteed to stay the same.

Theoretical illustration of bounding the perturbation set using f-divergences within the space of probability measures.

Full-Information vs. Information-Limited

A major advantage of this framework is its ability to utilize Full-Information. While prior work only used the probability that the model predicts the correct label, this new approach leverages the entire distribution of the model’s soft outputs (the scores for every class). The authors prove that incorporating this extra data always results in a tighter, more robust guarantee.

To make this practical, the authors provide a recipe to turn these theoretical bounds into a certification procedure that can be solved using standard convex optimization toolkits.

Key Results and Performance

The authors evaluated their framework across multiple domains, including image classification (MNIST, CIFAR-10, ImageNet) and audio classification (Librispeech).

  • The "Full-Info" Advantage: By looking at the soft scores rather than just the hard label, the framework proves models are robust to much larger attacks. On ImageNet, the full-info certificate proved robustness for a radius of 9.42, whereas the standard info-limited method could only manage 2.69 for the same point.
  • Massive Computational Speedups: For $\ell_0$ (sparsity) robustness, the method is orders of magnitude faster than previous state-of-the-art techniques. On ImageNet, it achieved a staggering 20 million times speedup compared to prior specialized $\ell_0$ certification methods, while remaining nearly as tight as optimal (but slower) approaches.
  • Audio Robustness: The framework successfully certified speaker identification models against "missing data" attacks, where parts of an audio signal are zeroed out. This marks a significant milestone: the first time a certifiably robust model was produced for an audio task with variable-length inputs.

Limitations and Future Work

While highly effective, the framework does have practical limitations:

  • Sampling Cost: Like all randomized smoothing methods, estimating class probabilities accurately requires running the model thousands of times. This makes inference time during the certification process quite high.
  • Hyperparameter Tuning: The choice of the smoothing distribution (e.g., noise variance) and the specific f-divergence used significantly impacts the results. Finding the optimal noise for a specific dataset still requires empirical trial and error.
  • Complex Perturbations: The framework is mathematically general, but calculating the maximum f-divergence for complex, non-norm-based perturbations—such as 3D rotations or lighting changes—remains an open mathematical challenge.

Summary updated

Abstract

Formal verification techniques that compute provable guarantees on properties of machine learning models, like robustness to norm-bounded adversarial perturbations, have yielded impressive results. Although most techniques developed so far require knowledge of the architecture of the machine learning model and remain hard to scale to complex prediction pipelines, the method of randomized smoothing has been shown to overcome many of these obstacles. By requiring only black-box access to the underlying model, randomized smoothing scales to large architectures and is agnostic to the internals of the network. However, past work on randomized smoothing has focused on restricted classes of smoothing measures or perturbations (like Gaussian or discrete) and has only been able to prove robustness with respect to simple norm bounds. In this paper we introduce a general framework for proving robustness properties of smoothed machine learning models in the black-box setting. Specifically, we extend randomized smoothing procedures to handle arbitrary smoothing measures and prove robustness of the smoothed classifier by using f-divergences. Our methodology improves upon the state of the art in terms of computation time or certified robustness on several image classification tasks and an audio classification task, with respect to several classes of adversarial perturbations.
BibTeX
@inproceedings{dvijotham2020framework,
  author = {Krishnamurthy Dj Dvijotham and Jamie Hayes and Borja Balle and Zico Kolter and Chongli Qin and András György and Kai Xiao and Sven Gowal and Pushmeet Kohli},
  title = {{A Framework for robustness Certification of Smoothed Classifiers using F-Divergences.}},
  booktitle = {ICLR},
  year = {2020},
  url = {https://openreview.net/forum?id=yLO9R2Vx5y6},
}
Figure