concentration in Banach spaces

Pinelis (see his 1992 and 1994 papers) 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 (see Pinelis approach to concentration) 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).

Chebyshev

The sample mean doesn’t necessarily concentrate in Banach spaces (see discussion in Banach space). One needs a smoothness assumption. But once such an assumption is added, we can get the following behavior of the sample mean. This result is from Mean Estimation in Banach Spaces Under Infinite Variance and Martingale Dependence.

Let $(X_n{)}_{n\ge 1}$ be random variables in a $(2,\beta )$-smooth Banach space which have conditional mean $\mu$ and conditional $p$-th moment, $p>1$, bounded by $v$ (i.e., $\mathbb{E}[\Vert X_n-\mu {\Vert }^p|{\mathcal{F}}_{n-1}]\le v$). Then, for any $\delta \in (0,1)$ and $n\ge 1$, we have

$$\mathbb{P}\left(\Vert {\hat{\mu }}_n-\mu \Vert \le \frac{2\beta v}{n^{(p-1)/p}}\right)\ge 1-\delta ,$$

or equivalently,

$$\mathbb{P}(\Vert {\hat{\mu }}_n-\mu \Vert \ge t)\le \frac{v{2}^p{\beta }^p}{n^{p-1}{t}^p}.$$

where ${\hat{\mu }}_n:=n^{-1}{\sum }_{m=1}^n{X}_m$ denotes the usual sample mean. So we see that $\beta$ pops up in the bound.

Marcinkiewicz–Zygmund inequality

The proof of Chebyshev’s inequality above actually relies on a Marcinkiewicz–Zygmund-style inequality in smooth Banach spaces. Let $(X_n{)}_{n\ge 1}$ be random variables in a $(2,\beta )$-smooth Banach space such that ${\mathbb{E}}_{n-1}{X}_n=0$ and $\mathbb{E}\Vert X_n{\Vert }^p<\infty$ for all $n\ge 0$ and some $p\in (1,2]$. Then, letting $(S_n{)}_{n\ge 0}$ be $S_n:=X_1+\cdots +X_n$, we have

$$\mathbb{E}\Vert S_n{\Vert }^p\le 2^p{\beta }^p\mathbb{E}\left[{\left(\sum _{m=1}^n\Vert X_m{\Vert }^2\right)}^{p/2}\right]\le 2^p{\beta }^p\sum _{m=1}^n\mathbb{E}\Vert X_m{\Vert }^p.$$

Hoeffding

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

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

Note the similarity to the usual Hoeffding bound (bounded 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 $\Vert \cdot \Vert$. Let $X_1,X_2,\dots$ have conditional mean $0$ with $\Vert X_t\Vert \le B$. Then

$$\mathbb{P}\left(\Vert \sum _{i\le n}{X}_i\Vert \ge u\right)\le 2\exp \left(-\frac{u^2/2}{D^2{\Vert {\sum }_{i\le n}{\mathbb{E}}_{i-1}{\Vert X_i-\mu \Vert }^2\Vert }_{\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}{\Vert X_i-\mu \Vert }^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 $\Vert X_i\Vert \le 1/2$. Then, with probability $1-\alpha$, simultaneously for all $t$:

$$\Vert \frac{{\sum }_{i\le t}{\lambda }_i{X}_i}{{\sum }_{i\le t}{\lambda }_i}-\mu \Vert \le D\frac{\frac{1}{2}{\sum }_{i\le t}{\psi }_E({\lambda }_i){\Vert X_i-{\hat{\mu }}_{i-1}\Vert }^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 mean estimation), 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$.

Whitehouse et al. (2024) propose extending Catoni and Giulini’s truncation-based estimator (truncation-based estimators) to Banach spaces. This estimator can handle infinite variance.