5 5 8 Approximately Sparse Linear Regression

This exercise is adapted from Cevid et al. [52]. We observe $Y \in \mathbb{R}^n$ and $\mathbf{X} \in \mathbb{R}^{n \times p}$. We assume that

(1)

\begin{align} Y=\mathbf{X}\left(\beta^*+b^*\right)+\varepsilon \end{align}

with $\beta^* \in \mathbb{R}^p$ coordinate sparse and $b^* \in \mathbb{R}^p$ with small $\ell^2$ norm. The noise term $\varepsilon$ is a random variable following a subgaussian $\left(\sigma^2 I\right)$ distribution, which means that for any $u \in \mathbb{R}^n$ we have $\mathbb{P}[\langle u, \varepsilon\rangle \geq \sigma t\|u\|] \leq e^{-t^2 / 2}$. We assume that the $p$ columns $X_1, \ldots, X_p$ of $\mathbf{X}$ are deterministic and have norm $\sqrt{n}$.

A) A Convex Estimator

For $\lambda_1, \lambda_2>0$, we consider the estimator of $\left(\beta^*, b^*\right)$

(2)

\begin{align} (\widehat{\beta}, \widehat{b}) \in \underset{\beta, b \in \mathbb{R}^p}{\operatorname{argmin}} \left\{ \frac{1}{n} \| Y - \mathbf{X} (\beta + b) \|^2 + \lambda_1 |\beta|_1 + \lambda_2 \|b\|^2 \right\} . \end{align}

We emphasize that this estimator does not correspond to the Elastic-Net, as the $\ell^1$ penalization is on $\beta$ and the $\ell^2$ penalization is on $b$.

1. This estimator makes sense in this context because the Lasso $\lambda_1 |\beta|_1$ term is consistent with the sparsity of $\beta^*$ and the Ridge $\lambda_2 \| b \|^2$ term is consistent with the hypothesis that $b^*$ has a small $\ell^2$ norm.

2. We prove that there exists a matrix $G \in \mathbb{R}^{p \times n}$ such that

(3)

\begin{align} \widehat{\beta} \in \underset{\beta \in \mathbb{R}^p}{\operatorname{argmin}} \left\{ \frac{1}{n} \left\| ( I - \mathbf{X} G)^{1/2} ( Y - \mathbf{X} \beta ) \right\|^2 + \lambda_1 |\beta|_1 \right\} \quad \text { and } \quad \widehat{b} = G ( Y - \mathbf{X} \widehat{\beta} ) \end{align}

First, let us denote the objective function:

(4)

\begin{align} \Phi: (\beta, b) \in \mathbb{R}^p \times \mathbb{R}^p \mapsto \frac{1}{n} \| Y - \mathbf{X} (\beta + b) \|^2 + \lambda_1 |\beta|_1 + \lambda_2 \|b\|^2 \end{align}

as well as $\Phi_\beta = \Phi ( \beta, \cdot )$ and $\Phi^b = \Phi ( \cdot, b )$.

Since for each $\beta \in \mathbb{R}^p$, the function $\Phi_\beta$ is differentiable over $\mathbb{R}^p$, we have:

(5)

\begin{aligned} b \in \operatorname{argmin} \Phi_\beta &\Rightarrow \nabla \Phi_\beta (b) = 0 \\ &\iff - \frac{1}{n} \mathbf{X}^\top ( Y - \mathbf{X} (\beta + b) ) + \lambda_2 b = 0 \\ &\iff (\mathbf{X}^\top \mathbf{X} + n \lambda_2 I_p) \, b = \mathbf{X}^\top (Y - \mathbf{X} \beta) \end{aligned}

Since $\mathbf{X}^\top \mathbf{X}$ has nonnegative eigenvalues, $\mathbf{X}^\top \mathbf{X} + n \lambda_2 I_p$ is invertible, and the previous conditions are equivalent to:

(6)

\begin{align} b = G ( Y - \mathbf{X} \beta) \quad \text{ with } \quad G = (\mathbf{X}^\top \mathbf{X} + n \lambda_2 I_p)^{-1} \mathbf{X}^\top \end{align}

In particular, since $\widehat{b} \in \operatorname{argmin} \Phi_{\widehat{\beta}}$, this gives:

(7)

\begin{align} \widehat{b} = G ( Y - \mathbf{X} \widehat{\beta}) \end{align}

Hence:

(8)

\begin{align} \widehat{\beta} \in \underset{\beta \in \mathbb{R}^p}{\operatorname{argmin}} \Phi (\beta, G ( Y - \mathbf{X} \beta)) \end{align}

To conclude the proof, we just have to rewrite this new objective function as a classical Lasso objective. Let us fix $\beta \in \mathbb{R}^p$, and denote, for the sake of convenience, $\delta = Y - \mathbf{X} \beta$. Then:

(9)

\begin{aligned} \Phi (\beta, G \delta) &= \frac{1}{n} \| Y - \mathbf{X} (\beta + G \delta) \|^2 + \lambda_1 |\beta|_1 + \lambda_2 \| G \delta \|^2 \\ &= \frac{1}{n} \| (I - \mathbf{X} G) \delta \|^2 + \lambda_1 |\beta|_1 + \lambda_2 \| G \delta \|^2 \\ &= \frac{1}{n} \| (I - \mathbf{X} G)^{1/2} \delta \|^2 + \frac{1}{n} \langle \mathbf{X} G \delta, (\mathbf{X} G - I) \delta \rangle + \lambda_1 |\beta|_1 + \lambda_2 \| G \delta \|^2 \\ &= \frac{1}{n} \| (I - \mathbf{X} G)^{1/2} \delta \|^2 + \frac{1}{n} \left[ \langle G \delta, (\mathbf{X}^\top \mathbf{X} G - \mathbf{X}^\top) \delta \rangle + \langle G \delta, n \lambda_2 G \delta \rangle \right] + \lambda_1 |\beta|_1 \\ &= \frac{1}{n} \| (I - \mathbf{X} G)^{1/2} \delta \|^2 + \frac{1}{n} \langle G \delta, \left[ (\mathbf{X}^\top \mathbf{X} + n \lambda_2 I_p) G - \mathbf{X}^\top \right] \delta \rangle + \lambda_1 |\beta|_1 \\ \Phi (\beta, G (Y - \mathbf{X} \beta)) &= \frac{1}{n} \left\| ( I - \mathbf{X} G)^{1/2} ( Y - \mathbf{X} \beta ) \right\|^2 + \lambda_1 |\beta|_1 \end{aligned}

3. Let us assume that $n \leq p$ and $\operatorname{rank}(\mathbf{X})=n$. Let $\mathbf{X}=\sum_{k=1}^n \sigma_k u_k v_k^T$ be a singular value decomposition of $\mathbf{X}$ (Theorem C.1, page 311).

We can compute the eigenvalues of $F:=$ $(I-\mathbf{X} G)^{1 / 2}$ in terms of the singular values of $\mathbf{X}$. For the sake of convenience, we denote $\Sigma = \mathbf{X}^\top \mathbf{X} + n \lambda_2 I_p$, such that $G = \Sigma^{-1} \mathbf{X}^\top$ and $I - \mathbf{X}^\top G = I - \mathbf{X} \Sigma^{-1} \mathbf{X}^\top$. Then, if $1 \leq k,j \leq n$:

(10)

\begin{aligned} \langle \mathbf{X} \Sigma^{-1} \mathbf{X}^\top u_k, u_j \rangle &= \langle \Sigma^{-1} \mathbf{X}^\top u_k, \mathbf{X}^\top u_j \rangle \\ &= \langle \Sigma^{-1} \sigma_k v_k, \sigma_j v_j \rangle \\ &= \frac{\sigma_k^2}{\sigma_k^2 + n \lambda_2} \delta_{k,j} \end{aligned}

So if $\sigma_1 \geq \dots \geq \sigma_n$, the eigenvalues of $F = (I - \mathbf{X} G)^{1/2}$ are:

(11)

\begin{align} \sqrt{\frac{n \lambda_2}{n \lambda_2 + \sigma_n^2}} \geq \dots \geq \sqrt{\frac{n \lambda_2}{n \lambda_2 + \sigma_1^2}} \end{align}

B) Linearly Transformed Lasso

Let $F \in \mathbb{R}^{n \times n}$ be any symmetric matrix and set $\widetilde{\mathbf{X}}=F \mathbf{X}, \widetilde{Y}=F Y$ and $\widetilde{\varepsilon}=F \varepsilon$. We analyze the estimator

(12)

\begin{align} \widehat{\beta} \in \underset{\beta \in \mathbb{R}^p}{\operatorname{argmin}}\left\{\frac{1}{n}\|\widetilde{Y}-\widetilde{\mathbf{X}} \beta\|^2+\lambda|\beta|_1\right\} \end{align}

in the model (5.31), for the choice $\lambda=A \sigma \sqrt{\frac{\log (p)}{n}} \lambda_{\max }\left(F^2\right)$, with $A>\sqrt{32}$ and $\lambda_{\max }\left(F^2\right)$ the largest eigenvalue of $F^2$. Our goal is to prove that we have

(13)

\begin{align} \mathbb{P}\left[\left|\widehat{\beta}-\beta^*\right|_1 \leq \frac{9 \lambda|\beta^*|_0}{\phi(\widetilde{\mathbf{X}}, S)^2}+\frac{6}{n \lambda}\left\|\widetilde{\mathbf{X}} b^*\right\|^2\right] \geq 1-2 p^{1-A^2 / 32} \end{align}

where $S=\left\{j: \beta_j^* \neq 0\right\}$,

(14)

\begin{align} \phi(\widetilde{\mathbf{X}}, S)=\min _{x \in R(S)} \frac{\sqrt{|S|} \| \widetilde{\mathbf{X}} x \|}{\sqrt{n}\left|x_S\right|_1}, \quad \text { with } R(S)=\left\{x \in \mathbb{R}^p:\left|x_{S^c}\right|_1 \leq 5\left|x_S\right|_1\right\} \end{align}

The proof technique is somewhat different from the one of Theorem 5.1 (page 95).

1. First, by optimality of $\widehat{\beta}$ we have that:

(15)

\begin{aligned} \frac{1}{n} \| \widetilde{Y} - \widetilde{\mathbf{X}} \widehat{\beta} \|^2 + \lambda | \widehat{\beta} |_1 &\leq \frac{1}{n} \| \widetilde{Y} - \widetilde{\mathbf{X}} \beta^* \|^2 + \lambda | \beta^* |_1 \\ \frac{1}{n} \| \widetilde{\mathbf{X}} \left( \widehat{\beta} - \beta^* \right) \|^2 + \lambda | \widehat{\beta} |_1 &\leq \frac{2}{n} \left\langle \widetilde{Y} - \widetilde{\mathbf{X}} \beta^*, \widetilde{\mathbf{X}} \left( \widehat{\beta} - \beta^* \right) \right\rangle + \lambda | \beta^* |_1 \\ \frac{1}{n} \left\| \widetilde{\mathbf{X}} \left(\widehat{\beta} - \beta^* - b^* \right) \right\|^2 + \lambda | \widehat{\beta} |_1 &\leq \frac{1}{n} \left\| \widetilde{\mathbf{X}} b^* \right\|^2 + \frac{2}{n} \left\langle \widetilde{\varepsilon}, \widetilde{\mathbf{X}} \left(\widehat{\beta} - \beta^* \right) \right\rangle + \lambda | \beta^* |_1 \end{aligned}

where we used the fact that $\widetilde{\varepsilon} = \widetilde{Y} -\widetilde{\mathbf{X}} \left( \beta^* + b^* \right)$.

2. In Questions 2 to 4 , we assume that the event $\Omega_\lambda = \left\{ \frac{1}{n} \left| \widetilde{\mathbf{X}}^T \widetilde{\varepsilon} \right|_{\infty} \leq \lambda / 4 \right\}$ holds.
Then on $\Omega_\lambda$:

(16)

