多分类学习样本复杂度由两个维度共同决定，突破了单一维度的局限。
Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
- 提出新样本复杂度上界，结合DS和Natarajan维数
- 小误差下，Natarajan维数主导渐近行为
- 基于自适应权重的在线算法，方法可独立应用
统计学习的基本定理表明，二分类PAC学习由单一参数VC维决定学习性和样本复杂度。将此推广至多分类长期困难，尽管Natarajan在80年代末提出Natarajan维（Nat）作为VC维的自然类比。Daniely与Shalev-Shwartz（2014）引入DS维，后被Brukhim等（2022）证明可刻画多分类可学习性。但后者也表明Nat与DS可任意偏离，暗示多分类学习应由DS而非Nat主导。本文证明，在对抗型多分类中，样本复杂度实际上由两个不同维度共同控制。具体地，我们给出了近乎紧致的样本复杂度上界：在忽略对数因子时，形式为 $\frac{DS^{1.5}}{ε} + \frac{Nat}{ε^2}$，其中 $ε$ 为过失风险。该界在第一项中仅差 $\sqrt{DS}$ 因子，几乎匹配已知的 $Nat/ε^2$ 与 $DS/ε$ 下界。第一项反映由DS控制的区域，第二项则表明当 $ε$ 很小时，Natarajan维仍决定渐近行为。因此，不同于二分类或在线学习中单一维度（如VC或Littlestone）同时控制学习性与样本复杂度，多分类学习本质上涉及两个结构参数。我们的技术路线脱离传统基于一致收敛或归约到可实现情形的方法。核心是设计一种基于自适应乘法权重的新型在线算法，实现标签空间压缩，该方法本身亦具独立价值。
原文摘要 · Abstract (English)
The fundamental theorem of statistical learning states that binary PAC learning is governed by a single parameter -- the Vapnik-Chervonenkis (VC) dimension -- which determines both learnability and sample complexity. Extending this to multiclass classification has long been challenging, since Natarajan's work in the late 80s proposing the Natarajan dimension (Nat) as a natural analogue of VC. Daniely and Shalev-Shwartz (2014) introduced the DS dimension, later shown by Brukhim et al. (2022) to characterize multiclass learnability. Brukhim et al. also showed that Nat and DS can diverge arbitrarily, suggesting that multiclass learning is governed by DS rather than Nat. We show that agnostic multiclass PAC sample complexity is in fact governed by two distinct dimensions. Specifically, we prove nearly tight agnostic sample complexity bounds that, up to log factors, take the form $\frac{DS^{1.5}}ε + \frac{Nat}{ε^2}$ where $ε$ is the excess risk. This bound is tight up to a $\sqrt{DS}$ factor in the first term, nearly matching known $Nat/ε^2$ and $DS/ε$ lower bounds. The first term reflects the DS-controlled regime, while the second shows that the Natarajan dimension still dictates asymptotic behavior for small $ε$. Thus, unlike binary or online classification -- where a single dimension (VC or Littlestone) controls both phenomena -- multiclass learning inherently involves two structural parameters. Our technical approach departs from traditional agnostic learning methods based on uniform convergence or reductions to realizable cases. A key ingredient is a novel online procedure based on a self-adaptive multiplicative-weights algorithm performing a label-space reduction, which may be of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。