Network Flow Algorithms for Structured Sparsity

By Julien Mairal, Rodolphe Jenatton, Guillaume Obozinski, Francis R. Bach. 2010

175 citations recorded by the source corpus.

We consider a class of learning problems that involve a structured sparsity-inducing norm defined as the sum of l∞-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.

Subfields: Computational Mechanics, Management Science and Operations Research, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

Regularizing Text Categorization with Clusters of Words (2016, background): “, through sets, trees (Kim and Xing, 2010; Liu and Ye, 2010; Mairal et al., 2010) or graphs (Jenatton et al.”
Optimization with Sparsity-Inducing Penalties (2011, background): “Indeed, as shown by [76], there exists a dual relation between such an operator and a quadratic min-cost flow problem on a particular graph, which can be tackled using network flow optimization techniques.”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “3) lead to applications to hierarchical dictionary learning and topic models [76], structured priors for image denoising [76, 77], background subtraction [95], and bioinformatics [71, 82].”
Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization (2013, methodology): “Its proximal operator can be computed efficiently [20], and it is thus easy to use the surrogates (5).”
Loss Functions for Top-k Error: Analysis and Insights (2015, methodology): “[33], denoted LR (SPAMS).”
Structured Sparsity in Structured Prediction (2011, methodology): “The tree-structured case has been addressed by Kim and Xing (2010), Liu and Ye (2010) and Mairal et al. (2010), along with L ∞ , 1 and L 2 , 1 regularization.”
Efficient Methods for Overlapping Group Lasso (2011, background): “Several recent works [6], [7], [8], [9], [10], [11], [12] have studied the overlapping group Lasso, where groups of features are given, potentially with overlaps between the groups.”
Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers (2011, unknown): “This can be extended further to handle overlapping groups, which is often useful in bioinformatics and other applications [181, 118].”
Moving Object Detection by Detecting Contiguous Outliers in the Low-Rank Representation (2011, methodology): “In the literatures mentioned above, Φ is fixed to be the training sequence [41] or previous frames on which background subtraction has been performed [40].”
Sparse Modeling for Image and Vision Processing (2014, methodology): “The implementation of the SPAMS software contains such variants, which have proven to be important in practice [see Mairal et al., 2010a, for additional discussions].”
Structured Variable Selection with Sparsity-Inducing Norms (2009, background): “…on the structure of the sparse representation is available, e.g., for multiple kernel learning (Micchelli and Pontil, 2006), multi-task learning (Argyriou et al., 2008; Obozinski et al., 2009; Kim and Xing, 2009) and sparse matrix factorization problems (Mairal et al., 2010; Jenatton et al., 2010).”
Proximal Methods for Hierarchical Sparse Coding (2010, background): “Note that this paper extends a shorter version published in the proceedings of the international conference of machine learning (Jenatton et al., 2010).”
Video Processing From Electro-Optical Sensors for Object Detection and Tracking in a Maritime Environment: A Survey (2016, unknown): “age reconstruction problem [145], [166], [167], [168], [169].”
Structured sparsity through convex optimization (2011, background): “…non-convex global formulations (see, e.g., Zou, Hastie and Tibshirani, 2006; Moghaddam, Weiss and Avidan, 2006; Aharon, Elad and Bruckstein, 2006; Mairal et al., 2010) which estimate simultaneously all principal components, typically do not require the orthogonality of the components, and are…”