Structured Variable Selection with Sparsity-Inducing Norms

Abstract

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 ${\ell }_1$-norm and the group ${\ell }_1$-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.

References in corpus (10)

• Consistency of the group Lasso and multiple kernel learning
• 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
• Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning
• Network Flow Algorithms for Structured Sparsity
• Convex and Network Flow Optimization for Structured Sparsity
• High-Dimensional Non-Linear Variable Selection through Hierarchical Kernel Learning
• Stability Selection

Cited by in corpus (77)

• Structured Compressed Sensing: From Theory to Applications
• Group Sparse Regularization for Deep Neural Networks
• A lasso for hierarchical interactions
• Supersparse Linear Integer Models for Optimized Medical Scoring Systems
• Proximal Methods for Hierarchical Sparse Coding
• Smoothing proximal gradient method for general structured sparse regression
• Group-Sparse Signal Denoising: Non-Convex Regularization, Convex Optimization
• C-HiLasso: A Collaborative Hierarchical Sparse Modeling Framework
• A convex model for non-negative matrix factorization and dimensionality reduction on physical space
• Matrix Completion on Graphs
• Group Lasso with Overlaps: the Latent Group Lasso approach
• Tree-guided group lasso for multi-response regression with structured sparsity, with an application to eQTL mapping
• Convex Tensor Decomposition via Structured Schatten Norm Regularization
• Gains in Power from Structured Two-Sample Tests of Means on Graphs
• More power via graph-structured tests for differential expression of gene networks
• Structured Sparsity and Generalization
• Hierarchical Sparse Modeling: A Choice of Two Group Lasso Formulations
• Online Structured Sparsity-based Moving Object Detection from Satellite Videos
• Convex Relaxation for Combinatorial Penalties
• High Dimensional Forecasting via Interpretable Vector Autoregression
• Tight conditions for consistency of variable selection in the context of high dimensionality
• Supervised Feature Selection in Graphs with Path Coding Penalties and Network Flows
• Learning Model-Based Sparsity via Projected Gradient Descent
• Proximal-Proximal-Gradient Method
• Reliable recovery of hierarchically sparse signals for Gaussian and Kronecker product measurements
• 10,000+ Times Accelerated Robust Subset Selection (ARSS)
• Learning Local Dependence In Ordered Data
• Learning the Structure for Structured Sparsity
• Sparse Subspace Clustering: Algorithm, Theory, and Applications
• Fast ConvNets Using Group-wise Brain Damage
• Exploiting spatial sparsity for multi-wavelength imaging in optical interferometry
• Beyond Moore-Penrose Part I: Generalized Inverses that Minimize Matrix Norms
• Prediction of hierarchical time series using structured regularization and its application to artificial neural networks
• High-dimensional Mixed Graphical Models
• Tight conditions for consistent variable selection in high dimensional nonparametric regression
• Bayesian Structured Sparsity from Gaussian Fields
• Combinatorial Selection and Least Absolute Shrinkage via the CLASH Algorithm
• Screening Rules for Overlapping Group Lasso
• Hierarchical Isometry Properties of Hierarchical Measurements
• Online Learning for Matrix Factorization and Sparse Coding
• A totally unimodular view of structured sparsity
• Stochastic Iterative Hard Thresholding for Graph-structured Sparsity Optimization
• Latent Variable Modeling with Diversity-Inducing Mutual Angular Regularization
• Sample Complexity of Dictionary Learning and other Matrix Factorizations
• Regularizers for Structured Sparsity
• Bayesian group latent factor analysis with structured sparsity
• A Linearly Convergent Majorized ADMM with Indefinite Proximal Terms for Convex Composite Programming and Its Applications
• Multimodal Sparse Bayesian Dictionary Learning
• Multi-scale Mining of fMRI data with Hierarchical Structured Sparsity
• Two-Level Structural Sparsity Regularization for Identifying Lattices and Defects in Noisy Images
• New explicit thresholding/shrinkage formulas for one class of regularization problems with overlapping group sparsity and their applications
• Simultaneous nonparametric regression in RADWT dictionaries
• Convex Banding of the Covariance Matrix
• Tail inverse regression for dimension reduction with extreme response
• A first-order optimization algorithm for statistical learning with hierarchical sparsity structure
• Fully Trainable and Interpretable Non-Local Sparse Models for Image Restoration
• Structure retrieval from 4D-STEM: statistical analysis of potential pitfalls in high-dimensional data
• Stochastic Hard Thresholding Algorithms for AUC Maximization
• Challenges of Feature Selection for Big Data Analytics
• Whole-brain Prediction Analysis with GraphNet
• Learning Undirected Graphical Models with Structure Penalty
• Sparse and redundant signal representations for x-ray computed tomography
• Fitting ARMA Time Series Models without Identification: A Proximal Approach
• Convex Latent Effect Logit Model via Sparse and Low-rank Decomposition
• StatEcoNet: Statistical Ecology Neural Networks for Species Distribution Modeling
• Adaptive matching pursuit for sparse signal recovery
• Multi-dimensional signal approximation with sparse structured priors using split Bregman iterations
• Image Segmentation Using Overlapping Group Sparsity
• A Greedy Homotopy Method for Regression with Nonconvex Constraints
• Efficient Algorithm for Extremely Large Multi-task Regression with Massive Structured Sparsity
• Regularization for Multiple Kernel Learning via Sum-Product Networks
• A Method for Finding Structured Sparse Solutions to Non-negative Least Squares Problems with Applications
• Multi-dimensional sparse structured signal approximation using split Bregman iterations
• Coarse-to-Fine Salient Object Detection with Low-Rank Matrix Recovery
• Sparse Optimization for Green Edge AI Inference
• Exclusive Group Lasso for Structured Variable Selection
• DC algorithms for a class of sparse group ${\ell }_0$ regularized optimization problems