Provably Robust Detection of Out-of-distribution Data (almost) for free

Alexander Meinke, Julian Bitterwolf, Matthias Hein

Abstract

The application of machine learning in safety-critical systems requires a reliable assessment of uncertainty. However, deep neural networks are known to produce highly overconfident predictions on out-of-distribution (OOD) data. Even if trained to be non-confident on OOD data, one can still adversarially manipulate OOD data so that the classifier again assigns high confidence to the manipulated samples. We show that two previously published defenses can be broken by better adapted attacks, highlighting the importance of robustness guarantees around OOD data. Since the existing method for this task is hard to train and significantly limits accuracy, we construct a classifier that can simultaneously achieve provably adversarially robust OOD detection and high clean accuracy. Moreover, by slightly modifying the classifier's architecture our method provably avoids the asymptotic overconfidence problem of standard neural networks. We provide code for all our experiments.

The Challenge of Overconfident Networks

Deep Neural Networks (DNNs) are notoriously overconfident. When encountering data that does not belong to any of their trained classes (Out-of-Distribution or OOD data), they often assign high-probability labels instead of signaling uncertainty. While techniques like "Outlier Exposure" (training on diverse non-task images) help, they remain vulnerable to adversarial OOD attacks. In these scenarios, an attacker can slightly perturb an OOD image—making changes invisible to humans—to trick the model into high-confidence misclassification.

Previous attempts to provide "provable" robustness (mathematical certainty that no such perturbation can trick the model) often incurred a heavy "accuracy tax," significantly degrading performance on normal, clean data. Furthermore, standard ReLU-based networks suffer from a structural flaw: their confidence tends to increase as inputs move further away from the training distribution toward infinity.

The ProoD Framework

To solve these issues, the authors introduce ProoD (Provable out-of-Distribution detector). ProoD utilizes a two-component joint architecture designed to decouple standard classification from safety-critical OOD detection.

The ProoD architecture uses a dual-model approach to maintain high accuracy while providing certified OOD detection.

Key Innovations

  1. Dual-Component Architecture: ProoD combines a standard high-performance classifier (e.g., ResNet) with a smaller, Certified Binary Discriminator. The discriminator is trained specifically to distinguish between "In-distribution" and "Out-distribution" data.
  2. Interval Bound Propagation (IBP): The binary discriminator is trained using IBP, a technique that calculates the worst-case output for any possible small perturbation within a defined range ($l_\infty$-ball). This allows the model to provide a mathematical "certificate" of low confidence for OOD samples.
  3. Fixing Asymptotic Overconfidence: By enforcing strictly negative weights in the discriminator's final output layer, the authors prove that the model's confidence must drop to a random-guess level ($1/K$) as the input moves toward infinity.
  4. Semi-Joint Training: The discriminator is trained first and kept fixed. The classifier is then trained to be low-confidence only in areas where the discriminator is uncertain. This decoupling allows the classifier to maintain state-of-the-art accuracy without being hindered by the mathematical constraints required for the discriminator's proof.

Experimental Results

ProoD was evaluated across standard benchmarks including CIFAR-10, CIFAR-100, and Restricted ImageNet, using OOD sets like SVHN, LSUN, and various noise patterns.

Comparison of ProoD against existing OOD detection methods across key performance and safety metrics.

Key Insights

  • No Accuracy Loss: On CIFAR-10, ProoD maintains ~95% accuracy, matching standard non-robust models. In contrast, previous provable methods like GOOD dropped to ~91% or lower.
  • Provable Safety: ProoD achieves significant Guaranteed AUC (GAUC). For example, on CIFAR-10 vs. SVHN, it guarantees an AUC of 53.3% against any possible adversarial attack, whereas standard models drop to 0% under attack.
  • Scalability: ProoD is the first method to provide worst-case OOD guarantees on high-resolution images (Restricted ImageNet), demonstrating that robust OOD detection can scale beyond small datasets.

Conclusion

ProoD demonstrates that provable adversarial robustness for OOD detection does not have to come at the cost of clean classification accuracy. By separating the safety check into a dedicated, certified discriminator and fixing the asymptotic overconfidence of ReLU networks, ProoD provides a scalable and effective framework for safer machine learning deployment.

Summary updated

Abstract

The application of machine learning in safety-critical systems requires a reliable assessment of uncertainty. However, deep neural networks are known to produce highly overconfident predictions on out-of-distribution (OOD) data. Even if trained to be non-confident on OOD data, one can still adversarially manipulate OOD data so that the classifier again assigns high confidence to the manipulated samples. We show that two previously published defenses can be broken by better adapted attacks, highlighting the importance of robustness guarantees around OOD data. Since the existing method for this task is hard to train and significantly limits accuracy, we construct a classifier that can simultaneously achieve provably adversarially robust OOD detection and high clean accuracy. Moreover, by slightly modifying the classifier's architecture our method provably avoids the asymptotic overconfidence problem of standard neural networks. We provide code for all our experiments.
BibTeX
@inproceedings{meinke2022provably,
  author = {Alexander Meinke and Julian Bitterwolf and Matthias Hein},
  title = {{Provably Robust Detection of Out-of-distribution Data (almost) for free}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=YfU5WTpv97},
}
Figure