Convex and Network Flow Optimization for Structured Sparsity

Abstract

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.

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

References in corpus (10)

• The composite absolute penalties family for grouped and hierarchical variable selection
• Structured Sparse Principal Component Analysis
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Proximal Methods for Hierarchical Sparse Coding
• Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
• Network Flow Algorithms for Structured Sparsity
• Structured sparsity-inducing norms through submodular functions
• High-Dimensional Non-Linear Variable Selection through Hierarchical Kernel Learning
• Structured Sparsity via Alternating Direction Methods
• CUR from a Sparse Optimization Viewpoint

Cited by in corpus (15)

• Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
• Network Flow Algorithms for Structured Sparsity
• Convex Tensor Decomposition via Structured Schatten Norm Regularization
• Forward - Backward Greedy Algorithms for Atomic Norm Regularization
• Online Structured Sparsity-based Moving Object Detection from Satellite Videos
• Supervised Feature Selection in Graphs with Path Coding Penalties and Network Flows
• Learning Heteroscedastic Models by Convex Programming under Group Sparsity
• Collaborative Filtering via Group-Structured Dictionary Learning
• Stable Feature Selection from Brain sMRI
• Learning Hierarchical Interactions at Scale: A Convex Optimization Approach
• A first-order optimization algorithm for statistical learning with hierarchical sparsity structure
• On a reduction for a class of resource allocation problems
• Multi-modal Image Registration for Correlative Microscopy
• Estimating Piecewise Monotone Signals
• Efficient Algorithm for Extremely Large Multi-task Regression with Massive Structured Sparsity