multivariate light-tailed concentration

Bounded distributions

Bernstein bounds

Bounds in ${\mathbb{R}}^d$: Let $X_1,\dots ,X_n\in {\mathbb{R}}^d$ obey $\Vert X_t\Vert \le c_t$ and $\mathbb{E}[{\Vert X_t\Vert }^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}(\Vert S_n\Vert \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).

Bounds in more general spaces: There are dimension-free Bernstein bounds that hold in Banach spaces: see concentration in Banach spaces. There are also dimension-free empirical Bernstein bounds, see empirical Bernstein bounds.

Sub-Gaussian distributions

See sub-Gaussian distributions distributions for definitions in multivariate settings.

Sub-Gaussian coordinates: If $X_1,\dots ,X_n$ are independent and sub-Gaussian with $\mathbb{E}{X}_i^2=1$, then the norm $\Vert X\Vert =\Vert (X_1,\dots ,X_n)\Vert$ is concentrated around $\sqrt{n}$. In particular, for some $c>0$,

$$\mathbb{P}(|\Vert X{\Vert }_2-\sqrt{n}|\ge u)\le 2\exp (-c{u}^2/K^4),$$

where $K={\max }_i\Vert X_i{\Vert }_{{\psi }_2}$ is the maximum sub-Gaussian Orlicz norm.

Sub-Gaussian random vectors. Hsu et al (2012) give state-of-the-art sub-Gaussian concentration. They show that for a fixed matrix $A$, if $X$ is $I$-sub-Gaussian with mean 0, then with probability $1-\delta$,

$$\Vert AX{\Vert }^2\le \text{Tr}(\Sigma )+2\Vert \Sigma \Vert u+2\sqrt{\text{Tr}({\Sigma }^2)u},$$

where $u=\log (1/\delta )$. This can be translated into a sub-Gaussian as follows: If $X$ is $I$-subGaussian, then $AX$ is $A^{t}A$-subGaussian. Therefore, the above gives a bound for $\Sigma$-subGaussian $X$ where $\Sigma$ can be decomposed as $\Sigma =A^{t}A$. For $n$ such vectors, we get the bound

$$\Vert {\overline{X}}_n{\Vert }^2\le \frac{\text{Tr}(\Sigma )+2\Vert \Sigma \Vert u+2\sqrt{\text{Tr}({\Sigma }^2)u}}{n}.$$

There is also a time-uniform bound that allows for martingale dependence which is nearly as tight, but not quite. See this paper for details. For $X_1,X_2,\dots$ where $X_i$ is conditionally $\Sigma$-subGaussian (and still mean 0) we have

$$\Vert \frac{{\sum }_{i\le t}{\lambda }_i{X}_i}{{\sum }_{i\le t}{\lambda }_i}\Vert \le \frac{{\sum }_{i\le t}{\psi }_N({\lambda }_i)(\Vert \Sigma \Vert +{\beta }^{-1}\text{Tr}(\Sigma ))+\beta /2+\log (1/\alpha )}{{\sum }_{i\le t}{\lambda }_i},$$

where $({\lambda }_i)$ is a predictable sequence. When instantiated with the optimal ${\lambda }_i$ and $\beta$ we get the rate

$$\tilde{O}\left(\sqrt{\text{Tr}(\Sigma )+\Vert \Sigma \Vert \log (1/\alpha )}\sqrt{\frac{\log t}{t}}\right).$$

This can be made into a bound with optimal iterated logarithm dependence (laws of the iterated logarithm) using stitching (stitching for LIL rates). At a fixed time $n$, the optimal choice of $\beta$ and $\lambda$ give the bound

$$\Vert {\overline{X}}_n{\Vert }^2\le \frac{\text{Tr}(\Sigma )+2\Vert \Sigma \Vert u+2\sqrt{2\Vert \Sigma \Vert \text{Tr}(\Sigma )u}}{n},$$

which we can see is worse than Hsu et al’s bound above, since $\Vert \Sigma \Vert \text{Tr}(\Sigma )\ge \text{Tr}({\Sigma }^2)$ (but not by the leading factor, so the asymptotics are the same). This bound is proved with the variational approach to concentration.

Sub-$\psi$ distributions

Using confidence sequences for convex functionals, Manole and Ramdas, give a bound for iid data $(X_t)$ with mean $\mu$ that obeys

$$\mathbb{E}\exp (\lambda ⟨\theta ,X-\mu ⟩)\le \exp (\psi (\lambda )),\text{ for all }\theta \in {\mathbb{S}}^{d-1}.$$

Note this is a multivariate sub-psi process with $V_t=I$. They show that with probability $1-\delta$, for all $t$,

$$\Vert {\overline{X}}_t-\mu \Vert \le 2({\psi }^{\ast }{)}^{-1}\left(\frac{\log \ell ({\log }_{2}t)+\log (1/\delta )+\log N_2}{\lceil t/2\rceil }\right),$$

where $N_{\gamma }$ is the covering number of the dual norm, and ${\psi }^{\ast }$ is the convex conjugate of $\psi$. For isotropic sub-exponential distributions, this gives a bound that scales as

$$O\left(\sqrt{\frac{\log \log (t)+\log (1/\alpha )+d}{t}}\right).$$

Other conditions

Log-concave distributions. This comes from this paper and is proved with the variational approach to concentration. Let $(X_t{)}_{t\ge 1}$ be conditionally log-concave, meaning that for all $t\ge 1$,

$${\Vert ⟨\theta ,X_t-\mathbb{E}[X_t|{\mathcal{F}}_{t-1}]⟩\Vert }_{{\psi }_1}\le C\sqrt{⟨\theta ,\Sigma \theta ⟩},$$

for all $\theta \in {\mathbb{R}}^d$, some $C>0$ and PSD $\Sigma$. Let $f_{\alpha }(u)=\sqrt{\text{Tr}(\Sigma )u}+u\sqrt{\Vert \Sigma \Vert }$. Then with probability $1-\alpha$, for all $t\ge 1$,

$$\Vert \frac{{\sum }_{i\le t}{\lambda }_i{X}_i}{{\sum }_{i\le t}{\lambda }_i}-\mu \Vert \le \frac{2C{f}_{\alpha }(1){\sum }_{i\le t}{\lambda }_i^2+4C{f}_{\alpha }(\log (2/\alpha ))}{{\sum }_{i\le t}{\lambda }_i},$$

where $({\lambda }_t)$ is any predictable sequence taking values in $(0,1)$. For a fixed-time $n$, taking $\lambda =\sqrt{\frac{2f_{\alpha }(\log (2/\alpha ))}{n{f}_{\alpha }(1)}}$ gives a width bounded by $8C\sqrt{\log (1/\alpha )\text{Tr}(\Sigma )}/\sqrt{n}$. In the sequential setting, taking ${\lambda }_t=\sqrt{\frac{2f_{\alpha }(\log (2/\alpha ))}{t\log (t+1)f_{\alpha }(1)}}$ gives a width of

$$\tilde{O}\left(\sqrt{\frac{\text{Tr}(\Sigma )\log (1/\alpha )\log (t)}{t}}\right).$$

Stitching can be used to get LIL rates (stitching for LIL rates).