Analysis of Multi-stage Convex Relaxation for Sparse Regularization
Tong Zhang; 11(Mar):1081−1107, 2010.
AbstractWe consider learning formulations with non-convex objective functions that often occur in practical applications. There are two approaches to this problem:
- 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.
- Convex relaxation such as L1-regularization that solves the problem under some conditions. However it often leads to a sub-optimal solution in reality.