Timezone: »

Is Out-of-Distribution Detection Learnable?
Zhen Fang · Yixuan Li · Jie Lu · Jiahua Dong · Bo Han · Feng Liu

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #920

Supervised learning aims to train a classifier under the assumption that training and test data are from the same distribution. To ease the above assumption, researchers have studied a more realistic setting: out-of-distribution (OOD) detection, where test data may come from classes that are unknown during training (i.e., OOD data). Due to the unavailability and diversity of OOD data, good generalization ability is crucial for effective OOD detection algorithms. To study the generalization of OOD detection, in this paper, we investigate the probably approximately correct (PAC) learning theory of OOD detection, which is proposed by researchers as an open problem. First, we find a necessary condition for the learnability of OOD detection. Then, using this condition, we prove several impossibility theorems for the learnability of OOD detection under some scenarios. Although the impossibility theorems are frustrating, we find that some conditions of these impossibility theorems may not hold in some practical scenarios. Based on this observation, we next give several necessary and sufficient conditions to characterize the learnability of OOD detection in some practical scenarios. Lastly, we also offer theoretical supports for several representative OOD detection works based on our OOD theory.

Author Information

Zhen Fang (University of Technology Sydney)

Zhen Fang received his PhD degree in computer science from the Australian Artificial Intelligence Institute, University of Technology Sydney, Australia, in 2021. Now, he is Postdoctoral Research Fellow at University of Technology Sydney, Australia. He is a Member of the Decision Systems and e-Service Intelligence (DeSI) Research Laboratory, Australian Artificial Intelligence Institute, University of Technology Sydney. His research interests include transfer learning and domain adaptation. He has published several paper related to domain adaptation, transfer learning and out-of-distribution learning in AAAI, IJCAI, ICML, NeurIPS, TPAMI.

Yixuan Li (University of Wisconsin-Madison)
Jie Lu
Jiahua Dong (ETHZ - ETH Zurich)
Feng Liu (University of Melbourne)

More from the Same Authors