Network Flow Algorithms for Structured Sparsity

Abstract

We consider a class of learning problems that involve a structured sparsity-inducing norm defined as the sum of ${\ell }_{\infty }$-norms over groups of variables. Whereas a lot of effort has been put in developing fast optimization methods when the groups are disjoint or embedded in a specific hierarchical structure, we address here the case of general overlapping groups. To this end, we show that the corresponding optimization problem is related to network flow optimization. More precisely, the proximal problem associated with the norm we consider is dual to a quadratic min-cost flow problem. We propose an efficient procedure which computes its solution exactly in polynomial time. Our algorithm scales up to millions of variables, and opens up a whole new range of applications for structured sparse models. We present several experiments on image and video data, demonstrating the applicability and scalability of our approach for various problems.

accepted for publication in Adv. Neural Information Processing Systems, 2010

References in corpus (20)

• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Simultaneous analysis of Lasso and Dantzig selector
• 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
• Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning
• Convex and Network Flow Optimization for Structured Sparsity
• Structured sparsity-inducing norms through submodular functions
• Fast Overlapping Group Lasso
• CUR from a Sparse Optimization Viewpoint
• The Benefit of Group Sparsity

Cited by in corpus (16)

• Structured Variable Selection with Sparsity-Inducing Norms
• Proximal Methods for Hierarchical Sparse Coding
• Smoothing proximal gradient method for general structured sparse regression
• A convex model for non-negative matrix factorization and dimensionality reduction on physical space
• Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization
• Convex and Network Flow Optimization for Structured Sparsity
• Structured sparsity-inducing norms through submodular functions
• Online Structured Sparsity-based Moving Object Detection from Satellite Videos
• PySAP: Python Sparse Data Analysis Package for Multidisciplinary Image Processing
• Convex Analysis and Optimization with Submodular Functions: a Tutorial
• On the Duality between Network Flows and Network Lasso
• Collaborative Filtering via Group-Structured Dictionary Learning
• Solving OSCAR regularization problems by proximal splitting algorithms
• Regularized Loss Minimizers with Local Data Perturbation: Consistency and Data Irrecoverability
• Moving Object Detection under Discontinuous Change in Illumination Using Tensor Low-Rank and Invariant Sparse Decomposition
• Efficient Algorithm for Extremely Large Multi-task Regression with Massive Structured Sparsity