Realizable Bayes-Consistency for General Metric Losses
Dan Tsir Cohen 1 Steve Hanneke 2 Aryeh Kontorovich 1
arXiv:2605.03823v1 [cs.LG] 5 May 2026
Abstract
Realizable strong universal Bayes-consistency. Fix an instance space (X , ρ), a label space (Y, ℓ) (where ρ and ℓ are metrics), and a hypothesis class H ⊆ Y X . ℓ is the (possibly unbounded) loss function. Given an i.i.d. sample (Xi , Yi )i∈[n] ∼ µ̄n from an unknown distribution µ̄ on X × Y, a learner outputs a predictor fn : X → Y and incurs risk
We study strong universal Bayes-consistency in the realizable setting for learning with general metric losses, extending classical characterizations beyond 0-1 classification (Bousquet et al., 2020; Hanneke et al., 2021) and real-valued regression (Attias et al., 2024b). Given an instance space (X , ρ), a label space (Y, ℓ) with possibly unbounded loss, and a hypothesis class H ⊆ Y 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 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 datagenerating 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 nondecreasing (γk )-Littlestone tree, where γk → ∞. This extends the Littlestone tree structure used in Bousquet et al. (2020) to the metric loss setting.
Rµ̄ (fn ) :=
E
ℓ(fn (X), Y ).
(X,Y )∼µ̄
We focus on the realizable setting: µ̄ is realizable by H if inf h∈H Rµ̄ (h) = 0.1 We ask for a distribution-free learning rule whose risk converges to 0 almost surely for every realizable µ̄. 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⋆ < ∞); 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.
1. Introduction Many learning problems are naturally expressed with a metric loss on the label space: one predicts a label y ∈ Y and is penalized by the distance ℓ(ŷ, y). This encompasses multiclass prediction (discrete metrics), regression (absolute loss), structured outputs with edit-type losses, and general costsensitive prediction. In such settings Y is typically infinite and ℓ 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? 1 Ben-Gurion University of the Negev 2 Purdue University, USA. Correspondence to: Dan Tsir Cohen <[email protected]>.
1 Under the compact-parameterization assumption used in our main results (compact Θ, h continuous in θ, Lemma 4.3), realizability is equivalent to the existence of f ⋆ ∈ H with Y = f ⋆ (X) almost surely (strict realizability), since the infimum over the compact image of Θ is attained. We use this equivalence freely in proofs. See Appendix A.4.5 for further discussion.
Proceedings of the 43 rd International Conference on Machine Learning, Seoul, South Korea. PMLR 306, 2026. Copyright 2026 by the author(s).
1
Realizable Bayes-Consistency for General Metric Losses
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.
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);
Informally, an infinite non-decreasing (γk )-Littlestone tree is a full binary tree of instances whose depth-k nodes admit two outgoing labels at metric distance at least γk , where γk ↑ ∞, and such that every finite root-to-leaf labeling pattern is realizable by some h ∈ 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).
• a constructive learning rule in the obstruction-free regime, proven to be strongly universally Bayesconsistent in the realizable setting (Theorem 6.5); • a separation demonstrating that natural finiteness-type conditions (e.g. candidates based on R⋆ < ∞) 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 the practical scope of the characterization, are presented in Appendix A.1. Extending the characterization to the agnostic setting, where µ̄ need not be realizable, is an important direction for future work; we discuss the barriers to such an extension in Appendix A.5.
For metric losses (possibly unbounded), realizable strong universal Bayes-consistency is possible for H if and only if H does not contain an infinite non-decreasing (γk )Littlestone tree with γk → ∞. Moreover: • (Lower bound.) If such a tree exists, then for every learning algorithm A there is a realizable distribution µ̄ for which the learner suffers catastrophic rare-event errors; in fact, ESn ∼µ̄n [Rµ̄ (A(Sn ))] = ∞ for every n (Theorem 5.1).
Organization. Section 2 discusses related work, with emphasis on universal learning and tree/game characterizations (Bousquet et al., 2020; Hanneke et al., 2023; Attias et al., 2024b), metric-loss learning algorithms (Tsir Cohen & Kontorovich, 2022), and combinatorial characterizations of learnability (Brukhim et al., 2022). Section 3 presents a counterexample showing that finiteness-type conditions alone do not guarantee distribution-free consistency for unbounded metric losses. Section 4 presents the main characterization and its proof, which consists of two parts: Section 5 proves the realizable lower bound: the existence of an infinite unbounded-gap Littlestone tree implies that no learner can be consistent (Theorem 5.1). Section 6 proves the matching upper bound: in the absence of such a tree, we construct a strongly universally Bayes-consistent learner (Theorem 6.5).
• (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 µ̄ (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 γk , and if γ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 gametheoretic 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 X then reduces the problem to countably many bounded-loss subproblems handled by existing metric-loss learners.
2. Related work Universal learning and game-theoretic characterizations. Our work builds on the recent program of understanding universal (i.e., distribution-free) learnability through the lens of infinite games and combinatorial trees. In the realizable 0-1 setting, Bousquet et al. (2020) introduced the universal learning model (allowing distribution-dependent constants) and developed a sharp theory of achievable rates via GaleStewart games and tree obstructions, highlighting the role of infinite Littlestone-type structures and measurability of 2
Realizable Bayes-Consistency for General Metric Losses
winning strategies. This framework was extended to multiclass prediction by Hanneke et al. (2023), who identified additional tree-based obstructions governing the universal rate landscape beyond the binary setting. More recently, Attias et al. (2024a) studied realizable regression in both PAC and online learning settings (notably for cut-off and absolute losses), providing characterizations of learnability via multiple combinatorial dimensions: scaled Graph dimension for ERM learnability, scaled One-Inclusion-Graph (OIG) dimension for general PAC learnability, and an online dimension based on scaled Littlestone trees (where the label separation is controlled by a resolution parameter or a scale sequence) that characterizes optimal cumulative loss in online learning (resolving an open question from prior work). The present paper continues this line in a different direction: rather than focusing on rates under bounded losses, we study strong universal Bayes-consistency under general metric losses, including unbounded ones, and provide a necessary-and-sufficient characterization in terms of an unbounded-gap Littlestone obstruction.
schitz functions and controls complexity via metric notions such as (doubling) dimension and fat-shattering. For example, Gottlieb and Krauthgamer and coauthors developed efficient large-margin classification algorithms for metric data whose runtime and guarantees depend on the doubling dimension and approximate proximity search/Lipschitz extension primitives (e.g., Gottlieb et al., 2014; see also proximity data structures in nearly doubling metrics Gottlieb & Krauthgamer, 2013). These works provide algorithmic and finite-sample perspectives tailored to geometric regimes (bounded diameter, doubling, or margin assumptions). Our setting is orthogonal: we do not assume low-dimensional geometry or bounded diameter globally, and the obstruction we identify is combinatorial (tree-based) rather than geometric. That said, our upper-bound construction explicitly exploits bounded-diameter subproblems (obtained via a data-driven partition of X ) and can therefore be viewed as a reduction that makes it possible to plug in existing boundedloss or bounded-range metric learners (including MedNet as used here) locally.
Learning with metric losses and unbounded risk. Learning with general metric losses has recently attracted attention as a common generalization of multiclass classification and real-valued regression. Most directly related is the MedNet algorithm of Tsir Cohen & Kontorovich (2022), which gives a constructive strong universal Bayesconsistent learner in the agnostic setting under separability assumptions and a bounded-in-expectation (BIE) condition on (Y, ℓ). That work extends the “optimistically universal” nearest-neighbor paradigm initiated for multiclass 0-1 learning on metric instance spaces (e.g., OptiNet and follow-ups Hanneke et al., 2021) to general metric label spaces, and emphasizes that naı̈ve extensions of classical metric-space methods can fail under general loss geometries. Our results are complementary in two ways. First, we focus on the realizable setting and ask when strong universal Bayesconsistency is possible as a function of the hypothesis class H, rather than imposing integrability conditions on Y or distributional conditions on µ̄. Second, the lower-bound construction underlying our characterization clarifies why unbounded losses fundamentally change the picture: even when the Bayes optimal risk is 0, rare mispredictions at increasing loss scales can preclude strong universal Bayesconsistency. In particular, our counterexample shows that finiteness-type conditions such as R∗ < ∞, suggested as a candidate in Tsir Cohen & Kontorovich (2022), are not sufficient in general without further structural assumptions.
Connections to classical combinatorial dimensions. Tree-based parameters are ubiquitous across learning models. In the uniform/PAC theory, VC dimension (binary) and its multiclass extensions (e.g., Natarajan and related dimensions) characterize learnability, with sharp recent results such as the DS-dimension characterization of multiclass PAC learnability (Brukhim et al., 2022). In adversarial online learning, the Littlestone dimension and its multiclass generalizations govern mistake bounds and regret. The universal-learning line (Bousquet et al., 2020; Hanneke et al., 2023; Attias et al., 2024b) reveals that infinite tree obstructions (and refinements thereof) also control distribution-dependent behavior beyond uniform convergence. Our contribution is to show that, for general metric losses in the realizable setting, the decisive obstruction is the existence of an infinite Littlestone-type tree whose label gaps can be forced to grow without bound along depth. This pinpoints the precise way in which unbounded loss magnitudes interact with realizability to make strong universal Bayes-consistency either possible or impossible.
3. R∗ < ∞ is insufficient In Tsir Cohen & Kontorovich (2022), a strongly universally Bayes-consistent learner for unbounded losses (MedNet) is achieved only when the label space Y is BIE. The label space Y is bounded in expectation (BIE) if E(X,Y )∼µ̄ ℓ(y0 , Y ) < ∞ for some y0 ∈ Y.
Metric-space learning, Lipschitz methods, and doubling structure. A parallel thread studies learning and generalization when instances are endowed with a metric and algorithms must leverage only distance information. A prominent approach models classifiers/regressors as Lip-
The BIE condition is a natural metric analogue of the realvalued moment assumption E |Y | < ∞. It was shown to be sufficient for Bayes consistency of MedNet, and it motivates the broader question of what, precisely, is required 3
Realizable Bayes-Consistency for General Metric Losses
4. Main result: characterization of H
for strong Bayes-consistency when the loss is unbounded. Accordingly, Tsir Cohen & Kontorovich (2022) posed the open problem of giving a necessary and sufficient condition on (X , ρ), (Y, ℓ), and µ̄ under which MedNet- or some other learning algorithm - is strongly Bayes-consistent. A natural and optimistic candidate was the finiteness of the Bayes risk, R∗ < ∞. In this section we show that this condition is not sufficient: without further assumptions, no strongly universally Bayes-consistent learner can exist.
We now state the main theorem, which characterizes when strong universal Bayes-consistency is achievable in the realizable setting under general (possibly unbounded) metric losses. The characterization is in terms of a single combinatorial obstruction: an unbounded-gap Littlestone tree. Definition 4.1 (non-decreasing-γk -Littlestone tree). Fix a non-decreasing sequence (γk )k≥1 with γk → ∞. A nondecreasing-γk -Littlestone tree for H (a metric-loss variant of the classical Littlestone tree (Littlestone, 1988); see also Bousquet et al. (2020, Definition 1.7)) is a rooted full binary tree whose internal nodes at depth k are labeled by instances xk,i ∈ X , and whose two outgoing edges from each such node are labeled by yk,i,1 , yk,i,2 ∈ Y satisfying ℓ(yk,i,1 , yk,i,2 ) ≥ γk , with the property that every finite rootto-leaf path is realizable by some h ∈ H (i.e., h matches the edge labels along that finite path). Definition 4.2 (realizable non-decreasing-γk -Littlestone tree). An infinite non-decreasing-γk -Littlestone tree is a tree of infinite depth satisfying the conditions of Definition 4.1 at every finite depth k. Such an infinite tree is realizable if, in addition to finite-prefix realizability, every infinite root-to-leaf path has its entire labeling realized by a single hypothesis in H (i.e., for each infinite path there exists h ∈ H matching all edge labels along that path). Lemma 4.3 (Bridging lemma: finite-prefix realizability implies infinite-path realizability). Suppose H satisfies the measurability condition of Bousquet et al. (2020, Definition 3.3) with a compact parameter space Θ and a function h : Θ × X → Y that is continuous in θ (i.e., θ 7→ h(θ, x) is continuous for each fixed x ∈ X ). Then every infinite non-decreasing-γk -Littlestone tree (Definition 4.1) is automatically realizable (Definition 4.2).
We will show that for any learning algorithm A, there exists a distribution µ, such that the expected risk (over the random given sample Sn ∼ µn ) of the learned hypothesis hn := A(Sn ) does not go to zero as sample size grows to ∞: E
Sn ∼µn
[R(A(Sn ))] ↛ 0 as n → ∞
Meaning that without further assumptions - no learner is strongly universally Bayes-consistent. Let X be the open interval (0, 1). Let Y = N0 := {0, 1, 2, . . . }, with the standard ℓ1 loss. Define for any k ∈ N : 1 1 Ik := , . 2k 2k−1 S Thus X = k∈N Ik . We look at the realizable case, with the uniform distribution µ over X , realized by the family of functions: H := f : ∀k ∈ N, ∀x ∈ Ik : f (x) ∈ 0, 22k+1 , thus defining the family of possible distributions on (X , Y). We now define a realizable distribution via an explicit product (coin-flip) construction. Let B = (Bk )k≥1 be i.i.d. fair bits, Bk ∼ Ber(1/2), and define fB ∈ H by ( 0 x ∈ Ik and Bk = 0, fB (x) := 2k+1 2 x ∈ Ik and Bk = 1. For each fixed B, let µ̄B be the distribution on X × Y given by X ∼ Unif(0, 1) and Y = fB (X). Then µ̄B is realizable by fB , hence R∗ (µ̄B ) = 0 < ∞. Thus, we observe this as a problem where the learner (learning algorithm) sees an i.i.d. sample Sn = {(X1 , Y1 ), . . . , (Xn , Yn )} ∼ µ̄nB and aims to output a predictor hn := A(Sn ) so as to minimize the risk: Rµ̄B (hn ) :=
E
Proof. The proof follows from the finite-intersection property of compact spaces; see Appendix A.4. Remark 4.4. Lemma 4.3 requires the compactparameterization assumption (compact Θ, h continuous in θ); we discuss in Appendix A.4 why this assumption is necessary in general, give a concrete example where the two tree notions differ without it, and argue that the assumption is mild and covers virtually all settings of practical interest. Theorem 4.5 (Main characterization). Assume (X , ρ) and (Y, ℓ) are Polish, and H satisfies the measurability condition of Bousquet et al. (2020, Definition 3.3) with compact Θ and h continuous in θ (cf. Lemma 4.3). Then the following are equivalent:
ℓ(hn (X), Y ).
(X,Y )∼µ̄B
The key point is that, conditional on any realized sample Sn , infinitely many intervals Ik remain unobserved, so Bk stays a fresh fair coin on each such interval. On Ik , at least one of the two possible labels {0, 22k+1 } must incur loss at least 2k (by the triangle inequality and integration over |Ik | = 2−k ), so with conditional probability at least 1/2 the interval contributes ≥ 2k to the risk. Independence across unseen k and Borel-Cantelli then force infinitely many such contributions, implying Rµ̄B (hn ) = ∞ almost surely. The full derivation is in Appendix A.6.
1. There exists a (distribution-free) learning rule A such that for every realizable distribution µ̄ on X × Y, the learned predictors hn := A(Sn ) satisfy Rµ̄ (hn ) → 0 4
almost surely as n → ∞.
Realizable Bayes-Consistency for General Metric Losses
2. H admits no infinite non-decreasing-(γk )-Littlestone tree (for any non-decreasing gap sequence (γk ) with γk → ∞).
“bad” coin outcome (the other label) occurs with conditional probability 1/2, independently across unseen depths. On that event the loss contribution is at least pm · m2 /2 = Θ(1). By the second Borel-Cantelli lemma, infinitely many such bad events occur almost surely, so Rµ̄B (hn ) = ∞ a.s. A Fubini argument over the random path B and a countable intersection over n ∈ N then yield, for the fixed learner A, a single distribution µ̄ with infinite expected risk at every sample size.
Proof. (1) =⇒ (2): Contrapositive: suppose an infinite non-decreasing-γk -Littlestone tree exists (Definition 4.1). By Lemma 4.3, the tree is automatically realizable (Definition 4.2). Theorem 5.1 then shows that no learner can be consistent. (2) =⇒ (1): If no such obstruction exists, then the explicit learner constructed in Section 6.5 is strongly universally Bayes-consistent for every realizable µ̄ (Theorem 6.5).
6. Upper bound: absence of an infinite tree implies strong universal consistency In this section we complete the argument that, under a suitable combinatorial condition on H, strong universal Bayesconsistent learning is possible in the realizable case, even when the loss is unbounded.
5. Lower bound: Existence of an infinite tree implies no consistency Theorem 5.1 (Lower bound). Let H be a hypothesis class that contains a realizable infinite non-decreasing-γk Littlestone tree with γk → ∞. Then, for any learning algorithm A, there exists a realizable distribution µ̄ such that the expected risk is infinite:
Proof roadmap. The upper bound proceeds in four steps: (1) we encode the tree obstruction as a Gale-Stewart game and invoke the measurable-strategy machinery of Bousquet et al. (2020) (Section 6.1); (2) we show that driving this game on an i.i.d. sample causes it to stabilize after finitely many rounds a.s., producing for each x a set of admissible labels HK (x) of bounded diameter (Sections 6.2-6.3); (3) we partition X into countably many cells, each with a common bounded label region (Section 6.4); (4) on each cell we apply the bounded-range learner MedNet of Tsir Cohen & Kontorovich (2022) and aggregate (Sections 6.5-6.6).
E [R(A(Sn ))] = ∞
Sn ∼µ̄n
for all n. In particular, no learner is consistent. Proof sketch; full proof in Appendix A.7. The argument generalizes the counterexample of Section 3: we construct a realizable distribution supported on selected tree nodes where the gap is large, then show every learner suffers infinite risk via a Borel-Cantelli argument on unseen nodes.
Standing measurability assumptions. To avoid measuretheoretic pathologies (measurable determinacy / measurable strategies and measurable selections), we assume that both (X , ρ) and (Y, ℓ) are Polish spaces. In particular, (Y, ℓ) is separable, hence admits a countable dense subset, which we will use to build a countable partition of X . In addition, we assume the hypothesis class H satisfies the measurability condition of Bousquet et al. (2020, Definition 3.3): there exists a Polish space Θ (the parameter space) and a Borel-measurable evaluation map h : Θ × X → Y, (θ, x) 7→ h(θ, x), such that H = {h(θ, ·) : θ ∈ Θ}. We strengthen this by requiring Θ to be compact and h to be continuous in θ (i.e., θ 7→ h(θ, x) is continuous for each fixed x ∈ X ; cf. Lemma 4.3, and see Appendix A.4 for a discussion of why this strengthening is needed and why it is mild), so that the game in Section 6.1 admits a universally measurable winning strategy for the learner. Whenever we define set-valued maps or indices using this strategy (e.g. Hk (·), jk (·), and the cells Ck,j ), we tacitly work with universally measurable versions so that these objects (and the final predictor) can be taken universally measurable.2
Distribution construction. Since γk → ∞, we can select depths k1 < k2 < · · · along the tree where γkm ≥ m2 . 2 Assign probability mass P pm ∝ 1/m to the depth-km node (normalized so that pm = 1). A random root-to-leaf path is drawn by tossing independent fair coins (Bk )k≥1 , one per tree level; the coin Bkm selects which of the two outgoing labels at depth km is the true label. Because the tree is realizable (Definition 4.2), the resulting distribution µ̄B is realizable by some fB⋆ ∈ H. Unseen depths act as fair coins. Fix any learner A and sample size n. A sample Sn ∼ µ̄nB can touch at most n of the countably many depths km , so all but finitely many remain unobserved. At each unseen depth km , the coin Bkm is independent of Sn , meaning the learner’s prediction hn (xkm ) is chosen with no information about the true label. Since the two candidate labels are at distance ≥ γkm ≥ m2 , the triangle inequality forces E[ℓ(hn (xkm ), Y ) | Sn ] ≥ m2 /2, regardless of what the learner predicts. Divergence via Borel-Cantelli. More precisely, whichever label the learner’s prediction is closer to, the
2 Concretely, this can be ensured by standard selection results on Polish spaces (e.g. Jankov-von Neumann type selection) applied
5
Realizable Bayes-Consistency for General Metric Losses
Intuitively, Hk (x) is the set of labels at x that the strategy σ never selects at the next round when paired with any sufficiently far feasible alternative.
6.1. A Gale-Stewart game Fix a non-decreasing sequence (γk )k≥1 with γk → ∞. The particular choice of diverging gap schedule is inessential: if H contains an infinite non-decreasing-gap tree whose gaps tend to ∞, then for any prescribed diverging sequence (γ̃m )m≥1 one can obtain an infinite non-decreasing-(γ̃m ) tree by passing to a subsequence of depths along which the original gaps exceed γ̃m (“skipping levels”). Consequently, the absence of an infinite non-decreasing-(γk ) tree for some diverging (γk ) is equivalent to the absence of any infinite unbounded-gap Littlestone tree obstruction.
Lemma 6.2 (Bounded diameter of history-conditional label sets). For every realizable history τk and every x ∈ X , diam(Hk (x)) :=
sup y,y ′ ∈H
ℓ(y, y ′ ) ≤ γk+1 .
k (x)
Proof. Suppose y, y ′ ∈ Hk (x) and ℓ(y, y ′ ) > γk+1 . Then the adversary may present (x, y, y ′ ) at round k+1 (this move is legal since y ∈ Vk (x)), in which case σ must choose one of y or y ′ , contradicting the defining property of Hk (x) for the chosen label. Therefore ℓ(y, y ′ ) ≤ γk+1 .
Now, we define an infinite Gale-Stewart game between an adversary PA and a learner PL . At round k = 1, 2, . . . :
6.3. Stabilization on an infinite i.i.d. sample
• PA chooses a triple (ξk , ηk,1 , ηk,2 ) ∈ X × Y × Y such that ℓ(ηk,1 , ηk,2 ) ≥ γk and such that there exists an h ∈ H consistent with the previous play and satisfying h(ξk ) ∈ {ηk,1 , ηk,2 }.
Let µ̄ be any realizable distribution on X × Y, realized by some f ∗ ∈ H. Let S∞ = ((Xi , Yi ))i≥1 ∼ µ̄∞ . We drive a simulation of the game using S∞ as follows. Maintain a current round counter k ≥ 0 and a current legal history. Scan i = 1, 2, . . . . If there exists a witness y ′ ∈ Y with ℓ(Yi , y ′ ) ≥ γk+1 such that (i) if the adversary plays (Xi , Yi , y ′ ) next then σ chooses Yi , and (ii) the extended history remains realizable by some hypothesis in H, then we advance the game: append that move and set k ← k + 1. Otherwise, do nothing and continue. Since σ is a winning strategy, the adversary cannot force an infinite legal play under σ. Thus along any outcome S∞ , the above procedure can advance only finitely many times. Let K∞ = K(S∞ ) < ∞ be the final round, and let τK∞ be the terminal history.
• PL chooses one of the two labels, denoted η̂k ∈ {ηk,1 , ηk,2 }. The learner wins if at some finite round the adversary has no legal move; otherwise the adversary wins (i.e., if play continues forever). Recall the definition of a non-decreasingγk -Littlestone tree from Definition 4.1. It is immediate that there exists an infinite non-decreasing-γk Littlestone tree iff PA has a winning strategy. Hence, if no such infinite tree exists, then PL has a winning strategy. Under the Polish assumptions, we fix a measurable winning strategy σ for PL . The existence of such a measurable strategy is explained in Appendix A.3, where we verify that the conditions of Bousquet et al. (2020, Theorem B.1) are met by our game.
Lemma 6.3 (True label is contained a.s. on a fresh draw). With probability one over S∞ ∼ µ̄∞ , for the terminal history τK∞ we have µ̄ {(x, y) : y ∈ / HK∞ (x)} = 0.
6.2. History-conditional label sets Definition 6.1 (History-conditional label sets). Let τk denote a finite history arising from a legal play under σ. Given such a history and a point x ∈ X , define the historyconditional feasible label set
Equivalently, conditional on S∞ , an independent test point (X, Y ) ∼ µ̄ satisfies Y ∈ HK∞ (X) almost surely. Proof. Fix an outcome S∞ for which the procedure stabilizes at K∞ with history τK∞ . Define E := {(x, y) : y ∈ VK∞ (x) and y ∈ / HK∞ (x)}. Since µ̄ is realizable by some f ∗ ∈ H and τK∞ is a realizable history (indeed consistent with f ∗ ), we have Y = f ∗ (X) ∈ VK∞ (X) almost surely for (X, Y ) ∼ µ̄, and hence µ̄ {(x, y) : y ∈ / HK∞ (x)} = µ̄(E).
Vk (x) := {y ∈ Y : ∃h ∈ H consistent with τk such that h(x) = y}, and the history-conditional label set Hk (x) := y ∈ Vk (x) : ∀y ′ ∈ Vk (x) with ℓ(y, y ′ ) ≥ γk+1 , σ does not choose y at round k+1 when presented with
By definition of HK∞ (x), for each (x, y) ∈ E there exists (ξk+1 , ηk+1,1 , ηk+1,2 ) = (x, y, y ′ ) . y ′ ∈ VK∞ (x) with ℓ(y, y ′ ) ≥ γK∞ +1 such that if the adversary plays (x, y, y ′ ) next, σ would choose y. Moreover, to the analytic sets arising from the legal-move relation and the strategy σ. since y ∈ VK∞ (x), there exists h ∈ H consistent with 6
Realizable Bayes-Consistency for General Metric Losses
Step 2: partition X using (qj ). Using τK , compute the set-valued map HK (·) and the induced mapping jK (·), hence the cell sets CK,j and bounded label regions YK,j .
τK∞ with h(x) = y, so the extended history after appending (x, y, y ′ ) and choosing y remains realizable. Therefore, whenever a sample point (Xi , Yi ) falls in E (with the terminal history fixed), that point is eligible to advance the game (using its witness y ′ ), contradicting stabilization unless this happens only finitely often. If µ̄(E) > 0, then by BorelCantelli for i.i.d. samples, (Xi , Yi ) ∈ E occurs infinitely often almost surely, contradiction. Hence µ̄(E) = 0.
(2)
For each j, let Sn,j denote the subsequence of the second(2)
half sample Sn consisting of those examples with Xi ∈ CK,j . Then, run the metric-loss learner MedNet of Tsir Cohen & Kontorovich (2022) (restricted to the label re(2) gion YK,j ) on Sn,j and on the restricted hypothesis class H|CK,j := {h|CK,j : h ∈ H}, and denote the resulting predictor by fbn,j : CK,j → YK,j .
6.4. Reducing per-x bounded diameter to countably many bounded-range subproblems Lemma 6.2 gives that each HK∞S(x) has diameter at most γK∞ +1 . However, the union x HK∞ (x) need not be bounded, so we cannot directly invoke a single boundeddiameter learning algorithm. We resolve this by partitioning X into countably many regions, each with a common bounded label region. Fix a countable dense subset {q1 , q2 , . . . } ⊆ Y. This is guaranteed to exist by the fact that Y is Polish. For a given history τk , define for each x ∈ X the index n o jk (x) := min j ∈ N : ∃y ∈ Hk (x) with ℓ(y, qj ) ≤ γk+1 .
(2) If Sn,j is empty, define fbn,j (x) ≡ qj on CK,j .
Output predictor.
fbn (x) := fbn,jK (x) (x). Operationally, one need not explicitly construct the whole partition: on input x, compute jK (x) and use only those (2) training points in Sn lying in the same cell. The sense in which this learning rule is “explicit” - given a measurable winning strategy σ - is discussed in Appendix A.2.
(Existence follows from density of (qj ) and nonemptiness of Hk (x) on legal F positions.) This induces a countable partition X = j≥1 Ck,j where Ck,j := {x : jk (x) = j}. For each cell define a bounded label region
6.6. Realizable strong universal Bayes-consistency Theorem 6.5 (Realizable upper bound). Assume that H admits no infinite non-decreasing-γk -Littlestone tree for some non-decreasing gap sequence (γk ) with γk → ∞. Assume (X , ρ) and (Y, ℓ) are Polish. Let µ̄ be any distribution on X × Y realizable by some f ∗ ∈ H.
Yk,j := {y ∈ Y : ℓ(y, qj ) ≤ 2γk+1 }. Lemma 6.4 (Cell-wise bounded range). For every k, j and every x ∈ Ck,j , we have Hk (x) ⊆ Yk,j . Consequently, if µ̄({(x, y) : y ∈ Hk (x)}) = 1 then µ̄(Y ∈ Yk,j | X ∈ Ck,j ) = 1 for every j with µ̄(X ∈ Ck,j ) > 0.
Then the learning rule Sn 7→ fbn defined in Section 6.5 is strongly universally Bayes-consistent in the realizable sense: Rµ̄ (fbn ) → 0
Proof. Fix x ∈ Ck,j . By definition, there exists yx ∈ Hk (x) with ℓ(yx , qj ) ≤ γk+1 . For any y ∈ Hk (x), Lemma 6.2 gives ℓ(y, yx ) ≤ γk+1 . Hence by triangle inequality, ℓ(y, qj ) ≤ ℓ(y, yx ) + ℓ(yx , qj ) ≤ 2γk+1 , so y ∈ Yk,j .
almost surely as n → ∞.
Proof. Fix a realizable distribution µ̄ realized by some f ∗ ∈ H, and couple all learned predictors to an i.i.d. infinite sample S∞ = ((Xi , Yi ))i≥1 ∼ µ̄∞ . For each even n = 2m, (1) the learning rule of Section 6.5 uses the first half S2m = m ((Xi , Yi ))i=1 to drive the game simulation and the second (2) half S2m = ((Xi , Yi ))2m i=m+1 to learn within cells. Since (1) (2) S2m and S2m are disjoint blocks of an i.i.d. sequence, these halves are independent. (Odd n can be handled by ignoring one sample; it suffices to prove convergence along the even subsequence.) The proof is organized into four steps.
6.5. A realizable learning rule We now define a distribution-free learning rule. Input. A labeled sample Sn = ((Xi , Yi ))ni=1 ∼ µ̄n from a realizable distribution µ̄ realized by some f ∗ ∈ H. Step 1: drive the game on half the sample. Split the (1) ⌊n/2⌋ (2) sample into two halves, Sn = ((Xi , Yi ))i=1 and Sn = n ((Xi , Yi ))i=⌊n/2⌋+1 . Run the stabilization procedure of Sec(1)
Define fbn : X → Y by
Step 1: stabilization and eventual agreement with the terminal history. Run the stabilization procedure of Section 6.3 on the entire infinite prefix ((Xi , Yi ))i≥1 . Since σ is a winning strategy, the procedure advances only finitely many times almost surely; denote by K∞ = K(S∞ ) < ∞
(1)
tion 6.3 on Sn , producing a terminal round K = K(Sn ) and terminal history τK . 7
Realizable Bayes-Consistency for General Metric Losses (2) S2m,j , yielding a predictor fb2m,j . Since µ̄ is realizable by ∗ f ∈ H, the restricted target f ∗ |CK,j is realizable by the restricted class H|CK,j , and by (3) the conditional problem on CK,j has bounded loss (hence is BIE). Therefore, by the strong universal Bayes-consistency guarantee of MedNet for metric losses on BIE label spaces (Tsir Cohen & Kontorovich, 2022), we have
the final round and by τK∞ the resulting terminal history. On the fixed sample path S∞ , let N0 = N0 (S∞ ) be an index large enough that, after scanning (Xi , Yi ) for i ≤ N0 , the procedure has already made all of its (finitely many) advances, and no further sample point (Xi , Yi ) with i > N0 can advance the game beyond round K∞ . Such an N0 exists because the procedure advances only finitely often. Now consider running the same procedure on a finite prefix of length m. For every m ≥ N0 , the run on ((Xi , Yi ))m i=1 must produce exactly the same terminal round and history, i.e. (1)
K(S2m ) = K∞
and
τK(S (1) ) = τK∞ .
Rµ̄j (fb2m,j ) → 0
(4)
(2)
(When S2m,j is empty, the rule outputs the default qj ; this case occurs only finitely often a.s. when pj > 0, and does not affect the limit.) Since there are countably many cells, we may intersect the probability-one events in (4) over all j ∈ N to obtain a single probability-one event on which (4) holds for every j simultaneously (cells with pj = 0 are irrelevant).
(1)
2m
Indeed, by definition of N0 there is no admissible advancement step after index N0 , so truncating the scan at any m ≥ N0 cannot remove an advance that occurs after N0 (there are none), nor can it create new advances. By Lemma 6.3, for the terminal history τK∞ we have µ̄ {(x, y) : y ∈ / HK∞ (x)} = 0. (2)
Step 4: aggregate risk and conclude. For even n = 2m large enough that (1) holds, the overall predictor satisfies fb2m (x) = fb2m,j (x) when x ∈ CK,j . Decomposing the risk by the partition, X Rµ̄ (fb2m ) := pj Rµ̄j (fb2m,j ). (5)
Combining (1) and (2), we obtain that on every sample path S∞ in this probability-one event, for all sufficiently large even n = 2m (namely, m ≥ N0 (S∞ )) the data-driven set map HK(S (1) ) (·) used by the learner coincides with 2m HK∞ (·) and thus contains the true label Y almost surely on an independent test draw.
j≥1
P
Fix j≥1 pj = 1, choose J so that P ε > 0. Since p < ε. On the probability-one event where (4) holds j>J j for all j ≤ J, choose m large enough that Rµ̄j (fb2m,j ) < ε for every j ≤ J. Then, using (3) to bound each conditional risk by 4γK+1 , X X Rµ̄ (fb2m ) ≤ pj ε + pj (4γK+1 ) ≤ ε + 4γK+1 ε.
Step 2: countable partition and bounded label regions. Fix such a sample path S∞ and write K := K∞ . Using the dense set (qj )j≥1 , define the countable partition {CK,j }j≥1 and bounded regions YK,j as in Section 6.4. By Lemma 6.4 and (2), for every j with pj := µ̄(X ∈ CK,j ) > 0 the conditional distribution µ̄j := µ̄(· | X ∈ CK,j ) is supported on Xj × YK,j , where Xj := CK,j , and in particular ℓ(y, y ′ ) ≤ diam(YK,j ) ≤ 4γK+1
almost surely as m → ∞.
j≤J
j>J
Since K is fixed on the sample path, γK+1 < ∞, and because ε > 0 was arbitrary, this shows Rµ̄ (fb2m ) → 0 almost surely along the even subsequence. The full sequence Rµ̄ (fbn ) also converges to 0 almost surely because Rµ̄ (fb2m ) → 0 implies lim supn→∞ Rµ̄ (fbn ) = 0 (e.g., by considering the nearest even index and noting the construction differs only by O(1) samples). This completes the proof.
∀ y, y ′ ∈ YK,j . (3)
Thus, within each cell the loss is bounded by the finite constant 4γK+1 (which depends on the realized terminal round K but is finite on the fixed sample path). Step 3: strong consistency within each cell. Consider any fixed j with pj > 0. The second half samples (2) S2m = ((Xi , Yi ))2m i=m+1 are i.i.d. from µ̄ and independent of the first half, hence independent of the (eventually (2) fixed) partition. Let S2m,j denote the subsequence of those examples with Xi ∈ CK,j . Conditional on Xi ∈ CK,j , these examples are i.i.d. from µ̄j . Moreover, since pj > 0, (2) the number Nm,j := |S2m,j | satisfies Nm,j → ∞ almost surely as m → ∞ (by the strong law of large numbers for Bernoulli indicators of the event {X ∈ CK,j }). On cell j, the learning rule runs MedNet (restricted to YK,j ) using
References Attias, I., Hanneke, S., Kalavasis, A., Karbasi, A., and Velegkas, G. Optimal learners for realizable regression: Pac learning and online learning, 2024a. URL https: //arxiv.org/abs/2307.03848. Attias, I., Hanneke, S., Kalavasis, A., Karbasi, A., and Velegkas, G. Universal Rates for Regression: Separations between Cut-Off and Absolute Loss. In Proceedings of Thirty Seventh Conference on Learning Theory, pp. 359–405. PMLR, 8
Realizable Bayes-Consistency for General Metric Losses
Example 1: a class that admits an unbounded-gap tree (not learnable). The counterexample of Section 3 implicitly constructs an unbounded-gap Littlestone tree. Recall H = {f : ∀k ∈ N, f (x) ∈ {0, 22k+1 } for x ∈ Ik }, where Ik = (2−k , 2−(k−1) ). The tree is built as follows: at depth k, place the instance xk at any point of Ik , and assign the two outgoing labels yk,1 = 0 and yk,2 = 22k+1 . The gap is ℓ(yk,1 , yk,2 ) = 22k+1 → ∞. Because the intervals (Ik )k≥1 are pairwise disjoint, the label choices at different depths are independent: for every root-to-leaf path (finite or infinite), the hypothesis in H that makes the corresponding binary choice on each interval realizes it. This is a realizable non-decreasing-γk -Littlestone tree with γk = 22k+1 (Definitions 4.1–4.2), and Theorem 5.1 shows that no learner can be consistent.
June 2024b. URL https://proceedings.mlr. press/v247/attias24a.html. ISSN: 26403498. Bousquet, O., Hanneke, S., Moran, S., van Handel, R., and Yehudayoff, A. A theory of universal learning, 2020. URL https://arxiv.org/abs/2011.04483. Brukhim, N., Carmon, D., Dinur, I., Moran, S., and Yehudayoff, A. A Characterization of Multiclass Learnability, March 2022. URL http://arxiv.org/abs/ 2203.01550. arXiv:2203.01550 [cs]. Gottlieb, L., Kontorovich, A., and Krauthgamer, R. Efficient classification for metric data (extended abstract COLT 2010). IEEE Transactions on Information Theory, 60(9):5750–5759, 2014. doi: 10.1109/TIT.2014. 2339840. URL http://dx.doi.org/10.1109/ TIT.2014.2339840.
The mechanism is instructive: the disjoint intervals allow the adversary to “hide” independent binary choices at geometrically increasing loss scales. On any finite sample only finitely many intervals are observed, so the learner must guess blindly on unseen intervals where the potential loss is enormous. This is precisely the rare-event failure mode that the tree obstruction captures.
Gottlieb, L.-A. and Krauthgamer, R. Proximity algorithms for nearly doubling spaces. SIAM J. Discrete Math., 27 (4):1759–1769, 2013. Hanneke, S., Kontorovich, A., Sabato, S., and Weiss, R. Universal bayes consistency in metric spaces, 2021. URL https://arxiv.org/abs/1906.09855.
Example 2: a class without an unbounded-gap tree (learnable). Let X = [0, 1], Y = R, ℓ(y, y ′ ) = |y − y ′ |, and let H = {f : [0, 1] → R : f is L-Lipschitz} for a fixed constant L > 0. This class has unbounded range (since f (0) is unconstrained), yet it admits no infinite non-decreasingγk -Littlestone tree with γk → ∞.
Hanneke, S., Moran, S., and Zhang, Q. Universal Rates for Multiclass Learning, July 2023. URL http://arxiv. org/abs/2307.02066. arXiv:2307.02066 [cs]. Littlestone, N. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2(4):285–318, 1988. doi: 10.1007/ BF00116827.
To see why, suppose an adversary attempts to build such a tree. At depth 1, the adversary may present any instance x1 ∈ [0, 1] with two labels y1,1 , y1,2 arbitrarily far apart (two L-Lipschitz functions with different “offsets” can disagree by any amount at a single point). But once the learner commits to a label v1 at x1 , every LLipschitz function consistent with this choice must satisfy |f (x) − v1 | ≤ L|x − x1 | ≤ L for all x ∈ [0, 1]. Hence, at any depth k ≥ 2, the gap between the two proposed labels is at most 2L. Since γk → ∞, eventually γk > 2L, and the adversary has no legal move. Therefore no infinite unbounded-gap tree exists, and by Theorem 4.5 a strongly universally Bayes-consistent learner exists for this class.
Tsir Cohen, D. and Kontorovich, A. Learning with metric losses. In Loh, P.-L. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 662–700. PMLR, 02–05 Jul 2022. URL https://proceedings.mlr.press/ v178/cohen22a.html.
A. Supplementary material
Discussion. Any hypothesis class with bounded range (suph∈H, x∈X ℓ(h(x), y0 ) < ∞ for some y0 ∈ Y) trivially has no infinite unbounded-gap tree. The Lipschitz example above shows that even unbounded-range classes can be tree-free when a regularity condition (here, the Lipschitz constraint on a compact domain) prevents the adversary from sustaining arbitrarily large label gaps.
A.1. Practical significance and examples Our characterization applies to any hypothesis class H ⊆ Y X over Polish spaces. A natural question is: which commonly studied classes satisfy tree-free condition (i.e., admitting no infinite non-decreasing-(γk )-Littlestone tree with γk → ∞) and thus admit realizable strong universal Bayesconsistency (RSUBC)? We give one positive and one negative example to build intuition.
Compactness of the domain is essential: the class of LLipschitz functions on all of R does admit an infinite 9
Realizable Bayes-Consistency for General Metric Losses
each finite prefix the legality condition “∃ h ∈ H consistent with history” is expressible as a projection over the Polish parameter space Θ from Definition 3.3. Hence Theorem B.1 applies directly.
unbounded-gap tree (the adversary can spread instances apart to create growing gaps). Similarly, the class of all monotone non-decreasing functions from [0, 1] to R admits such a tree despite the monotonicity constraint: the adversary places instances x1 < x2 < · · · in [0, 1] and at each depth k offers labels v and v + γk (where v is the previously committed value), which is always consistent with monotonicity. These contrasting examples illustrate that the tree obstruction captures a subtle interplay between the hypothesis class structure, the loss geometry, and the domain geometry, going beyond simple boundedness conditions.
A.4. On the compact-parameterization assumption In Theorem 4.5 the characterization is stated in terms of the finite-prefix tree notion (Definition 4.1), while the lower bound (Theorem 5.1) requires every infinite path through the tree to be realized by a single hypothesis (Definition 4.2). Lemma 4.3 bridges this gap under the compactparameterization assumption.
A.2. On the constructive nature of the learning rule
A.4.1. P ROOF OF L EMMA 4.3
The learning rule of Section 6.5 is “explicit” in the following sense: given access to a measurable winning strategy σ for PL in the Gale-Stewart game, the algorithm’s steps (drive the game on half the data, partition X using the terminal history, run MedNet per cell) are fully concrete and datadependent.
Proof. Fix an infinite path b = (b1 , b2 , . . .) ∈ {1, 2}N through the tree. For each finite prefix of length k, finiteprefix realizability gives a parameter θk ∈ Θ such that h(θk , xj ) = yj,bj for all j ≤ k. Define Θk (b) = θ ∈ Θ : h(θ, xj ) = yj,bj for all j ≤ k .
The existence (and universal measurability) of σ itself is guaranteed by Bousquet et al. (2020, Corollary 3.5) via a non-constructive determinacy argument (their Theorem B.1). This parallels the situation in Bousquet et al. (2020), whose universal learner for 0–1 classification also relies on a measurable winning strategy whose existence follows from determinacy. As noted in their Section 3.4, for hypothesis classes with countable ordinal Littlestone dimension, the strategy σ can be described explicitly via transfinite induction on the ordinal dimension. Any measurable H has at most countable ordinal Littlestone dimension (Bousquet et al., 2020, Lemma B.7), so in principle the strategy admits a concrete (if complex) description for any class encountered in practice.
Each Θk (b) is non-empty (it contains θk ) and closed (the preimage of the closed set {yj,bj } under the map θ 7→ h(θ, xj ), which is continuous in θ by assumption, intersected over finitely many j). Moreover Θ1 (b) ⊇ Θ2 (b) ⊇ · · · is a decreasing chain of non-empty closed subsets of the compact space Θ. Because the chain is decreasing, every Tm finite sub-collection Θk1 (b), . . . , Θkm (b) satisfies i=1 Θki (b) = Θmaxi ki (b) ̸= ∅, so the family {Θk (b)}k≥1 has the finite-intersection property. Since each Θk (b) is a closed T subset of the compact space Θ, compactness implies k≥1 Θk (b) ̸= ∅. Any θ∗ in this intersection satisfies h(θ∗ , xj ) = yj,bj for all j, so h(θ∗ , ·) ∈ H realizes the entire infinite path b.
A.3. Measurability of the winning strategy
A.4.2. W HY THE ASSUMPTION IS NECESSARY
The existence of a universally measurable winning strategy σ for PL follows from Bousquet et al. (2020, Corollary 3.5), which establishes that under Polish space assumptions and measurability of the concept class (in the sense of their Definition 3.3), any Gale-Stewart game with a finitely decidable winning condition admits a universally measurable winning strategy for the learner.
Without the compact-parameterization assumption, the two tree notions can differ. Consider the following example. Setup. Let Θ = N0 (the non-negative integers with the discrete topology, which is Polish), X = {xk : k ∈ N} (countable, discrete), Y = R with ℓ(y, y ′ ) = |y − y ′ |, and define
The underlying Theorem B.1 of Bousquet et al. (2020) requires the learner’s response sets {Yt } to be countable. In our game, PL selects an index from {1, 2} (choosing one of the two proposed labels), so each Yt = {1, 2} is countable; the adversary’s move spaces Xt = X × Y × Y are Polish. The winning condition is finitely decidable (the game ends when PA has no legal move), and coanalyticity of the winning set W follows by the same projection argument as in the proof of Bousquet et al. (2020, Corollary 3.5): the complement W c (play continues forever) is analytic, since at
h(n, xk ) = (k-th binary digit of n) · k, so that H = {hn : n ∈ N0 } where hn (·) = h(n, ·). A Definition 4.1 tree exists. At depth k, place instance xk with labels yk,1 = 0 and yk,2 = k; the gap is ℓ(0, k) = k → ∞, so the gaps are non-decreasing and divergent. Every finite path (b1 , . . . , bK ) ∈ {1, 2}K is realized by PK n = k=1 1[bk = 2] · 2k−1 (set the k-th binary digit of n to 1 iff bk = 2). 10
Realizable Bayes-Consistency for General Metric Losses
Not every infinite path is realizable. The all-2 path, bk = 2 for all Pk, requires n whose every binary digit equals 1, i.e. n = k≥1 2k−1 = ∞. No finite integer has this property, so no hn ∈ H realizes this infinite path.
A.4.4. E XAMPLES OF SETTINGS SATISFYING THE ASSUMPTION
• Finite or compact label spaces. When Y is compact (e.g., binary classification with Y = {0, 1}, multiclass classification with finite Y, or bounded regression with Y = [a, b]), the function space Y X is compact in the product topology by Tychonoff’s theorem, and the classical compactness argument of Bousquet et al. (2020) shows that the two tree notions coincide automatically. Our compact-parameterization assumption is not needed in this case and is strictly weaker than compactness of Y.
Yet H is RSUBC. Each hn has only finitely many non-zero values (since n has finitely many binary digits equal to 1). The memorize-and-predict-0 learner achieves risk → 0 for every strictly realizable distribution (since f ⋆ has finite support, every support point is eventually observed). In fact, the same learner also succeeds under non-strict realizability; see Section A.4.5.
• Parametric families with bounded parameters. Neural networks with bounded weights, support vector machines with bounded kernels, and Lipschitz functions on compact domains all naturally have compact parameter spaces (e.g., Θ = [−W, W ]d ) and continuous evaluation maps.
This example shows that a Definition 4.1 tree can coexist with RSUBC. Hence the lower bound cannot be proved from Definition 4.1 alone; the gap between the two definitions is genuine. Note that Θ = N0 is not compact (it is discrete and infinite), so the compact-parameterization assumption of Lemma 4.3 does not hold.
• The counterexample is pathological. The separating example of Section A.4.2 uses Θ = N0 (discrete, noncompact) and a discontinuous evaluation map. Classes parametrized by a countably infinite discrete space with no accumulation points are unusual in practical learning settings. In contrast, the compact-parameterization assumption permits Θ to be any compact Polish space, which includes all compact subsets of Rd , compact manifolds, and many infinite-dimensional spaces (e.g., compact subsets of function spaces in the compactopen topology).
A.4.3. T HE ASSUMPTION DOES NOT RULE OUT UNLEARNABILITY
The compact-parameterization assumption does not restrict Y to be bounded, and unlearnability remains possible even when the assumption holds. The label space Y remains a general (possibly unbounded) Polish space, and the label gaps along the tree can still diverge (γk → ∞), preserving the unbounded-loss character of the characterization. What the assumption ensures is that, for each fixed instance x, the achievable label set {h(θ, x) : θ ∈ Θ} is compact in Y; however, the diameter of this set may grow without bound as x varies.
A.4.5. R EALIZABILITY WITHOUT COMPACTNESS This paper defines realizability as inf h∈H Rµ̄ (h) = 0 (nonstrict realizability). Without the compact-parameterization assumption, this does not guarantee the existence of a hypothesis attaining zero risk, and two natural notions of realizability can diverge:
The motivating counterexample of Section 3 demonstrates this concretely. Recall H = {f : ∀k ∈ N, f (x) ∈ {0, 22k+1 } for x ∈ Ik }, where Ik = (2−k , 2−(k−1) ). Each function in H is determined by a binary sequence θ = (θ1 , θ2 , . . .) ∈ {0, 1}N , where θk selects whether f maps Ik to 0 or to 22k+1 . Thus the natural parameter space is Θ = {0, 1}N , which is compact (by Tychonoff’s theorem, as a countable product ofPfinite spaces) and Polish (the prod−k uct metric d(θ, θ′ ) = |θk − θk′ | is complete and k2 separable). The evaluation map h(θ, x) = θk · 22k+1 for x ∈ Ik is continuous in θ (it depends only on the k-th coordinate, which is a continuous projection in the product topology).
1. Strict realizability: there exists f ⋆ ∈ H such that Y = f ⋆ (X) almost surely, i.e. some hypothesis in H attains zero risk. 2. Non-strict realizability (the definition used in this paper): inf h∈H Rµ̄ (h) = 0, i.e. the Bayes risk is zero but no single hypothesis need attain it. Under the compact-parameterization assumption (compact Θ, h continuous in θ), the image H = {h(θ, ·) : θ ∈ Θ} is compact in the product topology on Y X . If inf h∈H Rµ̄ (h) = 0, a risk-minimizing sequence θn in the compact space Θ has a convergent subsequence θnj → θ⋆ , and continuity gives Rµ̄ (h(θ⋆ , ·)) = 0, so the infimum is attained and the two definitions coincide.
Yet the label gaps at depth k of the corresponding Littlestone tree are γk = 22k+1 → ∞, so the class admits an unbounded-gap tree and is not RSUBC by Theorem 5.1. In other words, the compact-parameterization assumption is compatible with the full range of unlearnability phenomena captured by our characterization. 11
Realizable Bayes-Consistency for General Metric Losses
A.5. Barriers to the agnostic extension
Without compactness the infimum may not be attained. Consider X = N (discrete), Y = N0 with ℓ1 loss, and H = {h : N → N0 : supp(h) is finite}. Let g : N → N0 be any function with infinite support (e.g. g(k) = k), and let µ̄ be the distribution with X ∼ µX supported on all of N (e.g. µX ({k}) = c/k 3 for a normalizing constant c) and Y = g(X). Defining P hN (k) = g(k)1k≤N gives hN ∈ H with Rµ̄ (hN ) = k>N µX ({k}) |g(k)|. For this H, nonstrict realizability (inf h∈H Rµ̄ (h) P= 0) is in fact equivalent to the first-moment condition k µX ({k}) |g(k)| < ∞: convergence of the series implies the tails vanish, while divergence forces every h ∈ H (having finite support) to incur infinite risk. When the first moment holds, Rµ̄ (hN ) → 0, so inf h∈H Rµ̄ (h) = 0. Yet g ∈ / H (infinite support), so no f ⋆ ∈ H achieves zero risk: µ̄ is non-strictly realizable but not strictly realizable.
Our characterization addresses the realizable setting: the data-generating distribution µ̄ is assumed to be realizable (inf h∈H Rµ̄ (h) = 0). A natural follow-up is whether the characterization extends to the agnostic setting, where µ̄ may not be realizable. The key obstacle lies in the upper-bound argument. The stabilization procedure (Section 6.3) drives the Gale-Stewart game using sample points (Xi , Yi ) and crucially relies on the fact that Yi = f ⋆ (Xi ) ∈ Vk (Xi ) (the true label is feasible given the current history). In the agnostic setting, labels need not come from any h ∈ H, so sample points may not constitute legal moves in the game, and the stabilization argument breaks down. Moreover, the counterexample of Section 3 shows that the natural distributional condition R⋆ < ∞ is insufficient even in the realizable setting. In the agnostic case, one would need to simultaneously handle approximation error (the gap between R⋆ and 0) and the unbounded-scale estimation difficulty, likely requiring a fundamentally different characterization. The agnostic counterpart of our result is an interesting open problem (connected to the open question originally posed by Tsir Cohen & Kontorovich (2022)) left for future work.
Despite this gap, the memorize-and-predict-0 learner succeeds under both realizability notions. Under strict realizability the argument is immediate (f ⋆ has finite support, so every support point is eventually observed). Under non-strict realizability, the learner’s risk P is k µX ({k}) |g(k)| 1{k ∈ / {X1 , . . . , Xn }}; each atom with µX ({k}) > 0 is eventually observed almost surely, and the terms are dominated by the summable µX ({k}) |g(k)|, so dominated convergence gives Rµ̄ (A(Sn )) → 0 almost surely.
A.6. Counterexample: infinite risk on unseen intervals
Since this paper assumes the compact-parameterization condition throughout, the two notions coincide for all results stated here, and readers may treat them interchangeably.
We include here the calculation deferred from Section 3 showing that, conditional on any realized sample, the learned predictor suffers infinite risk almost surely.
A.4.6. O PEN QUESTION : REMOVING COMPACTNESS
We now show that this forces infinite risk: conditional on any realized sample, infinitely many unseen intervals incur arbitrarily large loss. Define the (random) set of observed interval indices
Whether the characterization of Theorem 4.5 can be extended to general Polish Θ (without compactness) is an interesting open problem. We know that Definition 4.1 (finite-prefix realizability) is not the correct obstruction in the general case. The separating example of Section A.4.2 demonstrates this: the class H = {h : N → N0 : supp(h) is finite} admits a Definition 4.1 tree with γk = k → ∞, yet not every infinite branch is realizable (the all-nonzero branch requires infinite support), and the class is nevertheless RSUBC. Thus the finite-prefix tree obstruction produces false positives without the compact-parameterization assumption. A complete characterization in the non-compact setting would likely require a different tree notion; one possible direction is a coin-realizable variant, in which a randomly drawn infinite branch is realizable with probability one, rather than requiring every deterministic branch to be realizable. Finding the minimal topological or measure-theoretic conditions (weaker than compactness) under which the finiteintersection argument of Lemma 4.3 still holds remains open.
I(Sn ) := {k ∈ N : ∃i ≤ n with Xi ∈ Ik }. Condition on a realized sample Sn . Then hn = A(Sn ) is fixed, and for every unseen interval k ∈ / I(Sn ) the bit Bk remains an independent fair coin under the conditional law (since no sample point fell in Ik ). Write the contribution of interval Ik to the risk as Z
ℓ hn (x), fB (x) dx
Rk (Bk ) := I
(Rk =
RIk Ik
|hn (x)| dx |hn (x) − 2
(Bk = 0), 2k+1
| dx
(Bk = 1).
By the triangle inequality, for every x ∈ Ik , |hn (x)| + 12
Realizable Bayes-Consistency for General Metric Losses
|hn (x) − 22k+1 | ≥ 22k+1 . Integrating over Ik yields Z Z |hn (x)| dx + |hn (x) − 22k+1 | dx ≥ |Ik | · 22k+1 Ik
the maximum index m such that the sample contains a point with X = xkm (B) (take M (Sn ) = 0 if none). Then M (Sn ) < ∞ deterministically, as it is the maximum of n positive integers (though M (Sn ) is random and not bounded by any fixed constant uniformly over B).
Ik
= 2−k · 22k+1 = 2k+1 .
Consider any m > M (Sn ). Conditional on Sn and the path history up to depth km −1, the node xkm (B) and its two labels ykm ,1 (B), ykm ,2 (B) are fixed, while Bkm is still a fair coin. Thus, by the triangle inequality, Sn , (Bj )j<km E ℓ hn (xkm (B)), Y = 12 ℓ hn (xkm (B)), ykm ,1 (B) + 12 ℓ hn (xkm (B)), ykm ,2 (B) ≥ 21 ℓ ykm ,1 (B), ykm ,2 (B)
Hence at least one of the two displayed integrals is at least 2k , so P(Rk (Bk ) ≥ 2k | Sn ) ≥ 21 . Since the events {Rk (Bk ) ≥ 2k } over k ∈ / I(Sn ) are independent conditional on Sn , the second Borel-Cantelli lemma implies that almost surely (over the bits B conditional on Sn ) infinitely many unseen k satisfy Rk (Bk ) ≥ 2k . Therefore, X X Rµ̄B (hn ) = Rk (Bk ) ≥ 2k k∈I(S / n) Rk (Bk )≥2k
k≥1
=∞
γk m 2 m2 ≥ 2 .
≥
almost surely (over B conditional on Sn ).
Taking expectations over the joint draw (B, Sn ) and applying Fubini, we obtain: for each fixed n, for P-almost every B we have PSn ∼µ̄nB (Rµ̄B (A(Sn )) = ∞) = 1, hence ESn ∼µ̄nB [Rµ̄B (A(Sn ))] = ∞. Finally, taking a countable intersection over n ∈ N, there exists a single fixed B ⋆ (equivalently, a single fixed f ⋆ = fB ⋆ ∈ H) such that for the fixed realizable distribution µ̄ := µ̄B ⋆ , for all n ∈ N. E Rµ̄ (A(Sn )) = ∞
For each m > M (Sn ), define bbad m := arg max ℓ hn (xkm (B)), ykm ,b (B)
b∈{1,2}
(break ties arbitrarily), and the event Em := {Bkm = bbad m }. Since Bkm is a fresh fair coin conditional on Sn and (Bj )j<km , we have
Sn ∼µ̄n
P(Em | Sn , (Bj )j<km ) = 12 ,
A.7. Proof of Theorem 5.1
and on Em ,
Proof. Fix a realizable infinite non-decreasing-γk Littlestone tree as in Definition 4.2. Since γk → ∞, for each m ≥ 1 define an index
ℓ hn (xkm (B)), Y = ℓ hn (xkm (B)), ykm ,Bkm (B) ≥ 21 ℓ ykm ,1 (B), ykm ,2 (B) 2
≥ m2 .
km := min{k ≥ 1 : γk ≥ m2 }, which is finite and non-decreasing in m (and strictly increas6 1 ing P after removing duplicates). Let pm := π2 · m2 , so that p = 1. Now sample a random infinite root-to-leaf m≥1 m path by drawing i.i.d. fair bits (Bk )k≥1 , Bk ∈ {1, 2}. For each outcome B, let µ̄B be the distribution supported on the path nodes at depths (km ): Pµ̄B X = xkm (B) = pm ,
Moreover, conditional on Sn and the full path history (Bj )j≥1 except for the coordinates {Bkm : m > M (Sn )}, the bits {Bkm : m > M (Sn )} are independent fair coins. Hence, by (conditional) Borel-Cantelli, P(Em i.o. | Sn ) = 1. Therefore, almost surely, X Rµ̄B (hn ) = pm ℓ hn (xkm (B)), ykm ,Bkm (B) m≥1
Y = ykm ,Bkm (B) (deterministically).
X
≥
Here xkm (B) denotes the depth-km instance on the path determined by B1 , . . . , Bkm −1 , and ykm ,1 (B), ykm ,2 (B) are the two outgoing edge labels at that node. By realizability of the tree, for every B there exists fB⋆ ∈ H realizing the entire path; in particular Y = fB⋆ (X) almost surely under µ̄B , so µ̄B is realizable.
pm ·
m>M (Sn )
=
3 π2
X
m2 1{Em } 2
1{Em }
m>M (Sn )
= ∞. In particular, for each fixed n, PB,Sn Rµ̄B (A(Sn )) = ∞ = 1, so by Fubini, for PB -almost every B we have
Fix any learning algorithm A and any n. Draw B and then Sn ∼ µ̄nB , and let hn := A(Sn ). Let M (Sn ) be 13
Realizable Bayes-Consistency for General Metric Losses
ESn ∼µ̄nB [Rµ̄B (A(Sn ))] = ∞. Taking a countable intersection over n ∈ N of these probability-one sets of B, we may fix a single B ⋆ such that the expected risk is infinite for all n. Setting µ̄ := µ̄B ⋆ completes the proof.
14