arXiv:2608.25326cs.LG2026-08

揭示多分类领域中两种维度决定学习上限,统一了理论边界。

Two Dimensions Govern Agnostic Multiclass Transductive Learning

  • 用双维度框架分析无监督多分类的最优误差率
  • 证明误差下界为 d_DS/n + √(d_N/n),且两项均不可省略
  • 适合关注理论学习复杂度与模型泛化能力的研究者

在转换分类中,对手固定一个带标签的数据集,其中一个标签被均匀隐藏,学习者只能看到其余标签。对于二分类,无监督转换学习与PAC学习的最小最大速率相同。这一结论是否能推广到多分类情形,尤其是标签空间无界时(此时一致收敛可能失效)仍属未知。本文在对数因子范围内解决了该问题:对于任意多分类类 H,其 DS 维度为 d_DS,Natarajan 维度为 d_N,最优无监督转换超额误差满足 ~Θ(d_DS/n + √(d_N/n))。该结果适用于任意标签空间。两项均为必要项:DS伪立方体导致可实现情形下的 d_DS/n 阻碍,而带有重复点和公平标签的 Natarajan 立方体则带来无监督情形下的 √(d_N/n) 阻碍。上界采用随机预留原则:学习者主动忽略一部分可见标签,使真实测试点在较大未见区块中均匀分布。结合可实现压缩、标签空间降维及在此有限总体划分上的内部菜单无监督压缩,通过新提出的无放回乘法权重引理,保持了快速的 d_DS/n 项。因此,无监督多分类的PAC与转换学习在对数因子内遵循相同的双维律。

原文摘要 · Abstract (English)

In transductive classification, an adversary fixes a labeled population, one label is hidden uniformly, and the learner sees all remaining labels. For binary classes, agnostic transductive and PAC learning have the same minimax rate. Whether this extends to multiclass learning was open, especially for unbounded label spaces where uniform convergence can fail. We resolve the question up to logarithmic factors. For every multiclass class $\mathcal H$ with DS dimension $d_{DS}$ and Natarajan dimension $d_{\mathrm N}$, the optimal agnostic transductive excess error satisfies $\widetildeΘ\left(\frac{d_{DS}}{n}+\sqrt{\frac{d_{\mathrm N}}{n}}\right).$ The result holds for arbitrary label spaces. The two terms are both necessary. A DS pseudo-cube gives the realizable $d_{DS}/n$ obstruction, while a Natarajan cube with repeated points and fair labels gives the agnostic $\sqrt{d_{\mathrm N}/n}$ obstruction. The upper bound uses a random-reservation principle. The learner deliberately ignores a constant fraction of the visible labels, which makes the true test point uniform in a large unseen block. We combine realizable compression, a label-space reduction, and inside-menu agnostic compression across this finite-population split. A new without-replacement multiplicative-weights lemma preserves the fast $d_{DS}/n$ term. Consequently, agnostic multiclass PAC and transductive learning obey the same two-dimension law up to logarithmic factors.

多分类理论学习泛化误差

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。