Azuma–Hoeffding and McDiarmid

SECTION 01Azuma–Hoeffding Inequality

Formulation · Azuma–Hoeffding

Let Dₖ be determined by X₁ᵏ and satisfy E[Dₖ | X₁ᵏ⁻¹] = 0. Suppose there are constants aₖ ≤ bₖ such that Dₖ ∈ [aₖ, bₖ] almost surely. Then

P (| \sum_{k = 1}^{n} D_{k} | \geq t) \leq 2 e^{- \frac{2 t^{2}}{\sum_{k = 1}^{n} {(b_{k} - a_{k})}^{2}}}, t \geq 0

Proof of Azuma–Hoeffding

The increments Dₖ need not be independent, so we cannot directly apply the earlier Hoeffding bound for independent sums. Instead, we control their sum’s MGF by conditioning on the past.

Write Sₙ = ∑ₖ₌₁ⁿ Dₖ and cₖ = bₖ − aₖ.

(1) Given X₁ᵏ⁻¹, the variable Dₖ still lies in [aₖ, bₖ] and has conditional mean zero. Apply the bounded-variable sub-Gaussian result to this conditional distribution:

E [e^{λ D_{k}} | X_{1}^{k−1}] \leq e^{\frac{λ^{2} {c_{k}}^{2}}{8}}, λ \in R

(2) Condition on X₁ⁿ⁻¹. Since Sₙ₋₁ is already determined by these inputs,

E [e^{λ S_{n}}] = E [e^{λ S_{n−1}} E [e^{λ D_{n}} | X_{1}^{n−1}]]

E [e^{λ S_{n}}] \leq E [e^{λ S_{n−1}}] e^{\frac{λ^{2} {c_{n}}^{2}}{8}}

Repeat this step for n − 1, n − 2, …, 1, ending with S₀ = 0:

E [e^{λ S_{n}}] \leq e^{\frac{λ^{2}}{8} \sum_{k = 1}^{n} {c_{k}}^{2}}

(3) Hence Sₙ is sub-Gaussian with parameter squared σ²_S = ¼ ∑ₖ₌₁ⁿ cₖ². Substituting this into the two-sided sub-Gaussian tail bound gives the stated result.

SECTION 02Bounded Differences and McDiarmid’s Inequality

We now apply Azuma–Hoeffding to the Doob increments of f(X). The goal is to control their conditional ranges through an easily checked property of f.

Definition · Bounded Differences

Given x, x′ ∈ ℝⁿ, let x^\k be x with only coordinate k replaced by x′ₖ:

x_{j}^{\ k} = {\begin{cases} x_{j} & j \neq k \\ x_{k}^{'} & j = k \end{cases}

The function f satisfies the bounded differences property with parameters (L₁, …, Lₙ) if, for every coordinate k and all x, x′,

| f (x) - f (x^{\ k}) | \leq L_{k}

Formulation · McDiarmid’s Inequality

If f satisfies this property and X₁, …, Xₙ are independent, then

P (| f (X) - E [f (X)] | \geq t) \leq 2 e^{- \frac{2 t^{2}}{\sum_{k = 1}^{n} {L_{k}}^{2}}}, t \geq 0

Proof of McDiarmid’s Inequality

Use the Doob increments

D_{k} = E [f (X) | X_{1}^{k}] - E [f (X) | X_{1}^{k−1}]

We show that, given X₁ᵏ⁻¹, Dₖ lies in an interval of length at most Lₖ. Fix the past inputs and write

g_{k} (x) = E [f (X_{1}, \dots, X_{k−1}, x, X_{k + 1}^{n}) | X_{1}^{k−1}]

Define the lower and upper endpoints

A_{k} = inf_{x} g_{k} (x) - E [f (X) | X_{1}^{k−1}]

B_{k} = sup_{x} g_{k} (x) - E [f (X) | X_{1}^{k−1}]

Since gₖ(Xₖ) lies between its infimum and supremum, Aₖ ≤ Dₖ ≤ Bₖ almost surely.

By independence, gₖ(x) averages only over the remaining inputs Xₖ₊₁, …, Xₙ. Write Eₖ₊₁ for this expectation. Then

B_{k} - A_{k} = sup_{x} g_{k} (x) - inf_{x} g_{k} (x)

B_{k} - A_{k} \leq sup_{x, y} | E_{k + 1} [f (X_{1}, \dots, X_{k−1}, x, X_{k + 1}^{n}) - f (X_{1}, \dots, X_{k−1}, y, X_{k + 1}^{n})] | \leq L_{k}

Thus Bₖ − Aₖ ≤ Lₖ. Although Aₖ and Bₖ may depend on the past, once X₁ᵏ⁻¹ is given they are fixed. The same conditional-MGF argument used above therefore applies with interval width Lₖ, yielding McDiarmid’s inequality.

The following examples apply the bounded differences inequality by controlling the effect of changing one input.

Example · Recover the Independent-Sum Bound

Let X₁, …, Xₙ be independent and take values in [a, b], with μₖ = E[Xₖ]. Consider

f (x_{1}, \dots, x_{n}) = \sum_{k = 1}^{n} (x_{k} - μ_{k})

Changing only coordinate k gives

| f (x) - f (x^{\ k}) | = | (x_{k} - μ_{k}) - ({x_{k}}^{'} - μ_{k}) | = | x_{k} - {x_{k}}^{'} | \leq b - a

Thus the bounded differences property holds with Lₖ = b − a for every coordinate. McDiarmid’s inequality gives

P (| \sum_{k = 1}^{n} (X_{k} - μ_{k}) | \geq t) \leq 2 e^{- \frac{2 t^{2}}{n {(b - a)}^{2}}}, t \geq 0

This recovers the classical Hoeffding bound for independent bounded variables.

Example · Concentration of a Supremum

Let ε₁, …, εₙ be independent Rademacher variables, each taking −1 and +1 with equal probability. Given a nonempty collection of vectors A ⊂ ℝⁿ with finite coordinate bounds sup_a∈A|aₖ|, define

Z = sup_{a \in A} \sum_{k = 1}^{n} a_{k} ε_{k} = sup_{a \in A} ⟨ a, ε ⟩

Z measures how well vectors in A align with random signs. Its expectation R(A) = E[Z] is the Rademacher complexity of A.

View Z as f(ε₁, …, εₙ). To apply McDiarmid, bound the change when one sign is replaced. Since f(ε^\k) ≥ ⟨a, ε^\k⟩ for every a ∈ A,

⟨ a, ε ⟩ - f (ε^{\ k}) \leq ⟨ a, ε - ε^{\ k} ⟩ = a_{k} (ε_{k} - {ε_{k}}^{'}) \leq 2 | a_{k} |

Taking the supremum over a ∈ A gives

f (ε) - f (ε^{\ k}) \leq 2 sup_{a \in A} | a_{k} |

Exchanging the two sign vectors gives the reverse inequality. Hence the absolute difference is bounded by Lₖ = 2 sup_a∈A|aₖ|.

McDiarmid therefore yields

P (| Z - E [Z] | \geq t) \leq 2 e^{- \frac{t^{2}}{2 \sum_{k = 1}^{n} sup_{a \in A} {a_{k}}^{2}}}, t \geq 0

Equivalently, the conditional-MGF argument underlying McDiarmid shows that Z − E[Z] is sub-Gaussian with parameter at most

\sqrt{\sum_{k = 1}^{n} sup_{a \in A} {a_{k}}^{2}}