Realizable Bayes-Consistency for General Metric Losses

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., 2021; Hanneke et al., 2021) and real-valued regression (Attias et al., 2024). Given an instance space $(X,\rho)$, a label space $(Y,\ell)$ with possibly unbounded loss, and a hypothesis class $H \subseteq Y^{X}$, we resolve the realizable case of an open problem presented in Tsir Cohen and 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 data-generating distribution. Our main contribution is this sharp characterization in terms of a combinatorial obstruction: Similarly to Attias et al. (2023), we introduce the notion of an infinite non-decreasing $(\gamma_k)$-Littlestone tree, where $\gamma_k \to \infty$. This extends the Littlestone tree structure used in Bousquet et al. (2021) to the metric loss setting.

Modern machine learning increasingly tackles problems where predictions are not just labels but elements of structured spaces — for example, predicting the position of an object, a molecular geometry, or a protein conformation — and where mistakes are measured by a distance. We study the most basic question in this setting: for which problems can we guarantee that, given enough training data, our predictions become arbitrarily accurate, no matter what the underlying data-generating process looks like? Building on classical results for binary classification and recent work on real-valued regression, we give a precise answer for general distance-based prediction. Our main result identifies a single combinatorial structure — an infinite tree-shaped obstacle — whose presence rules out reliable learning, and whose absence permits an explicit learning procedure. The work resolves the realizable case of an open problem in the field and clarifies which prediction tasks are fundamentally tractable, even when errors can be arbitrarily costly.