PaperlayerView exact revision on arXiv

Source-linked AI summary

Is Out-of-Distribution Detection Learnable?

Zhen Fang, Yixuan Li, Jie Lu, Jiahua Dong, Bo Han, Feng Liu

arXiv:2210.14707v3cs.LGstat.ML

TL;DR

OOD detection must generalize from ID-only training data to diverse, unknown OOD distributions, raising whether it is PAC learnable. The paper develops a PAC theory, proves impossibility results and necessary conditions, and characterizes learnability in practical scenarios. It concludes that no universally consistent algorithm should be expected, while learnability remains possible under scenario-specific conditions.

  • Problem

    The paper asks whether OOD detection is PAC learnable when OOD data are unavailable, diverse, and priori-unknown.

  • Method

    The paper develops a PAC framework relating OOD learnability to domain and hypothesis spaces, then analyzes representative spaces and neural-network settings.

  • Results

    The paper derives a necessary condition, proves impossibility theorems in some spaces, and gives necessary and sufficient conditions for learnability in practical scenarios.

  • Takeaways & Limitations

    OOD detection can be learnable in certain scenarios, but the theory does not support expecting one universally consistent algorithm across all scenarios.

  • Takeaways & Limitations

    Near-OOD detection may be unlearnable under overlap conditions, and its feasibility remains an open question.

Abstract

from arXiv · show

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.

1 Introduction

OOD detection addresses test distributions containing unseen classes, but its learnability is unclear because OOD data are unavailable, diverse, and unknown during training. This paper develops PAC learning theory to identify when OOD detection can generalize and when it cannot.

  • OOD detection jointly identifies whether inputs are ID or OOD and classifies ID inputs into their respective classes.
  • The paper asks whether OOD detection is PAC learnable despite diverse, priori-unknown OOD data.
  • The theory studies how domain and hypothesis spaces must relate to make OOD detection learnable, rather than assuming distribution-free learnability.
  • In the total space, overlap can invalidate the necessary condition and yield an impossibility theorem; the separate space also remains unlearnable under some conditions.
  • The paper derives necessary and sufficient conditions in practical spaces, including an iff finite-feature-space condition for FCNNs in the separate space.
  • The theory supports representative OOD methods, explains learnability in far-OOD image scenarios, and indicates that different scenarios require different algorithms.

2 Learning Setups

The framework formalizes OOD detection as learning from ID data while testing on mixtures of ID and OOD distributions. It distinguishes ordinary and strong learnability and focuses on prior-unknown spaces, where learnability depends on the domain and hypothesis spaces.

  • Training uses ID samples, while testing combines ID and OOD distributions and requires both correct ID classification and OOD detection.
  • OOD data are assigned to one aggregate OOD class, and domains are mixtures of ID and OOD joint distributions.
  • The hypothesis framework includes multiclass ID/OOD classifiers, binary ID-versus-OOD classifiers, and scoring functions.
  • Learnability asks whether an algorithm returns hypotheses whose risk approaches the minimum as sample size increases.
  • Strong learnability additionally addresses unknown ID/OOD class-prior imbalance, and it is equivalent to learnability in prior-unknown spaces.
  • Unlike supervised agnostic PAC learning, OOD learnability is not distribution-free and depends on the relationship between domain and hypothesis spaces.

3 Learning in Priori-unknown Spaces

The paper introduces prior-unknown spaces to connect ordinary and strong OOD learnability and analyzes several representative domain spaces. Figure 1 motivates a linear condition by contrasting approximation under overlapping and separate ID/OOD supports.

  • A prior-unknown space contains every reweighted mixture of each domain, and in such spaces ordinary and strong learnability are equivalent.
  • Theorem 1 allows analysis to focus on prior-unknown spaces while preserving learnability through an enlarged domain space.
  • The representative spaces include single-distribution, total, separate, finite-ID-distribution, and density-based spaces.
  • In overlapping scenarios, straight estimated-risk lines cannot approximate the solid polyline, implying unlearnability; without overlap, straight lines may approximate the solid line.
  • These spaces correspond to practical settings such as finite ID datasets and discrete or continuous distributions defined through a measure.

