path-following procedure. Both methods can achieve unbiased feature selection.

Related to the above mentioned work, a different procedure, referred to as [*multi-stage convex relaxation*]{}, was analyzed in [@Zhang09-multistage]. This procedure solves a nonconvex problem using multiple stages of Lasso relaxations, where convex formulations are iteratively refined based on solutions obtained from the previous stages. However, only parameter estimation performance was analyzed in [@Zhang09-multistage]. Unfortunately, the result in [@Zhang09-multistage] does not directly imply that multi-stage convex relaxation achieves unbiased recovery of the support set. The purpose of this paper is to prove such a support recovery result analogous to related result in [@Zhang10-mc+] (which is for a different procedure), and this result complements the parameter estimation result of [@Zhang09-multistage].

Multi-Stage Convex Relaxation with Capped-$L_1$ Regularization {#sec:theory}
==============================================================

We are interested in recovering $\bar{{{\mathbf w}}}$ from noisy observations ${{\mathbf y}}$ using the following nonconvex regularization formulation: $$\hat{{{\mathbf w}}} = \arg\min_{{{\mathbf w}}} \left[ \frac{1}{n}\| X {{\mathbf w}}- {{\mathbf y}}\|_2^2 + \lambda \sum_{j=1}^p g(|{{\mathbf w}}_j|) \right] , \label{eq:sparse-reg}$$ where $g(|{{\mathbf w}}_j|)$ is a regularization function. For simplicity, this paper only considers the specific regularizer $$g(u) = \min(u,\theta) , \label{eq:capped-L1-reg}$$ which is referred to as capped-$L_1$ regularization in [@Zhang09-multistage]. The parameter $\theta$ is a thresholding 