McDiarmid’s Bounded Differences Inequality
Concentration, STAT 210B1 minute read
Part of the STAT 210B Results Toolbox: the result as stated in my 210B notes (Def. 2.44 and Prop. 2.45), plus the one proof step to recall to remember why it is true.
Statement
Definition 2.44 (Bounded Difference Property). The function \(g:\mathcal{X}^n\to\mathbb{R}\) has the bounded differences property if for all \((x_1,\dots,x_n,x_i’)\) and for all \(i=1,\dots,n\),
\[\big\lvert g(x_1,\dots,x_n) - g(x_1,\dots,x_i',\dots,x_n)\big\rvert \;\le\; c_i ,\]with constants \(c_1,\dots,c_n\).
Proposition 2.45 (Bounded Differences inequality (McDiarmid’s Inequality)). If \(X_1,\dots,X_n\) are independent random variables and \(g\) satisfies the bounded difference property, then for all \(t\ge0\),
\[\mathbb{P}\big( g(X_1,\dots,X_n) - \mathbb{E}\,g(X_1,\dots,X_n) \ge t \big) \;\le\; \exp\left( \frac{-2t^2}{\sum_{k} c_k^2} \right)\]and
\[\mathbb{P}\big( \big\lvert g(X_1,\dots,X_n) - \mathbb{E}\,g(X_1,\dots,X_n)\big\rvert \ge t \big) \;\le\; 2\exp\left( \frac{-2t^2}{\sum_{k} c_k^2} \right).\]With \(c_i = 1/n\) for every \(i\) — the typical case for an empirical average or a supremum of empirical averages over a \([0,1]\)-valued class — this reads \(g \le \mathbb{E}g + \epsilon\) with probability \(1 - e^{-2n\epsilon^2}\).
The fundamental step
Build the Doob martingale of conditional expectations,
\[D_i \;=\; \mathbb{E}\big[g \mid X_1,\dots,X_i\big] - \mathbb{E}\big[g \mid X_1,\dots,X_{i-1}\big], \qquad g - \mathbb{E}g = \sum_{i=1}^n D_i,\]i.e. reveal the inputs one at a time and track how the conditional expectation of \(g\) moves. Bounded differences says each increment lives in an interval of length \(c_i\), so Hoeffding’s lemma bounds each conditional MGF by \(e^{\lambda^2 c_i^2/8}\), and the tower property multiplies them up exactly as if the increments were independent.
The memory hook: revealing one coordinate at a time turns an arbitrary function of independent inputs into a sum of bounded martingale increments — and a sum of bounded increments is Hoeffding.
Where it’s used
- Twice inside the Rademacher generalization bound (Ma Thm. 4.18), as recorded in the Rademacher complexity notes: once to concentrate \(\sup_f [\frac1n\sum_i f(z_i) - \mathbb{E}f]\) around its mean, and once to replace the population Rademacher complexity \(R_n\) by the computable empirical \(R_S\).
- The companion in-expectation step is symmetrization.
Leave a Comment