Random Matrix Lecture 21

[[lecture-data]]

Info

let current = dv.current();
let previous = current.previous_lecture;
 
// get notes with this as the previous
let pages = dv.pages("")
	.where(p => p.previous_lecture)
	.where(p => String(p.previous_lecture)
		.includes(dv.current().file.link));
 
let output = `:LiArrowBigLeftDash: ${previous || "No Previous Lecture"} | `;
 
if (pages.length > 0) {
	output += pages
		.map(p => p.file.link).join(", ");
} else {
	output += 'No Next Lecture'
}
 
output += ' :LiArrowBigRightDash:'
 
dv.el('div', output)

Class Notes

Summary

• Subgaussian concentration inequalities for random matrices
  • McDiarmid Inequality
  • log-Sobolev inequalities
  • Gaussian-Lipschitz concentation
• Applications of Gaussian-Lipschitz

7. Non-Asymptotic RMT

Last time, we saw

Cor $X\in {\mathbb{R}}^{d\times d}$ symmetric with independent entries in $[-k,k]$, then $\text{Var}({\lambda }_1(X))\le 16k^2$ What if we don’t assume

• iid entries
• centered (${\mathbb{E}}_{}\left[X\right]=0$) ?

Example

Any adjacency matrix of an (unweighted) random graph with independent edges (Erdos-Renyi, SBM)

Remark

• Bounded Differences implies $\text{Var}(f(x))\le \frac{1}{4}{\sum }_{i=1}^n({\Delta }_{i}f{)}^2$
• Efron-Stein theorem implies $\text{Var}(f(x))\le {\mathbb{E}}_{}\left[\sum (f(x)-f(x^{(i)}){)}^2\right]$

Question What about, for example, $X\sim GOE(d)$ when $k=\infty$?

Pointcare Inequality

Let $\mu$ be a probability measure on ${\mathbb{R}}^N$. We say that $\mu$ satisfies the Pointcare Inequality, denoted $PI(C)$, if for all differentiable $f$, ${\text{Var}}_{x\sim \mu }(f(x))\le C{\mathbb{E}}_{x\sim \mu }\left[||\nabla f|{|}^2\right]$

Notes

• ${\sum }_{i=1}^N{\mathbb{E}}_{}\left[({\partial }_{i}f(x){)}^2\right]$ is an expression of the function’s sensitivity to each coordinate
• Sometimes, $\nabla f$ is the “other” notion of "$\nabla$"

see pointcare inequality

Theorem

If $\mu$ has pointcare inequality $C$ and $f$ is $L$ Lipschitz, then $\text{Var}(f)\le C{L}^2$

Proof

Exercise

Gaussian Pointcare Inquality Theorem (GIP)

$\mathcal{N}(0,I_N)$ has pointcare inequality where $C=1$ (independent of $N$!)

See Gaussian Pointcare Inequality Theorem

Corollary

$X\sim GOE(d)⟹\text{Var}({\lambda }_1(X))\le 2$

Proof

We can view $g\sim \mathcal{N}\left(0,I_{\frac{d(d+1)}{2}}\right)$ as $(g_{i,j}{)}_{i\le j}$ and construct $X\sim GOE$ where

\sqrt{ 2 }g_{1,1} & \dots & & \\ \vdots & \ddots & g_{i,j} & & \\ & g_{i,j} & \ddots \\ & & & \sqrt{ 2 }g_{\frac{d(d+1)}{2}} \end{bmatrix}$$ Then define $f(g)=\lambda_{1}(X(g))$. This is Lipschitz with $L=\sqrt{ 2 }$ and we have $$\begin{align} \text{Var}_{X \sim GOE(GPI)}(\lambda_{1}(X)) &= \text{Var}_{g \sim {\cal N}(0, I_{\underbrace{ N }_{ d(d+1)/2 }})}(f(g)) \\ \lvert f(g)-f(h) \rvert &= \lvert \lambda_{1}(X(g)) \rvert -\lvert \lambda_{1}(X(h)) \rvert \\ &\leq \lvert \lvert X(g) - X(h) \rvert \rvert _{\text{op}} \\ &\leq \lvert \lvert X(g) - X(h) \rvert \rvert _{F} \\ &\leq \sqrt{ 2 } \lvert \lvert g-h \rvert \rvert \end{align}$$ $$\tag*{$\blacksquare$}$$

Corollary

