# Is Out-of-Distribution Detection Learnable?

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

## Key facts

- Cited by 109 papers in the map (data through 14 Oct 2026).
- Builds on 56 of its 99 references that are in the map.
- First posted on arXiv 26 Oct 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [A Baseline for Detecting Misclassified and Out-of-Distribution Examples in Neural Networks](https://mlsanity.com/paper/1610.02136/) (2016)
- [Glow: Generative Flow with Invertible 1x1 Convolutions](https://mlsanity.com/paper/1807.03039/) (2018)
- [A Simple Unified Framework for Detecting Out-of-Distribution Samples and Adversarial Attacks](https://mlsanity.com/paper/1807.03888/) (2018)
- [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)
- [Deep Anomaly Detection with Outlier Exposure](https://mlsanity.com/paper/1812.04606/) (2018)
- [Generalized Out-of-Distribution Detection: A Survey](https://mlsanity.com/paper/2110.11334/) (2021)
- [Out-of-Distribution Detection with Deep Nearest Neighbors](https://mlsanity.com/paper/2204.06507/) (2022)
- [Towards Open Set Deep Networks](https://mlsanity.com/paper/1511.06233/) (2015)
- [ReAct: Out-of-distribution Detection With Rectified Activations](https://mlsanity.com/paper/2111.12797/) (2021)
- [Likelihood Ratios for Out-of-Distribution Detection](https://mlsanity.com/paper/1906.02845/) (2019)
- [Do Deep Generative Models Know What They Don't Know?](https://mlsanity.com/paper/1810.09136/) (2018)
- [Generalized ODIN: Detecting Out-of-distribution Image without Learning from Out-of-distribution Data](https://mlsanity.com/paper/2002.11297/) (2020)
- [On the Importance of Gradients for Detecting Distributional Shifts in the Wild](https://mlsanity.com/paper/2110.00218/) (2021)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Exploring the Limits of Out-of-Distribution Detection](https://mlsanity.com/paper/2106.03004/) (2021)
- [Positive-Unlabeled Learning with Non-Negative Risk Estimator](https://mlsanity.com/paper/1703.00593/) (2017)
- [A Simple Fix to Mahalanobis Distance for Improving Near-OOD Detection](https://mlsanity.com/paper/2106.09022/) (2021)
- [Reducing Network Agnostophobia](https://mlsanity.com/paper/1811.04110/) (2018)
- [A Unified Survey on Anomaly, Novelty, Open-Set, and Out-of-Distribution Detection: Solutions and Future Challenges](https://mlsanity.com/paper/2110.14051/) (2021)
- [Adversarial Reciprocal Points Learning for Open Set Recognition](https://mlsanity.com/paper/2103.00953/) (2021)
- [Likelihood Regret: An Out-of-Distribution Detection Score For Variational Auto-encoder](https://mlsanity.com/paper/2003.02977/) (2020)
- [DROCC: Deep Robust One-Class Classification](https://mlsanity.com/paper/2002.12718/) (2020)
- [ATOM: Robustifying Out-of-distribution Detection Using Outlier Mining](https://mlsanity.com/paper/2006.15207/) (2020)
- [Learning Open Set Network with Discriminative Reciprocal Points](https://mlsanity.com/paper/2011.00178/) (2020)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Can multi-label classification networks know what they don't know?](https://mlsanity.com/paper/2109.14162/) (2021)

## Built on by (most cited first, 30 of 109)

- [Delving into Out-of-Distribution Detection with Vision-Language Representations](https://mlsanity.com/paper/2211.13445/) (2022)
- [ARGS: Alignment as Reward-Guided Search](https://mlsanity.com/paper/2402.01694/) (2024)
- [Provable Dynamic Fusion for Low-Quality Multimodal Data](https://mlsanity.com/paper/2306.02050/) (2023)
- [Process Reward Model with Q-Value Rankings](https://mlsanity.com/paper/2410.11287/) (2024)
- [Dream the Impossible: Outlier Imagination with Diffusion Models](https://mlsanity.com/paper/2309.13415/) (2023)
- [Nearest Neighbor Guidance for Out-of-Distribution Detection](https://mlsanity.com/paper/2309.14888/) (2023)
- [FedFed: Feature Distillation against Data Heterogeneity in Federated Learning](https://mlsanity.com/paper/2310.05077/) (2023)
- [Out-of-distribution Detection with Implicit Outlier Transformation](https://mlsanity.com/paper/2303.05033/) (2023)
- [Diversified Outlier Exposure for Out-of-Distribution Detection via Informative Extrapolation](https://mlsanity.com/paper/2310.13923/) (2023)
- [Learning to Augment Distributions for Out-of-Distribution Detection](https://mlsanity.com/paper/2311.01796/) (2023)
- [Federated Incremental Semantic Segmentation](https://mlsanity.com/paper/2304.04620/) (2023)
- [How Does Unlabeled Data Provably Help Out-of-Distribution Detection?](https://mlsanity.com/paper/2402.03502/) (2024)
- [Maskomaly:Zero-Shot Mask Anomaly Segmentation](https://mlsanity.com/paper/2305.16972/) (2023)
- [Out-of-Domain Generalization in Dynamical Systems Reconstruction](https://mlsanity.com/paper/2402.18377/) (2024)
- [A Survey on Out-of-Distribution Detection in NLP](https://mlsanity.com/paper/2305.03236/) (2023)
- [Out-of-distribution Detection Learning with Unreliable Out-of-distribution Sources](https://mlsanity.com/paper/2311.03236/) (2023)
- [Learnability and Algorithm for Continual Learning](https://mlsanity.com/paper/2306.12646/) (2023)
- [Understanding the Feature Norm for Out-of-Distribution Detection](https://mlsanity.com/paper/2310.05316/) (2023)
- [Out-of-Distribution Detection: A Task-Oriented Survey of Recent Advances](https://mlsanity.com/paper/2409.11884/) (2024)
- [DIVERSIFY: A General Framework for Time Series Out-of-distribution Detection and Generalization](https://mlsanity.com/paper/2308.02282/) (2023)
- [Kernel PCA for Out-of-Distribution Detection](https://mlsanity.com/paper/2402.02949/) (2024)
- [ConjNorm: Tractable Density Estimation for Out-of-Distribution Detection](https://mlsanity.com/paper/2402.17888/) (2024)
- [Unleashing Mask: Explore the Intrinsic Out-of-Distribution Detection Capability](https://mlsanity.com/paper/2306.03715/) (2023)
- [Unsupervised Layer-wise Score Aggregation for Textual OOD Detection](https://mlsanity.com/paper/2302.09852/) (2023)
- [Hard Sample Matters a Lot in Zero-Shot Quantization](https://mlsanity.com/paper/2303.13826/) (2023)
- [Heterogeneous Forgetting Compensation for Class-Incremental Learning](https://mlsanity.com/paper/2308.03374/) (2023)
- [Average of Pruning: Improving Performance and Stability of Out-of-Distribution Detection](https://mlsanity.com/paper/2303.01201/) (2023)
- [OpenMIBOOD: Open Medical Imaging Benchmarks for Out-Of-Distribution Detection](https://mlsanity.com/paper/2503.16247/) (2025)
- [Handling Out-of-Distribution Data: A Survey](https://mlsanity.com/paper/2507.21160/) (2025)
- [NoiseDiffusion: Correcting Noise for Image Interpolation with Diffusion Models beyond Spherical Linear Interpolation](https://mlsanity.com/paper/2403.08840/) (2024)

## 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. To study the generalization of OOD detection, in this paper, we investigate the probably approximately correct (PAC) learning theory of OOD detection, which is proposed by researchers as an open problem. 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 also offer theoretical supports for several representative OOD detection works based on our OOD theory.