arXiv:2502.09257v1 宣告类型: cross 摘要: 我们研究了多类别列表分类问题，其中输入示例被映射到一个包含 $K$ 个可能标签集合中的 $m$ 个元素的子集，并且反馈是预测标签中存在于给定示例真实标签集中的那些标签。我们的主要结果是针对该问题的 $(\varepsilon,\delta)$-PAC 版本，我们设计了一个算法，该算法以高概率返回一个 $\varepsilon$-最优的假设，样本复杂度为 $O \big( (\mathrm{poly}(K/m) + sm / \varepsilon^2) \log (|H|/\delta) \big)$，其中 $H$ 是基础（有限）假设类，$s$ 是给定示例的真实标签数的上界。当 $s \ll K$ 时，此界优于已知的组合半带宽反馈问题的界。此外，在 $s = O(1)$ 的情况下，我们界的主要项与相应的全信息率匹配，这意味着半带宽反馈基本上不带来任何成本。我们的 PAC 学习算法在访问到 $H$ 的ERM预言机的情况下也是计算高效的。此外，我们还考虑了数据可以由对手生成的遗憾最小化设置，并建立了遗憾界 $\widetilde O(|H| + \sqrt{smT \log |H|})$。我们的结果推广并扩展了 Erez 等人（2024）的研究，他们考虑的是单标签设置，对应的 $s=m=1$，实际上这些结果适用于更一般的 $s$ 稀疏奖励的上下文组合半带宽反馈问题。