任意标签空间下的最优多分类在线遗憾

arXiv:2610.32339v1 公告类型：新 摘要：我们确定了具有任意（可能是无限）标签空间的无先验多分类在线学习中的最优遗憾。对于每个多分类 Littlestone 维数为 $d<\infty$ 的假设类，我们证明，在 $T$ 轮学习中，遗憾上界为 $O(\min\{T,\sqrt{dT}\})$，与已知下界相匹配。这解决了 Hanneke et al. (2023) 提出的问题，并扩展了 Alon et al. (2021) 关于二分类的最优遗憾界。我们的证明将 Hanneke et al. (2023) 的单边专家覆盖加强为分数覆盖。我们将该覆盖与一种针对有限专家博弈的极小极大归约相结合，其中最佳响应奖励提供了链式方法所需的不一致性界。