080. Linear Regression

Linear Regression

Problem formulation

unknown vector 인 regression vector ${\theta }^{\ast }\in {\mathbb{R}}^d$ 설정.

벡터 $Y=(Y_1,\cdots ,Y_n{)}^{\prime }\in {\mathbb{R}}^n$ 를 관측했으며, linear model $Y=X{\theta }^{\ast }+ϵ$ 를 통해 이와 관계되어 있는 $X\in {\mathbb{R}}^{n\times d}$ 를 가정하자. 이때 $ϵ={\left({ϵ}_1,\cdot \cdot \cdot ,{ϵ}_n\right)}^{\top }\in {\mathbb{R}}^n$ 이며, 각각은 independent zero-mean ${ϵ}_1,\cdots ,{ϵ}_n\in SG({\sigma }^2)$.

이제 $\hat{\theta }$ 를 ${\theta }^{\ast }$ 의 estimator 로 잡는다. 이하의 2가지가 주된 관심사.

1. Prediction

$X{\theta }^{\ast }+\widetilde{ϵ}=\tilde{Y}\stackrel{iid}{\sim }Y$ 라고 설정하자. 우리의 목적은 ${\theta }^{\ast }$ 에 대한 우리의 estimate $\hat{\theta }$ 의 구현값을 사용해서 $\tilde{Y}$ 를 predict. performance 에 대한 natural measure 는 이하와 같다. 이때 unavoidable error 는 말 그대로 unavoidable 이므로, 우리는 후자인 MSE, 즉 $\mathbb{E}\left[\Vert X({\theta }^{\ast }-\hat{\theta }){\Vert }_2^2\right]$, 를 조사하고자 한다.

$$\frac{1}{n}\mathbb{E}\left[\Vert \tilde{Y}-X\hat{\theta }{\Vert }_2^2\right]=\frac{1}{n}\mathbb{E}\left[\Vert \widetilde{ϵ}+X({\theta }^{\ast }-\hat{\theta }){\Vert }_2^2\right]=\underset{\text{unavoidable error}}{\underbrace{\frac{1}{n}\mathbb{E}\left[\Vert \widetilde{ϵ}{\Vert }_2^2\right]}}+\underset{\text{Mean Squared Error}}{\underbrace{\frac{1}{n}\mathbb{E}\left[\Vert X({\theta }^{\ast }-\hat{\theta }){\Vert }_2^2\right]}}$$

2. Parameter Estimation

위와는 다른 케이스로, 몇몇 경우에 우리는 regression vector $\theta \ast \ast$ 를 조사하고 싶어하는 경우가 있으며, 이 경우에 관심사 (조사대상) 는

$$\mathbb{E}\left[\Vert {\theta }^{\ast }-\hat{\theta }{\Vert }_2^2\right]$$

Least Squares Estimator in high dimensions

고전적인 LR 은 LS 문제를 풀어내는 것과 같다. 이하의 형을 구한다는 것과 equivalent 이며, 이는 보통 Ordinary Least Squares (OLS) estimator 로 통칭됨.

${\hat{\theta }}_{\mathrm{LS}}=(X^{\top }X{)}^{-1}{X}^{\top }Y=\arg \underset{\theta \in {\mathbb{R}}^d}{\min }\Vert Y-X\theta {\Vert }_2^2$

Gauss–Markov thm 에 의해 우리는 OLS Estimator 가 Best Linear Unbiased Estimator (BLUE) 임을 알고 있음.

• 왜냐고? 특정 condition 하에서의 Linear Unbiased Estimator 들의 class 내에서 OLS Estimator 가 가장 작은 Var 을 가지고 있으니까.

하지만 이 estimator 는 $X^{\prime }X$ 가 uninvertible 하면 존재할 수 없음. 다른 말로, $n\ge d$ 인 경우에만 존재할 수 있다는 거임.

$d>n$ 라도, ${\min }_{\theta \in {\mathbb{R}}^d}\Vert Y-X\theta {\Vert }_2^2$ 라는 문제에 대한 해를 찾아내는 건 가능함. 다음과 같이 매핑하는 function $\theta \mapsto \Vert Y=X\theta {\Vert }_2^2$ 는 convex 이므로, 1차 optimality condition 인 ${\nabla }_{\theta }\Vert Y-X\theta {\Vert }_2^2=0⟺X^{\top }X\theta =X^{\top }Y$ 를 체크하는 것만으로 충분함.

이의 해는 이하에 제시된 MP-pseudo Inverse $X^{\prime }X$ 의 형으로 서술될 수 있음.

Mean Squared Error of the Least Squares Estimator

:::{.theorem name=“Least Squares Estimator”}