4 Impossibility Theorems for OOD Detection

The paper derives a necessary linear condition for OOD learnability, then shows that broad settings can be impossible even when ID and OOD distributions are separated. Finite VC dimension alone does not guarantee learnability in the separate space.

  • Condition 1 is necessary and sufficient for OOD learnability in a single-distribution space and necessary in prior-unknown spaces.
  • Overlap between ID and OOD distributions can violate Condition 1, making OOD detection unlearnable in the total space.
  • Even in the separate space, OOD detection is unlearnable when Assumption 1 holds, VCdim(φ ◦H) is finite, and classifiers can label infinitely many inputs as ID.
  • Finite VC dimension, which normally supports supervised-learning learnability, cannot by itself guarantee OOD-detection learnability in the separate space.

5 When OOD Detection Can Be Successful

The paper identifies conditions under which OOD detection becomes learnable in practical spaces, including finite domains, compatible hypotheses, realizability, and suitable model capacity. In the finite-ID-distribution space, compatibility is necessary and sufficient.

  • For separate spaces, learnability requires either infinite VC dimension or a finite maximum number of inputs classified as ID.
  • When |X| < +∞, Assumption 1 holds, and the constant ID function belongs to H, OOD detection is learnable for the one-class case.
  • For multi-class detection, a binary ID/OOD classifier can be combined with an ID classifier, provided the hypothesis and loss spaces satisfy the stated conditions.
  • In the finite-ID-distribution space, OOD detection is learnable if and only if the compatibility condition holds.The setting assumes that X is bounded, and the consistency rate can attain O(1/...).
  • In density-based spaces, realizability together with finite Natarajan dimension yields learnability, and realizability can be necessary and sufficient in some practical scenarios.

6 Connecting Theory to Practice

The paper applies its theory to FCNN-based and score-based OOD detectors. In separate spaces, finite feature spaces characterize learnability for these model classes, while overlap still prevents learnability in the one-class case.

  • The theory provides support for representative scoring functions and FCNN-based methods in separate spaces and, under additional conditions, density-based spaces.
  • The notation q ≲ q′ compares FCNN architectures by depth, corresponding layer widths, and penultimate-layer width.
  • Score-based detection classifies an input as ID when its scoring function output reaches at least threshold λ, and as OOD otherwise.
  • For FCNN-based or score-based hypothesis spaces, OOD detection is learnable in the separate space if and only if |X| < +∞.
  • When K = 1, overlap between ID and OOD distributions is sufficient for unlearnability in FCNN-based and score-based spaces.
  • When K > 1, overlap between ID classes may allow learnability in special cases, unlike the one-class setting.

7 Discussion

The discussion applies the theory to far-OOD, near-OOD, and one-class novelty detection. It identifies learnable far-OOD settings, possible non-learnability for near-OOD, and model-capacity or realizability requirements for one-class detection.

  • Understanding Far-OOD Detection: Under appropriate hypothesis spaces, τ-far-OOD detection is learnable.When the ID hypothesis class is agnostic PAC learnable and X is compact, KNN-based OOD detection is consistent in the τ-far-OOD case.
  • Understanding Far-OOD Detection: For τ-far-OOD detection, compactness of X can replace the separate-space requirement that |X| be finite.
  • Understanding Near-OOD Detection: Near-OOD tasks may be unlearnable when similar semantics or styles imply overlap between ID and OOD distributions.Developing a theory for the feasibility of near-OOD detection remains an open question.
  • Understanding One-class Novelty Detection: One-class novelty detection in the separate space requires a large-capacity model for good generalization.The theory also suggests avoiding ID/OOD overlap or considering multi-class OOD detection when overlap cannot be avoided.
  • Understanding One-class Novelty Detection: In density-based spaces, one-class OOD detection requires a hypothesis space satisfying the Realizability Assumption.A large-capacity model can generally help ensure that assumption holds.

