Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides theory on PAC-learnability of out-of-distribution (OOD) detection.
OOD detection is classification task but test data may come from unknown classes.
If test data come from classes known during training, we want to classify them into those classes, but otherwise, we need to detect they belong to unknown classes.
The authors provide a series of theorems about conditions for OOD detection in several interesting setups.
Their results imply that we should not hope for finding an OOD detection algorithm that works in general cases, but we can still design algorithms for special cases.
strengths_and_weaknesses: # Strengths
- The paper provides rigorous theory on an important machine learning task.
- The paper is excellently-written and easy to follow despite its technical content although all the proofs are in the supplemental material.
- The scenarios that the authors consider are not too technical but highly relevant to practical OOD detection methods. Hence, it gives useful insights for practitioners as well.

# Weaknesses
- Most results are negative ones showing impossibility of OOD detection in general cases, and the paper does not provide concrete algorithms.
questions: - l.118, "they are equivalent by Markov's inequality": I can see that Eq. (2) implies the standard form of PAC-learnability by Markov's inequality, but I cannot see how we can confirm the converse. Could the authors provide a proof or a reference for that?
- ll.260-261, "Since researchers can only collect finite ID datasets as the training data in the process of algorithm design, it is worthy to study the learnability of OOD detection in the finite-ID-distribution space": I am not sure how to relate the fact to finite-ID-distribution space. Does "finite ID datasets" here mean datasets of finite samples or a finite variety of datasets? If it's for the latter sense, do the authors assume $\vert \mathcal{X} \vert < \infty$ here?
- Could the authors define the realizability assumption explicitly?
- The conditions of Theorem 3, $\inf_{h\in\mathcal{H}} R_D^{\mathrm{in}}(h) = 0$ and $\inf_{h\in\mathcal{H}} R_D^{\mathrm{out}}(h) = 0$, look similar to the realizability assumption and the compatibility condition. However, the conditions of Theorem 3 seem to be prohibiting the learnability in Theorem 3 while the realizability and the compatibility conditions are making the learning possible in Theorem 8 and Theorem 9. Should we consider such conditions as good ones or bad ones?
- The paper refer to distributions as "domains." Is this a common way of saying it in the literature? It is a little confusing to me, and I do not see good motivation for the choice of the word.
limitations: The theory only handles a few special combinations of distributions and hypothesis spaces although I do not consider this as a very strong limitation because they cover many common practical situations.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The out-of-distribution detection problem is defined as follows: after training on an ID joint distribution $D_{X_{ I}Y_{ I}}$ with random variables from $\mathcal{X}$ and labels in $\mathcal{Y}$, we need to learn a classifier which can detect a test sample as OOD if the sample is drawn from outside of $D_{X_{ I}Y_{ I}}$, while predicting the correct label if the test sample is drawn from ID distribution.

This paper mainly answers the agnostic PAC learnability of out-of-distribution detection in different scenarios, which is known as an open problem in out-of-distribution learning theory. 

This paper firstly defines the basic concepts of agnostic PAC learnability of OOD detection, which are natural extensions of agnostic PAC learnability of supervised learning. Then, considering the imbalance issue of OOD detection, the author proposes the prior-unknown spaces and indicates that researchers should focus on agnostic PAC learnability of OOD detection in the prior-unknown spaces.

By discovering a necessary condition (Condition 1), the author shows that the condition cannot hold in the total space and separate space. Based on this observation, the paper proves that in most general setting (total space and separate space), OOD detection is not agnostic PAC learnable. 

Next, the author proves the necessary and sufficient conditions to show that the separate space can be learnable if and only if the hypothesis space contains almost all classifiers, while the paper proves that in the finite-ID-distribution space, Condition 3 is the necessary and sufficient condition for the learnability of OOD detection. The paper also proves that in the realizability assumption case, OOD detection is learnable in density-based space.

Lastly, the author considers OOD detection in some practical hypothesis space—FCNN-based and score-based. The paper shows that in the separate space, OOD is learnable in FCNN-based spaces or score-based spaces iff the feature space is finite. In Theorem 11, the paper shows that Condition 1, condition 3 and realizability assumption and learnability are equivalent. In Theorem 12, the author also reveals that overlap will lead to the failure of OOD detection.

This paper is important to understand when and how OOD can work in real applications, as this also gives insight and guidance to OOD detection algorithm designing.


