Timezone: »
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)
Bo Han (HKBU / RIKEN)
Feng Liu (University of Melbourne)
More from the Same Authors
-
2021 Spotlight: TOHAN: A One-step Approach towards Few-shot Hypothesis Adaptation »
Haoang Chi · Feng Liu · Wenjing Yang · Long Lan · Tongliang Liu · Bo Han · William Cheung · James Kwok -
2022 Poster: SoLar: Sinkhorn Label Refinery for Imbalanced Partial-Label Learning »
Haobo Wang · Mingxuan Xia · Yixuan Li · Yuren Mao · Lei Feng · Gang Chen · Junbo Zhao -
2022 Poster: RSA: Reducing Semantic Shift from Aggressive Augmentations for Self-supervised Learning »
Yingbin Bai · Erkun Yang · Zhaoqing Wang · Yuxuan Du · Bo Han · Cheng Deng · Dadong Wang · Tongliang Liu -
2022 Poster: Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs »
Yongqiang Chen · Yonggang Zhang · Yatao Bian · Han Yang · MA Kaili · Binghui Xie · Tongliang Liu · Bo Han · James Cheng -
2022 Poster: Adversarial Training with Complementary Labels: On the Benefit of Gradually Informative Attacks »
Jianan Zhou · Jianing Zhu · Jingfeng ZHANG · Tongliang Liu · Gang Niu · Bo Han · Masashi Sugiyama -
2022 Poster: Towards Lightweight Black-Box Attack Against Deep Neural Networks »
Chenghao Sun · Yonggang Zhang · Wan Chaoqun · Qizhou Wang · Ya Li · Tongliang Liu · Bo Han · Xinmei Tian -
2022 : Pre-training Robust Feature Extractor Against Clean-label Data Poisoning Attacks »
Ting Zhou · Hanshu Yan · Lei LIU · Jingfeng Zhang · Bo Han -
2023 Poster: Enhancing Adversarial Contrastive Learning via Adversarial Invariant Regularization »
Xilie Xu · Jingfeng ZHANG · Feng Liu · Masashi Sugiyama · Mohan Kankanhalli -
2023 Poster: SODA: Robust Training of Test-Time Data Adaptors »
Zige Wang · Yonggang Zhang · Zhen Fang · Long Lan · Wenjing Yang · Bo Han -
2023 Poster: Federated Learning with Bilateral Curation for Partially Class-Disjoint Data »
Ziqing Fan · ruipeng zhang · Jiangchao Yao · Bo Han · Ya Zhang · Yanfeng Wang -
2023 Poster: InstanT: Semi-supervised Learning with Instance-dependent Thresholds »
Muyang Li · Runze Wu · Haoyu Liu · Jun Yu · Xun Yang · Bo Han · Tongliang Liu -
2023 Poster: Dream the Impossible: Outlier Imagination with Diffusion Models »
Xuefeng Du · Yiyou Sun · Jerry Zhu · Yixuan Li -
2023 Poster: FedFed: Feature Distillation against Data Heterogeneity in Federated Learning »
Zhiqin Yang · Yonggang Zhang · Yu Zheng · Xinmei Tian · Hao Peng · Tongliang Liu · Bo Han -
2023 Poster: FlatMatch: Bridging Labeled Data and Unlabeled Data with Cross-Sharpness for Semi-Supervised Learning »
Zhuo Huang · Li Shen · Jun Yu · Bo Han · Tongliang Liu -
2023 Poster: Subclass-Dominant Label Noise: A Counterexample for the Success of Early Stopping »
Yingbin Bai · Zhongyi Han · Erkun Yang · Jun Yu · Bo Han · Dadong Wang · Tongliang Liu -
2023 Poster: Combating Representation Learning Disparity with Geometric Harmonization »
Zhihan Zhou · Jiangchao Yao · Feng Hong · Yanfeng Wang · Bo Han · Ya Zhang -
2023 Poster: Efficient Adversarial Contrastive Learning via Robustness-Aware Coreset Selection »
Xilie Xu · Jingfeng ZHANG · Feng Liu · Masashi Sugiyama · Mohan Kankanhalli -
2023 Poster: Understanding and Improving Feature Learning for Out-of-Distribution Generalization »
Yongqiang Chen · Wei Huang · Kaiwen Zhou · Yatao Bian · Bo Han · James Cheng -
2023 Poster: Combating Bilateral Edge Noise for Robust Link Prediction »
Zhanke Zhou · Jiangchao Yao · Jiaxu Liu · Xiawei Guo · Quanming Yao · LI He · Liang Wang · Bo Zheng · Bo Han -
2023 Poster: A Graph-Theoretic Framework for Understanding Open-World Representation Learning »
Yiyou Sun · Zhenmei Shi · Yixuan Li -
2023 Poster: Diversified Outlier Exposure for Out-of-Distribution Detection via Informative Extrapolation »
Jianing Zhu · Yu Geng · Jiangchao Yao · Tongliang Liu · Gang Niu · Masashi Sugiyama · Bo Han -
2023 Poster: Learning to Augment Distributions for Out-of-distribution Detection »
Qizhou Wang · Zhen Fang · Yonggang Zhang · Feng Liu · Yixuan Li · Bo Han -
2023 Poster: Invariant Learning via Probability of Sufficient and Necessary Causes »
Mengyue Yang · Yonggang Zhang · Zhen Fang · Yali Du · Furui Liu · Jean-Francois Ton · Jianhong Wang · Jun Wang -
2023 Poster: Does Invariant Graph Learning via Environment Augmentation Learn Invariance? »
Yongqiang Chen · Yatao Bian · Kaiwen Zhou · Binghui Xie · Bo Han · James Cheng -
2023 Poster: Out-of-distribution Detection Learning with Unreliable Out-of-distribution Sources »
Haotian Zheng · Qizhou Wang · Zhen Fang · Xiaobo Xia · Feng Liu · Tongliang Liu · Bo Han -
2022 Spotlight: Lightning Talks 6A-4 »
Xiu-Shen Wei · Konstantina Dritsa · Guillaume Huguet · ABHRA CHAUDHURI · Zhenbin Wang · Kevin Qinghong Lin · Yutong Chen · Jianan Zhou · Yongsen Mao · Junwei Liang · Jinpeng Wang · Mao Ye · Yiming Zhang · Aikaterini Thoma · H.-Y. Xu · Daniel Sumner Magruder · Enwei Zhang · Jianing Zhu · Ronglai Zuo · Massimiliano Mancini · Hanxiao Jiang · Jun Zhang · Fangyun Wei · Faen Zhang · Ioannis Pavlopoulos · Zeynep Akata · Xiatian Zhu · Jingfeng ZHANG · Alexander Tong · Mattia Soldan · Chunhua Shen · Yuxin Peng · Liuhan Peng · Michael Wray · Tongliang Liu · Anjan Dutta · Yu Wu · Oluwadamilola Fasina · Panos Louridas · Angel Chang · Manik Kuchroo · Manolis Savva · Shujie LIU · Wei Zhou · Rui Yan · Gang Niu · Liang Tian · Bo Han · Eric Z. XU · Guy Wolf · Yingying Zhu · Brian Mak · Difei Gao · Masashi Sugiyama · Smita Krishnaswamy · Rong-Cheng Tu · Wenzhe Zhao · Weijie Kong · Chengfei Cai · WANG HongFa · Dima Damen · Bernard Ghanem · Wei Liu · Mike Zheng Shou -
2022 Spotlight: Adversarial Training with Complementary Labels: On the Benefit of Gradually Informative Attacks »
Jianan Zhou · Jianing Zhu · Jingfeng ZHANG · Tongliang Liu · Gang Niu · Bo Han · Masashi Sugiyama -
2022 Spotlight: Lightning Talks 5B-3 »
Yanze Wu · Jie Xiao · Nianzu Yang · Jieyi Bi · Jian Yao · Yiting Chen · Qizhou Wang · Yangru Huang · Yongqiang Chen · Peixi Peng · Yuxin Hong · Xintao Wang · Feng Liu · Yining Ma · Qibing Ren · Xueyang Fu · Yonggang Zhang · Kaipeng Zeng · Jiahai Wang · GEN LI · Yonggang Zhang · Qitian Wu · Yifan Zhao · Chiyu Wang · Junchi Yan · Feng Wu · Yatao Bian · Xiaosong Jia · Ying Shan · Zhiguang Cao · Zheng-Jun Zha · Guangyao Chen · Tianjun Xiao · Han Yang · Jing Zhang · Jinbiao Chen · MA Kaili · Yonghong Tian · Junchi Yan · Chen Gong · Tong He · Binghui Xie · Yuan Sun · Francesco Locatello · Tongliang Liu · Yeow Meng Chee · David P Wipf · Tongliang Liu · Bo Han · Bo Han · Yanwei Fu · James Cheng · Zheng Zhang -
2022 Spotlight: Watermarking for Out-of-distribution Detection »
Qizhou Wang · Feng Liu · Yonggang Zhang · Jing Zhang · Chen Gong · Tongliang Liu · Bo Han -
2022 Spotlight: Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs »
Yongqiang Chen · Yonggang Zhang · Yatao Bian · Han Yang · MA Kaili · Binghui Xie · Tongliang Liu · Bo Han · James Cheng -
2022 Spotlight: Lightning Talks 4A-2 »
Barakeel Fanseu Kamhoua · Hualin Zhang · Taiki Miyagawa · Tomoya Murata · Xin Lyu · Yan Dai · Elena Grigorescu · Zhipeng Tu · Lijun Zhang · Taiji Suzuki · Wei Jiang · Haipeng Luo · Lin Zhang · Xi Wang · Young-San Lin · Huan Xiong · Liyu Chen · Bin Gu · Jinfeng Yi · Yongqiang Chen · Sandeep Silwal · Yiguang Hong · Maoyuan Song · Lei Wang · Tianbao Yang · Han Yang · MA Kaili · Samson Zhou · Deming Yuan · Bo Han · Guodong Shi · Bo Li · James Cheng -
2022 Spotlight: Exact Shape Correspondence via 2D graph convolution »
Barakeel Fanseu Kamhoua · Lin Zhang · Yongqiang Chen · Han Yang · MA Kaili · Bo Han · Bo Li · James Cheng -
2022 Spotlight: RSA: Reducing Semantic Shift from Aggressive Augmentations for Self-supervised Learning »
Yingbin Bai · Erkun Yang · Zhaoqing Wang · Yuxuan Du · Bo Han · Cheng Deng · Dadong Wang · Tongliang Liu -
2022 Workshop: Robustness in Sequence Modeling »
Nathan Ng · Haoran Zhang · Vinith Suriyakumar · Chantal Shaib · Kyunghyun Cho · Yixuan Li · Alice Oh · Marzyeh Ghassemi -
2022 Poster: Watermarking for Out-of-distribution Detection »
Qizhou Wang · Feng Liu · Yonggang Zhang · Jing Zhang · Chen Gong · Tongliang Liu · Bo Han -
2022 Poster: Exact Shape Correspondence via 2D graph convolution »
Barakeel Fanseu Kamhoua · Lin Zhang · Yongqiang Chen · Han Yang · MA Kaili · Bo Han · Bo Li · James Cheng -
2022 Poster: Counterfactual Fairness with Partially Known Causal Graph »
Aoqi Zuo · Susan Wei · Tongliang Liu · Bo Han · Kun Zhang · Mingming Gong -
2022 Poster: SIREN: Shaping Representations for Detecting Out-of-Distribution Objects »
Xuefeng Du · Gabriel Gozum · Yifei Ming · Yixuan Li -
2022 Poster: Class-Dependent Label-Noise Learning with Cycle-Consistency Regularization »
De Cheng · Yixiong Ning · Nannan Wang · Xinbo Gao · Heng Yang · Yuxuan Du · Bo Han · Tongliang Liu -
2022 Poster: Synergy-of-Experts: Collaborate to Improve Adversarial Robustness »
Sen Cui · Jingfeng ZHANG · Jian Liang · Bo Han · Masashi Sugiyama · Changshui Zhang -
2022 Poster: Pluralistic Image Completion with Gaussian Mixture Models »
Xiaobo Xia · Wenhao Yang · Jie Ren · Yewen Li · Yibing Zhan · Bo Han · Tongliang Liu -
2022 Poster: Delving into Out-of-Distribution Detection with Vision-Language Representations »
Yifei Ming · Ziyang Cai · Jiuxiang Gu · Yiyou Sun · Wei Li · Yixuan Li -
2022 Poster: OpenOOD: Benchmarking Generalized Out-of-Distribution Detection »
Jingkang Yang · Pengyun Wang · Dejian Zou · Zitang Zhou · Kunyuan Ding · WENXUAN PENG · Haoqi Wang · Guangyao Chen · Bo Li · Yiyou Sun · Xuefeng Du · Kaiyang Zhou · Wayne Zhang · Dan Hendrycks · Yixuan Li · Ziwei Liu -
2021 : Uncovering the Deep Unknowns of ImageNet Model: Challenges and Opportunties »
Yixuan Li -
2021 Poster: Understanding and Improving Early Stopping for Learning with Noisy Labels »
Yingbin Bai · Erkun Yang · Bo Han · Yanhua Yang · Jiatong Li · Yinian Mao · Gang Niu · Tongliang Liu -
2021 Poster: On the Importance of Gradients for Detecting Distributional Shifts in the Wild »
Rui Huang · Andrew Geng · Yixuan Li -
2021 Poster: Can multi-label classification networks know what they don’t know? »
Haoran Wang · Weitang Liu · Alex Bocchieri · Yixuan Li -
2021 Poster: Universal Semi-Supervised Learning »
Zhuo Huang · Chao Xue · Bo Han · Jian Yang · Chen Gong -
2021 Poster: Probabilistic Margins for Instance Reweighting in Adversarial Training »
qizhou wang · Feng Liu · Bo Han · Tongliang Liu · Chen Gong · Gang Niu · Mingyuan Zhou · Masashi Sugiyama -
2021 Poster: Meta Two-Sample Testing: Learning Kernels for Testing with Limited Data »
Feng Liu · Wenkai Xu · Jie Lu · Danica J. Sutherland -
2021 Poster: ReAct: Out-of-distribution Detection With Rectified Activations »
Yiyou Sun · Chuan Guo · Yixuan Li -
2021 Poster: Instance-dependent Label-noise Learning under a Structural Causal Model »
Yu Yao · Tongliang Liu · Mingming Gong · Bo Han · Gang Niu · Kun Zhang -
2021 Poster: TOHAN: A One-step Approach towards Few-shot Hypothesis Adaptation »
Haoang Chi · Feng Liu · Wenjing Yang · Long Lan · Tongliang Liu · Bo Han · William Cheung · James Kwok -
2020 Poster: Energy-based Out-of-distribution Detection »
Weitang Liu · Xiaoyun Wang · John Owens · Yixuan Li