8 Related Work

The related-work discussion distinguishes this PAC theory from OOD detection theory, open-set learning, reject-option classification, robust statistics, and PQ learning. The paper’s distinction is its focus on PAC learnability without requiring test or OOD data during training and its attention to both ID and OOD risks.

  • OOD Detection Theory: The paper focuses on PAC learnability of OOD detection, whereas prior OOD theory studies goodness-of-fit, typical-set assumptions, or provable algorithm design.
  • Open-set Learning Theory: Existing open-set detection and domain-adaptation bounds require test data during training, while other work without test access uses strong and impractical assumptions.
  • Learning Theory for Classification with Reject Option: Classification-with-reject-option theories mainly analyze how rejection rules affect ID risk, whereas this theory also addresses OOD risk.
  • Robust Statistics: Robust statistics studies estimators and testers that mitigate outlier effects and has established statistical limits through impossibility results.
  • PQ Learning Theory: PQ learning can represent PAC theory for OOD detection when test data are available during training, while this theory also studies cases beyond the Realizability Assumption.

9 Conclusions and Future Works

The paper provides a PAC theory for OOD detection and shows that universal consistency is impossible across all scenarios. It also identifies practical scenarios where necessary and sufficient learnability conditions exist.

  • The paper provides a PAC theory for OOD detection and identifies necessary and sufficient conditions for learnability.
  • A universally consistent OOD detection algorithm cannot be expected to handle all scenarios.
  • When only finite ID datasets are available, Theorem 8 provides a necessary and sufficient condition for successful OOD detection.
  • The authors identify robustness of OOD detection based on robust statistics as future work.

Checklist

The checklist records complete assumptions and proofs for theoretical results, while experiments and asset-related items are marked not applicable. It also documents related OOD detection methods and theoretical settings.

  • Theoretical results: The paper reports that it states the full assumptions and includes complete proofs for all theoretical results.
  • Experiments: Experimental reporting items, including training details, error bars, and compute resources, are marked not applicable.
  • Assets and ethics: Asset, consent, participant-risk, and compensation items are marked not applicable, while the paper reports discussing limitations and potential negative societal impacts.
  • OOD detection methods: The related-work material covers classification-based, density-based, outlier-exposure, and generated-OOD detection methods.
  • Related theory: The paper distinguishes its setting from prior theories involving test-data access, rejection rules, robust statistics, or realizability assumptions.

B Limitations and Potential Negative Societal Impacts

The paper does not answer the most general PAC-learnability question for arbitrary hypothesis and domain spaces. It instead presents a conjecture for future work and reports no negative societal impacts for this theoretical study.

  • Limitations: The main limitation is that the paper does not establish necessary and sufficient conditions for arbitrary hypothesis and domain spaces.The authors leave this most general question open because it remains difficult to address.
  • Limitations: The paper conjectures that compatibility is equivalent to OOD learnability when the hypothesis space is agnostic learnable for supervised learning.This statement is presented as a conjecture rather than a proved result.
  • Potential Negative Societal Impacts: The paper reports no potential negative societal impacts because it is theoretical and studies OOD detection for machine-learning safety.This statement concerns the authors’ assessment of societal impacts, not an empirical safety evaluation.
  • Scope of Results: The theory establishes impossibility results in total and separate spaces, while identifying finite-feature-space conditions for learnability in some separate-space settings.These results include non-learnability for any non-trivial hypothesis space in the total space and finite-feature-space conditions under specified hypothesis classes.

F Proof of Theorem 2

