这个不等式是Azuma鞅不等式的一个特例见Azuma不等式 ，下面的证明不用复杂的理论。 从wikipedia摘抄的。 注意，markov不等式中的y是x，不等式右边的E(X) ,换成E(|X|)。证明过程假设X是非负随机变量 下面几个typo，然后下面X在[a,b]区间的概率为1，应该是P(X \in [a,b]) = 1 Hoeffding不等式如下： 设是取值在区间中的随机变量，令

之前提过的 Professor Yaser Abu-Mostafa 的机器学习课程在 Lecture 5、6、7 三课中讲到了 VC Theory 的一些内容，用来回答他在课程中提到的“Can We Learn？”这个问题。更具体地来说，他这里主要解决了 binary classification 问题中的 Learnability 的问题，结论就是：如果 hypothesis space

照片由Unsplash上的Luca Bravo拍摄 1：背景与动机 霍夫丁不等式是数理统计和机器学习 (ML) 中的一个重要的集中不等式，广泛应用于统计学习理论等理论领域以及强化学习等应用领域。 我注意到，在机器学习社区的一些地方，通常将 Hoeffding 的不等式呈现为“给定”，而对于所述不等式的来源仅提供轻微的直觉（如果有的话）。