multivariate light-tailed concentration

Bounded random vectors

Dimension-free Bernstein bound

Let $X_1,\dots ,X_n\in {\mathbb{R}}^d$ obey $\left|X_t\right|\le c_t$ and $\mathbb{E}[{\left|X_t\right|}^2]\le v_t^2$. Let $V_n={\sum }_{i\le n}{v}_i^2$. Using the martingale-variance inequality martingale concentration:Variance bound, we obtain

$$\mathbb{P}(\left|S_n\right|\ge \sqrt{V_n}+ϵ)\ge \exp \left(\frac{-{ϵ}^2}{4V_n}\right),$$

for $ϵ\le V/{\max }_t{c}_t$. A bound of this form was first given by David Gross here.

Note that a weaker form of this bound can be obtained by appealing to the Azuma-Hoeffding inequality (martingale concentration:Azuma-Hoeffding inequality). The difference is equivalent to the difference between the Hoeffding bound and the Bernstein/Bennett bound in the scalar case (see bounded scalar concentration).