1Ben-Gurion University of the Negev · 2Purdue University, USA.
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⊆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.