Is Out-of-Distribution Detection Learnable?

Introduction

The success of supervised learning is established on an implicit assumption that training and test data share a same distribution, i.e., in-distribution (ID) . However, test data distribution in many real-world scenarios may violate the assumption and, instead, contain out-of-distribution (OOD) data whose labels have not been seen during the training process . To mitigate the risk of OOD data, researchers have considered a more practical learning scenario: OOD detection which determines whether an input is ID/OOD, while classifying the ID data into respective classes. OOD detection has shown great potential to ensure the reliable deployment of machine learning models in the real world. A rich line of algorithms have been developed to empirically address the OOD detection problem . However, very few works study theory of OOD detection, which hinders the rigorous path forward for the field. This paper aims to bridge the gap.

In this paper, we provide a theoretical framework to understand the learnability of the OOD detection problem. We investigate the probably approximately correct (PAC) learning theory of OOD detection, which is posed as an open problem to date. Unlike the classical PAC learning theory in a supervised setting, our problem setting is fundamentally challenging due to the absence of OOD data in training. In many real-world scenarios, OOD data can be diverse and priori-unknown. Given this, we study whether there exists an algorithm that can be used to detect various OOD data instead of merely some specified OOD data. Such is the significance of studying the learning theory for OOD detection . This motivates our question: is OOD detection PAC learnable? i.e., is there the PAC learning theory to guarantee the generalization ability of OOD detection?

To investigate the learning theory, we mainly focus on two basic spaces: domain space and hypothesis space. The domain space is a space consisting of some distributions, and the hypothesis space is a space consisting of some classifiers. Existing agnostic PAC theories in supervised learning are distribution-free, i.e., the domain space consists of all domains. Yet, in Theorem 4, we shows that the learning theory of OOD detection is not distribution-free. In fact, we discover that OOD detection is learnable only if the domain space and the hypothesis space satisfy some special conditions, e.g., Conditions 1 and 3. Notably, there are many conditions and theorems in existing learning theories and many OOD detection algorithms in the literature. Thus, it is very difficult to analyze the relation between these theories and algorithms, and explore useful conditions to ensure the learnability of OOD detection, especially when we have to explore them from the scratch. Thus, the main aim of our paper is to study these essential conditions. From these essential conditions, we can know when OOD detection can be successful in practical scenarios. We restate our question and goal in following:

Given hypothesis spaces and several representative domain spaces, what are the conditions to ensure the learnability of OOD detection? If possible, we hope that these conditions are necessary and sufficient in some scenarios.

Main Results. We investigate the learnability of OOD detection starting from the largest space—the total space, and give a necessary condition (Condition 1) for the learnability. However, we find that the overlap between ID and OOD data may result in that the necessary condition does not hold. Therefore, we give an impossibility theorem to demonstrate that OOD detection fails in the total space (Theorem 4). Next, we study OOD detection in the separate space, where there are no overlaps between the ID and OOD data. Unfortunately, there still exists impossibility theorem (Theorem 5), which demonstrates that OOD detection is not learnable in the separate space under some conditions.

Although the impossibility theorems obtained in the separate space are frustrating, we find that some conditions of these impossibility theorems may not hold in some practical scenarios. Based on this observation, we give several necessary and sufficient conditions to characterize the learnability of OOD detection in the separate space (Theorems 6 and 10). Especially, when our model is based on fully-connected neural network (FCNN), OOD detection is learnable in the separate space if and only if the feature space is finite. Furthermore, we investigate the learnability of OOD detection in other more practical domain spaces, e.g., the finite-ID-distribution space (Theorem 8) and the density-based space (Theorem 9). By studying the finite-ID-distribution space, we discover a compatibility condition (Condition 3) that is a necessary and sufficient condition for this space. Next, we further investigate the compatibility condition in the density-based space, and find that such condition is also the necessary and sufficient condition in some practical scenarios (Theorem 11).

Implications and Impacts of Theory. Our study is not of purely theoretical interest; it has also practical impacts. First, when we design OOD detection algorithms, we normally only have finite ID datasets, corresponding to the finite-ID-distribution space. In this case, Theorem 8 gives the necessary and sufficient condition to the success of OOD detection. Second, our theory provides theoretical support (Theorems 10 and 11) for several representative OOD detection works . Third, our theory shows that OOD detection is learnable in image-based scenarios when ID images have clearly different semantic labels and styles (far-OOD) from OOD images. Fourth, we should not expect a universally working algorithm. It is necessary to design different algorithms in different scenarios.

Learning Setups

Given an ID joint distribution $D_{X_{\rm I}Y_{\rm I}}$ and a training data $S:=\{(\mathbf{x}^{1},{y}^{1}),...,(\mathbf{x}^{n},{y}^{n})\}$ drawn independent and identically distributed from $D_{X_{\rm I}Y_{\rm I}}$, the aim of OOD detection is to train a classifier $f$ by using the training data $S$ such that, for any test data $\mathbf{x}$ drawn from the mixed marginal distribution $D_{X}$: 1) if $\mathbf{x}$ is an observation from $D_{X_{\rm I}}$, $f$ can classify $\mathbf{x}$ into correct ID classes; and 2) if $\mathbf{x}$ is an observation from $D_{X_{\rm O}}$, $f$ can detect $\mathbf{x}$ as OOD data.

According to the survey , when $K>1$, OOD detection is also known as the open-set recognition or open-set learning ; and when $K=1$, OOD detection reduces to one-class novelty detection and semantic anomaly detection .

OOD Label and Domain Space. Based on Problem 1, we know it is not necessary to classify OOD data into the correct OOD classes. Without loss of generality, let all OOD data be allocated to one big OOD class, i.e., $Y_{\rm O}=K+1$ . To investigate the PAC learnability of OOD detection, we define a domain space $\mathscr{D}_{XY}$, which is a set consisting of some joint distributions $D_{XY}$ mixed by some ID joint distributions and some OOD joint distributions. In this paper, the joint distribution $D_{XY}$ mixed by ID joint distribution $D_{X_{\rm I}Y_{\rm I}}$ and OOD joint distribution $D_{X_{\rm O}Y_{\rm O}}$ is called domain.

The $\alpha$-risk $R_{D}^{\alpha}({h}):=(1-\alpha)R^{\rm in}_{D}({h})+\alpha R^{\rm out}_{D}({h}),\forall\alpha\in$, where the risks $R^{\rm in}_{D}({h})$, $R^{\rm out}_{D}({h})$ are

Learnability. We aim to select a hypothesis function $h\in\mathcal{H}$ with approximately minimal risk, based on finite data. Generally, we expect the approximation to get better, with the increase in sample size. Algorithms achieving this are said to be consistent. Formally, we introduce the following definition:

Given a domain space $\mathscr{D}_{XY}$ and a hypothesis space $\mathcal{H}\subset\{{h}:\mathcal{X}\rightarrow\mathcal{Y}_{\rm all}\}$, we say OOD detection is learnable in $\mathscr{D}_{XY}$ for $\mathcal{H}$, if there exists an algorithm $\mathbf{A}:\cup_{n=1}^{+\infty}(\mathcal{X}\times\mathcal{Y})^{n}\rightarrow\mathcal{H}$Similar to , in this paper, we regard an algorithm as a mapping from $\cup_{n=1}^{+\infty}(\mathcal{X}\times\mathcal{Y})^{n}$ to $\mathcal{H}$. and a monotonically decreasing sequence $\epsilon_{\rm cons}(n)$, such that $\epsilon_{\rm cons}(n)\rightarrow 0$, as $n\rightarrow+\infty$, and for any domain $D_{XY}\in\mathscr{D}_{XY}$,

An algorithm $\mathbf{A}$ for which this holds is said to be consistent with respect to $\mathscr{D}_{XY}$.

Since OOD data are unavailable, it is impossible to obtain information about the class-prior probability $\pi^{\rm out}$. Furthermore, in the real world, it is possible that $\pi^{\rm out}$ can be any value in $[0,1)$. Therefore, the imbalance issue between ID and OOD distributions, and the priori-unknown issue (i.e., $\pi^{\rm out}$ is unknown) are the core challenges. To ease these challenges, researchers use AUROC, AUPR and FPR95 to estimate the performance of OOD detection . It seems that there is a gap between Definition 1 and existing works. To eliminate this gap, we revise Eq. (2) as follows:

If an algorithm $\mathbf{A}$ satisfies Eq. (3), then the imbalance issue and the prior-unknown issue disappear. That is, $\mathbf{A}$ can simultaneously classify the ID data and detect the OOD data well. Based on the above discussion, we define the strong learnability of OOD detection as follows:

Given a domain space $\mathscr{D}_{XY}$ and a hypothesis space $\mathcal{H}\subset\{{h}:\mathcal{X}\rightarrow\mathcal{Y}_{\rm all}\}$, we say OOD detection is strongly learnable in $\mathscr{D}_{XY}$ for $\mathcal{H}$, if there exists an algorithm $\mathbf{A}:\cup_{n=1}^{+\infty}(\mathcal{X}\times\mathcal{Y})^{n}\rightarrow\mathcal{H}$ and a monotonically decreasing sequence $\epsilon_{\rm cons}(n)$, such that $\epsilon_{\rm cons}(n)\rightarrow 0$, as $n\rightarrow+\infty$, and for any domain $D_{XY}\in\mathscr{D}_{XY}$,

In Theorem 1, we have shown that the strong learnability of OOD detection is equivalent to the learnability of OOD detection, if the domain space $\mathscr{D}_{XY}$ is a prior-unknown space (see Definition 3). In this paper, we mainly discuss the learnability in the prior-unknown space. Therefore, when we mention that OOD detection is learnable, we also mean that OOD detection is strongly learnable.

Goal of Theory. Note that the agnostic PAC learnability of supervised learning is distribution-free, i.e., the domain space $\mathscr{D}_{XY}$ consists of all domains. However, due to the absence of OOD data during the training process , it is obvious that the learnability of OOD detection is not distribution-free (i.e., Theorem 4). In fact, we discover that the learnability of OOD detection is deeply correlated with the relationship between the domain space $\mathscr{D}_{XY}$ and the hypothesis space $\mathcal{H}$. That is, OOD detection is learnable only when the domain space $\mathscr{D}_{XY}$ and the hypothesis space $\mathcal{H}$ satisfy some special conditions, e.g., Condition 1 and Condition 3. We present our goal as follows:

Goal: given a hypothesis space $\mathcal{H}$ and several representative domain spaces $\mathscr{D}_{XY}$, what are the conditions to ensure the learnability of OOD detection? Furthermore, if possible, we hope that these conditions are necessary and sufficient in some scenarios.

Therefore, compared to the agnostic PAC learnability of supervised learning, our theory doesn’t focus on the distribution-free case, but focuses on discovering essential conditions to guarantee the learnability of OOD detection in several representative and practical domain spaces $\mathscr{D}_{XY}$. By these essential conditions, we can know when OOD detection can be successful in real applications.

Learning in Priori-unknown Spaces

We first investigate a special space, called prior-unknown space. In such space, Definition 1 and Definition 2 are equivalent. Furthermore, we also prove that if OOD detection is strongly learnable in a space $\mathscr{D}_{XY}$, then one can discover a larger domain space, which is prior-unknown, to ensure the learnability of OOD detection. These results imply that it is enough to consider our theory in the prior-unknown spaces. The prior-unknown space is introduced as follows:

Given a domain space $\mathscr{D}_{XY}$, we say $\mathscr{D}_{XY}$ is a priori-unknown space, if for any domain $D_{XY}\in\mathscr{D}_{XY}$ and any $\alpha\in[0,1)$, we have $D_{XY}^{\alpha}:=(1-\alpha)D_{X_{\rm I}Y_{\rm I}}+\alpha D_{X_{\rm O}Y_{\rm O}}\in\mathscr{D}_{XY}$.

Given domain spaces $\mathscr{D}_{XY}$ and $\mathscr{D}_{XY}^{\prime}=\{D_{XY}^{\alpha}:\forall D_{XY}\in\mathscr{D}_{XY},\forall\alpha\in[0,1)\}$, then 1) $\mathscr{D}_{XY}^{\prime}$ is a priori-unknown space and $\mathscr{D}_{XY}\subset\mathscr{D}_{XY}^{\prime}$; 2) if $\mathscr{D}_{XY}$ is a priori-unknown space, then Definition 1 and Definition 2 are equivalent; 3) OOD detection is strongly learnable in $\mathscr{D}_{XY}$ if and only if OOD detection is learnable in $\mathscr{D}_{XY}^{\prime}$.

The second result of Theorem 1 bridges the learnability and strong learnability, which implies that if an algorithm $\mathbf{A}$ is consistent with respect to a prior-unknown space, then this algorithm $\mathbf{A}$ can address the imbalance issue between ID and OOD distributions, and the priori-unknown issue well. Based on Theorem 1, we focus on our theory in the prior-unknown spaces. Furthermore, to demystify the learnability of OOD detection, we introduce five representative priori-unknown spaces:

