techniques for multivariate concentration

Suppose we have a stochastic process $(S_t)$ evolving in some space. What techniques are available for bounding $\Vert S_t\Vert$? If $S_t\in \mathbb{R}$, then we usually argue about $S_t$ and $-S_t$ and take a union bound to get a bound on $|S_t|$ (see eg bounded scalar concentration and light-tailed, unbounded scalar concentration). However, in higher-dimensional spaces (in ${\mathbb{R}}^d$, $d\ge 2$, say) a union bound doesn’t suffice: there are infinitely many directions one has to worry about.

There are several techniques for dealing with this problem.

Working directly with the norm

There are roughly two approaches that I’m aware of: The Doob decomposition approach and the Pinelis approach.

The idea for the first is to form a Doob martingale from the increments of the process and then apply well-known martingale bounds. Set

$$Z_t=\mathbb{E}[\Vert S_n\Vert |{\mathcal{F}}_t]-\Vert S_n\Vert .$$

So $(Z_t)$ is a martingale with $Z_0=0$. Let $D_t=Z_t-Z_{t-1}$, be the increments of the process. Various martingale concentration bounds are stated as conditions on the increments of the process. For instance:

• If $S_t$ is bounded for each $t$, then we can use the Azuma-Hoeffding inequality (martingale concentration:Azuma-Hoeffding inequality)
• If a bound on the variance of $D_t$ is known, then we can use the equivalent of a Bernstein inequality (martingale concentration:Variance bound, often called a Freedman inequality. This approach is taken by eg David Gross here to get vector Bernstein inequalities.

The Pinelis approach to concentration is another method which works directly with the norm. We might also label this the Yurinskii approach, since he does something similar in an earlier 1976 paper.

For multivariate light-tailed concentration of sub-Gaussian distributions, the technique of Hsu et al is another example of working directly with the norm. Their technique seems specific to sub-Gaussian distributions however; it doesn’t seem to constitute a general approach.

Covering arguments

See concentration via covering for an overview. The idea is decompose $\Vert S_t\Vert$ into ${\sup }_{\theta }⟨\theta ,S_t⟩$ where the supremum is over the unit ball, cover the the unit ball with an finite net, bound $⟨\theta ,S_t⟩$ for each $\theta$ in this finite set, and then take a union bound. You suffer the covering number (covering and packing) of the underlying space in the bound.

This means covering arguments lead to dimension-dependent bounds because covering numbers will depend geometrically on the underlying space. Obviously, you also have to be able to calculate the covering number.

Chaining

This also works by decomposing $\Vert S_t\Vert ={\sup }_{\theta }⟨\theta ,S_t⟩$. See chaining for a more detailed overview. Chaining provides high probability guarantees of the form

$$\mathbb{P}\left(\underset{\theta \in {\mathbb{S}}^{d-1}}{\sup }⟨\theta ,S_n⟩\ge tS\right)\lesssim \exp (-t^2),$$

where

$$S=\underset{\theta \in {\mathbb{S}}^{d-1}}{\sup }\sum _{n\le N}{2}^{n/2}\rho (\theta ,{\Theta }_n),$$

and ${\Theta }_0\subset {\Theta }_1\subset \cdots \subset {\Theta }_N$ are a selected sequence of sets which slowly “approximate” $\Theta ={\mathbb{S}}^{d-1}$. The difference between generic chaining and Dudley chaining is how they choose to handle $S$. The latter typically bounds it using covering numbers and metric entropy.

The variational approach

See variational approach to concentration. The idea is to use PAC-Bayes inequalities which are high probability guarantees over all probabilities measures into a simultaneous guarantee over all directions.

In some scenarios they allow you to escape-dimension dependence (eg for sub-Gaussian random vectors) which neither chaining nor covering arguments allow you to do.

Reading

• Variational approach to concentration
• Confidence estimation via sequential likelihood mixing by Kirschner et al. Gives several strategies including the variational approach to concentration and also relates it to variational inference.