arXiv:2608.10869cs.LGstat.ML2026-08被引 1

提出多分类学习的乐观率,实现更紧的泛化误差上界。

Optimistic Rates for Multiclass PAC Learning

  • 基于压缩与比较框架,设计无需已知风险的自适应学习算法。
  • 在任意最优风险下,误差上界为√(L⋆d_N/n) + d_DS/n,达到最优。
  • 适用于多分类和列表学习,突破传统理论瓶颈。

多分类学习的最坏情况界在最优分类器接近正确时不会变小:缺少的是依赖于真实风险本身的乐观率。对于Natarajan维数d_N和Daniely-Shalev-Shwartz维数d_DS,在可实现情形(d_DS/n)与非可实现情形(√(d_N/n)+d_DS/n)之间存在未解之问。本文填补空白:对任意固定真实风险L⋆,最优过失风险为˜Θ(√(L⋆d_N/n)+d_DS/n),且该界对字母表大小一致成立,由一个不依赖于L⋆或置信度的学习器实现。上界结合了[CEH+26]的覆盖-菜单-压缩结构与[Pab26]的可实现率,并引入新的面向比较器的相对压缩定理:若大小为k的压缩规则在经验上优于比较器h,则其总体风险不超过L(h)+O(√(L(h)Γ)+Γ),其中Γ=(k log n + log(1/δ))/n,无需稳定性假设。该定理转移了[MQZ26]中尖锐二分类理论的比较原则,舍弃其布尔立方体几何,因其无法推广至多分类标签。下界通过一对阿苏阿德方案与伪立方上的纤维论证,针对每个固定的L⋆,同时强制两项。两个定理均扩展至列表学习:针对最佳r元组假设,相同架构与两引擎给出相同形状的乐观率与下界,证实了[Pab26]预期的波动项必要性,并移除了已知可实现列表下界中的因子r。

原文摘要 · Abstract (English)

Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales with the oracle risk itself. For a class of Natarajan dimension $d_N$ and Daniely-Shalev-Shwartz dimension $d_{DS}$, the optimal excess risk is known at the two endpoints ($d_{DS}/n$ realizable, $\sqrt{d_N/n}+d_{DS}/n$ agnostic [HMZ24, CEH+26, Pab26]) and open in between. We close the gap: at every fixed oracle risk $L^\star$, the optimal excess risk is $\widetildeΘ(\sqrt{L^\star d_N/n}+d_{DS}/n)$, uniformly in the alphabet size, attained by a learner that knows neither $L^\star$ nor the confidence level. The upper bound composes the cover-menu-compression architecture of [CEH+26], at the realizable rate of [Pab26], with a new comparator-facing relative compression theorem: a size-$k$ compression rule that empirically dominates a comparator $h$ has population risk at most $L(h)+O(\sqrt{L(h)Γ}+Γ)$ with $Γ=(k\log n+\log(1/δ))/n$, without stability; this transfers the comparison principle of the sharp binary theory [MQZ26] while discarding its Boolean-cube geometry, which does not lift to multiclass labels. The lower bound forces both terms using one class and one distribution at every fixed $L^\star$, by a pair-Assouad scheme calibrated to $L^\star$ and a fiber argument on the pseudo-cubes underlying the Natarajan-versus-DS separation of [BCD+22]. Both theorems extend to list learning: against the best $r$-tuple of hypotheses, the same architecture and the same two engines yield an optimistic rate and a lower bound of the same shape, forcing the fluctuation term that [Pab26] expected to be necessary against list comparators, and removing the factor $r$ from the known realizable list lower bound.

多分类学习理论乐观率压缩

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