Is Out-of-Distribution Detection Learnable?
Authors: Zhen Fang
Yixuan Li
Jie Lu
Jiahua Dong
Bo Han
Feng Liu
Venue: NeurIPS 2022 Accept (2022)
Keywords: AI Reliability

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.

Is Out-of-Distribution Detection Learnable?
Zhen Fang', Yixuan Li², Jie Lu'; Jiahua Dong24, Bo Han Feng Liu Australian Artificial Intelligence Institute, University of Technology Sydney. Department of Computer Sciences, University of Ausconsin-Madisee State Key Laboratory of Robotics, Shenyang Institute of Automation, Chinese Academy of Sciences. *ETH Zurich, Switzerland.
Department of Computer Science, Hong Kong Baptist University.
School Mathematics and Statistics, University Melbourne. { 1zhen. fang, jie. lutuutt edu, au, sharonli Ccs wisc. edu, dong]iahual 11 com, bhanm 1 @comp. hkbu. edu. hk, feng. 1 liule funimelb.... edu.ueub.........ee..m.......... au
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-distributte test data may come from classes that 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 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 impossibil- ity 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.
(OOD) detection, where
Introduction
The success of supervised learning is established implicit assumption that training and test data share a same distribution, i.e,, in-distribution (ID) [1, 2, 3, 4]. However, test data distribution in many real-world scenarios may violate the assumption and, instead, contain out-of-distributtin (OOD) data whose labels have not been seen during the training process [5, 6]. To mitigate the risk of OOD data, researchers have considered 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 ensure the reliable deployment of machine learning models the real world. A rich line of algorithms have been developed to empirically address the OOD detection problem [6. 7, 8, 9, 10, 11, 12, 13. 14, 15, 16, 17, 18. 19, 20]. 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, provide theoretical framework understand the learnability of the OOD detection problem. We investigate the probably approximately correct (PAC) learning theory of OOD detection, which is posed 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.
"Corresponding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In many real-world scenarios, OOD data can be diverse and wnoor-unkkown. 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 [4]. 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 space consisting of some classifiers. Existing agnostic PAC theories in supervised learning [21. 22] are distributionn-fre free,, i.e., the domain space consists of all domains. Yet. in Theorem 4, we shows that the learning theory of OOD detection not distribution freee. 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 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 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 finite. Furthermore, we investigate the learnability of OOD detection in other more practical domain spaces, e.g., the finite-ID-disee ID-distribution space (Theorem 8) and the density- based space (Theorem 9). By studying the finite-ID ID-distribution space, we discover a compatibility condition (Condition 3) that is necessary and sufficient condition for this space. Next, we further investigate the compatibility condition in the density- space, and find that such condition 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 iiiit-IDddistribution 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 [7, 8, 23). Third, our theory shows that OOD detection is learnable in amage-bases 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.
2 Learning Setups
We start by introducing the necessary concepts and notations for our theoretical framework. Given a feature space X C Rd and a label space ) := [I,... K). we have an ID joint distribution D X over X' x Y, where X, E X and Y1 E y are random variables. We also have OOD joint distribution Dx,Yo- where Xo is a random variable from X, but Yo is a random variable whose outputs do not belong to y. During testing,
will meet mixture of ID and OOD joint distributions: DXY == (1 - out) D Dx,y; + x out DxoY. and can only observe the marginal distribution Dx :=
(1 - n out Dxi + π out D Dxo. where the constant out E [0, 1) is an unknown class-prior probability.
2

---

Problem 1 (OOD Detection [4]). Given an ID joint distribution DX,,, and a training data S := {(x', y )...., (x" y drawn independent and identically distributed from D D the aim of OOD detection is to train classifier I by using the training data S such that, for any test data x drawn from the mixed marginal distribution Dx: 1) if x is an observation from D Dxp I can classify x into correct ID classes; and 2) if is an observation from Dxo- I can detect x as OOD data.
According to the survey [4], when K > 1, OOD detection is also known the open-set recognition or open-set learning [24, 25]; and when K" = 1, OOD detection reduces to one-class novelty detection and semantic anomaly detection [26, 27, 28).
OOD Label and Domain Space. Based on Problem I, 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., Yo = K + 1 [24, 29]. To investigate the PAC learnability of OOD detection, we define a domain space 2xY. which is set consisting of some joint distributions Dxy mixed by some ID joint distributions and some OOD joint distributions. In this paper, the joint distribution Dxy mixed by ID joint distribution Dx,x, and OOD joint distribution DXo Yo is called domain.
Hypothesis Spaces and Scoring Function Spaces. A hypothesis space H is subset of function space, Le.,, H C {h:
X + y U [K + 1]}. We set Hin C (h: X' + 3 to the II) hypothesis space. We also define Hb C (h : X - {1,2}} as the hypothesis space for binary classification, where I represents the ID data, and 2 represents the OOD data. The function h is called the hypothesis function. A scoring function space is a subset of function space, i.e., Fi C {f X - R'), where / is the output's 's dimension of the vector-vaie vaalud function f. The function f is called the scoring function.
Loss and Risks. Let Vau = yu {K + 1. Given a loss function Van x Van - 18 satisfying that E(y), y2) 0 if and only if y1 = 1/2 and any h H. then the risk with respect to DXY is
(h) == Bxxw)>DD> ((h(x),
The a-riisk (h) == (1 a) B + RRD (h), Vo E [0, 1]. where the risks RB) AD (h) are RB(h) == (xxx))>DxM ((((x),))
RD (h) == Dx {(1(x), K + 1).
Learnability. We aim to select hypothesis function h E 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: Definition (Learnability of OOD Detection). Given a domain space 2xY and a hypothesis space H C {h: X + }. we say OOD detection is learnable in 2XY for H. if there exists an algorithm A - (X x vyyn + H and a monotonically decreasing sequence (cons(n), such that <cons (n) 0, as n +oc, and for any domain DXY E 2XY,
ES [RD(A(S))
inf RD(h)] S (c)one(t). kEW
An algorithm A for which this holds is said to be consistent with respect to 2XY.
Definition 1 is a natural extension of agnostic PAC learnability of supervised learning [30]. If for any DxY E IXY, zou 0, then Definition 2 is the agnostic PAC learnability of supervised learning. Although the expression of Definition 1 is different from the normal definition of agnostic PAC learning in [21], one can easily prove that they are equivalent when & is bounded, see Appendix D.3.
Since OOD data are unavailable, it is impossible to obtain information about the class class-prior probability Tuu Furthermore, in the real world, it is possible that out can be any value in [0, 1). Therefore, the imbalance issue between ID and OOD distributions, and the priori-unknown issue (i.e., nu is unknown) are the core challenges. To ease these challenges, researchers use AUROC, AUPR and FPR95 to estimate the performance of OOD detection [18, 31, 32, 33, 34, 35). It seems that there is gap between Definition I and existing works. To eliminate this gap. we revise Eq. (2) as follows:
ES (A(S)) inf R$ (h)) S (n), Va E [0, 1]. NEW
(3)
If an algorithm A satisfies Eq. (3), then the imbalance issue and the prior-unknown issue disappear. That is, 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:
Note that Pan x Vau is a finite set, therefore, is bounded. SSiiilar to [30], in this paper, regard algorithm mapping from U (X x )0)" to H.
3

---

Definition 2 (Strong Learnability of OOD Detection). Given domain space 9XY and a hypothesis space H C (h : X + ). we say OOD detection is strongly learnable in Xx for H. if there exists an algorithm A - (X ) HH and a monotonically decreasing sequence Econs (n),
such that Econs (n) + O, as +oc, and for any domain Dxy E 9XY,
ES (AS))
inf [2)()] S (n), Va E [0. hEH
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 2XY 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 Xx consists of all domains. However, due to the absence of OOD data during the training process [8, 14, 24), 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 2x and the hypothesis space H. That is, OOD detection learnable only when the domain space 2xy and the hypothesis space H satisfy some special conditions, egg., Condition I and Condition 3. We present our goal as follows:
Goal: given hypothesis space H and several representative domain spaces 2XY, 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 't focus on the distribution-Fi case, but focuses on discovering essential conditions to guarantce the learnability of OOD detection in several representative and practical domain spaces 9xy. By these essential conditions, we can know when OOD detection can be successful in real applications.
3 Learning in Priori-unknowe 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 9xY, 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 consider our theory in the prior-unknown spaces. The prior-unknown space is introduced as follows:
Definition 3. Given domain space 9XY. we say XX a priori-unknown space, ffr any domain DXY E 2xY and any E [0, 1), we have Dx == (1 Dxvi + aDxoYo E -xv.
Theorem 1. Given domain spaces 2xY and =xxy= (Dxx MD E 2XY, Va E [0, 1)}. then
1) Dxy y a priori-unknown space and XXY C '''v:
2) if Ix is a priori-umknown space, then Definition and Definition 2 are equivalent:
3) OOD detection is strongly learnable in 2x if and only if OOD) detection is learnable in D'yy-
The second result of Theorem I bridges the learnability and strong learnability, which implies that an algorithm is consistent with respect to a prior-unknown space, then this algorithm 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 undrow spaces. Furthermore, to demystify the learaailiiyy of OOD detection, we introduce five representative priori-unknown spaces:
Single-distribttion space 2 Dxy
For domain DXY. 2 2xx =(D% Va E [),
XY
Total space gelt, which consists of all domains.
Separate space Pxy, which consists of all domains that satisfy the separate condition, that is for any Dxy E Dy., suppDxo SsuppDx, = 0, where supp means the support set.
Finite- Finite-ID-distrine ID-iistribution space of which a prior-unknowe space satisfying that the number of distinct ID joint distributions Dx,r in 2 is finite, i.e., (DxM VDxy E 2 +00.
Density- bbsse space 2ub. which is prior-unknown space consisting of some domains satisfying that: for any Dxy, there exists a density function ff with 1/b < f < b in suppy and 0.5 Dx,

---

0.80
n=15,000
n=15,000
OOD
0.60
n-20 000
n=25,000 000
0.15
n-20.000
n=25,000
a-nikk
infox (956)
0.40
0.05
Cleas
Class K
0.00
0.00
0.20
0.40 0.60 0.80
1.00
0.00
0.20
0.40 0.60 0.80
1.00
Values of
Valuues of
(a) ID and OOD Distributions
(b) Overlap Exists
(c) No Overlap
Figure I: Illustration kn (h) (solid lines with triangle marks) and estimated Eg Dr. R& (A())
(dash lines) with E [0. 1) in different scenarios, where Dm. Dx,y, and the algorithm A is the free-energy OOD detection method [23]. Subfigure (a) shows the ID and OOD distributions. In (a), gapro represents distance between support sets of ID and OOD distributions. In (b), since there is an overlap between ID and OOD data, the solid line is a ployline. In (c), since there is no overlap hetween ID and OOD data, we can check that se (h) forms straight line (the solid line). However, since dash lines are always straight lines, observations
be obtained from (b) and (c): 1) dash lines cannot approximate the solid ployline in (b), which implies the unlearnability OOD detection; and 2) the solid line in (c) is straight line and may be approximated by the dash lines in (c). The above observations motivate us to propose Condition
0.5 Dx. = fdj,, where is measure defined over X. Note that if μu is discrete, then Dx is discrete distribution; and if μ is the Lebesgue measure, then Dx 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 distribution belonging
separate space 2xy y and 2) when designing have finite ID datasets, e.g., CIFAR-10 10, MNIST, SVHN, and ImageNet, to build a model. Then, finite-ID Mnite-ID-distrinee distrrrbibttion space 9 Xy can handle this real scenario. Note that the single-distribution space a special case of the finite-ID- ID-istribuutn space. In this paper, we mainly discuss these five spaces.
algorithm,
only
Impossibility Theorems for OOD Detection
In this section, first give necessary condition for the learnability of OOD detection. Then, show this necessary condition does not hold in the total space Φ and the separate space 2Xy-
Necessary Condition. We find necessary condition for the learnability of OOD detection, i.e. Con- dition I, motivated by the experiments in Figure Details of Figure can be found Appendix C.2.
Condition 1 (Linear Condition). For any Dxy E 2xx and any E [0,
inf (h) aa) a) inf (h) + inf RD (h). hEH
KER
To reveal the importance of Condition 1, Theorem 2 shows that Condition 1 is necessary and sufficient condition for the learnability of OOD detection if the 2x is the single-distribution space.
Theorem 2. Given a hypothesis space Ht and a domain Dxv, OOD detection is learnable in the single-distribation space 2Qx for H if and only if linear condition (i.e., Condition 1) holds.
Theorem implies that Condition is important for the learnability of OOD detection. Due to the simplicity of single-distrbuttion space, Theorem 2 implies that Condition is the necessary condition for the learnability of OOD detection in the prior-unknown space, see Lemma in Appendix F.
Impossibility Theorems. Here, we first study whether Condition holds in the total space Sxlly If Condition does not hold, then OOD detection is not learnable. Theorem 3 shows that Condition is not always satisfied, especially, when there is an overlap between the ID and OOD distributions:
Definition (Overlap Between ID and OOD). We say a domain DXy has overlap between ID and OOD distributions, if there is o o--fnite measure such that Dx is absolutely continuous with respect to ns and jí( Aoverlap) > O, where Aowerlap = (x E X fi(x) > and fo(x) >> 0}. Here fi and fo are the representers of Dx, and Dxo in Radon-Nikodym Theorem [36),
Dx fidp, Dxo f fodp.
5

---

Given a hypothesis space HH and a prior-unknown space PxY, ifere is Dxy E 9XY, which has overlap between ID and OOD, and inf Ri)(h) and nnf RD (h) = then Condition I does not hold. Therefore, OOD detection is not learnable in 2x for H.
Theorem 3.
Theorem 3 clearly shows that under proper conditions, Condition does not hold, if there exists 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 g for any non-trivial hypothesis space H.
Theorem 4 (Impossibility Theorem for Total Space), OOD detection is not learnable in the total space X for H. o H| > 1, where & maps ID labels to and maps OOD labels to 2.
Since the overlaps between ID and OOD distributions may cause that Condition I does not hold, we then consider studying the learnability of OOD detection in the separate space Ixy, where there are no overlaps between the ID and OOD distributions. However, Theorem 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, ie.,, Theorem 5, need mild assumption:
Assumption 1 (Separate Space for OOD). hypothesis space H separate for OOD data, ifr each data point x E X. there exists at least one hypothesis function hx E H. such that hx (x) = K + 1.
Assumption 1 means that every data point has the possibility to be detected as OOD data. Assump- tion 1 mild and can be satisfied by many hypothesis spaces, egg. 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- Shenik--Cherooenkis (VC) dimension [22] to measure the size of hypothesis space, and study the learnability of OOD detection in D based on the VC dimension.
Theorem 5 (Impossibility Theorem for Separate Space). If Assumption I holds, VCdim( H) < too and suPnEи {x E X : h(x) E y/ = +00, then OOD detection is not learnable in separate space Xx for H. where á 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 and 6).
When OOD Detection Can Be Successful
Here, we discuss when the OOD detection can be learnable in the separate space 2 finite-ID- distribution space Dfy and density-based space Luk. We first study the separate space 2xy
OOD Detection in the Separate Space. Theorem 5 has indicated that VCdim (d o H) = +oo or suPnez [x E X : h(x)= E VH < +o is necessary to ensure the learnability of OOD detection in 2x if Assumption holds. However, generally, hypothesis spaces generated by forwaforward neural networks with proper activation functions have finite VC dimension [37, 38]. Therefore, we study the learnability of OOD detection the case that | < +00, which implies that suPдch Ixx E X h(x) E ))1 too. Additionally, Theorem 10 also implies that | < +oo is the necessary and sufficient condition for the Icarnability of OOD detection in separate space, when the hypothesis space is generated by FCNN. Hence, | < +oo may be necessary in the space Dxy
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 Pxy, when |X] < toc.
Theorem 6. Let K 1 and |X'| < -30. Suppose that Assumption holds and the constant
function h := 1 E H. Then OOD detection is learnable in Pxy for H. if and only if Haul [hown) C H. where Hall is the hypothesis space consisting of all hypothesis functions, and hout a constant function that hout := 2, here 1 represents ID data and 2 represents OOD data.
The condition 1 E H presented Theorem is mild. Many practical hypothesis spaces satisfy this condition, e.g., the FCNN-based hypothesis space (Proposition 1 in Appendix K), score-based hy- pothesis space (Proposition 2 Appendix K) and universal kernel-based hypothesis space. Theorem 6 implics that if K = and OOD detection is learnable in y for H. then the hypothesis space H

---

should contain almost all hypothesis functions, implying that if the OOD detection can be learnable in the distribution aggnssic case, then a large-capacity model 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. classify the IDD and OOD data. Then, for the ID data identified by h2, ID hypothesis function ft will be used to classify them into corresponding ID classes. We state this strategy as follows: given a hypothesis space 7ith for ID distribution and binary classification hypothesis space H² introduced in Section 2, we use 7t and H to construct an OOD detection's 's hypothesis space H. which consists of all hypothesis functions h satisfying the following condition: there exist h H and h² E 7t such that for any x E X,
h(x) = i, if 4 (x) = and h (x) = 1; otherwise, h(x) K + 1.
(4)
We use 7ith 76b to represent hypothesis space consisting of all h defined in Eq. (4). In addition, we also need an additional condition for the loss function L. This condition is shown as follows:
Condition 2. E(y2, vi) S E(K + 1, ). for any in-distribution labels y and y2 EV.
Theorem 7. Let | < +o0 and H Hiu HH. Hall (hout } C HD and Condition 2 holds, then OOD detection is learnable in Fx for H. where Hall and hout are defined in Theorem 6.
OOD Detection in the Finite- Dai---DDDDitttttion 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-I--disrriie -iiittriibutinn space 9 Xy. We first show two necessary concepts below.
Definition 5 (ID Consistency). Given domain space 9XY, say any domains Dxy 2x and D'x E XXY are ID consistency, if Dx,Y, = D'x,y-- We use the notation ~ to represent the ID consistency, i.e,, DXY ~ D'xy if and only if Dxy and D'xy are ID consistency.
It is easy to check that the ID consistency ~ is equivalence relation. Therefore, we define the set [Dxy] == (D'xy E +xxY DXY ~ >'xy> as the equivalence class with respect to space 2XY- Condition 3 (Compatibility). For any equivalence class [D'yy] with respect to 9xY and any e > there exists hypothesis function he E 'H such that for any domain Dxy E [D'ylb.
he E (h' E H 12 (1-) S inf 12 (h) +e) n (h' E H Re)(h') S inf (1) + +e}. hEW
NER
In Appendix F, Lemma 2 has implied that Condition 3 is general version of Condition 1. Next, Theorem indicates that Condition is the necessary and sufficient condition the space Dxx-
Theorem 8. Suppose that X' is a bounded set. OOD detection is learnable in the finite-ID- distribution space d &y for H. if and only if the compatibility condition (i.e., Condition 3) holds. Furthermore, the learning rate Ccous can attain O(1/ "nl///nn"),, for any 9 E 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 is essential for the learmabliity 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 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 DXY E .xx, there exists h² E H such that RD(h") = O. We discover that in the density-based space Du.k 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 Dhd,, if p(x) < +o0, the Realizability Assumption holds, then when H has finite Natarajan dimension [21], 00D desection is learnable in Luch for H. Furthermore, the learning rate Ecous(n) can attain O(1/ D(1/Vn1-0) for any 8 E (0,
To further investigate the importance and necessary of Realizability Assumption, Theorem 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 Icarnability of OOD detection in some practical scenarios.
7

---

6 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- neeural-etwoork-bare hypothesis spaces and score- score-based hypothesis spaces.
(4..4,..... 1n), where I; and are positive use y represent the depth of neural network and use represent the width of the i-th layer. After the activation function a is selected', we can obtain the architecture of FCNN according to the sequence q. Let fw.b be the function generated by FCNN with weights and bias b. An FCNN-based scoring function space is defined as: Fq = {fw. : V weights w, A bias bj. In addition, for simplicity, given any two sequences q = (l,, ..... 44) and q' = (Li,..., l'g)), we use the notation q 2 q' to represent the following equations and inequalities:
Fully-connected Neural Networks. Given a sequence integers and g >
1) g S g4 = 14 = ./: 2)4 S 41 vi= l.... 9- 1; and 3) 4-11 S 4, Vi g.... of
In Appendix L, Lemma 10 shows q S q + Fq C Fq. We use S to compare the sizes of FCNNs.
FCNN-based Hypothesis Space. Let 1 - K + 1. The FCNN-based scoring function space Fq can induce an FCNN-based hypothesis space. For any fw,b E Fq. the induced hypothesis function is:
bw.b arg max f where Wwb is the k-th coordinate of fw.b-
AE((,....K11
Then, the FCNN-based hypothesis space is defined as Hg (/w,b V weights w, A bias b}.
Score-based Hypothesis Space. Many OOD detection algorithms detect OOD data by using score-based strategy. That is. given a threshold X, scoring function space Fi C {f X' + R'}
and a scoring function F: Fi - IR, then x is regarded as IID data if and only if F(((()) 2 X. We
introduce several representative scoring functions E' as follows: for any f [f .... J4] E Fi.
softmax-based function [7] and temperature-scaled function [8]: À E (7, 1) and T > 0,
exp (s*)
exp (J*
E(f)
max k)
E(f)=
max ke (E(
(5)
Ei= exp (fo)*
Ee=1 exp (fo/T)
energy-based function [23]: X E (0, +00) and T O.
F(f) T log Σ exp (T²/T).
Using E, A and f Fq. we have a classifier: (x) 1, if E(f(x)) 2 x: otherwise, 12) where 1 represents the IDD data and 2 represents the OOD data. Hence, binary classification hypothesis space Hb, which consists of all h22 is generated. We define H == thr, vT FG).
Learnability of OOD Detection in Different Hypothesis Spaces. Next, we present applications of theory regarding the above two practical and important hypothesis spaces Hę and Ha.d
Theorem 10. Suppose that Condition 2 holds and the hypothesis space H is FCNN-based or score- based, i.e. H. = Hg or H Hin Hb, where Hi is an ID hypothesis space, H. Hoo and H. = Hin nD is introduced below Eq. (4), here E is introduced in Eqs. (5) or (6). Then
There is sequence q (41,.., lg) such that OOD detection learnable in the separate space X H if and only if [X| < +oc.
Furthermore, (x < +00, then there exists a sequence q = (41..., 1g) such that for any sequence q' satisfying that q S q', OOD detection is learnable in Dx for H.
Theorem 10 states that 1) when the hypothesis space is FCNN- 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
*We consider the rectified linear unit (ReLU) function as the default activation function which is defined by a (xx) max(2, 0). V H. We will not repeatedly mention the definition of a in the rest of our paper.
8

---

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 theoretical support for the representative works [8, 23, 7]. Furthermore, Theorem 11 also offers theoretical supports for these works in the density- based space, when K 1.
Theorem 11. Suppose that each domain Dxy in IX is attainable, i.e., arg minggu (D(h) + 9 (the finite discrete domains satisfy this). Let K 1 and the hypothesis space H be score-based (H = +H=Hq where E is in Eqs. (5) or (6) or FCNN-bused (H = HQ)) If u(2) < +00, then the following four conditions are equivalent:
Learnability in 2xy for H 3 Condition 1 Realizability Assumption
Condition 3
Theorem 11 still holds if the function space Fq 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, based, what will happen if there exists an overlap between the II) and OOD distributions?
Theorem 12. Let K 1 and the hypothesis space H. be score-based (H. =H where É is in Eqs. (5) or (6)) or FCNN-based (H = Hg)) Given a prior-unknown space Φxy, if there exists a domain Dxy E 2xv, which has an overlap between ID and OOD distributions (see Definition 4), then OOD detection is not learnable the domain space 2X for H.
When K- = 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 BB (h) 0 and inf R2 (h) O. However, when K > 1, we can ensure inf H (h) > 0 if ID distribution Dx,yi 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.
7 Discussion
Understanding Far-OOD Detection. Many existing works [7, 39] study the far-OOD detection issue. Existing benchmarks include 1) MNIST [40] as ID dataset, and Texture [41], CIFAR-10 [42] or Place365 [43] as OOD datasets; and 2) CIFAR-10 [42] as ID dataset, and MNIST [40], or Fashion- MNIST [43] OOD datasets. In far-OOD case, 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 7 > 0, domain space 2XY is 7-far-OOD, if for any domain Dxy 2xX.
dist(supp xuppp>>x) > T.
Theorems 7, and 10 imply that under appropriate hypothesis space, far- detection is learnable. In Theorem 7, the condition |X < +oo is necessary for the separate space. However, one can prove that in the far-OOD case, when Hin is agnostic PAC Icarnable for ID distribution, the results in Theorem 7 still holds, if the condition | < too is replaced by weaker condition that X' is compact. In addition, it is notable that when 7 is agnostic PAC learnable for ID distribution and X is compact, the Kased OOD detection algorithm [44] is consistent in the r-rr--ODD case.
Understanding Near-OOD Detection. When the ID and OOD datasets have similar semantics or styles, OOD detection tasks become more challenging. [45, 46] consider this issue and name it near-OOD detection. Existing benchmarks include 1) MNIST [40] as ID dataset, and Pashion-MNIST [43] or Not-MNIST [47] as OOD datasets; and 2) 10 [42] as ID) dataset, and CIFAR-100 [48] as OOD dataset. From the thcoretical 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 fcasibility 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 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. 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 has shown that necessary to select a suitable hypothesis space satisfying the Realizability Assumption ensure the lcaraailityy of OOD

---

detection in the density-based based space. Generally, a Sarge-capacity model can be helpful to guarantee that the Realizability Assumption holds.
8 Related Work
We briefly review the related theoretical works below. See Appendix A for detailed related works.
OOD Detection Theory. [49] understands the OOD detection via goodness-of-fn 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 [49], [50] paves new avenue to designing provable OOD detection algorithms. Compared to [50, 49], 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 door to study OOD detection in theory.
Open-set Learning Theory. [51] and [29, propose the agnostic PAC learning bounds for open-set detection and open-set domain adaptation, respectively. Unfortunately, [29, 51, 52] 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, [24] proposes and investigates the almost agnostic PAC learnability for OSL. However, the assumptions used in [24] are very strong and unpractical.
Learning Theory for Classificatton with Reject Option. Many works [53, 54] also investigate the classification with reject option (CwRO) problem, which is similar to OOD detection in some cases. [55, 56, 57, 58, 59] 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 DD (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 the OOD risk.
Robust Statisties. In the field of robust statistics [60], 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 [61, 62, 63]. Existing works [64, 65, 66] in the field have identified and resolved the statistical limits of outlier robust statistics by constructing estimators and proving impossibility results. In the future, is a promising and interesting research direction study the robustness of OOD detection based robust statistics.
PQ Learning Theory. Under some conditions, PQ learning theory [67, 68) 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, [67, 68] aim to give the PAC estimation under Realizability Assumption [21]. 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.
9 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 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 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 provides 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 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 [64, 69].
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. 7FF would also like to thank Prof. Peter Bartlett and Dr. Tongliang Liu for productive discussions.
10

---

References
[1] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR, 2021.
[2] Gao Huang, Zhuang Liu, Laurens der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In CVPR, 2017.
[3] Yen-Chang Hsu, Yilin Shen. Hongxia Jin, and Zsolt Kira. Generalized ODIN: detecting out-of-disttibution image without learning from di-oo--distibutton data. In CVPR, 2020.
[4] Jingkang Yang, Kaiyang Zhou, Yixuan Li, and Ziwei Liu. Generalized out-of-distr detection: A survey. CoRR, 00ss2110.11134. 2021.
[5] Abhijit Bendale and Terrance E Boult. Towards open set deep networks. In CVPR, 2016.
[6] Jiefeng Chen, Yixuan Li, Xi Wu, Yingyu Liang, and Somesh Jha. Atom: Robustifying out-of- distribution detection using outlier mining. ECMI,, 2021.
[7] Dan Hendrycks and Kevin Gimpel. baseline for detecting misclassified and out-o--distribution examples in neural networks. In ICLR, 2017.
[8] Shiyu Liang, Yixuan Li, and R. Srikant. Enhancing the reliability of out-of-distribution image detection in neural networks. In ICLR, 2018
[9] Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. simple unified framework for detecting out-o--distribution samples and adversarial attacks. In NeurIPS, 2018.
[10] Bo Zong, Qi Song, Martin Rengiang Min, Wei Cheng, Cristian Lumezanu, Dae-ki Cho. and Haifeng Chen. Deep autoencoding gaussian mixture model for unsupervised anomaly detection. In ICLR, 2018.
[11] Stanislav Pidhorskyi, Ranya Almohsen, and Gianfranco Doretto. Generative probabílistic novelty detection with adversarial autoencoders. In NewrlPS, 2018.
[12] Eric T. Nalisnick, Akihiro Matsukawa, Yee Whye Teh, Dilan Görür, and Balaji Lakshmi- narayanan. Do deep generative models know what they don't ton't know? In ICLR, 2019.
[13] Dan Hendrycks, Mantas Mazeika, and Thomas G. Dietterich. Deep anomaly detection with outlier exposure. ICLR, 2019.
[14] Jie Ren, Peter Liu, Emily Fertig, Jasper Snoek, Ryan Poplin, Mark A. DePristo, Joshua Dillon, and Balaji Lakshminarayanan. Likelihood ratios for out-o--distribution detection. In NeurlPS, 2019.
[15] Ziqian Lin, Sreya Dutta Roy, and Yixuan Li. Mood: Multi-level out-of-distribution detection. In CVPR, 2021.
[16] Mohammadreza Salehi, Hossein Mirzaei, Dan Hendrycks, Yixuan Li, Mohammad Hossein Rohban, and Mohammad Sabokrou. A unified survey on anomaly, novelty, open-set, and out-of-distributio detection: Solutions and future challenges. arXiv preprint 10.005, 2021.
[17] Yiyou Sun, Chuan Guo, and Yixuan Li. React: Out-of-distribution detection with rectified activations. NeurlPS, 2021.
[18] Rui Huang, Andrew Geng, and Yixuan Li. On the Importance Gradients for Detecting Distributional Shifts in the Wild. In NeurlPS, 2021.
[19] Stanislav Fort, Jie Ren, and Balaji Lakshminarayanan. Exploring the Limits of Out-of- Distribution Detection. In NeurlPS, 2021.
[20] Yifei Ming, Hang Yin, and Yixuan Li. On the impact of spurious correlation for out-of- distribution detection. AAAI, 2022.
[21] Shai Shalev-Shwartz and Shai Ben-David, Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[22] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning.
MIT press, 2018
11

---

[23] Weitang Liu, Xiaoyun Wang, John D. Owens, and Yixuan Li. Energy-based cut-of-distribution detection. In NeurIPS, 2020.
[24] Zhen Fang, Jie Lu, Anjin Liu, Feng Liu, and Guangquan Zhang. Learning bounds for open-set learning. In ICML, 2021.
[25] Guangyao Chen, Peixi Peng, Xiangqian Wang, and Yonghong Tian. Adversarial reciprocal points learning for open set recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[26] Lukas Ruff, Nico Görnitz, Lucas Deecke, Shoaib Ahmed Siddiqui, Robert A. Vandermeulen, Alexander Binder, Emmanuel Müller, and Marius Kloft. Deep one-class classification. In ICML., 2018.
[27] Sachin Goyal, Aditi Raghunathan, Moksh Jain, Harsha Vardhan Simhadri, and Prateek Jain. DROCC: deep robust one-class classification. ICML, 2020.
[28] Lucas Deecke, Robert A. Vandermeulen, Lukas Ruff, Stephan Mandt, and Marius Kloft. Image anomaly detection with generative adversarial networks. In ECML, 2018.
[29] Z. Fang, Jie Lu, F. Liu, Junyu Xuan, and G. Zhang. Open set domain adaptation: Theoretical bound and algorithm. IEEÉ Transactions on Neural Networks and Learning Systems, 2020.
[30] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. J. Mach. Learn. Res., 11:2635-2670, 2010.
[31] Guangyao Chen, Limeng Qiao, Yemin Shi, Peixi Peng. Jia Li, Tiejun Huang, Shiliang Pu, and Yonghong Tian. Learning open set network with discriminative reciprocal points. ICCV, 2020.
[32] Jiefeng Chen, Yixuan Li, Xi Wu, Yingyu Liang, and Somesh Jha. Informative outlier matters: Robustifying distribbttti detection using outlier mining. ICML Workshop, 2020.
[33] Jiefeng Chen, Yixuan Li, Xi Wu, Yingyu Liang, and Somesh Jha. Robust out-of-distribution detection for neural networks. arXiv preprint arXiv:2003.09711, 2020.
[34] Wentao Bao, Qi Yu, and Yu Kong. Evidential deep learning for open action recognition. ICCV, 2021.
[35] Wentao Bao, Qi Yu, and Yu Kong. Opental: Towards open set temporal action localization. CVPR, 2022.
[36] Donald L. Cohn. Measure theory. Springer, 2013.
[37] Peter I.. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve- dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1-17, 2019.
(38] Marek Karpinski and Angus Macintyre. Polynomial bounds for VC dimension of sigmoidal and general pfaffian neural networks. J. Comput. Syst. Sci., 54(():169-176, 1997.
[39] Jingkang Yang, Kaiyang Zhou, and Ziwei Liu. Full-spectrum out-of-distribution detection. CoRR, 2022.
[40] Li Deng. The MNIST database of handwritten digit images for machine learning research [best of the web]. IEEE Signal Process. Mag., 2012.
[41] Gustaf Kylberg. Kylberg texture dataset v. 1.0. 2011.
[42] Alex Krizhevsky and Geoff Hinton. Convolutional deep belief networks on cifar-10. Technical report, Citeseer, 2009.
[43] Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: A 10 million image database for scene recognition. IEEE Trans. Puttern Anal. Mach. Intell., 2018.
[44] Yiyou Sun, Yifei Ming. Xiaojin Zhu, and Yixuan Li. Out-of-distribution detection with deep nearest neighbors. ICML, 2022.
[45] Jie Ren, Stanislav Fort, Jeremiah Liu, Abhijit Guha Roy, Shreyas Padhy, and Balaji Lakshmi- narayanan. A simple fix to mahalanobis distance for improving near-ood detection. CoRR, abs/2106.09022,, 2021.
[46] Stanislav Fort, Jie Ren, and Balaji Lakshminarayanan. Exploring the limits of out-o--distributtin detection. In NeurIPS, 2021.
12

---

[47] Yaroslav Bulatov. Notmnist dataset. Google (Books/OCR), Tech. Rep.[Online]. Available: http://yaroslavvb. blogspot. it/201 ht000///////mmmstaaaaaaaassss h 2011.
[48] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- 10 and cifar- 100 datasets. 2009.
[49] Lily H. Zhang, Mark Goldstein, and Rajesh Ranganath. Understanding failures in out-of-
distribution detection with deep generative models. In ICML, 2021.
[50] Peyman Morteza and Yixuan Li. Provable guarantees for understanding out-of-distributtin detection. AAAI, 2022.
[51] Si Liu, Risheck Garrepalli, Thomas G. Dietterich, Alan Fern, and Dan Hendrycks. Open category detection with PAC guarantees. In ICML, 2018.
[52] Yadan Luo, Zijian Wang. Zi Huang, and Mahsa Baktashmotlagh. Progressive graph learning for open-set domain adaptation. In ICML, 2020.
[53] C. K. Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on Informa- tion Theory, 1970.
[54] Vojtech Franc, Daniel Prúša, and V. Voracck. Optimal strategies for reject option classifiers. CoRR, abs/2101. 2021.
[55] Corinna Cortes, Giulia DeSalvo, and Mchryar Mohri. Learning with rejection. In ALT, 2016.
[56] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Boosting with abstention. In NeurIPS, 2016.
[57] Chenri Ni, Nontawat Charoenphakdee, Junya Honda, and Masashi Sugiyama. On the calibration of multiclass classification with rejection. In NeurlPS, 2019.
[58] Nontawat Charoenphakdee, Zhenghang Cui, Yivan Zhang, and Masashi Sugiyama. Classifica- tion with rejection based cost-sensitive classification. In ICML, 2021.
[59] Peter L. Bartlett and Marten H. Wegkamp. Classification with a reject option using a hinge loss. Journal of Machine Learning Research, 2008
[60] Peter J Rousseeuw, Frank R Hampel, Elvezio M Ronchetti, and Werner A Stahel. Robust stutistics: the approuch bused on influence functions. John Wiley & Sons, 2011.
[61]
Elvezio M Ronchetti and Peter Huber. Robust statistics. John Wiley & Sons, 2009.
[62] Ilias Diakonikolas, Daniel M. Kane, and Ankit Pensia. Outlier robust mean estimation with subgaussian rates via stability. In NeurIPS, 2020.
[63] Ilias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Eric Price, and Alistair Stewart. Outlier- robust high-dimensional sparse estimation via iterative filtering. In NewrIPS, 2019.
[64] Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, and Yuxin Sun. Outlier-robust learning of ising models under dobrushin's condition. In COLT, 2021.
[65] Yu Cheng, Ilas Diakonikolas, Daniel M Kane, Rong Ge, Shivam Gupta, and Mahdi Soltanolkotabi. Outlier-robust sparse estimation via non-convex optimization. In NeurIPS, 2021.
[66] Ilias Diakonikolas, Daniel M Kane, Jasper CH Lee, and Ankit Pensia. Outlier-robust sparse mean estimation for heavy-tailed distributions. In NeurIPS, 2022.
[67] Shafi Goldwasser, Adam Tauman Kalai, Yael Kalai, and Omar Montasser. Beyond perturbations: Learning guarantees with arbitrary adversarial test examples. In NeurIPS, 2020.
[68] Adam Tauman Kalai and Varun Kanade. Efficient learning with arbitrary covariate shift. In
ALT, Proceedings of Machine Learning Research, 2021.
[69] Ilias Diakonikolas and Daniel M. Kane. Recent advances in algorithmic high-dimensional robust statistics. A shorter version appears as an Invited Book Chapter in Beyond the Worst-Case Analysis of Algorithms, 2020.
[70] Akshay Raj Dhamija, Manuel Günther, and Terrance E. Boult. Reducing network agnostophobia. In NeurIPS, pages 9175-9186. 2018
[71] Haoran Wang, Weitang I. Liu, Alex Bocchieri, and Yixuan Li. Can multi-label classification networks know what they don't 't know? In NeurlPS, 2021.
[72] Diederik Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1x1 convolu- tions. In NewrIPS, 2018
13

---

[73] Zhisheng Xiao, Qing Yan, and Yali Amit. Likelihood regret: An out off.iiitiibutiionn detection score for variational entoeeen In NeurIPS, 2020.
[74] Alireza Zaeemzadeh, Niccoló Bisagno, Zeno Sambugaro, Nicola Conci, Nazanin Rahnavard, and Mubarak Shah. nut-of-distributiio detection using union of 1-dimensional subspaces. In CVPR, 2021.
[75] Joost Van Amersfoort, Lewis Smith, Yee Whye Teh, and Yarin Gal. Uncertainty estimation using a single deep deterministic neural network. In ICML, 2020.
[76] Sachin Vernekar, Ashish Gaurav, Vahdat Abdelzad, Taylor Denouden, Rick Salay, and Krzysztof Czarnecki. Out-of-distribution detection in classifiers via generation. NewrIPS Workshop, 2019.
[77] Ryuichi Kiryo, Gang Niu, Marthinus Christoffel du Plessis, and Masashi Sugiyama. Positive- unlabeled learning with non-negative risk estimator. In NeurlPS, 2017.
[78] Takashi Ishida, Gang Niu, and Masashi Sugiyama. Binary classification from positive- confidence data. In NeurIPS, 2018.
[79] Shuo Chen, Gang Niu, Chen Gong, Jun Li, Jian Yang, and Masashi Sugiyama. Large-margin contrastive learning with distance polarization regularizer. ICML, 2021.
[80] Jiahua Dong, Yang Cong, Gan Sun, Bineng Zhong, and Xiaowei Xu. What can be transferred: Unsupervised domain adaptation for endoscopic lesions segmentation. In CVPR, 2020.
[81] Zhen Fang, Jie Lu, Feng Liu, and Guangquan Zhang. Semi-supervised heterogeneous domain adaptation: Theory and algorithms. IEEE Trunsactions on Pattern Analysis and Machine Intelligence, 2022.
[82] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
[83] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander J. Smola. A kernel two-sample test. Journal of Machine Learning Research, 2012.
[84] Itay Safran and Ohad Shamir. Depth-width tradcoffs in approximating natural functions with neural networks. In ICML, 2017.
[85] Allan Pinkus. Approximation theory of the mlp model in neural networks. Acta numerica, 143-195, 1999.
[86] Peter L Bartlett and Wolfgang Maass. Vapnik-chervonente dimension of neural nets. The handbook of brain theory and neural networks, 2003.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Appendix B
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Appendix B
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
14

---

(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasig new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "U1IOGByRwM", "reviewer": "Reviewer_FqYr", "summary": "This paper provides theory on PAC-learnability of out-of-distribution (OOD) detection.\nOOD detection is classification task but test data may come from unknown classes.\nIf test data come from classes known during training, we want to classify them into those classes, but otherwise, we need to detect they belong to unknown classes.\nThe authors provide a series of theorems about conditions for OOD detection in several interesting setups.\nTheir results imply that we should not hope for finding an OOD detection algorithm that works in general cases, but we can still design algorithms for special cases.", "questions": "- l.118, \"they are equivalent by Markov's inequality\": I can see that Eq. (2) implies the standard form of PAC-learnability by Markov's inequality, but I cannot see how we can confirm the converse. Could the authors provide a proof or a reference for that?\n- ll.260-261, \"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\": I am not sure how to relate the fact to finite-ID-distribution space. Does \"finite ID datasets\" here mean datasets of finite samples or a finite variety of datasets? If it's for the latter sense, do the authors assume $\\vert \\mathcal{X} \\vert < \\infty$ here?\n- Could the authors define the realizability assumption explicitly?\n- The conditions of Theorem 3, $\\inf_{h\\in\\mathcal{H}} R_D^{\\mathrm{in}}(h) = 0$ and $\\inf_{h\\in\\mathcal{H}} R_D^{\\mathrm{out}}(h) = 0$, look similar to the realizability assumption and the compatibility condition. However, the conditions of Theorem 3 seem to be prohibiting the learnability in Theorem 3 while the realizability and the compatibility conditions are making the learning possible in Theorem 8 and Theorem 9. Should we consider such conditions as good ones or bad ones?\n- The paper refer to distributions as \"domains.\" Is this a common way of saying it in the literature? It is a little confusing to me, and I do not see good motivation for the choice of the word.", "limitations": "The theory only handles a few special combinations of distributions and hypothesis spaces although I do not consider this as a very strong limitation because they cover many common practical situations.\n", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n- The paper provides rigorous theory on an important machine learning task.\n- The paper is excellently-written and easy to follow despite its technical content although all the proofs are in the supplemental material.\n- The scenarios that the authors consider are not too technical but highly relevant to practical OOD detection methods. Hence, it gives useful insights for practitioners as well.\n\n# Weaknesses\n- Most results are negative ones showing impossibility of OOD detection in general cases, and the paper does not provide concrete algorithms.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TWaPSS0iHc", "reviewer": "Reviewer_iXvy", "summary": "Recently, reliable AI plays important role in designing an intelligent machine learning system. How to let AI system tell “do not know” is critical for reliable AI systems, which is the focus of this paper. In this paper, the authors consider a practical scenario where out-of-distribution data (the system should not know) is unseen during the training process. In this scenario, the authors want to investigate if the OOD detection is learnable. \n\nThe theoretical part is easy to follow. I find that the theoretical contributions are completed and interesting. At first, this paper shows that OOD detection is not learnable in the most general case, which does make sense due to the unavailability of OOD data. Then, this paper points out a necessary condition (sometimes as a necessary and sufficient condition) of the learnability of OOD detection, which directly induces a lot of necessary and sufficient conditions of learnability of OOD detection. In my opinion, this is a significant contribution to the field. Finding necessary and sufficient conditions is always a core and the most important part when studying a problem.\n\nFrom the practical part, several theorems are considered using networks or finite in-distribution domains, making the whole paper also fit the taste of practitioners. In many practical scenarios, we cannot expect OOD data is the ones we have already seen, which is exactly the problem this paper studies. Besides, the theorem regarding finite ID distributions is also practical. If I understand correctly, in this practical scenario, this paper gives a better result, which is very interesting to me and significant to the field (we often only have finite ID distributions in practice).\n", "questions": "Please answer/revise your paper according to the questions proposed in weaknesses 1,2,3,4,7,8.", "limitations": "It is a pure theoretical paper. So I think there is no negative social impacts.\n\n", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n1. This paper is the first to characterize the learnability of OOD detection, which makes a significant contribution to the field. There are many OOD detection papers targeting the problem this paper considers. The problem is very difficult yet very important in practice. Previously, no theoretical works are proposed for this problem. In this paper, a completed theory is proposed for this problem, including when OOD detection will fail and when OOD detection will succeed. A lot of necessary and sufficient conditions of learnability of OOD detection are exciting to this field.\n\n2. For practitioners, this paper relieves some big concerns regarding existing OOD detection methods. Before this work, one could intuitively think that OOD detection is not learnable (which is true in the most general case, yet our common datasets are not such general). However, this paper gives a theoretical boundary between learnability and unlearnability of OOD detection by proving some necessary and sufficient conditions. Thus, we can know, on what kind of datasets, OOD detection is learnable.\nThis contribution is significant and meaningful. \n\n3. Fig. 1 is very helpful in understanding the key necessary condition of OOD detection, which seems that it can motivate a bunch of papers in this research direction.\n\n4. I can see that there are three research topics regarding that “let AI say don’t know”: 1) classification with reject option; 2) PQ learning; and 3) OOD detection. The first two have already had some theories but the last one does not have. This paper fills up this gap, making OOD detection method (which might be more practical than the other two) possible in theory.\n\n5. Although the proofs of this paper are not easy to follow, the logic and organizations of proofs are clear. I have read most proofs and have not found unrecoverable errors for important results. The proofs are soundness.\n\nCons:\n\n1. I have read some papers regarding PQ learning and feel that PQ learning is totally different from OOD detection. PQ learning focuses on scenarios where OOD data are somehow available, yet OOD detection focuses on the opposite scenarios. However, it is better to demonstrate their difference deeply. Does PQ learning have limitations when meeting different OOD data in the future? I am interested to see some discussions regarding this part.\n\n2. Similar to PQ learning, classification with reject option could be deeply compared to OOD detection instead of just comparing both using plain words. I know they are very different and OOD detection theory is more difficult. But giving more detailed comparation is better for this paper.\n\n3. I have some questions regarding Figure 1, which I hope that the authors can confirm with me. In my opinion, the solid line is the ground-truth line. Do we expect that the estimated lines (dash lines) get closer to the solid line? If so, when overlap exists, why is the solid line not straight? Can you bring me to the specific part regarding this? It seems that the solid line will be straight if there are no overlaps, which makes OOD detection learnable. Is that correct?\n\n4. More explanation, like Figure 1, could be added for understanding the theorems better. Brief proofs might be also useful.\n\n5. In line 26, there are too many separate citations. In my opinion, it is not necessary.\n\n6. Line 148 should not be a new paragraph.\n\n7. The density-based space is very important and interesting. Especially, the theorem 11 is one of the spotlights. Can you give more explanations or applications regarding density-based space (theorems 9 and 11)? \n\n8. The mathematic expression in Definition 1 about PAC learnability is different with the normal expression of PAC learnability. Although line 118 has told us that they are equivalent and I also realize that they are equivalent by paper [21,30] (exercise 4.5 in [21] can prove it?) , the paper will be improved and more clear if a brief proof for the equivalent descriptions is given in the final version.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4Ep1FKIoPb_", "reviewer": "Reviewer_KK6q", "summary": "This paper explores the theoretical foundation of learnability of out-of-distribution detection. Based on the PAC learning theory, the paper proved several impossibility theorems for the learnability of OOD detection under some scenarios, and finds some conditions that OOD detection is PAC-learnable. Also, the paper demonstrate the theory in real practice using FCNN and OOD scores as examples. Recently there are loads of papers proposed empirical methods for OOD detection, but the theory is rarely explored.This paper is the first to investigate the theory of OOD detection so thoroughly, which is meaningful to this field.", "questions": "- What is the \"+\" means in $D_X := (1-\\pi^{out}) D_{X_1} + \\pi^{out} D_{X_O}$ ? (line 82) ", "limitations": "Yes.", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is clear and well-written. And the proofs are generally correct.\n- This paper is one of the few theoretical works focusing on OOD detection, which plays a significant role in this field.\n- The theory is intuitive and have some practical impacts. It can somewhat guide the design of OOD detection algorithms.\n\nWeakness:\n- Some notations and expressions can be refined in Section 2. For example, $S$ or $D_{XY}^n $ in eq.2 can be explained (minor). \n- Some typos. In section 2 Definition 1. \"if there exist an algorithm\" -> \"if there exists an algorithm\".\n- Some experiments can be added to show the correctness of the theorems.\n- The practical impacts may not be large enough. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-RvrWLeYR4Y", "reviewer": "Reviewer_KYDH", "summary": "The out-of-distribution detection problem is defined as follows: after training on an ID joint distribution $D_{X_{ I}Y_{ I}}$ with random variables from $\\mathcal{X}$ and labels in $\\mathcal{Y}$, we need to learn a classifier which can detect a test sample as OOD if the sample is drawn from outside of $D_{X_{ I}Y_{ I}}$, while predicting the correct label if the test sample is drawn from ID distribution.\n\nThis paper mainly answers the agnostic PAC learnability of out-of-distribution detection in different scenarios, which is known as an open problem in out-of-distribution learning theory. \n\nThis paper firstly defines the basic concepts of agnostic PAC learnability of OOD detection, which are natural extensions of agnostic PAC learnability of supervised learning. Then, considering the imbalance issue of OOD detection, the author proposes the prior-unknown spaces and indicates that researchers should focus on agnostic PAC learnability of OOD detection in the prior-unknown spaces.\n\nBy discovering a necessary condition (Condition 1), the author shows that the condition cannot hold in the total space and separate space. Based on this observation, the paper proves that in most general setting (total space and separate space), OOD detection is not agnostic PAC learnable. \n\nNext, the author proves the necessary and sufficient conditions to show that the separate space can be learnable if and only if the hypothesis space contains almost all classifiers, while the paper proves that in the finite-ID-distribution space, Condition 3 is the necessary and sufficient condition for the learnability of OOD detection. The paper also proves that in the realizability assumption case, OOD detection is learnable in density-based space.\n\nLastly, the author considers OOD detection in some practical hypothesis space—FCNN-based and score-based. The paper shows that in the separate space, OOD is learnable in FCNN-based spaces or score-based spaces iff the feature space is finite. In Theorem 11, the paper shows that Condition 1, condition 3 and realizability assumption and learnability are equivalent. In Theorem 12, the author also reveals that overlap will lead to the failure of OOD detection.\n\nThis paper is important to understand when and how OOD can work in real applications, as this also gives insight and guidance to OOD detection algorithm designing.\n\n", "questions": "See the weakness 1,2,3,4.", "limitations": "The paper focuses on theory for OOD detection and gives the first theoretical support to understand when OOD detection can work. There is no any potential negative social impact.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.\tThe issue is definitely relevant to the NeurIPS as well as ICML, ALT and COLT. When OOD detection can be learnable is an open issue in OOD learning. Due to missing necessary information from the OOD data, the learnability of OOD detection is very difficult. Despite plenty of applied work, there is still few theory to be established for this issue. To address this issue, it requires the author to dig and discovery unknown necessary conditions from scratch. This paper does make an effort to address this problem and make great progress.  \n2.\tThis paper is sound. I am interested in this topic, but the paper is long. So I spend several days to check the proofs carefully. All of the results in this paper are supported by proofs.  From what I have checked, all proofs are correct.\n3.\tThe paper answers negatively and positively the question of agnostic PAC learnability of OOD, and introduces sufficient assumptions to recover it (such as assumption 1). These assumptions are practical and mild, and can be satisfied by many practical cases, for example, FCNNs, CNNs and kernel space. Therefore, the theory can be tightly connected with practical applications.\n4.\tPlenty applied work has been proposed to address this OOD, but theoretical works discussing when OOD detection work is lacking. The paper theoretical shows when OOD can work in practical cases. I think the contribution are significantly important and this work can give a good guidance for the development of OOD detection. This paper has the potential to achieve a long term impact to OOD learning field.\n5.\tThe paper is written well enough to understand.\n\n\nWeaknesses:\n\n1.\tThe appendix is long and the proofs are complicated. Although I have check almost all important proofs and believe they are correct, I still spend three days to check them. It is better for the author to provide proof sketch and intuitions for important theorems. \n2.\tIt seems that the description of Theorem 4 in main text is slightly different from the description of Theorem 4 in appendix. I have checked it and found that the description Theorem 4 in appendix is more rigorous. Although you have explained why they are different (because of the space limitation) in appendix G.2, I still suggest that the author should use the description of Theorem 4 in appendix to replace Theorem 4 in main text, because the description in appendix is correct. \n3.\tTypos/grammar:\n1) In line 305, $K$ should be $\\lambda$.\n2) In line 340, $D_{XY|Y}^{ in}$ should be $D_{X_{I}Y_{I}}$.\n3) In line 171, $D_{X_{I}}$ should be $D_{X_{I}Y_{I}}$?\n4.  After checking your proof, I think Condition 2 can be removed from Theorems 7 and 10. Although Condition 2 is weak and meaningful, I still think it is better to remove Condition 2. The idea about how to remove Condition 2 can be motivate from the proof of Theorem 9 (the second part).\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept