# On the Learnability of Out-of-distribution Detection

Zhen Fang<EMAIL_ADDRESS>
Australian Artificial Intelligence Institute
University of Technology Sydney
61 Broadway, Ultimo NSW 2007, Australia Yixuan Li<EMAIL_ADDRESS>
Department of Computer Sciences
The University of Wisconsin Madison
1210 W Dayton St, Madison, WI 53706, USA Feng Liu ${}^{\textrm{{\char
0\relax}}}$<EMAIL_ADDRESS>
School of Computing and Information Systems
The University of Melbourne
700 Swanston Street, Carlton VIC 3053, Australia Bo Han
<EMAIL_ADDRESS>
Department of Computer Science
Hong Kong Baptist University
Kowloon Tong, Hong Kong SAR Jie Lu ${}^{\textrm{{\char 0\relax}}}$
<EMAIL_ADDRESS>
Australian Artificial Intelligence Institute
University of Technology Sydney
61 Broadway, Ultimo NSW 2007, Australia

###### 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, and corresponding learning theory is still an _open
problem_. To study the generalization of OOD detection, this paper
investigates the _probably approximately correct_ (PAC) learning theory of OOD
detection that fits the commonly used evaluation metrics in the literature.
First, we find a necessary condition for the learnability of OOD detection.
Then, using this condition, we prove several impossibility theorems for the
learnability of OOD detection under some scenarios. Although the impossibility
theorems are frustrating, we find that some conditions of these impossibility
theorems may not hold in some practical scenarios. Based on this observation,
we next give several necessary and sufficient conditions to characterize the
learnability of OOD detection in some practical scenarios. Lastly, we offer
theoretical support for representative OOD detection works based on our OOD
theory.

Accepted by JMLR in 7th of April, 2024

Keywords: out-of-distribution detection, weakly supervised learning,
learnability

##  1 Introduction

The success of supervised learning is established on an in-distribution (ID)
assumption that training and test data share the same distribution
(Dosovitskiy et al., 2021; Huang et al., 2017; Hsu et al., 2020; Yang et al.,
2021). However, in many real-world scenarios, the distribution of test data
violates the assumption and, instead, contains _out-of-distribution_ (OOD)
data whose labels have not been seen during the training process (Bendale and
Boult, 2016; Chen et al., 2021a). To mitigate the risk brought by OOD data, a
more practical learning scenario is considered in the machine learning field:
OOD detection, which determines whether an input is ID/OOD, while classifying
the ID data into respective classes.

OOD detection can significantly increase the reliability of machine learning
models when deploying them in the real world. Many seminar algorithms have
been developed to empirically address the OOD detection problem (Hendrycks and
Gimpel, 2017; Liang et al., 2018; Lee et al., 2018; Zong et al., 2018;
Pidhorskyi et al., 2018; Nalisnick et al., 2019; Hendrycks et al., 2019; Ren
et al., 2019; Lin et al., 2021; Salehi et al., 2021; Sun et al., 2021). A
common solution paradigm to OOD detection is to propose a new learning
objective or/and a score function to identify if one upcoming data point is
OOD data. When evaluating algorithms under this solution paradigm, both
threshold-dependent metrics (e.g., risk) and threshold-independent metrics
(e.g., AUC) will be used to see to what extent the algorithms can successfully
identify OOD data. 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, a theoretical framework is proposed to understand the
learnability of OOD detection problem in view of threshold-dependent metrics
and threshold-independent metrics111This paper is an extended version of our
previous conference paper (Fang et al., 2022a). In Section 7, we discuss the
main difference between this paper and Fang et al. (2022a).. We investigate
the probably approximately correct (PAC) learning theory of OOD detection when
the evaluation metrics are risk and AUC, 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. Because OOD data can be diverse in many real-world scenarios, we
want to study whether there exists an algorithm that can be used to detect
data from various OOD distributions instead of merely data from some specified
OOD distributions. Such is the significance of studying the learning theory
for OOD detection (Yang et al., 2021). 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 under two common metrics: risk and
AUC?

To answer the above research question and investigate the learning theory, we
mainly focus on two basic spaces: domain space and function space. The domain
space is a space consisting of some distributions, and the function space is a
space consisting of some classifiers or ranking functions. Existing agnostic
PAC theories in supervised learning (Shalev-Shwartz and Ben-David, 2014; Mohri
et al., 2018) are distribution-free, i.e., the domain space consists of all
domains. Yet, in Theorem 4 and Theorem 6, we show that the learning theory of
OOD detection is not distribution-free. Furthermore, we find that OOD
detection is learnable only if the domain space and the function space satisfy
some special conditions, e.g., Conditions 1, 2, and 4. 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 under risk and AUC metrics. From these essential
conditions, we can know when OOD detection can be successful in practical
scenarios. We restate our question and goal in the following:

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

#### Main Results.

We start to study the learnability of OOD detection in the largest space—the
total space, and give two necessary conditions for the learnability of OOD
detection under risk and AUC (Condition 1 for risk and Condition 2 for AUC).
However, we find that the overlap between ID and OOD data may result in that
both necessary conditions do not hold. Therefore, we give two impossibility
theorems to demonstrate that OOD detection fails in the total space (Theorem 4
under risk and Theorem 6 under AUC). Then, we investigate OOD detection in a
separate space, where the ID and OOD data do not overlap. Unfortunately, there
still exists impossibility theorems (Theorem 5 under risk and Theorem 7 under
AUC), meaning that we cannot expect OOD detection is learnable under risk and
AUC in the separate space under some conditions of the developed theorems.

It is frustrating to find the impossibility theorems regarding OOD detection
in a separate space, but we find that some conditions of these impossibility
theorems may not hold in several practical scenarios. Stemming from this
observation, we give several _necessary and sufficient_ conditions to
characterize the learnability of OOD detection under risk and AUC in the
separate space (Theorems 8 and 14 under risk, and Theorems 10 and 15 under
AUC). Especially, when our function space is based on _fully-connected neural
network_ (FCNN), OOD detection is learnable under risk and AUC in the separate
space if and only if the feature space is finite. Then, we focus on other more
practical domain spaces, e.g., the finite-ID-distribution space and the
density-based space and investigate the learnability of OOD detection in both
spaces. Theorem 11 shows a necessary and sufficient condition of learnability
of OOD detection under risk. Theorems 12 and 13 show two sufficient conditions
for the learnability of OOD detection under risk and AUC, respectively. It
should be noted that when studying learnability of OOD detection in the
finite-ID-distribution space, we discover a compatibility condition (Condition
4) that is a necessary and sufficient condition of learnability of OOD
detection under risk for this space. Then, we explore 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 16).

#### Implications and Impacts of Theory.

Our study is not of purely theoretical interest; it has also practical
impacts. (i) From the perspective of domain space, we consider the finite-ID-
distribution space that fits the common scenarios in the real world: we
normally only have finite ID datasets. In this case, Theorem 11 gives a
necessary and sufficient condition to the success of OOD detection under risk.
More importantly, 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. (ii) From the perspective of function space,
we investigate the learnability of OOD detection under risk and AUC for
commonly used FCNN-based function spaces. Our theory provides theoretical
support (Theorems 14 and 16 under risk, and Theorems 15 and 17 under AUC) for
several representative OOD detection works (Hendrycks and Gimpel, 2017; Liang
et al., 2018; Liu et al., 2020). (iii) From the perspective of evaluation
metrics, our paper studies the learnability of OOD detection under risk and
the learnability of OOD detection under AUC, which covers the major evaluation
metrics used in OOD detection evaluation and provides theoretical guidance
when users have different requirement in evaluating OOD detection performance.
Based on all of our theoretical results, they suggest we should not expect a
universally working OOD detection algorithm. It is necessary to design
different algorithms in different scenarios.

##  2 Learning Setups

We begin by introducing the necessary concepts and notations for our
theoretical framework. Given a feature space
$\mathcal{X}\subset\mathbb{R}^{d}$ and a label space
$\mathcal{Y}:=\\{1,\ldots,K\\}$, we have an ID joint distribution $D_{X_{\rm
I}Y_{\rm I}}$ over $\mathcal{X}\times\mathcal{Y}$, where $X_{\rm
I}\in\mathcal{X}$ and $Y_{\rm I}\in\mathcal{Y}$ are random variables. We also
have an OOD joint distribution $D_{X_{\rm O}Y_{\rm O}}$, where $X_{\rm O}$ is
a random variable from $\mathcal{X}$, but $Y_{\rm O}$ is a random variable
whose outputs do not belong to $\mathcal{Y}$. During testing, we encounter a
mixture of ID and OOD joint distributions: $D_{XY}=(1-\pi^{\rm out})D_{X_{\rm
I}Y_{\rm I}}+\pi^{\rm out}D_{X_{\rm O}Y_{\rm O}}$, and we can only observe the
marginal distribution $D_{X}=(1-\pi^{\rm out})D_{X_{\rm I}}+\pi^{\rm
out}D_{X_{\rm O}}$, where the constant $\pi^{\rm out}\in[0,1)$ represents an
unknown class-prior probability. Next, we provide the formal definition of the
OOD detection problem and key concepts used in this paper.

###  2.1 Problem Setting and Concepts

######  Problem 1 (OOD Detection (Yang et al., 2021))

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}$:

  * •

if $\mathbf{x}$ is an observation from $D_{X_{\rm I}}$, $f$ can classify
$\mathbf{x}$ into correct ID classes;

  * •

if $\mathbf{x}$ is an observation from $D_{X_{\rm O}}$, $f$ can detect
$\mathbf{x}$ as OOD data.

According to Yang et al. (2021), when $K=1$, OOD detection reduces to one-
class novelty detection or semantic anomaly detection (Ruff et al., 2018;
Goyal et al., 2020; Deecke et al., 2018). Next, we introduce some basic and
important concepts and notations.

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$
(Fang et al., 2021, 2020). 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.

Hypothesis Spaces and Scoring Function Spaces. A hypothesis space
$\mathcal{H}$ is a subset of function space, i.e.,
$\mathcal{H}\subset\\{{h}:\mathcal{X}\rightarrow\mathcal{Y}\cup\\{K+1\\}\\}.$
We set $\mathcal{H}^{\rm
in}\subset\\{{h}:\mathcal{X}\rightarrow\mathcal{Y}\\}$ to the ID hypothesis
space. We also define $\mathcal{H}^{\rm
b}\subset\\{{h}:\mathcal{X}\rightarrow\\{1,2\\}\\}$ as the hypothesis space
for binary classification, where $1$ 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.,
$\mathcal{F}_{l}\subset\\{\mathbf{f}:\mathcal{X}\rightarrow\mathbb{R}^{l}\\}$,
where $l$ is the output’s dimension of the vector-valued function
$\mathbf{f}$. The function $\mathbf{f}$ is called the scoring function.

Ranking Function Spaces. Most representative OOD detection algorithms (Liu et
al., 2020) output a ranking function from a given ranking function space
$\mathcal{R}\subset\mathcal{R}_{\rm
all}=\\{r:\mathcal{X}\rightarrow\mathbb{R}\\}$. If the ranking function
$r(\mathbf{x})$ has a higher value, then $\mathbf{x}$ is from $D_{X_{\rm I}}$
with a higher probability. A perfect ranking function $r^{*}$ fulfills the
condition $r^{*}(\mathbf{x})>r^{*}(\mathbf{x}^{\prime})$ for all $\mathbf{x}$
from $D_{X_{\rm I}}$ and all $\mathbf{x}^{\prime}$ from $D_{X_{\rm O}}$,
indicating that rankings of ID data are always higher than rankings of OOD
data. The general strategy to construct the ranking function space
$\mathcal{R}$ is to design a scoring function
$E:\mathbb{R}^{l}\rightarrow\mathbb{R}$ and integrate it with the scoring
function space $\mathcal{F}_{l}$, i.e., $\mathcal{R}=E\circ\mathcal{F}_{l}$.

Loss, Risks and AUC Metric. Let $\mathcal{Y}_{\rm
all}=\mathcal{Y}\cup\\{K+1\\}$. Given a loss function $\ell:\mathcal{Y}_{\rm
all}\times\mathcal{Y}_{\rm all}\rightarrow\mathbb{R}_{\geq 0}$ satisfying that
$\ell(y_{1},y_{2})=0$ if and only if $y_{1}=y_{2}$, and any
${h}\in\mathcal{H}$, then the risk with respect to ${D}_{XY}$ is

$\begin{split}&R_{D}({h}):=\mathbb{E}_{(\mathbf{x},y)\sim
D_{XY}}\ell({h}(\mathbf{x}),{y}).\end{split}$ (1)

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

$\begin{split}&R^{\rm in}_{D}({h}):=\mathbb{E}_{(\mathbf{x},y)\sim D_{X_{\rm
I}Y_{\rm I}}}\ell({h}(\mathbf{x}),{y}),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ R^{\rm
out}_{D}({h}):=\mathbb{E}_{\mathbf{x}\sim D_{X_{\rm
O}}}\ell({h}(\mathbf{x}),K+1).\end{split}$

Except for using risk to evaluate the OOD detection performance, AUC is also a
promising metric to see if a ranking function $r$ can separate the ID and OOD
data:

${\rm AUC}(r;D_{XY})=\mathbb{E}_{\mathbf{x}\sim D_{X_{\rm
I}}}\mathbb{E}_{\mathbf{x}^{\prime}\sim D_{X_{\rm
O}}}\big{[}\mathbf{1}_{r(\mathbf{x})>r(\mathbf{x}^{\prime})}+\frac{1}{2}\mathbf{1}_{r(\mathbf{x})=r(\mathbf{x}^{\prime})}\big{]}.$
(2)

Note that since value of ${\rm AUC}$ only denpends on the marginal
distributions $D_{X_{\rm I}}$ and $D_{X_{\rm O}}$, therefore, it is also
convientent for us to rewrite ${\rm AUC}(r;D_{XY})$ as ${\rm AUC}(r;D_{X_{\rm
I}},D_{X_{\rm O}}).$

###  2.2 Learnability under Risk

Based on risk defined in Eq. (1), OOD detection aims 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 under
risk. Formally, we have:

######  Definition 1 (Learnability of OOD Detection under Risk)

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}$ under
risk, if there exists an algorithm
$\mathbf{A}:\cup_{n=1}^{+\infty}(\mathcal{X}\times\mathcal{Y})^{n}\rightarrow\mathcal{H}$222Similar
to Shalev-Shwartz et al. (2010), in this paper, we regard an algorithm as a
mapping from $\cup_{n=1}^{+\infty}(\mathcal{X}\times\mathcal{Y})^{n}$ to
$\mathcal{H}$ or $\mathcal{R}$. 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}$,

$\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}\big{[}R_{D}(\mathbf{A}(S))-\inf_{h\in\mathcal{H}}R_{D}(h)\big{]}\leq\epsilon_{\rm
cons}(n),$ (3)

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

Definition 1 is a natural extension of agnostic PAC learnability of supervised
learning (Shalev-Shwartz et al., 2010). If for any
$D_{XY}\in\mathscr{D}_{XY}$, $\pi^{\rm out}=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 Shalev-Shwartz and Ben-David (2014), one can prove that they are equivalent
if $\ell$ is bounded, see Appendix A.3.

Since OOD data are unavailable, it is impossible to obtain any 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 mitigate this challenge, we revise Eq. (3) as follows:

$\begin{split}&\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}\big{[}R_{D}^{\alpha}(\mathbf{A}(S))-\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)\big{]}\leq\epsilon_{\rm
cons}(n),\leavevmode\nobreak\ \forall\alpha\in[0,1].\end{split}$ (4)

If an algorithm $\mathbf{A}$ satisfies Eq. (4), 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 under risk as
follows:

######  Definition 2 (Strong Learnability of OOD Detection under Risk)

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}$,

$\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}\big{[}R_{D}^{\alpha}(\mathbf{A}(S))-\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)\big{]}\leq\epsilon_{\rm
cons}(n),\leavevmode\nobreak\ \forall\alpha\in[0,1].$

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

###  2.3 Learnability under AUC

Based on AUC defined in Eq. (2), OOD detection aims to select a ranking
function $r\in\mathcal{R}$ with approximately maximal AUC, 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 under AUC.
Formally, we have:

######  Definition 3 (Learnability of OOD Detection under AUC)

Given a domain space $\mathscr{D}_{XY}$, a ranking function space
$\mathcal{R}\subset\\{r:\mathcal{X}\rightarrow\mathbb{R}\\}$, we say OOD
detection is learnable in $\mathscr{D}_{XY}$ for $\mathcal{R}$ under AUC, if
there exists an algorithm
$\mathbf{A}:\cup_{n=1}^{+\infty}(\mathcal{X}\times\mathcal{Y})^{n}\rightarrow\mathcal{R}$
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}$,

$\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}\big{[}\sup_{r\in\mathcal{R}}{\rm AUC}(r;D_{XY})-{\rm
AUC}(\mathbf{A}(S);D_{XY})\big{]}\leq\epsilon_{\rm cons}(n).$ (5)

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

Definition 3 is another version of Definition 1. Here, we use AUC instead of
risk to evaluate the performance of the OOD detection. Note that the
learnability of OOD detection under AUC is not influenced by the $\pi_{\rm
out}$, as AUC is directly calculated by using $D_{X_{\rm I}}$ and $D_{X_{\rm
O}}$.

###  2.4 Goal of Our 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
(Liang et al., 2018; Ren et al., 2019; Fang et al., 2021), it is obvious that
the learnability of OOD detection is not distribution-free (i.e., Theorem 4
and Theorem 6). 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}$ (or the ranking
function space $\mathcal{R}$). That is, OOD detection is learnable only when
the domain space $\mathscr{D}_{XY}$ and the hypothesis space $\mathcal{H}$ (or
the ranking function space $\mathcal{R}$) satisfy some special conditions,
e.g., Conditions 1, 4 (under risk), Conditions 2 (under AUC). We present our
goal as follows:
Goal: given a hypothesis space $\mathcal{H}$ $($or a ranking function space
$\mathcal{R})$, 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.

##  3 Learning in Priori-unknown Spaces

We first investigate a special space, called prior-unknown space and prove
that if OOD detection is strongly learnable under risk or learnable under AUC
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 under risk
or AUC. These results imply that it is enough to study learnabiligy of OOD
detection in the prior-unknown spaces. The prior-unknown space is as follows:

###### Definition 4

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}$.

Then the following theorem presents importance and necessity of priori-unknown
space.

###### Theorem 1

Given 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}$ under risk if and
only if OOD detection is learnable in $\mathscr{D}_{XY}^{\prime}$ under risk;
4) OOD detection is learnable in $\mathscr{D}_{XY}$ under AUC if and only if
OOD detection is learnable in $\mathscr{D}_{XY}^{\prime}$ under AUC.

The second result of Theorem 1 bridges the learnability and strong
learnability under risk, 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. The fourth result of Theorem 1 shows that
the learnability of OOD detection under AUC is not influenced by the unknown
class-prior probability $\pi^{\rm out}$. Based on Theorem 1, we focus on our
theory in the prior-unknown spaces. To demystify the learnability of OOD
detection, we introduce five representative priori-unknown spaces:

  * •

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)\\}$.

  * •

Total space $\mathscr{D}_{XY}^{\rm all}$, which consists of all domains.

  * •

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}D$ means the support set of a
distribution $D$.

  * •

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$.

  * •

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.

##  4 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}$.

###  4.1 Necessary Conditions for Learnability of OOD Detection

We first find a necessary condition for the learnability of OOD detection
under risk (AUC), i.e., Condition 1 (Condition 2).

######  Condition 1 (Linear Condition under Risk)

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

$\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)=(1-\alpha)\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+\alpha\inf_{h\in\mathcal{H}}R_{D}^{\rm out}(h).$

The importance of Condition 1 is reflected by Theorem 2, showing that
Condition 1 is a necessary and sufficient condition for the learnability of
OOD detection under risk 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 under risk in the single-distribution space
$\mathscr{D}_{XY}^{D_{XY}}$ for $\mathcal{H}$ if and only if Condition 1
holds.

Theorem 2 implies that Condition 1 is important for the learnability of OOD
detection under risk. Due to the simplicity of single-distribution space,
Theorem 2 implies that Condition 1 is the necessary condition for the
learnability of OOD detection under risk in the prior-unknown space, see Lemma
3 in Appendix C. Then, we focus on finding a necessary condition for the
learnability of OOD detection under AUC. The condition is similar to Condition
1 but replacing risk with AUC. Note that, for simplicity, in the following of
this paper, we use ${\rm AUC}(r;D_{X_{\rm I}},D_{X_{\rm O}})$ to present ${\rm
AUC}(r;D_{XY})$.

######  Condition 2 (Linear Condition under AUC)

For any $D_{XY}=\beta D_{X_{\rm I}Y_{\rm I}}+(1-\beta)D_{X_{\rm O}Y_{\rm O}},$
$D_{XY}^{\prime}=\beta^{\prime}D_{X_{\rm I}Y_{\rm
I}}+(1-\beta^{\prime})D_{X_{\rm O}Y_{\rm O}}^{\prime}\in\mathscr{D}_{XY}$,
then for any $\alpha\in[0,1)$,

$\begin{split}\alpha\sup_{r\in\mathcal{R}}{\rm AUC}(r;D_{X_{\rm I}},D_{X_{\rm
O}})+(1-\alpha)\sup_{r\in\mathcal{R}}{\rm AUC}(r;D_{X_{\rm I}},D_{X_{\rm
O}}^{\prime})=\sup_{r\in\mathcal{R}}{\rm AUC}(r;D_{X_{\rm I}},{D}_{X_{\rm
O}}^{\alpha}),\end{split}$

where ${D}_{X_{\rm O}}^{\alpha}=\alpha D_{X_{\rm O}}+(1-\alpha)D_{X_{\rm
O}}^{\prime}$.

The importance of Condition 2 is reflected in Theorem 3, showing that
Condition 2 is a necessary condition for the learnability of OOD detection
under AUC if the $\mathscr{D}_{XY}$ is a simple distribution space.

###### Theorem 3

Given a ranking function space $\mathcal{R}$ and a domain space
$\mathscr{D}_{XY}$, if OOD detection is learnable under AUC for $\mathcal{R}$
in $\mathscr{D}_{XY}$, then for any
$D_{XY},D_{XY}^{\prime}\in\mathscr{D}_{XY}$, the linear condition under AUC
(i.e., Condition 2) holds.

Since the Condition 2 is a necessary condition for the learnability of OOD
detection under AUC, this condition provides a new way to check if an OOD
detection is learnable under AUC. Namely, if Condition 2 does not hold, OOD
detection is not learnable under AUC.

###  4.2 Impossibility Theorems under Risk

In this subsection, 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 under risk. Theorem 1 shows that Condition 1 is not
always satisfied, especially, when there is an overlap between the ID and OOD
distributions:

######  Definition 5 (Overlap Between ID and OOD)

We say a domain $D_{XY}$ has overlap between ID and OOD distributions, if
there is a $\sigma$-finite measure $\tilde{\mu}$ such that $D_{X}$ is
absolutely continuous with respect to $\tilde{\mu}$, and $\tilde{\mu}(A_{\rm
overlap})>0,\leavevmode\nobreak\ \textit{ where}$ $A_{\rm
overlap}=\\{\mathbf{x}\in\mathcal{X}:f_{\rm
I}(\mathbf{x})>0\leavevmode\nobreak\ \textit{and}\leavevmode\nobreak\ f_{\rm
O}(\mathbf{x})>0\\}$. Here $f_{\rm I}$ and $f_{\rm O}$ are the representers of
$D_{X_{\rm I}}$ and $D_{X_{\rm O}}$ in Radon–Nikodym Theorem (Cohn, 2013),

$D_{X_{\rm I}}=\int f_{\rm I}{\rm d}\tilde{\mu},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ D_{X_{\rm O}}=\int f_{\rm O}{\rm
d}\tilde{\mu}.$

###### Lemma 1

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$,
$\inf_{h\in\mathcal{H}}R_{D}^{\rm out}(h)=0$, then Condition 1 does not hold.
Therefore, OOD detection is not learnable under risk in $\mathscr{D}_{XY}$ for
$\mathcal{H}$.

Lemma 1 clearly shows that under proper conditions, Condition 1 does not hold,
if there exists a domain whose ID and OOD distributions have overlap. By Lemma
1, 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 under Risk)

OOD detection is not learnable under risk 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:

######  Assumption 1 (Separate Space for OOD under Risk)

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 3 in
Appendix N), score-based hypothesis space (Proposition 4 in Appendix N) and
universal kernel space. Next, we use Vapnik–Chervonenkis (VC) dimension (Mohri
et al., 2018) 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 under Risk)

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$,
OOD detection is not learnable under risk in the 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 under risk in the separate space, which
reveals the difficulty of the OOD detection.

###  4.3 Impossibility Theorems under AUC

We then study whether Condition 2 holds in the total space
$\mathscr{D}_{XY}^{\rm all}$. If Condition 2 does not hold, then OOD detection
is not learnable under AUC. We first present Lemma 2 to point out when
Condition 2 does not hold.

###### Lemma 2

Given a ranking function space $\mathcal{R}$, a domain space
$\mathscr{D}_{XY}$ and $D_{XY}=\beta D_{X_{\rm I}Y_{\rm I}}+(1-\beta)D_{X_{\rm
O}Y_{\rm O}},$ $D_{XY}^{\prime}=\beta^{\prime}D_{X_{\rm I}Y_{\rm
I}}+(1-\beta^{\prime})D_{X_{\rm O}Y_{\rm O}}^{\prime}\in\mathscr{D}_{XY}$, let
$P$ be the overlap set between $D_{X_{\rm I}}$ and $D_{X_{\rm O}}$ and
$P^{\prime}$ be the overlap set between $D_{X_{\rm I}}$ and $D_{X_{\rm
O}}^{\prime}$ based on the Definition 5. If

$\displaystyle\sup_{r\in\mathcal{R}}{\rm AUC}(r;D_{X_{\rm I}},D_{X_{\rm O}})$
$\displaystyle=\sup_{r\in\mathcal{R}_{\rm all}}{\rm AUC}(r;D_{X_{\rm
I}},D_{X_{\rm O}})$ $\displaystyle\sup_{r\in\mathcal{R}}{\rm AUC}(r;D_{X_{\rm
I}},D_{X_{\rm O}}^{\prime})$ $\displaystyle=\sup_{r\in\mathcal{R}_{\rm
all}}{\rm AUC}(r;D_{X_{\rm I}},D_{X_{\rm O}}^{\prime}),$

and $D_{X_{\rm I}}(P\cap P^{\prime})<\min\\{D_{X_{\rm I}}(P),D_{X_{\rm
I}}(P^{\prime})\\}$, then Condition 2 does not hold, where $\mathcal{R}_{\rm
all}$ is a ranking function space consisting of all ranking functions from
$\mathcal{X}$ to $\mathbb{R}$. Therefore, OOD detection is not learnable under
AUC in $\mathscr{D}_{XY}$ for $\mathcal{R}$.

Based on Lemma 2, we know that, under proper conditions, Condition 2 does not
hold once there is one domain whose ID and OOD distributions overlap. Then,
based on Lemma 2, we can obtain that the OOD detection is not learnable in the
total space $\mathscr{D}^{\rm all}_{XY}$ for any non-trivial ranking function
space $\mathcal{R}$.

######  Theorem 6 (Impossibility Theorem for Total Space under AUC)

Given ranking function space $\mathcal{R}$, if there exist
$\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}$ and
$r,r^{\prime}\in\mathcal{R}$ such that

$r(\mathbf{x})>r(\mathbf{x}^{\prime})\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\
r^{\prime}(\mathbf{x}^{\prime})>r^{\prime}(\mathbf{x}),$

then the learnability of OOD detection under AUC is not distribution-free for
$\mathcal{R}$.

From Lemma 2, we know that the overlap between $D_{X_{\rm I}}$ and $D_{X_{\rm
O}}$ is an important factor to influence the learnability of OOD detection
under AUC. Thus, similar to the situation under risk, we want to study the
learnability of OOD detection under AUC in separate space
$\mathscr{D}_{XY}^{s}$ first. Before introducing the impossibility theorem for
separate space, we need a mild assumption demonstrated below.

######  Assumption 2 (Separate Space for OOD under AUC)

A ranking function space $\mathcal{R}$ is called separate ranking function
space, if for any $\mathbf{x}\in\mathcal{X}$, there exists
$r_{\mathbf{x}}\in\mathcal{R}$ such that
$r_{\mathbf{x}}(\mathbf{x})<r_{\mathbf{x}}(\mathbf{x}^{\prime})$, for any
$\mathbf{x}^{\prime}\in\mathcal{X}-\\{\mathbf{x}\\}$.

Note that, the above assumption is weak and can be satisfied by some well-
known spaces (see Propositions 1 and 2). The above assumption means that, for
any data point $\mathbf{x}$, its ranking can be the lowest one compared to
other data points in the space $\mathcal{X}$. Finally, we use
Vapnik–Chervonenkis (VC) dimension (Mohri et al., 2018) to help measure the
size of ranking function space, and study the learnability of OOD detection
under AUC in $\mathscr{D}_{XY}^{s}$ with the help the VC dimension.

######  Theorem 7 (Impossibility Theorem for Separate Space under AUC)

Given a separate ranking function space $\mathcal{R}$, if ${\rm
VC}[\phi\circ\mathcal{R}]=d<+\infty$ and
$|\mathcal{X}|\geq(28d+14)\log(14d+7)$, then OOD detection is not learnable
under AUC in $\mathscr{D}_{XY}^{s}$ for $\mathcal{R}$, where
$\phi\circ\mathcal{R}=\\{\mathbf{1}_{r(\mathbf{x})>r(\mathbf{x}^{\prime})}:r\in\mathcal{R}\\}.$

Based on Theorem 7, we obtain a similar result to the learnability of OOD
detection under risk: the finite VC dimension cannot guarantee the
learnability of OOD detection under AUC in the separate space, which further
reveals the difficulty of OOD detection. Although the above impossibility
theorems (under risk and AUC) are frustrating, there is still room to discuss
the conditions in Theorem 5 and Theorem 7, and to find out the proper
conditions for ensuring the learnability of OOD detection under risk and AUC
in the separate space (see the following section).

##  5 When OOD Detection Can Be Successful

Here, we discuss when the OOD detection can be learnable under risk/AUC in
different spaces. We first study the separate space $\mathscr{D}_{XY}^{s}$.

###  5.1 OOD Detection in the Separate Space

Both Theorem 5 and Theorem 7 have 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$
(or
$\sup_{{r}\in\mathcal{R}}|\\{\mathbf{x}\in\mathcal{X}:{r}(\mathbf{x})\in\mathcal{R}\\}|<+\infty$
under AUC metric) is necessary to ensure the learnability of OOD detection
under risk or AUC in $\mathscr{D}_{XY}^{s}$ if Assumption 1 or Assumption 2
holds. However, generally, hypothesis spaces generated by feed-forward neural
networks with proper activation functions have finite VC dimension (Bartlett
et al., 2019; Karpinski and Macintyre, 1997). 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$
under risk metric or
$\sup_{{r}\in\mathcal{R}}|\\{\mathbf{x}\in\mathcal{R}:{r}(\mathbf{x})\in\mathcal{X}\\}|<+\infty$
under AUC metric. Additionally, Theorem 14 also implies that
$|\mathcal{X}|<+\infty$ is the necessary and sufficient condition for the
learnability of OOD detection under risk in a separate space, when the
hypothesis space is generated by FCNN. Hence, $|\mathcal{X}|<+\infty$ may be
necessary in the space $\mathscr{D}_{XY}^{s}$.

#### Learnability under Risk.

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 under risk in $\mathscr{D}_{XY}^{s}$, when
$|\mathcal{X}|<+\infty$.

###### Theorem 8

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 under risk 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 8 is mild. Many
practical hypothesis spaces satisfy this condition, e.g., the FCNN-based
hypothesis space (Proposition 3 in Appendix N), score-based hypothesis space
(Proposition 4 in Appendix N) and universal kernel-based hypothesis space.
Theorem 8 implies that if $K=1$ and OOD detection is learnable under risk 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 under risk in the distribution-agnostic
case, then a large-capacity model is necessary.

Next, we extend Theorem 8 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 $\forall\mathbf{x}\in\mathcal{X}$,

$h(\mathbf{x})=i,\leavevmode\nobreak\ \leavevmode\nobreak\ \textnormal{
if}\leavevmode\nobreak\ h^{\rm in}(\mathbf{x})=i\leavevmode\nobreak\
\textnormal{ and }\leavevmode\nobreak\ h^{\rm b}(\mathbf{x})=1;\textnormal{
otherwise},\leavevmode\nobreak\ h(\mathbf{x})=K+1.$ (6)

We use $\mathcal{H}^{\rm in}\bullet\mathcal{H}^{\rm b}$ to represent a
hypothesis space consisting of all $h$ defined in Eq. (6). In addition, we
also need an additional condition for the loss function $\ell$, shown as
follows:

###### Condition 3

$\ell(y_{2},y_{1})\leq\ell(K+1,y_{1})$, for any in-distribution labels $y_{1}$
and $y_{2}\in\mathcal{Y}.$

###### Theorem 9

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 3 holds, then OOD detection
is learnable under risk in $\mathscr{D}_{XY}^{s}$ for $\mathcal{H}$, where
$\mathcal{H}_{\rm all}$ and $h^{\rm out}$ are defined in Theorem 8.

#### Learnability under AUC.

Then, we study the learnability of OOD detection under AUC in the separate
space. Here we require to introduce a basic assumption in learning theory for
AUC—AUC-based Realizability Assumption, i.e., for any
$D_{XY}\in\mathscr{D}_{XY}$, there exists $r^{*}\in\mathcal{R}$ such that
${\rm AUC}(r^{*};D_{X_{\rm I}},D_{X_{\rm O}})=1$ (see Appendix A.2). Based on
this AUC-based Realizability Assumption, we prove the following theorem.

###### Theorem 10

Given a separate ranking function space $\mathcal{R}$, if
$|\mathcal{X}|<+\infty$, then OOD detection is learnable under AUC in the
separate space $\mathscr{D}_{XY}^{s}$ for $\mathcal{R}$ if and only if AUC-
based Realizability Assumption holds.

Theorem 10 indicates the significance of AUC-based Realizability Assumption in
OOD detection under AUC, which also means that a large ranking function space
is essential for the success of OOD detection under AUC.

###  5.2 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 under risk in the finite-ID-distribution space
$\mathscr{D}_{XY}^{F}$. We first show two necessary concepts below.

######  Definition 6 (ID Consistency)

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 $\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 regarding $\mathscr{D}_{XY}$.

######  Condition 4 (Compatibility)

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}]$,

$h_{\epsilon}\in\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
out}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
out}(h)+\epsilon\\}\cap\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
in}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm in}(h)+\epsilon\\}.$

In Appendix C, Lemma 4 has implied that Condition 4 is a general version of
Condition 1. Next, Theorem 11 shows that Condition 4 is the necessary and
sufficient condition in $\mathscr{D}_{XY}^{F}$.

###### Theorem 11

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

Theorem 11 shows that, in the process of algorithm design, OOD detection
cannot be successful without the compatibility condition if we use risk to
evaluate the performance. Theorem 11 also implies that Condition 4 is
essential for the learnability of OOD detection under risk. 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.

As for the learnability of OOD detection under AUC in the finite-ID-
distribution space, since Condition 2 only considers linearity between OOD
distributions instead of OOD and ID distributions as shown in Condition 1. To
further reveal the learnability of OOD detection under AUC in the finite-ID-
distribution space, we might need to discover a new condition for
compatibility w.r.t. OOD and ID distributions to extend Condition 2.

###  5.3 OOD Detection in the Density-based Space

#### Learnability under Risk.

To ensure that Condition 4 holds, we consider a basic assumption in learning
theory—Risk-based Realizability Assumption (see Appendix A.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}$, Risk-based Realizability Assumption can conclude
the compatibility condition (Condition 4). Based on this observation, we prove
the following theorem:

###### Theorem 12

Given a density-based space $\mathscr{D}_{XY}^{\mu,b}$, if
$\mu(\mathcal{X})<+\infty$, the Risk-based Realizability Assumption holds,
then when $\mathcal{H}$ has finite Natarajan dimension (Shalev-Shwartz and
Ben-David, 2014), 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 Risk-based
Realizability Assumption, Theorem 16 has indicated that in some practical
scenarios, Risk-based Realizability Assumption is the necessary and sufficient
condition for the learnability of OOD detection under risk in the density-
based space. Therefore, Risk-based Realizability Assumption may be
indispensable for the learnability of OOD detection under risk in some
practical scenarios.

#### Learnability under AUC.

To study the learnability of OOD detection under AUC in the density-based
space, we first need to introduce a constant-closure assumption for
$\mathcal{R}$.

###### Assumption 3

We say a ranking function space $\mathcal{R}$ is constant closure, if for any
$r\in\mathcal{R}$, the constant function space
$\overline{r(\mathcal{X})}:={\\{c:r(\mathbf{x})=c,\leavevmode\nobreak\
\forall\mathbf{x}\in\mathcal{X},r\in\mathcal{R}\\}}\subset\mathcal{R}$.

Note that, the above assumption is weak and can be satisfied by some well-
known ranking function space (see Propositions 1 and 2). Based on this
assumption, we give a sufficient condition for learnability of OOD detection
under AUC in the density-based space:

###### Theorem 13

Suppose that $\mathcal{R}$ is constant closure, separate, and
$\mu(\mathcal{X})<+\infty$. Given a density-based space
$\mathscr{D}_{XY}^{\mu,b}$, if the AUC-based Realizability Assumption holds,
then when ${\rm VC}[\phi\circ\mathcal{R}]<+\infty$, OOD detection is learnable
under AUC in $\mathscr{D}_{XY}^{\mu,b}$ for $\mathcal{R}$, where
$\phi\circ\mathcal{R}=\\{\mathbf{1}_{r_{1}(\mathbf{x})>r_{2}(\mathbf{x}^{\prime})}:r_{1},r_{2}\in\mathcal{R}\\}.$
Furthermore, the learning rate $\epsilon_{\rm cons}(n)$ can attain
${O}(1/\sqrt{n^{1-\theta}})$, for any $\theta\in(0,1)$.

Based on Theorem 13, we find that the AUC-based Realizability Assumption is
also important for the learnability of OOD detection under AUC in the density-
based space.

##  6 Connecting Theory to Practice

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

###  6.1 Key Concepts Regarding Fully-connected Neural Networks

#### Fully-connected Neural Networks.

Given a sequence $\mathbf{q}=(l_{1},l_{2},...,l_{g})$, where $l_{i}$ and $g$
are positive integers and $g>2$, we use $g$ to represent the depth of neural
network and use $l_{i}$ to represent the width of the $i$-th layer. After the
activation function $\sigma$ is selected333We consider the _rectified linear
unit_ (ReLU) function as the default activation function $\sigma$, which is
defined by $\sigma(x)=\max\\{x,0\\}$, $\forall$ $x\in\mathbb{R}$. We will not
repeatedly mention the definition of $\sigma$ in the rest of our paper. , we
can obtain the architecture of FCNN according to the sequence $\mathbf{q}$.
Let $\mathbf{f}_{\mathbf{w},\mathbf{b}}$ be the function generated by FCNN
with weights $\mathbf{w}$ and bias $\mathbf{b}$. An FCNN-based scoring
function space is defined as:
$\mathcal{F}_{\mathbf{q}}^{\sigma}:=\\{\mathbf{f}_{\mathbf{w},\mathbf{b}}:\forall\leavevmode\nobreak\
\textnormal{weights}\leavevmode\nobreak\ \mathbf{w},\leavevmode\nobreak\
\forall\leavevmode\nobreak\ \textnormal{bias}\leavevmode\nobreak\
\mathbf{b}\\}.$ In addition, for simplicity, given any two sequences
$\mathbf{q}=(l_{1},...,l_{g})$ and
$\mathbf{q}^{\prime}=(l_{1}^{\prime},...,l_{g^{\prime}}^{\prime})$, we use the
notation $\mathbf{q}\lesssim\mathbf{q}^{\prime}$ to represent the following
equations and inequalities:

$1)\leavevmode\nobreak\ g\leq
g^{\prime},l_{1}=l_{1}^{\prime},l_{g}=l_{g^{\prime}}^{\prime};\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ 2)\leavevmode\nobreak\ l_{i}\leq
l^{\prime}_{i},\leavevmode\nobreak\ \forall i=1,...,g-1;\leavevmode\nobreak\
\leavevmode\nobreak\ \textnormal{and}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ 3)\leavevmode\nobreak\ l_{g-1}\leq
l^{\prime}_{i},\leavevmode\nobreak\ \forall i=g,...,g^{\prime}-1.$

Lemma 16 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:

$h_{\mathbf{w},\mathbf{b}}:=\operatorname*{arg\,max}_{k\in\\{1,...,K+1\\}}{f}^{k}_{\mathbf{w},\mathbf{b}},\leavevmode\nobreak\
\textnormal{where}\leavevmode\nobreak\
{f}^{k}_{\mathbf{w},\mathbf{b}}\leavevmode\nobreak\ \textnormal{is
\leavevmode\nobreak\ the\leavevmode\nobreak\
}k\textnormal{-th}\leavevmode\nobreak\
\textnormal{coordinate\leavevmode\nobreak\ of}\leavevmode\nobreak\
\mathbf{f}_{\mathbf{w},\mathbf{b}}.$

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

#### FCNN-based Ranking Function Space.

Then, based on the definition of FCNN, we show that, given a specific
$\mathbf{q}$, under some mild conditions, $\mathcal{F}_{\mathbf{q}}^{\sigma}$
is the separate and constant closure ranking function space.

###### Proposition 1

Let $\mathcal{X}$ be a bounded feature space. Given
$\mathbf{q}=(l_{1},...,l_{g-1},1)$, then

  * •

if some $s$ with $1<s<g$, $d=l_{1}\leq l_{2}\leq...\leq l_{s}$, and $l_{s}\geq
2d$, $\mathcal{F}_{\mathbf{q}}^{\sigma}$ is the separate ranking function
space;

  * •

$\mathcal{F}_{\mathbf{q}}^{\sigma}$ is constant closure;

  * •

$\\{\mathbf{1}_{f_{1}(\mathbf{x})<f_{2}(\mathbf{x}^{\prime})}:f_{1},f_{2}\in\mathcal{F}_{\mathbf{q}}^{\sigma}\\}$
has finite VC dimension.

#### Score-based Hypothesis Space.

Many OOD detection algorithms detect OOD data by using a score-based strategy.
That is, given a threshold $\lambda$, a scoring function space
$\mathcal{F}_{l}\subset\\{\mathbf{f}:\mathcal{X}\rightarrow\mathbb{R}^{l}\\}$
and a score function $E:\mathcal{F}_{l}\rightarrow\mathbb{R}$, then
$\mathbf{x}$ is regarded as ID data if and only if
$E(\mathbf{f}(\mathbf{x}))\geq\lambda$. We introduce several representative
score functions $E$ as follows: for any
$\mathbf{f}=[f^{1},...,f^{l}]^{\top}\in\mathcal{F}_{l}$,

  * •

softmax-based function (Hendrycks and Gimpel, 2017):
$\lambda\in(\frac{1}{l},1)$ and $T>0$,

$E(\mathbf{f})=\max_{k\in\\{1,...,l\\}}\frac{\exp{(f^{k})}}{\sum_{c=1}^{l}\exp{(f^{c})}};$
(7)

  * •

temperature-scaled function (Liang et al., 2018): $\lambda\in(\frac{1}{l},1)$
and $T>0$,

$E(\mathbf{f})=\max_{k\in\\{1,...,l\\}}\frac{\exp{(f^{k}/T)}}{\sum_{c=1}^{l}\exp{(f^{c}/T)}};$
(8)

  * •

energy-based function (Liu et al., 2020): $\lambda\in(0,+\infty)$ and $T>0$,

$E(\mathbf{f})=T\log\sum_{c=1}^{l}\exp{(f^{c}/T)}.\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ $ (9)

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}\\}$.

#### Score-based Ranking Function Space.

Similar to the FCNN-based ranking function space, for several representative
score functions $E$ (e.g.,, Eqs (7), (8), and (9)), the FCNN-based score
ranking function space ${E}\circ\mathcal{F}_{\mathbf{q}}^{\sigma}$ is
separate, which is evidence that Assumption 2 is weak and can be easily
satisfied.

###### Proposition 2

Given $\mathbf{q}=(l_{1},...,l_{g-1},l)$ and
$\mathbf{q}^{\prime}=(l_{1},...,l_{g-1},1)$, let
$\mathcal{R}={E}\circ\mathcal{F}_{\mathbf{q}}^{\sigma}$, then

  * •

