Hoeffding Inequality

Definition

A concentration inequality bounds the probability that an empirical quantity deviates from its expectation by more than $\epsilon$. Hoeffding: independent $Z_1,\dots ,Z_n\in [0,1]$ with mean $S_n$. McDiarmid: independent $X_i$ and a function $f$ that changes by at most $c_i$ when only the $i$-th argument changes.

Formula

$$P(|S_n-E(S_n)|\ge \epsilon )\le 2e^{-2n{\epsilon }^2},P(|f-Ef|\ge \epsilon )\le 2\exp \left(\frac{-2{\epsilon }^2}{{\sum }_i{c}_i^2}\right)$$

• Independence is crucial, identical distributions are not needed.
• Hoeffding is McDiarmid with $f$ = mean and $c_i=1/n$.
• For a fixed function: $|R(f_0)-R_n(f_0)|\le \sqrt{\log (2/\delta )/(2n)}$ with probability $1-\delta$; about $1/{\epsilon }^2$ samples for accuracy $\epsilon$.

Appears in

• Lecture 3, Proposition 2
• Lecture 3, Theorem 3 (McDiarmid)
• Lecture 3, error of a fixed function and sample complexity
• Lecture 3, exam-style task
• Lecture 4, McDiarmid proves the stability bound

Related concepts

• Generalization Bound
• Uniform Convergence