acceptodds
Under review as a conference paper at ICLR 2027

The Moving Blind Spot in OOD Detection: Mixing Makes Universal Rates Uniform

Abstract

An out-of-distribution (OOD) detector learns from in-distribution (ID) data and is judged on a distribution it never observes. Problems sharing an ID law are indistinguishable and form an observation fiber, on which every learner is a schedule fixed in advance. The sample size is only a clock, and since a clock can run at any speed, a fiber admits every universal rate or none. We ask which, for errors against a detector class at all ID/OOD proportions. A fiber can be consistent without being uniformly learnable: each hidden law is eventually served, yet at every time some law is missed, a moving blind spot. Mixing hidden laws preserves consistency and the worst-case value of a fiber, yet our main theorem shows it turns universal rates into uniform ones: a learner attains a rate on the countable-mixture completion of a fiber exactly when it attains it uniformly. The key step, that consistency makes the class-relative optimal risk affine under mixing, holds verbatim for AUC and any criterion linear in the hidden law. Once hidden laws can be mixed, a moving blind spot admits no rate: one hidden law, condensing the blind spots of infinitely many times, defeats any candidate rate. Nontrivial rates arise only across fibers: selection costs an exponentially small error over finitely many ID laws, a sub-exponential one over countably many, and can defeat consistency over uncountably many, by Baire's theorem. With unrestricted detectors on measure-separated domains, all slowness is statistical, from an exact rate to none.

Primary area:
learning theory
Keywords:
out-of-distribution detection, novelty detection, statistical learning theory, universal learning, universal rates, learnability, consistency

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 2 reviews, above 9% of the others.
Reviewer_EuUJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies OOD detection when training data come from the ID distribution. The main result shows that for a chosen ID distribution, reaching a universal convergence rate over the countable-mixture completion of an OOD family is equivalent to attaining that rate uniformly over the original family. The paper also studies learning across different ID distributions and derives lower bounds using a single difficult distribution.

Critical strengths
  1. A connection between universal and uniform rates. For a fixed ID distribution, the main theorem shows that attaining a universal rate on the countable mixture completion of an OOD family is equivalent to attaining that rate uniformly over the original family. For each learner and proposed convergence rate, the paper constructs one fixed distribution on which that rate fails at infinitely many sample sizes. The difficult distribution remains the same as the sample size increases.
  2. A concrete correction to prior work. The counterexample to the necessity claim in Fang et al. is valuable as it identifies a gap between guarantees on expected risk for each domain and the existence of a single detector that performs well across domains.
Critical weaknesses
  1. The presentation hides the understanding of the paper. Despite many careful readings, I found the exposition from the abstract to the statistical problem until the results very difficult to follow. I recognize that formal definitions are present, but the accumulation of terms such as “fiber”, “clock”, “schedule”, "slowness", "blind spot", “window” are used from the abstract, together with metaphors such as " "every star is lit in time, yet every row keeps stars in the dark" are amusing but makes the reading very difficult. Moreover, for example, the statement that a family admits “every rate or none” needs a much clearer explanation. In the positive case, each target rate may require a different learning procedure. The paper should make this dependence more explicit and better explain how these procedures are constructed. The metaphor that “a clock can run at any speed” is amusing but does not in any way explain the mathematical argument.

  2. The extent of the main obstruction needs stronger motivation. Theorem 3.3 provides a link between universal and uniform rates under countable mixtures. However, the examples in Proposition 3.5 and Appendix D.6 both use detector classes that exclude a detector whose inclusion eliminates the obstruction. The paper acknowledges this and provides a useful compactness explanation but my remaining question is whether the same obstruction occurs in a detector class motivated independently of the construction.

Standard hypothesis classes in deep learning (e.g., neural networks with bounded weights and Lipschitz activations on bounded domains) typically enjoy relative compactness. Thus, it remains unclear to me whether the "moving blind spot" is an inherent barrier for realistic learning representations or an artifact of artificially non-compact families.

Overall assessment: Weak rejection. The paper contains very interesting theoretical results, including a precise rate equivalence and a valuable correction to prior work. However, I do not recommend acceptance in its current form. Indeed, my rassessment is primarily on two concerns: the exposition makes the central claims and their interpretation unnecessarily difficult to assess, and the manuscript does not sufficiently establish the relevance of its main obstruction to independently motivated detector classes . Resolving it would require a significant restructuring of the exposition, rather than local clarifications alone. I expect an ICLR submission to communicate its scientific contribution clearly, precisely, and above all accessibly to the research community. The text repeatedly shifts between figurative language and mathematical assertions without articulating the logical connections. Although formal definitions appear later, the overall exposition leaves the reader with the burden to reconstruct and to determine what is assumed, what is proved, and what the results imply. Addressing this concern requires a lot of rewriting of the exposition, beginning with the abstract and introduction. I do not consider the manuscript currently suitable for acceptance at ICLR.

Questions for authors
  1. Could you provide a self-contained explanation of the Lemma 2.1 and Proposition 2.2, using explicit (and simpler) mathematical statements? In particular, please distinguish the distribution of a learner’s output at a fixed ID law from the construction of a different learner by reindexing, and clarify which quantities may depend on the target rate.
  2. Beyond the correction to Fang et al., what specific problem does your theorem solve ? I would like to know how broadly it applies to standard detector classes and real-world OOD families. Please show a concrete example of a standard class where your result provides a new conclusion about what can be learned.
4 comments
AuthorsOpenReview ↗

Response to Reviewer EuUJ (1/3)

