Structured Variable Selection with Sparsity-Inducing Norms

By Rodolphe Jenatton, Jean-Yves Audibert, Francis R. Bach. 2009

630 citations recorded by the source corpus.

We consider the empirical risk minimization problem for linear supervised learning, with regularization by structured sparsity-inducing norms. These are defined as sums of Euclidean norms on certain subsets of variables, extending the usual l1-norm and the group l1-norm by allowing the subsets to overlap. This leads to a specific set of allowed nonzero patterns for the solutions of such problems. We first explore the relationship between the groups defining the norm and the resulting nonzero patterns, providing both forward and backward algorithms to go back and forth from groups to patterns. This allows the design of norms adapted to specific prior knowledge expressed in terms of nonzero patterns. We also present an efficient active set algorithm, and analyze the consistency of variable selection for least-squares linear regression in low and high-dimensional settings.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, 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 Computer Vision and Pattern Recognition

In Statistics and Probability

Citations in the corpus

Supersparse linear integer models for optimized medical scoring systems (2015, methodology): “This presents a practical alternative to create classification models that obey structured sparsity constraints (see e.g., Jenatton et al., 2011) or hierarchical constraints (see e.g., Bien et al., 2013).”
Regularizing Text Categorization with Clusters of Words (2016, background): “To do so, they proposed to regularize with the L1,2 norm of the feature weight vector: Ω(θ) = λ ∑ g λg‖θg‖2 (9) where θg is the subset of feature weights restricted to group g. Note that the groups can be overlapping (Jacob et al., 2009; Schmidt and Murphy, 2010; Jenatton et al., 2011; Yuan et al., ”
Fast ConvNets Using Group-Wise Brain Damage (2015, methodology): “A classical way to achieve this is through the use of group-sparsity regularization [47, 41, 24].”
Deep Learning of Representations: Looking Forward (2013, background): “Sparse coding is not actually very good as a generative model, but has been very successful for unsupervised feature learning (Raina et al., 2007; Coates and Ng, 2011; Yu et al., 2011; Grosse et al., 2007; Jenatton et al., 2009; Bach et al., 2011).”
Optimization with Sparsity-Inducing Penalties (2011, background): “Note that here the weights dg should not be taken equal to one (see, [56] for more details).”
Bayesian group factor analysis with structured sparsity (2016, methodology): “…structure of Λ in GFA models belongs to a general class of structured sparsity methods that has drawn attention recently (Zou and Hastie, 2005; Yuan and Lin, 2006; Jenatton et al., 2011, 2010; Kowalski, 2009; Kowalski and Torrésani, 2009; Zhao et al., 2009; Huang et al., 2011; Jia et al., 2010).”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “For simplicity, we have assumed invertibility of X⊤X, which forbids the high-dimensional situation p > n, but we could extend to the type of assumptions used in [111] or to more general smooth losses.”
Handbook of Big Data (2016, neutral): “A number of extensions to the group lasso have been proposed, for instance to accommodate overlapping groups (Jacob et al., 2009; Jenatton et al., 2011) and to induce sparsity within the groups (Simon et al.”
Network Flow Algorithms for Structured Sparsity (2010, positive): “The latter setting has first been considered for hierarchies [7, 11, 15], and then extended to general group structures [5].”
A LASSO FOR HIERARCHICAL INTERACTIONS (2012, methodology): “Zhao, Rocha and Yu (2009) [and, relatedly, Jenatton, Audibert and Bach (2011)] describe composite absolute penalties (CAP), a very broad class of penalties that can achieve group and hierarchical sparsity.”
Super-Resolution With Sparse Mixing Estimators (2010, methodology): “Structured approximation algorithms use such pri or information to restrict the set of possible approximation spaces [29], [32].”
Sparse Subspace Clustering: Algorithm, Theory, and Applications (2013, background): “Hence, minimizing (28) corresponds to minimizing the number of nonzero rows of C [61], [62], [63], i.”
Weakly decomposable regularization penalties and structured sparsity (2012, background): “…paper, we are primarily interested in extensions of the `1-penalty to general structured sparsity penalties such as the group Lasso introduced by Yuan & Lin (2006) and further structured versions given by Zhao et al. (2009), Jacob et al. (2009), Jenatton et al. (2011) and Micchelli et al. 2010.”
Proximal Methods for Hierarchical Sparse Coding (2010, methodology): “As analyzed by Zhao et al. (2009) and Jenatton et al. (2009), when penalizing by W , some of the vectors a | g are set to zero for some g ∈ G .”
Sparse Modeling for Image and Vision Processing (2014, methodology): “This notion is called structured sparsity and has been introduced under a large number of different point of views [Zhao et al., 2009, Jacob et al., 2009, Jenatton et al., 2011a, Baraniuk et al., 2010, Huang et al., 2011].”