Structured sparsity through convex optimization

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

345 citations recorded by the source corpus.

Sparse estimation methods are aimed at using or obtaining parsimonious representations of data or models. While naturally cast as a combinatorial optimization problem, variable or feature selection admits a convex relaxation through the regularization by the $\ell_1$-norm. In this paper, we consider situations where we are not only interested in sparsity, but where some structural prior knowledge is available as well. We show that the $\ell_1$-norm can then be extended to structured norms built on either disjoint or overlapping groups of variables, leading to a flexible framework that can deal with various structures. We present applications to unsupervised learning, for structured sparse principal component analysis and hierarchical dictionary learning, and to supervised learning in the context of non-linear variable selection.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Disentangling Factors of Variation via Generative Entangling (2012, background): “…tensor, our approach employs highly structured and sparse connections between latent variables (e.g. g ik is not interact with or h jk (cid:48) for k (cid:48) (cid:54) = k ), reminiscent of recent work on structured sparse coding (Gregor et al., 2011) and structured l 1-norms (Bach et al., 2011).”
Deep Learning of Representations: Looking Forward (2013, background): “t from the usual deﬁnition of score in statistics , where the derivative is with respect to the parameters 7 To deﬁne energy, we write probability as the normalized exponential of minus the energy. 5 Bach et al., 2011). See Bengio et al. (2013c) for a brief overview in the context of deep learning, ”
Movement Pruning: Adaptive Sparsity by Fine-Tuning (2020, background): “In future work, it would also be interesting to leverage group-sparsity inducing penalties [Bach et al., 2011] to remove entire columns or filters.”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “, [210, 112, 104, 108, 119, 114, 140, 130], a review in [11, 12] and Chapter 6 for various examples).”
A LASSO FOR HIERARCHICAL INTERACTIONS (2012, methodology): “For example, Zhao, Rocha and Yu (2009) consider the penalty Likewise, the framework of Bach et al. (2012) if specialized to this paper’s focus would lead to a penalty of the form for some q > 1 and d j > 0.”
Structure Regularization for Structured Prediction (2014, methodology): “red classiﬁcation models [15, 6] and structured prediction sce narios [20, 14], via adopting mixed norm regularization [18], Group Lasso [32], posterior regularization [8], and a string of variations [2, 17, 9]. Compared with those prior work, we emphasize that our proposal on tag structure regulari”
Machine Learning for Survival Analysis (2019, methodology): “This is also supported by the effectiveness of structured sparsity-based regularization methods in regression (Bach et al. 2012).”
Traffic Sign Recognition via Multi-Modal Tree-Structure Embedded Multi-Task Learning (2017, methodology): “Combining (5) and (16) we obtain the following form: qL(Wt) = argmin W ( 1 2 ‖W −V‖2F + λ̃1‖W‖T ) = arg min W1,...,WD D∑ i=1 ( 1 2 ‖Wi −Vi‖2F + λ̃1‖Wi‖T ) (17) where Wi, Vi denotes the ith row of the matrix W, V respectively.”
Unsupervised Feature Learning and Deep Learning: A Review and New Perspectives (2012, background): “Different group sparsity patterns can incorporate different forms of prior knowledge (Kavukcuoglu et al. , 2009; Jenatton et al. , 2009; Bach et al. , 2011; Gregor et al. , 2011a).”
Feature Selection Based on Structured Sparsity: A Comprehensive Study (2017, background): “structured sparsity-induced [28]–[30] feature selection algorithms considering the structure of features have shown promising results in many practical applications and have received more and more attention.”
Hierarchical Sparse Modeling: A Choice of Two Group Lasso Formulations (2015, background): “While a modification of GL is possible to curb this over-aggressiveness of GL (Jenatton, Audibert and Bach, 2011, Bach et al., 2012, Bien, Bunea and Xiao, 2016), doing so complicates the computation and makes for a more difficult to describe estimator.”
Learning Adaptive Discriminative Correlation Filters via Temporal Consistency Preserving Spatial Feature Selection for Robust Visual Object Tracking (2018, background): “(9), we introduce slack variables to construct the following objective based on convex optimization [68]:”
Representation Learning: A Review and New Perspectives (2012, methodology): “It has been used to model natural textures (Kivinen and Williams, 2012) in a tiled-convolution configuration (see section 11.2).”
Machine Learning for Survival Analysis: A Survey (2017, methodology): “This is also supported by the effectiveness of structured sparsity based regularization methods in regression [Bach et al. 2012].”
Visual classification with multi-task joint sparse representation (2010, methodology): “In this paper, motivated by the success of multitask sparse linear regression models [10][15][25], we investigate into the problem of multi-task joint sparse representation along with its applications in visual recognition.”
Sparse Modeling for Image and Vision Processing (2014, methodology): “Solving (2.11) is easy with any standard method adapted to large-scale `1-regularized convex problems [see Bach et al., 2012a, for a review].”