if $\mathcal{F}_{\mathbf{q}^{\prime}}^{\sigma}$ is a separate ranking function
space, $\mathcal{R}$ is the separate ranking function space;

  * •

$\mathcal{R}$ is constant closure;

  * •

$\\{\mathbf{1}_{r_{1}(\mathbf{x})<r_{2}(\mathbf{x}^{\prime})},r_{1},r_{2}\in\mathcal{R}\\}$
has finite VC dimension,

where $E$ is Eq. (7), (8) or (9).

According to the previous section, we find that FCNN-based ranking function
space and FCNN-based score ranking function space can satisfy almost all
conditions in theorems.

###  6.2 Learnability of OOD Detection in Different Spaces

Next, we present applications of our theory regarding the above practical and
important hypothesis spaces and ranking function spaces.

###### Theorem 14

Suppose that Condition 3 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. (6), here $E$ is Eq. (7), (8) or (9). Then

There is a sequence $\mathbf{q}=(l_{1},...,l_{g})$ such that OOD detection is
learnable under risk 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 under risk in $\mathscr{D}^{s}_{XY}$ for
$\mathcal{H}$.

If we consider the ranking function space, we can obtain a similar theoretical
result.

###### Theorem 15

Suppose the ranking function space $\mathcal{R}$ is separate, and FCNN-based
or score-based, i.e., $\mathcal{R}=\mathcal{F}_{\mathbf{q}}^{\sigma}$ or
$\mathcal{R}=E\circ\mathcal{F}_{\mathbf{q}}^{\sigma}$, where $E$ is Eq. (7),
(8) or (9). Then

There is a sequence $\mathbf{q}=(l_{1},...,l_{g})$ such that OOD detection is
AUC learnable in the separate space $\mathscr{D}^{s}_{XY}$ for $\mathcal{R}$
if and only if $|\mathcal{X}|<+\infty$.

Furthermore, if $|\mathcal{X}|<+\infty$, then there is 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 under AUC in $\mathscr{D}^{s}_{XY}$ for
$\mathcal{R}$.

Theorems 14 and 15 state that 1) when the hypothesis space or ranking function
space is FCNN-based or score-based, the finite feature space is the necessary
and sufficient condition for the learnability of OOD detection (under risk or
AUC) 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. (7), (8), or (9) as the score function
$E$, Theorems 14 and 15 also show that the selected score functions $E$ can
guarantee the learnability of OOD detection (under risk or AUC), which is a
theoretical support for the representative works (Liang et al., 2018; Liu et
al., 2020; Hendrycks and Gimpel, 2017). Furthermore, Theorems 16 and 17 also
offer theoretical supports for these works in the density-based space.

###### Theorem 16

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
Eq. (7), (8), or (9)$)$ or FCNN-based
$($$\mathcal{H}=\mathcal{H}_{\mathbf{q}}^{\sigma}$$)$. 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$ Risk-based Realizability Assumption $\iff$ Condition 4

###### Theorem 17

Suppose that the ranking function space $\mathcal{R}$ is separate and score-
based $($$\mathcal{R}=E\circ\mathcal{F}_{\mathbf{q}}^{\sigma})$ or FCNN-based
$($$\mathcal{R}=\mathcal{F}_{\mathbf{q}}^{\sigma})$, where $E$ is Eq. (7), (8)
or (9). If $\mu(\mathcal{X})<+\infty$, then the following three conditions
satisfy:
AUC-based Realizability Assumption $\Rightarrow$ Learnability in
$\mathscr{D}_{XY}^{\mu,b}$ for $\mathcal{R}$ $\Rightarrow$ Condition 2

Compared to Theorem 16, Theorem 17 cannot obtain the equivalence among
Realizability Assumption, Learnability in $\mathscr{D}_{XY}^{\mu,b}$ and
linear condition under AUC. The main reason is that Condition 2 is a weaker
necessary condition for learnability of OOD detection under AUC than Condition
1 for learnability of OOD detection under risk. We need to discover a strong
necessary condition for learnability of OOD detection under AUC to obtain a
similar equivalence that appeared in Theorem 16444A stronger necessary
condition normally means that this necessary condition is closer to the
necessary and sufficient condition..

###  6.3 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?

###### Theorem 18

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
Eq. (7), (8), or (9)$)$ or FCNN-based
$($$\mathcal{H}=\mathcal{H}_{\mathbf{q}}^{\sigma}$$)$. 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 5), then OOD detection is not learnable under
risk in $\mathscr{D}_{XY}$ for $\mathcal{H}$.

When $K=1$ and the hypothesis space is FCNN-based or score-based, Theorem 18
shows that overlap between ID and OOD distributions is the sufficient
condition for the unlearnability of OOD detection under risk. Theorem 18 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. As for the ranking function space, we can obtain a corresponding
but weaker theoretical result shown below.

###### Theorem 19

Let the separate ranking function space $\mathcal{R}$ be FCNN-based or score-
based (where the score function $E$ is Eq. (7), (8), or (9)). Suppose that
$D_{XY},D_{XY}^{\prime}\in\mathscr{D}_{XY}$ are discrete distributions with
$D_{X_{\rm I}Y_{\rm I}}=D_{X_{\rm I}Y_{\rm I}}$ and $D_{X_{\rm
O}}=\delta_{\mathbf{x}},D_{X_{\rm O}}^{\prime}=\delta_{\mathbf{x}^{\prime}}$.
If $D_{X_{\rm O}}=\delta_{\mathbf{x}},D_{X_{\rm
O}}^{\prime}=\delta_{\mathbf{x}^{\prime}}$ have overlaps with $D_{X_{\rm
I}Y_{\rm I}}$ and $D_{X_{\rm O}}\neq D_{X_{\rm O}}^{\prime}$, then OOD
detection is not learnable under AUC in $\mathscr{D}_{XY}$ for $\mathcal{R}$.

##  7 Discussion

#### Connections between Theorems under Risk and AUC.

In our previous conference paper (Fang et al., 2022a), we mainly focus on the
learnability of OOD detection under risk. However, in practice, AUC-related
metrics are often used to evaluate the performance of OOD detection algorithms
(Lin et al., 2021; Huang et al., 2021; Fort et al., 2021b; Ming et al., 2022;
Yang et al., 2022). To fill this gap, we take a further step: investigating
the learnability of OOD detection under AUC. Figure 1 illustrates the
connections between the main theoretical results of learnability of OOD
detection under risk and AUC. In the most of domain spaces considered in this
paper, we can obtain similar theoretical results under AUC compared to
theoretical results under risk. However, when considering the finite-ID-
distribution space, we cannot get a corresponding theorem for the learnability
of OOD detection under AUC. The main reason is that Condition 2 is a weaker
necessary condition for learnability of OOD detection under AUC than Condition
1 for learnability of OOD detection under risk. Thus, additional information
might be required to obtain a stronger necessary condition for AUC
learnability. The influence of Condition 2 also appears in Theorem 17 where we
cannot obtain a strong theoretical result like Theorem 16. To conclude, since
Condition 1 is stronger (i.e., it is closer to necessary and sufficient
condition) than Condition 2, the theoretical results under risk are stronger
than those under AUC. In the future, we need to discover a stronger necessary
condition for learnability of OOD detection under AUC.

Figure 1: Connections among main theoretical results in this paper. Compared
to risk, AUC has a more strict requirement for the classification. Perfect
classification (i.e., accuracy is 100%) does not imply perfect AUC, which is
the reason why theories regarding risk and AUC are very different.

#### Understanding Far-OOD Detection.

Many existing works (Hendrycks and Gimpel, 2017; Yang et al., 2022) study the
far-OOD detection issue. Existing benchmarks include 1) MNIST (Deng, 2012) as
ID dataset, and Texture (Kylberg, 2011), CIFAR-$10$ (Krizhevsky and Hinton,
2009) or Place$365$ (Zhou et al., 2018) as OOD datasets; and 2) CIFAR-$10$
(Krizhevsky and Hinton, 2009) as ID dataset, and MNIST (Deng, 2012), or
Fashion-MNIST (Zhou et al., 2018) 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}$,

${\rm dist}({{\rm supp}D_{X_{\rm O}}},{{\rm supp}D_{X_{\rm I}}})>\tau.$

Theorems 9, 11 and 14 imply that under appropriate hypothesis space,
$\tau$-far-OOD detection is learnable under risk. Theorem 15 implies that
under appropriate hypothesis space, $\tau$-far-OOD detection is learnable
under AUC. In Theorem 9, 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 9 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 (Sun et al., 2022) 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. (Ren et al., 2021; Fort et al., 2021a) consider
this issue and name it near-OOD detection. Existing benchmarks include 1)
MNIST (Deng, 2012) as ID dataset, and Fashion-MNIST (Zhou et al., 2018) or
Not-MNIST (Bulatov, 2011) as OOD datasets; and 2) CIFAR-$10$ (Krizhevsky and
Hinton, 2009) as ID dataset, and CIFAR-$100$ (Krizhevsky et al., 2009) as OOD
dataset. From the theoretical view, some near-OOD tasks may imply the overlap
condition, i.e. Definition 5. Therefore, Lemma 1 and Theorem 18 imply that
near-OOD detection may be not learnable under risk, and Lemma 2 and Theorem 19
imply that near-OOD detection may be not learnable under AUC. Developing a
theory to understand the feasibility of near-OOD detection is an open
question.

##  8 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 (Hendrycks and Gimpel, 2017)555Note that,
some methods assume that OOD data are available in advance (Hendrycks et al.,
2019; Dhamija et al., 2018). However, the exposure of OOD data is a strong
assumption (Yang et al., 2021). We do not consider this situation in our
paper.. Representative works consider using the maximum softmax score
(Hendrycks and Gimpel, 2017), temperature-scaled score (Ren et al., 2019) and
energy-based score (Liu et al., 2020; Wang et al., 2021) to identify OOD data.
2) Density-based methods aim to estimate an ID distribution and identify the
low-density area as OOD data (Zong et al., 2018). 3) The recent development of
generative models provides promising ways to make them successful in OOD
detection (Pidhorskyi et al., 2018; Nalisnick et al., 2019; Ren et al., 2019;
Kingma and Dhariwal, 2018; Xiao et al., 2020). Distance-based methods are
based on the assumption that OOD data should be relatively far away from the
centroids of ID classes (Lee et al., 2018), including Mahalanobis distance
(Lee et al., 2018; Ren et al., 2021), cosine similarity (Zaeemzadeh et al.,
2021), and kernel similarity (Amersfoort et al., 2020).

Early works consider using the maximum softmax score to express the ID-ness
(Hendrycks and Gimpel, 2017). Then, temperature scaling functions are used to
amplify the separation between the ID and OOD data (Ren et al., 2019).
Recently, researchers propose hyperparameter-free energy scores to improve the
OOD uncertainty estimation (Liu et al., 2020; Wang et al., 2021).
Additionally, researchers also consider using the gradients to help improve
the performance of OOD detection (Huang et al., 2021).

Except for the above algorithms, researchers also study the situation, where
auxiliary OOD data can be obtained during the training process (Hendrycks et
al., 2019; Dhamija et al., 2018). 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 (Yang et
al., 2021). Thus, researchers also consider generating OOD data to help the
separation of OOD and ID data (Vernekar et al., 2019). 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.

Zhang et al. (2021) rejects the typical set hypothesis, the claim that
relevant OOD distributions can lie in high likelihood regions of data
distribution, as implausible. Zhang et al. (2021) argues that minimal density
estimation errors can lead to OOD detection failures without assuming an
overlap between ID and OOD distributions. Compared to Zhang et al. (2021), our
theory focuses on the PAC learnable theory of OOD detection. If detectors are
generated by FCNN, our theory (Theorem 18) shows that the overlap is the
sufficient condition to the failure of learnability of OOD detection, which is
complementary to Zhang et al. (2021). 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 Zhang et al.
(2021), Morteza and Li (2022) paves a new avenue to designing provable OOD
detection algorithms. Compared to Morteza and Li (2022), our paper aims to
characterize the learnability of OOD detection to answer the question: is OOD
detection PAC learnable?

#### Open-set Learning Theory.

Liu et al. (2018) is the first to propose the agnostic PAC guarantees for
open-set detection. Unfortunately, the test data must be used during the
training process. Fang et al. (2020) considers the open-set domain adaptation
(OSDA) (Luo et al., 2020) and proposes the first learning bound for OSDA. Fang
et al. (2020) mainly depends on the positive-unlabeled learning techniques
(Kiryo et al., 2017; Ishida et al., 2018; Chen et al., 2021b). However,
similar to Liu et al. (2018), the test data must be available during training.
To study open-set learning (OSL) without accessing the test data during
training, Fang et al. (2021) proposes and studies the almost PAC learnability
for OSL, which is motivated by transfer learning (Dong et al., 2020; Fang et
al., 2022b). Recently, Wang et al. (2022) proposes a novel AUC-based OOD
detection objective named OpenAUC (Yang et al., 2023; Jiang et al., 2023) as
objective function to learn open-set predictors, and builds a corresponding
AUC-based open-set learning theory. In our paper, we study the PAC
learnability for OOD detection, which is an open problem proposed by Fang et
al. (2021).

#### Learning Theory for Classification with Reject Option.

Many works (Chow, 1970; Franc et al., 2021) also investigate the
_classification with reject option_ (CwRO) problem, which is similar to OOD
detection in some cases. Cortes et al. (2016b, a); Ni et al. (2019);
Charoenphakdee et al. (2021); Bartlett and Wegkamp (2008) 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 (Rousseeuw et al., 2011), 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 (Ronchetti and
Huber, 2009; Diakonikolas et al., 2020, 2019). Existing works (Diakonikolas et
al., 2021; Cheng et al., 2021; Diakonikolas et al., 2022) 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 (Goldwasser et al., 2020; Kalai and
Kanade, 2021) 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 Goldwasser
et al. (2020); Kalai and Kanade (2021) aims to give the PAC estimation under
Realizability Assumption (Shalev-Shwartz and Ben-David, 2014). Our theory
focuses on the PAC theory in different cases, which is more difficult and more
practical than PAC theory under Realizability Assumption.

##  9 Conclusions and Future Works

OOD detection has become an important technique to increase the reliability of
machine learning. However, its theoretical foundation is merely investigated,
which hinders real-world applications of OOD detection algorithms. This paper
is the _first_ to provide the PAC theory for OOD detection in terms of two
commonly used metrics: risk and AUC. Our results imply that a universally
consistent algorithm might not exist for all scenarios in OOD detection. Yet,
we still discover some scenarios where OOD detection is learnable under risk
or AUC metrics. Our theory reveals many necessary and sufficient conditions
for the learnability of OOD detection under risk or AUC, hence _paving a road_
to studying the learnability of OOD detection. In the future, we will focus on
studying the robustness of OOD detection based on robust statistics
(Diakonikolas et al., 2021; Diakonikolas and Kane, 2020).

Acknowledgments and Disclosure of Funding

JL and ZF were supported by the Australian Research Council (ARC) under
FL190100149. YL is supported by National Science Foundation (NSF) Award No.
IIS-2237037. FL was supported by the ARC with grant numbers DP230101540 and
DE240101089, and the NSF&CSIRO Responsible AI program with grant number
2303037. ZF would also like to thank Prof. Peter Bartlett, Dr. Tongliang Liu
and Dr. Zhiyong Yang for productive discussions.