$\bullet$ Single-distribution space $\mathscr{D}_{XY}^{D_{XY}}$. For a domain $D_{XY}$, $\mathscr{D}_{XY}^{D_{XY}}:=\{D_{XY}^{\alpha}:\forall\alpha\in[0,1)\}$. $\bullet$ Total space $\mathscr{D}_{XY}^{\rm all}$, which consists of all domains. $\bullet$ Separate space $\mathscr{D}_{XY}^{s}$, which consists of all domains that satisfy the separate condition, that is for any $D_{XY}\in\mathscr{D}_{XY}^{s}$, ${\rm supp}D_{X_{\rm O}}\cap{\rm supp}D_{X_{\rm I}}=\emptyset,$ where ${\rm supp}$ means the support set. $\bullet$ Finite-ID-distribution space $\mathscr{D}_{XY}^{F}$, which is a prior-unknown space satisfying that the number of distinct ID joint distributions $D_{X_{\rm I}Y_{\rm I}}$ in $\mathscr{D}_{XY}^{F}$ is finite, i.e., $|\{D_{X_{\rm I}Y_{\rm I}}:\forall D_{XY}\in\mathscr{D}_{XY}^{F}\}|<+\infty$. $\bullet$ Density-based space $\mathscr{D}^{\mu,b}_{XY}$, which is a prior-unknown space consisting of some domains satisfying that: for any $D_{XY}$, there exists a density function $f$ with $1/b\leq f\leq b$ in ${\rm supp}\mu$ and $0.5*D_{X_{\rm I}}+0.5*D_{X_{\rm O}}=\int f{\rm d}\mu$, where $\mu$ is a measure defined over $\mathcal{X}$. Note that if $\mu$ is discrete, then $D_{X}$ is a discrete distribution; and if $\mu$ is the Lebesgue measure, then $D_{X}$ is a continuous distribution.

The above representative spaces widely exist in real applications. For example, 1) if the images from different semantic labels with different styles are clearly different, then those images can form a distribution belonging to a separate space $\mathscr{D}_{XY}^{s}$; and 2) when designing an algorithm, we only have finite ID datasets, e.g., CIFAR-10, MNIST, SVHN, and ImageNet, to build a model. Then, finite-ID-distribution space $\mathscr{D}_{XY}^{F}$ can handle this real scenario. Note that the single-distribution space is a special case of the finite-ID-distribution space. In this paper, we mainly discuss these five spaces.

Impossibility Theorems for OOD Detection

In this section, we first give a necessary condition for the learnability of OOD detection. Then, we show this necessary condition does not hold in the total space $\mathscr{D}_{XY}^{\rm all}$ and the separate space $\mathscr{D}_{XY}^{s}$.

Necessary Condition. We find a necessary condition for the learnability of OOD detection, i.e., Condition 1, motivated by the experiments in Figure 1. Details of Figure 1 can be found in Appendix C.2.

For any $D_{XY}\in\mathscr{D}_{XY}$ and any $\alpha\in[0,1)$,

To reveal the importance of Condition 1, Theorem 2 shows that Condition 1 is a necessary and sufficient condition for the learnability of OOD detection if the $\mathscr{D}_{XY}$ is the single-distribution space.

Theorem 2. Given a hypothesis space $\mathcal{H}$ and a domain $D_{XY}$, OOD detection is learnable in the single-distribution space $\mathscr{D}_{XY}^{D_{XY}}$ for $\mathcal{H}$ if and only if linear condition (i.e., Condition 1) holds.

Theorem 2 implies that Condition 1 is important for the learnability of OOD detection. Due to the simplicity of single-distribution space, Theorem 2 implies that Condition 1 is the necessary condition for the learnability of OOD detection in the prior-unknown space, see Lemma 1 in Appendix F.

Impossibility Theorems. Here, we first study whether Condition 1 holds in the total space $\mathscr{D}_{XY}^{\rm all}$. If Condition 1 does not hold, then OOD detection is not learnable. Theorem 3 shows that Condition 1 is not always satisfied, especially, when there is an overlap between the ID and OOD distributions:

Given a hypothesis space $\mathcal{H}$ and a prior-unknown space $\mathscr{D}_{XY}$, if there is $D_{XY}\in\mathscr{D}_{XY}$, which has overlap between ID and OOD, and $\inf_{h\in\mathcal{H}}R_{D}^{\rm in}(h)=0$ and $\inf_{h\in\mathcal{H}}R_{D}^{\rm out}(h)=0$, then Condition 1 does not hold. Therefore, OOD detection is not learnable in $\mathscr{D}_{XY}$ for $\mathcal{H}$.

Theorem 3 clearly shows that under proper conditions, Condition 1 does not hold, if there exists a domain whose ID and OOD distributions have overlap. By Theorem 3, we can obtain that the OOD detection is not learnable in the total space $\mathscr{D}^{\rm all}_{XY}$ for any non-trivial hypothesis space $\mathcal{H}$.

Theorem 4 (Impossibility Theorem for Total Space). OOD detection is not learnable in the total space $\mathscr{D}^{\rm all}_{XY}$ for $\mathcal{H}$, if $|\phi\circ\mathcal{H}|>1$, where $\phi$ maps ID labels to $1$ and maps OOD labels to $2$.

Since the overlaps between ID and OOD distributions may cause that Condition 1 does not hold, we then consider studying the learnability of OOD detection in the separate space $\mathscr{D}_{XY}^{s}$, where there are no overlaps between the ID and OOD distributions. However, Theorem 5 shows that even if we consider the separate space, the OOD detection is still not learnable in some scenarios. Before introducing the impossibility theorem for separate space, i.e., Theorem 5, we need a mild assumption:

A hypothesis space $\mathcal{H}$ is separate for OOD data, if for each data point $\mathbf{x}\in\mathcal{X}$, there exists at least one hypothesis function $h_{\mathbf{x}}\in\mathcal{H}$ such that $h_{\mathbf{x}}(\mathbf{x})=K+1$.

Assumption 1 means that every data point $\mathbf{x}$ has the possibility to be detected as OOD data. Assumption 1 is mild and can be satisfied by many hypothesis spaces, e.g., the FCNN-based hypothesis space (Proposition 1 in Appendix K), score-based hypothesis space (Proposition 2 in Appendix K) and universal kernel space. Next, we use Vapnik–Chervonenkis (VC) dimension to measure the size of hypothesis space, and study the learnability of OOD detection in $\mathscr{D}_{XY}^{s}$ based on the VC dimension.

Theorem 5 (Impossibility Theorem for Separate Space). If Assumption 1 holds, ${\rm VCdim}(\phi\circ\mathcal{H})<+\infty$ and $\sup_{{h}\in\mathcal{H}}|\{\mathbf{x}\in\mathcal{X}:{h}(\mathbf{x})\in\mathcal{Y}\}|=+\infty$, then OOD detection is not learnable in separate space $\mathscr{D}_{XY}^{s}$ for $\mathcal{H}$, where $\phi$ maps ID labels to ${1}$ and maps OOD labels to $2$.

The finite VC dimension normally implies the learnability of supervised learning. However, in our results, the finite VC dimension cannot guarantee the learnability of OOD detection in the separate space, which reveals the difficulty of the OOD detection. Although the above impossibility theorems are frustrating, there is still room to discuss the conditions in Theorem 5, and to find out the proper conditions for ensuring the learnability of OOD detection in the separate space (see Sections 5 and 6).

