# On the Learnability of Out-of-distribution Detection

arXiv: https://arxiv.org/abs/2404.04865 · HTML: https://mlsanity.com/paper/2404.04865/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 54 of its 110 references that are in the map.
- First posted on arXiv 7 Apr 2024.

## Builds on (most cited first, 30 of 54)

- [Enhancing The Reliability of Out-of-distribution Image Detection in Neural Networks](https://mlsanity.com/paper/1706.02690/) (2017)
- [Energy-based Out-of-distribution Detection](https://mlsanity.com/paper/2010.03759/) (2020)
- [Generalized Out-of-Distribution Detection: A Survey](https://mlsanity.com/paper/2110.11334/) (2021)
- [Exploring the Limits of Weakly Supervised Pretraining](https://mlsanity.com/paper/1805.00932/) (2018)
- [Out-of-Distribution Detection with Deep Nearest Neighbors](https://mlsanity.com/paper/2204.06507/) (2022)
- [ReAct: Out-of-distribution Detection With Rectified Activations](https://mlsanity.com/paper/2111.12797/) (2021)
- [Snapshot Ensembles: Train 1, get M for free](https://mlsanity.com/paper/1704.00109/) (2017)
- [On the Importance of Gradients for Detecting Distributional Shifts in the Wild](https://mlsanity.com/paper/2110.00218/) (2021)
- [VOS: Learning What You Don't Know by Virtual Outlier Synthesis](https://mlsanity.com/paper/2202.01197/) (2022)
- [Mitigating Neural Network Overconfidence with Logit Normalization](https://mlsanity.com/paper/2205.09310/) (2022)
- [MOS: Towards Scaling Out-of-distribution Detection for Large Semantic Space](https://mlsanity.com/paper/2105.01879/) (2021)
- [Convergent Learning: Do different neural networks learn the same representations?](https://mlsanity.com/paper/1511.07543/) (2015)
- [Delving into Out-of-Distribution Detection with Vision-Language Representations](https://mlsanity.com/paper/2211.13445/) (2022)
- [OpenOOD v1.5: Enhanced Benchmark for Out-of-Distribution Detection](https://mlsanity.com/paper/2306.09301/) (2023)
- [A Unified Survey on Anomaly, Novelty, Open-Set, and Out-of-Distribution Detection: Solutions and Future Challenges](https://mlsanity.com/paper/2110.14051/) (2021)
- [Non-Parametric Outlier Synthesis](https://mlsanity.com/paper/2303.02966/) (2023)
- [How to Exploit Hyperspherical Embeddings for Out-of-Distribution Detection?](https://mlsanity.com/paper/2203.04450/) (2022)
- [Is Out-of-Distribution Detection Learnable?](https://mlsanity.com/paper/2210.14707/) (2022)
- [POEM: Out-of-Distribution Detection with Posterior Sampling](https://mlsanity.com/paper/2206.13687/) (2022)
- [Training OOD Detectors in their Natural Habitats](https://mlsanity.com/paper/2202.03299/) (2022)
- [Model Patching: Closing the Subgroup Performance Gap with Data Augmentation](https://mlsanity.com/paper/2008.06775/) (2020)
- [Provable Guarantees for Understanding Out-of-distribution Detection](https://mlsanity.com/paper/2112.00787/) (2021)
- [Dream the Impossible: Outlier Imagination with Diffusion Models](https://mlsanity.com/paper/2309.13415/) (2023)
- [Unknown-Aware Object Detection: Learning What You Don't Know from Videos in the Wild](https://mlsanity.com/paper/2203.03800/) (2022)
- [On the Impact of Spurious Correlation for Out-of-distribution Detection](https://mlsanity.com/paper/2109.05642/) (2021)
- [Robust Out-of-distribution Detection for Neural Networks](https://mlsanity.com/paper/2003.09711/) (2020)
- [Feed Two Birds with One Scone: Exploiting Wild Data for Both Out-of-Distribution Generalization and Detection](https://mlsanity.com/paper/2306.09158/) (2023)
- [Rethinking Domain Generalization for Face Anti-spoofing: Separability and Alignment](https://mlsanity.com/paper/2303.13662/) (2023)
- [Frequency Domain Image Translation: More Photo-realistic, Better Identity-preserving](https://mlsanity.com/paper/2011.13611/) (2020)
- [Mitigating Memorization of Noisy Labels by Clipping the Model Prediction](https://mlsanity.com/paper/2212.04055/) (2022)

## Built on by (most cited first, 8 of 8)

- [Process Reward Model with Q-Value Rankings](https://mlsanity.com/paper/2410.11287/) (2024)
- [Adaptive Hierarchical Graph Cut for Multi-granularity Out-of-distribution Detection](https://mlsanity.com/paper/2412.15668/) (2024)
- [REALM: An MLLM-Agent Framework for Open World 3D Reasoning Segmentation and Editing on Gaussian Splatting](https://mlsanity.com/paper/2510.16410/) (2025)
- [LoD: Loss-difference OOD Detection by Intentionally Label-Noisifying Unlabeled Wild Data](https://mlsanity.com/paper/2505.12952/) (2025)
- [Double Descent Meets Out-of-Distribution Detection: Theoretical Insights and Empirical Analysis on the role of model complexity](https://mlsanity.com/paper/2411.02184/) (2024)
- [Predictive Sample Assignment for Semantically Coherent Out-of-Distribution Detection](https://mlsanity.com/paper/2512.12906/) (2025)
- [On Hallucinations in Inverse Problems: Fundamental Limits and Provable Assessment Methods](https://mlsanity.com/paper/2605.13146/) (2026)
- [Surprises in Proper Positive-Only Learning](https://mlsanity.com/paper/2606.28309/) (2026)

## Abstract (arXiv)

Supervised learning aims to train a classifier under the assumption that training and test data are from the same distribution. To ease the above assumption, researchers have studied a more realistic setting: out-of-distribution (OOD) detection, where test data may come from classes that are unknown during training (i.e., OOD data). Due to the unavailability and diversity of OOD data, good generalization ability is crucial for effective OOD detection algorithms, and corresponding learning theory is still an open problem. To study the generalization of OOD detection, this paper investigates the probably approximately correct (PAC) learning theory of OOD detection that fits the commonly used evaluation metrics in the literature. First, we find a necessary condition for the learnability of OOD detection. Then, using this condition, we prove several impossibility theorems for the learnability of OOD detection under some scenarios. Although the impossibility theorems are frustrating, we find that some conditions of these impossibility theorems may not hold in some practical scenarios. Based on this observation, we next give several necessary and sufficient conditions to characterize the learnability of OOD detection in some practical scenarios. Lastly, we offer theoretical support for representative OOD detection works based on our OOD theory.