$X_{ij}=X_{ji}\stackrel{iid}{\sim }\mathcal{N}({\mu }_{ij},{\sigma }_{ij}^2)⟹\text{Var}({\lambda }_1(X))\le 2{\max }_{ij}{\sigma }_{ij}^2$

Lemma ("Tensorization" of PI)

Suppose ${\mu }_1,\dots ,{\mu }_N$ are probability measures over $\mathbb{R}$ each with PI $C$. Then the product measure $\mu =\underset{\text{Law}(X_1,\dots ,X_N)}{\underbrace{{\mu }_1\otimes \cdots \otimes {\mu }_N}}$ Also has PI $C$.

Proof

Using the Efron-Stein theorem, we see

\text{Var}_{X\sim \mu}(f(x)) &\leq \sum_{i=1}^N \mathbb{E}_{\text{all except }i}\left[ \overbrace{\text{Var}_{X_{i}\sim \mu_{i}}(f(x)) }^{PI \text{ of }\mu_{i}}\right] \\ &\leq \sum_{i=1}^N \mathbb{E}_{\text{all except }i}\left[C\mathbb{E}_{X_{i}\sim \mu_{i}}\left[(\partial_{i} f(x))^2\right] \right] \\ &\leq C \mathbb{E}_{}\left[\lvert \lvert \nabla f(x) \rvert \rvert ^2\right] \end{align}$$

see tensorization of PI

Proof of GPI

Proof

By the tensorization lemma, it suffices to do $N=1$. We will use the central limit theorem and Efron-Stein.

Introduce $z_1,z_2,\dots \stackrel{\text{iid}}{\sim }\text{Unif}(\{\pm 1\})$. Then we have