Thank you for the review, and for Question 1: the difference between the law of a learner's output at a fixed ID law and the learner built from it by reindexing is the step a reader most needs, and Proposition 2.2 now states that learner and what it depends on. On your first concern we agree: the exposition made the central claims hard to assess, and we have revised the abstract and introduction (below). On your second weakness, including its paragraph on bounded weights, the obstruction is not an artifact of non-compact parameters: closed halfspaces, whose parameters form a compact set, can have a moving blind spot. Halfspaces that each reject a given OOD point can converge to one whose boundary passes through that point and so accepts it; for closed halfspaces this produces a blind spot only when the ID law and some OOD law both put mass on a hyperplane (Proposition 3.6).

Weakness 1 and the overall assessment (presentation). What changed:

  • Pages 1–2. The abstract, most of which is revised, no longer uses "observation fiber" or "completion". The introduction opens with a paragraph that separates what is assumed, what is proved and what is implied, then states the main theorem with its quantifiers (page 2), followed by a one-sentence statement of the halfspace result (the example itself is Proposition 3.6, page 8). The metaphors you quote are gone from the main text, as are "clock" and "slowness"; the epigraph has been removed from page 1, and Figure 1 has literal panel titles and caption.
  • Inside Sections 2–6, whose order is unchanged, Proposition 2.2 states the learner it constructs (Question 1 below), Theorem 3.3 opens with the equivalence it proves, the compactness paragraph at the end of Section 3 is rewritten around Proposition 3.6, and the Discussion opens with what the results imply.
  • Terms. Four of the terms you named remain. Fiber, schedule and moving blind spot are defined in running text on page 2, and window in Section 2; Table 2 (Section 2), to which Table 1 now points, collects them for lookup. A fiber is the set of problems sharing an ID law; a schedule is a data-independent sequence of laws on detectors; a window is a finite subfamily of a fiber; and a moving blind spot is a family that is consistent but has V>0V>0, where the value VV is the best worst-case expected error over the family.

Question 1 and "every rate or none" (Lemma 2.1 and Proposition 2.2, explicitly). Fix the ID law PP. A learner AA maps a sample Sn∼PnS_n\sim P^n and an independent seed to a detector in H\mathcal H. The loss is bounded by MM.

Lemma 2.1. Let μn\mu_n be the law of the detector A(Sn)A(S_n) under PnP^n and the seed. It depends on AA, PP and nn, not on the OOD law QQ, and for every QQ,

E E(P,Q)(A(Sn))=∫E(P,Q)(h) dμn(h).\mathbb E\thinspace\mathcal E_{(P,Q)}(A(S_n))=\int\mathcal E_{(P,Q)}(h)\thinspace d\mu_n(h).

On the set of problems with ID law PP, the errors of AA are therefore determined by the sequence (μn)(\mu_n) alone.

Proposition 2.2. Suppose AA attains a rate rr for this PP: every QQ has CQ,cQ>0C_Q,c_Q>0 with E E(P,Q)(A(Sn))≤CQr(cQn)\mathbb E\thinspace\mathcal E_{(P,Q)}(A(S_n))\le C_Qr(c_Qn) for all nn. Let ss be any other rate. Choose integers φs(n)\varphi_s(n) with r(φs(n)/n)≤s(n)r(\varphi_s(n)/n)\le s(n) (they exist because r(t)→0r(t)\to0), and let the learner BsB_s, at sample size nn, ignore its sample and output a detector drawn from μφs(n)\mu_{\varphi_s(n)}. Then, for every QQ and nn,

E E(P,Q)(Bs(Sn))≤max⁡{CQ, M/s(1/cQ)} s(n).\mathbb E\thinspace\mathcal E_{(P,Q)}(B_s(S_n))\le\max\lbrace C_Q,\ M/s(1/c_Q)\rbrace\thinspace s(n).

Indeed, by Lemma 2.1 the left side equals E E(P,Q)(A(Sφs(n)))≤CQr(cQφs(n))\mathbb E\thinspace\mathcal E_{(P,Q)}(A(S_{\varphi_s(n)}))\le C_Qr(c_Q\varphi_s(n)). If n≥1/cQn\ge1/c_Q, then cQφs(n)≥φs(n)/nc_Q\varphi_s(n)\ge\varphi_s(n)/n, and since rr is nonincreasing, r(cQφs(n))≤r(φs(n)/n)≤s(n)r(c_Q\varphi_s(n))\le r(\varphi_s(n)/n)\le s(n). If n<1/cQn\lt1/c_Q, the left side is at most M≤(M/s(1/cQ)) s(n)M\le(M/s(1/c_Q))\thinspace s(n), since ss is nonincreasing. What depends on what:

  • μn\mu_n depends on (A,P,n)(A,P,n);
  • φs\varphi_s depends on (r,s)(r,s);
  • BsB_s depends on (A,P,r,s)(A,P,r,s) and not on QQ;
  • the constants depend on QQ and ss, and on AA and rr through CQ,cQC_Q,c_Q.

So yes, each target rate has its own learner: BsB_s depends on ss. On particular families one learner can attain every rate at once (on the point-mass family of Proposition 3.5, the learner that outputs hn+1h_{n+1} does), but Proposition 2.2 does not claim this. BsB_s is a valid learner only because PP is fixed: it samples from μ\mu at PP. Proposition 2.2 uses that PP is known; this is why rates for one ID law are all or none, and why nontrivial rates need the sample to identify PP (Sections 4 and 5). Theorem 3.3 is stated for each fixed learner and does not use reindexing, and Theorem 4.1(b) applies it when the ID law is unknown. Proposition 2.2 now states these dependencies.

