# Realizable Bayes-Consistency for General Metric Losses

arXiv: https://arxiv.org/abs/2605.03823 · HTML: https://mlsanity.com/paper/2605.03823/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 16 references that are in the map.
- First posted on arXiv 5 May 2026.

## Builds on (most cited first, 6 of 6)

- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [Universal Bayes consistency in metric spaces](https://mlsanity.com/paper/1906.09855/) (2019)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Efficient Classification for Metric Data](https://mlsanity.com/paper/1306.2547/) (2013)
- [Universal Rates for Multiclass Learning](https://mlsanity.com/paper/2307.02066/) (2023)

## Abstract (arXiv)

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., 2024). Given an instance space (X,ρ), a label space (Y,ℓ) with possibly unbounded loss, and a hypothesis class H subseteq YX, 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. (2024), we introduce the notion of an infinite non-decreasing (γk)-Littlestone tree, where γk → ∞. This extends the Littlestone tree structure used in Bousquet et al. (2020) to the metric loss setting.