一致收敛性所探讨的问题是：需要多少个随机样本，才能使得经验均值在整类函数上同时地、一致地逼近其理论期望值。它既是概率论中的一个核心概念，也是统计学习理论的重要基石。对于取值为二元（即{0,1}）的函数类，Vapnik–Chervonenkis定理指出，一致收敛性成立当且仅当该函数类的VC维有限；进一步地，当VC维为 $d$ 时，为达到加性误差 $\varepsilon$ 所需的最坏情形样本复杂度（即最小样本量）精确地为 $d/\varepsilon^2$ 量级。而对于实值函数类，与之对应的组合参数是“胖破碎维数”（fat-shattering dimension），它依赖于一个近似尺度 $\gamma$。此时的关键挑战在于：能否仅用 $d/\varepsilon^2$ 量级的样本，就实现总误差为 $\gamma + \varepsilon$ 的一致逼近——其中 $d$ 现在指在尺度 $\gamma$ 下的胖破碎维数；这一样本量界须与前述二元函数类的最优界完全匹配。此前的研究成果要么达到了最优的误差尺度（即最优 $\gamma$），要么实现了最优的样本复杂度（即最优 $d/\varepsilon^2$），但始终未能二者兼得。本文的主要结果成功弥合了这一长期存在的缺口，首次确立了在最优误差尺度下的尖锐（即不可改进的）样本复杂度界。在证明过程中，我们发展并运用了若干可能具有独立意义的技术工具： 第一，我们引入了“带间隔的 $\varepsilon$-网”（$\varepsilon$-nets with margin）。经典定义中，一个 $\varepsilon$-网要求与给定函数族中所有测度不小于 $\varepsilon$ 的集合均发生交集；而我们允许该网仅需与每个此类集合的一个略微放大版本相交。出人意料的是，这一看似微小的松弛，却使得所得界在自然的几何设定下可完全摆脱环境空间维度的影响。 第二，我们在离散与实值两类设定下均获得了更优的覆盖数（covering number）上界：一方面，我们将Haussler覆盖引理推广至“偏概念类”（partial concept classes）；另一方面，利用这一推广，我们为实值函数类构造出了在最优尺度下达到最优 $\ell_2$ 距离精度的覆盖。 第三，我们通过精心设计覆盖结构，实现了在最优尺度下的“链式界”（chaining bound）：具体而言，我们使逐层逼近所用的覆盖彼此对齐，从而保证后续层级的近似结果相较前一层越来越接近目标函数，进而显著提升链式论证的整体效率。
ALL 