AuthorsOpenReview ↗

Response to Reviewer EuUJ (2/3)

Weakness 2 (an independently motivated class, and bounded weights). Closed halfspaces: yes. Bounded-weight networks with one hidden ReLU unit define exactly the same detectors, so the answer carries over. In both cases a blind spot requires that the ID law and some hidden law each put mass on a hyperplane, and Proposition 3.6 gives one where they do.

Our submission's remark "A moving blind spot requires a noncompact class" (end of Section 3) dropped the lower-semicontinuity hypothesis of Proposition C.8, and without it the remark is false. No theorem or proof used it, and the statement of Proposition C.8 is unchanged. New Proposition 3.6 replaces the remark. It takes binary detection with zero-one loss and closed halfspaces {w⋅x+b≥0}\lbrace w\cdot x+b\ge0\rbrace, with (w,b)(w,b) on the unit sphere (VC dimension d+1d+1).

  • A blind spot (d≥2d\ge2). Let the ID law be a point mass at 00 and the hidden laws point masses at u=(−1,0)u=(-1,0) and vj=(1,1/j)v_j=(1,1/j). For any finitely many of these points, one halfspace accepts 00 and rejects all of them. But a halfspace that accepts 00 and rejects uu has w1>b≥0w_1>b\ge0, so it accepts vjv_j for all large jj. If pp is the probability that a random halfspace accepts 00 and rejects uu, its expected strong excess is 1−p1-p on uu and at least pp in the limit on vjv_j. So V≥1/2V\ge1/2, and an even mixture of {x2≤0}\lbrace x_2\le0\rbrace and {x1≥0}\lbrace x_1\ge0\rbrace attains 1/21/2. The countable family is learnable at every rate; its mixture completion is consistent but has no rate (Corollary 3.4, Theorem 3.3).
  • No blind spot. If every hidden law, or the ID law, puts no mass on any hyperplane, every consistent fiber is uniformly learnable at every rate.
  • One-unit networks. A bounded-weight network x↦a ReLU(w⋅x+b)+cx\mapsto a\thinspace\mathrm{ReLU}(w\cdot x+b)+c, accepting where it is nonnegative, accepts a closed halfspace, everything, or nothing, and every closed halfspace arises (Appendix D.7). As a detector class, this smallest network is exactly the closed halfspaces.

Relative compactness alone does not exclude a blind spot, because thresholding a score is not continuous. The separators of Appendix D.7 converge to the halfspace {x2≤0}\lbrace x_2\le0\rbrace, whose boundary carries the ID atom and the hidden atom uu. Their pointwise limit S={x2<0}∪{x2=0, x1≥0}S=\lbrace x_2\lt0\rbrace\cup\lbrace x_2=0,\ x_1\ge0\rbrace is neither open nor closed, so no continuous score thresholded at zero, with ≥\ge or >\gt, accepts exactly SS. As with the prefix class, the class misses its pointwise limit. What changes is that the class is a standard one, fixed independently of the example; a larger class can still remove this particular blind spot (below). Proposition 3.6(2) identifies what any closed-halfspace blind spot needs: ID mass and hidden mass on hyperplanes.

For a linear head on a fixed feature map, such as a pretrained one, Proposition 3.6 applies to the feature laws, and these can charge hyperplanes: ReLU features have exact zeros, and features confined to a proper affine subspace lie in a hyperplane (Appendix D.7). So part (2) does not exclude a blind spot there. With strict thresholds, hidden laws with densities suffice, though the ID law must still charge a hyperplane (Appendix D.7).

Excess is class-relative, so enlarging the class can remove a given blind spot: two ReLU units accepting {∣x1∣≤1/2}\lbrace\vert x_1\vert\le1/2\rbrace are exact on this family. For wider fixed architectures the question is open; what Proposition 3.6 shows is that compact parameters, a Lipschitz activation and a bounded domain do not by themselves exclude the obstruction. Proposition 3.6 is in Section 3, with proofs in Appendix D.7; the one-unit case and the open question are stated after it.

Question 2 (the problem solved, for a standard class). The problem is whether a consistent detector trained on ID data alone can come with a universal rate, that is, a rate whose constants depend on the OOD law. Theorem 3.3 answers that, for a fixed ID law and a family closed under countable mixtures, it can only if the family is uniformly learnable. To our knowledge, prior OOD learnability theory (Fang et al., 2022; 2024; Garov & Chaudhuri, 2025), which studies uniform and certified learnability, does not ask this. For closed halfspaces, and hence one-unit ReLU networks, with K=1K=1 and zero-one loss, Theorem 3.3 reduces the question to whether V=0V=0, and Proposition 3.6 settles it except when both the ID law and some hidden law charge hyperplanes, where both outcomes occur.

AuthorsOpenReview ↗

Response to Reviewer EuUJ (3/3)

  • No rate (Theorem 3.3). For one known ID law, a consistent family closed under countable mixtures can have no rate at all, but only if the ID law and some hidden law each charge a hyperplane (Proposition 3.6).
  • Every rate (Proposition 3.6(2), the complementary side). With a known ID law, consistency already implies uniform learnability at every rate whenever the ID law, or every OOD law, charges no hyperplane; in particular for every ID law with a density.
  • Finitely many ID laws. With finitely many ID laws that charge no hyperplane, every consistent family, together with its mixtures, is learnable at a uniform exponential rate (Proposition 3.6(2) with Theorem 4.1; Appendix D.7, "Finitely many ID laws").