When OOD Detection Can Be Successful

Here, we discuss when the OOD detection can be learnable in the separate space $\mathscr{D}_{XY}^{s}$, finite-ID-distribution space $\mathscr{D}_{XY}^{F}$ and density-based space $\mathscr{D}_{XY}^{\mu,b}$. We first study the separate space $\mathscr{D}_{XY}^{s}$.

OOD Detection in the Separate Space. Theorem 5 has indicated that ${\rm VCdim}(\phi\circ\mathcal{H})=+\infty$ or $\sup_{{h}\in\mathcal{H}}|\{\mathbf{x}\in\mathcal{X}:{h}(\mathbf{x})\in\mathcal{Y}\}|<+\infty$ is necessary to ensure the learnability of OOD detection in $\mathscr{D}_{XY}^{s}$ if Assumption 1 holds. However, generally, hypothesis spaces generated by feed-forward neural networks with proper activation functions have finite VC dimension . Therefore, we study the learnability of OOD detection in the case that $|\mathcal{X}|<+\infty$, which implies that $\sup_{{h}\in\mathcal{H}}|\{\mathbf{x}\in\mathcal{X}:{h}(\mathbf{x})\in\mathcal{Y}\}|<+\infty$. Additionally, Theorem 10 also implies that $|\mathcal{X}|<+\infty$ is the necessary and sufficient condition for the learnability of OOD detection in separate space, when the hypothesis space is generated by FCNN. Hence, $|\mathcal{X}|<+\infty$ may be necessary in the space $\mathscr{D}_{XY}^{s}$.

For simplicity, we first discuss the case that $K=1$, i.e., the one-class novelty detection. We show the necessary and sufficient condition for the learnability of OOD detection in $\mathscr{D}_{XY}^{s}$, when $|\mathcal{X}|<+\infty$.

Theorem 6. Let $K=1$ and $|\mathcal{X}|<+\infty$. Suppose that Assumption 1 holds and the constant function $h^{\rm in}:=1\in\mathcal{H}$. Then OOD detection is learnable in $\mathscr{D}_{XY}^{s}$ for $\mathcal{H}$ if and only if $\mathcal{H}_{\rm all}-\{h^{\rm out}\}\subset\mathcal{H}$, where $\mathcal{H}_{\rm all}$ is the hypothesis space consisting of all hypothesis functions, and $h^{\rm out}$ is a constant function that $h^{\rm out}:=2$, here $1$ represents ID data and $2$ represents OOD data.

The condition $h^{\rm in}\in\mathcal{H}$ presented in Theorem 6 is mild. Many practical hypothesis spaces satisfy this condition, e.g., the FCNN-based hypothesis space (Proposition 1 in Appendix K), score-based hypothesis space (Proposition 2 in Appendix K) and universal kernel-based hypothesis space. Theorem 6 implies that if $K=1$ and OOD detection is learnable in $\mathscr{D}^{s}_{XY}$ for $\mathcal{H}$, then the hypothesis space $\mathcal{H}$ should contain almost all hypothesis functions, implying that if the OOD detection can be learnable in the distribution-agnostic case, then a large-capacity model is necessary.

Next, we extend Theorem 6 to a general case, i.e., $K>1$. When $K>1$, we will first use a binary classifier $h^{b}$ to classify the ID and OOD data. Then, for the ID data identified by $h^{b}$, an ID hypothesis function $h^{\rm in}$ will be used to classify them into corresponding ID classes. We state this strategy as follows: given a hypothesis space $\mathcal{H}^{\rm in}$ for ID distribution and a binary classification hypothesis space $\mathcal{H}^{\rm b}$ introduced in Section 2, we use $\mathcal{H}^{\rm in}$ and $\mathcal{H}^{\rm b}$ to construct an OOD detection’s hypothesis space $\mathcal{H}$, which consists of all hypothesis functions $h$ satisfying the following condition: there exist $h^{\rm in}\in\mathcal{H}^{\rm in}$ and $h^{\rm b}\in\mathcal{H}^{b}$ such that for any $\mathbf{x}\in\mathcal{X}$,

Let $|\mathcal{X}|<+\infty$ and $\mathcal{H}=\mathcal{H}^{\rm in}\bullet\mathcal{H}^{\rm b}$. If $\mathcal{H}_{\rm all}-\{h^{\rm out}\}\subset\mathcal{H}^{\rm b}$ and Condition 2 holds, then OOD detection is learnable in $\mathscr{D}_{XY}^{s}$ for $\mathcal{H}$, where $\mathcal{H}_{\rm all}$ and $h^{\rm out}$ are defined in Theorem 6.

OOD Detection in the Finite-ID-Distribution Space. Since researchers can only collect finite ID datasets as the training data in the process of algorithm design, it is worthy to study the learnability of OOD detection in the finite-ID-distribution space $\mathscr{D}_{XY}^{F}$. We first show two necessary concepts below.

Given a domain space $\mathscr{D}_{XY}$, we say any two domains $D_{XY}\in\mathscr{D}_{XY}$ and $D_{XY}^{\prime}\in\mathscr{D}_{XY}$ are ID consistency, if $D_{X_{\rm I}Y_{\rm I}}=D_{X_{\rm I}Y_{\rm I}}^{\prime}$. We use the notation $\sim$ to represent the ID consistency, i.e., $D_{XY}\sim D_{XY}^{\prime}$ if and only if $D_{XY}$ and $D_{XY}^{\prime}$ are ID consistency.

It is easy to check that the ID consistency $\sim$ is an equivalence relation. Therefore, we define the set $[D_{XY}]:=\{D_{XY}^{\prime}\in\mathscr{D}_{XY}:D_{XY}\sim D_{XY}^{\prime}\}$ as the equivalence class with respect to space $\mathscr{D}_{XY}$.

For any equivalence class $[D_{XY}^{\prime}]$ with respect to $\mathscr{D}_{XY}$ and any $\epsilon>0$, there exists a hypothesis function $h_{\epsilon}\in\mathcal{H}$ such that for any domain $D_{XY}\in[D_{XY}^{\prime}]$,

In Appendix F, Lemma 2 has implied that Condition 3 is a general version of Condition 1. Next, Theorem 8 indicates that Condition 3 is the necessary and sufficient condition in the space $\mathscr{D}_{XY}^{F}$.

Theorem 8. Suppose that $\mathcal{X}$ is a bounded set. OOD detection is learnable in the finite-ID-distribution space $\mathscr{D}_{XY}^{F}$ for $\mathcal{H}$ if and only if the compatibility condition (i.e., Condition 3) holds. Furthermore, the learning rate $\epsilon_{\rm cons}(n)$ can attain ${O}(1/\sqrt{n^{1-\theta}})$, for any $\theta\in(0,1)$.

