Non-vacuous Generalization Bounds for Adversarial Risk in Stochastic Neural Networks

Waleed Mustafa, Philipp Liznerski, Antoine Ledent, Dennis Wagner, Puyu Wang, Marius KloftAISTATS 2024 · OpenReview

Introduction

Deep learning models are notoriously fragile when faced with adversarial examples—carefully crafted inputs designed to trick the network. While researchers have developed ways to "certify" robustness for individual images, a significant gap remains: we lack a way to guarantee how a model will perform on an entire unseen population of data under attack.

In theoretical machine learning, "generalization bounds" are used to predict this performance. However, most existing bounds for deep learning are "vacuous," meaning they produce values greater than 1.0. If a bound tells you your error rate is less than 150%, it provides zero practical information. This research addresses the challenge of creating tight, informative bounds (e.g., an error rate < 20%) specifically for adversarial settings.

Theoretical Framework: PAC-Bayes and Randomized Smoothing

The authors bridge two powerful frameworks to achieve non-vacuous bounds:

  1. PAC-Bayesian Analysis: Instead of looking at a single set of weights, the network is treated as a "stochastic" model where weights are drawn from a distribution. The "population risk" (performance on unseen data) is bounded using the "empirical risk" (performance on training data) plus a complexity term based on the Kullback-Leibler (KL) divergence between a prior and posterior distribution of weights.
  2. Randomized Smoothing (RS): This technique adds noise to the input at inference time to create a "smoothed" classifier that is provably robust to small perturbations.

The core innovation is a new Robust Loss function ($\tilde{\ell}$). This loss incorporates the "margin" of the smoothed classifier. If the model is correct but "barely" so (low confidence), the robust loss treats it as a failure, anticipating that an adversary could easily flip the prediction.

The authors also provide a practical training algorithm, Adversarial PAC-Bayes, which optimizes the network specifically to minimize these theoretical bounds, effectively "training for certification."

Experimental Results

The approach was evaluated on standard computer vision benchmarks: MNIST and CIFAR-10. The authors successfully produced the first robust risk certificates for stochastic convolutional neural networks under the $L_2$ threat model.

Non-Vacuous and Tight Bounds

On both MNIST and CIFAR-10, the calculated bounds were well below 1.0, often tracking the actual test-set performance quite closely. This scalability is notable; the method works even for deep architectures with tens of millions of parameters, where previous bounding methods failed completely.

Figure 1: Certified 0-1 loss vs. perturbation radius R without adversarial training. The theoretical risk bound (blue) closely tracks the test data performance (green).

Impact of Adversarial Training

Surprisingly, training with adversarial examples (like PGD attacks) doesn't just help empirical robustness; it actually helps the theoretical bounds stay tight. This suggests that KL regularization and adversarial training are complementary.

Figure 2: Certified 0-1 loss vs. perturbation radius R with adversarial training. Note the lower overall loss and tighter gap between the bound and test performance compared to the non-adversarial case.

Key Insights

  • Smoothing as a Regularizer: Randomized smoothing is the primary factor behind achieving non-trivial bounds. It effectively "tames" the landscape of the loss function, making it easier to provide theoretical guarantees.
  • Complexity Measures: Traditional theory suggests larger models generalize worse due to parameter count. This work shows that using KL divergence as a complexity measure allows deeper networks (like a 41M-parameter VGG-like model) to achieve tight bounds.
  • Data-Dependent Priors: Learning a "prior" on a subset of the data before calculating the bound on the remainder significantly reduces the generalization gap.

Limitations and Future Directions

While a major step forward, the method has limitations:

  • Computational Cost: Training these self-certified models is expensive (e.g., 30 hours on 8 A100 GPUs for CIFAR-10).
  • Hyperparameter Sensitivity: Bounds are sensitive to the choice of prior variance ($\Sigma_0$).
  • Threat Model Scope: Currently focused on $L_2$ perturbations; extending to $L_\infty$ or other attacks remains an open challenge.

Summary updated

Abstract

Adversarial examples are manipulated samples used to deceive machine learning models, posing a serious threat in safety-critical applications. Existing safety certificates for machine learning models are limited to individual input examples, failing to capture generalization to unseen data. To address this limitation, we propose novel generalization bounds based on the PAC-Bayesian and randomized smoothing frameworks, providing certificates that predict the model’s performance and robustness on unseen test samples based solely on the training data. We present an effective procedure to train and compute the first non-vacuous generalization bounds for neural networks in adversarial settings. Experimental results on the widely recognized MNIST and CIFAR-10 datasets demonstrate the efficacy of our approach, yielding the first robust risk certificates for stochastic convolutional neural networks under the $L_2$ threat model. Our method offers valuable tools for evaluating model susceptibility to real-world adversarial risks.
BibTeX
@inproceedings{mustafa2024non,
  author = {Waleed Mustafa and Philipp Liznerski and Antoine Ledent and Dennis Wagner and Puyu Wang and Marius Kloft},
  title = {{Non-vacuous Generalization Bounds for Adversarial Risk in Stochastic Neural Networks}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=Ieeru9GRpC},
}
Figure