\begin{aligned} \frac{1}{n} \left\langle \widetilde{\varepsilon}, \widetilde{\mathbf{X}} \left(\widehat{\beta} - \beta^* \right) \right\rangle &= \left\langle \frac{1}{n} \widetilde{\mathbf{X}}^\top \widetilde{\varepsilon}, \widehat{\beta} - \beta^* \right\rangle \\ &\leq_{\text{(Hölder's inequality)}} \frac{1}{n} \left| \widetilde{\mathbf{X}}^T \widetilde{\varepsilon} \right|_{\infty} \left| \widehat{\beta} - \beta^* \right|_1 \\ &\leq \frac{\lambda}{4} \left| \widehat{\beta} - \beta^* \right|_1 \\ &\leq \frac{\lambda}{4} \left( \left| \widehat{\beta}_S - \beta^*_S \right|_1 + \left| \widehat{\beta}_{S^c} \right|_1 \right) \end{aligned}

Moreover, without assuming $\Omega_\lambda$ holds:

(17)

\begin{align} \left| \beta^* \right|_1 - \left| \widehat{\beta} \right|_1 = \left| \beta^*_S \right|_1 - \left| \widehat{\beta}_S \right|_1 - \left| \widehat{\beta}_{S^c} \right|_1 \leq \left| \widehat{\beta}_S - \beta^*_S \right|_1 - \left| \widehat{\beta}_{S^c} \right|_1 \end{align}

Combining both inequalities we get:

(18)

\begin{align} \lambda \left( \left| \beta^* \right|_1 - \left| \widehat{\beta} \right|_1 \right) + \frac{2}{n} \left\langle \widetilde{\varepsilon}, \widetilde{\mathbf{X}} \left(\widehat{\beta} - \beta^* \right) \right\rangle \leq \frac{3 \lambda}{2} \left| \widehat{\beta}_S - \beta^*_S \right|_1 - \frac{\lambda}{2} \left| \widehat{\beta}_{S^c} \right|_1 \end{align}

which in turn, combined with last question's inequality, gives the desired result:

(19)

\begin{align} \frac{1}{n} \left\| \widetilde{\mathbf{X}} \left(\widehat{\beta} - \beta^* - b^* \right) \right\|^2 + \frac{\lambda}{2} \left| \widehat{\beta}_{S^c} \right|_1 \leq \frac{3 \lambda}{2} \left|\widehat{\beta}_S - \beta_S^* \right|_1 + \frac{1}{n} \left\| \widetilde{\mathbf{X}} b^* \right\|^2 \end{align}

3. In the case where $\left\|\widetilde{\mathbf{X}} b^*\right\|^2 \geq n \lambda\left|\widehat{\beta}_S-\beta_S^*\right|_1$, and assuming that $\Omega_\lambda$ holds:

(20)

\begin{aligned} \frac{1}{n} \left\| \widetilde{\mathbf{X}} \left(\widehat{\beta} - \beta^* - b^* \right) \right\|^2 + \frac{\lambda}{2} \left| \widehat{\beta}_{S^c} \right|_1 &\leq \frac{3}{2n} \left\| \widetilde{\mathbf{X}} b^* \right\|^2 + \frac{1}{n} \left\| \widetilde{\mathbf{X}} b^* \right\|^2 \\ \frac{\lambda}{2} \left| \widehat{\beta}_{S^c} \right|_1 &\leq \frac{5}{2n} \left\| \widetilde{\mathbf{X}} b^* \right\|^2 \\ \left| \widehat{\beta}_S - \beta^*_S \right|_1 + \left| \widehat{\beta}_{S^c} \right|_1 &\leq \frac{1}{n \lambda} \left\| \widetilde{\mathbf{X}} b^* \right\|^2 + \frac{5}{n \lambda} \left\| \widetilde{\mathbf{X}} b^* \right\|^2 \end{aligned}

Hence:

(21)

\begin{align} \left| \widehat{\beta} - \beta^* \right|_1 \leq \frac{6}{n \lambda} \left\| \widetilde{\mathbf{X}} b^* \right\|^2 \end{align}

4. In the case where $\left\| \widetilde{\mathbf{X}} b^* \right\|^2 \leq n \lambda \left| \widehat{\beta}_S - \beta_S^* \right|_1$, and assuming that $\Omega_\lambda$ holds:

(22)

\begin{align} \frac{1}{n} \left\| \widetilde{\mathbf{X}} \left(\widehat{\beta} - \beta^* - b^* \right) \right\|^2 + \frac{\lambda}{2} \left| \widehat{\beta}_{S^c} \right|_1 \leq \frac{5 \lambda}{2} \left|\widehat{\beta}_S - \beta_S^* \right|_1 \end{align}

In particular: $\left| \left( \widehat{\beta} - \beta^* \right)_{S^c} \right|_1 \leq 5 \left| \left( \widehat{\beta} - \beta^* \right)_S \right|_1$ hence $\widehat{\beta} - \beta^*$ is in $R(S)$. Then, adding $\frac{\lambda}{2} \left|\widehat{\beta}_S - \beta_S^* \right|_1$ to each side of the previous inequality:

(23)

\begin{aligned} \frac{1}{n} \left\| \widetilde{\mathbf{X}} \left( \widehat{\beta} - \beta^* - b^* \right) \right\|^2 + \frac{\lambda}{2} \left| \widehat{\beta} - \beta^* \right|_1 &\leq 3 \lambda \left|\widehat{\beta}_S - \beta_S^* \right|_1 \\ &\leq 3 \frac{\lambda \sqrt{|\beta^*|_0} \left\| \widetilde{\mathbf{X}} \left( \widehat{\beta} - \beta^* \right) \right\|}{\sqrt{n} \phi ( \widetilde{\mathbf{X}}, S )} \end{aligned}

because $\phi ( \widetilde{\mathbf{X}}, S ) \leq \frac{\sqrt{\left| \beta^* \right|_0} \left\| \widetilde{\mathbf{X}} \left( \widehat{\beta} - \beta^* \right) \right\|}{\sqrt{n} \left|\widehat{\beta}_S - \beta_S^* \right|_1}$.

5. To conclude the proof of (5.33), we first prove that on $\Omega_\lambda$:

(24)

\begin{align} \left|\widehat{\beta}-\beta^*\right|_1 \leq \frac{9 \lambda|\beta^*|_0}{\phi(\widetilde{\mathbf{X}}, S)^2}+\frac{6}{n \lambda}\left\|\widetilde{\mathbf{X}} b^*\right\|^2 \end{align}

then that:

(25)

\begin{align} \mathbb{P}\left( \Omega_\lambda \right) \geq 1-2 p^{1-A^2 / 32} \end{align}

- Proving the inequality on $\Omega_\lambda$: In the case of Question 3, it is immediate. Then, let us make the same assumption than in Question 4.

For the sake of convenience, let us denote $\alpha = 3 \frac{\lambda \sqrt{|\beta^*|_0}}{\phi ( \widetilde{\mathbf{X}}, S )}$. Then inequality from Question 4 rewrites:

(26)

\begin{aligned} \frac{1}{n} \left\| \widetilde{\mathbf{X}} \left( \widehat{\beta} - \beta^* - b^* \right) \right\|^2 + \frac{\lambda}{2} \left| \widehat{\beta} - \beta^* \right|_1 &\leq \frac{\alpha}{\sqrt{n}} \left\| \widetilde{\mathbf{X}} \left( \widehat{\beta} - \beta^* \right) \right\| \\ &\leq_{\text{(Triangle inequality)}} \frac{\alpha}{\sqrt{n}} \left\| \widetilde{\mathbf{X}} \left( \widehat{\beta} - \beta^* - b^* \right) \right\| + \frac{\alpha}{\sqrt{n}} \left\| \widetilde{\mathbf{X}} b^* \right\| \\ &\leq_{\text{(Young)}} \frac{\alpha^2}{4} + \frac{1}{n} \left\| \widetilde{\mathbf{X}} \left( \widehat{\beta} - \beta^* - b^* \right) \right\|^2 + \frac{\alpha^2}{4} + \frac{1}{n} \left\| \widetilde{\mathbf{X}} b^* \right\|^2 \\ &\leq \frac{\alpha^2}{2} + \frac{1}{n} \left\| \widetilde{\mathbf{X}} \left( \widehat{\beta} - \beta^* - b^* \right) \right\|^2 + \frac{1}{n} \left\| \widetilde{\mathbf{X}} b^* \right\|^2 \end{aligned}

Then both sides simplify and give the desired inequality.

- Lower bounding $\mathbb{P}\left( \Omega_\lambda \right)$: We must show that:

(27)

\begin{align} \mathbb{P} \left( \overline{\Omega_\lambda} \right) \leq 2 p^{1 - A^2/32} \end{align}

We have:

(28)

\begin{aligned} \mathbb{P} \left( \overline{\Omega_\lambda} \right) &= \mathbb{P} \left( \| \mathbf{X}^\top F^2 \varepsilon \|_\infty > \frac{n \lambda}4 \right) \\ &\leq \sum_{j=1}^p \mathbb{P} \left( | \mathbf{X}^\top_j F^2 \varepsilon | \geq \frac{n \lambda}4 \right) \end{aligned}

Since $\varepsilon$ has a subgaussian$(\sigma^2 I)$ distribution, and $\| \mathbf{X}^\top_j F^2 \|_{\mathrm{op}} \leq \sqrt{n} \| F^2 \|_{\mathrm{op}}$, the $\mathbf{X}^\top_j F^2 \varepsilon, 1 \leq j \leq p$ have subgaussian$(n \| F^2 \|_{\mathrm{op}}^2 \sigma^2)$ distributions. Then for any $t \geq 0$:

(29)

\begin{align} \sum_{j=1}^p \mathbb{P} \left( \frac{| \mathbf{X}^\top_j F^2 \varepsilon |}{\sqrt{n} \| F^2 \|_{\mathrm{op}}} \geq t \right) \leq 2p\, \mathrm{e}^{-t^2/ (2 \sigma^2)} \end{align}

For $t = \frac{\sqrt{n} \lambda}{4 \| F^2 \|_{\mathrm{op}}}$, $\frac{t^2}{2 \sigma^2} = \frac{A^2}{32} \log p$, which concludes the proof.