Extension of the Azuma-Hoeffding inequality (when the differences are bounded with large probability)

Question

Let $(X_i)$ be a super-martingale and suppose their differences are bounded ''with high probability'', that is $$\mathbb{P}(\exists\,i=1,\dots,n\text{ s.t. }|X_i-X_{i-1}|>c_i) \,\leq\, \epsilon$$ for suitable constants $(c_i)$ and $\epsilon>0$. I read in Dubhashi-Panconesi book that for all $t>0$ $$\mathbb{P}(X_n>X_0+t) \,\leq\, \exp\left(-\frac{t^2}{2\,\sum_{i=1}^nc_i^2}\right) +\,\epsilon\;.$$

How can I prove this result? I already know that it holds for $\epsilon=0$ (it is the so called Azuma-Hoeffding inequality). But I don't manage to deduce this corollary. My first idea was to split and bound the probability as follows: $$\mathbb{P}(|X_n-X_0|<t) \,\leq\, \mathbb{P}(|X_n-X_0|<t \ \big|\ \forall\,i=1,\dots,n\,|X_i-X_{i-1}|\leq c_i) \,+\, \epsilon$$ but then I don't know how to bound the first term on the r.h.s. because I don't know if $(X_i)$ is still a super-martingale with respect to the conditional probability.

Answer 1

The general idea behind such inequalities is to follow the martingale $X$ until you lose control over the differences, then force it to be constant. This defines a new martingale $Y$ with bounded differences, which is therefore concentrated. You then add to your probability of error the probability that the differences of $X$ are too large, so that $Y \neq X$.

This is worked out carefully for a wide range of various of various desirable properties that might fail with some small probability in Section 8 of Fan Chung and Linyuan Lu's Concentration inequalities and martingale inequalities — a survey.

Answer 2

Take a look at the Kutin-Niyogi extension of McDiarmid's inequality: "Almost-Everywhere Algorithmic Stability and Generalization Error", UAI 2002 people.cs.uchicago.edu/~niyogi/papersps/uai-stability.ps

or the more recent paper, https://dl.dropboxusercontent.com/u/3198145/mcdiarmid-unbounded.pdf "Concentration in unbounded metric spaces and algorithmic stability", ICML 2014 The latter has a lot of additional references.

Answer 3

As stated, the bound is actually false, as the following counter example shows: let $n=1$, $X_0 = 0$ and let $X_1$ be a random variable which is equal to $1$ with probability $1-\epsilon$, and equal to $-\frac{1-\epsilon}\epsilon$ with probability $\epsilon$ where $\epsilon$ is a small (as it turns out, $\epsilon=1/10$ will do). For $c_1=1.2$ and $t=.9$, the probability on the left hand side is equal to $ \mathbb P(X_1 > 0.9)=1-\epsilon$, while the claimed bound becomes $$ \mathbb P(X_1 > 0.9) \leq \exp\left(-\frac{(0.9)^2}{2(1.2)^2}\right) + \epsilon = \exp(-9/32) + \epsilon \approx 0.755 + \epsilon. $$ which is strictly smaller than $1-\epsilon$ for $\epsilon$ small enough.

To make the statement true, you need a slightly stronger bound on the Martingale differences, which is easiest formulated in a Doob-Martingale setting where $X_i=\mathbb E[f|Y_1,\dots, Y_i]$ for a function $f$ of some independent random variables $Y_1,\dots,Y_n$. If you define $$\Delta_i(Y_1,\dots,Y_{i-1})=\sup_x|\mathbb E[f|Y_1,\dots,Y_{i-1}, Y_{i}=x] - \mathbb E[f|Y_1,\dots,Y_{i-1}] |, $$ then it is true that $$ \mathbb P(X_n-X_0\geq t)\leq \exp\left(-\frac{t^2}{2\sum_ic_i^2}\right) + \mathbb P(\exists i: \Delta_i>c_i). $$ To prove the statement, defined a stopping time $\tau$ such that $\tau$ is equal to the first $i\in \{0,1,\dots,n-1\}$ such that $\Delta_{i+1}(Y_1,\dots,Y_i)>c_{i+1}$ and consider the stopped martingale $X_{n\wedge \tau}$.

See also [Tao, T. and Vu, V., https://doi.org/10.1002/rsa.10032] Section 3, which to my knowledge is the first place introducing the stronger Martingale difference condition.