Theorem 8 shows that, in the process of algorithm design, OOD detection cannot be successful without the compatibility condition. Theorem 8 also implies that Condition 3 is essential for the learnability of OOD detection. This motivates us to study whether OOD detection can be successful in more general spaces (e.g., the density-based space), when the compatibility condition holds.

OOD Detection in the Density-based Space. To ensure that Condition 3 holds, we consider a basic assumption in learning theory—Realizability Assumption (see Appendix D.2), i.e., for any $D_{XY}\in\mathscr{D}_{XY}$, there exists $h^{*}\in\mathcal{H}$ such that $R_{D}(h^{*})=0$. We discover that in the density-based space $\mathscr{D}_{XY}^{\mu,b}$, Realizability Assumption can conclude the compatibility condition (i.e., Condition 3). Based on this observation, we can prove the following theorem:

Theorem 9. Given a density-based space $\mathscr{D}_{XY}^{\mu,b}$, if $\mu(\mathcal{X})<+\infty$, the Realizability Assumption holds, then when $\mathcal{H}$ has finite Natarajan dimension , OOD detection is learnable in $\mathscr{D}_{XY}^{\mu,b}$ for $\mathcal{H}$. Furthermore, the learning rate $\epsilon_{\rm cons}(n)$ can attain ${O}(1/\sqrt{n^{1-\theta}})$, for any $\theta\in(0,1)$.

To further investigate the importance and necessary of Realizability Assumption, Theorem 11 has indicated that in some practical scenarios, Realizability Assumption is the necessary and sufficient condition for the learnability of OOD detection in the density-based space. Therefore, Realizability Assumption may be indispensable for the learnability of OOD detection in some practical scenarios.

Connecting Theory to Practice

In Section 5, we have shown the successful scenarios where OOD detection problem can be addressed in theory. In this section, we will discuss how the proposed theory is applied to two representative hypothesis spaces—neural-network-based hypothesis spaces and score-based hypothesis spaces.

In Appendix L, Lemma 10 shows $\mathbf{q}\lesssim\mathbf{q}^{\prime}\Rightarrow\mathcal{F}_{\mathbf{q}}^{\sigma}\subset\mathcal{F}_{\mathbf{q}^{\prime}}^{\sigma}$. We use $\lesssim$ to compare the sizes of FCNNs.

FCNN-based Hypothesis Space. Let $l_{g}=K+1$. The FCNN-based scoring function space $\mathcal{F}_{\mathbf{q}}^{\sigma}$ can induce an FCNN-based hypothesis space. For any $\mathbf{f}_{\mathbf{w},\mathbf{b}}\in\mathcal{F}_{\mathbf{q}}^{\sigma}$, the induced hypothesis function is:

Then, the FCNN-based hypothesis space is defined as $\mathcal{H}_{\mathbf{q}}^{\sigma}:=\{h_{\mathbf{w},\mathbf{b}}:\forall~{}\textnormal{weights}~{}\mathbf{w},~{}\forall~{}\textnormal{bias}~{}\mathbf{b}\}.$

$\bullet$ energy-based function : $\lambda\in(0,+\infty)$ and $T>0$,

Using $E$, $\lambda$ and $\mathbf{f}\in\mathcal{F}_{\mathbf{q}}^{\sigma}$, we have a classifier: $h^{\lambda}_{\mathbf{f},E}(\mathbf{x})=1$, if $E(\mathbf{f}(\mathbf{x}))\geq\lambda$; otherwise, $h^{\lambda}_{\mathbf{f},E}(\mathbf{x})=2$, where $1$ represents the ID data and $2$ represents the OOD data. Hence, a binary classification hypothesis space $\mathcal{H}^{b}$, which consists of all $h^{\lambda}_{\mathbf{f},E}$, is generated. We define $\mathcal{H}^{{\sigma},\lambda}_{{\mathbf{q}},E}:=\{h^{\lambda}_{\mathbf{f},E}:\forall\mathbf{f}\in\mathcal{F}_{\mathbf{q}}^{\sigma}\}$.

Learnability of OOD Detection in Different Hypothesis Spaces. Next, we present applications of our theory regarding the above two practical and important hypothesis spaces $\mathcal{H}_{\mathbf{q}}^{\sigma}$ and $\mathcal{H}_{\mathbf{q},E}^{\sigma,\lambda}$.

Suppose that Condition 2 holds and the hypothesis space $\mathcal{H}$ is FCNN-based or score-based, i.e., $\mathcal{H}=\mathcal{H}_{\mathbf{q}}^{\sigma}$ or $\mathcal{H}=\mathcal{H}^{\rm in}\bullet\mathcal{H}^{\rm b}$, where $\mathcal{H}^{\rm in}$ is an ID hypothesis space, $\mathcal{H}^{\rm b}=\mathcal{H}^{{\sigma},\lambda}_{{\mathbf{q}},E}$ and $\mathcal{H}=\mathcal{H}^{\rm in}\bullet\mathcal{H}^{\rm b}$ is introduced below Eq. (4), here $E$ is introduced in Eqs. (5) or (6). Then There is a sequence $\mathbf{q}=(l_{1},...,l_{g})$ such that OOD detection is learnable in the separate space $\mathscr{D}^{s}_{XY}$ for $\mathcal{H}$ if and only if $|\mathcal{X}|<+\infty$. Furthermore, if $|\mathcal{X}|<+\infty$, then there exists a sequence $\mathbf{q}=(l_{1},...,l_{g})$ such that for any sequence $\mathbf{q}^{\prime}$ satisfying that $\mathbf{q}\lesssim\mathbf{q}^{\prime}$, OOD detection is learnable in $\mathscr{D}^{s}_{XY}$ for $\mathcal{H}$.

Theorem 10 states that 1) when the hypothesis space is FCNN-based or score-based, the finite feature space is the necessary and sufficient condition for the learnability of OOD detection in the separate space; and 2) a larger architecture of FCNN has a greater probability to achieve the learnability of OOD detection in the separate space. Note that when we select Eqs. (5) or (6) as the scoring function $E$, Theorem 10 also shows that the selected scoring functions $E$ can guarantee the learnability of OOD detection, which is a theoretical support for the representative works . Furthermore, Theorem 11 also offers theoretical supports for these works in the density-based space, when $K=1$.

