${{\mathbf E}}y_i = \bar{{{\mathbf w}}}^\top {{\mathbf x}}_i$, and $\bar{k}=\|\bar{{{\mathbf w}}}\|_0$, and we choose $\theta$ and $\lambda$ such that $$\lambda \geq 20 \sigma \sqrt{2\rho_+(1) \ln (2p/\eta)/n}$$ and $$\theta \geq 9 \lambda /\rho_-(2\bar{k}+s) .$$ Assume that $\rho_+(s)/\rho_-(2\bar{k}+2s) 
\leq 1+ 0.5 s/\bar{k}$ for some $s \geq 2 \bar{k}$, then with probability larger than $1-\eta$: $$\|\hat{{{\mathbf w}}}^{(\ell)} - \bar{{{\mathbf w}}}\|_2
  \leq 
  \frac{17}{\rho_-(2\bar{k}+s)}
  \left[ 2 \sigma \sqrt{\rho_+(\bar{k})} \left(\sqrt{\frac{7.4 \bar{k}}{n}} +
      \sqrt{\frac{2.7 \ln (2/\eta)}{n}} \right) 
+\lambda \sqrt{k_\theta} \right]
+ \frac{0.7^{\ell} \cdot \sqrt{\bar{k}} \lambda}{\rho_-(2 \bar{k}+s)} ,
\label{eq:multi-stage-param-est-bound}$$ where $\hat{{{\mathbf w}}}^{(\ell)}$ is the solution of (\[eq:convex-relax-L1\]), and $k_\theta = \left|\{j \in \bar{F}: |\bar{{{\mathbf w}}}_j| \leq 2\theta\}\right|$.

The condition $\rho_+(s)/\rho_-(2\bar{k}+2s) \leq 1+ 0.5 s/\bar{k}$ requires the eigenvalue ratio $\rho_+(s)/\rho_-(s)$ to grow sub-linearly in $s$. Such a condition, referred to as [*sparse eigenvalue condition*]{}, is also needed in the standard analysis of $L_1$ regularization [@ZhangHuang06; @Zhang07-l1]. It is related but slightly weaker than the RIP condition in compressive sensing [@CandTao05-rip], which requires the condition $$1 - \delta_{s'} \leq \rho_-(s') \leq \rho_+(s') \leq 1 + \delta_{s'} ,$$ for some $\delta_{s'} \in (0,1)$ and $s'>\bar{k}$. For example, with $s'=6\bar{k}$, and the restricted isometry constant $\delta_{s'} \leq 1/3$, then the sparse eigenvalue condition above holds with $s=2\bar{k}$. For simplicity, in this paper we 