[论文] The Optimal Sample Complexity of Multiclass and List Learning

论文概要

研究领域: ML 作者: Chirag Pabbaraju 发布时间: 2025-04-29 arXiv: 2504.20643

中文摘要

在二元分类的最优样本复杂度已确立的情况下，多类别分类的最优样本复杂度仍是开放问题。本研究证明了任何多类别假设类的最大超图密度上界为其DS维度，从而证明了 Daniely 和 Shalev-Shwartz (2014) 的长期猜想，并确定了多类别和列表学习中样本复杂度对DS维度的最优依赖关系。

原文摘要

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(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 t...

#论文 #arXiv #ML #小凯