let linear model $Y=X{\theta }^{\ast }+ϵ$, 이때 $ϵ$ 의 elements 각각은 independent zero-mean ${ϵ}_1,\cdots ,{ϵ}_n\in SG({\sigma }^2)$.

이때 ${\hat{\theta }}_{LS}$ 는 이하를 만족하며, 2번째 ineq는 with probability at least $1-\delta$ 로 만족.

\begin{alignat}{2} & &&\frac{1}{n}E \Bigg ( && \Bigg \| X\bigl(\widehat{\theta}_{\mathrm{LS}}-\theta^{*}\bigr) \Bigg \|_{2}^{2} \Bigg) &&\lesssim \sigma^{2}\frac{r}{m} && \; \; \; \; \; \; \; \; \;\;r= rank(X'X) \\ &\forall \delta>0: && {\frac{1}{n}} &&\|X(\widehat{\theta}_{\mathrm{LS}}-\theta^{*})\|_{2}^{2} &&\lesssim\sigma^{2} \left({\frac{r+\log(\frac 1 \delta)}{n}} \right) \end{alignat}

:::

• Remark

$d\le n$ 이며 $rank(B)=rank\left(\frac{X^{\prime }X}{n}\right)=d$ 일 때, 이하가 성립한다. 이때 ${\lambda }_{\min }(B)$ 는 $B$ 의 ev 중 최소인 값이며, 따라서 이에 $\Vert {\hat{\theta }}_{LS}-{\theta }^{\ast }{\Vert }_2^2$ 를 탐색하기 위해 thm 8.2. 를 바로 적용하는 것이 가능하다.

그러나 고차원 케이스에서는 $d>n$ 일 때 ${\lambda }_{\min }(B)=0$ 이므로 이 방법론을 쓸 수 없다. 따라서 MSE 의 형으로 ${\lambda }_{\min }(B)$ 의 bound 를 설정할 필요가 있기 때문에 가정이 추가적으로 필요하다.

\begin{alignat}{2} & && \lambda_{\mathrm{min}}(B) &&\Bigg \|\widehat{\theta}_{\mathrm{LS}}-\theta^{*}\Bigg \|_{2}^{2} &&\leq\left(\widehat{\theta}_{\mathrm{LS}}-\theta^{*}\right)^{\top}B&&(\widehat{\theta}_{\mathrm{LS}}-\theta^{*}) \\ & && \lambda_{\mathrm{min}}(B) &&\Bigg \|\widehat{\theta}_{\mathrm{LS}}-\theta^{*}\Bigg \|_{2}^{2} &&\leq\left(\widehat{\theta}_{\mathrm{LS}}-\theta^{*}\right)^{\top}\frac{X'X}{n}&&(\widehat{\theta}_{\mathrm{LS}}-\theta^{*}) \\ &\iff && && \Bigg \|{\widehat\theta}_{\mathrm{LS}}-\theta^{*} \Bigg \|_{2}^{2} &&\leq{\frac{1}{\lambda_{\mathrm{min}}(B)}}\cdot\frac{1}{n} &&\Bigg \|X({\widehat\theta}_{\mathrm{LS}}-\theta^{*}) \Bigg \|_{2}^{2} \end{alignat}

• Proof

8.2 의 증명은 basic inequality 와 sup-out 테크닉에 의존.

1. Basic ineq.

첫줄의 ineq. 는 의 정의에 의해 성립. 이때 $ϵ$ 과 ${\hat{\theta }}_{LS}$ 는 dependent 하기 때문에 $\frac{{ϵ}^{\top }X({\hat{\theta }}_{\mathrm{LS}}-{\theta }^{\ast })}{||X({\hat{\theta }}_{\mathrm{LS}}-{\theta }^{\ast })|{|}_2}$ 를 control 하기가 어렵다는 것을 note. dependence structure 가 complicated 하다면 더더욱 그럴 것. 이 dependence 를 지워 없애기 위해 sup-out tachnique 를 사용. 이의 maximal ineq. 를 적용하는 것이 해당 문제 해결의 열쇠가 된다.

\begin{array} & & &\|Y-X{\widehat{\theta}}_{\mathrm{LS}}\|_{2}^{2} &\leq &\|Y-X\theta^{*}\|_{2}^{2} &= \|\epsilon\|_{2}^{2} \\ &= & \| \epsilon + X(\theta^\ast - \hat \theta_{LS})\| & \\ &= &\|\epsilon\|_{2}^{2}+2\epsilon^{\mathsf{T}}X(\theta^{*}-{\widehat{\theta}}_{\mathsf{L S}})+\|X(\theta^{*}-{\widehat{\theta}}_{\mathsf{L S}})\|_{2}^{2} && \\ \iff & &\|X(\theta^{*}-\hat{\theta}_{\mathrm{LS}})\|_{2}^{2}\; &\leq &\;2\epsilon^{\top}X(\hat{\theta}_{\mathrm{LS}}-\theta^{*}) & &= &2\|X(\hat{\theta}_{\mathrm{LS}}-\theta^{*})\|_{2}\times\frac{\epsilon^{\top}X(\hat{\theta}_{\mathrm{LS}}-\theta^{*})}{\|X(\hat{\theta}_{\mathrm{LS}}-\theta^{*})\|_{2}} \end{array}

2. Sup-Out

$X$의 column span 의 orthonormal basis 를 $\Psi =[{\psi }_1,\cdots ,{\psi }_r]\in {\mathbb{R}}^{n\times r}$ 라고 하자. (SVD 를 생각하자.) 특히, $\exists \nu \in {\mathbb{R}}^r:X({\hat{\theta }}_{LS}-{\theta }^{\ast })=\Psi \nu$. 이때 이 $\nu$ 에 대해

\begin{alignat}{2} & &&\frac{\epsilon^{\top}X(\widehat{\theta}_{\mathrm{LS}}-\theta^{*})}{||X(\widehat{\theta}_{\mathrm{LS}}-\theta^{*})||_{2}} =\frac{\epsilon^{\top}\Psi\nu}{||\Psi \nu||_{2}} &&=\frac{\epsilon^{\top}\Psi\nu}{||\nu||_{2}} \\ & && &&=\frac{\tilde \epsilon^{\top}\Psi}{||\nu||_{2}} &&\le&&\sup\limits_{u\in\mathbb{R}^{r}:||u||_{2}=1}\tilde{\epsilon}^{\top}u \\ & \iff && &&||X(\theta^{*}-\widehat{\theta}_{\mathrm{LS}})||_{2}^{2} &&\leq4 \cdot &&\sup\limits_{u\in\mathrm{R}^{r}:\|u\|_{2}=1}(\tilde{\epsilon}^{\mathsf{T}}u)^{2} \end{alignat}

since $\forall u\in {\mathbb{S}}^{r-1}:u^{\text{T}}{\Psi }^{\text{T}}\Psi u=u^{\text{T}}u=1$,^[${\mathbb{S}}^{r-1}=\{x\in {\mathbb{R}}^r:\Vert x{\Vert }_2=1\}$] $\forall s\in \mathbb{R}:\mathbb{E}[e^{s{\widetilde{ϵ}}^{\top }}u]=\mathbb{E}[e^{s{ϵ}^{\top }\Psi u}]\le e^{\frac{s^2{\sigma }^2}{2}}$.

이는 곧 $\widetilde{ϵ}\in SG({\sigma }^2)$ 이라는 소리. 이때 $X\sim SG({\sigma }^2)⟹Var(X)\le {\sigma }^2$ (Lecture 2). 따라서 CS ineq. 에 의해 $\mathbb{E}\left[\underset{u\in {\mathbb{R}}^r:\Vert u{\Vert }_2=1}{\sup }({\widetilde{ϵ}}^{\mathsf{T}}u{)}^2\right]\le \sum _{i=1}^r\mathbb{E}\left[{\widetilde{ϵ}}_i^2\right]\le r{\sigma }^2$. 이것이 thm 8.2. 의 첫번째 claim 을 증명.

bound in Probability 를 보이기 위해, 우리는 standard discretization argument 를 사용. $N_{\frac{1}{2}}$ 를 ${\mathbb{S}}^{r-1}$ 의 $\frac{1}{2}$-covering 이라고 하자. 그러면 Lecture 4 에서의 결과물을 사용하는 것으로 $\underset{u\in {\mathbb{R}}^r:\Vert u{\Vert }_2=1}{\sup }{\widetilde{ϵ}}^{\top }u\le 2{\max }_{u\in N_{\frac{1}{2}}}{\widetilde{ϵ}}^{\top }u$ 가 얻어진다.

따라서 이하가 성립하며 이를 만족시키는 임의의 $\delta$ 를 잡았을때 이에서 파생되는 임의의 $t$ 를 얻는다.

$$\begin{array}{rlrl}\mathbb{P}(\Vert X({\theta }^{\ast }-{\hat{\theta }}_{LS}){\Vert }_2^2\ge t)& \le \mathbb{P}(\underset{u\in N_{\frac{1}{2}}}{\max }({\widetilde{ϵ}}^{T}u{)}^2\ge \frac{t}{16})& & \\ & \le \left|N_{\frac{1}{2}}\right|e^{-\frac{t}{32{\sigma }^2}}& & \\ & \le 5^r{e}^{-\frac{t}{32{\sigma }^2}}& & \\ \exists \delta :& \le \delta & & ⟺\exists t:t\ge 32{\sigma }^2\left\{r\log 5+\log \left(\frac{1}{\delta }\right)\right\}\end{array}$$

따라서 with probability at least $1-\delta$, $||X({\theta }^{\ast }-{\hat{\theta }}_{\mathrm{LS}})|{|}_2^2\lesssim {\sigma }^2\{r+\log \left(\frac{1}{\delta }\right)\}$.

Sparse linear regression

이상을 통해 우리는 $\frac{d}{n}\to 0$ 일 때 ${\hat{\theta }}_{LS}$ 가 consistent 함을 확인. 따라서 $\frac{d}{n}\to 0$ 가 우리가 바랄 수 있는 최적의 condition. 특히 $\frac{d}{n}$ 이 0에서 bounded away 된 채로 남는다면 consistent estimator 를 획득하는 건 불가능함. (minimax point of view 에서는.) 이러한 이유로 $d>n$ 상황에서 작업을 할 때는 unknown regression vector ${\theta }^{\ast }$ 에 추가적인 structure 을 얹는 게 필수가 됨. 이제 ${\theta }^{\ast }$ 의 대다수가 0이라는 조건인 sparse condition 에 대해서 논해보자.

Lasso

linear model (8.1)에서 $\theta$ 의 support set $S({\theta }^{\ast })=\{j\in \{1,\dots ,d\}:{\theta }_j^{\ast }\ne 0\}$ 이 cardinality $s=|S({\theta }^{\ast })|\stackrel{substantially}{<}d$, 즉 s-sparse 인 상황 가정. regularized estimator 로서, lasso estimator ${\hat{\theta }}_{\mathrm{lasso}}=\arg \underset{\theta \in {\mathbb{R}}^d}{\min }\left\{\frac{1}{2n}\Vert Y-X\theta {\Vert }_2^2+{\lambda }_n\Vert \theta {\Vert }_1\right\}$ 는 이러한 sparse structural assumption 에 대한 설명력을 가진다.

lasso esimator 는 $\text{for many }j\in \{1,\cdots ,d\}:({\hat{\theta }}_{\mathrm{lasso}}{)}_j$ 라는 sparcity property 를 가지며 이건 ${\lambda }_n$ 을 무엇으로 골랐는지에 의존한다. 위의 등식 (8.3)은 lasso problem 이라고 불리며, 이는 convex optimization problem 이고, computationally tractable.

• Lasso Estimator 는 이하로 표현/요약될 수도 있다.

$$\mathrm{supp}({\hat{\theta }}_{\mathrm{lasso}})=\{j:({\hat{\theta }}_{\mathrm{lasso}}{)}_j\ne 0\},|\mathrm{supp}({\hat{\theta }}_{\mathrm{lasso}})|\ll d.$$ $$\Vert {\hat{\theta }}_{\mathrm{lasso}}{\Vert }_0\ll d,\text{and it is (weakly) increasing in }{\lambda }_n$$

---

• lemma name=“Basic inequality

lasso estimator 에 대한 basic ineq.

$$\frac{1}{2n}\Vert X({\hat{\theta }}_{\mathrm{lasso}}-{\theta }^{\ast }){\Vert }_2^2\le \frac{{ϵ}^{\top }X({\hat{\theta }}_{\mathrm{lasso}}-{\theta }^{\ast })}{n}+{\lambda }_n(\Vert {\theta }^{\ast }{\Vert }_1-\Vert {\hat{\theta }}_{\mathrm{lasso}}{\Vert }_1)$$

---

• Proof.

Lasso 의 정의에 의해,

$$\frac{1}{2n}\Vert Y-X{\hat{\theta }}_{\mathrm{lasso}}{\Vert }_2^2+{\lambda }_n\Vert {\hat{\theta }}_{\mathrm{lasso}}{\Vert }_1\le \frac{1}{2n}\Vert Y-X{\theta }^{\ast }{\Vert }_2^2+{\lambda }_n\Vert {\theta }^{\ast }{\Vert }_1=\frac{1}{2n}||ϵ|{|}_2^2+{\lambda }_n||{\theta }^{\ast }|{|}_1$$

그리고 MSE 를 확장하는 것으로

$$\frac{1}{2n}\Vert Y-X{\hat{\theta }}_{\mathrm{lasso}}{\Vert }_2^2=\frac{1}{2n}\Vert ϵ{\Vert }_2^2+\frac{1}{2n}\Vert X({\hat{\theta }}_{\mathrm{lasso}}-{\theta }^{\ast }){\Vert }_2^2+\frac{{ϵ}^{\top }X({\theta }^{\ast }-{\hat{\theta }}_{\mathrm{laaso}})}{n}$$

둘을 복합.

Slow convergence rate

위에서의 basic inequality (lemma 8.3) 이 주어졌을 때, 우리는 lasso estimator ${\hat{\theta }}_{lasso}$ 의 consistency 를 보장하는 sufficient condition 생성 가능. 이는 deterministic bound 를 구하는 것부터 시작함.

---

• theorem name=“Slow Convergence Rate”

$X_j$ 를 $X$ 의 j-th column 이라고 하고, ${\lambda }_n\ge {\left|\left|\frac{X^{\top }ϵ}{n}\right|\right|}_{\infty }={\max }_{i\le j\le d}\left|\frac{X_j^{\text{T}}ϵ}{n}\right|$ 라고 가정하자. 이 때 lasso estimator 는 이하를 만족.

$$\frac{1}{n}\Vert X({\hat{\theta }}_{\mathrm{lasso}}-{\theta }^{\ast }){\Vert }_2^2\le 4{\lambda }_n\Vert {\theta }^{\ast }{\Vert }_1$$

---

• Proof:

$$\begin{array}{rlrl}\frac{1}{2n}||X({\hat{\theta }}_{\mathrm{lasso}}-{\theta }^{\ast })|{|}_2^2& \le \frac{{ϵ}^{\top }X({\hat{\theta }}_{\mathrm{lasso}}-{\theta }^{\ast })}{n}& & +{\lambda }_n(||{\theta }^{\ast }|{|}_1-||{\hat{\theta }}_{\mathrm{lasso}}|{|}_1)\\ & \stackrel{(i)}{\le }\frac{1}{n}\Vert {ϵ}^{\mathsf{T}}X{\Vert }_{\infty }\Vert {\hat{\theta }}_{\mathrm{lasso}}-{\theta }^{\ast }{\Vert }_1& & +{\lambda }_n(\Vert {\theta }^{\ast }{\Vert }_1-\Vert {\hat{\theta }}_{\mathrm{lasso}}{\Vert }_1)\\ & \stackrel{(ii)}{\le }\frac{1}{n}||{ϵ}^{\top }X|{|}_{\infty }(||{\hat{\theta }}_{\mathrm{lasso}}|{|}_1+||{\theta }^{\ast }|{|}_1)& & +{\lambda }_n(||{\theta }^{\ast }|{|}_1-||{\hat{\theta }}_{\mathrm{lasso}}|{|}_1)\\ & =\Vert {\hat{\theta }}_{\mathrm{lasso}}{\Vert }_1\left(\frac{1}{n}\Vert {ϵ}^{\mathsf{T}}X{\Vert }_{\infty }-{\lambda }_n\right)& & +\Vert {\theta }^{\ast }{\Vert }_1\left(\frac{1}{n}\Vert {ϵ}^{\mathsf{T}}X{\Vert }_{\infty }+{\lambda }_n\right)\\ & \stackrel{(iii)}{\le }2{\lambda }_n||{\theta }^{\ast }{\Vert }_1& & \end{array}$$

1. 휠더 부등식
2. triangle ineq.
3. (8.4) 의 ${\lambda }_n$ 에 대해 걸었던 condition.

th, 8.4. 의 error bound 는 (8.4) 에서 ${\lambda }_n$ 에 대해 걸었던 condition 에 의존. 이제 좀 더 자세히 살펴보자.

• $lambd{a}_n$ 의 good choice 는 무엇인가?

랜덤벡터 $ϵ\in SG({\sigma }^2)$ 이었음을 상기. 이제 $\exists C>0:\underset{1\le j\le d}{\max }\Vert X_i{\Vert }_2\le C\sqrt{n}$ 라고 가정 assume 하자. 이때 $\forall n,d:\underset{1\le j\le d}{\max }\left\{\frac{1}{n}{\sum }_{i=1}^n{X}_{ij}^2\right\}\le C$ 가 성립한다. 이를 통해 standard argument 를 만들수 있다:

$$\begin{array}{rlrl}\mathbb{P}\left(\frac{1}{n}||{ϵ}^{\text{T}}X|{|}_{\infty }\ge t\right)& =\mathbb{P}\left(\underset{1\le j\le d}{\max }|X_j^{\text{T}}ϵ|\ge tn\right)& & \\ & \le \sum _{j=1}^d\mathbb{P}(|X_j^{\top }ϵ|\ge tn)& & \\ & =\sum _{j=1}^d\mathbb{P}\left(\frac{|X_j^{\top }ϵ|}{||X_j|{|}_2}\ge \frac{tn}{||X_j|{|}_2}\right)& & \\ & \le 2d\exp \left(-\frac{n^2{t}^2}{2{\sigma }^2\underset{1\le j\le d}{\max }||X_j|{|}^2}\right)& & \\ & \le 2d\exp \left(-\frac{n{t}^2}{2C^2{\sigma }^2}\right)& & =\delta \end{array}$$

마지막 ineq. 는 시작 전 더해둔 assumption $\underset{1\le j\le d}{\max }\Vert X_j{\Vert }_2\le C\sqrt{n}.$ 에 의해서 성립. 이제 $t={\lambda }_n^{\ast }=\sqrt{\frac{2{\sigma }^2{C}^2}{n}\left\{\log (\frac{1}{\delta })+\log (\frac{2}{d})\right\}}$ 를 하나 고르는 것으로, 우리는 with probability $1-\delta$ 에 의해 $\frac{1}{n}\Vert {ϵ}^{\mathsf{T}}X{\Vert }_{\infty }\le {\lambda }_n^{\ast }$ 가 성립한다는 사실을 파악할 수 있다.

따라서 $\delta =\frac{1}{n}$ 으로 잡는 것으로, thm 8.4 를 적용하는 것으로 ${\lambda }_n^{\ast }$ 가 주어진 lasso estimator 는 이하를 보장한다.

$$\frac{1}{n}\Vert X({\hat{\theta }}_{\mathrm{lasso}}-{\theta }^{\ast }){\Vert }_2^2\lesssim \Vert {\theta }^{\ast }{\Vert }_1\cdot \sigma \sqrt{\frac{\log (d)+\log (n)}{n}}$$

여기에 추가로 $\underset{1\le j\le d}{\max }\left|{\theta }_j^{\ast }\right|$ 가 uniformly bounded 되어 있다고 suppose 한다면? 그 경우 ${\theta }^{\ast }$ 의 $s$-sparcity 하에서, $s\sqrt{\frac{\log (d)}{n}}\to 0$ 이 1번이라도 발생한 순간 MSE 는 0으로 간다.

• Parameter Estimation

위에서 언급되었 듯이, $\text{d}\le n$ 이며 ${\lambda }_{\min }\left(\frac{X^{\text{T}}X}{n}\right)\ge C_{\min }>0,$ 일 경우, 앞의 결과는 이하를 보장한다. 안타깝게도 이 전략은 $d>n$ 인 경우에는 작동하지 않는다. $X^{\prime }X$ 가 rank-deficient 가 되어 버리므로.

$$||{\hat{\theta }}_{\mathrm{lasso}}-{\theta }^{\ast }|{|}_2^2\lesssim \frac{||{\theta }^{\ast }|{|}_1}{C_{\min }}\cdot \sigma \sqrt{\frac{\log (d)+\log (n)}{n}}$$

Fast Convergence Rate

디자인 매트릭스 $X$ 에 추가적인 assumption 을 붙이는 것으로 좀 더 빠른 convergence rate 를 얻는 것이 가능. 여기선 Restricted Ev (RE) condition 을 사용할 것. $\{1,\cdots ,d\}$ 의 subset $S$ 에 대해 $Z_S=(Z_{S,1},\cdots ,Z_{S,d})\in {\mathbb{R}}^d)$ 이며 $\forall j\in S:Z_{S,j}=Z_j$, o.w. $Z_{S,j}=0$ 으로 정의.

$S^c$ 를 $S$ 의 complement 로 잡자. 즉슨 $Z_{S^c}$ 도 $Z_S$ 와 유사하게 정의. 이때 $\forall \alpha \ge 1:C(\alpha ,S)=\{\Delta \in {\mathbb{R}}^d:||{\Delta }_{S^c}|{|}_1\le \alpha \Vert {\Delta }_S{\Vert }_1\}$. 이 notation 들을 써서 이하 정의.

:::{.definition name=“RE condition”}

매트릭스 $X$ 는 이하를 만족할 경우, 패러미터 $(\alpha ,\kappa )$ 와 함께 $S$ 에 대해 RE condition 을 만족한다.

$$forall\Delta \in C(\alpha ,S):\frac{1}{n}\Vert X\Delta {\Vert }_2^2\ge \kappa \Vert \Delta {\Vert }_2^2$$

:::

• Remark.

RE condition 에 대한 직관을 좀 얻어보자. cost difference ${\mathcal{L}}_n({\hat{\theta }}_{\mathrm{lasso}})-{\mathcal{L}}_n({\theta }^{\ast })=\frac{1}{2n}||Y-X{\hat{\theta }}_{\mathrm{lasso}}|{|}_2^2-\frac{1}{2n}||Y-X{\theta }^{\ast }|{|}_2^2$ 가 작다면, error vector ${\hat{\theta }}_{lasso}-{\theta }^{\ast }$ 도 또한 작다는 것을 장담할 수 있을까? 일반적으로 이는 그렇다고 할 수 없다. 특히 cost function ${\mathcal{L}}_n(\theta )$ 가 flat 할 경우에는 더더욱. 이 flat 상황을 피하기 위해 cost function ${\mathcal{L}}_n(\theta )$ 로 하여금 이의 optimum ${\hat{\theta }}_{lasso}$ 주위에서 높은 curvature 를 갖도록 하는 것이 요구됨. curvature 는 Hessian MAtrix ${\nabla }^2{\mathcal{L}}_n(\theta )=\frac{1}{n}{X}^{\top }X$ 의 구조에 의해 결정됨. 만약 우리가 이 Hessian Matrix 의 ev 가 0 에서 bounded away 되었다고 장담할 수 있다면, 즉, $\forall \Delta \in {\mathbb{R}}^d\setminus \{0\}:\frac{1}{n}||X\Delta |{|}_2^2\ge \kappa ||\Delta |{|}_2^2>0$ 라면, 우리는 모든 지점에서 curvature 를 갖는다는 것을 확신할 수 있을 것.

하지만 고차원 상황 $d>n$ 에서는 Hessian Matrix 는 0 ev 를 가져야만 하고, condition (8.7) (바로 위 상황) 은 성립할 수 없다. 역으로 우리는 $C(\alpha ,S)$ 로 정의된 특정한 지점에서 cost function 이 curved 한지를 고려한다. 이 직관을 써서 RE condition 하에서 lasso estimator 에 대한 deterministic bound 를 생산할 수 있다. 이것이 아래의 thm.

:::{.theorem name=“Fast Convergence Rate”}

linear model (8.1) 을 살피고, $S=\{i:{\theta }_i^{\ast }\ne 0\}$ 에 대해 패러미터 $(3,\kappa )$ 를 통해 RE condition 을 만족하는 $X$ 를 assume. 이때, $S$ 의 cardinality 가 $s$ 를 쓰자. 여기서 만약 ${\lambda }_n\ge 2{\Vert \frac{X^{\text{T}}ϵ}{n}\Vert }_{\infty }$ 가 성립한다면 이하가 성립.

$$\frac{1}{n}||X({\hat{\theta }}_{\mathrm{lasso}}-{\theta }^{\ast })|{|}_2^2\le 9\frac{s{\lambda }_n^2}{\kappa },||{\hat{\theta }}_{\mathrm{lasso}}-{\theta }^{\ast }|{|}_2\le 3\frac{\sqrt{s}{\lambda }_n}{n}$$

:::

• Proof:

편의를 위해 $\hat{\Delta }={\hat{\theta }}_{lasso}-{\theta }^{\ast }$. 주어진 condition 하에서 $\hat{\Delta }\in C(3,S)$ 임을 먼저 보이자. basic ineq. (lemma 8.3) 을 사용하면 $\frac{1}{2n}||X\hat{\Delta }|{|}_2^2\le \frac{{ϵ}^{\top }X\hat{\Delta }}{n}+{\lambda }_n(||{\theta }^{\ast }|{|}_1-||{\hat{\theta }}_{\mathrm{lasso}}|{|}_1)$ 임을 보일 수 있다. ${\theta }^{\ast }$ 가 s-sparse 이며 $\hat{\Delta }={\hat{\theta }}_{lasso}-{\theta }^{\ast }$ 이므로 이하가 성립.

$$\begin{array}{rlrl}\Vert {\theta }^{\ast }{\Vert }_1-\Vert {\hat{\theta }}_{\mathrm{lasso}}{\Vert }_1& =\Vert {\theta }_S^{\ast }{\Vert }_1-\Vert {\hat{\theta }}_{\mathrm{lasso}}{\Vert }_1& & \\ & =\Vert {\theta }_S^{\ast }{\Vert }_1-\Vert \hat{\Delta }+{\theta }^{\ast }{\Vert }_1& & \\ & =\Vert {\theta }_S^{\ast }{\Vert }_1& & -\Vert {\hat{\Delta }}_S+{\theta }_S^{\ast }{\Vert }_1-\Vert {\hat{\Delta }}_{S^c}{\Vert }_1\\ & \le \Vert {\hat{\Delta }}_S{\Vert }_1+\Vert {\hat{\Delta }}_S+{\theta }_S^{\ast }{\Vert }_1& & -\Vert {\hat{\Delta }}_S+{\theta }_S^{\ast }{\Vert }_1-\Vert {\hat{\Delta }}_{S^c}{\Vert }_1\\ & =\Vert {\hat{\Delta }}_S{\Vert }_1-\Vert {\hat{\Delta }}_{S^c}{\Vert }_1& & \end{array}\text{\hspace{1em}(triangle ineq.)}$$ $$\begin{array}{rl}0\le \frac{1}{n}\Vert X\hat{\Delta }{\Vert }_2^2& \stackrel{(i)}{\le }\frac{2}{n}\Vert {ϵ}^{\top }X{\Vert }_{\infty }\Vert \hat{\Delta }{\Vert }_1+2{\lambda }_n(\Vert {\hat{\Delta }}_S{\Vert }_1-\Vert {\hat{\Delta }}_{S^c}{\Vert }_1)\\ & \stackrel{(\mathrm{ii})}{\le }{\lambda }_n\Vert \hat{\Delta }{\Vert }_1+2{\lambda }_n(\Vert {\hat{\Delta }}_S{\Vert }_1-\Vert {\hat{\Delta }}_{S^c}{\Vert }_1)\\ & ={\lambda }_n(\Vert {\hat{\Delta }}_S{\Vert }_1+\Vert {\hat{\Delta }}_{S^c}{\Vert }_1)+2{\lambda }_n(\Vert {\hat{\Delta }}_S{\Vert }_1-\Vert {\hat{\Delta }}_{S^c}{\Vert }_1)\\ & ={\lambda }_n(3\Vert {\hat{\Delta }}_S{\Vert }_1-\Vert {\hat{\Delta }}_{S^c}{\Vert }_1).\end{array}\text{\hspace{1em}(Holder)(condition (8.8) on λn)}$$

이를 통해 $\hat{\Delta }\in C(3,S)$ 라고 결론지을 수 있으며, 우리는 $X$ 가 패러미터 $(3,\kappa )$ 와 함께 RE condition 을 만족한다고 assume 했으므로, 이는 곧 $\frac{1}{n}\Vert X\hat{\Delta }{\Vert }_2^2\ge \kappa \Vert \hat{\Delta }{\Vert }_2^2$ 라는 것을 보여준다.

앞의 과정을 다시 사용해서 이제

$$\begin{array}{rl}\frac{1}{n}\Vert X\hat{\Delta }{\Vert }_2^2& \le {\lambda }_n(3\Vert {\hat{\Delta }}_S{\Vert }_1-\Vert {\hat{\Delta }}_{S^c}{\Vert }_1)\le 3{\lambda }_n\Vert {\hat{\Delta }}_S{\Vert }_1\\ & \stackrel{(i)}{\le }3{\lambda }_n\sqrt{s}||{\hat{\Delta }}_S|{|}_2\\ & \le 3{\lambda }_n\sqrt{s}||\hat{\Delta }|{|}_2\\ & \stackrel{(ii)}{\le }\frac{3{\lambda }_n\sqrt{s}}{\sqrt{n\kappa }}\Vert X\hat{\Delta }{\Vert }_2\\ ⟺\frac{1}{n}\Vert X({\hat{\theta }}_{\mathrm{lasso}}-{\theta }^{\ast }){\Vert }_2^2& \le 9\frac{s{\lambda }_n^2}{\kappa }\end{array}\text{\hspace{1em}(1)(ineq. (8.9))}$$

1. $\forall x\in {\mathbb{R}}^d,\Vert x{\Vert }_1\le \sqrt{d}\Vert x{\Vert }_2$

따라서 위의 마지막 ineq. 와 ineq. (8.9) 를 다시 한번 적용하면 증명 완료.

• Remark.

${\lambda }_n\asymp \sigma \sqrt{\frac{\log (d)+\log (n)}{n}}$ 상황이라고 가정하자. 이 경우 design 매트릭스에 (8.5) 와 유사한 condition 을 두고 같은 argument 를 적용하면 ${\lambda }_n\ge 2{\Vert \frac{X^{\top }ϵ}{n}\Vert }_{\infty }$ with probability at least $1-\frac{1}{n^c}$ for some constant $c>0$ 임을 보일 수 있다. 이는 또한 ($d\gg n$ 일 때) $\frac{1}{n}\Vert X({\hat{\theta }}_{\mathrm{lasso}}-{\theta }^{\ast }){\Vert }_2^2\lesssim \frac{s\log (d)}{n}$ 라는 것으로도 이어지며, 따라서 RE condition 하에서 once $\frac{s\log (d)}{n}\to 0$ 라면 lasso estimator 는 consistent 하다.

이와 별개로 $\underset{n\to \infty }{\lim }{\lambda }_n=0$ 를 가정하는 것으로, thm 8.6 의 결과가 8.4의 결과를 former의 upper bound 가 ${\lambda }_n$ 이 아니라 ${\lambda }_n^2$ 에 의존한다는 것으로 진화시킨다는 것을 발견할 수 있다.