Multi-stage Convex Relaxation for Learning with Sparse Regularization

We study learning formulations with non-convex regularizaton that are natural for sparse linear models. There are two approaches to this problem: (1) Heuristic methods such as gradient descent that only find a local minimum. A drawback of this approach is the lack of theoretical guarantee showing that the local minimum gives a good solution. However it often leads to sub-optimal sparsity in reality. This paper tries to remedy the above gap between theory and practice.