# Relation between Gaussian width and its squared version

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.

• @GabrielRomon: thank you so much, sorry for the late reply! The part I was missing was moving the square out of the supremum. – VHarisop Sep 9 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}$$.