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$. Thentodo