# Open Category Detection with PAC Guarantees

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Aug 2018.

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

- [Generalized Out-of-Distribution Detection: A Survey](https://mlsanity.com/paper/2110.11334/) (2021)
- [Is Out-of-Distribution Detection Learnable?](https://mlsanity.com/paper/2210.14707/) (2022)
- [Long-Tailed Recognition via Weight Balancing](https://mlsanity.com/paper/2203.14197/) (2022)
- [ImbSAM: A Closer Look at Sharpness-Aware Minimization in Class-Imbalanced Recognition](https://mlsanity.com/paper/2308.07815/) (2023)
- [Learning Bounds for Open-Set Learning](https://mlsanity.com/paper/2106.15792/) (2021)
- [iDECODe: In-distribution Equivariance for Conformal Out-of-distribution Detection](https://mlsanity.com/paper/2201.02331/) (2022)
- [Self-Supervised Anomaly Detection in Computer Vision and Beyond: A Survey and Outlook](https://mlsanity.com/paper/2205.05173/) (2022)
- [MAMo: Leveraging Memory and Attention for Monocular Video Depth Estimation](https://mlsanity.com/paper/2307.14336/) (2023)
- [OpenCoS: Contrastive Semi-supervised Learning for Handling Open-set Unlabeled Data](https://mlsanity.com/paper/2107.08943/) (2021)
- [Bayesian OOD detection with aleatoric uncertainty and outlier exposure](https://mlsanity.com/paper/2102.12959/) (2021)
- [DistractFlow: Improving Optical Flow Estimation via Realistic Distractions and Pseudo-Labeling](https://mlsanity.com/paper/2303.14078/) (2023)
- [Resisting Out-of-Distribution Data Problem in Perturbation of XAI](https://mlsanity.com/paper/2107.14000/) (2021)
- [Task-Relevant Failure Detection for Trajectory Predictors in Autonomous Vehicles](https://mlsanity.com/paper/2207.12380/) (2022)
- [Dense Uncertainty Estimation](https://mlsanity.com/paper/2110.06427/) (2021)
- [Benchmark for Out-of-Distribution Detection in Deep Reinforcement Learning](https://mlsanity.com/paper/2112.02694/) (2021)
- [DejaVu: Conditional Regenerative Learning to Enhance Dense Prediction](https://mlsanity.com/paper/2303.01573/) (2023)
- [Understanding the Effect of Bias in Deep Anomaly Detection](https://mlsanity.com/paper/2105.07346/) (2021)
- [Responsible and Regulatory Conform Machine Learning for Medicine: A Survey of Challenges and Solutions](https://mlsanity.com/paper/2107.09546/) (2021)
- [DIFT: Dynamic Iterative Field Transforms for Memory Efficient Optical Flow](https://mlsanity.com/paper/2306.05691/) (2023)
- [Taming False Positives in Out-of-Distribution Detection with Human Feedback](https://mlsanity.com/paper/2404.16954/) (2024)
- [Task-Driven Detection of Distribution Shifts with Statistical Guarantees for Robot Learning](https://mlsanity.com/paper/2106.13703/) (2021)
- [Diffusion based Semantic Outlier Generation via Nuisance Awareness for Out-of-Distribution Detection](https://mlsanity.com/paper/2408.14841/) (2024)
- [Autoencoder Attractors for Uncertainty Estimation](https://mlsanity.com/paper/2204.00382/) (2022)
- [Understanding Open-Set Recognition by Jacobian Norm and Inter-Class Separation](https://mlsanity.com/paper/2209.11436/) (2022)
- [SaliencyCut: Augmenting Plausible Anomalies for Anomaly Detection](https://mlsanity.com/paper/2306.08366/) (2023)
- [Energy-bounded Learning for Robust Models of Code](https://mlsanity.com/paper/2112.11226/) (2021)
- [On The Relationship Between Continual Learning and Long-Tailed Recognition](https://mlsanity.com/paper/2306.13275/) (2023)
- [Theoretical Investigation on Inductive Bias of Isolation Forest](https://mlsanity.com/paper/2505.12825/) (2025)
- [Learning Acceptance Regions for Many Classes with Anomaly Detection](https://mlsanity.com/paper/2209.09963/) (2022)
- [Propheter: Prophetic Teacher Guided Long-Tailed Distribution Learning](https://mlsanity.com/paper/2304.04135/) (2023)

## Abstract (arXiv)

Open category detection is the problem of detecting "alien" test instances that belong to categories or classes that were not present in the training data. In many applications, reliably detecting such aliens is central to ensuring the safety and accuracy of test set predictions. Unfortunately, there are no algorithms that provide theoretical guarantees on their ability to detect aliens under general assumptions. Further, while there are algorithms for open category detection, there are few empirical results that directly report alien detection rates. Thus, there are significant theoretical and empirical gaps in our understanding of open category detection. In this paper, we take a step toward addressing this gap by studying a simple, but practically-relevant variant of open category detection. In our setting, we are provided with a "clean" training set that contains only the target categories of interest and an unlabeled "contaminated" training set that contains a fraction α of alien examples. Under the assumption that we know an upper bound on α, we develop an algorithm with PAC-style guarantees on the alien detection rate, while aiming to minimize false alarms. Empirical results on synthetic and standard benchmark datasets demonstrate the regimes in which the algorithm can be effective and provide a baseline for further advancements.