large in magnitude. In the extreme case where $k_\theta = \left|\{j: |\bar{{{\mathbf w}}}_j| \in (0,2\theta]\}\right|=0$, which can be achieved when all nonzero components of $\bar{{{\mathbf w}}}$ are larger than the order $\sigma \sqrt{\ln p/n}$, we obtain the following better bound $$\|\hat{{{\mathbf w}}}^{(\ell)}- \bar{{{\mathbf w}}}\|_2 = O(\sqrt{\bar{k}/n} + \sqrt{\ln (1/\eta)/n})$$ for the multi-stage procedure for a sufficiently large $\ell$ at the order of $\ln k + \ln \ln p$. This bound is superior to the standard one-stage $L_1$ regularization bound $\|\hat{{{\mathbf w}}}_{L_1}- \bar{{{\mathbf w}}}\|_2 = O(\sqrt{\bar{k} \ln (p/\eta)/n})$.

In the literature, one is often interested in two types of results, one is parameter estimation bound as in (\[eq:multi-stage-param-est-bound\]), and the other is feature selection consistency: that is, to identify the set of nonzero coefficients of the truth. Although the parameter estimation bound in (\[eq:multi-stage-param-est-bound\]) is superior to Lasso, the result does not imply that one can correctly select all variables under this condition. Moreover, the specific proof presented in [@Zhang09-multistage] does not directly imply such a result. Therefore it is important to know whether the multi-stage convex relaxation can achieve unbiased feature selection as studied in [@Zhang10-mc+]. In the following, we present such a result which supplements the parameter estimation bound 