CoChat
Sign Up
Cited by 61Adversarial Robustness in Machine LearningAnomaly Detection Techniques and ApplicationsMachine Learning and Data Classification

Is Out-Of-Distribution Detection Learnable?

Open access
Fang, Zhen, Li, Yixuan, Lu, Jie, Dong, Jiahua, Han, Bo, Liu, Feng·2022·Advances in Neural Information Processing Systems 35
DOI 10.52202/068431-2696
Open this paper in CoChat — free accountOpen PDF

Abstract

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

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.52202/068431-2696

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Learning an OOD model is difficult and may be impossible in certain situations.

    “Recent research shows that learning an OOD model is a difficult problem to solve and may even prove to be impossible in certain situations (Zhang et al., 2021;Fang et al., 2022).”

    From Novelty Detection in Reinforcement Learning with World Models (2023) · cites this paper as Fang et al., 2022

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 78

  1. [1][1] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR , 2021. -
  2. [2][2] Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In CVPR , 2017. -
  3. [3][3] Yen-Chang Hsu, Yilin Shen, Hongxia Jin, and Zsolt Kira. Generalized ODIN: detecting out-of-distribution image without learning from out-of-distribution data. In CVPR , 2020. -
  4. [4][4] Jingkang Yang, Kaiyang Zhou, Yixuan Li, and Ziwei Liu. Generalized out-of-distribution detection: A survey. CoRR , abs/2110.11334, 2021. - · arXiv
  5. [5][5] Abhijit Bendale and Terrance E Boult. Towards open set deep networks. In CVPR , 2016. -
  6. [6][6] Jiefeng Chen, Yixuan Li, Xi Wu, Yingyu Liang, and Somesh Jha. Atom: Robustifying out-ofdistribution detection using outlier mining. ECML , 2021. -
  7. [7][7] Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of-distribution examples in neural networks. In ICLR , 2017. -
  8. [8][8] Shiyu Liang, Yixuan Li, and R. Srikant. Enhancing the reliability of out-of-distribution image detection in neural networks. In ICLR , 2018. -
  9. [9][9] Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting out-of-distribution samples and adversarial attacks. In NeurIPS , 2018. -
  10. [10][10] Bo Zong, Qi Song, Martin Renqiang Min, Wei Cheng, Cristian Lumezanu, Dae-ki Cho, and Haifeng Chen. Deep autoencoding gaussian mixture model for unsupervised anomaly detection. In ICLR , 2018. -
  11. [11][11] Stanislav Pidhorskyi, Ranya Almohsen, and Gianfranco Doretto. Generative probabilistic novelty detection with adversarial autoencoders. In NeurIPS , 2018. -
  12. [12][12] Eric T. Nalisnick, Akihiro Matsukawa, Yee Whye Teh, Dilan G¨ or¨ ur, and Balaji Lakshminarayanan. Do deep generative models know what they don't know? In ICLR , 2019. -
  13. [13][13] Dan Hendrycks, Mantas Mazeika, and Thomas G. Dietterich. Deep anomaly detection with outlier exposure. In ICLR , 2019. -
  14. [14][14] Jie Ren, Peter J. Liu, Emily Fertig, Jasper Snoek, Ryan Poplin, Mark A. DePristo, Joshua V. Dillon, and Balaji Lakshminarayanan. Likelihood ratios for out-of-distribution detection. In NeurIPS , 2019. -
  15. [15][15] Ziqian Lin, Sreya Dutta Roy, and Yixuan Li. Mood: Multi-level out-of-distribution detection. In CVPR , 2021. -
  16. [16][16] Mohammadreza Salehi, Hossein Mirzaei, Dan Hendrycks, Yixuan Li, Mohammad Hossein Rohban, and Mohammad Sabokrou. A unified survey on anomaly, novelty, open-set, and out-of-distribution detection: Solutions and future challenges. arXiv preprint arXiv:2110.14051 , 2021. - · arXiv
  17. [17][17] Yiyou Sun, Chuan Guo, and Yixuan Li. React: Out-of-distribution detection with rectified activations. In NeurIPS , 2021. -
  18. [18][18] Rui Huang, Andrew Geng, and Yixuan Li. On the Importance of Gradients for Detecting Distributional Shifts in the Wild. In NeurIPS , 2021. -
  19. [19][19] Stanislav Fort, Jie Ren, and Balaji Lakshminarayanan. Exploring the Limits of Out-ofDistribution Detection. In NeurIPS , 2021. -
  20. [20][20] Yifei Ming, Hang Yin, and Yixuan Li. On the impact of spurious correlation for out-ofdistribution detection. AAAI , 2022. -
  21. [21][21] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms . Cambridge university press, 2014. -
  22. [22][22] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning . MIT press, 2018. -
  23. [23][23] Weitang Liu, Xiaoyun Wang, John D. Owens, and Yixuan Li. Energy-based out-of-distribution detection. In NeurIPS , 2020. -
  24. [24][24] Zhen Fang, Jie Lu, Anjin Liu, Feng Liu, and Guangquan Zhang. Learning bounds for open-set learning. In ICML , 2021. -
  25. [25][25] Guangyao Chen, Peixi Peng, Xiangqian Wang, and Yonghong Tian. Adversarial reciprocal points learning for open set recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence , 2021. -
  26. [26][26] Lukas Ruff, Nico G¨ ornitz, Lucas Deecke, Shoaib Ahmed Siddiqui, Robert A. Vandermeulen, Alexander Binder, Emmanuel M¨ uller, and Marius Kloft. Deep one-class classification. In ICML , 2018. -
  27. [27][27] Sachin Goyal, Aditi Raghunathan, Moksh Jain, Harsha Vardhan Simhadri, and Prateek Jain. DROCC: deep robust one-class classification. In ICML , 2020. -
  28. [28][28] Lucas Deecke, Robert A. Vandermeulen, Lukas Ruff, Stephan Mandt, and Marius Kloft. Image anomaly detection with generative adversarial networks. In ECML , 2018. -
  29. [29][29] Z. Fang, Jie Lu, F. Liu, Junyu Xuan, and G. Zhang. Open set domain adaptation: Theoretical bound and algorithm. IEEE Transactions on Neural Networks and Learning Systems , 2020. -
  30. [31][31] Guangyao Chen, Limeng Qiao, Yemin Shi, Peixi Peng, Jia Li, Tiejun Huang, Shiliang Pu, and Yonghong Tian. Learning open set network with discriminative reciprocal points. ICCV , 2020. -
  31. [32][32] Jiefeng Chen, Yixuan Li, Xi Wu, Yingyu Liang, and Somesh Jha. Informative outlier matters: Robustifying out-of-distribution detection using outlier mining. ICML Workshop , 2020. -
  32. [33][33] Jiefeng Chen, Yixuan Li, Xi Wu, Yingyu Liang, and Somesh Jha. Robust out-of-distribution detection for neural networks. arXiv preprint arXiv:2003.09711 , 2020. - · arXiv
  33. [34][34] Wentao Bao, Qi Yu, and Yu Kong. Evidential deep learning for open set action recognition. ICCV , 2021. -
  34. [35][35] Wentao Bao, Qi Yu, and Yu Kong. Opental: Towards open set temporal action localization. CVPR , 2022. -
  35. [36][36] Donald L Cohn. Measure theory . Springer, 2013. -
  36. [37][37] Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vcdimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research , 20(63):1-17, 2019. -
  37. [38][38] Marek Karpinski and Angus Macintyre. Polynomial bounds for VC dimension of sigmoidal and general pfaffian neural networks. J. Comput. Syst. Sci. , 54(1):169-176, 1997. -
  38. [39][39] Jingkang Yang, Kaiyang Zhou, and Ziwei Liu. Full-spectrum out-of-distribution detection. CoRR , 2022. -
  39. [40][40] Li Deng. The MNIST database of handwritten digit images for machine learning research [best of the web]. IEEE Signal Process. Mag. , 2012. -
  40. [43][43] Bolei Zhou, ` Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: A 10 million image database for scene recognition. IEEE Trans. Pattern Anal. Mach. Intell. , 2018. -
  41. [44][44] Yiyou Sun, Yifei Ming, Xiaojin Zhu, and Yixuan Li. Out-of-distribution detection with deep nearest neighbors. In ICML , 2022. -
  42. [45][45] Jie Ren, Stanislav Fort, Jeremiah Liu, Abhijit Guha Roy, Shreyas Padhy, and Balaji Lakshminarayanan. A simple fix to mahalanobis distance for improving near-ood detection. CoRR , abs/2106.09022, 2021. - · arXiv
  43. [46][46] Stanislav Fort, Jie Ren, and Balaji Lakshminarayanan. Exploring the limits of out-of-distribution detection. In NeurIPS , 2021. -
  44. [49][49] Lily H. Zhang, Mark Goldstein, and Rajesh Ranganath. Understanding failures in out-ofdistribution detection with deep generative models. In ICML , 2021. -
  45. [50][50] Peyman Morteza and Yixuan Li. Provable guarantees for understanding out-of-distribution detection. AAAI , 2022. -
  46. [51][51] Si Liu, Risheek Garrepalli, Thomas G. Dietterich, Alan Fern, and Dan Hendrycks. Open category detection with PAC guarantees. In ICML , 2018. -
  47. [52][52] Yadan Luo, Zijian Wang, Zi Huang, and Mahsa Baktashmotlagh. Progressive graph learning for open-set domain adaptation. In ICML , 2020. -
  48. [53][53] C. K. Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory , 1970. -
  49. [54][54] Vojtech Franc, Daniel Pr˚ uˇ sa, and V . V oracek. Optimal strategies for reject option classifiers. CoRR , abs/2101.12523, 2021. - · arXiv
  50. [56][56] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Boosting with abstention. In NeurIPS , 2016. -
  51. [57][57] Chenri Ni, Nontawat Charoenphakdee, Junya Honda, and Masashi Sugiyama. On the calibration of multiclass classification with rejection. In NeurIPS , 2019. -
  52. [58][58] Nontawat Charoenphakdee, Zhenghang Cui, Yivan Zhang, and Masashi Sugiyama. Classification with rejection based on cost-sensitive classification. In ICML , 2021. -
  53. [59][59] Peter L. Bartlett and Marten H. Wegkamp. Classification with a reject option using a hinge loss. Journal of Machine Learning Research , 2008. -
  54. [60][60] Peter J Rousseeuw, Frank R Hampel, Elvezio M Ronchetti, and Werner A Stahel. Robust statistics: the approach based on influence functions . John Wiley & Sons, 2011. -
  55. [61][61] Elvezio M Ronchetti and Peter J Huber. Robust statistics . John Wiley & Sons, 2009. -
  56. [62][62] Ilias Diakonikolas, Daniel M. Kane, and Ankit Pensia. Outlier robust mean estimation with subgaussian rates via stability. In NeurIPS , 2020. -
  57. [63][63] Ilias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Eric Price, and Alistair Stewart. Outlierrobust high-dimensional sparse estimation via iterative filtering. In NeurIPS , 2019. -
  58. [64][64] Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, and Yuxin Sun. Outlier-robust learning of ising models under dobrushin's condition. In COLT , 2021. -
  59. [65][65] Yu Cheng, Ilias Diakonikolas, Daniel M Kane, Rong Ge, Shivam Gupta, and Mahdi Soltanolkotabi. Outlier-robust sparse estimation via non-convex optimization. In NeurIPS , 2021. -
  60. [66][66] Ilias Diakonikolas, Daniel M Kane, Jasper CH Lee, and Ankit Pensia. Outlier-robust sparse mean estimation for heavy-tailed distributions. In NeurIPS , 2022. -
  61. [67][67] Shafi Goldwasser, Adam Tauman Kalai, Yael Kalai, and Omar Montasser. Beyond perturbations: Learning guarantees with arbitrary adversarial test examples. In NeurIPS , 2020. -
  62. [68][68] Adam Tauman Kalai and Varun Kanade. Efficient learning with arbitrary covariate shift. In ALT , Proceedings of Machine Learning Research, 2021. -
  63. [69][69] Ilias Diakonikolas and Daniel M. Kane. Recent advances in algorithmic high-dimensional robust statistics. A shorter version appears as an Invited Book Chapter in Beyond the Worst-Case Analysis of Algorithms , 2020. -
  64. [70][70] Akshay Raj Dhamija, Manuel G¨ unther, and Terrance E. Boult. Reducing network agnostophobia. In NeurIPS , pages 9175-9186, 2018. -
  65. [71][71] Haoran Wang, Weitang Liu, Alex Bocchieri, and Yixuan Li. Can multi-label classification networks know what they don't know? In NeurIPS , 2021. -
  66. [72][72] Diederik P. Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1x1 convolutions. In NeurIPS , 2018. -
  67. [73][73] Zhisheng Xiao, Qing Yan, and Yali Amit. Likelihood regret: An out-of-distribution detection score for variational auto-encoder. In NeurIPS , 2020. -
  68. [74][74] Alireza Zaeemzadeh, Niccol´ o Bisagno, Zeno Sambugaro, Nicola Conci, Nazanin Rahnavard, and Mubarak Shah. Out-of-distribution detection using union of 1-dimensional subspaces. In CVPR , 2021. -
  69. [75][75] Joost Van Amersfoort, Lewis Smith, Yee Whye Teh, and Yarin Gal. Uncertainty estimation using a single deep deterministic neural network. In ICML , 2020. -
  70. [76][76] Sachin Vernekar, Ashish Gaurav, Vahdat Abdelzad, Taylor Denouden, Rick Salay, and Krzysztof Czarnecki. Out-of-distribution detection in classifiers via generation. In NeurIPS Workshop , 2019. -
  71. [77][77] Ryuichi Kiryo, Gang Niu, Marthinus Christoffel du Plessis, and Masashi Sugiyama. Positiveunlabeled learning with non-negative risk estimator. In NeurIPS , 2017. -
  72. [78][78] Takashi Ishida, Gang Niu, and Masashi Sugiyama. Binary classification from positiveconfidence data. In NeurIPS , 2018. -
  73. [79][79] Shuo Chen, Gang Niu, Chen Gong, Jun Li, Jian Yang, and Masashi Sugiyama. Large-margin contrastive learning with distance polarization regularizer. In ICML , 2021. -
  74. [80][80] Jiahua Dong, Yang Cong, Gan Sun, Bineng Zhong, and Xiaowei Xu. What can be transferred: Unsupervised domain adaptation for endoscopic lesions segmentation. In CVPR , 2020. -
  75. [81][81] Zhen Fang, Jie Lu, Feng Liu, and Guangquan Zhang. Semi-supervised heterogeneous domain adaptation: Theory and algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence , 2022. -
  76. [82][82] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR , 2015. -
  77. [83][83] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Sch¨ olkopf, and Alexander J. Smola. A kernel two-sample test. Journal of Machine Learning Research , 2012. -
  78. [84][84] Itay Safran and Ohad Shamir. Depth-width tradeoffs in approximating natural functions with neural networks. In ICML , 2017. -

Cited by

Sorted by citations

Authors
Fang, Z., Li, Y., Lu, J., Dong, J., Han, B., & Liu, F.
Venue
Advances in Neural Information Processing Systems 35
Publisher
Neural Information Processing Systems Foundation, Inc. (NeurIPS)
Published
2022
Pages
37199-37213
ISSN
1049-5258 (ISSN-L)
DOI
10.52202/068431-2696
OpenAlex
W7133240830
Cited by
61
References
0
Citations by year
2026: 10 · 2025: 12 · 2024: 12 · 2023: 27
FWCI
7.05
Type
conference paper
Language
en
Open access
Locations
  • neural information processing systems (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Natural Science Foundation of China (62006202)
  • Young Scientists Fund
  • Air Force Office of Scientific Research
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Adversarial Robustness in Machine Learning
  • Physical Sciences › Computer Science › Artificial Intelligence › Anomaly Detection Techniques and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Data Classification
Keywords
out-of-distribution detection, learnability, generalization, anomaly detection, robustness

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review