chaining

Chaining is a generic method of generating maximal inequalities on the suprema of random processes.

Suppose we have a collection of random variables indexed by some set which we assume is a centered (zero-mean) sub-Gaussian process in the sense that

$$\mathbb{P}(|X_{\theta }-X_{\varphi }|\ge ϵ)\le 2\exp \left(-\frac{{ϵ}^2}{2{\rho }^2(\theta ,\varphi )}\right),$$

for some metric $\rho$. The ultimate goal is to bound $\mathbb{E}{\sup }_{\theta }{X}_{\theta }$ but this is done via bounding

$$\mathbb{P}(\underset{\theta }{\sup }{X}_{\theta }\ge ϵ).$$

If $X_{\theta }$ is mean-zero, then $\mathbb{E}{\sup }_{\theta }{X}_{\theta }=\mathbb{E}{\sup }_{\theta }(X_{\theta }-X_{{\theta }_0})$ for any ${\theta }_0$ so we often focus on the quantity $X_{\theta }-X_{{\theta }_0}$.

Overview

The idea is to decompose $X_{\theta }-X_{{\theta }_0}$ as

$$X_{\theta }-X_{{\theta }_0}=\sum _{n\ge 1}(X_{{\pi }_n(\theta )}-X_{{\pi }_{n-1}(\theta )}),$$

where ${\pi }_0(\theta )={\theta }_0$ and ${\pi }_N(\theta )=\theta$ for all large enough $N$ (so that the sum is really a finite sum). This is the “chain”. Here ${\pi }_n$ is a map from $\Theta \to {\Theta }_n$ where

$$\{{\theta }_0\}={\Theta }_0\subset {\Theta }_1\subset \cdots \subset {\Theta }_N=\Theta .$$

So ${\theta }_n(\theta )\subset {\Theta }_n$ is the approximation of $\theta$ within ${\Theta }_n$. We enforce that ${\Theta }_n$ is finite, so that union bound type arguments will apply. In particular we set $|{\Theta }_n|=2^{2^n}$, which looks ridiculous I know, but we will want exponential growth in log-space. We let ${\pi }_n(\theta )$ be the closest point to $\theta$ in ${\Theta }_n$, so that

$$\rho (\theta ,{\pi }_n(\theta ))=\underset{\varphi \in {\Theta }_n}{\inf }\rho (\theta ,\varphi ).$$

The intuition is the following:

• Bound $\mathbb{P}(|X_{{\pi }_n(\theta )}-X_{{\pi }_{n-1}(\theta )}\ge ϵ)$ using that $X_{\theta }$ is a sub-Gaussian process.
• Union bound over all elements of ${\Theta }_n\times {\Theta }_{n-1}$ (both are finite).
• Union bound over all $n\le N$ (again finite).
• Use the chaining decomposition above to provide a bound on $X_{\theta }-X_{{\theta }_0}$.

Chapter 2.2 in Talagrand’s book below provides the details. We end up with a bound of the form:

$$\mathbb{P}(\underset{\theta }{\sup }|X_{\theta }-X_{{\theta }_0}|\ge tS)\le 2\sum _{n\le N}{2}^{2^{n+1}}\exp (-t^2{2}^{n-1})\lesssim \exp (-t^2/2),$$

where

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

where we’ve used the triangle inequality $\rho ({\pi }_n(\theta ),{\pi }_{n-1}(\theta ))\le \rho ({\pi }_n(\theta ),\theta )+\rho (\theta ,{\pi }_{n-1}(\theta ))$. This gives $\mathbb{E}{\sup }_{\theta }{X}_{\theta }\lesssim A$.

There are two main ways of dealing with $A$. One is generic chaining, and one is Dudley chaining. The latter is looser than the former, but sometimes easier to compute.

References

• Upper and lower bounds for stochastic processes, Talagrand.