parameter which says that we use $L_1$ penalization when a coefficient is sufficiently small, but the penalty does not increase when the coefficient is larger than a threshold $\theta$. Detailed discussions can be found in [@Zhang09-multistage]. Similar to [@Zhang09-multistage], one can analyze general regularization function $g(u)$. However, some of such functions (such as adaptive Lasso) do not completely remove the bias. Therefore we only analyze the simple function (\[eq:capped-L1-reg\]) in this paper for clarity. While a theoretical justification has been given in [@Zhang09-multistage] for multi-stage convex relaxation, similar procedure has been shown to work well empirically without theoretical justification [@CanWakBoy08; @WipfNaga10]. Moreover, a two-stage version was proposed in [@ZouLi08], which does not remove the bias issue discussed in this paper.

Since the regularizer (\[eq:capped-L1-reg\]) is nonconvex, the resulting optimization problem (\[eq:sparse-reg\]) is a non-convex regularization problem. However the regularizer in (\[eq:capped-L1-reg\]) is continuous and piecewise differentiable, and thus its solution is easier to compute than the $L_0$ regularization method in (\[eq:L0\]). For example, standard numerical techniques such as sub-gradient descent lead to local minimum solutions. Unfortunately, it is difficult to find the global optimum, and it is also difficult to analyze the quality of the local minimum obtained from the 