For pooled deployments, the theorem says when per-source learning curves carry over to mixtures of the sources. Appendix I.1 discusses deployments pooled over sources, such as hospitals or OOD test sets, with unknown weights. For a fixed ID law, a learning curve that holds for each source, however fast, extends to all countable mixtures of the sources only if it holds uniformly over them. Finite mixtures inherit per-source curves, so the condition matters for open-ended families of sources. Appendix I.1 also gives a worst-case diagnostic built from existing per-source miss rates; it is not an estimate of deployed error.

If the revised pages and Proposition 3.6 address your two concerns, we would appreciate it if you would reconsider your rating.

Thank you for the care you put into your response and the revision. I found the contrast between the countable family and its mixture closure interesting as taking mixtures preserves consistency while ruling out every rate. The new halfspace example also answered one of my main questions. I think there are very good ideas here, and I appreciated the chance to understand them better through your response.

I also appreciate the detail you added to the AI use statement. Reading it left me less confident that I had understood the extent of the LLM contribution from the original declaration. I would welcome a clearer account of the role the models played in developing the main results that were already in the submission, and of how you checked those arguments yourselves. The detail you provided about the work done during the discussion period was helpful, and I would appreciate the same level of clarity about the original results.

I’m keeping my rating at 2 because I still found it difficult to follow the paper and see the scope of the results from the main text. I’d strongly encourage you to made the paper more accessible and easy to follow: what is the problem and why it it theoretically grounded, in order to solve this problem what are the naturel mathematical object and how they naturally appears. Then I strongly encourage the authors to resubmit it as soon as possible (if it doesn't go throught ICLR 2027). I think maybe, just maybe, putting the contrast between the countable family and its mixture closure near the beginning as a motivation, then building the exposition around it, would give readers a much simpler way into the paper as that example helped me see what makes the result interesting, and I’d like more readers to have that experience.

Thank you again for your thorought work for the revision.

Reviewer_TFQwOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This MS concerns the important problem of anomaly detection or out-of-distribution detection: given data from one distribution PP, devise a classifier which will reliably detect new samples coming from a different distribution QQ, about which we know nothing. (*) Unsurprisingly, this is hard. Even if PP were known in advance we would be trying to build a hypothesis test with non-trivial error probabilities based on a single sample. Without restrictions, QQ can have the same support as PP, and indeed be arbitrarily close to PP (in, e.g., total variation) while still being a distinct distribution, hence the best attainable error probabilities are going to be bad. The MS., like much of the literature, tries to get around this by focusing on the excess risk, over and above the best detectors in some class.

This is still going to be a very weak sort of result, because a little thought reveals a sort of "no free lunch" result. Any "detector", i,e., classifier, like any hypothesis test, can be described by the set c⊂Xc \subset \mathcal{X} on which the detector outputs "in-distribution", with the output being "out of distribution" on c‾≡X∖c\overline{c} \equiv \mathcal{X} \setminus c. (The MS. does not consider randomized detectors.) The probability of a true negative will be P(c)P(c), a false positive P(c‾)P(\overline{c}), a true positive Q(c‾)Q(\overline{c}), and a false negative Q(c)Q(c). Since the learner outputs a detector based on nn data points drawn from PP (and perhaps some internal randomness), the acceptance region is really a random set CnC_n. Because all of the data points are drawn from PP, it is possible to control P(Cn)P(C_n) and/or P(Cn‾)P(\overline{C_n}). Even if, for some QQ, we could arrange to pick CnC_n so as to guarantee that Q(Cn)Q(C_n) becomes low (without also making P(Cn)P(C_n) small!), there will inevitably be other distributions Q′Q^{\prime}, distinct from both PP and QQ, where P(Cn)P(C_n) and Q′(Cn)Q^{\prime}(C_n) are arbitrarily close. Indeed there will exist alternative distributions Q′Q^{\prime} which differ from PP by placing too much probability on CnC_n. If the terms of the problem are to guarantee decreasing error probabilities, in the face of arbitrary QQ, without any data from QQ, it is hopeless. We simply never get any information at all about QQ from any number of samples from PP. Because we have no information, it is not surprising that we cannot establish any rates of convergence.

The only way OOD detection can possibly work is by placing strong a priori restrictions on QQ and how it is related to PP, so that making observations on PP does tell us, by implication, about QQ. If, for instance, we assume PP and QQ have disjoint supports, we could try to learn the support of PP, and report "out of distribution" outside that estimated support (**). Or, if one knew that QQ had to be at least distance δ\delta from PP (in whatever metric or divergence on distributions), that could be worked with too. It is only under assumption of this type (albeit more complicated ones) that this MS. claims to have any rates at all. Those rates come entirely from the a priori restrictions. We cannot, obviously, test or support such restrictions on the basis of data from PP alone.

I admit that the previous two paragraphs are rather dismissive, and ignore all sorts of subtle points about uniform versus universal rates of convergence, etc., etc., in favor of a brisk dismissal. This is because at no point does the MS. do anything to convince the reader that those subtleties are even theoretically interesting, let alone relevant as guides to practice. This is not just because I am out of sympathy with OOD detection; I understand the point of results like those in Garov and Chaudhuri (2025) or Fang et al. (2024). But even if all the proofs presented here are exactly correct, I cannot fathom why anyone should care.

I said "so far as I can tell" because the writing is very, very bad. The text uses a series of metaphors --- fibers, blind spots, clocks, middle positions --- which are neither illuminating on their own nor integrated with each other. The arguments are confused, the prose is prolix and repetitive, and the logic, such as it is, confined to the appendices. Whether or not the statement about LLM usage is entirely forthcoming, this MS. does not meet minimal standards of clarity and concision for acceptable scientific communication.

*: I am aware that the MS. considers the situation where the training data is actually from KK classes, and the goal is, supposedly, to actually classify new points into either one of these KK classes, or into the class "K+1K+1" representing out-of-distribution. Since KK, and the in-distribution classification process, seem to play absolutely no role in the analysis, I will ignore that complication in the rest of this review.

**: Any two ergodic measures on infinite sequences are either identical, or have disjoint supports. To the extent that OOD detection works in practice on text, it is probably because of this.

Critical strengths

None.

Critical weaknesses

See above.

Questions for authors

None.

3 comments
AuthorsOpenReview ↗

Response to Reviewer TFQw (1/3)

Thank you for the review. We agree that the writing made the paper harder to read than it should be. We have rewritten most of the abstract and the opening of the introduction, and removed the figurative passages from the main text (such as the clock, the middle position and slowness); of the metaphors you named, only "fiber" and "moving blind spot" remain, each with its definition in Table 2 (general response, item 1). Your no-free-lunch argument is also our starting point. What it does not settle is whether a rate whose constants depend on the OOD law can exist; for a fixed ID law, the paper answers that for hidden families closed under countable mixtures and for countable ones.

Significance. In supervised learning, universal rates are an established way past pessimistic uniform rates, since they can be exponentially fast where uniform rates are not (Bousquet et al., 2021). Theorem 3.3 shows that, within a fiber, this route is closed for OOD detection once hidden laws can be mixed: for a fixed ID law and a hidden family closed under countable mixtures, a rate with law-dependent constants exists only if a uniform one does, so a mixture-closed restriction gives no rate unless it already gives uniform learnability. The same holds when the ID law is one of finitely many and the learner must use its sample (Theorem 4.1(b)). Lack of information about the OOD law does not by itself decide the question. Two families with the same ID law, class and atoms are equally uninformative, yet behave in opposite ways: on the countable point-mass family of Proposition 3.5, one learner attains every rate, because each law is learned exactly after finitely many steps, with constants that depend on the law and no uniform guarantee; on its closure under countable mixtures, every law is still learned, yet no learner attains any rate at all. Prior OOD learnability theory (Fang et al., 2022; 2024; Garov & Chaudhuri, 2025) studies uniform and certified learnability; to our knowledge it does not ask when a consistent learner has a universal rate. Separately, the paper shows by counterexample that a condition stated as necessary in Fang et al. (2024, Theorem 13) is not necessary, and it locates the failing step in their proof (Section 4, Appendix G.2). The contribution is to theory. Its practical reading is limited to guarantees: a rate bound proved for one learner on each of infinitely many OOD sources extends to their countable mixtures only if it holds with one pair of constants for all of them (Appendix I.1).

"Never get any information at all about Q", and "a priori restrictions". We agree that, with a fixed ID law, the sample carries no information about the OOD law; Lemma 2.1 is the formal version: every learner acts as a fixed sequence of laws on detectors. We also agree that, against hidden laws that can be mixed, a rate needs a restriction that ID data cannot test (Section 6, "What the results imply"), and Theorem 3.3 says which mixture-closed restrictions can give one: exactly those that make the family uniformly learnable. We do not agree that rates then come entirely from the restriction. A nontrivial rate needs several ID laws (Proposition 2.2), and in our results its value is the cost of identifying the ID law: e−cne^{-cn} in Theorem 4.1, sharp for some conflicting fibers (Proposition E.2), and order 1/n1/n in Theorem 5.2.

The two restrictions you propose.

  • A distance between the laws. With all detectors, K=1K=1 and zero-one loss, the strong excess benchmarks both error types at zero, so any overlap leaves a floor: every detector law has excess at least 12(1−TV(PX,Q))\frac12(1-\mathrm{TV}(P_X,Q)) (Section 6, "Boundaries"), and separation in total variation below 11 gives nothing. This is a property of the criterion; for AUC, overlap alone is not an obstruction (Appendix G.3). With a restricted class, separation alone need not help: in Proposition 3.6 (closed halfspaces, d≥2d\ge2), every hidden law is mutually singular to the ID law, with support at distance at least 11 from it, and the mixture-closed family is consistent but has no rate.
  • Separated supports, with all detectors, K=1K=1 and zero-one loss. Once supports may touch, even at one point, no universal rate survives: the witness of Theorem 5.3 has supports meeting only at 00. Disjoint closed supports with bounded ID support give a universal rate O((log⁡n)d/n)O((\log n)^d/n), and a known margin with ID supports of bounded diameter gives a uniform bound; on Rd\mathbb R^d, once ID supports may be unbounded, even a known margin gives no rate. These are in Section 5 ("Separated supports") and Appendix F.4, with details in the response to Reviewer wsSs.
AuthorsOpenReview ↗

Response to Reviewer TFQw (2/3)

The "no free lunch" argument. For a fixed ID law and class-relative error, the argument becomes: there is a constant c>0c>0 such that, for every learner, at every sample size some hidden law has expected excess at least cc. This holds exactly when V>0V>0 (take c=V/2c=V/2), and it rules out uniform guarantees, not consistency. Theorem 3.3 and Corollary 3.4 decide what it implies for rates on mixture-closed and on countable families.

Soundness. The core argument has three steps: Lemma 2.1 (Section 2; proof in Appendix C.1), and Lemma 3.2 and Theorem 3.3, proved in full in Section 3. Fix the ID law PP and a learner AA. For a detector hh and an OOD law QQ, E(P,Q)(h)\mathcal E_{(P,Q)}(h) is the larger of the ID excess and the OOD excess of hh over the best detector in the class H\mathcal H.

  1. Decoupling. The sample is drawn from PnP^n, so the law μn\mu_n of the output A(Sn)A(S_n) does not depend on QQ, and E E(P,Q)(A(Sn))=∫E(P,Q) dμn\mathbb E\thinspace\mathcal E_{(P,Q)}(A(S_n))=\int\mathcal E_{(P,Q)}\thinspace d\mu_n.
  2. Affinity (Lemma 3.2). Suppose one sequence (μn)(\mu_n) has expected excess tending to 00 on each (P,Qk)(P,Q_k). Then the best-in-class OOD risk bb satisfies b(Q⋆)=∑kwkb(Qk)b(Q_\star)=\sum_kw_kb(Q_k) for Q⋆=∑kwkQkQ_\star=\sum_kw_kQ_k, and hence E(P,Q⋆)(h)≥wk E(P,Qk)(h)\mathcal E_{(P,Q_\star)}(h)\ge w_k\thinspace\mathcal E_{(P,Q_k)}(h) for every hh and kk.
  3. Diagonal (Theorem 3.3). If AA is not consistent on the mixtures, a single mixture already defeats every rate. Otherwise, suppose the worst-case excess sn=sup⁡Q∫E(P,Q) dμns_n=\sup_Q\int\mathcal E_{(P,Q)}\thinspace d\mu_n is not O(r(cn))O(r(cn)) for any cc. Pick times n1<n2<⋯n_1\lt n_2\lt\cdots with snk>4kr(nk/k)s_{n_k}>4^kr(n_k/k) and laws QkQ_k that are nearly worst at nkn_k. Then Q⋆=∑k2−kQkQ_\star=\sum_k2^{-k}Q_k has expected excess above 2k−1r(nk/k)2^{k-1}r(n_k/k) at nkn_k, which exceeds C r(cnk)C\thinspace r(cn_k) for every fixed C,cC,c once kk is large.

The techniques are classical: decoupling, and a gliding-hump diagonal as in the condensation of singularities. What is new is the equivalence itself, which fails without mixture closure (Proposition 3.5); for criteria whose benchmark can be positive, such as the fixed-proportion excess and AUC (Proposition D.1), it also needs Step 2. Three side remarks of the submission were false as stated, each because it omitted a hypothesis; the revision adds the missing hypotheses, and no proof used any of the three remarks (general response, item 3).

Clarity, concision and metaphors. Besides the changes above, the introduction now opens by separating what is assumed, proved and implied, and it states the main theorem formally; the epigraph has been removed from page 1, and the Discussion paragraph "Other observation structures" has moved to Appendix I.3. The main text is one page longer than before, mainly because of Proposition 3.6 and Table 2.

"The logic … confined to the appendices". As in the submission, the main text proves Propositions 2.2, 3.1, 3.5 and 4.3, Theorems 2.3 and 3.3, Lemma 3.2, and Corollary 3.4; the certification statements in Proposition 3.1 and Corollary 3.4 use Theorem 2.4, completed in Appendix C.2. The appendices hold the proofs of Lemma 2.1, Theorems 2.4, 4.1 and 4.2, Proposition 3.6 and Section 5, and the general theory.

Randomized detectors. The submission allowed randomized learners: a learner maps the sample and an independent seed to a detector (Section 2). The pointwise randomized test, which outputs each label yy, including rejection, at xx with probability μ{h:h(x)=y}\mu\lbrace h: h(x)=y\rbrace, is now treated in Appendix A ("Two ways to charge a randomized learner"): its strong excess is within a factor two of our charge, so no learnability notion or rate class changes.

The role of KK. Under zero-one loss, KK enters only through the ID excess, and every lower-bound construction uses K=1K=1, as Section 2 now says. The general upper bounds, such as Theorem 5.1, hold for every KK, which is why the setup keeps it.

AuthorsOpenReview ↗

Response to Reviewer TFQw (3/3)

LLM use. The submitted AI-use statement said that the original research ideas and initial manuscript draft were developed by the authors, and that language models were used to help reorganize the paper around observation fibers; to formulate and prove several new claims, which it names; to formulate the open problems and short observations of Appendix I; to write and edit proofs and text; to produce the figures; and to check citations against Crossref, arXiv and publisher records. We have extended it, after the main text, to the discussion period: language models were used to formulate and prove Proposition 3.6 and the results after it in Appendix D.7, the separated-support results of Section 5 and Appendix F.4, and the remark on randomized tests in Appendix A; to re-check the proofs of Sections 2 and 3; to check the description of Fang et al. (2024) in Appendix G.2 against the published text; and to draft the revised exposition. Each new claim was also checked in model-based verification passes; as the statement says, the authors reviewed all AI-assisted content and take full responsibility for the correctness of the manuscript.

Ergodic measures. In the measure sense the footnote is right: distinct ergodic measures are mutually singular, which is the condition Section 6 ("Boundaries") identifies for learning a single domain with all detectors, K=1K=1 and zero-one loss. Their supports can still coincide (non-degenerate Bernoulli shifts on {0,1}N\lbrace0,1\rbrace^{\mathbb N} both have full support), which puts such pairs outside the support-based results of Section 5, where Q(supp⁡PX)=0Q(\operatorname{supp}P_X)=0.

Comments on the paper

6 comments
AuthorsOpenReview ↗

General Response (1/3)

We thank the three reviewers. Summary for the area chair. The decisive concerns are presentation (Reviewer EuUJ, Reviewer TFQw), significance (Reviewer TFQw: whether universal rates matter when ID data carry no information about the OOD law; item 3), and whether the main obstruction occurs for a standard detector class (Reviewer EuUJ, Reviewer wsSs). No review reports an incorrect proof step; in re-checking the proofs we found three side remarks that were false as stated, and the revision corrects them (item 3). The revision rewrites most of the abstract and the opening of the introduction, which now states the main theorem with its quantifiers on page 2. It also adds Proposition 3.6 (page 8): closed halfspaces, a standard class with compact parameters, can have a moving blind spot, which corrects a remark of the submission that suggested otherwise. Limits: for closed halfspaces (K=1K=1, zero-one loss) there is provably no blind spot when the ID law has a density (Proposition 3.6(2)); whether wider networks or learned features have one is open. All new and rewritten text in the revised PDF is in blue; the deletions are listed below.

1. Presentation (Reviewer EuUJ, Reviewer TFQw, Reviewer wsSs). We agree that the exposition made the central claims hard to assess: the submission stated its results through figurative language before stating them mathematically. We have rewritten most of the abstract and the opening of the introduction, and removed the figurative passages from the main text (such as the clock, the middle position and slowness). The abstract no longer uses "observation fiber" or "completion", and, of the metaphors Reviewer TFQw named, "fiber" and "moving blind spot" remain, now as defined terms. The title is unchanged.

  • The introduction now opens with a paragraph that separates what is assumed, what is proved and what is implied, and it states the main theorem formally, with its quantifiers, on page 2.
  • Of the words the reviewers named, "clock", "slowness" and "middle position" are gone from the main text. "Fiber", "schedule", "window", "value" and "moving blind spot" are defined terms, collected for lookup in Table 2 (Section 2); "moving blind spot" means only "consistent but V>0V>0".
  • Proposition 2.2 now states the learner it constructs and what that learner depends on (Reviewer EuUJ, question 1).
  • The epigraph has been removed from page 1, and Figure 1 has literal panel titles and caption.

The main theorem, as the introduction now states it: fix an ID law PP, a detector class H\mathcal H, and a family Q\mathcal Q of OOD laws closed under countable mixtures. Write en(Q)=E E(P,Q)(A(Sn))e_n(Q)=\mathbb E\thinspace\mathcal E_{(P,Q)}(A(S_n)) for the expected class-relative excess of a learner AA after nn ID samples. For every learner AA and every rate rr,

[∀Q∈Q ∃CQ,cQ>0 ∀n: en(Q)≤CQ r(cQn)]  ⟺  [∃C,c>0 ∀n: sup⁡Q∈Qen(Q)≤C r(cn)].\Big[\forall Q\in\mathcal Q\ \exists C_Q,c_Q>0\ \forall n:\ e_n(Q)\le C_Q\thinspace r(c_Qn)\Big]\iff\Big[\exists C,c>0\ \forall n:\ \sup_{Q\in\mathcal Q}e_n(Q)\le C\thinspace r(cn)\Big].

So if no learner is uniformly consistent on Q\mathcal Q (V>0V>0), no learner attains any rate on Q\mathcal Q, even when some learner eventually learns every Q∈QQ\in\mathcal Q. That case, consistent but V>0V>0, is a moving blind spot.

2. Standard detector classes (Reviewer EuUJ, weakness 2 and question 2; Reviewer wsSs). Does the obstruction occur for an independently motivated class? For closed halfspaces, which bounded-weight networks with one hidden ReLU unit define exactly, yes: a moving blind spot can occur with all laws in a bounded set. It needs the ID law and some hidden law each to put mass on a hyperplane, so it never occurs when the ID law has a density (new Proposition 3.6, page 8; proofs in Appendix D.7). Proposition 3.6 takes binary detection (K=1K=1) with zero-one loss and closed halfspaces {x:w⋅x+b≥0}\lbrace x: w\cdot x+b\ge0\rbrace, with (w,b)(w,b) on the unit sphere of Rd+1\mathbb R^{d+1} (a compact parameter set; VC dimension d+1d+1).

  • A blind spot (d≥2d\ge2). Let the ID law be a point mass at the origin and the hidden laws point masses at u=(−1,0)u=(-1,0) and vj=(1,1/j)v_j=(1,1/j). For any finitely many hidden points, one halfspace accepts the origin and rejects them all. But a halfspace that accepts the origin and rejects uu accepts vjv_j for all large jj, so every randomized detector has expected strong excess at least 1/21/2 on uu or on some vjv_j, and V=1/2V=1/2. The countable family is learnable at every rate, while its mixture completion is consistent but has no rate (Corollary 3.4, Theorem 3.3).
  • No blind spot. If every hidden law, or the ID law, puts no mass on any hyperplane, every consistent fiber of this class is uniformly learnable at every rate.
AuthorsOpenReview ↗

General Response (2/3)

This corrects a remark of the submission. Its sentence "A moving blind spot requires a noncompact class" (end of Section 3) dropped the lower-semicontinuity hypothesis of Proposition C.8, stated in the sentence before it, and without that hypothesis it fails. No theorem or proof used the remark, and the statement of Proposition C.8 is unchanged; its title now names both hypotheses. The corrected text is the paragraph "When does compactness help?" at the end of Section 3.

The responses to Reviewer EuUJ and Reviewer wsSs give the details: why the limit of the separators is not a halfspace, strict thresholds, linear heads on fixed features, the two-unit network that removes this blind spot, and the consequence for finitely many ID laws (Appendix D.7). Whether a fixed wider architecture has a moving blind spot is open, and we make no claim about it.

3. Soundness and significance (Reviewer TFQw; Reviewer EuUJ, question 2). The main text proves the main chain (Proposition 2.2, Theorem 2.3, Proposition 3.1, Lemma 3.2, Theorem 3.3, Corollary 3.4, Proposition 3.5); the certification statements in Proposition 3.1 and Corollary 3.4 use Theorem 2.4, completed in Appendix C.2, and the response to Reviewer TFQw gives the core argument in a few lines. The revision corrects three statements of the submission that were false as stated, each because it omitted a hypothesis; no proof used any of them:

  • the compactness remark (item 2);
  • the accept-all/reject-all example in Section 2, which omitted zero-one loss, now added;
  • the remark after Lemma 3.2, which omitted individual rejectability and zero-one loss, both now added.

We also clarified two points:

  • Eq. (2): Section 2 now notes that, for a fixed learner and rate, Eq. (2) is exactly non-attainment of the rate; unlike a minimax bound, its hard domain does not change with nn. Theorem 3.3 now opens with the equivalence of item 1, in words;
  • the caption of Figure 1(c), which now gives the threshold for every C/(cn)C/(cn), not only for C/nC/n.

On significance: in supervised learning, universal rates are an established way past pessimistic uniform rates, since they can be exponentially fast where uniform rates are not (Bousquet et al., 2021). Theorem 3.3 shows that for OOD detection with a fixed ID law this route is closed once hidden laws can be mixed.

Reviewer TFQw's argument is that, since ID data carry no information about the OOD law, a rate can come only from an a priori restriction on the OOD family, and then comes entirely from that restriction. We agree that, against hidden laws that can be mixed, a rate needs such a restriction, and the paper makes this exact. Whether a rate exists is decided by the ID law, the class and the hidden family, not by the sample; when a nontrivial rate exists in the paper's results, its value is the cost of identifying the ID law (Sections 4 and 5). For a fixed ID law, Theorem 3.3 then says which restrictions can give a rate.

  • Restrictions closed under countable mixtures. Such a restriction gives a rate only if it makes the family uniformly learnable (V=0V=0), and ID data cannot verify that.
  • Restrictions that break mixture closure. On the point-mass family of Proposition 3.5 (V=1V=1), one learner attains every rate, with constants that depend on the hidden law and a worst case that stays at 11, although the sample carries no information about the hidden law. This is not a usable guarantee; it shows only that lack of information does not by itself exclude a rate, and Theorem 3.3 identifies what does.
  • A distance between the laws. For a restricted class, separation alone need not help. In Proposition 3.6 every hidden law is mutually singular to the ID law, with support at distance at least 11 from it, all laws lying in a bounded set, and the mixture completion still has no rate.

The negative case concerns one fixed OOD law for all sample sizes, not a different law at each nn. For every learner and candidate rate there is a single OOD law, chosen after the learner and the rate but before any constant, on which the learner's error decays more slowly than that rate. The same holds when the ID law is one of finitely many and the learner must use its sample (Theorem 4.1(b)).

As a statement about guarantees: for one learner and a fixed ID law, a rate bound CQr(cQn)C_Qr(c_Qn) proved separately for each of infinitely many OOD sources extends to every countable mixture of them only if it holds with one pair of constants (C,c)(C,c) for all sources; for finitely many sources it always extends. Appendix I.1 also gives a worst-case diagnostic built from existing per-source miss rates; it is not an estimate of deployed error.

AuthorsOpenReview ↗

General Response (3/3)

To our knowledge, prior OOD learnability theory (Fang et al., 2022; 2024; Garov & Chaudhuri, 2025) studies uniform and certified learnability; it does not ask when a consistent learner has a universal rate, that is, a rate with constants that depend on the OOD law. Separately from Theorem 3.3, the paper shows by counterexample that a deterministic compatibility condition stated as necessary in Fang et al. (2024, Theorem 13) is not necessary, and it locates the failing step in their proof (Section 4, Appendix G.2).

Revisions in the uploaded PDF (new and rewritten text in blue):

  • deleted from the main text: the epigraph on page 1 (Appendix J, which discusses it, remains), the passages using "clock", "slowness" and "middle position", and the sentence "A moving blind spot requires a noncompact class";
  • the new abstract, Figure 1 caption and introduction, including the assumed/proved/implied paragraph (item 1);
  • Table 2 of terms, the explicit Proposition 2.2, and a sentence on the role of KK, in Section 2 (item 1; Reviewer EuUJ, question 1; Reviewer TFQw);
  • Proposition 3.6 on closed halfspaces, with the one-unit case after it and the proofs, the strict-threshold case and the finite-ID consequence in Appendix D.7 (item 2);
  • a paragraph "Separated supports" at the end of Section 5, proved in Appendix F.4, relating Theorem 5.3 to disjoint, closed and separated supports (Reviewer wsSs), and a remark after Fact B.9;
  • the corrections of item 3;
  • a Discussion that states what the results imply, with its paragraph "Other observation structures" moved to Appendix I.3;
  • in the appendices: randomized tests in Appendix A ("Two ways to charge a randomized learner"; Reviewer TFQw), the practical statement of Appendix I.1, and new titles for Appendix J and Proposition C.8;
  • smaller blue edits: a sentence in Section 2 stating the excess bound V(C)/2V(\mathcal C)/2 (Theorem C.7), new titles for Theorem C.7 and Fact B.9, a sentence in Appendix I.5 on bounded backgrounds, and wording edits elsewhere.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.