concentration of self-bounding functions

Let $f:{\mathcal{X}}^n\to \mathbb{R}$ and $f_i:{\mathcal{X}}^n\to \mathbb{R}$ for $i=1,\dots ,n$. We say $f$ is self-bounding (wrt to $(f_i)$) if

$$0\le f(x)-f_i(x^{(i)})\le 1,$$

and

$$\sum _{i=1}^n(f(x)-f_i(x^{(i)}))\le f(x),$$

where $x^{(i)}$ drops the $i$-th coordinate of $x$. Often we take

$$f_i(x^{(i)})=\underset{x_i^{\prime }}{\inf }f(x^{(i)},x_i^{\prime }).$$

This definition has been weakened by others. See second ref below for details.

Results

Let $X_1,\dots ,X_n$ be independent, and set $X=(X_1,\dots ,X_n).$

If $f$ is self-bounding then it is roughly a Poisson random variable, in the sense that

$$\log \mathbb{E}[e^{\lambda (Z-\mathbb{E}Z)}]\le (e^{\lambda }-\lambda -1)\mathbb{E}Z,$$

where $Z=f(X^n)$. Consequently, applying the Chernoff method, one obtains that

$$\mathbb{P}(Z\ge \mathbb{E}Z+t)\le \exp \left(\frac{-t^2}{2(\mathbb{E}Z+t/3)}\right).$$

Also note that the first self-bounding property condition implies that $(f(X)-f_i(X^{(i)}){)}^2\le f(X)-f_i(X^{(i)})$. Therefore, the Efron-Stein inequality implies that

$$\mathbb{V}(Z)\le \sum _i\mathbb{E}[(f(X)-f_i(X^{(i)}{)}^2]\le \sum _i\mathbb{E}[f(X)-f_i(X^{(i)})]\le \mathbb{E}[f(X)]=\mathbb{E}Z,$$

where the final inequality follows from the second self-bounding property condition.

This simply fact, that the variance is bounded by the expected value, has many applications. See Section 3.1 in first ref below.

References

• Concentration inequalities by Boucheron, Lugosi, Massart, Chapter 3.1 and 3.3.
• Concentration of self-bounding functions by Boucheron, Lugosi, Massart