Realizable Bayes-Consistency for General Metric Losses

arXiv:2605.03823v1 Announce Type: new Abstract: We study strong universal Bayes-consistency in the realizable setting for learning with general metric losses, extending classical characterizations beyond 0-1 classification itep{bousquet_theory_2021, hanneke2021universalbayesconsistencymetric} and real-valued regression itep{attias_universal_2024}. 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 itet{pmlr-v178-cohen22a}. 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 itet{attias2024optimallearnersrealizableregression}, we introduce the notion of an infinite non-decreasing (gamma_k)-Littlestone tree, where gamma_k o infty. This extends the Littlestone tree structure used in itet{bousquet_theory_2021} to the metric loss setting.

Source: arXiv cs.LG | 2026-05-06