## References

  * Amersfoort et al. (2020) J. V. Amersfoort, L. Smith, Y. W. Teh, and Y. Gal.  Uncertainty estimation using a single deep deterministic neural network.  In _ICML_ , 2020.
  * Bartlett and Maass (2003) P. L. Bartlett and W. Maass.  Vapnik-chervonenkis dimension of neural nets.  _The handbook of brain theory and neural networks_ , 2003.
  * Bartlett and Wegkamp (2008) P. L. Bartlett and M. H. Wegkamp.  Classification with a reject option using a hinge loss.  _Journal of Machine Learning Research_ , 2008.
  * Bartlett et al. (2019) P. L. Bartlett, N. Harvey, C. Liaw, and A. Mehrabian.  Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks.  _Journal of Machine Learning Research_ , 20(63):1–17, 2019.
  * Bendale and Boult (2016) A. Bendale and T. E. Boult.  Towards open set deep networks.  In _CVPR_ , 2016.
  * Bulatov (2011) Y. Bulatov.  Notmnist dataset.  _Google (Books/OCR), Tech. Rep.[Online]. Available: http://yaroslavvb. blogspot. it/2011/09/notmnist-dataset. html,2_ , 2011.
  * Charoenphakdee et al. (2021) N. Charoenphakdee, Z. Cui, Y. Zhang, and M. Sugiyama.  Classification with rejection based on cost-sensitive classification.  In _ICML_ , 2021.
  * Chen et al. (2021a) J. Chen, Y. Li, X. Wu, Y. Liang, and S. Jha.  Atom: Robustifying out-of-distribution detection using outlier mining.  _ECML_ , 2021a.
  * Chen et al. (2021b) S. Chen, G. Niu, C. Gong, J. Li, J. Yang, and M. Sugiyama.  Large-margin contrastive learning with distance polarization regularizer.  In _ICML_ , 2021b.
  * Cheng et al. (2021) Y. Cheng, I. Diakonikolas, D. M. Kane, R. Ge, S. Gupta, and M. Soltanolkotabi.  Outlier-robust sparse estimation via non-convex optimization.  In _NeurIPS_ , 2021.
  * Chow (1970) C. K. Chow.  On optimum recognition error and reject tradeoff.  _IEEE Transactions on Information Theory_ , 1970.
  * Cohn (2013) D. L. Cohn.  _Measure theory_.  Springer, 2013.
  * Cortes et al. (2016a) C. Cortes, G. DeSalvo, and M. Mohri.  Boosting with abstention.  In _NeurIPS_ , 2016a.
  * Cortes et al. (2016b) C. Cortes, G. DeSalvo, and M. Mohri.  Learning with rejection.  In _ALT_ , 2016b.
  * Deecke et al. (2018) L. Deecke, R. A. Vandermeulen, L. Ruff, S. Mandt, and M. Kloft.  Image anomaly detection with generative adversarial networks.  In _ECML_ , 2018.
  * Deng (2012) L. Deng.  The MNIST database of handwritten digit images for machine learning research [best of the web].  _IEEE Signal Process. Mag._ , 2012.
  * Dhamija et al. (2018) A. R. Dhamija, M. Günther, and T. E. Boult.  Reducing network agnostophobia.  In _NeurIPS_ , pages 9175–9186, 2018.
  * Diakonikolas and Kane (2020) I. Diakonikolas and D. 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.
  * Diakonikolas et al. (2019) I. Diakonikolas, D. Kane, S. Karmalkar, E. Price, and A. Stewart.  Outlier-robust high-dimensional sparse estimation via iterative filtering.  In _NeurIPS_ , 2019.
  * Diakonikolas et al. (2020) I. Diakonikolas, D. M. Kane, and A. Pensia.  Outlier robust mean estimation with subgaussian rates via stability.  In _NeurIPS_ , 2020.
  * Diakonikolas et al. (2021) I. Diakonikolas, D. M. Kane, A. Stewart, and Y. Sun.  Outlier-robust learning of ising models under dobrushin’s condition.  In _COLT_ , 2021.
  * Diakonikolas et al. (2022) I. Diakonikolas, D. M. Kane, J. C. Lee, and A. Pensia.  Outlier-robust sparse mean estimation for heavy-tailed distributions.  In _NeurIPS_ , 2022.
  * Dong et al. (2020) J. Dong, Y. Cong, G. Sun, B. Zhong, and X. Xu.  What can be transferred: Unsupervised domain adaptation for endoscopic lesions segmentation.  In _CVPR_ , 2020.
  * Dosovitskiy et al. (2021) A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _ICLR_ , 2021.
  * Fang et al. (2020) Z. Fang, J. Lu, F. Liu, J. Xuan, and G. Zhang.  Open set domain adaptation: Theoretical bound and algorithm.  _IEEE Transactions on Neural Networks and Learning Systems_ , 2020\.
  * Fang et al. (2021) Z. Fang, J. Lu, A. Liu, F. Liu, and G. Zhang.  Learning bounds for open-set learning.  In _ICML_ , 2021.
  * Fang et al. (2022a) Z. Fang, Y. Li, J. Lu, J. Dong, B. Han, and F. Liu.  Is out-of-distribution detection learnable?  In _NeurIPS_ , 2022a.
  * Fang et al. (2022b) Z. Fang, J. Lu, F. Liu, and G. Zhang.  Semi-supervised heterogeneous domain adaptation: Theory and algorithms.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2022b.
  * Fort et al. (2021a) S. Fort, J. Ren, and B. Lakshminarayanan.  Exploring the limits of out-of-distribution detection.  In _NeurIPS_ , 2021a.
  * Fort et al. (2021b) S. Fort, J. Ren, and B. Lakshminarayanan.  Exploring the Limits of Out-of-Distribution Detection.  In _NeurIPS_ , 2021b.
  * Franc et al. (2021) V. Franc, D. Průša, and V. Voracek.  Optimal strategies for reject option classifiers.  _CoRR_ , abs/2101.12523, 2021.
  * Goldwasser et al. (2020) S. Goldwasser, A. T. Kalai, Y. Kalai, and O. Montasser.  Beyond perturbations: Learning guarantees with arbitrary adversarial test examples.  In _NeurIPS_ , 2020.
  * Goyal et al. (2020) S. Goyal, A. Raghunathan, M. Jain, H. V. Simhadri, and P. Jain.  DROCC: deep robust one-class classification.  In _ICML_ , 2020.
  * Gretton et al. (2012) A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. J. Smola.  A kernel two-sample test.  _Journal of Machine Learning Research_ , 2012.
  * Hendrycks and Gimpel (2017) D. Hendrycks and K. Gimpel.  A baseline for detecting misclassified and out-of-distribution examples in neural networks.  In _ICLR_ , 2017.
  * Hendrycks et al. (2019) D. Hendrycks, M. Mazeika, and T. G. Dietterich.  Deep anomaly detection with outlier exposure.  In _ICLR_ , 2019.
  * Hsu et al. (2020) Y. Hsu, Y. Shen, H. Jin, and Z. Kira.  Generalized ODIN: detecting out-of-distribution image without learning from out-of-distribution data.  In _CVPR_ , 2020.
  * Huang et al. (2017) G. Huang, Z. Liu, L. van der Maaten, and K. Q. Weinberger.  Densely connected convolutional networks.  In _CVPR_ , 2017.
  * Huang et al. (2021) R. Huang, A. Geng, and Y. Li.  On the Importance of Gradients for Detecting Distributional Shifts in the Wild.  In _NeurIPS_ , 2021.
  * Ishida et al. (2018) T. Ishida, G. Niu, and M. Sugiyama.  Binary classification from positive-confidence data.  In _NeurIPS_ , 2018.
  * Jiang et al. (2023) Y. Jiang, Q. Xu, Y. Zhao, Z. Yang, P. Wen, X. Cao, and Q. Huang.  Positive-unlabeled learning with label distribution alignment.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2023.
  * Kalai and Kanade (2021) A. T. Kalai and V. Kanade.  Efficient learning with arbitrary covariate shift.  In _ALT_ , Proceedings of Machine Learning Research, 2021.
  * Karpinski and Macintyre (1997) M. Karpinski and A. Macintyre.  Polynomial bounds for VC dimension of sigmoidal and general pfaffian neural networks.  _J. Comput. Syst. Sci._ , 54(1):169–176, 1997\.
  * Kingma and Dhariwal (2018) D. P. Kingma and P. Dhariwal.  Glow: Generative flow with invertible 1x1 convolutions.  In _NeurIPS_ , 2018.
  * Kiryo et al. (2017) R. Kiryo, G. Niu, M. C. du Plessis, and M. Sugiyama.  Positive-unlabeled learning with non-negative risk estimator.  In _NeurIPS_ , 2017.
  * Krizhevsky and Hinton (2009) A. Krizhevsky and G. Hinton.  Convolutional deep belief networks on cifar-10.  _Technical report, Citeseer_ , 2009.
  * Krizhevsky et al. (2009) A. Krizhevsky, V. Nair, and G. Hinton.  Cifar-10 and cifar-100 datasets.  2009\.
  * Kylberg (2011) G. Kylberg.  _Kylberg texture dataset v. 1.0_.  2011\.
  * Lee et al. (2018) K. Lee, K. Lee, H. Lee, and J. Shin.  A simple unified framework for detecting out-of-distribution samples and adversarial attacks.  In _NeurIPS_ , 2018.
  * Liang et al. (2018) S. Liang, Y. Li, and R. Srikant.  Enhancing the reliability of out-of-distribution image detection in neural networks.  In _ICLR_ , 2018.
  * Lin et al. (2021) Z. Lin, S. D. Roy, and Y. Li.  Mood: Multi-level out-of-distribution detection.  In _CVPR_ , 2021.
  * Liu et al. (2018) S. Liu, R. Garrepalli, T. G. Dietterich, A. Fern, and D. Hendrycks.  Open category detection with PAC guarantees.  In _ICML_ , 2018.
  * Liu et al. (2020) W. Liu, X. Wang, J. D. Owens, and Y. Li.  Energy-based out-of-distribution detection.  In _NeurIPS_ , 2020.
  * Luo et al. (2020) Y. Luo, Z. Wang, Z. Huang, and M. Baktashmotlagh.  Progressive graph learning for open-set domain adaptation.  In _ICML_ , 2020.
  * Ming et al. (2022) Y. Ming, H. Yin, and Y. Li.  On the impact of spurious correlation for out-of-distribution detection.  _AAAI_ , 2022.
  * Mohri et al. (2018) M. Mohri, A. Rostamizadeh, and A. Talwalkar.  _Foundations of machine learning_.  MIT press, 2018.
  * Morteza and Li (2022) P. Morteza and Y. Li.  Provable guarantees for understanding out-of-distribution detection.  _AAAI_ , 2022.
  * Nalisnick et al. (2019) E. T. Nalisnick, A. Matsukawa, Y. W. Teh, D. Görür, and B. Lakshminarayanan.  Do deep generative models know what they don’t know?  In _ICLR_ , 2019.
  * Ni et al. (2019) C. Ni, N. Charoenphakdee, J. Honda, and M. Sugiyama.  On the calibration of multiclass classification with rejection.  In _NeurIPS_ , 2019.
  * Pidhorskyi et al. (2018) S. Pidhorskyi, R. Almohsen, and G. Doretto.  Generative probabilistic novelty detection with adversarial autoencoders.  In _NeurIPS_ , 2018.
  * Pinkus (1999) A. Pinkus.  Approximation theory of the mlp model in neural networks.  _Acta numerica_ , 8:143–195, 1999.
  * Ren et al. (2019) J. Ren, P. J. Liu, E. Fertig, J. Snoek, R. Poplin, M. A. DePristo, J. V. Dillon, and B. Lakshminarayanan.  Likelihood ratios for out-of-distribution detection.  In _NeurIPS_ , 2019.
  * Ren et al. (2021) J. Ren, S. Fort, J. Liu, A. G. Roy, S. Padhy, and B. Lakshminarayanan.  A simple fix to mahalanobis distance for improving near-ood detection.  _CoRR_ , abs/2106.09022, 2021.
  * Ronchetti and Huber (2009) E. M. Ronchetti and P. J. Huber.  _Robust statistics_.  John Wiley & Sons, 2009.
  * Rousseeuw et al. (2011) P. J. Rousseeuw, F. R. Hampel, E. M. Ronchetti, and W. A. Stahel.  _Robust statistics: the approach based on influence functions_.  John Wiley & Sons, 2011.
  * Ruff et al. (2018) L. Ruff, N. Görnitz, L. Deecke, S. A. Siddiqui, R. A. Vandermeulen, A. Binder, E. Müller, and M. Kloft.  Deep one-class classification.  In _ICML_ , 2018.
  * Safran and Shamir (2017) I. Safran and O. Shamir.  Depth-width tradeoffs in approximating natural functions with neural networks.  In _ICML_ , 2017.
  * Salehi et al. (2021) M. Salehi, H. Mirzaei, D. Hendrycks, Y. Li, M. H. Rohban, and M. Sabokrou.  A unified survey on anomaly, novelty, open-set, and out-of-distribution detection: Solutions and future challenges.  _arXiv preprint arXiv:2110.14051_ , 2021.
  * Shalev-Shwartz and Ben-David (2014) S. Shalev-Shwartz and S. Ben-David.  _Understanding machine learning: From theory to algorithms_.  Cambridge university press, 2014.
  * Shalev-Shwartz et al. (2010) S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan.  Learnability, stability and uniform convergence.  _J. Mach. Learn. Res._ , 11:2635–2670, 2010.
  * Sun et al. (2021) Y. Sun, C. Guo, and Y. Li.  React: Out-of-distribution detection with rectified activations.  In _NeurIPS_ , 2021.
  * Sun et al. (2022) Y. Sun, Y. Ming, X. Zhu, and Y. Li.  Out-of-distribution detection with deep nearest neighbors.  In _ICML_ , 2022.
  * Vernekar et al. (2019) S. Vernekar, A. Gaurav, V. Abdelzad, T. Denouden, R. Salay, and K. Czarnecki.  Out-of-distribution detection in classifiers via generation.  In _NeurIPS Workshop_ , 2019.
  * Wang et al. (2021) H. Wang, W. Liu, A. Bocchieri, and Y. Li.  Can multi-label classification networks know what they don’t know?  In _NeurIPS_ , 2021.
  * Wang et al. (2022) Z. Wang, Q. Xu, Z. Yang, Y. He, X. Cao, and Q. Huang.  Openauc: Towards auc-oriented open-set recognition.  _Advances in Neural Information Processing Systems_ , 35:25033–25045, 2022.
  * Xiao et al. (2020) Z. Xiao, Q. Yan, and Y. Amit.  Likelihood regret: An out-of-distribution detection score for variational auto-encoder.  In _NeurIPS_ , 2020.
  * Yang et al. (2021) J. Yang, K. Zhou, Y. Li, and Z. Liu.  Generalized out-of-distribution detection: A survey.  _CoRR_ , abs/2110.11334, 2021.
  * Yang et al. (2022) J. Yang, K. Zhou, and Z. Liu.  Full-spectrum out-of-distribution detection.  _CoRR_ , 2022.
  * Yang et al. (2023) Z. Yang, Q. Xu, W. Hou, S. Bao, Y. He, X. Cao, and Q. Huang.  Revisiting auc-oriented adversarial training with loss-agnostic perturbations.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , pages 1–18, 2023.
  * Zaeemzadeh et al. (2021) A. Zaeemzadeh, N. Bisagno, Z. Sambugaro, N. Conci, N. Rahnavard, and M. Shah.  Out-of-distribution detection using union of 1-dimensional subspaces.  In _CVPR_ , 2021.
  * Zhang et al. (2021) L. H. Zhang, M. Goldstein, and R. Ranganath.  Understanding failures in out-of-distribution detection with deep generative models.  In _ICML_ , 2021.
  * Zhou et al. (2018) B. Zhou, À. Lapedriza, A. Khosla, A. Oliva, and A. Torralba.  Places: A 10 million image database for scene recognition.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 2018.
  * Zong et al. (2018) B. Zong, Q. Song, M. R. Min, W. Cheng, C. Lumezanu, D. Cho, and H. Chen.  Deep autoencoding gaussian mixture model for unsupervised anomaly detection.  In _ICLR_ , 2018.