Suppose that each domain $D_{XY}$ in $\mathscr{D}_{XY}^{\mu,b}$ is attainable, i.e., $\operatorname*{arg\,min}_{h\in\mathcal{H}}R_{D}(h)\neq\emptyset$ (the finite discrete domains satisfy this). Let $K=1$ and the hypothesis space $\mathcal{H}$ be score-based $($$\mathcal{H}=\mathcal{H}_{\mathbf{q},E}^{\sigma,\lambda}$, where $E$ is in Eqs. (5) or (6)$)$ or FCNN-based $(<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi mathvariant="script">H</mi><mo>=</mo><msubsup><mi mathvariant="script">H</mi><mi mathvariant="bold">q</mi><mi>σ</mi></msubsup></mrow><annotation encoding="application/x-tex">\mathcal{H}=\mathcal{H}_{\mathbf{q}}^{\sigma}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathcal" style="margin-right:0.0097em;">H</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1.0975em;vertical-align:-0.3831em;"></span><span class="mord"><span class="mord mathcal" style="margin-right:0.0097em;">H</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.7144em;"><span style="top:-2.453em;margin-left:-0.0097em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathbf mtight">q</span></span></span></span><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight" style="margin-right:0.0359em;">σ</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.3831em;"><span></span></span></span></span></span></span></span></span></span></span>)$. If $\mu(\mathcal{X})<+\infty$, then the following four conditions are equivalent: Learnability in $\mathscr{D}_{XY}^{\mu,b}$ for $\mathcal{H}$ $\iff$ Condition 1 $\iff$ Realizability Assumption $\iff$ Condition 3

Theorem 11 still holds if the function space $\mathcal{F}_{\mathbf{q}}^{\sigma}$ is generated by Convolutional Neural Network.

Overlap and Benefits of Multi-class Case. We investigate when the hypothesis space is FCNN-based or score-based, what will happen if there exists an overlap between the ID and OOD distributions?

Let $K=1$ and the hypothesis space $\mathcal{H}$ be score-based $($$\mathcal{H}=\mathcal{H}_{\mathbf{q},E}^{\sigma,\lambda}$, where $E$ is in Eqs. (5) or (6)$)$ or FCNN-based $(<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi mathvariant="script">H</mi><mo>=</mo><msubsup><mi mathvariant="script">H</mi><mi mathvariant="bold">q</mi><mi>σ</mi></msubsup></mrow><annotation encoding="application/x-tex">\mathcal{H}=\mathcal{H}_{\mathbf{q}}^{\sigma}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathcal" style="margin-right:0.0097em;">H</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1.0975em;vertical-align:-0.3831em;"></span><span class="mord"><span class="mord mathcal" style="margin-right:0.0097em;">H</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.7144em;"><span style="top:-2.453em;margin-left:-0.0097em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathbf mtight">q</span></span></span></span><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight" style="margin-right:0.0359em;">σ</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.3831em;"><span></span></span></span></span></span></span></span></span></span></span>)$. Given a prior-unknown space $\mathscr{D}_{XY}$, if there exists a domain $D_{XY}\in\mathscr{D}_{XY}$, which has an overlap between ID and OOD distributions (see Definition 4), then OOD detection is not learnable in the domain space $\mathscr{D}_{XY}$ for $\mathcal{H}$.

When $K=1$ and the hypothesis space is FCNN-based or score-based, Theorem 12 shows that overlap between ID and OOD distributions is the sufficient condition for the unlearnability of OOD detection. Theorem 12 takes roots in the conditions $\inf_{h\in\mathcal{H}}R_{D}^{\rm in}(h)=0$ and $\inf_{h\in\mathcal{H}}R_{D}^{\rm out}(h)=0$. However, when $K>1$, we can ensure $\inf_{h\in\mathcal{H}}R_{D}^{\rm in}(h)>0$ if ID distribution $D_{X_{\rm I}Y_{\rm I}}$ has overlap between ID classes. By this observation, we conjecture that when $K>1$, OOD detection is learnable in some special cases where overlap exists, even if the hypothesis space is FCNN-based or score-based.

Discussion

Understanding Far-OOD Detection. Many existing works study the far-OOD detection issue. Existing benchmarks include 1) MNIST as ID dataset, and Texture , CIFAR-$10$ or Place$365$ as OOD datasets; and 2) CIFAR-$10$ as ID dataset, and MNIST , or Fashion-MNIST as OOD datasets. In far-OOD case, we find that the ID and OOD datasets have different semantic labels and different styles. From the theoretical view, we can define far-OOD detection tasks as follows: for $\tau>0$, a domain space $\mathscr{D}_{XY}$ is $\tau$-far-OOD, if for any domain $D_{XY}\in\mathscr{D}_{XY}$,

Theorems 7, 8 and 10 imply that under appropriate hypothesis space, $\tau$-far-OOD detection is learnable. In Theorem 7, the condition $|\mathcal{X}|<+\infty$ is necessary for the separate space. However, one can prove that in the far-OOD case, when $\mathcal{H}^{\rm in}$ is agnostic PAC learnable for ID distribution, the results in Theorem 7 still holds, if the condition $|\mathcal{X}|<+\infty$ is replaced by a weaker condition that $\mathcal{X}$ is compact. In addition, it is notable that when $\mathcal{H}^{\rm in}$ is agnostic PAC learnable for ID distribution and $\mathcal{X}$ is compact, the KNN-based OOD detection algorithm is consistent in the $\tau$-far-OOD case.

Understanding Near-OOD Detection. When the ID and OOD datasets have similar semantics or styles, OOD detection tasks become more challenging. consider this issue and name it near-OOD detection. Existing benchmarks include 1) MNIST as ID dataset, and Fashion-MNIST or Not-MNIST as OOD datasets; and 2) CIFAR-$10$ as ID dataset, and CIFAR-$100$ as OOD dataset. From the theoretical view, some near-OOD tasks may imply the overlap condition, i.e. Definition 4. Therefore, Theorems 3 and 12 imply that near-OOD detection may be not learnable. Developing a theory to understand the feasibility of near-OOD detection is still an open question.

Understanding One-class Novelty Detection. In one-class novelty detection and semantic anomaly detection (i.e. $K=1$), Theorem 6 has revealed that it is necessary to use a large-capacity model to ensure the good generalization in the separate space. Theorem 3 and Theorem 12 suggest that we should try to avoid the overlap between ID and OOD distributions in the one-class case. If the overlap cannot be avoided, we suggest considering the multi-class OOD detection instead of the one-class case. Additionally, in the density-based space, Theorem 11 has shown that it is necessary to select a suitable hypothesis space satisfying the Realizability Assumption to ensure the learnability of OOD detection in the density-based space. Generally, a large-capacity model can be helpful to guarantee that the Realizability Assumption holds.

Related Work

We briefly review the related theoretical works below. See Appendix A for detailed related works.

OOD Detection Theory. understands the OOD detection via goodness-of-fit tests and typical set hypothesis, and argues that minimal density estimation errors can lead to OOD detection failures without assuming an overlap between ID and OOD distributions. Beyond , paves a new avenue to designing provable OOD detection algorithms. Compared to , our theory focuses on the PAC learnable theory of OOD detection and identifies several necessary and sufficient conditions for the learnability of OOD detection, opening a door to study OOD detection in theory.

