w}}\in R^p} \left[ \frac{1}{n}\|X {{\mathbf w}}- {{\mathbf y}}\|_2^2 + 
                \sum_{j=1}^p  \lambda_j^{(\ell-1)} |{{\mathbf w}}_j| \right] .
              \label{eq:convex-relax-L1}$$

-   Let $\lambda_j^{(\ell)} = \lambda I(|\hat{{{\mathbf w}}}_j^{(\ell)}| \leq \theta )$ ($j=1,\ldots,d$)

Theoretical Analysis
====================

We require some technical conditions for our analysis. First we assume sub-Gaussian noise as follows.

\[assump:fixed\] Assume that $\{\epsilon_i\}_{i=1,\ldots,n}$ in (\[eq:noise-def\]) are independent (but not necessarily identically distributed) sub-Gaussians: there exists $\sigma \geq 0$ such that $\forall i$ and $\forall t \in R$, $${{\mathbf E}}_{\epsilon_i} e^{t \epsilon_i} \leq e^{\sigma^2 t^2/2} .$$

Both Gaussian and bounded random variables are sub-Gaussian using the above definition. For example, if a random variable $\xi \in [a,b]$, then ${{\mathbf E}}_\xi e^{t (\xi - {{\mathbf E}}\xi)} \leq e^{(b-a)^2 t^2/8}$. If a random variable is Gaussian: $\xi \sim N(0,\sigma^2)$, then ${{\mathbf E}}_\xi e^{t \xi} \leq e^{\sigma^2 t^2/2}$.

We also introduce the concept of sparse eigenvalue, which is standard in the analysis of $L_1$ regularization.

Given $k$, define $$\begin{aligned}
  \rho_+(k)=&\sup \left\{\frac{1}{n}\|X {{\mathbf w}}\|_2^2/\|{{\mathbf w}}\|_2^2 : \|{{\mathbf w}}\|_0 \leq k \right\} ,\\
  \rho_-(k)=&\inf \left\{\frac{1}{n}\|X {{\mathbf w}}\|_2^2/\|{{\mathbf w}}\|_2^2 : \|{{\mathbf w}}\|_0 \leq k \right\} .\end{aligned}$$

The following result for parameter estimation was obtained in [@Zhang09-multistage], under the Assumption \[assump:fixed\]. If we assume that the target $\bar{{{\mathbf w}}}$ is sparse, with 