concentration inequality

Let $Z_1, Z_2, ..., Z_m$ be $m$ i.i.d. Bernoulli($\phi$) random variables ($P(Z_i = 1) = \phi)$.

Let $\hat{\phi} = \frac{1}{m} \sum_{i=1}^m Z_i$, and let $\gamma >0$ be fixed. Then

$P(|\phi - \hat{\phi} |> \gamma) \leq 2 \exp{(-2\gamma^2 m)}$

Video – Intuition, similar to Central limit theorem, but this isn't an asymptotic result!

https://www.wikiwand.com/en/Hoeffding's_inequality

video, where it is applied to proving agnostic lernability

Very similar to the Chernoff bound