Open-set Learning Theory. and propose the agnostic PAC learning bounds for open-set detection and open-set domain adaptation, respectively. Unfortunately, all require that the test data are indispensable during the training process. To investigate open-set learning (OSL) without accessing the test data during training, proposes and investigates the almost agnostic PAC learnability for OSL. However, the assumptions used in are very strong and unpractical.

Learning Theory for Classification with Reject Option. Many works also investigate the classification with reject option (CwRO) problem, which is similar to OOD detection in some cases. study the learning theory and propose the PAC learning bounds for CwRO. However, compared to our work regarding OOD detection, existing CwRO theories mainly focus on how the ID risk $R^{\rm in}_{D}$ (i.e., the risk that ID data is wrongly classified) is influenced by special rejection rules. Our theory not only focuses on the ID risk, but also pays attention to the OOD risk.

Robust Statistics. In the field of robust statistics , researchers aim to propose estimators and testers that can mitigate the negative effects of outliers (similar to OOD data). The proposed estimators are supposed to be independent of the potentially high dimensionality of the data . Existing works in the field have identified and resolved the statistical limits of outlier robust statistics by constructing estimators and proving impossibility results. In the future, it is a promising and interesting research direction to study the robustness of OOD detection based on robust statistics.

PQ Learning Theory. Under some conditions, PQ learning theory can be regarded as the PAC theory for OOD detection in the semi-supervised or transductive learning cases, i.e., test data are required during training. Besides, aim to give the PAC estimation under Realizability Assumption . Our theory does not only study the PAC estimation in the realization cases, but also studies the other cases, which are more difficult than PAC theory under Realizability Assumption.

Conclusions and Future Works

Detecting OOD data has shown its significance in improving the reliability of machine learning. However, very few works discuss OOD detection in theory, which hinders real-world applications of OOD detection algorithms. In this paper, we are the first to provide the PAC theory for OOD detection. Our results imply that we cannot expect a universally consistent algorithm to handle all scenarios in OOD detection. Yet, it is still possible to make OOD detection learnable in certain scenarios. For example, when we design OOD detection algorithms, we normally only have finite ID datasets. In this real scenario, Theorem 8 provides a necessary and sufficient condition for the success of OOD detection. Our theory reveals many necessary and sufficient conditions for the learnability of OOD detection, hence opening a door to studying the learnability of OOD detection. In the future, we will focus on studying the robustness of OOD detection based on robust statistics .

Acknowledgment

JL and ZF were supported by the Australian Research Council (ARC) under FL190100149. YL is supported by the AFOSR Young Investigator Program Award. BH was supported by the RGC Early Career Scheme No. 22200720 and NSFC Young Scientists Fund No. 62006202. ZF would also like to thank Prof. Peter Bartlett and Dr. Tongliang Liu for productive discussions.

References

Checklist

Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? [Yes]

Did you describe the limitations of your work? [Yes] See Appendix B

Did you discuss any potential negative societal impacts of your work? [Yes] See Appendix B

Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]

If you are including theoretical results…

Did you state the full set of assumptions of all theoretical results? [Yes]

Did you include complete proofs of all theoretical results? [Yes]

Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A]

Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]

Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A]

Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]

If you are using existing assets (e.g., code, data, models) or curating/releasing new assets…

If your work uses existing assets, did you cite the creators? [N/A]

Did you mention the license of the assets? [N/A]

Did you include any new assets either in the supplemental material or as a URL? [N/A]

Did you discuss whether and how consent was obtained from people whose data you’re using/curating? [N/A]

Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]

If you used crowdsourcing or conducted research with human subjects…

Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]

Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]

Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]

Appendix A Detailed Related Work

OOD Detection Algorithms. We will briefly review many representative OOD detection algorithms in three categories. 1) Classification-based methods use an ID classifier to detect OOD data Note that, some methods assume that OOD data are available in advance . However, the exposure of OOD data is a strong assumption . We do not consider this situation in our paper.. Representative works consider using the maximum softmax score , temperature-scaled score and energy-based score to identify OOD data. 2) Density-based methods aim to estimate an ID distribution and identify the low-density area as OOD data . 3) The recent development of generative models provides promising ways to make them successful in OOD detection . Distance-based methods are based on the assumption that OOD data should be relatively far away from the centroids of ID classes , including Mahalanobis distance , cosine similarity , and kernel similarity .

Early works consider using the maximum softmax score to express the ID-ness . Then, temperature scaling functions are used to amplify the separation between the ID and OOD data . Recently, researchers propose hyperparameter-free energy scores to improve the OOD uncertainty estimation . Additionally, researchers also consider using the information contained in gradients to help improve the performance of OOD detection .

Except for the above algorithms, researchers also study the situation, where auxiliary OOD data can be obtained during the training process . These methods are called outlier exposure, and have much better performance than the above methods due to the appearance of OOD data. However, the exposure of OOD data is a strong assumption . Thus, researchers also consider generating OOD data to help the separation of OOD and ID data . In this paper, we do not make an assumption that OOD data are available during training, since this assumption may not hold in real world.

OOD Detection Theory. rejects the typical set hypothesis, the claim that relevant OOD distributions can lie in high likelihood regions of data distribution, as implausible. argues that minimal density estimation errors can lead to OOD detection failures without assuming an overlap between ID and OOD distributions. Compared to , our theory focuses on the PAC learnable theory of OOD detection. If detectors are generated by FCNN, our theory (Theorem 12) shows that the overlap is the sufficient condition to the failure of learnability of OOD detection, which is complementary to . In addition, we identify several necessary and sufficient conditions for the learnability of OOD detection, which opens a door to studying OOD detection in theory. Beyond , paves a new avenue to designing provable OOD detection algorithms. Compared to , our paper aims to characterize the learnability of OOD detection to answer the question: is OOD detection PAC learnable?

Open-set Learning Theory. is the first to propose the agnostic PAC guarantees for open-set detection. Unfortunately, the test data must be used during the training process. considers the open-set domain adaptation (OSDA) and proposes the first learning bound for OSDA. mainly depends on the positive-unlabeled learning techniques . However, similar to , the test data must be available during training. To study open-set learning (OSL) without accessing the test data during training, proposes and studies the almost PAC learnability for OSL, which is motivated by transfer learning . In our paper, we study the PAC learnability for OOD detection, which is an open problem proposed by .

Learning Theory for Classification with Reject Option. Many works also investigate the classification with reject option (CwRO) problem, which is similar to OOD detection in some cases. study the learning theory and propose the agnostic PAC learning bounds for CwRO. However, compared to our work regarding OOD detection, existing CwRO theories mainly focus on how the ID risk (i.e., the risk that ID data is wrongly classified) is influenced by special rejection rules. Our theory not only focuses on the ID risk, but also pays attention to the OOD risk.

