I'm currently reading through Roman Vershynin's High Dimensional Probability and working through one of the exercises (7.6.1). Consider a set $T \subseteq \mathbf{R}^n$ and define its Gaussian width $w(T)$, as

$$ w(T) := \mathbb{E} \sup_{x \in T} \langle g, x\rangle, \quad g \sim \mathcal{N}(0, I_n). $$

A closely related version, $h(T)$, is defined similarly:

$$ h(T) := \sqrt{\mathbb{E}\left[ \sup_{x \in T} \langle g, x \rangle^2 \right]}. $$

Now, Exercise 7.6.1 in the book asks the reader to show that

$$ h(T - T) \leq w(T - T) + C_1 \mathrm{diam}(T), \quad (*) $$ with $T - T := \left\{u - v : u, v \in T \right\}$, and the hint is to use Gaussian concentration. I have been unable to use this hint, and only end up with a trivial upper bound where $C_1 = \sqrt{n}$, as follows:

$$ h(T - T)^2 = \mathbb{E} \sup_{x \in T - T} \langle g, x \rangle^2 = \mathbb{E} \left( \sup_{x \in T - T} \left\langle g, \frac{x}{\| x \|_2} \right\rangle^2 \| x \|_2^2 \right) \\ \leq \sup_{x \in T - T} \| x \|_2^2 \mathbb{E} \| g \|_2^2 = \mathrm{diam}^2(T) \cdot n, $$ followed by taking square roots.

Question: How does one use Gaussian concentration to show the bound $(*)$? I tried showing that $g \mapsto \sqrt{\sup_{x \in T - T} \langle g, x \rangle^2} - \sup_{y \in T - T} \langle g, y \rangle$ is Lipschitz, but couldn't get anything useful since there is a square root involved.

  • 1
    $\begingroup$ @GabrielRomon: thank you so much, sorry for the late reply! The part I was missing was moving the square out of the supremum. $\endgroup$ – VHarisop Sep 9 '19 at 0:50

For fixed $g$ note that $\sup\limits_{x,y\in T} \langle g,x-y \rangle = \sup\limits_{x,y\in T} |\langle g,x-y \rangle|$, hence

$$\left(\sup\limits_{x,y\in T} \langle g,x-y \rangle \right)^2=\left(\sup\limits_{x,y\in T} |\langle g,x-y \rangle|\right)^2=\sup\limits_{x,y\in T} |\langle g,x-y \rangle|^2=\sup\limits_{x,y\in T} \langle g,x-y \rangle^2$$

Let $F:g\mapsto \sup\limits_{x,y\in T} \langle g,x-y \rangle$. The previous equalities show that $h(T-T)^2=\mathbb E(F(g)^2)$, and of course $w(T-T)=\mathbb E(F(g))$.
Let us prove that $F$ is $\mathrm{diam}(T)$-Lipschitz: for $g,g'\in \mathbb R^n$, $$\langle g,x-y \rangle = \langle g-g',x-y \rangle + \langle g',x-y \rangle \leq \|g-g'\|\mathrm{diam}(T) + F(g')$$ hence $F(g) - F(g')\leq \|g-g'\|\mathrm{diam}(T)$ and the claim is obtained by symmetry.

Gaussian concentration provides an upper bound on $\mathbb V(F(g))$. Indeed $$\mathbb V(F(g)) = \int_0^\infty P(| F(g)- \mathbb E(F(g))|\geq \sqrt t)\leq 2\int_0^\infty e^{-t/(2 \mathrm{diam}(T)^2)} = 4\mathrm{diam}(T)^2$$

Thus $h(T-T)=\sqrt{\mathbb E(F(g)^2)}\leq \sqrt{w(T-T)^2 + 4\mathrm{diam}(T)^2}\leq w(T-T) + 2\mathrm{diam}(T)$.

Using the Gaussian Poincaré inequality one can get the stronger inequality
$$h(T-T)\leq w(T-T) + \mathrm{diam}(T)$$

Regarding the other inequalities, $w(T-T)\leq h(T-T)$ follows from Jensen's inequality: $$h(T-T)=\sqrt{\mathbb E\left[\left(\sup\limits_{x,y\in T} |\langle g,x-y \rangle| \right)^2\right]}\geq \mathbb E (\sup\limits_{x,y\in T} |\langle g,x-y \rangle|) = w(T-T)$$ The last inequality $w(T-T)+2\mathrm{diam}(T) \leq Cw(T-T)$ follows from Proposition 7.5.2 of the book: $$w(T-T)+2\mathrm{diam}(T)\leq w(T-T)+ 2\sqrt{2\pi}w(T) = \left(1+\sqrt{2\pi} \right)w(T-T)$$ Using the tighter bound on the variance, the last constant can be improved to $1+\sqrt{\frac \pi 2}$.


h(T-T) is $L_2$ norm of $\sup\langle g,t\rangle$. Study subgaussian norm of $\sup\langle g,t\rangle$ using Gaussian concentration inequality then using $ \|\sup\langle g,t\rangle\|_{L_2}\le \sqrt{2}C\|\sup\langle g,t\rangle\|_{\psi_2}.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.