Structured Sparsity via Alternating Direction Methods

Details Structured Sparsity via Alternating Direction Methods Structured Sparsity via Alternating Direction Methods

2011-05-04

arxiv.org/abs/1105.0728v2

Mathematics

Optimization and Control

Scientific paper

We consider a class of sparse learning problems in high dimensional feature space regularized by a structured sparsity-inducing norm which incorporates prior knowledge of the group structure of the features. Such problems often pose a considerable challenge to optimization algorithms due to the non-smoothness and non-separability of the regularization term. In this paper, we focus on two commonly adopted sparsity-inducing regularization terms, the overlapping Group Lasso penalty $l_1/l_2$-norm and the $l_1/l_\infty$-norm. We propose a unified framework based on the augmented Lagrangian method, under which problems with both types of regularization and their variants can be efficiently solved. As the core building-block of this framework, we develop new algorithms using an alternating partial-linearization/splitting technique, and we prove that the accelerated versions of these algorithms require $O(\frac{1}{\sqrt{\epsilon}})$ iterations to obtain an $\epsilon$-optimal solution. To demonstrate the efficiency and relevance of our algorithms, we test them on a collection of data sets and apply them to two real-world problems to compare the relative merits of the two norms.

Affiliated with

Also associated with

No associations

Rating

Structured Sparsity via Alternating Direction Methods does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Structured Sparsity via Alternating Direction Methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Structured Sparsity via Alternating Direction Methods will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-688948