1 Table of Contents of Appendix

##  Appendix A Notations

###  A.1 Main Notations and Their Descriptions

In this section, we summarize important notations in Table 1.

Table 1: Main notations and their descriptions. Notation |  Description
---|---
$\bullet$ Spaces and Labels |
$d$ and $\mathcal{X}\subset\mathbb{R}^{d}$ |  the feature dimension of data point and feature space
$\mathcal{Y}$ |  ID label space $\\{1,...,K\\}$
$K+1$ |  $K+1$ represents the OOD labels
$\mathcal{Y}_{\rm all}$ |  $\mathcal{Y}\cup\\{K+1\\}$
$\bullet$ Distributions |
$X_{\rm I}$, $X_{\rm O}$, $Y_{\rm I}$, $Y_{\rm O}$ |  ID feature, OOD feature, ID label, OOD label random variables
$D_{X_{\rm I}Y_{\rm I}}$, $D_{X_{\rm O}Y_{\rm O}}$ |  ID joint distribution and OOD joint distribution
$D_{XY}^{\alpha}$ |  $D_{XY}^{\alpha}=(1-\alpha)D_{X_{\rm I}Y_{\rm I}}+\alpha D_{X_{\rm O}Y_{\rm O}},\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\alpha\in[0,1]$
$\pi^{\rm out}$ |  class-prior probability for OOD distribution
$D_{XY}$ |  $D_{XY}=(1-\pi^{\rm out})D_{X_{\rm I}Y_{\rm I}}+\pi^{\rm out}D_{X_{\rm O}Y_{\rm O}}$, called domain
$D_{X_{\rm I}},D_{X_{\rm O}},D_{X}$ |  marginal distributions for $D_{X_{\rm I}Y_{\rm I}}$, $D_{X_{\rm O}Y_{\rm O}}$ and $D_{XY}$, respectively
$\bullet$ Domain Spaces |
$\mathscr{D}_{XY}$ |  domain space consisting of some domains
$\mathscr{D}_{XY}^{\rm all}$ |  total space
$\mathscr{D}_{XY}^{s}$ |  seperate space
$\mathscr{D}_{XY}^{D_{XY}}$ |  single-distribution space
$\mathscr{D}_{XY}^{F}$ |  finite-ID-distribution space
$\mathscr{D}_{XY}^{\mu,b}$ |  density-based space
$\bullet$ Loss Function, Function Spaces |
$\ell(\cdot,\cdot)$ |  loss: $\mathcal{Y}_{\rm all}\times\mathcal{Y}_{\rm all}\rightarrow\mathbb{R}_{\geq 0}$: $\ell(y_{1},y_{2})=0$ if and only if $y_{1}=y_{2}$
$\mathcal{H}$ |  hypothesis space
$\mathcal{H}^{\rm in}$ |  ID hypothesis space
$\mathcal{H}^{\rm b}$ |  hypothesis space in binary classification
$\mathcal{F}_{l}$ |  scoring function space consisting some $l$ dimensional vector-valued functions
$\mathcal{R}$ |  ranking function space consisting some ranking functions
$\bullet$ Risks, Partial Risks and AUC |
$R_{D}(h)$ |  risk corresponding to $D_{XY}$
$R_{D}^{\rm in}(h)$ |  partial risk corresponding to $D_{X_{\rm I}Y_{\rm I}}$
$R_{D}^{\rm out}(h)$ |  partial risk corresponding to $D_{X_{\rm O}Y_{\rm O}}$
$R_{D}^{\alpha}(h)$ |  $\alpha$-risk corresponding to $D_{XY}^{\alpha}$
${\rm AUC}(r;D_{XY})$ |  AUC corresponding to $D_{XY}$
${\rm AUC}(r;D_{X_{\rm I}},D_{X_{\rm O}})$ |  AUC corresponding to $D_{X_{\rm I}},D_{X_{\rm O}}$
$\bullet$ Fully-Connected Neural Networks |
$\mathbf{q}$ |  a sequence $(l_{1},...,l_{g})$ to represent the architecture of FCNN
$\sigma$ |  activation function. In this paper, we use ReLU function
$\mathcal{F}_{\mathbf{q}}^{\sigma}$ |  FCNN-based scoring function space
$\mathcal{H}_{\mathbf{q}}^{\sigma}$ |  FCNN-based hypothesis space
$\mathbf{f}_{\mathbf{w},\mathbf{b}}$ |  FCNN-based scoring function, which is from $\mathcal{F}_{\mathbf{q}}^{\sigma}$
${h}_{\mathbf{w},\mathbf{b}}$ |  FCNN-based hypothesis function, which is from $\mathcal{H}_{\mathbf{q}}^{\sigma}$
$\bullet$ Score-based Hypothesis Space |
$E$ |  scoring function
$\lambda$ |  threshold
$\mathcal{H}_{\mathbf{q},E}^{\sigma,\lambda}$ |  score-based hypothesis space—a binary classification space
${h}_{\mathbf{f},E}^{\lambda}$ |  score-based hypothesis function—a binary classifier

Given $\mathbf{f}=[f^{1},...,f^{l}]^{\top}$, for any
$\mathbf{x}\in\mathcal{X}$,

$\operatorname*{arg\,max}_{k\in\\{1,...,l\\}}f^{k}(\mathbf{x}):=\max\\{k\in\\{1,...,l\\}:f^{k}(\mathbf{x})\geq
f^{i}(\mathbf{x}),\forall i=1,...,l\\},$

where $f^{k}$ is the $k$-th coordinate of $\mathbf{f}$ and $f^{i}$ is the
$i$-th coordinate of $\mathbf{f}$. The above definition about
$\operatorname*{arg\,max}$ aims to overcome some special cases. For example,
there exist ${k}_{1}$, ${k}_{2}$ ($k_{1}<k_{2}$) such that
$f^{k_{1}}(\mathbf{x})=f^{k_{2}}(\mathbf{x})$ and
$f^{k_{1}}(\mathbf{x})>f^{i}(\mathbf{x})$,
$f^{k_{2}}(\mathbf{x})>f^{i}(\mathbf{x})$, $\forall
i\in\\{1,...,l\\}{-}\\{k_{1},k_{2}\\}$. Then, according to the above
definition,
$k_{2}=\operatorname*{arg\,max}_{k\in\\{1,...,l\\}}f^{k}(\mathbf{x})$.

###  A.2 Realizability Assumptions

######  Assumption 4 (Risk-based Realizability Assumption)

A domain space $\mathscr{D}_{XY}$ and hypothesis space $\mathcal{H}$ satisfy
the Risk-based Realizability Assumption, if for each domain
$D_{XY}\in\mathscr{D}_{XY}$, there exists at least one hypothesis function
$h^{*}\in\mathcal{H}$ such that $R_{D}(h^{*})=0$.

######  Assumption 5 (AUC-based Realizability Assumption)

A domain space $\mathscr{D}_{XY}$ and ranking function space $\mathcal{R}$
satisfy the AUC-based Realizability Assumption under AUC, if for each domain
$D_{XY}\in\mathscr{D}_{XY}$, there exists at least one hypothesis function
$r^{*}\in\mathcal{R}$ such that ${\rm AUC}(h^{*};D_{XY})=1$.

###  A.3 Learnability and PAC learnability

Here we give a proof to show that Learnability given in Definition 1 and PAC
learnability are equivalent.

First, we prove that Learnability concludes the PAC learnability.

According to Definition 1,

$\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R_{D}(\mathbf{A}(S))\leq\inf_{h\in\mathcal{H}}R_{D}(h)+\epsilon_{\rm
cons}(n),$

which implies that

$\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}[R_{D}(\mathbf{A}(S))-\inf_{h\in\mathcal{H}}R_{D}(h)]\leq\epsilon_{\rm
cons}(n).$

Note that $R_{D}(\mathbf{A}(S))-\inf_{h\in\mathcal{H}}R_{D}(h)\geq 0$.
Therefore, by Markov’s inequality, we have

$\mathbb{P}(R_{D}(\mathbf{A}(S))-\inf_{h\in\mathcal{H}}R_{D}(h)<\epsilon)>1-\mathbb{E}_{S\sim
D^{n}_{X_{\rm I}Y_{\rm
I}}}[R_{D}(\mathbf{A}(S))-\inf_{h\in\mathcal{H}}R_{D}(h)]/\epsilon\geq
1-\epsilon_{\rm cons}(n)/\epsilon.$

Because $\epsilon_{\rm cons}(n)$ is monotonically decreasing, we can find a
smallest $m$ such that $\epsilon_{\rm cons}(m)\geq\epsilon\delta$ and
$\epsilon_{\rm cons}(m-1)<\epsilon\delta$, for $\delta\in(0,1)$. We define
that $m(\epsilon,\delta)=m$. Therefore, for any $\epsilon>0$ and
$\delta\in(0,1)$, there exists a function $m(\epsilon,\delta)$ such that when
$n>m(\epsilon,\delta)$, with the probability at least $1-\delta$, we have

$R_{D}(\mathbf{A}(S))-\inf_{h\in\mathcal{H}}R_{D}(h)<\epsilon,$

which is the definition of PAC learnability.

Second, we prove that the PAC learnability concludes Learnability.

PAC-learnability: for any $\epsilon>0$ and $0<\delta<1$, there exists a
function $m(\epsilon,\delta)>0$ such that when the sample size
$n>m(\epsilon,\delta)$, we have that with the probability at least
$1-\delta>0$,

$R_{D}(\mathbf{A}(S))-\inf_{h\in\mathcal{H}}R_{D}(h)\leq\epsilon.$

Note that the loss $\ell$ defined in Section 2 has upper bound (because
$\mathcal{Y}\cup\\{K+1\\}$ is a finite set). We assume the upper bound of
$\ell$ is $M$. Hence, according to the definition of PAC-learnability, when
the sample size $n>m(\epsilon,\delta)$, we have that

$\mathbb{E}_{S}[R_{D}(\mathbf{A}(S))-\inf_{h\in\mathcal{H}}R_{D}(h)]\leq\epsilon(1-\delta)+2M\delta<\epsilon+2M\delta.$

If we set $\delta=\epsilon$, then when the sample size
$n>m(\epsilon,\epsilon)$, we have that

$\mathbb{E}_{S}[R_{D}(\mathbf{A}(S))-\inf_{h\in\mathcal{H}}R_{D}(h)]<(2M+1)\epsilon,$

this implies that

$\lim_{n\rightarrow+\infty}\mathbb{E}_{S}[R_{D}(\mathbf{A}(S))-\inf_{h\in\mathcal{H}}R_{D}(h)]=0,$

which implies the Learnability in Definition 1. We have completed this proof.

##  Appendix B Proof of Theorem 1

See 1

Proof [Proof of Theorem 1.]

Proof of the First Result.

To prove that $\mathscr{D}_{XY}^{\prime}$ is a priori-unknown space, we need
to show that for any $D_{XY}^{\alpha^{\prime}}\in\mathscr{D}_{XY}^{\prime}$,
then $D_{XY}^{\alpha}\in\mathscr{D}_{XY}^{\prime}$ for any $\alpha\in[0,1)$.

According to the definition of $\mathscr{D}_{XY}^{\prime}$, for any
$D_{XY}^{\alpha^{\prime}}\in\mathscr{D}_{XY}^{\prime}$, we can find a domain
$D_{XY}\in\mathscr{D}_{XY}$, which can be written as $D_{XY}=(1-\pi^{\rm
out})D_{X_{\rm I}Y_{\rm I}}+\pi^{\rm out}D_{X_{\rm O}Y_{\rm O}}$ (here
$\pi^{\rm out}\in[0,1)$) such that

$D_{XY}^{\alpha^{\prime}}=(1-\alpha^{\prime})D_{X_{\rm I}Y_{\rm
I}}+\alpha^{\prime}D_{X_{\rm O}Y_{\rm O}}.$

Note that $D_{XY}^{\alpha}=(1-\alpha)D_{X_{\rm I}Y_{\rm I}}+\alpha D_{X_{\rm
O}Y_{\rm O}}$. Therefore, based on the definition of
$\mathscr{D}_{XY}^{\prime}$, for any $\alpha\in[0,1)$,
$D_{XY}^{\alpha}\in\mathscr{D}_{XY}^{\prime}$, which implies that
$\mathscr{D}_{XY}^{\prime}$ is a prior-known space. Additionally, for any
$D_{XY}\in\mathscr{D}_{XY}$, we can rewrite $D_{XY}$ as $D_{XY}^{\pi_{\rm
out}}$, thus $D_{XY}=D_{XY}^{\pi_{\rm out}}\in\mathscr{D}_{XY}^{\prime}$,
which implies that $\mathscr{D}_{XY}\subset\mathscr{D}_{XY}^{\prime}$.

Proof of the Second Result.

First, we prove that Definition 1 concludes Definition 2, if
$\mathscr{D}_{XY}$ is a prior-unknown space:

$\mathscr{D}_{XY}$ is a priori-unknown space, and OOD detection is learnable
in $\mathscr{D}_{XY}$ for $\mathcal{H}$. $\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ {\Huge\Downarrow}$ OOD detection is
strongly learnable in $\mathscr{D}_{XY}$ for $\mathcal{H}$: there exist an
algorithm
$\mathbf{A}:\cup_{n=1}^{+\infty}(\mathcal{X}\times\mathcal{Y})^{n}\rightarrow\mathcal{H}$,
and a monotonically decreasing sequence $\epsilon(n)$, such that
$\epsilon(n)\rightarrow 0$, as $n\rightarrow+\infty$
$\begin{split}\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}\big{[}R^{\alpha}_{D}(\mathbf{A}(S))&-\inf_{h\in\mathcal{H}}R^{\alpha}_{D}(h)\big{]}\leq\epsilon(n),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\forall\alpha\in[0,1],\leavevmode\nobreak\ \forall
D_{XY}\in\mathscr{D}_{XY}.\end{split}$

