We study the sample complexity of multiclass prediction inseveral learning settings. For the PAC setting our analysisreveals a surprising phenomenon: In sharp contrast to binaryclassification, we show that there exist multiclass hypothesisclasses for which some Empirical Risk Minimizers (ERM learners)have lower sample complexity than others. Furthermore, there areclasses that are learnable by some ERM learners, while other ERMlearners will fail to learn them. We propose a principle fordesigning good ERM learners, and use this principle to provetight bounds on the sample complexity of learningsymmetric multiclass hypothesis classes---classes thatare invariant under permutations of label names. We furtherprovide a characterization of mistake and regret bounds formulticlass learning in the online setting and the banditsetting, using new generalizations of Littlestone's dimension. color="gray">
展开▼
机译：我们研究了多种学习设置下的多类预测的样本复杂性。对于PAC设置，我们的分析揭示了一个令人惊讶的现象：与二元分类形成鲜明对比，我们表明存在多个类别假设类别，其中一些经验风险最小化器（ERM学习者）具有更低的样本复杂度。此外，有些ERM学习者可以学习某些课程，而其他ERM学习者将无法学习它们。我们提出了一个设计优秀的ERM学习者的原则，并用此原则来证明学习对称多类假设类别的样本复杂性的界限，这些类别在标签名称的排列下是不变的。我们使用Littlestone维度的新概括为在线环境和匪徒环境中的多类学习提供错误和遗憾界限的表征。 color =“ gray”>
展开▼
