Convex and Network Flow Optimization for Structured Sparsity

Details Convex and Network Flow Optimization for Structured Sparsity Convex and Network Flow Optimization for Structured Sparsity

2011-04-11

arxiv.org/abs/1104.1872v3

Journal of Machine Learning Research 12 (2011) 2681?2720

Mathematics

Optimization and Control

to appear in the Journal of Machine Learning Research (JMLR)

Scientific paper

We consider a class of learning problems regularized by a structured sparsity-inducing norm defined as the sum of l_2- or l_infinity-norms over groups of variables. Whereas much effort has been put in developing fast optimization techniques when the groups are disjoint or embedded in a hierarchy, we address here the case of general overlapping groups. To this end, we present two different strategies: On the one hand, we show that the proximal operator associated with a sum of l_infinity-norms can be computed exactly in polynomial time by solving a quadratic min-cost flow problem, allowing the use of accelerated proximal gradient methods. On the other hand, we use proximal splitting techniques, and address an equivalent formulation with non-overlapping groups, but in higher dimension and with additional constraints. We propose efficient and scalable algorithms exploiting these two strategies, which are significantly faster than alternative approaches. We illustrate these methods with several problems such as CUR matrix factorization, multi-task learning of tree-structured dictionaries, background subtraction in video sequences, image denoising with wavelets, and topographic dictionary learning of natural image patches.

Affiliated with

Also associated with

No associations

Rating

Convex and Network Flow Optimization for Structured Sparsity 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 Convex and Network Flow Optimization for Structured Sparsity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convex and Network Flow Optimization for Structured Sparsity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-58259