提出通用度量损失下可实现情形的贝叶斯一致性条件。
Realizable Bayes-Consistency for General Metric Losses
- 用无限递增小石树结构刻画学习一致性的组合障碍。
- 证明了在可实现设定下，风险几乎必然收敛至零的充要条件。
- 适用于推广分类与回归的泛化理论研究者。
我们研究了在可实现设定下，使用通用度量损失进行学习时的强普适贝叶斯一致性问题，扩展了经典分类（0-1损失）和实值回归（Attias et al., 2024）的表征。给定实例空间 $(X,ρ)$、标签空间 $(Y, ilde{ u})$（损失可能无界）以及假设类 $H \ Y^{X}$，我们解决了 Tsir Cohen 和 Kontorovich (2022) 提出的一个开放问题。具体而言，我们给出了假设类 $H$ 的必要且充分条件：存在一种无分布的学习规则，使其风险对任意可实现数据生成分布几乎必然收敛到最优类风险（即零）。核心贡献是通过组合障碍的精确刻画——类似于 Attias 等人（2024）引入的无限非减 $(γ_k)$-小石树结构，其中 $γ_k \to \infty$，将 Bousquet 等人（2020）的小石树结构推广至度量损失场景。
原文摘要 · Abstract (English)
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,\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 $(γ_k)$-Littlestone tree, where $γ_k \to \infty$. This extends the Littlestone tree structure used in Bousquet et al. (2020) to the metric loss setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。