Algorithmic Strategies for Non-convex Optimization in Sparse Learning
published: May 6, 2009, recorded: April 2009, views: 7764
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
We consider optimization formulations with non-convex regularization that are natural for learning 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. 2. Convex relaxation such as L1-regularization that solves the problem under some conditions, but often leads to sub-optimal sparsity in reality.
This talk tries to remedy the above gap between theory and practice by presenting two algorithms for direct optimization of non-convex objectives in sparse learning, for which performance guarantees can be established. The first method is a multi-stage convex relaxation scheme that iteratively refines the L1-regularization. The second approach is a greedy procedure for solving non-convex sparse regularization. We show that under appropriate conditions, both procedures lead to desirable local solutions of sparse non-convex formulations that are superior to the global solution of L1-regularization.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !