# An upper bound on Gaussian mean width

The following is an excerpt from this blog post on Talagrand's Generic Chaining:

"Suppose that we have a subset $$T \subseteq {\mathbb R}^n$$, we pick a random Gaussian vector $$g$$ from $$N({\bf 0}, I)$$, and we are interested in the random variable $$\sup_{t \in T} \langle g,t \rangle$$.

A first observation is that each $$\langle g,t \rangle$$ is Gaussian with mean zero and variance $$|| t||^2$$. If $$T$$ is finite, we can use a union bound to estimate the tail of $$\sup_{t\in T} \langle t,g \rangle$$ as $$\displaystyle \Pr \left[ \sup_{t\in T}\ \langle g, t \rangle > \ell \right] \leq |T| \cdot e^{-\ell^2 / 2 \sup_{t\in T} \lVert t\rVert^2}$$

and we can compute the upper bound

$$\mathbb{E}_{g \sim N({\bf 0},I)} \left( \sup_{t \in T} \langle g,t \rangle \right) \leq O \left( \sqrt{\log |T|}\cdot \sup_{t \in T}\lVert t\rVert \right) ."$$

I don't see how we get the last bound on expectation. We can get a lower bound on the cdf of $$\sup_{t \in T} \langle g,t \rangle$$ from the tail bound. But this doesn't seem to help in getting an upper bound on the expectation.

A useful result from Talagrand's book is that for any r.v. $$X \ge 0$$ satisfying for any $$t\ge 0$$ $$P(X \ge t) \le A \exp (-t^2/B^2)$$ for constants $$A\ge 2$$ and $$B>0$$. Then $$E X \le CB \sqrt{\log A}$$, where $$C$$ is a universal constant.

The proof is straightforward:

\begin{align*} E X &= \int_0^{\infty} P(X \ge t) dt\\ &= \int_0^{t_0} P(X \ge t) dt + \int_{t_0}^{\infty} P(X \ge t) dt\\ &\le t_0 + \int_{t_0}^{\infty} P(X \ge t) dt\\ &\le t_0 + \int_{t_0}^{\infty} A\exp \left (-\frac{t^2}{B^2}\right)dt\\ &\le t_0 + \frac{1}{t_0}\int_{t_0}^{\infty} t A\exp \left (-\frac{t^2}{B^2}\right)dt\\ &= t_0 + \frac{AB^2}{2t_0} \exp \left ( -\frac{t_0^2}{B^2} \right), \end{align*} and minimizing with respect to $$t_0$$ yields the choice $$t_0 = B\sqrt{\log A}$$.

See also this post for a similar result going from high probability to expectation.

What if $$X$$ is not non-negative? If $$X$$ cannot be assumed non-negative, as in the case for example where $$X := \sup_{t \in T} \langle g, t\rangle$$, then we can use instead the fact:

$$E X = \int_0^{\infty} P(X \ge t) dt - \int_{-\infty}^0 P(X < t)dt \le \int_0^{\infty} P(X \ge t) dt$$ and reason as above.

How do we get $$t_0 = CB\sqrt{\log A}$$?

Since as you say the minimizer in closed form is hard/impossible to compute, the idea here is to reason about the correct order of the minimizer. In our case, we have

$$t_0 + \frac{AB^2}{2t_0} \exp \left ( -\frac{t_0^2}{B^2} \right) \le t_0 + \frac{AB^2}{2} \exp \left ( -\frac{t_0^2}{CB^2} \right)$$ is always true for a constant $$C$$ large enough. Now we have two terms that move in opposite directions, as $$t_0$$ grows bigger, the first term grows but the second term is smaller, and vice versa. The idea then is to find a $$t_0$$ such that both terms are of constant order. Note that the choice of $$t_0$$ mentioned before does exactly this. This is not an exact minimizer but it is a minimizer up to constants which is good enough for our purpose. Note that universal constants $$C$$ can differ from line to line.

• Thank you for the neat proof! Why can we assume that $\sup_{t \in T} \langle g,t \rangle$ is non-negative? In fact it is easy to come up with $n$ and $T$ where it is negative sometimes. Jan 8, 2023 at 18:49
• you're right - i missed that. I think you can still salvage it without making assumptions on $T$ by using the fact that for general r.v. $X$ then $E X = \int_0^\infty P(X \ge t)dt - \int_{-\infty}^0 P(X<t)dt \le \int_0^\infty P(X \ge t)dt$ Jan 8, 2023 at 21:04
• Let $f(t) = t + \frac{AB^2}{2t}e^{-\frac{t^2}{B^2}}$. Now, $f'(t) = 1 - Ae^{-\frac{t^2}{B^2}} - \frac{AB^2}{4t^2}e^{-\frac{t^2}{B^2}}$. $f'(B\sqrt{\log A}) = -\frac{1}{4\log A}$, which is not equal to $0$. Why then do we choose $t = B\sqrt{\log A}$ to get the upper bound? Note that I couldn't solve for $f'(t)=0$. Jan 9, 2023 at 9:26