030. Concentration inequalities

Concentration inequalities

SG 는 꽤 빡빡한 strict 개념. mgf 여부에 기반한 sub-Exponential 은 좀 느슨함.

Sub-exponential random variables

:::{.definition name=“sub-Exponential rv”}

$E(X)=\mu$, 패러미터 $\exists (\nu ,\alpha )\ge 0$ 에 대해 이하가 성립하면 랜덤변수 $X$는 sub-exponential.

$$\forall |\lambda |<\frac{1}{\alpha }:\mathbb{E}[e^{\lambda (X-\mu )}]\le e^{\frac{{\nu }^2{\lambda }^2}{2}}$$

SG 또한 $1/0=+\infty$ 로 해석할 경우 $\nu =\sigma$, $\alpha =0$ 인 sub-exponential. :::

Bernstein’s condition

$X$의 polynomial moment를 조작하는 것으로 $X$의 sub-exponential 성질을 증명할 수 있다.

:::{.definition name=“Bernstein’s Condition”}

let $E(X)=\mu$, $Var(X)={\sigma }^2=E(X^2)-{\mu }^2$ 인 랜덤변수 $X$. 이하의 경우와 패러미터 $b$ 에 대해 Bernstein’s Condition 이 성립한다.

$$\begin{array}{rlrl}& \left|E\right[(X-\mu {)}^k]|\le \frac{1}{2}k!{\sigma }^2{b}^{k-2},& & k=2,3,4,\cdots \end{array}$$

이때, 모든 bounded 랜덤변수 (즉 $|X-\mu |\le b$) 에 대해 Bernstein’s Condition 이 성립한다는 것을 파악해라. :::

$X$가 Bernstein’s condition 을 만족할 경우, X는 패러미터 $(\sqrt{2}\sigma ,2b)$ 인 sub-exponential.

:::{.theorem name=“Bernstein-type inequality”}

Bernstein’s Condition 을 만족하는 모든 랜덤변수에 대해 이하가 성립한다.

$$\begin{array}{rlrlrl}& \forall |\lambda |<\frac{1}{b}:& & E\left[e^{\lambda (X-\mu )}\right]& & \le \exp \left(\frac{\frac{{\lambda }^2{\sigma }^2}{2}}{1-b|\lambda |}\right)\\ & \forall t\ge 0:& & P(|X-\mu |\ge t)& & \le 2\exp \left(-\frac{t^2}{2({\sigma }^2+bt)}\right)\end{array}$$

:::

McDiarmid’s inequality

:::{.theorem name=“McDiarmid’s inequality”}

이하의 조건을 만족한다고 하자.

1. 랜덤변수 $X_1,\cdots ,X_n$ 이 independent
2. 함수 $f:{\mathbb{R}}^n\mapsto \mathbb{R}$: $|f(x_1,\cdots ,x_n)-f(x_1,\cdots ,x_{k-1},x_k^{\prime },x_{k+1},\cdots ,x_n)|\le L_k$ (bounded condition)

위 둘이 성립하면 이하가 성립한다.

$$\forall t\ge 0:P\left(|f(X_1,\cdots ,X_n)-E[f(X_1,\cdots ,X_n)\left]\right|\ge t\right)\le 2\exp \left(-\frac{2t^2}{{\sum }_{k=1}^n{L}_k^2}\right)$$

:::

Levy’s inequality

충분히 smooth 한 Gaussian 랜덤변수에 대해, 유사한 concentration inequality 가 존재한다. 이때는 다른 가정이 필요. $X_1,\cdots ,X_n\stackrel{iid}{\sim }N(0,1)$ 에 대해

$$\begin{array}{rlrlrlrl}& \forall x_1,\cdot \cdot \cdot ,x_n,y_1,\cdot \cdot \cdot ,y_n\in \mathbb{R}& & :& & |f(x_1,\dots ,x_n)-f(y_1,\dots ,y_n)|& & \le L\sqrt{\sum _{i=1}^n(x_i-y_i{)}^2}\\ & & & & & & & \\ ⟹& \forall t\ge 0& & :& & \mathbb{P}\left(|f(X_1,\cdot \cdot \cdot ,X_n)-\mathbb{E}[f(X_1,\cdot \cdot \cdot ,X_n)\left]\right|\ge t\right)& & \le 2\exp \left(-\frac{t^2}{2L^2}\right)\end{array}$$

Quadratic form

$Q$ 가 symmetric Matrix 일 때 이하를 정의할 수 있다.

$$\begin{array}{rl}\Vert Q{\Vert }_{\mathrm{op}}& =\underset{\Vert u{\Vert }_2=1}{\sup }\Vert Qu{\Vert }_2\\ \Vert Q{\Vert }_{\mathrm{F}}& =\sqrt{\sum _{i=1}^n\sum _{j=1}^n{Q}_{ij}^2}\end{array}\text{\hspace{1em}(l2-operator norm)(Frobenius norm)}$$

이하는 관련한 thm.

:::{.theorem name=“Hanson–Wright inequality”}

independent, zero-mean, $X\in SG({\sigma }^2)$ 인 랜덤벡터 $X=(X_1,\cdots ,X_n{)}^{\prime }\in {\mathbb{R}}^n$ 를 정의하자. 그러면 Hanson–Wright inequality 에 의해 이하와 같이 quadratic form $X^{\prime }QX$ 의 tail bound 가 정의된다.

$$\forall t\ge 0:\mathbb{P}\left(|X^{\top }QX-\mathbb{E}[X^{\top }QX\left]\right|\ge t\right)\le 2\exp \left(-\min \left\{\frac{c_1{t}^2}{\Vert Q{\Vert }_{\mathrm{F}}},\frac{c_{2}t}{\Vert Q{\Vert }_{\mathrm{op}}}\right\}\right)$$

