light-tailed scalar concentration

Here we list concentration inequalities for scalar-valued random variables under various light-tailed conditions (which typically means that the MGF exists in some neighborhood). This is contrast to heavy-tailed scalar concentration, where we assume only a few moments.

For rvs $X_1,\dots ,X_n$ let ${\overline{X}}_n=\frac{1}{n}{\sum }_{i=1}^n{X}_i$.

Many of these concentration inequalities are proven using corresponding exponential inequalities. There are also time-uniform versions of these inequalities which stem from the sub-psi process given by the corresponding exponential inequality.

Bounded random variables

Hoeffding bound

Let $X_1,\dots ,X_n$ be independent with $a_i\le X_i\le b_i$. Hoeffding showed that

$$\mathbb{P}(|{\overline{X}}_n-\mu |\ge ϵ)\le 2\exp \left(\frac{-{ϵ}^2{n}^2}{{\sum }_{i=1}^n(b_i-a_i)}\right).$$

The natural one sided versions also exist. This is generalized by McDiarmid’s inequality (bounded difference inequalities).

Bennett’s inequality

Hoeffding’s bound doesn’t use any information beside boundedness of the observations. It therefore must (implicitly) assume a worse case bound on the variance. If we know a bound on the variance, we can do better. Both Bennett’s inequality and Bernstein’s inequality use such information to tighten the bound.

Let $X_1,\dots ,X_n$ be independent with finite variance and one-sided boundedness, i.e., $X_i\le B$ for some $B$. If ${\sigma }^2={\sum }_{i\le n}\mathbb{E}[(X_i-\mathbb{E}{X}_i{)}^2]$ and $S={\sum }_{k\le n}(X_i-\mathbb{E}{X}_i)$ then

$$\mathbb{P}(S\ge ϵ)\le \exp \left(-\frac{{\sigma }^2}{B^2}h(Bϵ/{\sigma }^2)\right),$$

where $h(u)=(1+u)\log (1+u)-u$. If we assume that $|X_i|\le B$ then we can get a bound on $|S|$. This trend of first presenting a result using only the boundedness of observations and then giving a variance-adaptive result is a common one, see from boundedness to variance adaptivity.

If the $X_i$ have conditional mean $\mu$, then we can replace ${\sigma }^2$ with ${\sum }_{i\le n}{\mathbb{E}}_{i-1}{\left|X_i-\mathbb{E}{X}_i\right|}^2$ where ${\mathbb{E}}_{i-1}$ is the expectation conditional on the first $i-1$ observations.

Bernstein bound 1

There are several bounds that go under the name “Bernstein bound”. The most common is perhaps a relaxation of Bennett’s bound and uses that

$$h(u)\ge \frac{u^2}{2(1+u/3)},$$

to show that

$$\mathbb{P}(S\ge ϵ)\le \exp \left(-\frac{{ϵ}^2}{2(M+Bϵ/3)}\right),$$

where $M$ and $B$ are as above. Both Bennett’s bound and Bernstein’s bound are proven using the Chernoff method.

There are two regimes in Bernstein’s bound: A sub-Gaussian regime where the tail decays at a sub-Gaussian rate, and a sub-exponential regime where it decays at a sub-exponential rate. The former occurs when the contribution of $Bϵ/3$ is small, so the tail decays as ${ϵ}^2$. When $Bϵ/3$ is large, the bound decays as $ϵ$.

Empirical Bernstein bounds

Empirical Bernstein bounds replace the oracle variance with an estimated variance. This is useful because the true variance is not always known. These bounds deserve their own page: empirical Bernstein bounds.

todo non-bounded stuff

References

• Concentration inequalities by Boucheron, Lugosi, and Massart.