Chaining tail bound for centered sub-Gaussian process?

Question

On page 5 of a recent manuscript by Lugosi-Mendelson, a claim equivalent to the following statement is made:

Suppose $Z$ is a centered, $\mathbf{R}^d$-valued random variable with $\mathbf{E} e^{\lambda \langle Z, z \rangle} \leq e^{\lambda^2 \|z\|_2^2/2}$, for all $\lambda \in \mathbf{R}, z \in \mathbf{R}^d$. Let $T = \{x : \|x\|_\ast \leq 1\}$ denote the dual norm ball for $\|\cdot\|$ on $\mathbf{R}^d$ and $Z_t := \langle Z, t \rangle$ for $t \in T$. Then with probability at least $1 - \delta$, $$\sup_{t \in T} Z_t \lesssim w(\Sigma^{1/2} T) + \log^{1/2} (1/\delta) \sup_{t \in T} \|Z_t\|_{L^2},$$ where $\Sigma := \mathbf{E} ZZ^T$ denotes covariance and $w(S) := \mathbf{E}_{g \sim N(0, I_d)} \sup_{s \in S}\langle g, s \rangle$ is the Guassian mean-width for $S \subset \mathbf{R}^d$.

(Above $\lesssim$ hides a universal constant.) They say it is a consequence of majorizing measures and the generic chaining. A naive application would give $\gamma_2(T, \|\cdot\|_2)$ (which could be upper bounded by $w(T)$) and ${\rm diam}(T)$ (with resepct to $\ell_2^d$.

Could anyone either sketch the argument for majorizing measures/generic chaining or point me to a reference for this result?

Answer 1

Let $G_t$ be a Gaussian process indexed by a subset $T \subset R^d$.The majorizing measure theorem states that $$\mathbb{E} \sup_{t \in T} G_t \asymp \tau(T) $$ where $\tau(T)$ is a functional which is defined solely in terms of the geometry of $T$, and the $\asymp$ symbol means that the quantity on the left can be upper or lower bounded by the quantity on the right up to a universal non-zero constants. See, say, Talagrand's "The Generic Chaining" book or his papers on the topic for a precise definition and a motivated discussion.

It turns out that upper bounding the left side by the right is the easier direction of the claim. This is a theorem of C. Preston from about 1970 (who, unfortunately, rarely gets credited/cited for this result). Preston's result improves on an earlier similar result of Dudley which produces an upper bound similar to the above, but with a slightly less efficient quantity replacing $\tau(T)$. Now one important feature of Preston's result is that he doesn't fully use that $G_t$ is a Gaussian process, he only uses that it is sub-Gaussian, or that it satisfies the inequality in the first line of the mathematical statement in your question.

Now the second (and deeper) part of the relation above, is that the expectation of the sup is in fact lower bounded by the combinatorial functional $\tau(T)$. This is a remarkable result of Talagrand. The lower bound is known only for the more restricted case of Gaussian processes.

Combining the above observations it follows that if $X_t$ is a sub-Gaussian and $G_t$ is a Gaussian process with the same index set then $$\mathbb{E} \sup_{t \in T} X_t \lesssim \tau(T) \lesssim \mathbb{E} \sup_{t \in T} G_t $$

Now the statement in your question isn't about expectations, but about events that hold with a constant probability. However, one should be able to deduce this from the expectation version of this statement using concentration of measure inequalities for random processes (see, for instance, Lemma 11 in my paper https://arxiv.org/pdf/1212.1988.pdf).

Answer 2

To continue on this, I believe the actual assumption that is present in the work above is: $$ \|Z_t - Z_s\|_{\psi_2} \leq \|Z_t - Z_s\|_{L^2} = d_{\Sigma}(t, s). $$ Above, $d_{\Sigma}$ denotes the induced distance by the positive definite covariance matrix $\Sigma = \mathbf{E} ZZ^T$ (i.e., $d_\Sigma(t, s) = \|t - s\|_{\Sigma} = \|\Sigma^{1/2} (t- s)\|_2$).

If this is the assumption, then we conclude construct a scaled process which is $\psi_2$. Let $X = \Sigma^{-1/2} Z$, and take $\tilde T = \Sigma^{1/2} T$. Then $Z_{\Sigma^{-1/2}t} \overset{d}{=} X_{t}$, for $t \in \tilde T$. Additionally, for $t, s \in \tilde T$: $$ \|X_t - X_s\|_{\psi_2} \leq \|t - s\|_2. $$

By generic chaining, for $t_0 \in \tilde T$, with probability at least $1 - \delta$ $$ \sup_{t \in \tilde T}|X_t - X_{t_0}| \lesssim \gamma_2(\tilde T, \|\cdot\|_2) +\sqrt{\log(1/\delta)} \left( {\rm diam}_{\|\cdot\|_2}(\tilde T)\right). $$ Let us unpack this a bit:

• By definition, we have $\gamma_2(\tilde T, \|\cdot\|_2) = \gamma_2(\Sigma^{1/2} T, \|\cdot\|_2)$. On the other hand, by majorizing measures we also have $$ \gamma_2(\Sigma^{1/2}T, \|\cdot\|_2) \asymp \mathbf{E} \sup_{t \in \Sigma^{1/2} T} \langle g, t \rangle = w(\Sigma^{1/2}T). $$
• By the triangle inequality, $$ {\rm diam}_{\|\cdot\|_2} (\tilde T) = \sup_{t, s \in \tilde T} \|t - s\|_2 \lesssim \sup_{t \in \Sigma^{1/2}T} \|t\|_2 = \sup_{t \in T} \|\Sigma^{1/2}t\|_2 = \sup_{\|t\|_\ast \leq 1} \|Z_t\|_{L^2}. $$
• By definition, we also have at least in distribution, $$ \sup_{t \in \tilde T} |X_t - X_{t_0}| = \sup_{t \in T} |X_{\Sigma^{1/2}t} - X_{t_0}| = \sup_{t \in T} |Z_t - Z_{\Sigma^{-1/2} t_0}|. $$
• Take $t_0 = 0 \in \mathbf{R}^d$. Then by the above $$ \sup_{t\in T} Z_t = \sup_{t \in T} (Z_t - Z_{\Sigma^{-1/2}t_0}) \leq \sup_{t \in \tilde T} |X_t - X_{t_0}|. $$

Putting the pieces together, we conclude $$ \sup_t Z_t \lesssim w(\Sigma^{1/2}T) + \sqrt{\log (1/\delta)} \sup_t \|Z_t\|_{L^2}, $$ which is what we wanted.