Robust Statistics. In the field of robust statistics , researchers aim to propose estimators and testers that can mitigate the negative effects of outliers (similar to OOD data). The proposed estimators are supposed to be independent of the potentially high dimensionality of the data . Existing works in the field have identified and resolved the statistical limits of outlier robust statistics by constructing estimators and proving impossibility results. In the future, it is a promising and interesting research direction to study the robustness of OOD detection based on robust statistics.

PQ Learning Theory. Under some conditions, PQ learning theory can be regarded as the PAC theory for OOD detection in the semi-supervised or transductive learning cases, i.e., test data are required during the training process. Additionally, PQ learning theory in aims to give the PAC estimation under Realizability Assumption . Our theory focuses on the PAC theory in different cases, which is more difficult and more practical than PAC theory under Realizability Assumption.

Appendix B Limitations and Potential Negative Societal Impacts

Limitations. The main limitation of our work lies in that we do not answer the most general question:

Given any hypothesis space $\mathcal{H}$ and space $\mathscr{D}_{XY}$, what is the necessary and sufficient condition to ensure the PAC learnability of OOD detection?

However, this question is still difficult to be addressed, due to limited mathematical skills. Yet, based on our observations and the main results in our paper, we believe the following result may hold:

Conjecture: If $\mathcal{H}$ is agnostic learnable for supervised learning, then OOD detection is learnable in $\mathscr{D}_{XY}$ if and only if compatibility condition (i.e., Condition 3) holds.

Potential Negative Societal Impacts. Since our paper is a theoretical paper and the OOD detection problem is significant to ensure the safety of deploying existing machine learning algorithms, there are no potential negative societal impacts in our paper.

Appendix C Discussions and Details about Experiments in Figure 1

In this section, we summarize our main results, then give the details of the experiments in Figure 1.

We summarize our main results as follows:

$\bullet$ A necessary condition (i.e., Condition 1) for the learnability of OOD detection is proposed. Theorem 2 shows that Condition 1 is the necessary and sufficient condition for the learnability of OOD detection, when the domain space is the single-distribution space $\mathscr{D}_{XY}^{D_{XY}}$. This implies the Condition 1 is the necessary condition for the learnability of OOD detection.

$\bullet$ Theorem 3 has shown that the overlap between ID and OOD data can lead the failures of OOD detection under some mild assumptions. Furthermore, Theorem 12 shows that when $K=1$, the overlap is the sufficient condition for the failures of OOD detection, when the hypothesis space is FCNN-based or score-based.

$\bullet$ Theorem 4 provides an impossibility theorem for the total space $\mathscr{D}_{XY}^{\rm all}$. OOD detection is not learnable in $\mathscr{D}_{XY}^{\rm all}$ for any non-trivial hypothesis space.

$\bullet$ Theorem 5 gives impossibility theorems for the separate space $\mathscr{D}_{XY}^{s}$. To ensure the impossibility theorems hold, mild assumptions are required. Theorem 5 also implies that OOD detection may be learnable in the separate space $\mathscr{D}_{XY}^{s}$, if the feature space is finite, i.e., $|\mathcal{X}|<+\infty$. Additionally, Theorem 10 implies that the finite feature space may be the necessary condition to ensure the learnability of OOD detection in the separate space.

$\bullet$ When $|\mathcal{X}|<+\infty$ and $K=1$, Theorem 6 provides the necessary and sufficient condition for the learnability of OOD detection in the separate space $\mathscr{D}_{XY}^{s}$. Theorem 6 implies that if the OOD detection can be learnable in the distribution-agnostic case, then a large-capacity model is necessary. Based on Theorem 6, Theorem 7 studies the learnability in the $K>1$ case.

$\bullet$ The compatibility condition (i.e., Condition 3) for the learnability of OOD detection is proposed. Theorem 8 shows that Condition 3 is the necessary and sufficient condition for the learnability of OOD detection in the finite-ID-distribution space $\mathscr{D}_{XY}^{F}$. This also implies Condition 3 is the necessary condition for any prior-unknown space. Note that we can only collect finite ID datasets to build models. Hence, Theorem 8 can handle the most practical scenarios.

$\bullet$ To further understand the importance of the compatibility condition (Condition 3). Theorem 9 considers the density-based space $\mathscr{D}_{XY}^{\mu,b}$. We discover that Realizability Assumption implies the compatibility condition in the density-based space. Based on this observation, we prove that OOD detection is learnable in $\mathscr{D}_{XY}^{\mu,b}$ under Realizability Assumption.

$\bullet$ Theorem 10 gives practical applications of our theory. In this theorem, we discover that the finite feature space is a necessary and sufficient condition for the learnability of OOD detection in the separate space $\mathscr{D}_{XY}^{s}$, when the hypothesis space is FCNN-based or score-based.

$\bullet$ Theorem 11 has shown that when $K=1$ and the hypothesis space is FCNN-based or score-based, Realizability Assumption, Condition 3, Condition 1 and the learnability of OOD detection in the density-based space $\mathcal{D}_{XY}^{\mu,b}$ are all equivalent.

$\bullet$ Meaning of Our Theory. In classical statistical learning theory, the generalization theory guarantees that a well-trained classifier can be generalized well on the test set as long as the training and test sets are from the same distribution . However, since the OOD data are unseen during the training process, it is very difficult to determine whether the generalization theory holds for OOD detection.

Normally, OOD data are unseen and can be various. We hope that there exists an algorithm that can be used for the various OOD data instead of some certain OOD data, which is the reason why the generalization theory for OOD detection needs to be developed. In this paper, we investigate the generalization theory regarding OOD detection and point out when the OOD detection can be successful. Our theory is based on the PAC learning theory. The impossibility theorems and the given necessary and sufficient conditions outlined provide important perspectives from which to think about OOD detection.

C.2 Details of Experiments in Figure 1

In this subsection, we present details of the experiments in Figure 1, including data generation, configuration and OOD detection procedure.

Data Generation. ID and OOD data are drawn from the following uniform (U) distributions (note that we use ${\rm U}(\mathbf{I})$ to present the uniform distribution in region $\mathbf{I}$). $\bullet$ The marginal distribution of ID distribution for class $c$: for any $c\in\{1,...,10\}$,

here $d_{i}=5+{\rm gap}_{\rm II}*(i-1)+4(i-2)$ and ${\rm gap}_{\rm II}$ is a positive constant. $\bullet$ The class-prior probability for class $c$: for any $c\in\{1,...,10\}$,

$\bullet$ The marginal distribution of OOD distribution:

Figure 2 shows the OOD and ID distributions, when ${\rm gap}_{\rm II}=20$ and ${\rm gap}_{\rm IO}=-2$. In Figure 1, we draw $n$ data from ID distribution ($n=15,000,20,000,25,000$) and $25,000$ data from the OOD distribution.