18
$\begingroup$

I was going through some notes on concentration inequalities when I noticed that there are two commonly-cited forms of McDiarmid's inequality. Long story short: I know how to prove the weaker one from Azuma's inequality. I also know how to prove the stronger one not directly from Azuma. But is there a way to prove the strong one from Azuma's inequality?

In what follows I will assume for simplicity that all differences are bounded by 1.

Azuma's inequality: Let $S_n = \sum_{i=1}^n X_i$ and $S_0 = 0$. Let the filtration $\{\mathcal{F}_n\}$ be the usual one defined by $\mathcal{F}_n = \sigma(X_1, \ldots, X_n)$. If $\{S_n\}_{n \geq 0}$ is a martingale and $|X_n| \leq 1$ for all $n$, then for $\lambda>0$, $$P(S_n \geq \lambda) \leq \exp \left(-\frac{\lambda^2}{2n} \right)$$

Now here is the "weak" version of McDiarmid's which is an obvious application of Azuma's inequality:

McDiarmid's inequality: Suppose $\xi_1, \ldots, \xi_n$ are independent. Let $Z = f(\xi_1, \ldots, \xi_n)$. Also, assume that: $$ \Big|\; f(\xi_1, \ldots, \xi_k, \ldots, \xi_n) - f(\xi_1, \ldots, \xi_k', \ldots, \xi_n) \;\Big| \leq 1$$ for two realizations of the same random variable $\xi_k$ and $\xi_k'$. Then for $\lambda>0$, $$ P(Z-EZ \geq \lambda) \leq \exp \left(-\frac{\lambda^2}{2n} \right) $$

Now the strong version of McDiarmid's inequality has the same setup except that the "2" in the denominator is moved up to the numerator, so the bound is: $$P(Z-EZ \geq \lambda) \leq \exp \left(-\frac{2\lambda^2}{n} \right)$$ Clearly this bound is sharper than the one in the version presented above. I know a proof for this bound but it does not explicitly use Azuma's inequality above.

The question: Is it possible to adapt Azuma's inequality to prove this second bound. More specifically, is there a more general form of Azuma's inequality that can be applied to the case of McDiarmid's inequality to yield the tighter bound?

Edit: After pondering it over, I now think that it is not possible. Just intuitively, the bounded martingale difference condition in Azuma's inequality seems somehow "weaker" than the condition in McDiarmid's inequality, which is a Lipschitz-like condition on the function $f$. So one would expect that using Azuma's inequality would not give the sharpest bound.

Edit 2: To shed some more light on this, the proof of the "weak" McDiarmid's using Azuma's inequality goes like this. Define $S_n = E(Z \;|\; \xi_1, \ldots, \xi_m) - EZ$. Then $\{S_m\}_{m \geq 1}$ is a martingale. Also, for $m=n$, $S_m = S_n = Z - EZ$.

To prove that the martingale differences are bounded, let $\xi_1', \ldots, \xi_n'$ be independent copies of the $\xi_1, \ldots, \xi_n$. Then we have: $$ E\big[f(\xi_1, \ldots, \xi_m, \ldots, \xi_n) \;\big|\; \xi_1, \ldots, \xi_{m-1}\big] = E\big[f(\xi_1, \ldots, \xi_m', \ldots, \xi_n) \;\big|\; \xi_1, \ldots, \xi_m\big] $$ Thus we have: $$\big|S_m - S_{m-1}\big| \leq E\big[|\, f(\xi_1, \ldots, \xi_m, \ldots, \xi_n) - f(\xi_1, \ldots, \xi_m', \ldots, \xi_n)\,| \;\big|\; \xi_1, \ldots, \xi_m\big]$$ So to satisfy the bounded martingale difference in Azuma's inequality, we only need the expectation of the difference of $f(\cdot) - f(\cdot)$ (conditional on $\xi_1, \ldots, \xi_m$) to be bounded, whereas the assumption in McDiarmid's is slightly stronger. However, the bounded martingale difference must also hold for all $m$, and in particular for the case of conditioning on $\xi_1, \ldots, \xi_n$. In that case it seems to reduce to assumption. So... it does seem like Azuma's inequality (in this form) is not strong enough. Thoughts?

Here is a resource presenting the "standard" proof of the strong version of McDiarmid's inequality: http://empslocal.ex.ac.uk/people/staff/yy267/McDiarmid.pdf

$\endgroup$
  • 1
    $\begingroup$ Have you looked at the original McDiarmid paper? I have uploaded it for you here. $\endgroup$ – ivan Aug 9 '13 at 10:24
4
$\begingroup$

The difference is the sharper constants for the sub-Gaussian norm/parameter of the bounded variables. You can still use Azuma's technique to get the sharper bound. Here are some notes I wrote a while ago:

Sub-Gaussian tail bounds

  • Recall that $\mathbb{E} e^{\lambda X} \le e^{\sigma^2 \lambda^2/2 }$ implies the following tail bound ($\mathbb{E} X = 0$) \begin{align*} \mathbb{P}( X \ge t) \le \exp\Big( {- \frac{t^2}{2\sigma^2}}\Big) \end{align*} Such a random variable is called sub-Gaussian with parameter $\sigma$.

  • A bounded variable $X \in [a,b]$ has squared sub-G parameter $\sigma^2 = (b-a)^2/4$. This sharp bound requires some work to show (left as an exercise.)

Azuma-Hoeffding approach

