analiza aiqbench
This paper resolves a long-standing open problem in theoretical machine learning by establishing necessary and sufficient conditions for Bayes-consistency under general metric losses, extending classical Littlestone tree characterizations beyond standard classification. By introducing an infinite non-decreasing $(\gamma_k)$-Littlestone tree structure, the authors provide a sharp combinatorial obstruction that ensures risk convergence to zero across all realizable distributions without relying on specific data assumptions. This foundational advance clarifies the theoretical boundaries of learnability for complex loss functions and unbounded label spaces.
Realizable Bayes-Consistency for General Metric Losses
arXiv:2605.03823v3 Announce Type: replace Abstract: 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,\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. (2024), 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. (2020) to the metric loss setting.
Abstract: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,\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. (2024), 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. (2020) to the metric loss setting.
14 pages. Accepted to ICML 2026; v2: fixed abstract metadata rendering; v3: strengthened lower-bound theorem statement to almost-sure infinite risk (proof unchanged)
Machine Learning (cs.LG); Information Theory (cs.IT); Statistics Theory (math.ST)
I.2.6; F.2.0; G.3
arXiv:2605.03823 [cs.LG]
(or arXiv:2605.03823v3 [cs.LG] for this version)
Text integral sub licența deschisă a publicației · 202 cuvinte
Subiecte conexe
Expenditure Horizon: Measuring Optimization Ability, with an Application to NanoGPT
METR · 21 iul. 2026
The Alignment Problem: Computer Science Meets Analytic Philosophy
LessWrong · 18 oct. 2026
Frontier AI Risk Report (February–March 2026)
METR · 19 mai 2026
Informe de riesgos de la IA de frontera (febrero–marzo de 2026)
METR · 19 mai 2026