strengths_and_weaknesses: Strengths:
1.	The issue is definitely relevant to the NeurIPS as well as ICML, ALT and COLT. When OOD detection can be learnable is an open issue in OOD learning. Due to missing necessary information from the OOD data, the learnability of OOD detection is very difficult. Despite plenty of applied work, there is still few theory to be established for this issue. To address this issue, it requires the author to dig and discovery unknown necessary conditions from scratch. This paper does make an effort to address this problem and make great progress.  
2.	This paper is sound. I am interested in this topic, but the paper is long. So I spend several days to check the proofs carefully. All of the results in this paper are supported by proofs.  From what I have checked, all proofs are correct.
3.	The paper answers negatively and positively the question of agnostic PAC learnability of OOD, and introduces sufficient assumptions to recover it (such as assumption 1). These assumptions are practical and mild, and can be satisfied by many practical cases, for example, FCNNs, CNNs and kernel space. Therefore, the theory can be tightly connected with practical applications.
4.	Plenty applied work has been proposed to address this OOD, but theoretical works discussing when OOD detection work is lacking. The paper theoretical shows when OOD can work in practical cases. I think the contribution are significantly important and this work can give a good guidance for the development of OOD detection. This paper has the potential to achieve a long term impact to OOD learning field.
5.	The paper is written well enough to understand.


Weaknesses:

1.	The appendix is long and the proofs are complicated. Although I have check almost all important proofs and believe they are correct, I still spend three days to check them. It is better for the author to provide proof sketch and intuitions for important theorems. 
2.	It seems that the description of Theorem 4 in main text is slightly different from the description of Theorem 4 in appendix. I have checked it and found that the description Theorem 4 in appendix is more rigorous. Although you have explained why they are different (because of the space limitation) in appendix G.2, I still suggest that the author should use the description of Theorem 4 in appendix to replace Theorem 4 in main text, because the description in appendix is correct. 
3.	Typos/grammar:
1) In line 305, $K$ should be $\lambda$.
2) In line 340, $D_{XY|Y}^{ in}$ should be $D_{X_{I}Y_{I}}$.
3) In line 171, $D_{X_{I}}$ should be $D_{X_{I}Y_{I}}$?
4.  After checking your proof, I think Condition 2 can be removed from Theorems 7 and 10. Although Condition 2 is weak and meaningful, I still think it is better to remove Condition 2. The idea about how to remove Condition 2 can be motivate from the proof of Theorem 9 (the second part).


questions: See the weakness 1,2,3,4.
limitations: The paper focuses on theory for OOD detection and gives the first theoretical support to understand when OOD detection can work. There is no any potential negative social impact.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper explores the theoretical foundation of learnability of out-of-distribution detection. Based on the PAC learning theory, the paper proved several impossibility theorems for the learnability of OOD detection under some scenarios, and finds some conditions that OOD detection is PAC-learnable. Also, the paper demonstrate the theory in real practice using FCNN and OOD scores as examples. Recently there are loads of papers proposed empirical methods for OOD detection, but the theory is rarely explored.This paper is the first to investigate the theory of OOD detection so thoroughly, which is meaningful to this field.
strengths_and_weaknesses: Strengths:
- The paper is clear and well-written. And the proofs are generally correct.
- This paper is one of the few theoretical works focusing on OOD detection, which plays a significant role in this field.
- The theory is intuitive and have some practical impacts. It can somewhat guide the design of OOD detection algorithms.

Weakness:
- Some notations and expressions can be refined in Section 2. For example, $S$ or $D_{XY}^n $ in eq.2 can be explained (minor). 
- Some typos. In section 2 Definition 1. "if there exist an algorithm" -> "if there exists an algorithm".
- Some experiments can be added to show the correctness of the theorems.
- The practical impacts may not be large enough. 
questions: - What is the "+" means in $D_X := (1-\pi^{out}) D_{X_1} + \pi^{out} D_{X_O}$ ? (line 82) 
limitations: Yes.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: Recently, reliable AI plays important role in designing an intelligent machine learning system. How to let AI system tell “do not know” is critical for reliable AI systems, which is the focus of this paper. In this paper, the authors consider a practical scenario where out-of-distribution data (the system should not know) is unseen during the training process. In this scenario, the authors want to investigate if the OOD detection is learnable. 

The theoretical part is easy to follow. I find that the theoretical contributions are completed and interesting. At first, this paper shows that OOD detection is not learnable in the most general case, which does make sense due to the unavailability of OOD data. Then, this paper points out a necessary condition (sometimes as a necessary and sufficient condition) of the learnability of OOD detection, which directly induces a lot of necessary and sufficient conditions of learnability of OOD detection. In my opinion, this is a significant contribution to the field. Finding necessary and sufficient conditions is always a core and the most important part when studying a problem.

From the practical part, several theorems are considered using networks or finite in-distribution domains, making the whole paper also fit the taste of practitioners. In many practical scenarios, we cannot expect OOD data is the ones we have already seen, which is exactly the problem this paper studies. Besides, the theorem regarding finite ID distributions is also practical. If I understand correctly, in this practical scenario, this paper gives a better result, which is very interesting to me and significant to the field (we often only have finite ID distributions in practice).