We want to provide concentration bounds for $Z = f(X) = f(X_1,\dots,X_n)$.

Let $\mathbb{E}_i[Z] := \mathbb{E}[Z | X_1,\dots,X_i]$ and $\Delta_i = \mathbb{E}_i[Z] - \mathbb{E}_{i-1}[Z]$. Then, $\{\Delta_i\}$ is a martingale difference sequence: $\mathbb{E}_{i-1}[\Delta_i] = 0$. Let $S_j := \sum_{i=1}^j \Delta_i$ which is only a function of $X_i, i \le j$. \begin{align*} S_n = \sum_{i=1}^n \Delta_i = Z - \mathbb{E} Z \end{align*} Let us assume that (*) $\mathbb{E}_{i-1} [e^{\lambda \Delta_i}] \le e^{\sigma_i^2 \lambda^2/2}$ for all $\lambda \ge 0$, and all $i$, almost surely. Then, \begin{align*} \mathbb{E}_{n-1} [ e^{\lambda S_n}] = e^{\lambda S_{n-1}}\mathbb{E}_{n-1} [ e^{\lambda \Delta_n}] \le e^{\lambda S_{n-1}} e^{\sigma_n^2 \lambda^2/2} \end{align*} Taking $\mathbb{E}_{n-2}$ of both sides: \begin{align*} \mathbb{E}_{n-2} [ e^{\lambda S_n}] \le e^{\sigma_n^2 \lambda^2/2} \mathbb{E}_{n-2}[ e^{\lambda S_{n-1}} ] \le e^{\lambda S_{n-2}} e^{(\sigma_n^2 + \sigma_{n-1}^2)\lambda^2/2} \end{align*} Repeating the process, we get $\mathbb{E}_{0} [e^{\lambda S_n}] \le \exp ( (\sum_{i=1}^n \sigma_i^2)\lambda^2/2 ) $. Showing that $S_n$ is sub-G with squared-param. $\sigma^2 = \sum_{i=1}^n \sigma_i^2$.

Bounded difference

Conditional sub-G assumption (*) holds under bounded difference \begin{align*} |f(x_1,\dots,x_{i-1},x_i,x_{i+1},\dots,x_n) - f(x_1,\dots,x_{i-1},x_i',x_{i+1},\dots,x_n)| \le L_i \end{align*} Let $g_i(x_1,\dots,x_i) := \mathbb{E}[f(x_1,\dots,x_{i-1},x_i,X_{i+1},\dots,X_n) ]$ so that $\mathbb{E}_i[Z] = g_i(X_1,\dots,X_i)$. This uses independence, i.e. the distribution of the rest does not change by conditioning. It is easy to see that $g_i$ satisfies bounded difference condition with constants $(L_1,\dots,L_i)$, by an application of Jensen.

  1. Naive bound: We have \begin{align*} \Delta_i = \mathbb{E}_i[Z] - \mathbb{E}_{i-1}[\mathbb{E}_i[Z]] = g_i(X_1,\dots,X_i) - \mathbb{E}_{i-1}[g_i(X_1,\dots,X_i)] \end{align*} Conditioned on $X_1,\dots,X_{i-1}$, we are effectively looking at ($X'_i$ is an independent copy of $X_i$) \begin{align*} g_i(x_1,\dots,x_{i-1},X_i)- \mathbb{E}[g_i(x_1,\dots,x_{i-1},X'_i)] \end{align*} due to independence of $\{X_i\}$. Thus, $|\Delta_i| \le L_i$ condition on $X_1,\dots,X_{i-1}$. That is, $\mathbb{E}_{i-1} [e^{\lambda \Delta_i}] \le e^{\sigma_i^2 \lambda^2/2}$ where $\sigma_i^2 = (2L_i)^2/4 = L_i^2$.

  2. Better bound: We can show that $\Delta_i \in I_i$ where $|I_i| \le L_i$, improving the constant by $4$: Conditioned on $X_1,\dots, X_i$, we are effectively looking at \begin{align*} \Delta_i = g_i(x_1,\dots,x_{i-1},X_i) - \mu_i \end{align*} where $\mu_i$ is a constant (only a function of $x_1,\dots,x_{i-1}$). Then, $\Delta_i + \mu_i \in [a_i,b_i]$ where $a_i = \inf_x g_i(x_1,\dots,x_{i-1},x)$ and $b_i = \sup_x g_i(x_1,\dots,x_{i-1},x)$. We have \begin{align*} b_i - a_i = \sup_{x,y} \big[ g_i(x_1,\dots,x_{i-1},x) - g_i(x_1,\dots,x_{i-1},y) \big] \le L_i \end{align*} Thus, we have $\mathbb{E}_{i-1}[e^{\lambda \Delta_i}] \le e^{\sigma^2 \lambda^2/2}$ where $\sigma_i^2 = (b_i-a_i)^2/4 \le L_i^2/4$.

$\endgroup$
0
$\begingroup$

I guess to get the weak version of McDiarmid's inequality from Azuma's inequality directly, we don't need the assumption that $\xi_1, \ldots, \xi_n$ are independent. It can be checked by your proof of boundness.

So one more conjecture: the strong version of McDiarmid's inequality may actually need the assumption that $\xi_1, \ldots, \xi_n$ are independent.

$\endgroup$
  • $\begingroup$ Both require independence. $\endgroup$ – passerby51 Apr 14 '17 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.