concentration in Banach spaces

Pinelis is responsible for both a Hoeffding and Bernstein bound in smooth and separable Banach spaces. At the core of his proof is the construction of a supermartingale; his results can therefore be made time-uniform by applying Ville’s inequality instead of Markov’s inequality (though they’re usually stated as fixed-time bounds).

Hoeffding

Consider a $(2,D)$-smooth separable Banach space with norm $\left|\cdot \right|$. Let $X_1,X_2,\dots$ have conditional mean $0$ with $\left|X_t\right|\le B$. Then:

$$\mathbb{P}\left(\left|\sum _{i\le n}{X}_i\right|\ge u\right)\le 2\exp \left(-\frac{u^2}{2n{D}^2{B}^2}\right).$$

Note the similarity to the usual Hoeffding bound (light-tailed scalar concentration) but with the extra factor of $D$. This is because Hilbert spaces are $(2,1)$-smooth Banach spaces.

Bernstein

Consider a $(2,D)$-smooth separable Banach space with norm $\left|\cdot \right|$. Let $X_1,X_2,\dots$ have conditional mean $0$ with $\left|X_t\right|\le B$. Then

$$\mathbb{P}\left(\left|\sum _{i\le n}{X}_i\right|\ge u\right)\le 2\exp \left(-\frac{u^2/2}{D^2{\left|{\sum }_{i\le n}{\mathbb{E}}_{i-1}{\left|X_i-\mu \right|}^2\right|}_{\infty }+uB/3}\right).$$

Like for Bernstein’s/Bennett’s inequality in the scalar setting (Bennett’s inequality), if the random variables are iid then ${\mathbb{E}}_{i-1}{\left|X_i-\mu \right|}^2$ is simply the variance.

Empirical-Bernstein

See discussion on the work of Martinez-Taboada and Ramdas in empirical Bernstein bounds:

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.

Link to original

Heavy-tailed concentration

In 2015, Minsker proposed the geometric median-of-means for Banach spaces. This is a general method for boosting weak (polynomial rate) estimators into an estimator with exponential rate. The idea is similar to the Lugosi-Mendelson median-of-means (see multivariate heavy-tailed concentration), but the weak estimators are aggregated using the geometric median. This can be computed in polynomial time (in ${\mathbb{R}}^d$) using Weisfeld’s algorithm, since the objective is convex. This estimator was proposed simultaneously by Hsu and Sabato.

In 2022, Yun and Park extended geometric median-of-means to Polish spaces, which include separable Banach spaces. They seem to get the same rates as Minsker, which are not quite sub-Gaussian in ${\mathbb{R}}^d$.