In the priori-unknown space, for any $D_{XY}\in\mathscr{D}_{XY}$, we have that
for any $\alpha\in[0,1)$,

$D_{XY}^{\alpha}=(1-\alpha)D_{X_{\rm I}Y_{\rm I}}+\alpha D_{X_{\rm O}Y_{\rm
O}}\in\mathscr{D}_{XY}.$

Then, according to the definition of learnability of OOD detection, we have an
algorithm $\mathbf{A}$ and a monotonically decreasing sequence $\epsilon_{\rm
cons}(n)\rightarrow 0$, as $n\rightarrow+\infty$, such that for any
$\alpha\in[0,1)$,

$\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R_{D^{\alpha}}(\mathbf{A}(S))\leq\inf_{h\in\mathcal{H}}R_{D^{\alpha}}(h)+\epsilon_{\rm
cons}(n),\leavevmode\nobreak\ \leavevmode\nobreak\
(\textnormal{{by\leavevmode\nobreak\ the\leavevmode\nobreak\
property\leavevmode\nobreak\ of\leavevmode\nobreak\ priori}-{\rm
unknown\leavevmode\nobreak\ space}})$

where

$R_{D^{\alpha}}(\mathbf{A}(S))=\int_{\mathcal{X}\times\mathcal{Y}_{\rm
all}}\ell(\mathbf{A}(S)(\mathbf{x}),y){\rm
d}D^{\alpha}_{XY}(\mathbf{x},y),\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ R_{D^{\alpha}}(h)=\int_{\mathcal{X}\times\mathcal{Y}_{\rm
all}}\ell(h(\mathbf{x}),y){\rm d}D^{\alpha}_{XY}(\mathbf{x},y).$

Since $R_{D^{\alpha}}(\mathbf{A}(S))=R_{D}^{\alpha}(\mathbf{A}(S))$ and
$R_{D^{\alpha}}(h)=R_{D}^{\alpha}(h)$, we have that

$\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R_{D}^{\alpha}(\mathbf{A}(S))\leq\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)+\epsilon_{\rm
cons}(n),\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\forall\alpha\in[0,1).$ (10)

Next, we consider the case that $\alpha=1$. Note that

$\liminf_{\alpha\rightarrow
1}\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)\geq\liminf_{\alpha\rightarrow
1}\alpha\inf_{h\in\mathcal{H}}R_{D}^{\rm
out}(h)=\inf_{h\in\mathcal{H}}R_{D}^{\rm out}(h).$ (11)

Then, we assume that $h_{\epsilon}\in\mathcal{H}$ satisfies that

$R_{D}^{\rm out}(h_{\epsilon})-\inf_{h\in\mathcal{H}}R_{D}^{\rm
out}(h)\leq\epsilon.$

It is obvious that

$R_{D}^{\alpha}(h_{\epsilon})\geq\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h).$

Let $\alpha\rightarrow 1$. Then, for any $\epsilon>0$,

$R_{D}^{\rm out}(h_{\epsilon})=\lim_{\alpha\rightarrow
1}R_{D}^{\alpha}(h_{\epsilon})=\limsup_{\alpha\rightarrow
1}R_{D}^{\alpha}(h_{\epsilon})\geq\limsup_{\alpha\rightarrow
1}\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h),$

which implies that

$\inf_{h\in\mathcal{H}}R_{D}^{\rm out}(h)=\lim_{\epsilon\rightarrow
0}R_{D}^{\rm out}(h_{\epsilon})\geq\lim_{\epsilon\rightarrow
0}\limsup_{\alpha\rightarrow
1}\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)=\limsup_{\alpha\rightarrow
1}\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h).$ (12)

Combining Eq. (11) with Eq. (12), we have

$\inf_{h\in\mathcal{H}}R_{D}^{\rm out}(h)=\limsup_{\alpha\rightarrow
1}\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)=\liminf_{\alpha\rightarrow
1}\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h),$ (13)

which implies that

$\inf_{h\in\mathcal{H}}R_{D}^{\rm out}(h)=\lim_{\alpha\rightarrow
1}\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h).$ (14)

Note that

$\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R_{D}^{\alpha}(\mathbf{A}(S))=(1-\alpha)\mathbb{E}_{S\sim D^{n}_{X_{\rm
I}Y_{\rm I}}}R_{D}^{\rm in}(\mathbf{A}(S))+\alpha\mathbb{E}_{S\sim
D^{n}_{X_{\rm I}Y_{\rm I}}}R_{D}^{\rm out}(\mathbf{A}(S)).$

Hence, Lebesgue’s Dominated Convergence Theorem (Cohn, 2013) implies that

$\lim_{\alpha\rightarrow 1}\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R_{D}^{\alpha}(\mathbf{A}(S))=\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R_{D}^{\rm out}(\mathbf{A}(S)).$ (15)

Using Eq. (10), we have that

$\lim_{\alpha\rightarrow 1}\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R_{D}^{\alpha}(\mathbf{A}(S))\leq\lim_{\alpha\rightarrow
1}\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)+\epsilon_{\rm cons}(n).$ (16)

Combining Eq. (14), Eq. (15) with Eq. (16), we obtain that

$\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm I}}}R_{D}^{\rm
out}(\mathbf{A}(S))\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm out}(h)+\epsilon_{\rm
cons}(n).$

Since $R_{D}^{\rm out}(\mathbf{A}(S))=R_{D}^{1}(\mathbf{A}(S))$ and
$R_{D}^{\rm out}(h)=R_{D}^{1}(h)$, we obtain that

$\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R_{D}^{1}(\mathbf{A}(S))\leq\inf_{h\in\mathcal{H}}R_{D}^{1}(h)+\epsilon_{\rm
cons}(n).$ (17)

Combining Eq. (10) and Eq. (17), we have proven that: if the domain space
$\mathscr{D}_{XY}$ is a priori-unknown space, then OOD detection is learnable
in $\mathscr{D}_{XY}$ for $\mathcal{H}$.
$\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ {\Huge\Downarrow}$
OOD detection is strongly learnable in $\mathscr{D}_{XY}$ for $\mathcal{H}$:
there exist an algorithm
$\mathbf{A}:\cup_{n=1}^{+\infty}(\mathcal{X}\times\mathcal{Y})^{n}\rightarrow\mathcal{H}$,
and a monotonically decreasing sequence $\epsilon(n)$, such that
$\epsilon(n)\rightarrow 0$, as $n\rightarrow+\infty$,

$\begin{split}\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R^{\alpha}_{D}(\mathbf{A}(S))&\leq\inf_{h\in\mathcal{H}}R^{\alpha}_{D}(h)+\epsilon(n),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\forall\alpha\in[0,1],\leavevmode\nobreak\ \forall
D_{XY}\in\mathscr{D}_{XY}.\end{split}$

Second, we prove that Definition 2 concludes Definition 1:
OOD detection is strongly learnable in $\mathscr{D}_{XY}$ for $\mathcal{H}$:
there exist an algorithm
$\mathbf{A}:\cup_{n=1}^{+\infty}(\mathcal{X}\times\mathcal{Y})^{n}\rightarrow\mathcal{H}$,
and a monotonically decreasing sequence $\epsilon(n)$, such that
$\epsilon(n)\rightarrow 0$, as $n\rightarrow+\infty$,
$\begin{split}\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}\big{[}R^{\alpha}_{D}(\mathbf{A}(S))&-\inf_{h\in\mathcal{H}}R^{\alpha}_{D}(h)\big{]}\leq\epsilon(n),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\forall\alpha\in[0,1],\leavevmode\nobreak\ \forall
D_{XY}\in\mathscr{D}_{XY}.\end{split}$ $\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ {\Huge\Downarrow}$ OOD detection is
learnable in $\mathscr{D}_{XY}$ for $\mathcal{H}$.

If we set $\alpha=\pi^{\rm out}$, then $\mathbb{E}_{S\sim D^{n}_{X_{\rm
I}Y_{\rm
I}}}R^{\alpha}_{D}(\mathbf{A}(S))\leq\inf_{h\in\mathcal{H}}R^{\alpha}_{D}(h)+\epsilon(n)$
implies that

$\begin{split}\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R_{D}(\mathbf{A}(S))\leq\inf_{h\in\mathcal{H}}R_{D}(h)+\epsilon(n),\end{split}$

which means that OOD detection is learnable in $\mathscr{D}_{XY}$ for
$\mathcal{H}$. We have completed this proof.

Proof of the Third Result.

The third result is a simple conclusion of the second result. Hence, we omit
it.

Proof of the Fourth Result.

The fourth result is a simple conclusion of the property of AUC metric. Hence,
we omit it.

##  Appendix C Proof of Theorem 2

Before introducing the proof of Theorem 2, we extend Condition 1 to a general
version (Condition 5). Then, Lemma 3 proves that Conditions 1 and 5 are the
necessary conditions for the learnability of OOD detection. First, we provide
the details of Condition 5.

Let $\Delta_{l}^{\rm
o}=\\{(\lambda_{1},...,\lambda_{l}):\sum_{j=1}^{l}\lambda_{j}<1\leavevmode\nobreak\
{\rm and}\leavevmode\nobreak\ \lambda_{j}\geq 0,\forall j=1,...,l\\}$, where
$l$ is a positive integer. Next, we introduce an important definition as
follows:

######  Definition 7 (OOD Convex Decomposition and Convex Domain)

Given any domain $D_{XY}\in\mathscr{D}_{XY}$, we say joint distributions
$Q_{1},...,Q_{l}$, which are defined over $\mathcal{X}\times\\{K+1\\}$, are
the OOD convex decomposition for $D_{XY}$, if

$D_{XY}=(1-\sum_{j=1}^{l}\lambda_{j})D_{X_{\rm I}Y_{\rm
I}}+\sum_{j=1}^{l}\lambda_{j}Q_{j},$

for some $(\lambda_{1},...,\lambda_{l})\in\Delta_{l}^{\rm o}$. We also say
domain $D_{XY}\in\mathscr{D}_{XY}$ is an OOD convex domain corresponding to
OOD convex decomposition $Q_{1},...,Q_{l}$, if for any
$(\alpha_{1},...,\alpha_{l})\in\Delta_{l}^{\rm o}$,

$(1-\sum_{j=1}^{l}\alpha_{j})D_{X_{\rm I}Y_{\rm
I}}+\sum_{j=1}^{l}\alpha_{j}Q_{j}\in\mathscr{D}_{XY}.$

We extend the linear condition (Condition 1) to a multi-linear scenario.

######  Condition 5 (Multi-linear Condition)

For each OOD convex domain $D_{XY}\in\mathscr{D}_{XY}$ corresponding to OOD
convex decomposition $Q_{1},...,Q_{l}$, the following function

$f_{D,Q}(\alpha_{1},...,\alpha_{l}):=\inf_{h\in\mathcal{H}}\Big{(}(1-\sum_{j=1}^{l}\alpha_{j})R_{D}^{\rm
in}(h)+\sum_{j=1}^{l}\alpha_{j}R_{Q_{j}}(h)\Big{)},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\forall(\alpha_{1},...,\alpha_{l})\in\Delta_{l}^{\rm o}$

satisfies that

$f_{D,Q}(\alpha_{1},...,\alpha_{l})=(1-\sum_{j=1}^{l}\alpha_{j})f_{D,Q}(\mathbf{0})+\sum_{j=1}^{l}\alpha_{j}f_{D,Q}({\bm{\alpha}}_{j}),$

where $\mathbf{0}$ is the $1\times l$ vector, whose elements are $0$, and
${\bm{\alpha}}_{j}$ is the $1\times l$ vector, whose $j$-th element is $1$ and
other elements are $0$.

This is a more general condition compared to Condition 1. When $l=1$ and the
domain space $\mathscr{D}_{XY}$ is a priori-unknown space, Condition 5
degenerates into Condition 1. Lemma 3 shows that Condition 5 is necessary for
the learnability of OOD detection.

###### Lemma 3

Given a priori-unknown space $\mathscr{D}_{XY}$ and a hypothesis space
$\mathcal{H}$, if OOD detection is learnable in $\mathscr{D}_{XY}$ for
$\mathcal{H}$, then Conditions 1 and 5 hold.

Proof [Proof of Lemma 3]

Since Condition 1 is a special case of Condition 5, we only need to prove that
Condition 5 holds.

For any OOD convex domain $D_{XY}\in\mathscr{D}_{XY}$ corresponding to OOD
convex decomposition $Q_{1},...,Q_{l}$, and any
$(\alpha_{1},...,\alpha_{l})\in\Delta_{l}^{\rm o}$, we set

$Q^{\bm{\alpha}}=\frac{1}{\sum_{i=1}^{l}\alpha_{i}}\sum_{j=1}^{l}\alpha_{j}Q_{j}.$

Then, we define

$D_{XY}^{\bm{\alpha}}=(1-\sum_{i=1}^{l}\alpha_{i})D_{X_{\rm I}Y_{\rm
I}}+(\sum_{i=1}^{l}\alpha_{i})Q^{\bm{\alpha}},\leavevmode\nobreak\
\textnormal{which\leavevmode\nobreak\ belongs\leavevmode\nobreak\
to\leavevmode\nobreak\ }\mathscr{D}_{XY}.$

Let

$R^{\bm{\alpha}}_{D}(h)=\int_{\mathcal{X}\times\mathcal{Y}_{\rm
all}}\ell(h(\mathbf{x}),y){\rm d}D_{XY}^{\bm{\alpha}}(\mathbf{x},y).$

Since OOD detection is learnable in $\mathscr{D}_{XY}$ for $\mathcal{H}$,
there exist an algorithm
$\mathbf{A}:\cup_{n=1}^{+\infty}(\mathcal{X}\times\mathcal{Y})^{n}\rightarrow\mathcal{H}$,
and a monotonically decreasing sequence $\epsilon(n)$, such that
$\epsilon(n)\rightarrow 0$, as $n\rightarrow+\infty$, and

$0\leq\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R^{\bm{\alpha}}_{D}(\mathbf{A}(S))-\inf_{h\in\mathcal{H}}R^{\bm{\alpha}}_{D}(h)\leq\epsilon(n).$

Note that

$\begin{split}&\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R^{\bm{\alpha}}_{D}(\mathbf{A}(S))=(1-\sum_{j=1}^{l}\alpha_{j})\mathbb{E}_{S\sim
D^{n}_{X_{\rm I}Y_{\rm I}}}R^{\rm
in}_{D}(\mathbf{A}(S))+\sum_{j=1}^{l}\alpha_{j}\mathbb{E}_{S\sim D^{n}_{X_{\rm
I}Y_{\rm I}}}R_{Q_{j}}(\mathbf{A}(S)),\end{split}$

and

$\inf_{h\in\mathcal{H}}R^{\bm{\alpha}}_{D}(h)=f_{D,Q}(\alpha_{1},...,\alpha_{l}),$

where

