Year: 2010, Volume: 11, Issue: 35, Pages: 1081−1107
We 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.