Hoeffding's Lemma

Why This Matters

Hoeffding's inequality appears in the sample-complexity bound of every finite-class PAC argument on this site, and it is a one-line corollary of a single MGF estimate: Hoeffding's lemma. The lemma is the deeper result. It says that any zero-mean random variable supported on $[a, b]$ has a sub-Gaussian moment generating function with explicit parameter $(b - a)^2 / 4$, and the proof exposes exactly which two facts do the work — the convexity of $e^{\lambda x}$ and the curvature bound on a specific log-sum-exp function.

Once you internalize the lemma, every bounded-variable concentration statement on the site reduces to:

1. write down the MGF bound from Hoeffding's lemma,
2. multiply across independent (or martingale) summands,
3. run the Chernoff method and optimize.

The bound $\frac{(b-a)^2}{8}$ in the exponent is not folklore. It is the exact best constant achievable from convexity plus a second-derivative bound of $1/4$, and tracking where that $1/4$ comes from is what makes the proof rememberable.

Quick Version

For a centered random variable $X \in [a, b]$ almost surely,

$\mathbb{E}[e^{\lambda X}] \leq \exp\!\left(\frac{\lambda^2 (b-a)^2}{8}\right) \quad \text{for all } \lambda \in \mathbb{R}.$

In sub-Gaussian language: $X - \mathbb{E}[X]$ is sub-Gaussian with proxy variance $(b-a)^2/4$. The constant $1/8$ is sharp in this convexity-based proof; the $1/4$ in the proxy variance is the maximum of $p(1-p)$ over $p \in [0,1]$, and it appears as the Bernoulli$(1/2)$ worst case.

Mental Model

Three observations make the proof natural rather than mysterious.

1. Convexity of $e^{\lambda x}$ controls the worst-case mean MGF. Among all distributions on $[a, b]$ with a fixed mean, the one that maximizes $\mathbb{E}[e^{\lambda X}]$ is supported on the two endpoints $\{a, b\}$. Convexity of $e^{\lambda x}$ implies that mass at the interior is always dominated by the corresponding two-point mass.
2. The two-point worst case is a tilted Bernoulli. After centering, the worst-case distribution puts mass $p = -a/(b-a)$ at $b$ and mass $1 - p$ at $a$. Its log-MGF is the function $\psi(u) = -p u + \log(1 - p + p e^u)$ with $u = \lambda(b - a)$.
3. Curvature is bounded by $1/4$. A short calculation shows $\psi''(u) = q(u)(1 - q(u))$ where $q(u) \in [0, 1]$, so $\psi''(u) \leq 1/4$ uniformly in $u$ and $p$. Taylor's theorem with remainder then gives $\psi(u) \leq u^2 / 8$, and substituting $u = \lambda(b - a)$ recovers Hoeffding's lemma exactly.

Recall: convexity of $e^{\lambda x}$. For any convex $f$ and $\alpha \in [0,1]$, $f(\alpha a + (1-\alpha) b) \leq \alpha f(a) + (1-\alpha) f(b)$. Below we use $\alpha = (b - x) / (b - a)$ so that $x = \alpha a + (1 - \alpha) b$ and apply this to $f(x) = e^{\lambda x}$.

Formal Setup

Let $X$ be a real-valued random variable with $\mathbb{E}[X] = 0$ and $a \leq X \leq b$ almost surely, where $a < 0 < b$ (the centered case forces $a < 0$ unless $X$ is degenerate at zero). Define the standardized parameter $u = \lambda (b - a)$ and the convex weight $p = -a / (b - a) \in [0, 1]$.

\mathbb{E}[e^{\lambda X}] \leq \exp\!\left(\frac{\lambda^2 (b-a)^2}{8}\right)

From the Lemma to Hoeffding's Inequality

The lemma is the only nontrivial step in the proof of Hoeffding's inequality. The rest is the Chernoff method plus independence.

\Pr\!\left[\bar{X}_n - \mu \geq t\right] \leq \exp\!\left(-\frac{2 n^2 t^2}{\sum_{i=1}^n (b_i - a_i)^2}\right)

Bridge: Polynomial vs. Exponential Tails

Hoeffding's lemma is what changes the exponent from polynomial to exponential. The same sample mean $\bar{X}_n$ admits both a Chebyshev bound $\sigma^2 / (n t^2)$ and a Hoeffding bound $\exp\bigl(-2 n t^2 / (b-a)^2\bigr)$, and the second decays infinitely faster in $n$ for any fixed $t$. The practical effect: the sample size needed to certify $\Pr[|\bar{X}_n - \mu| \geq \epsilon] \leq \delta$ is $O(1 / (\delta \epsilon^2))$ under Chebyshev and $O(\log(1/\delta) / \epsilon^2)$ under Hoeffding. This is the reason every PAC sample-complexity statement carries a $\log(1/\delta)$ inside instead of a $1/\delta$.

Common Confusions

Exercises

References

Canonical:

• Hoeffding, W. (1963). "Probability Inequalities for Sums of Bounded Random Variables." Journal of the American Statistical Association, 58(301), 13-30. The original lemma is stated mid-paper as the MGF bound on which Hoeffding's inequality rests.
• Boucheron, S., Lugosi, G., & Massart, P. (2013). Concentration Inequalities. Oxford University Press. Lemma 2.2 (Hoeffding's lemma) and Theorem 2.8 (Hoeffding's inequality).
• Shalev-Shwartz, S., & Ben-David, S. (2014). Understanding Machine Learning. Cambridge University Press. Lemma B.7 (Hoeffding's lemma) and Lemma B.6 (Hoeffding's inequality) in Appendix B.

Current:

• Wainwright, M. J. (2019). High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press. Section 2.1.2 derives the lemma in the sub-Gaussian framework.
• Vershynin, R. (2018). High-Dimensional Probability. Cambridge University Press. Theorem 2.2.6 (Hoeffding's lemma) with discussion of sharpness.
• van Handel, R. (2016). Probability in High Dimension. Lecture notes, Princeton. Chapter 3 develops Hoeffding's lemma alongside the broader sub-Gaussian framework.

Next Topics

• Hoeffding's inequality: the corollary that almost every PAC sample-complexity bound invokes
• Bennett's inequality: variance-aware MGF bound, sharper when the variance is much smaller than the squared range
• Bernstein's inequality: the sample-mean form that follows from Bennett via $h(a) \geq a^2 / (2 + 2a/3)$
• Sub-Gaussian random variables: the abstract framework around the proxy variance $(b-a)^2 / 4$
• Azuma-Hoeffding (martingale extension): extension to martingale differences with bounded increments
• McDiarmid's inequality: bounded-differences concentration for functions of independent variables