  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.
