not optimize (\[eq:sparse-reg\]), while the latter is a path-following algorithm for solving formulations similar to (\[eq:sparse-reg\]). Although results in [@Zhang10-mc+] are comparable to ours, we should note that unlike our procedure, which is efficient due to the finite number of convex optimization, there is no proof showing that the path-following strategy in [@Zhang10-mc+] is always efficient (in the sense that there may be exponentially many switching points).

Simulation Study
================

Numerical examples can be found in [@Zhang09-multistage] that demonstrate the advantage of multi-stage convex relaxation over Lasso. Therefore we shall not repeat a comprehensive study. Nevertheless, this section presents a simple simulation study to illustrate the theoretical results. The $n \times p$ design matrix $X$ is generated with iid random Gaussian entries and each column is normalized with 2-norm $\sqrt{n}$. Here $n=100$ and $p=250$. We then generate a vector $\bar{{{\mathbf w}}}$ with $\bar{k}=30$ nonzero coefficients, and each nonzero coefficient is uniformly generated from the interval $(1,10)$. The observation is $y=X \bar{{{\mathbf w}}} + \epsilon$, where $\epsilon$ is zero-mean iid Gaussian noise with standard deviation $\sigma=1$. We study the feature selection performance of Multi-stage convex relaxation method in Figure \[fig:multi-stage-sparse\] using various configurations of $\lambda=\tau \sigma \sqrt{\ln(p)/n}$ (with $\tau=1,2,4,8,16,32$), and $\theta=\mu 