Realizable Bayes-Consistency for General Metric Losses

Dan Tsir Cohen, Steve Hanneke, Aryeh Kontorovich · 2026

Read Realizable Bayes-Consistency for General Metric Losses by Dan Tsir Cohen, Steve Hanneke, Aryeh Kontorovich (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-03823.txt.

Introduction

Dan Tsir Cohen, Steve Hanneke, and Aryeh Kontorovich settle a question about when learning with general metric losses can be Bayes-consistent in the realizable setting. Bayes-consistency means a learning rule's risk converges to the best possible as data grow. Earlier work covered classification and real-valued regression. General metric losses stayed open since 2022.

The authors work with an instance space and a label space carrying possibly unbounded loss. They find necessary and sufficient conditions on the hypothesis class. Under them, a distribution-free rule's risk converges almost surely to zero on every realizable distribution. The characterization turns on a combinatorial obstruction: an infinite non-decreasing Littlestone tree with growing gap parameters. It extends earlier tree structures to the metric loss setting.

Catalog record

CREATORDan Tsir Cohen, Steve Hanneke, Aryeh Kontorovich
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.03823

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Realizable Bayes-Consistency for General Metric Losses Dan Tsir Cohen, Steve Hanneke, Aryeh Kontorovich Abstract We study strong universal Bayes-consistency in the realizable setting for learning with general metric losses, extending classical characterizations beyond 0 0 - 1 1 classification ( Bousquet et al. 2020 ; Hanneke et al. 2021 ) and real-valued regression ( Attias et al. 2024b ) . Given an instance space ( 𝒳 , ρ ) (\mathcal{X},\rho) , a label space ( 𝒴 , ℓ ) (\mathcal{Y},\ell) with possibly unbounded loss, and a hypothesis class ℋ ⊆ 𝒴 𝒳 \mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}} , we resolve the realizable case of an open problem presented in Tsir Cohen & Kontorovich 2022 . Specifically, we find the necessary and sufficient conditions on the hypothesis class ℋ \mathcal{H} under which there exists a distribution-free learning rule whose risk converges almost surely to the best-in-class risk (which is zero) for every realizable data-generating distribution. Our main contribution is this sharp characterization in terms of a combinatorial obstruction: Similarly to Attias et al. 2024a , we introduce the notion of an infinite non-decreasing ( γ k ) (\gamma_{k}) -Littlestone tree, where γ k → ∞ \gamma_{k}\to\infty . This extends the Littlestone tree structure used in Bousquet et al. 2020 to the metric loss setting. 1 Introduction Many learning problems are naturally expressed with a metric loss on the label space: one predicts a label y\in{\mathcal{Y}} and is penalized by the distance \ell(\hat{y},y) . This encompasses multiclass prediction (discrete metrics), regression (absolute loss), structured outputs with edit-type losses, and general cost-sensitive prediction. In such settings {\mathcal{Y}} is typically infinite and \ell may be unbounded. While unbounded losses are standard in regression, they are far less understood in the broader metric-loss setting from the most basic distribution-free perspective: when is strong universal consistency possible at all? Realizable strong universal Bayes-consistency. Fix an instance space ({\mathcal{X}},\rho) , a label space ({\mathcal{Y}},\ell) (where \rho and \ell are metrics), and a hypothesis class {\mathcal{H}}\subseteq{\mathcal{Y}}^{\mathcal{X}} . \ell is the (possibly unbounded) loss function. Given an i.i.d. sample (X_{i},Y_{i})_{i\in[n]}\sim{\bar{\mu}}^{n} from an unknown distribution {\bar{\mu}} on {\mathcal{X}}\times{\mathcal{Y}} , a learner outputs a predictor f_{n}:{\mathcal{X}}\to{\mathcal{Y}} and incurs risk R_{{\bar{\mu}}}(f_{n})\ :=\ \mathop{\mathbb{E}}_{(X,Y)\sim{\bar{\mu}}}\,\ell(f_{n}(X),Y). We focus on the realizable setting: {\bar{\mu}} is realizable by {\mathcal{H}} if \inf_{h\in{\mathcal{H}}}R_{{\bar{\mu}}}(h)=0 . 1 1 1 Under the compact-parameterization assumption used in our main results (compact \Theta , h continuous in \theta , Lemma 4.3 ), realizability is equivalent to the existence of f^{\star}\in{\mathcal{H}} with Y=f^{\star}(X) almost surely (strict realizability), since the infimum over the compact image of \Theta is attained. We use this equivalence freely in proofs. See Appendix A.4.5 for further discussion. We ask for a distribution-free learning rule whose risk converges to 0 almost surely for every realizable {\bar{\mu}} . This is the natural strong-law analogue of universal consistency. In bounded loss settings, realizability is already a powerful structural assumption and often collapses the distinction between “risk goes to 0 ” and “errors go to 0 .” For unbounded metric losses, this intuition fails in a very concrete way: a learner may make mistakes on events whose probability decays with n , yet the scale of those mistakes can grow so quickly that the risk does not vanish (and can even be infinite). Understanding when such catastrophic rare-event failures are avoidable uniformly over all realizable distributions is the crux of the problem. Why unbounded metric losses are genuinely harder. With any bounded loss, every mistake costs at most a constant, so controlling the probability of error is essentially synonymous with controlling the risk. With general metric losses, a learner can be forced to guess between two labels that are extremely far apart on regions of the instance space that are rare but not ignorable. Realizability alone does not preclude this: an adversary can “hide” an infinite sequence of increasingly separated label choices behind a rapidly decaying probability mass. This phenomenon is absent in the bounded-loss theory and is not captured by purely distributional finiteness conditions (e.g., candidate assumptions such as R^{\star}<\infty ); indeed, in Section 3 we give an explicit counterexample showing that such finiteness-type conditions do not suffice to guarantee any distribution-free consistent learner in the realizable unbounded-loss regime. Main result (informal; refer to Section 4 ). Our contribution is a sharp hypothesis-class characterization of when realizable strong universal Bayes-consistency is possible for general metric losses. The characterization is in terms of a single combinatorial obstruction: an unbounded-gap Littlestone tree. Informally, an infinite non-decreasing (\gamma_{k}) -Littlestone tree is a full binary tree of instances whose depth- k nodes admit two outgoing labels at metric distance at least \gamma_{k} , where \gamma_{k}\uparrow\infty , and such that every finite root-to-leaf labeling pattern is realizable by some h\in{\mathcal{H}} (Definition 4.1 ). Under a mild compact-parameterization assumption (Lemma 4.3 ), this finite-prefix condition automatically ensures that every infinite path is realized by a single hypothesis. In particular, the counterexample of Section 3 naturally satisfies this assumption, demonstrating that unlearnability remains possible even under it (see Appendix A.4.3 for details). For metric losses (possibly unbounded), realizable strong universal Bayes-consistency is possible for {\mathcal{H}} if and only if {\mathcal{H}} does not contain an infinite non-decreasing (\gamma_{k}) -Littlestone tree with \gamma_{k}\to\infty . Moreover: • ( Lower bound. ) If such a tree exists, then for every learning algorithm {\mathcal{A}} there is a realizable distribution {\bar{\mu}} for which the learner suffers catastrophic rare-event errors; in fact, \mathop{\mathbb{E}}_{S_{n}\sim{\bar{\mu}}^{n}}[R_{{\bar{\mu}}}({\mathcal{A}}(S_{n}))]=\infty for every n (Theorem 5.1 ). • ( Upper bound. ) If no such tree exists, then there is an explicit distribution-free learning rule whose risk converges to 0 almost surely for every realizable {\bar{\mu}} (Theorem 6.5 ). Proof architecture. The lower bound converts an unbounded-gap tree into a realizable distribution on a random root-to-leaf path: at depths the sample misses (which exist for every finite n ), the learner is forced to guess between two labels separated by \gamma_{k} , and if \gamma_{k} grows fast enough the expected risk diverges. This is a metric-loss analogue of the classical adversarial role of Littlestone trees, but with the new ingredient that the scale of the ambiguity diverges. The upper bound takes a complementary game-theoretic route. Absence of an infinite unbounded-gap tree implies the learner wins an infinite Gale-Stewart game over realizable adversarial extensions, in the sense of Bousquet et al. 2020 . Simulating a winning strategy on the i.i.d. sample stabilizes a.s. after finitely many advances, yielding for each x a bounded-diameter set of admissible labels that contains the true label. A data-dependent countable partition of {\mathcal{X}} then reduces the problem to countably many bounded-loss subproblems handled by existing metric-loss learners. Contributions. In summary, this paper provides: • a complete hypothesis-class characterization of realizable strong universal Bayes-consistency for general metric losses, via the infinite unbounded-gap Littlestone tree obstruction (Theorem 4.5 ); • a constructive learning rule in the obstruction-free regime, proven to be strongly universally Bayes-consistent in the realizable setting (Theorem 6.5 ); • a separation demonstrating that natural finiteness-type conditions (e.g. candidates based on R^{\star}<\infty ) do not capture the correct characterization in the unbounded metric-loss realizable setting, resolving the realizable case of the open problem posed by Tsir Cohen & Kontorovich 2022 . Concrete examples of hypothesis classes that do and do not admit an unbounded-gap tree, illustrating

Read the complete text