strengths_and_weaknesses: Pros:

1. This paper is the first to characterize the learnability of OOD detection, which makes a significant contribution to the field. There are many OOD detection papers targeting the problem this paper considers. The problem is very difficult yet very important in practice. Previously, no theoretical works are proposed for this problem. In this paper, a completed theory is proposed for this problem, including when OOD detection will fail and when OOD detection will succeed. A lot of necessary and sufficient conditions of learnability of OOD detection are exciting to this field.

2. For practitioners, this paper relieves some big concerns regarding existing OOD detection methods. Before this work, one could intuitively think that OOD detection is not learnable (which is true in the most general case, yet our common datasets are not such general). However, this paper gives a theoretical boundary between learnability and unlearnability of OOD detection by proving some necessary and sufficient conditions. Thus, we can know, on what kind of datasets, OOD detection is learnable.
This contribution is significant and meaningful. 

3. Fig. 1 is very helpful in understanding the key necessary condition of OOD detection, which seems that it can motivate a bunch of papers in this research direction.

4. I can see that there are three research topics regarding that “let AI say don’t know”: 1) classification with reject option; 2) PQ learning; and 3) OOD detection. The first two have already had some theories but the last one does not have. This paper fills up this gap, making OOD detection method (which might be more practical than the other two) possible in theory.

5. Although the proofs of this paper are not easy to follow, the logic and organizations of proofs are clear. I have read most proofs and have not found unrecoverable errors for important results. The proofs are soundness.

Cons:

1. I have read some papers regarding PQ learning and feel that PQ learning is totally different from OOD detection. PQ learning focuses on scenarios where OOD data are somehow available, yet OOD detection focuses on the opposite scenarios. However, it is better to demonstrate their difference deeply. Does PQ learning have limitations when meeting different OOD data in the future? I am interested to see some discussions regarding this part.

2. Similar to PQ learning, classification with reject option could be deeply compared to OOD detection instead of just comparing both using plain words. I know they are very different and OOD detection theory is more difficult. But giving more detailed comparation is better for this paper.

3. I have some questions regarding Figure 1, which I hope that the authors can confirm with me. In my opinion, the solid line is the ground-truth line. Do we expect that the estimated lines (dash lines) get closer to the solid line? If so, when overlap exists, why is the solid line not straight? Can you bring me to the specific part regarding this? It seems that the solid line will be straight if there are no overlaps, which makes OOD detection learnable. Is that correct?

4. More explanation, like Figure 1, could be added for understanding the theorems better. Brief proofs might be also useful.

5. In line 26, there are too many separate citations. In my opinion, it is not necessary.

6. Line 148 should not be a new paragraph.

7. The density-based space is very important and interesting. Especially, the theorem 11 is one of the spotlights. Can you give more explanations or applications regarding density-based space (theorems 9 and 11)? 

8. The mathematic expression in Definition 1 about PAC learnability is different with the normal expression of PAC learnability. Although line 118 has told us that they are equivalent and I also realize that they are equivalent by paper [21,30] (exercise 4.5 in [21] can prove it?) , the paper will be improved and more clear if a brief proof for the equivalent descriptions is given in the final version.

questions: Please answer/revise your paper according to the questions proposed in weaknesses 1,2,3,4,7,8.
limitations: It is a pure theoretical paper. So I think there is no negative social impacts.
review_title: null

Meta-review: metareview: This paper studies generalization and learnability questions in the realm of out-of-distribution (OOD) detection. Specifically, it applies PAC learning to the theory of OOD detection. The contributions include new conceptual definitions of agnostic PAC learnability of OOD detection. Then, the authors argue for studying prior-unknown spaces under certain necessary conditions. This leads to a number of novel results, both in theory and in terms of possible practical impact (e.g., when OOD detection will succeed vs. fail). The reviewers found the paper sound, insightful, clearly-written, and novel. This paper benefits the community because it is one of the few theoretical studies of OOD detection.

For the final version, the reviewers have many comments regarding definitions, terminology, and some of the technical details. I encourage the authors to incorporate as much of this feedback as possible to make the paper easier to read for future audiences. For example, please 
- add the full proof of how Eq. (2) relates to PAC-learnability,
- add and clarify the realizability assumption in the revision,
- use the description of Theorem 4 in appendix G.2 to replace Theorem 4 in main text.

The authors should also provide proof sketches for the main results (either in the main paper or the appendix). This paper contains many theoretical results, as well as ways to unpack them in the context of more practical scenarios. All of this would benefit from clear exposition. There are also a handful of typos to fix (in the notation/equations and in the exposition). Given the large number of small questions/issues, it is important to address these in the final version of the paper.

The reviewers all vote positively toward acceptance of this paper, and therefore, I also recommend acceptance.
confidence: Certain
Decision: Accept