Buhlmann and van de Geer (2011) Section 6.2 Least squares and the Lasso 2/2

6.2.2 続き

• Let , , .
• 明らかに .

Lemma 6.3: On with , .

Proof.

Lemma 6.1 と から，

\begin{align*}2||\mathbf{X}(\hat \beta - \beta^0) ||_2^2/n + 2\lambda || \hat \beta ||_1 \le \lambda ||\hat \beta - \beta^0|| + 2 \lambda || \beta^0 ||_1\end{align*}

また，三角不等式から

\begin{align*} || \hat \beta ||_1 = || \hat \beta_{S_0} ||_1 + || \hat \beta_{S_0^c} ||_1 \ge || \beta_{S_0}^0 ||_1 - || \hat \beta_{S_0} - \beta_{S_0}^0 ||_1 + || \hat \beta_{S_0^c} ||_1 \end{align*}

さらに，, から結果を得る．

• Cauchy-Schwarz inequality から，
• Recall that , .
• ここで，ある について ならば，不等式をさらに進めることができる．
• 一方， はランダムなので上の不等式を満たす を直接仮定することはできない． のある集合上で一様に不等式を満たす を考える．
• Lemma 6.3 から， の上で を満たす．

Compatibility condition: ある と について，.

• Compatibility condition はどのようなときに満たされる？
  • から， の最小固有値が十分に大きければOK．
  • の制約があるので，直接固有値に仮定を入れるよりは弱い．
  • は観測できないので，仮定を直接検証することはできない．
  • Bickel et al. (2009) では restricted eigenvalue assumption と呼んでいる．

Theorem 6.1: Compatibility condition + + .

\begin{align*}||\mathbf{X}(\hat \beta - \beta^0) ||_2^2/n \le 4 \lambda^2 s_0 / \phi_0^2, \quad ||\hat \beta - \beta^0||_1 \le 4 \lambda s_0 / \phi_0^2 \end{align*}

Proof. 

Lemma 6.3 から

\begin{align*} 2||\mathbf{X}(\hat \beta - \beta^0) ||_2^2/n + \lambda||\hat \beta - \beta^0||_1 & = 2||\mathbf{X}(\hat \beta - \beta^0) ||_2^2/n + \lambda||\hat \beta_{S_0} - \beta^0_{S_0}||_1 + \lambda ||\hat \beta_{S_0^c}||_1 \\ & = 4 \lambda ||\hat \beta_{S_0} - \beta^0_{S_0}||_1 \\ & \le 4 \lambda \sqrt{s_0} ||\hat \beta_{S_0} - \beta^0_{S_0}||_2 \\ & \le 4 \lambda \sqrt{s_0} ||\mathbf{X}(\hat \beta - \beta^0)||_2/(\sqrt{n}\phi_0) \\ & \le  ||\mathbf{X}(\hat \beta - \beta^0)||_2^2/n + 4 \lambda^2 s_0/\phi_0^2 \end{align*}

最後の不等式では を使った．