Relation between Gaussian width and its squared version

Question

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.

Answer 1

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}$.