Sketching curvature for efficient out-of-distribution detection for deep neural networks

Apoorva Sharma, Navid Azizan, Marco Pavone

Abstract

Deep Neural Networks (DNNs) are often prone to overconfidence when encountering out-of-distribution (OoD) data, which presents significant risks in safety-critical deployments. We introduce SCOD (Sketching Curvature for OoD Detection), a post-hoc framework designed to equip pre-trained models with reliable epistemic uncertainty signals. By leveraging randomized matrix sketching to efficiently approximate the model's curvature (Fisher Information Matrix), SCOD achieves the detection accuracy of computationally expensive Deep Ensembles at a fraction of the cost. Our results across diverse benchmarks, including autonomous taxi navigation and image classification, demonstrate that SCOD provides a scalable and architecture-agnostic solution for robust OoD detection.

Introduction

A fundamental challenge in deploying AI in real-world environments—such as autonomous driving or medical diagnostics—is the model's inability to identify "unknown unknowns." When a DNN trained on clear-weather data is exposed to snowy conditions, it may produce high-confidence but incorrect predictions. This necessitates the measurement of epistemic uncertainty, which quantifies the lack of training data in specific regions of the input space.

A principled approach to measuring this uncertainty is the Laplace approximation, which examines the "curvature" of the model's loss landscape. If a small weight perturbation significantly alters the output for a given input, the model is likely uncertain. However, for a model with $N$ parameters, the curvature matrix (Fisher Information Matrix, or FIM) is $N \times N$. For modern networks with millions of weights, storing and inverting this matrix is computationally prohibitive.

Methodology

SCOD makes curvature-based uncertainty tractable through two primary innovations:

  1. Offline Matrix Sketching: Instead of computing the full FIM, SCOD employs "sketching" techniques from randomized numerical linear algebra. Using Subsampled Randomized Fourier Transforms during a single pass over the training data, the framework constructs a low-rank approximation of the FIM. This captures the most influential directions in weight space without ever instantiating the full $N \times N$ matrix.
  2. Online Uncertainty Metric: At test time, SCOD computes the gradient of the model's output for a new input and measures its alignment with the learned directions in the sketched FIM. A high misalignment indicates that the input lies in a region of the weight space unexplored during training, triggering a high uncertainty score ($Unc$).
Conceptual overview of SCOD's offline sketching and online uncertainty estimation phases.

Crucially, SCOD is post-hoc and architecture-agnostic, allowing it to be applied to existing trained models. The authors also found that applying SCOD specifically to the last layers (SCOD-LL) often yields superior performance, as these layers contain the task-specific knowledge defining the distribution.

Experimental Evaluation

The authors evaluated SCOD across a variety of regression and classification tasks, including Wine Quality prediction, Rotated MNIST, and TaxiNet (a Boeing/DARPA benchmark for aircraft runway positioning). Classification performance was tested on MNIST and CIFAR-10 against various OoD sources like FashionMNIST and SVHN.

Key Results

  • Pareto Efficiency: SCOD consistently occupies the optimal region of the accuracy-vs-runtime trade-off. It significantly outperforms "Naive" entropy-based methods and is substantially faster than KFAC Laplace approximations.
  • Competitive with Ensembles: On multiple tasks, SCOD matched or exceeded the performance of Deep Ensembles (the current gold standard), despite Deep Ensembles requiring 5x more resources for training and inference.
  • High-Stakes Reliability: In the complex TaxiNet environment, SCOD achieved an AUROC near 1.00, effectively flagging shifts in weather or lighting conditions that fell outside the training distribution.
Comparison of AUROC vs. Runtime across multiple datasets, showing SCOD's superior efficiency-accuracy trade-off.

Discussion and Future Work

While SCOD offers a significant leap in efficiency, challenges remain regarding memory scaling for "foundation" models with billions of parameters, where even linear scaling ($O(NT)$) is demanding. Additionally, the method requires tuning hyperparameters such as the sketch budget ($T$) and rank ($k$).

Future research may explore SCOD's application in continual learning, where the incremental nature of matrix sketching could allow models to detect and adapt to new tasks over time. By providing a mathematically grounded yet computationally feasible uncertainty signal, SCOD represents a vital step toward safer and more reliable deep learning systems.

Summary updated

Abstract

In order to safely deploy Deep Neural Networks (DNNs) within the perception pipelines of real-time decision making systems, there is a need for safeguards that can detect out-of-training-distributi...
BibTeX
@inproceedings{sharma2021sketching,
  author = {Apoorva Sharma and Navid Azizan and Marco Pavone},
  title = {{Sketching curvature for efficient out-of-distribution detection for deep neural networks}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=DqQzppyIGAb},
}
Figure