技术摘要：尺度敏感的破碎性：最优尺度下的可学习性与可评估性

问题陈述

本文探讨了统计学习理论中关于实值函数类的基本问题。具体而言，它研究了三个核心概念之间的精确关系：不可知可学习性（agnostic learnability）、一致收敛性（uniform convergence）以及fat-shattering 维数（fat-shattering dimension，即 VC 维数的尺度敏感推广）。

虽然"PAC 学习基本定理”确立了这些概念在二分类情形下的等价性，但在实值设定中，历史上一直存在差距。先前的工作（例如 Bartlett 和 Long，1998）证明了有限的 $\gamma$-fat-shattering 维数意味着一致收敛性和可学习性，但仅在 $2\gamma$ 尺度（或 $c\gamma$ 尺度，其中 $c>2$）下成立。这留下了一个问题：尺度上的 2 倍乘数因子是否不可避免？这一猜想归因于 Anthony 和 Bartlett（1999）教科书中的 Phil Long。

此外，本文还探讨了度量熵（覆盖数的对数）与 fat-shattering 维数之间的关系。先前的结果（Alon 等人，1997；Rudelson 和 Vershynin，2006）给出了度量熵的界，但留下了以下问题未决：在最优尺度下，对样本量 $n$ 的依赖能否从 $O(\log^2 n)$ 改进为 $O(\log n)$，以及这些界中的尺度因子是否可以收紧。

最后，本文将这些理论见解应用于基于积分概率度量（IPMs）的生成模型的可评估性与可估计性。近期针对二值测试函数的二分法结果（Aiyer 等人，2026）表明，此类度量要么是可估计的，要么是弱可评估的，且最优尺度为 $c=3$。将这一结果扩展到实值函数受到了上述一致收敛结果中尺度差距的阻碍。

方法论

作者的主要技术创新是直接对经验 $\ell_\infty$ 覆盖数进行界定，绕过了通过打包数（packing numbers）的标准迂回路径。

1. 通过部分概念类进行直接覆盖：
   作者没有将覆盖数与打包数相关联（这本质上会导致尺度损失），而是利用了部分概念类（partial concept classes）的理论（Lon01; AHHM22）。他们根据相对于尺度 $\gamma$ 的阈值，将实值函数映射为部分二值函数。通过界定这些诱导的部分类的 VC 维数，他们构建了显式的亚指数大小覆盖。这使得他们能够直接在最优尺度 $\gamma/2$ 而非 $2\gamma$ 处推导覆盖数界。

2. 迭代细化：
   为了在任意接近 $\gamma/2$ 的尺度上获得界，作者采用了一种迭代构造方法。从粗略覆盖开始，他们递归地细化盒子，几何级数地减小半径，同时控制覆盖大小的增长。这得出了关于度量熵 $H(F, \gamma/2 + \epsilon, n)$ 的界，该界在 $n$ 上是次线性的。

3. 样本压缩与对偶类：
   对于尺度较大（$\gamma > 2\gamma^*$）的情形，作者利用了样本压缩方案。他们利用这样一个事实：具有有限 fat-shattering 维数的函数类的对偶类也满足一致收敛性（这是从他们的主要定理中推导出的结果），从而稀疏化分布并构建常数大小的压缩方案。这导致了 $O(\log n)$ 的熵界。

4. 归约到全变差：
   在应用于可评估性时，作者构建了一个从具有无限 fat-shattering 维数的一般 IPM 到全变差（TV）距离设定的归约。他们精心构造了破碎集上的分布混合，以表明 IPM 在渐近意义上表现得像 TV 距离，同时保留了最优尺度常数。

主要贡献与结果

1. 尺度差距的解决（定理 1）

本文建立了实值类 PAC 学习基本定理的精确类比。对于有界函数类 $F$ 和尺度 $\gamma > 0$，以下命题等价：

1. $F$ 是 $\gamma/2$-可学习的。
2. $F$ 满足 $\gamma$-一致收敛性。
3. 对于每一个 $\gamma' > \gamma$，$F$ 的 $\gamma'$-fat-shattering 维数是有限的。

意义： 这一结果反驳了 2 倍差距不可避免猜想。它证明了只要 fat-shattering 维数在严格大于 $\gamma$ 的任何尺度下是有限的，可学习性和一致收敛性就在最优尺度 $\gamma/2$（针对可学习性）和 $\gamma$（针对收敛性）下成立。

2. 精确的度量熵界（定理 2）

本文基于临界尺度 $\gamma^* = \inf\{\gamma : \text{fat}_\gamma(F) < \infty\}$，提供了度量熵 $H(F, \gamma, n)$ 增长的完整刻画：

• 线性区域（$\gamma < \gamma^*/2$）： $H(F, \gamma, n) = \Theta(n)$。
• 中间区域（$\gamma^*/2 < \gamma \le 2\gamma^*$）： $H(F, \gamma, n) = O(\log^2 n)$。本文表明，对于 $\gamma \in (\gamma^*/2, \gamma^*)$，该界是紧的（忽略低阶项），解决了 Alon 等人（1997）关于 $\log^2 n$ 因子是否必要的问题。
• 大尺度区域（$\gamma > 2\gamma^*$）： $H(F, \gamma, n) = O(\log n)$。这证实了在足够大的尺度下，指数可以降至 1，解决了 Rudelson 和 Vershynin（2006）提出的问题。

3. 生成模型可评估性的二分法（定理 3 与命题 1）

应用精确的尺度敏感结果，本文建立了有界积分概率度量（IPMs）的二分法：

• 如果对于所有 $\gamma > 0$，fat-shattering 维数都是有限的，则该 IPM 是可估计的（因此是强可评估的，且 $c=1$）。
• 如果对于某个 $\gamma \in (0, 1/2)$，fat-shattering 维数是无限的，则该 IPM 是弱可评估的，且最优尺度为 $c=3$，但对于任何 $c < 3$ 则不可评估。

意义： 这将 Aiyer 等人（2026）的二值二分法扩展到了实值函数。证明的关键在于作者能够在没有 2 倍损失的情况下建立尺度 $\gamma$ 下的一致收敛性；如果没有这一点，关于最优尺度 $c=3$ 的论证就会失败。

4. 闭包性质

本文证明了 $\gamma$-可学习性和 $\gamma$-一致收敛性在以下操作下是不变的：

• 对偶性： 一致收敛类的对偶类也是一致收敛的。
• 聚合： 通过 1-Lipschitz 函数聚合类，可以在相同尺度下保持一致收敛性。

意义与主张

作者声称，他们的工作解决了学习理论中的几个长期未决问题：

1. 反驳 2 倍因子猜想： 通过证明可学习性和一致收敛性在最优尺度下成立，本文明确回答了 Anthony 和 Bartlett（1999）提出的问题，表明 2 倍差距并非固有属性。
2. 精确的熵界： 本文确定了度量熵对样本量 $n$ 和尺度 $\gamma$ 的精确依赖关系，阐明了何时可以实现 $O(\log n)$ 界，以及何时 $O(\log^2 n)$ 是必要的。
3. 可评估性的定性刻画： 本文认为，一致收敛尺度上从 2 倍到 1 倍的定量改进，解锁了对生成模型评估的定性刻画，建立了可估计性与 $c=3$ 的弱可评估性之间的精确二分法。

作者指出，虽然他们解决了渐近行为和二分法的存在性，但在中间范围 $\gamma^* < \gamma \le 2\gamma^*$ 内熵的精确行为以及在最优尺度下学习的精确样本复杂度界仍然是未解决的问题。此外，fat-shattering 维数与其他 $\ell_p$ 度量下覆盖数之间的关系留待未来研究。