$R_{Q_{j}}(\mathbf{A}(S))=\int_{\mathcal{X}\times\\{K+1\\}}\ell(\mathbf{A}(S)(\mathbf{x}),y){\rm
d}Q_{j}(\mathbf{x},y).$

Therefore, we have that for any $(\alpha_{1},...,\alpha_{l})\in\Delta_{l}^{\rm
o}$,

$\begin{split}&\big{|}(1-\sum_{j=1}^{l}\alpha_{j})\mathbb{E}_{S\sim
D^{n}_{X_{\rm I}Y_{\rm I}}}R^{\rm
in}_{D}(\mathbf{A}(S))+\sum_{j=1}^{l}\alpha_{j}\mathbb{E}_{S\sim D^{n}_{X_{\rm
I}Y_{\rm
I}}}R_{Q_{j}}(\mathbf{A}(S))-f_{D,Q}(\alpha_{1},...,\alpha_{l})\big{|}\leq\epsilon(n).\end{split}$
(18)

Let

$g_{n}(\alpha_{1},...,\alpha_{l})=(1-\sum_{j=1}^{l}\alpha_{j})\mathbb{E}_{S\sim
D^{n}_{X_{\rm I}Y_{\rm I}}}R^{\rm
in}_{D}(\mathbf{A}(S))+\sum_{j=1}^{l}\alpha_{j}\mathbb{E}_{S\sim D^{n}_{X_{\rm
I}Y_{\rm I}}}R_{Q_{j}}(\mathbf{A}(S)).$

Note that Eq. (18) implies that

$\begin{split}\lim_{n\rightarrow+\infty}g_{n}(\alpha_{1},...,\alpha_{l})&=f_{D,Q}(\alpha_{1},...,\alpha_{l}),\leavevmode\nobreak\
\leavevmode\nobreak\ \forall(\alpha_{1},...,\alpha_{l})\in\Delta_{l}^{\rm
o},\\\
\lim_{n\rightarrow+\infty}g_{n}(\mathbf{0})&=f_{D,Q}(\mathbf{0}).\end{split}$
(19)

Step 1. Since ${\bm{\alpha}}_{j}\notin\Delta_{l}^{\rm o}$, we need to prove
that

$\lim_{n\rightarrow+\infty}\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R_{Q_{j}}(\mathbf{A}(S))=f({\bm{\alpha}}_{j}),\textit{i.e.},\lim_{n\rightarrow+\infty}g_{n}({\bm{\alpha}}_{j})=f({\bm{\alpha}}_{j}),$
(20)

where ${\bm{\alpha}}_{j}$ is the $1\times l$ vector, whose $j$-th element is
$1$ and other elements are $0$.

Let $\tilde{D}_{XY}=0.5*D_{X_{\rm I}Y_{\rm I}}+0.5*Q_{j}$. The second result
of Theorem 1 implies that

$\begin{split}\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm I}}}R^{\rm
out}_{\tilde{D}}(\mathbf{A}(S))\leq\inf_{h\in\mathcal{H}}R^{\rm
out}_{\tilde{D}}(h)+\epsilon(n).\end{split}$

Since $R^{\rm out}_{\tilde{D}}(\mathbf{A}(S))=R_{Q_{j}}(\mathbf{A}(S))$ and
$R^{\rm out}_{\tilde{D}}(h)=R_{Q_{j}}(h)$,

$\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R_{Q_{j}}(\mathbf{A}(S))\leq\inf_{h\in\mathcal{H}}R_{Q_{j}}(h)+\epsilon(n).$

Note that $\inf_{h\in\mathcal{H}}R_{Q_{j}}(h)\leq\mathbb{E}_{S\sim
D^{n}_{X_{\rm I}Y_{\rm I}}}R_{Q_{j}}(\mathbf{A}(S))$. We have

$0\leq\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R_{Q_{j}}(\mathbf{A}(S))-\inf_{h\in\mathcal{H}}R_{Q_{j}}(h)\leq\epsilon(n).$
(21)

Eq. (21) implies that

$\lim_{n\rightarrow+\infty}\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R_{Q_{j}}(\mathbf{A}(S))=\inf_{h\in\mathcal{H}}R_{Q_{j}}(h).$ (22)

We note that $\inf_{h\in\mathcal{H}}R_{Q_{j}}(h)=f_{D,Q}({\bm{\alpha}}_{j})$.
Therefore,

$\lim_{n\rightarrow+\infty}\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R_{Q_{j}}(\mathbf{A}(S))=f_{D,Q}({\bm{\alpha}}_{j}),\leavevmode\nobreak\
\textit{i.e.},\lim_{n\rightarrow+\infty}g_{n}({\bm{\alpha}}_{j})=f({\bm{\alpha}}_{j}).$
(23)

Step 2. It is easy to check that for any
$(\alpha_{1},...,\alpha_{l})\in\Delta_{l}^{\rm o}$,

$\begin{split}\lim_{n\rightarrow+\infty}g_{n}(\alpha_{1},...,\alpha_{l})&=\lim_{n\rightarrow+\infty}\big{(}(1-\sum_{j=1}^{l}\alpha_{j})g_{n}(\mathbf{0})+\sum_{j=1}^{l}\alpha_{j}g_{n}({\bm{\alpha}}_{j})\big{)}\\\
&=(1-\sum_{j=1}^{l}\alpha_{j})\lim_{n\rightarrow+\infty}g_{n}(\mathbf{0})+\sum_{j=1}^{l}\alpha_{j}\lim_{n\rightarrow+\infty}g_{n}({\bm{\alpha}}_{j}).\end{split}$
(24)

According to Eq. (19) and Eq. (23), we have

$\begin{split}&\lim_{n\rightarrow+\infty}g_{n}(\alpha_{1},...,\alpha_{l})=f_{D,Q}(\alpha_{1},...,\alpha_{l}),\leavevmode\nobreak\
\leavevmode\nobreak\ \forall(\alpha_{1},...,\alpha_{l})\in\Delta_{l}^{\rm
o},\\\ &\lim_{n\rightarrow+\infty}g_{n}(\mathbf{0})=f_{D,Q}(\mathbf{0}),\\\
&\lim_{n\rightarrow+\infty}g_{n}({\bm{\alpha}}_{j})=f({\bm{\alpha}}_{j}),\end{split}$
(25)

Combining Eq. (25) with Eq. (24), we complete the proof.

###### Lemma 4

$\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)=(1-\alpha)\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+\alpha\inf_{h\in\mathcal{H}}R_{D}^{\rm out}(h),\leavevmode\nobreak\
\forall\alpha\in[0,1),$

if and only if for any $\epsilon>0$,

$\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
in}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+2\epsilon\\}\cap\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
out}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
out}(h)+2\epsilon\\}\neq\emptyset.$

Proof [Proof of Lemma 4] For the sake of convenience, we set
$f_{D}(\alpha)=\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)$, for any
$\alpha\in[0,1]$.

First, we prove that $f_{D}(\alpha)=(1-\alpha)f_{D}(0)+\alpha f_{D}(1)$,
$\forall\alpha\in[0,1)$ implies

$\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
in}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+2\epsilon\\}\cap\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
out}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
out}(h)+2\epsilon\\}\neq\emptyset.$

For any $\epsilon>0$ and $0\leq\alpha<1$, we can find
$h_{\epsilon}^{\alpha}\in\mathcal{H}$ satisfying that

$R_{D}^{\alpha}(h_{\epsilon}^{\alpha})\leq\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)+\epsilon.$

Note that

$\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)=\inf_{h\in\mathcal{H}}\Big{(}(1-\alpha)R_{D}^{\rm
in}(h)+\alpha R_{D}^{\rm
out}(h)\Big{)}\geq(1-\alpha)\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+\alpha\inf_{h\in\mathcal{H}}R_{D}^{\rm out}(h).$

Therefore,

$(1-\alpha)\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+\alpha\inf_{h\in\mathcal{H}}R_{D}^{\rm
out}(h)\leq\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)\leq
R_{D}^{\alpha}(h_{\epsilon}^{\alpha})\leq\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)+\epsilon.$
(26)

Note that $f_{D}(\alpha)=(1-\alpha)f_{D}(0)+\alpha
f_{D}(1),\forall\alpha\in[0,1)$, i.e.,

$\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)=(1-\alpha)\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+\alpha\inf_{h\in\mathcal{H}}R_{D}^{\rm out}(h),\forall\alpha\in[0,1).$
(27)

Using Eqs. (26) and (27), we have that for any $0\leq\alpha<1$,

$\epsilon\geq\big{|}R^{\alpha}_{D}(h_{\epsilon}^{\alpha})-\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)\big{|}=\big{|}(1-\alpha)\big{(}R_{D}^{\rm
in}(h_{\epsilon}^{\alpha})-\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)\big{)}+\alpha\big{(}R_{D}^{\rm
out}(h_{\epsilon}^{\alpha})-\inf_{h\in\mathcal{H}}R_{D}^{\rm
out}(h)\big{)}\big{|}.$ (28)

Since $R_{D}^{\rm out}(h_{\epsilon}^{\alpha})-\inf_{h\in\mathcal{H}}R_{D}^{\rm
out}(h)\geq 0$ and $R_{D}^{\rm
in}(h_{\epsilon}^{\alpha})-\inf_{h\in\mathcal{H}}R_{D}^{\rm in}(h)\geq 0$, Eq.
(28) implies that: for any $0<\alpha<1$,

$\begin{split}&R_{D}^{\rm
in}(h_{\epsilon}^{\alpha})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+\epsilon/(1-\alpha),\\\ &R_{D}^{\rm
out}(h_{\epsilon}^{\alpha})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
out}(h)+\epsilon/\alpha.\end{split}$

Therefore,

$h_{\epsilon}^{\alpha}\in\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
in}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+\epsilon/(1-\alpha)\\}\cap\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
out}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
out}(h)+\epsilon/\alpha\\}.$

If we set $\alpha=0.5$, we obtain that for any $\epsilon>0$,

$\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
in}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+2\epsilon\\}\cap\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
out}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
out}(h)+2\epsilon\\}\neq\emptyset.$

Second, we prove that for any $\epsilon>0$, if

$\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
in}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+2\epsilon\\}\cap\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
out}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
out}(h)+2\epsilon\\}\neq\emptyset,$

then $f_{D}(\alpha)=(1-\alpha)f_{D}(0)+\alpha f_{D}(1)$, for any
$\alpha\in[0,1)$.

Let $h_{\epsilon}\in\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
in}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+2\epsilon\\}\cap\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
out}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm out}(h)+2\epsilon\\}$.

Then,

$\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)\leq
R_{D}^{\alpha}(h_{\epsilon})\leq(1-\alpha)\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+\alpha\inf_{h\in\mathcal{H}}R_{D}^{\rm
out}(h)+2\epsilon\leq\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)+2\epsilon,$

which implies that $|f_{D}(\alpha)-(1-\alpha)f_{D}(0)-\alpha f_{D}(1)|\leq
2\epsilon$.

As $\epsilon\rightarrow 0$, $|f_{D}(\alpha)-(1-\alpha)f_{D}(0)-\alpha
f_{D}(1)|\leq 0$. We have completed the proof.
See 2

Proof [Proof of Theorem 2] Based on Lemma 3, we obtain that Condition 1 is the
necessary condition for the learnability of OOD detection in the single-
distribution space $\mathscr{D}_{XY}^{D_{XY}}$. Next, it suffices to prove
that Condition 1 is the sufficient condition for the learnability of OOD
detection in the single-distribution space $\mathscr{D}_{XY}^{D_{XY}}$. We use
Lemma 4 to prove the sufficient condition.

Let $\mathscr{F}$ be the infinite sequence set that consists of all infinite
sequences, whose coordinates are hypothesis functions, i.e.,

$\mathscr{F}=\\{{\bm{h}}=(h_{1},...,h_{n},...):\forall
h_{n}\in\mathcal{H},n=1,....,+\infty\\}.$

For each ${\bm{h}}\in\mathscr{F}$, there is a corresponding algorithm
$\mathbf{A}_{\bm{h}}$666In this paper, we regard an algorithm as a mapping
from $\cup_{n=1}^{+\infty}(\mathcal{X}\times\mathcal{Y})^{n}$ to $\mathcal{H}$
or $\mathcal{R}$. So we can design an algorithm like this.:
$\mathbf{A}_{\bm{h}}(S)=h_{n},\leavevmode\nobreak\ {\rm
if}\leavevmode\nobreak\ |S|=n$. $\mathscr{F}$ generates an algorithm class
$\mathscr{A}=\\{\mathbf{A}_{\bm{h}}:\forall{\bm{h}}\in\mathscr{F}\\}$. We
select a consistent algorithm from the algorithm class $\mathscr{A}$.

We construct a special infinite sequence
$\tilde{{\bm{h}}}=(\tilde{h}_{1},...,\tilde{h}_{n},...)\in\mathscr{F}$. For
each positive integer $n$, we select $\tilde{h}_{n}$ from
$\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
in}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+2/n\\}\cap\\{h^{\prime}\in\mathcal{H}:R_{D}^{\rm
out}(h^{\prime})\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm out}(h)+2/n\\}$ (the
existence of $\tilde{h}_{n}$ is based on Lemma 4). It is easy to check that

$\begin{split}&\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm I}}}R_{D}^{\rm
in}(\mathbf{A}_{\tilde{{\bm{h}}}}(S))\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+2/n.\\\ &\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm I}}}R_{D}^{\rm
out}(\mathbf{A}_{\tilde{{\bm{h}}}}(S))\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm
out}(h)+2/n.\end{split}$

Since $(1-\alpha)\inf_{h\in\mathcal{H}}R_{D}^{\rm
in}(h)+\alpha\inf_{h\in\mathcal{H}}R_{D}^{\rm
out}(h)\leq\inf_{h\in\mathcal{H}}R_{D}^{\rm\alpha}(h)$, we obtain that for any
$\alpha\in[0,1]$,

$\begin{split}&\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}R_{D}^{\alpha}(\mathbf{A}_{\tilde{{\bm{h}}}}(S))\leq\inf_{h\in\mathcal{H}}R_{D}^{\alpha}(h)+2/n.\end{split}$

We have completed this proof.

##  Appendix D Proof of Theorem 3

See 3

Proof [Proof of Theorem 3] According to Definition 3, we assume that
$\mathbf{A}$ is the AUC learnable algorithm: there exists learning rate
$\epsilon(n)$ such that for any $D_{XY}\in\mathscr{D}_{XY}$,

$\mathbb{E}_{S\sim D^{n}_{X_{\rm I}Y_{\rm
I}}}\big{[}\sup_{r\in\mathcal{R}}{\rm AUC}(r;D_{XY})-{\rm
AUC}(\mathbf{A}(S);D_{XY})\big{]}\leq\epsilon(n).$ (29)

For any $D_{XY}=\beta D_{X_{\rm I}Y_{\rm I}}+(1-\beta)D_{X_{\rm O}Y_{\rm O}},$
$D_{XY}^{\prime}=\beta^{\prime}D_{X_{\rm I}Y_{\rm
I}}+(1-\beta^{\prime})D_{X_{\rm O}Y_{\rm O}}^{\prime}\in\mathscr{D}_{XY}$, we