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

6.2.1 Introduction

$Y_i = \sum_{j = 1}^p \beta_j X_i^{(j)} + \epsilon_i$ , $i = 1, \ldots, n$ . In matrix notation, $\mathbf{Y} = \mathbf{X}\beta + \epsilon$ .
$\mathbf{X}$ は固定， $\epsilon$ は i.i.d. $N(0,\sigma^2)$ とする．

For the moment, $p \le n$ とおく．

Least squares estimator: $\hat b := (\mathbf{X}^\top \mathbf{X})^{-1} \mathbf{X} \mathbf{Y}$
このとき， $|| \mathbf{X}(\hat b - \beta^0) ||_2^2/\sigma^2 = \epsilon^\top \mathbf{X} (\mathbf{X}^\top \mathbf{X})^{-1} \mathbf{X}^\top \epsilon/\sigma^2 \sim \chi_p^2$

とくに， $\frac{E || \mathbf{X}(\hat b - \beta^0) ||_2^2}{n} = \frac{\sigma^2}{n}p$ もわかる (as $trace[\mathbf{X} (\mathbf{X}^\top \mathbf{X})^{-1} \mathbf{X}^\top] = p$ )．
つまり， $\mathbf{X}^\top \mathbf{X}/n = I_p$ と正規化しておけば，各 $\beta^0_j$ を $\sigma^2/n$ (全体としては $(\sigma^2 / n) \times p$ ) の精度で推定可能．

以降では， $p \gt n$ と仮定する．

Active set: $S_0 := \{j: \beta_j^0 \neq 0\}$ , Sparsity index: $s_0 = |S_0|$ .
$S_0$ が既知かつ $s_0 \le n$ ならば，上の議論から，推定二乗誤差は $(\sigma^2 / n) \times s_0$ になる．
The Lasso:

\begin{align*}\hat \beta := \arg\min_\beta \left\{ \frac{|| \mathbf{Y} - \mathbf{X}\beta||_2^2}{n} + \lambda ||\beta||_1\right\}\end{align*}

$\lambda$ をうまく ( $\sigma \sqrt{\log p/n}$ ) のオーダーで選ぶと...

Oracle Inequality: $\frac{|| \mathbf{X}(\hat \beta - \beta^0) ||_2^2}{n} \le \text{cont.} \frac{\sigma^2 \log p}{n} s_0$ .

つまり， $S_0$ がわからない場合でも $\log p$ だけの損失で済む．

6.2.2 The result assuming the truth is linear

Lemma 6.1 (Basic Inequality)

$|| \mathbf{X}(\hat \beta - \beta^0) ||_2^2/n + \lambda || \hat \beta ||_1 \le 2 \epsilon^\top \mathbf{X}(\hat \beta - \beta^0)/n + \lambda ||\beta^0||_1$ .

Proof.

$\hat \beta$ の定義から，

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

また， $\mathbf{Y} - \mathbf{X}\hat \beta = -\mathbf{X}(\hat \beta - \beta^0) + \epsilon$ なので，これを代入すれば結果を得る．

$2 \epsilon^\top \mathbf{X}(\hat \beta - \beta^0)/n$ を empirical process part などと呼ぶ．
Empirical process part は

\begin{align*}2|\epsilon^\top \mathbf{X}(\hat \beta - \beta^0)|/n \le 2 \left( \max_j |\epsilon^\top \mathbf{X}^{(j)}| \right) ||\hat \beta - \beta^0 ||_1/n\end{align*}

で bound できる．

通常， $\lambda$ は empirical process part を dominate するように選ぶ．
$\mathcal{T} := \left\{ 2 \max_j |\epsilon^\top \mathbf{X}^{(j)}|/n \le \lambda_0 \right\}$ とするとき， $\lambda \ge 2\lambda_0$ とおくことで $|| \mathbf{X}(\hat \beta - \beta^0) ||_2^2/n \lesssim \lambda$ を目指す.
Let $\hat \Sigma := \mathbf{X}^\top \mathbf{X} /n$ and $\hat{\sigma}^2_j := \hat \Sigma_{j,j}$ ( $j = 1, \ldots, p$ ).

Lemma 6.2

$\hat{\sigma}^2_j = 1$ とする．このとき，任意の $t \gt 0$ について， $\lambda_0 := 2 \sigma \sqrt{\frac{t^2 + 2 \log p}{n}}$ とおけば，

\begin{align*} \Pr(\mathcal{T}) \ge 1 - 2 \exp[-t^2/2]. \end{align*}

Proof.

仮定から, $V_j := \epsilon^\top \mathbf{X}^{(j)}/\sqrt{n \sigma^2} \sim N(0,1)$ . したがって，

\begin{align*} \Pr(\mathcal{T}) & = \Pr\left(2 \max_j |\epsilon^\top \mathbf{X}^{(j)}|/n \gt 2 σ \sqrt{\frac{t^2 + 2 \log p}{n}} \right) \\ & = \Pr\left( \max_j |V_j| \gt \sqrt{t^2 + 2 \log p} \right) \\ & \le 2 p \exp \left[ - \frac{t^2 + 2 \log p}{2}\right] = 2 \exp \left[ - \frac{t^2}{2}\right]. \end{align*}*1

Corollary 6.1 (Consistency of the Lasso)

$\hat{\sigma}^2_j = 1$ とする．このとき，任意の $t \gt 0$ について， $\lambda := 4 \hat \sigma \sqrt{\frac{t^2 + 2 \log p}{n}}$ とおく． $\hat \sigma$ は $\sigma$ の推定量．このとき，少なくとも $1- \alpha$ の確率で

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

ただし $\alpha := 2 \exp[-t^2/2] + \Pr(\hat \sigma \le \sigma)$

Proof.

Lemma 6.1 から，

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

ここで，もし $4 \max_j |\epsilon^\top \mathbf{X}^{(j)}|/n \le \lambda$ ならば，三角不等式から

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

また，

\begin{align*}\Pr(4 \max_j |\epsilon^\top \mathbf{X}^{(j)}|/n \le \lambda) & = 1 - \Pr\left(4 \max_j |\epsilon^\top \mathbf{X}^{(j)}|/n \gt 4 \hat σ \sqrt{\frac{t^2 + 2 \log p}{n}} \right) \\ & \ge 1 - \Pr\left( \max_j |\epsilon^\top \mathbf{X}^{(j)}|/n \gt \hat σ \sqrt{\frac{t^2 + 2 \log p}{n}}, \hat σ \gt σ \right) - \Pr(\hat σ \le σ) \\ & \ge 1 - 2 \exp[-t^2/2] - \Pr(\hat σ \le σ) \end{align*}

この結果から， $\lambda \asymp \sqrt{\log p /n}$ であるとき， $||\beta^0||_1 = o(\sqrt{n/ \log p})$ ならば Lasso は一致性を持つ．

*1:Chernoff bound + Standard normality