揭示函数类在最优尺度下的可学习性与泛化关系,打破理论瓶颈。
Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale
- 提出尺度敏感的泛化理论,统一了学习与收敛条件
- 证明在γ/2尺度下可学习,且在2γ尺度达到O(log n)熵界
- 解决多个经典开放问题,适用于理论机器学习研究者
我们研究实值函数类在最优尺度下实现一致收敛与可学习性的条件。核心结果表明:对任意有界实值函数类及任意γ>0,尺度γ下的一致收敛、尺度γ/2下的广义学习能力,以及所有尺度γ'>γ下的fat-shattering维数有限性三者等价。该结论解决了Anthony和Bartlett(1999)提出的关于学习性决定尺度的疑问,推翻了被归因于Phil Long的‘2倍因子间隙不可避免’猜想,并改进了Bartlett与Long(JCSS 1998)的上界。关键技术在于直接给出经验ℓ∞覆盖数的上界,避免了传统通过填充数的绕行路径。由此得到关于fat-shattering尺度γ的精确渐近度量熵界:在尺度γ/2下为O(log²n),在尺度2γ下为O(log n),且后者有时紧致。这些结果解决了Alon等人(JACM 1997)与Rudelson-Vershynin(Ann. of Math. 2006)的开放问题。作为应用,我们建立了有界积分概率度量的严格二分定理:每个此类度量要么可估计,要么无法以任何乘性因子c<3进行弱评估,而3-弱评估恒成立,解决了Aiyer等人(ICML 2026)的开放问题。同时指出若干关于样本复杂度与评估性的未解问题。
原文摘要 · Abstract (English)
We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability. Our main result establishes a scale-sensitive generalization of the fundamental theorem of PAC learning: for every bounded real-valued class and every $γ>0$, uniform convergence at scale $γ$, agnostic learnability at scale $γ/2$, and finiteness of the fat-shattering dimension at every scale $γ'>γ$ are equivalent. This resolves a question by Anthony and Bartlett (Cambridge Univ. Press 1999) on the precise scales governing learnability, refuting a conjecture attributed there to Phil Long that a multiplicative 2-factor gap is unavoidable, and improves the upper bounds of Bartlett and Long (JCSS 1998), which incur such a loss. The key technical ingredient is a direct bound on empirical $\ell_\infty$ covering numbers, avoiding the standard detour through packing numbers. As a consequence, we obtain sharp asymptotic metric-entropy bounds in terms of the fat-shattering scale $γ$: an $O(\log^2 n)$ bound holds already at scale $γ/2$, while an $O(\log n)$ bound holds at scale $2γ$. We further show that the $O(\log^2 n)$ bound is sometimes tight. These results resolve open questions by Alon et al. (JACM 1997) and Rudelson and Vershynin (Ann. of Math. 2006). As an application, we establish a sharp dichotomy for bounded integral probability metrics: every such IPM is either estimable or cannot be weakly evaluated within any multiplicative factor $c<3$, while $3$-weak evaluability always holds, resolving an open question from Aiyer et al. (ICML 2026). We also highlight several open questions on quantitative sample complexity and evaluability.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。