Pinelis approach to concentration

Let $X_1,X_2,\dots$ be random variables taking values in a $\beta$-smooth Banach space $(\mathcal{X},\Vert \cdot \Vert )$ with conditional mean $\mu$, i.e., $\mathbb{E}[X_t|X_1,\dots ,X_{t-1}]=\mu$, and satisfying $\Vert X_t-\mu \Vert \le B$ almost surely. We want to develop concentration inequalities for $S_t={\sum }_{i\le t}\Vert X_i-\mu \Vert$.

Pinelis’ approach to concentration (explored in his 1994 and 1992 papers) involves studying the process $\cosh (\lambda \Vert S_t\Vert )$. In particular, he shows that the process defined by

$$M_t=G_t\cosh (\lambda \Vert S_t\Vert ),$$

is a nonnegative supermartingale, where

$$G_t=\exp \left\{-\frac{{\beta }^2}{B^2}{\Vert \sum _{i\le t}\Vert X_t-\mu {\Vert }^2\Vert }_{\infty }\sum _{k\ge 2}\frac{(\lambda B{)}^2}{k!}\right\}.$$

Applying Markov’s inequality to $M_n$ for a fixed $n$ and optimizing $\lambda$ gives either the gives the equivalent of Hoeffding’s bound and Bernstein bound 1 for bounded Banach space-valued observations; see concentration in Banach spaces for the statements. Applying Ville’s inequality instead of Markov’s inequality gives time-uniform versions of these inequalities.