The proof establishes that Condition 1 is necessary and sufficient for learnability in the single-distribution space, then shows overlap can violate it and make total-space OOD detection impossible.

  • Necessary conditions: Conditions 1 and 4 are necessary for OOD learnability in a priori-unknown spaces.Condition 4 generalizes the linear condition to OOD convex decompositions and reduces to Condition 1 when l = 1.
  • Single-distribution learnability: In the single-distribution space, OOD detection is learnable if and only if Condition 1 holds.The proof combines necessity from Lemma 1 with sufficiency via the infimum-risk characterization in Lemma 2.
  • Overlap obstruction: If an ID and OOD distribution overlap and the optimal ID risk is zero, Condition 1 fails, so OOD detection is not learnable.The overlap construction forces positive mixed risk for every hypothesis at intermediate mixture weights.
  • Total-space impossibility: In the total space, OOD detection is impossible whenever the binary image φ ◦ H contains more than one hypothesis.A non-trivial hypothesis space can assign conflicting ID and OOD labels to the same point, creating overlapping distributions with zero separate risks.

H Proof of Theorem 5

The proof derives impossibility in the separate space under finite VC dimension and unbounded ID support, then establishes learnability in several finite or structurally restricted settings.

  • Separate-space impossibility: For finite discrete domains satisfying the separate-space assumption, positive optimal risk implies OOD detection is not learnable.The argument uses the multi-linear necessary condition and constructs a finite-support domain violating it.
  • Separate-space impossibility: If the separate-space assumption holds, VCdim(φ ◦ H) is finite, and hypotheses can label infinitely many ID points, OOD detection is not learnable.The result follows by combining the capacity condition with the finite-domain impossibility lemma.
  • Finite-domain characterization: For finite X with K = 1, learnability holds exactly when the hypothesis space contains every binary classifier except the constant OOD function.The constant ID function must be present, while the remaining required classifiers are characterized by Hall − {hout} ⊂ H.
  • Other learnable spaces: Finite-ID-distribution spaces can be learnable over equivalence classes, with learning rate O(1/n).This result is stated for bounded X and a hypothesis space satisfying the relevant condition.

J.2 Proof of Theorem 9

The proof of Theorem 9 constructs a consistent algorithm for density-based spaces by controlling ID and OOD risks under bounded densities and realizability.

  • Density-based setting: The density-based setting assumes each domain has a density bounded between 1/b and b relative to a base measure.This defines the prior-unknown space used in the theorem.
  • Risk control: The proof reduces learnability to comparing risks under the mixture measure and the ground-truth labeling function.It uses realizability to identify the optimal mixture risk and bounds the hypothesis risk around it.
  • Consistency and rate: Uniform complexity bounds yield a consistent algorithm whose convergence rate can attain O(1/n).The construction selects a consistent sequence of algorithms using empirical-risk and dimension-based bounds.
  • General loss: The argument extends from zero-one loss to the paper’s general loss through equivalence of the corresponding realizability assumptions.A constant-factor comparison between losses transfers consistency from the zero-one case.

L Proof of Theorem 10

The proof shows that FCNN- and score-based hypothesis spaces can learn OOD detection in the separate space on finite domains, whereas infinite domains remain impossible under the stated conditions.

  • FCNN capacity: ReLU FCNN hypothesis spaces have finite VC dimension, supporting application of the separate-space impossibility and learnability theorems.The finite-VC result follows from standard feed-forward-network VC-dimension theory within the paper’s argument.
  • Finite domains: On finite X, sufficiently expressive FCNNs can represent all required binary classifiers and yield learnable OOD detection.The construction uses finite-domain representation results and contains all binary classifiers in the induced hypothesis space.
  • Score-based spaces: For score-based spaces, nonempty threshold regions and Condition 2 allow construction of a network architecture that learns in the separate space on finite X.The result holds for architectures at least as expressive as the constructed sequence.
  • Finite-versus-infinite domains: For FCNN- or score-based hypothesis spaces, finite X is necessary and sufficient for learnability in the separate space under the theorem’s assumptions.When X is infinite, the hypotheses can label unboundedly many ID points, triggering the separate-space impossibility theorem.
  • Overlap obstruction: If a score-based hypothesis space contains an overlapping ID/OOD domain, OOD detection is not learnable there.This directly instantiates the overlap obstruction for score-based hypotheses.
Loading 2210.14707v3…