empirical Bernstein bounds

A Bernstein bound is a kind of concentration inequality that takes advantage of the variance of the distribution. They are usually part of a progression of bounds for random variables with bounded range. See from boundedness to variance adaptivity.

Empirical-Bernstein bounds replace knowledge of the variance with data-driven estimates of the variance. This is useful since we often don’t know what the variance is. Ideally, such bounds can be shown to converge in the limit to a bound with width depending on the true variance — i.e., they scale asymptotically with the true variance.

Some examples:

Scalar-random variables

The first empirical Bernstein bound was given by Maurer and Pontil in 2009. A second, tighter bound, was given by Waudby-Smith and Ramdas using the betting approach to concentration (see estimating means by betting). These are very reminiscent of Bennett’s bound (estimating means by betting). These are very reminiscent of Bennett’s bound (light-tailed scalar concentration:Bennett’s bound), but has a data-driven variance term.

Let $X_1,X_2,,\dots ,X_n$ be iid random variables in $[0,1]$. The Maurer and Pontil bound reads that with probability $1-\delta$,

$$|\frac{1}{n}\sum _i{X}_i-\mathbb{E}{X}_1|\le \sqrt{\frac{2{\hat{\sigma }}_n\log (2/\delta )}{n}}+\frac{7\log (1/\delta )}{3(n-1)},$$

where ${\hat{\sigma }}_n=\frac{1}{n(n-1)}{\sum }_{i<j}(X_i-X_j{)}^2$ is the sample variance. The width of the bound, $W_n$ (the RHS above), has the limiting behavior $\sqrt{n}{W}_n\to \sigma \sqrt{2\log (4/\alpha )}$.

For the same setting, the bound by Waudby-Smith and Ramdas gives that for any ${\lambda }_n>0$, with probability $1-\delta$,

$$|\frac{1}{n}\sum _i{X}_i-\mathbb{E}{X}_1|\le \frac{\log (1/\alpha )+{\psi }_E({\lambda }_n){\sum }_{i\le n}{v}_i}{{\lambda }_{n}n},$$

for $v_i-{\hat{\mu }}_{i-1}$ where ${\hat{\mu }}_{i-1}$ is any function based on $X_1,\dots ,X_{i-1}$ (though one should think of it as roughly $\frac{1}{i}{\sum }_{j\le i}{X}_i$). For the appropriate choice of ${\lambda }_n$ the width scales as $\sqrt{n}{W}_n\to \sigma \sqrt{2\log (2/\alpha )}$, which is optimal and has the same asymptotic variance as the Hoeffding bound (light-tailed scalar concentration:Hoeffding bound).

Finally, betting techniques can yield other empirical-Bernstein bounds depending on the choice of predictable plug-in. These do not have closed-form solutions, but are often tighter. See estimating means by betting.

Random vectors

Using elements of the Pinelis approach to concentration in addition to some game-theoretic techniques (game-theoretic statistics), Martinez-Taboada and Ramdas gave a time-uniform empirical Bernstein bound in (2,$D$)-smooth Banach spaces. They show that, for $X_1,X_2,\dots$ with conditional mean $\mu$ with $\left|X_i\right|\le 1/2$. Then, with probability $1-\alpha$, simultaneously for all $t$:

$$\left|\frac{{\sum }_{i\le t}{\lambda }_i{X}_i}{{\sum }_{i\le t}{\lambda }_i}-\mu \right|\le D\frac{\frac{1}{2}{\sum }_{i\le t}{\psi }_E({\lambda }_i){\left|X_i-{\hat{\mu }}_{i-1}\right|}^2+2\log (1/\alpha )}{{\sum }_{i\le t}{\lambda }_i}.$$

where ${\overline{\mu }}_t={\sum }_{i\le t}{\lambda }_i{X}_i/{\sum }_{i\le t}{\lambda }_i$ and ${\psi }_E(\lambda )=-\log (1-\lambda )-\lambda$ and $({\lambda }_t)$ is a predictable sequence with values in $(0,0.8]$.

We also give an empirical-Bernstein bound for random vectors in ${\mathbb{R}}^d$ in Time-uniform confidence spheres for means of random vectors using the variational approach to concentration but it has explicit dependence on the dimension.

Random matrices

Wang and Ramdas develop an empirical Bernstein bound for random matrices.todo