改进经典VC定理的收敛速率估计，提升大样本下的精度。
A Refinement of Vapnik--Chervonenkis' Theorem
- 用正态近似替代霍夫丁不等式，控制误差更精确
- 在ε√n较大时，收敛速度比传统估计快约(ε√n)⁻¹倍
- 适合关注理论边界与高精度分析的研究者
Vapnik--Chervonenkis 定理是机器学习中的基石性结果，它给出了经验概率在事件族上一致收敛到理论概率的充分条件，并提供了收敛速率的估计。本文重新审视经典证明中的概率部分，不再使用霍夫丁不等式作为最后一步，而是采用带有显式 Berry--Esseen 误差控制的正态近似。该方法得到了一个中偏差意义下的精化估计，在 ε√n 较大时，主指数项中多出一个阶为 (ε√n)⁻¹ 的因子，从而改进了传统的 VC 估计。
原文摘要 · Abstract (English)
Vapnik--Chervonenkis' theorem is a seminal result in machine learning. It establishes sufficient conditions for empirical probabilities to converge to theoretical probabilities, uniformly over families of events. It also provides an estimate for the rate of such uniform convergence. We revisit the probabilistic component of the classical argument. Instead of applying Hoeffding's inequality at the final step, we use a normal approximation with explicit Berry--Esseen error control. This yields a moderate-deviation sharpening of the usual VC estimate, with an additional factor of order $(\varepsilon\sqrt{n})^{-1}$ in the leading exponential term when $\varepsilon\sqrt{n}$ is large.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。