Optimistic Rates for Multiclass PAC Learning

技术摘要：多分类 PAC 学习中的乐观速率

问题陈述
本文探讨了 PAC 学习框架下多分类问题的统计难度。现有的多分类学习最坏情况界限依赖于两个容量参数：Natarajan 维度 ($d_N$) 和 Daniely–Shalev-Shwartz (DS) 维度 ($d_{DS}$)。虽然在两个极端情况——实现型学习（$L^\star = 0$）和完全不可知型学习（$L^\star$ 为常数）——下已知最优速率，但两者之间的行为仍未得到解决。具体而言，当前的最坏情况不可知界限按 $\sqrt{d_N/n} + d_{DS}/n$ 缩放，未能反映出如果最佳分类器几乎是正确的（即 oracle 风险 $L^\star$ 很小），则学习问题应该更容易这一事实。本研究的目标是建立一种“乐观速率”，其通过 $L^\star$ 来缩放波动项，从而在快速的实现型速率与缓慢的不可知型速率之间进行插值。

方法论
作者提出了一种学习器 RMC（相对菜单压缩，Relative Menu Compression），该学习器无需预先知道 $L^\star$ 或置信水平 $\delta$ 即可实现这种插值。其证明架构依赖于一种三阶段样本拆分策略，改编自 [CEH+26] 中的“覆盖–菜单–压缩”（cover–menu–compression）归约，但引入了一种全新的统计接口。

1. 第一阶段（覆盖/Cover）： 一个确定性压缩器将无限假设类减少为一个规模约为 $d_{DS} \log^2 n$ 的有限族 $\hat{\mathcal{F}}$。这一步确保了对于任何比较器 $h$，在 $\hat{\mathcal{F}}$ 中都存在一个“规范见证”（canonical witness），该见证在 $h$ 正确的区域内与 $h$ 一致。
2. 第二阶段（菜单/Menu）： 一个乘法权重算法学习一个“菜单” $\mu$（即每个输入的候选标签集合），该菜单覆盖了规范见证在 oracle 正确区域上的标签。这一步控制了正确标签缺失在菜单中的概率，其失败模式受 $d_{DS}$ 控制。
3. 第三阶段（压缩/Compression）： 一旦菜单固定，问题便简化为菜单内的二分类问题。学习器应用一种压缩规则，该规则在经验上优于一个固定的比较器。

其核心技术创新是面向比较器的相对压缩定理（定理 3.3）。不同于标准的压缩界限（其比较学习器的总体风险与其经验风险，产生 $\sqrt{k/n}$ 的波动），该定理直接将学习器的总体风险与其固定比较器的总体风险 $L(h)$ 进行比较。它确立了如果一个大小为 $k$ 的压缩规则的经验损失不大于 $h$，那么：
$$L(A(S)) \leq L(h) + O\left(\sqrt{L(h) \frac{k \log n}{n}} + \frac{k \log n}{n}\right)$$
至关重要的是，$L(h)$ 的系数恰好为 1，且波动随 $\sqrt{L(h)}$ 缩放。这是通过使用带有重复索引的有序描述和单侧 Bernstein 不等式实现的，且无需稳定性假设。

主要贡献

1. 最优多分类乐观速率： 本文证明了对于一个具有 Natarjan 维度 $d_N$ 和 DS 维度 $d_{DS}$ 的类，其最优超额风险为：
   $$\tilde{\Theta}\left( \sqrt{\frac{L^\star d_N}{n}} + \frac{d_{DS}}{n} \right)$$
   该结果在字母表大小方面是均匀成立的。$d_N$ 项通过 $L^\star$ 进行局部化，而 $d_{DS}$ 项则保持为实现型阶数的余项。
2. 匹配的下界： 作者构造了一个单一的假设类和单一的分布，对于任何固定的 $L^\star$，都能迫使上界中的两项同时发生。这证实了角色分离——即 $d_{DS}$ 控制标签覆盖，而 $d_N$ 控制菜单内的波动——是该问题内在的属性，而非分析过程中的人工产物。
3. 向列表学习（List Learning）的扩展： 该架构被扩展到了列表学习（输出 $r$ 个标签）。作者推导了针对最佳 $r$-元组假设的乐观速率，并将波动项局部化在 oracle 列表风险处。这解决了 [Pab26] 关于是否有必要引入 $r$ 进制 Natarajan 波动项的预期，并通过移除一个因子 $r$ 改进了已知的实现型列表下界。
4. 形式化验证： 主要定理及其证明已在 Lean 4 中进行了机器检查，确保了常数和逻辑依赖关系的正确性。

结果

• 上界（定理 3.1）： RMC 学习器以 $1-\delta$ 的概率实现速率 $\tilde{O}(\sqrt{L^\star d_N/n} + d_{DS}/n)$。该学习器是无参数的（独立于 $L^\star$ 和 $\delta$）。
• 下界（定理 4.1）： 对于任何 $1 \leq d_N \leq d_{DS}$，存在一个类和分布，使得任何学习器产生的期望超额风险至少为 $\Omega(\sqrt{L^\star d_N/n} + d_{DS}/n)$。该构造使用了噪声 Natarajan 立方体与伪立方体（源自 [BCD+22]）的乘积，以分离这两个维度。
• 列表学习（定理 5.1 & 5.2）： 乐观速率扩展到了针对最佳 $r$-元组的列表学习器，其下界证实了波动项的必要性。此外，一个新的实现型列表学习下界移除了 [HMZ24] 中存在的因子 $r$。

意义与主张
本文声称填补了已知实现型与不可知型多分类速率之间的空白，提供了第一个分布无关、无参数的多分类乐观速率。

• 理论统一： 它证明了此前通过布尔立方体几何结构 [MQZ26] 在二分类中建立的“系数一”比较原则，可以通过将标签几何（由菜单/覆盖处理）与随机波动（由相对压缩处理）解耦，从而提升到多分类设置中。
• 内在分离： 下界证明了两个容量参数（$d_N$ 和 $d_{DS}$）扮演着截然不同且不可互换的角色：$d_{DS}$ 决定了正确标签是否可见（覆盖度），而 $d_N$ 决定了在可见标签中进行选择的难度（波动度）。
• 局限性： 作者指出，上界中的对数因子尚未得到优化，且该学习器是信息论层面的（不一定是计算高效的）。结果假设标签字母表是有限的，尽管该界限在字母表基数上是均匀的。

这项工作被视为解决了多分类 PAC 学习中的插值问题，确立了难度确实取决于实现程度，并给出了这种难度退化的精确速率。