Relation between Gaussian width and its squared version

665 Views Asked by At

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.

2

There are 2 best solutions below

0
On BEST ANSWER

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

0
On

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