Is Out-of-distribution Detection Learnable?

Zhen Fang, Yixuan Li, Jie Lu*, Jiahua Dong, Bo Han, Feng Liu*

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

33 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publication36th Conference on Neural Information Processing Systems (NeurIPS 2022)
PublisherNeural Information Processing Systems Foundation
Number of pages15
Publication statusPublished - 28 Nov 2022
Event36th Conference on Neural Information Processing Systems, NeurIPS 2022 - New Orleans Convention Center, New Orleans, United States
Duration: 28 Nov 20229 Dec 2022
https://neurips.cc/Conferences/2022
https://openreview.net/group?id=NeurIPS.cc/2022/Conference
https://proceedings.neurips.cc/paper_files/paper/2022

Publication series

NameAdvances in Neural Information Processing Systems
Volume35
ISSN (Print)1049-5258
NameNeurIPS Proceedings

Conference

Conference36th Conference on Neural Information Processing Systems, NeurIPS 2022
Country/TerritoryUnited States
CityNew Orleans
Period28/11/229/12/22
Internet address

Fingerprint

Dive into the research topics of 'Is Out-of-distribution Detection Learnable?'. Together they form a unique fingerprint.

Cite this