基于查询反馈的可实现多分类 PAC 学习研究

研究者提出了组合参数「查询维度」（query dimension），用于刻画基于查询反馈的可实现多分类 PAC 学习的样本复杂度。该参数概括了单元素查询下的 bandit DS 维度，确立了 $\Omega(D/\varepsilon)$ 的样本复杂度下界和 $\widetilde{O}(D^2/\varepsilon)$ 的上界。