破解多分类最优样本复杂度难题，证明关键猜想并确定理论极限。
The Optimal Sample Complexity of Multiclass and List Learning
- 基于DS维数构建超图密度上界，突破传统分析瓶颈。
- 首次确立多分类与列表学习的样本复杂度最优依赖关系。
- 适合理论机器学习研究者及算法设计人员阅读。
尽管二分类的样本复杂度在VC维下已明确，但多分类的最优样本复杂度仍悬而未决。多分类的合适复杂度参数为DS维数，尽管已有大量研究，上下界之间仍存在√DS的差距。近期Hanneke等（2026）提出了基于DS维数的多分类假设类的新代数刻画。在此基础上，本文证明任意多分类假设类的最大超图密度不超过其DS维数，从而证实了Daniely与Shalev-Shwartz（2014）提出的长期猜想。作为推论，我们确定了多分类及列表学习中样本复杂度对DS维数的最优依赖关系。
原文摘要 · Abstract (English)
While the optimal sample complexity of binary classification in terms of the VC dimension is well-established, determining the optimal sample complexity of multiclass classification has remained open. The appropriate complexity parameter for multiclass classification is the DS dimension, and despite significant efforts, a gap of $\sqrt{\text{DS}}$ has persisted between the upper and lower bounds on sample complexity. Recent work by Hanneke et al. (2026) shows a novel algebraic characterization of multiclass hypothesis classes in terms of their DS dimension. Building up on this, we show that the maximum hypergraph density of any multiclass hypothesis class is upper-bounded by its DS dimension. This proves a longstanding conjecture of Daniely and Shalev-Shwartz (2014). As a consequence, we determine the optimal dependence of the sample complexity on the DS dimension for multiclass as well as list learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。