이때 $c_1,c_2$는 SG 패러미터 $\sigma$ 에 의존하는 some constant. 증명 개어려움. decoupling 테크닉을 다수 쓰는데 궁금하면 Vershynin 책 찾아보던가.

:::

The Johnson–Lindenstrauss Lemma

Example 3.5 에서 확인한 ${\chi }^2$ 의 tail bound 의 응용으로서 유명한 것 중 하나는 “random projection”. $d$ 가 충분히 큰 데이터셋 $X_1,\cdots ,X_n\in {\mathbb{R}}^d$ 을 가지고 있다고 치자. 이러한 데이터셋을 보관하는 것은 과한 비용을 요구하므로, 이를 해결하기 위해 우리는 이때 우리는 $m\ll d$ 인 map $F:{\mathbb{R}}^d\mapsto {\mathbb{R}}^m$ 을 만든 것이 목적인 “sketching”, 혹은 “random projection” 을 사용한다. 이를 적용한 이후에 우리는 앞서 말한 대용량 데이터셋을 저장하는 대신 $\{F(X_1),\cdots ,F(X_n)\}$ 를 보관하게 된다. 여기서 관건은 오리지널 데이터셋의 본질을 해치지 않는 map $F$ 를 만들어내는 것이다. 특히, 우리는 모든 pair $(X_i,X_j)$ 에 대해 이하가 성립하는 것을 목표로 하며, i.e., map 은 모든 pair-wise distance 를 $(1\pm ϵ)$ factor 에 bound 되게 보존한다.

$$(1-ϵ)\Vert X_i-X_j{\Vert }_2^2\le \Vert F(X_i)-F(X_j){\Vert }_2^2\le (1+ϵ)\Vert X_i-X_j{\Vert }_2^2$$

이때 Johnson-Lindenstrauss lemma 은 실로 놀라운 결과를 보여준다. $m\ge \frac{16\log \left(\frac{n}{\delta }\right)}{{ϵ}^2}$ 라는 조건이 주어져 있다면, simple randomized construction 만으로 그러한 map 을 with probability $\max (c,1-\delta )$ 로 생산할 수 있다는 것이다.

이 결과는 원본 데이터셋의 dim $d$ 와는 완전히 독립이며

points 의 숫자 $n$ 에만 logarithmical 하게 의존한다는 것에 notice. 이 map 은 핵심적으로 모든 pairwise 거리를 보존하면서도 보관 비용을 획기적으로 줄일 수 있다.

map 그 자체의 방법론은 매우 간단하다. matrix $\mathbf{Z}\in {\mathbb{R}}^{m\times d}$, $Z_{jk}\stackrel{iid}{\sim }N(0,1)$ 이 되도록 설계하고, map 이 $F(X_i)=\frac{\mathbf{Z}{X}_i}{\sqrt{m}}$ 되도록 정의한다.

이제 pair 중에 $(X_j,X_k)$ 하나를 고르고 이하를 생각하자.

$$\frac{\Vert F\left(X_j\right)-F\left(X_k\right){\Vert }_2^2}{\Vert X_j-X_k{\Vert }_2^2}={\Vert \frac{\mathbf{Z}(X_j-X_k)}{\sqrt{m}\Vert X_j-X_k{\Vert }_2}\Vert }_2^2=\frac{1}{m}\sum _{i=1}^m\underset{T_i}{\underbrace{{⟨{\mathbf{Z}}_i,\frac{X_j-X_k}{\Vert X_j-X_k{\Vert }_2}⟩}^2}}$$

이때 ${\mathbf{Z}}_i$ 는 $\mathbf{Z}$ 의 i-th row. 이제, for some fixed numbers $a_j$ 에 대해, $\sum _{j=1}^d{a}_j{Z}_{ij}\sim N\left(0,\sum _{j=1}^d{a}_j\right)$. 따라서 이에 의해 $T_i\sim {\chi }^2$ 이며 각각은 independent. 이제 ${\chi }^2$ 의 tail bound 를 적용하는 것으로 우리는 이하를 얻는다.

$$\mathbb{P}\left(\left|\frac{\Vert F(X_j)-F(X_k){\Vert }_2^2}{\Vert X_j-X_k{\Vert }_2^2}-1\right|\ge ϵ\right)\le 2\exp \left(\frac{-m{ϵ}^2}{8}\right)$$

따라서 fixed pair $(X_i,X_j)$ 에 대해, 우리의 map 이 distance 를 보존 (preserve) 하는데에 실패할 확률은 exponentially small, i.e., 최대로 해봐야 $2\exp \left(\frac{-m{ϵ}^2}{8}\right)$. 이제 우리의 map 이 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ 중 무엇 하나라도 보전에 실패할 확률은 단순히 union bound 적용해보면 해결됨. 이 계산을 통하면 $P(\text{Failure})\le 2\left(\genfrac{}{}{0ex}{}{n}{2}\right)\exp \left(\frac{-m{ϵ}^2}{8}\right)$.

따라서 $m\ge \frac{16\log \left(\frac{n}{\delta }\right)}{{ϵ}^2}$ 일때 위에서 이야기했던 확률이 최대로 해봐야 $\delta$ 임을 증명하는 건 쉽다. 여기서 note 해야 할 것은 $m$ 을 그러한 작은 값으로 이끄는 exponential concentration 이라는 개념이다. (i.e., 이는 그냥 sample size 에 맞춰서 logarithmically 하게 grow 하기만 하면 된다)