8.8 Linear Regression

이것때문이라고 설마?







8.8.1 Problem formulation

unknown vector 인 regression vector \(\theta^\ast \in \mathbb R^d\) 설정.

벡터 \(Y = (Y_1 , \cdots, Y_n)' \in \mathbb R^n\) 를 관측했으며, linear model \(Y=X\theta^{*}+\epsilon\) 를 통해 이와 관계되어 있는 \(X \in \mathbb R^{n \times d}\) 를 가정하자. 이때 \(\epsilon\;=\;\left(\epsilon_{1},\cdot\cdot\cdot,\epsilon_{n}\right)^{\top}~\in~\mathbb{R}^{n}\;\) 이며, 각각은 independent zero-mean \(\epsilon_1 , \cdots, \epsilon_n \in SG(\sigma^2)\).

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

  1. Prediction

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

\[ \frac{1}{n}\mathbb{E}\left [\Bigg \|{\tilde{Y}}-X{\widehat{\theta}}\Bigg \|_{2}^{2}\right ] = \frac{1}{n}\mathbb{E}\left [\Bigg \|{\tilde{\epsilon}}+X(\theta^{*}-{\widehat{\theta}})\Bigg \|_{2}^{2}\right ] = \underbrace{\frac{1}{n}\mathbb{E}\left [\Bigg \|\tilde \epsilon\Bigg \|_{2}^{2}\right ]}_{\text{unavoidable error}} + \underbrace{\frac{1}{n}\mathbb{E}\left [\Bigg \|X(\theta^{*}-{\widehat{\theta}})\Bigg \|_{2}^{2}\right ]}_{\text{Mean Squared Error}} \]

  1. Parameter Estimation

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

\[ \mathbb{E}\left [\Bigg \|\theta^{*}-{\widehat{\theta}}\Bigg \|_{2}^{2}\right ] \]







8.8.2 Least Squares Estimator in high dimensions

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

\({\widehat{\theta}}_{\mathrm{LS}}=(X^{\top}X)^{-1}X^{\top}Y=\arg \min\limits_{\theta \in \mathbb R^d}\|Y-X\theta\|_{2}^{2}\)

Gauss–Markov thm 에 의해 우리는 OLS Estimator 가 Best Linear Unbiased Estimator (BLUE) 임을 알고 있음. 왜냐고 특정 condition 하에서의 Linear Unbiased Estimator 들의 class 내에서 OLS Estimator 가 가장 작은 Var 을 가지고 있으니까. 하지만 이 estimator 는 \(X'X\) 가 uninvertible 하면 존재할 수 없음. 다른 말로, \(n \ge d\) 인 경우에만 존재할 수 있다는 거임. \(d>n\) 라도, \(\operatorname*{min}_{\theta\in\mathbb{R}^{d}}\|Y-X\theta\|_{2}^{2}\) 라는 문제에 대한 해를 찾아내는 건 가능함. 다음과 같이 매핑하는 function \(\theta\mapsto\|Y=X\theta\|_{2}^{2}\) 는 convex 이므로, 1차 optimality condition 인 \(\nabla_{\theta}\|Y-X\theta\|_{2}^{2}=0\quad\Longleftrightarrow\quad X^{\top}X\theta=X^{\top}Y\) 를 체크하는 것만으로 충분함. 이의 해는 이하에 제시된 MP-pseudo Inverse \(X'X\) 의 형으로 서술될 수 있음.




8.8.2.1 Mean Squared Error of the Least Squares Estimator

Theorem 8.13 (Least Squares Estimator) let linear model \(Y=X\theta^{*}+\epsilon\), 이때 \(\epsilon\) 의 elements 각각은 independent zero-mean \(\epsilon_1 , \cdots, \epsilon_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'X}{n}\right) =d\) 일 때, 이하가 성립한다. 이때 \(\lambda_{\mathrm{min}}(B)\) 는 \(B\) 의 ev 중 최소인 값이며, 따라서 이에 \(\|\hat \theta_{LS} - \theta^\ast \|^2_2\) 를 탐색하기 위해 thm 8.2. 를 바로 적용하는 것이 가능하다.

그러나 고차원 케이스에서는 \(d>n\) 일 때 \(\lambda_{\mathrm{min}}(B) = 0\) 이므로 이 방법론을 쓸 수 없다. 따라서 MSE 의 형으로 \(\lambda_{\mathrm{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. 는 의 정의에 의해 성립. 이때 \(\epsilon\) 과 \(\hat \theta_{LS}\) 는 dependent 하기 때문에 \(\frac{\epsilon^{\top}X(\widehat{\theta}_{\mathrm{LS}}-\theta^{*})}{||X(\widehat{\theta}_{\mathrm{LS}}-\theta^{*})||_{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}\]

$$

  1. 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^{\textsf{T}}\Psi^{\textsf{T}}\Psi u=u^{\textsf{T}}u=1\),11 \(\forall s \in \mathbb R: \mathbb{E}[e^{s{\tilde{\epsilon}}^{\top}}u]=\mathbb{E}[e^{s\epsilon^{\top}\Psi u}]\leq e^{{\frac{s^{2}\sigma^2}{2}}}\).

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

bound in Probability 를 보이기 위해, 우리는 standard discretization argument 를 사용. \(N_{\frac12}\) 를 \(\mathbb S^{r-1}\) 의 \(\frac12\)-covering 이라고 하자. 그러면 Lecture 4 에서의 결과물을 사용하는 것으로 \(\sup\limits_{u\in\mathbb{R}^{r}:\|u\|_{2}=1} \widetilde{\epsilon}^{\top}u\le2\operatorname*{max}_{u\in{N}_{\frac12}}\widetilde{\epsilon}^{\top}u\) 가 얻어진다.

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

$$ \[\begin{alignat}{2} \mathbb{P}(\|X(\theta^{*}-{\widehat{\theta}}_{LS})\|_{2}^{2}\geq t)&\leq\mathbb{P}{\Big(}\max\limits_{u\in{ N}_{\frac12}}({\tilde{\epsilon}}^{T}u)^{2}\geq \frac t {16}{\Big)} \\ &\leq \Bigg|{ N}_{\frac 12} \Bigg|e^{-{\frac{t}{32 \sigma^2}}} \\ &\leq5^{r}e^{-{\frac{t}{32 \sigma^2}}} \\ \exists \delta: &\le \delta &&\iff \exists t: t \ge 32 \sigma^2 \left \{ r \log 5 + \log \left( \frac {1} {\delta} \right) \right \} \end{alignat}\] $$

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







8.8.3 Sparse linear regression

이상을 통해 우리는 \(\frac d n \righarrow 0\) 일 때 \(\hat \theta_{LS}\) 가 consistent 함을 확인. 따라서 \(\frac d n \righarrow 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 에 대해서 논해보자.




8.8.3.1 Lasso

linear model (8.1)에서 \(\theta\) 의 support set \(S(\theta^{*})=\{j\in\{1,\ldots, d\}:\theta_{j}^{*}\not=0\}\) 이 cardinality \(s=|S(\theta^\ast)| \overset{substantially}{<} d\), 즉 s-sparse 인 상황 가정. regularized estimator 로서, lasso estimator \(\widehat{\theta}_{\mathrm{lasso}}=\arg\min\limits_{\theta\in\mathbb{R}^{d}}\left\{\frac{1}{2n}\|Y-X\theta\|_{2}^{2}+\lambda_{n}\|\theta\|_{1}\right\}\) 는 이러한 sparse structural assumption 에 대한 설명력을 가진다. lasso esimator 는 for many \(j \in \{1, \cdots, d\}:\hat_{lasso, \; j} = 0\) 라는 sparcity property 를 가지며 이건 \(\lambda_n\) 을 무엇으로 골랐는지에 의존한다. 위의 등식 (8.3)은 lasso problem 이라고 불리며, 이는 convex optimization problem 이고, computationally tractable.

Lemma 8.1 (Basic inequality) lasso estimator 에 대한 basic ineq.

\[ {\frac{1}{2n}}\|X(\widehat{\theta}_{\mathrm{lasso}}-\theta^{*})\|_{2}^{2}\ \leq\ {\frac{\epsilon^{\top}X(\widehat{\theta}_{\mathrm{lasso}}-\theta^{*})}{n}}+\lambda_{n}(\|\theta^{*}\|_{1}-\|\widehat{\theta}_{\mathrm{lasso}}\|_{1}) \]

  • Proof.

Lasso 의 정의에 의해,

\[ \frac{1}{2n}\Vert Y-X\widehat{\theta}_{\mathrm{lasso}}\Vert_{2}^{2}+\lambda_{n}\Vert\widehat{\theta}_{\mathrm{lasso}}\Vert_{1}\ \leq\ \frac{1}{2n}\Vert Y-X\theta^{*}\Vert_{2}^{2}+\lambda_{n}\Vert\theta^{*}\Vert_{1} = \frac{1}{2n} ||\epsilon||_2^2 + \lambda_n ||\theta^\ast ||_1 \]

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

\[ {\frac{1}{2n}}\|Y-X{\widehat{\theta}}_{\mathrm{lasso}}\|_{2}^{2}\ =\ {\frac{1}{2n}}\|\epsilon\|_{2}^{2}+{\frac{1}{2n}}\|X({\widehat{\theta}}_{\mathrm{lasso}}-\theta^{*})\|_{2}^{2}+{\frac{\epsilon^{\top}X(\theta^{*}-{\widehat{\theta}}_{\mathrm{laaso}})}{n}} \]

둘을 복합.




8.8.3.2 Slow convergence rate

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

Theorem 8.14 (Slow Convergence Rate) \(X_j\) 를 \(X\) 의 j-th column 이라고 하고, \(\lambda_{n}\,\geq\,\left|\left|\frac{X^{\top}\epsilon}{n}\right|\right|_{\infty}\ = \max_{i \le j \le d}\left|\frac{X_{j}^{\textsf{T}}\epsilon}{n}\right|\) 라고 가정하자. 이 때 lasso estimator 는 이하를 만족.

\[ \frac{1}{n} \Bigg\| X(\widehat{\theta}_{\mathrm{lasso}}-\theta^{*}) \Bigg\| _{2}^{2}\leq4\lambda_{n} \Bigg\| \theta^{*} \Bigg\| _{1} \]

  • Proof:

$$ \[\begin{align} \frac{1}{2n}||X(\widehat{\theta}_{\mathrm{lasso}}-\theta^{*})||_{2}^{2}\ &\leq\ \frac{\epsilon^{\top}X(\widehat{\theta}_{\mathrm{lasso}}-\theta^{*})}{n} &&+\lambda_{n}(||\theta^{*}||_{1}-||\widehat{\theta}_{\mathrm{lasso}}||_{1}) \\ &\overset{(i)}{\le} {\frac{1}{n}}\|\epsilon^{\mathsf{T}}X\|_{\infty}\|\widehat{\theta}_{\mathrm{lasso}}-\theta^{*}\|_{1} &&+\lambda_{n}(\|\theta^{*}\|_{1}-\|\widehat{\theta}_{\mathrm{lasso}}\|_{1}) \\ &\overset{(ii)}{\le}\frac{1}{n}||\epsilon^{\top}X||_{\infty}(||\widehat{\theta}_{\mathrm{lasso}}||_{1}+||\theta^{*}||_{1}) &&+\lambda_{n}(||\theta^{*}||_{1}-||\widehat{\theta}_{\mathrm{lasso}}||_{1}) \\ &= \|\widehat\theta_{\mathrm{lasso}}\|_{1}\left(\frac{1}{n}\|\epsilon^{\mathsf{T}}X\|_{\infty}-\lambda_{n}\right) &&+\|\theta^{*}\|_{1}\left(\frac{1}{n}\|\epsilon^{\mathsf{T}}X\|_{\infty}+\lambda_{n}\right) \\ &\stackrel{(iii)}{\le}2\lambda_{n}\vert\vert\theta^{*}\|_{1} \end{align}\] $$

  1. 휠더 부등식
  2. triangle ineq.
  3. (8.4) 의 \(\lambda_n\) 에 대해 걸었던 condition.

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

  • \(lambda_n\) 의 good choice 는 무엇인가?

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

$$ \[\begin{alignat}{2} \mathbb{P}\!\left(\frac{1}{n}||\epsilon^{\textsf{T}}X||_{\infty}\geq t\right)\ &= \mathbb{P}\!\left(\max\limits_{1\le j \le d} |X_{j}^{\textsf{T}}\epsilon|\geq\,t n\right) \\ &\leq\mathrm{~}\sum_{j=1}^{d}\mathbb{P}(|X_{j}^{\top}\epsilon|\geq\,t n) \\ &=\;\sum_{j=1}^{d}\mathbb{P}\left({\frac{|X_{j}^{\top}\epsilon|}{||X_{j}||_{2}}}\geq\,{\frac{t n}{||X_{j}||_{2}}}\right) \\ &\leq\ 2d\exp\left(-\,\frac{n^{2}t^{2}}{2\sigma^{2}\,\max\limits_{1\le j\le d}\,||X_{j}||^{2}}\right) \\ &\leq\ 2d\exp\left(-\,\frac{n t^{2}}{2C^{2}\sigma^{2}}\right) &&=\delta \end{alignat}\]\end{alignat} $$

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

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

\[ {\frac{1}{n}}\|X(\widehat{\theta}_{\mathrm{lasso}}-\theta^{*})\|_{2}^{2}\lesssim \|\theta^{*}\|_{1} \cdot \sigma\sqrt{\frac{\log(d)+\log(n)}{n}} \]

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

  • Parameter Estimation

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

\[ ||{\widehat\theta}_{\mathrm{lasso}}-\theta^{*}||_{2}^{2} \lesssim {\frac{||\theta^{*}||_1}{C_{\mathrm{min}}}} \cdot \sigma\sqrt{\frac{\log(d)+\log(n)}{n}} \]




8.8.3.3 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\ge1:C(\alpha,S)=\{\Delta\in\mathbb{R}^{d}:||\Delta_{S^{c}}||_{1}\leq\alpha\|\Delta_{S}\|_{1}\}\). 이 notation 들을 써서 이하 정의.

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

\[ forall \Delta\in C(\alpha,S):{\frac{1}{n}}\|X\Delta\|_{2}^{2}\geq\kappa\|\Delta\|_{2}^{2} \]

  • Remark.

RE condition 에 대한 직관을 좀 얻어보자. cost difference \(\mathcal{L}_{n}(\widehat{\theta}_{\mathrm{lasso}})-\mathcal{L}_{n}(\theta^{*})=\frac{1}{2n}\vert\vert Y-X\widehat{\theta}_{\mathrm{lasso}}\vert\vert_{2}^{2}-\frac{1}{2n}\vert\vert Y-X\theta^{*}\vert\vert_{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}\geq\kappa||\Delta||_{2}^{2}\gt 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 8.15 (Fast Convergence Rate) linear model (8.1) 을 살피고, \(S=\{i : \theta^\ast_i \not = 0 \}\) 에 대해 패러미터 \((3, \kappa)\) 를 통해 RE condition 을 만족하는 \(X\) 를 assume. 이때, \(S\) 의 cardinality 가 \(s\) 를 쓰자. 여기서 만약 \(\lambda_{n}\geq2\left\| \frac{X^{\textsf{T}}\epsilon}{n}\right\|_{\infty}\) 가 성립한다면 이하가 성립.

\[ {\frac{1}{n}}||X(\widehat{\theta}_{\mathrm{lasso}}-\theta^{*})||_{2}^{2}\leq9{\frac{s\lambda_{n}^{2}}{\kappa}}, \; \; \; \; \; \; \; \; \; \; \; ||\widehat{\theta}_{\mathrm{lasso}}-\theta^{*}||_{2} \le3{\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}\; \leq \;{\frac{\epsilon^{\top}X\hat{\Delta}}{n}}+\lambda_{n}(||\theta^{*}||_{1}-||\hat{\theta}_{\mathrm{lasso}}||_{1})\) 임을 보일 수 있다. \(\theta^\ast\) 가 s-sparse 이며 \(\hat \Delta = \hat \theta_{lasso}-\theta^\ast\) 이므로 이하가 성립.

$$ \[\begin{alignat}{2} \|\theta^{*}\|_{1}-\|{\widehat{\theta}}_{\mathrm{lasso}}\|_{1} &=\|\theta_{S}^{*}\|_{1}-\|\widehat{\theta}_{\mathrm{lasso}}\|_{1} \\ &= \| \theta_{S}^{*}\|_{1}-\|{\hat{\Delta}}+\theta^{*}\|_{1} \\ &=\|\theta_{S}^{*}\|_{1} &&-\|\widehat{\Delta}_{S}+\theta_{S}^{*}\|_{1} - \| \hat \Delta_{S^c} \|_1 \\ &\leq \|\hat{\Delta}_{S}\|_{1}+\ \|\widehat{\Delta}_{S}+\theta_{S}^{*}\|_{1} &&- \|\widehat{\Delta}_{S}+\theta_{S}^{*}\|_{1}\nonumber-\|\widehat{\Delta}_{S^{c}}\|_{1}\nonumber \tag{triangle ineq.} \\ &= \| \hat \Delta_S \|_1 - \| \hat \Delta_{S^c}\|_1 \end{alignat}\] $$

$$ \[\begin{alignat}{2} 0\;\leq\;\frac{1}{n}\Vert X\hat{\Delta}\Vert_{2}^{2} &\stackrel{(i)}{\le}\;\frac{2}{n}\Vert\epsilon^{\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}) \tag{Holder} \\ & {\stackrel{\mathrm{(ii)}}{\leq}}\ \ \lambda_{n}\|{\widehat\Delta}\|_{1} &&+2\lambda_{n}(\|{\hat\Delta}_{S}\|_{1}-\|{\hat\Delta}_{S^{c}}\|_{1}) \tag{condition (8.8) on λ_n} \\ &= \lambda_n (\| \hat \Delta_S \|_1 + \| \hat \Delta_{S^c}\|_1 ) &&+2\lambda_n (\| \hat \Delta_S \|_1 - \| \hat \Delta_{S^c}\|_1 ) \\ &=\lambda_{n}(3||\widehat\Delta_{S}||_1-||\widehat\Delta_{S^{c}}||_1) \end{alignat}\] $$

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

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

$$ \[\begin{align} {\frac{1}{n}}\|X{\widehat{\Delta}}\|_{2}^{2}\;&\leq\;\lambda_{n}(3\|\widehat{\Delta}_{S}\|_{1}-\|\widehat{\Delta}_{S^{c}}\|_{1})\leq3\lambda_{n}\|\widehat{\Delta}_{S}\|_{1} \\ &\overset{(i)}{\le} 3 \lambda_{n}\sqrt{s}||\hat{\Delta}_{S}||_{2} \tag{1} \\ &\leq\ 3\lambda_{n}\sqrt{s}||\hat{\Delta}||_{2} \\ &\overset{(ii)}{\le}\frac{3\lambda_{n}\sqrt{s}}{\sqrt{n\kappa}}\|X\widehat{\Delta}\|_{2} \tag{ineq. (8.9)} \\ \iff {\frac{1}{n}}\|X(\widehat{\theta}_{\mathrm{lasso}}-\theta^{*})\|_{2}^{2} & \leq9{\frac{s\lambda_{n}^{2}}{\kappa}} \end{align}\] $$

  1. \(\forall x\in\mathbb{R}^{d},\,\|x\|_{1}\leq{\sqrt{d}}\|x\|_{2}\)

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

  • Remark.

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

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