\text{Var}_{g\sim {\cal N}(0, 1)}(f(g)) &\overset{\text{(CLT)}}\approx \text{Var}\left( f\left( \frac{1}{\sqrt{ k }}\sum_{i=1}^k z_{k} \right) \right) \\ &\overset{(ES)}\leq \frac{1}{2} \sum_{i=1}^k \mathbb{E}_{}\left[\left( f\left( \underbrace{ \frac{1}{\sqrt{ k }}\sum_{j=1}^k z_{j} }_{ \frac{1}{\sqrt{ k }}\sum_{j\neq i}z_{j} +\frac{z_{i}}{\sqrt{ k }} }\right) -f\left( \underbrace{ \frac{1}{\sqrt{ k }} \sum_{j\neq i}z_{j} }_{ S_{i} } + \frac{z_{i}}{\sqrt{ k }} \right) \right)^2\right] \\ &= \frac{1}{4} \sum_{i=1}^k \mathbb{E}_{}\left[\left( f\left( S_{i}+\frac{1}{\sqrt{ k }} \right)-f\left( S_{i}-\frac{1}{\sqrt{ k }} \right) \right)^2\right] \\ &\approx \frac{1}{4} \sum_{i=1}^k \mathbb{E}_{}\left[\left( f'(S_{i}) \frac{2}{\sqrt{ k }} \right)^2\right] \\ &= \mathbb{E}_{}\left[(f'(S_{1}))^2\right] \\ &\approx \mathbb{E}_{g \sim {\cal N}(0,1)}\left[(f'(g))^2\right] \end{align}$$

Example

$f(x)={\max }_{i=1\dots N}{x}_i$ where $x_i\stackrel{\text{iid}}{\sim }\mathcal{N}(0,1)$. Then ${\mathbb{E}}_{}\left[f(x)\right]=\sqrt{2\log N}$ and $f$ is $1$ Lipschitz. Thus $\text{Var}(f(x))\le 1$

Subgaussian Concentration

$\text{Var}(f(x))\le {\sigma }^2⟹\mathbb{P}[|f-{\mathbb{E}}_{}\left[f\right]\ge t|]\stackrel{\text{(Chebyshev)}}{\le }\frac{{\sigma }^2}{t^2}$ Our bounded difference inequality gives us $\text{Var}(f(x))\le {\sigma }^2:=\frac{1}{4}{\sum }_i({\Delta }_{i}f{)}^2$

Theorem McDiarmid / Azumai-Hoefding $f-{\mathbb{E}}_{}\left[f\right]$ is ${\sigma }^2$-subgaussian And from homework 1, we have $\mathbb{P}[|f-{\mathbb{E}}_{}\left[f\right]|>t]\le 2\exp \left(-\frac{t^2}{2{\sigma }^2}\right)$

Proof Like Efron-Stein (to get something that looks like $\text{Var}\left(\sum X_i\right)=\sum \text{Var}(X_i)$) using a Doob martingale $({\mathbb{E}}_{\le k}\left[f(x)\right]{)}_{k=1}^N$ to get something from Hoefding.

Fact (important) Theorem

Theorem (important!)

(Generalization of GPI for Subgaussians)

If $x\sim \mathcal{N}(0,I_N)$ and $f$ is $L$ Lipschitz, then $f(x)-{\mathbb{E}}_{}\left[f(x)\right]$ is $L^2$ subgaussian, ie

\mathbb{P}[\,\lvert f(x)-\mathbb{E}_{}\left[f(x)\right] \rvert \geq t] &\leq 2\exp\left( -\frac{t^2}{2L^2} \right) \\ \iff f(x)&= \mathbb{E}_{}\left[f(x)\right] \pm {\cal O}(L)\quad \text{w.h.p.} \end{align}$$

See Gaussian Lipschitz concentration inequality HD Stat Theorem 2.26

"Very Gaussian" proof

Exercise

(homework 4)

Corollaries If $x\sim \mathcal{N}(0,I_N)$ and $X\sim GOE(d)$, then

• $\max \{x_i\}$ is 1-subgaussian
• ${\lambda }_1(X)$ is 2-subgaussian
• $X_{ij}\stackrel{\text{iid}}{\sim }\mathcal{N}({\mu }_{ij},{\sigma }_{ij})⟹{\lambda }_1(X)$ is $2\max \{{\sigma }_{ij}^2\}$ subgaussian
• $Y=\beta v{v}^{⊺}+X⟹{\lambda }_1(Y)$ is 2-subgaussian
• If $x\sim \mathcal{N}(0,I_N)$, then with high probability, $||x||$ is 1-subgaussian (compare to the proof for Johnson-Lindenstrauss)

Log-Sobolev Inequality

For $X>0$,

\text{Ent}[X] &= \mathbb{E}_{}\left[X\log X\right] -\mathbb{E}_{}\left[X\right] \log(\mathbb{E}_{}\left[X\right] ) \\ & \mathbb{E}_{}\left[\phi(X)\right] - \phi(\mathbb{E}_{}\left[X\right] ) \end{align}$$ We can think of this as a "generalized variance" Lemma 1 [[Efron-Stein theorem|Efron-Stein]] for Entropy $$\text{Ent}[f(x)] \leq \sum_{i=1}^N \mathbb{E}_{\text{all except }i}\left[\text{Ent}[f(x)]\right] $$ Lemma (Herbst argument) Suppose for all $\lambda$, $\frac{\text{Ent}\left[ {e^{\lambda X}} \right]}{\mathbb{E}_{}\left[e^{\lambda X}\right]} \leq \frac{\sigma^2}{2}\lambda^2$. Then $X$ is $\sigma^2$ [[subgaussian]]. $\frac{\text{Ent}\left[ {e^{\lambda X}} \right]}{\mathbb{E}_{}\left[e^{\lambda X}\right]}$ is like $\psi_{X}(\lambda)$ but with tensorization! Where $\psi_{x}(\lambda)=\log(\mathbb{E}_{}\left[e^{\lambda x}\right])$ is the moment generating function. Def Modified Log Sobolev Inequality Suppose $\mu$ satisfies **MLSI**($C$). If $$\text{Ent}(e^{f(x)}) \leq C\,\mathbb{E}_{x \sim \mu}\left[\lvert \lvert \nabla f(x) \rvert \rvert^2\right] e^{f(x)}$$ see [[MLSI]] Lemma MLSI tensorizes (like [[pointcare inequality|PI]]) Theorem If $\mu$ has [[MLSI]]$(C)$ and $f$ is $L$ [[Lipschitz continuous|Lipschitz]], and $x \sim \mu$, then $f(x)$ is $2CL^\xi$ [[subgaussian]] Theorem ${\cal N}(0, 1)$ has [[MLSI]]$\left( \frac{1}{2} \right)$ ```datacorejsx const { dateTime } = await cJS() return function View() { const file = dc.useCurrentFile(); return <p class="dv-modified">Created {dateTime.getCreated(file)} ֍ Last Modified {dateTime.getLastMod(file)}</p> } ```