"Bernstein version" of McDiarmid?

202 Views Asked by At

I have seen used in a paper the following variant of McDiarmid's inequality, referred to as a "Bernstein-type variant":

Theorem. Let $f\colon \mathbb{R}^n \to \mathbb{R}$, and $X_1,\dots, X_n$ be independent random variables, and let, for $1\leq i\leq n$, $$ v_i^2 := \max_{x\in\mathbb{R}^n} \mathbb{E}[ (f(x_1,\dots, x_{i-1}, X_i, x_{i+1}, \dots, x_n) - \mathbb{E}[f(x_1,\dots, x_{i-1}, X_i, x_{i+1}, \dots, x_n)])^2], $$ and $$ B := \max_{1\leq i\leq n}\max_{x\in\mathbb{R}^n} |f(x) - \mathbb{E}[f(x_1,\dots, x_{i-1}, X_i, x_{i+1}, \dots, x_n)]| $$ Then, for all $t>0$, we have $$ \mathbb{P}\{ |f(X)-\mathbb{E}[f(X)]| \geq t \} \leq 2\exp\left({-\frac{t^2}{2\sum_{i=1}^n v_i^2 + \frac{t}{3}B}}\right) $$

The reference given is this note by Y. Ying (PDF), and I couldn't find any other source.

In particular, this doesn't seem to be mentioned, or immediately follow from any of the results in the Boucheron–Lugosi–Massart Concentration Inequalities book (it looks related to Theorems 6.16, 8.6, and 12.2, but they seem either weaker or incomparable (?)).

Is there a textbook or peer-reviewed reference for the statement above (or an analogous one, with maybe different constants)?

1

There are 1 best solutions below

0
On BEST ANSWER

A colleague pointed to me that this is described in Eq. (8.5) of [1] (the result then follows from their Theorem 8.2 combined with this), and shown in Problem 8.14 in that book.

It is also in the original paper by McDiarmid [2], as Theorem 3.8.

[1] Dubhashi, Devdatt P.; Panconesi, Alessandro. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, Cambridge, 2009. xvi+196 pp. ISBN: 978-0-521-88427-3

[2] McDiarmid, Colin. Concentration. Probabilistic methods for algorithmic discrete mathematics, 195--248, Algorithms Combin., 16, Springer, Berlin, 1998.