Extension of the Azuma-Hoeffding inequality (when the differences are bounded with large probability) 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.
 A: 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.
A: 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.
