1
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Jan 8, 2023 at 18:49
  • 1
    $\begingroup$ 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$ $\endgroup$ Jan 8, 2023 at 21:04
  • $\begingroup$ 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$. $\endgroup$ Jan 9, 2023 at 9:26
  • $\begingroup$ @lively_radish i've added some clarifications $\endgroup$ Jan 10, 2023 at 18:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .