of (\[eq:multi-stage-param-est-bound\]). While the main high-level argument follows that of [@Zhang09-multistage], there are many differences in the details, and hence a full proof (which is included in Section \[apx:proof\]) is still needed. This theorem is the main result of the paper. It is worth mentioning that although we only consider the simple capped-$L_1$ regularizer, similar results can be obtained for other regularizers (with virtually the same proof) such that $g'(u) \in [0, \infty)$, $g'(u)>0$ when $u$ belongs to a neighbor of $0$, and $g'(u)=0$ when $u \geq \theta$, with a threshold $\theta>0$ appropriately chosen at the order of the noise level — the condition of $g'(u)=0$ when $u \geq \theta$ ensures the removal of feature selection “bias” of Lasso which we discussed above. As an example, very similar result can be obtained for the MC+ penalty of [@Zhang10-mc+] or SCAD penalty of [@FanLi01] using the multi-stage convex relaxation procedure here. In fact, in practice there may be additional advantages of using a smooth nonconvex penalty such as MC+ due to the extra smoothness, although such advantage is not revealed in our theoretical analysis.

\[thm:multi-stage-featsel\] Let Assumption \[assump:fixed\] hold. Assume also that the target $\bar{{{\mathbf w}}}$ is sparse, with ${{\mathbf E}}y_i 