Support union recovery in high-dimensional multivariate regression

Abstract

In multivariate regression, a $K$-dimensional response vector is regressed upon a common set of $p$ covariates, with a matrix $B^{\ast }\in {\mathbb{R}}^{p\times K}$ of regression coefficients. We study the behavior of the multivariate group Lasso, in which block regularization based on the ${\ell }_1/{\ell }_2$ norm is used for support union recovery, or recovery of the set of $s$ rows for which $B^{\ast }$ is nonzero. Under high-dimensional scaling, we show that the multivariate group Lasso exhibits a threshold for the recovery of the exact row pattern with high probability over the random design and noise that is specified by the sample complexity parameter $\theta (n,p,s):=n/[2\psi (B^{\ast })\log (p-s)]$. Here $n$ is the sample size, and $\psi (B^{\ast })$ is a sparsity-overlap function measuring a combination of the sparsities and overlaps of the $K$-regression coefficient vectors that constitute the model. We prove that the multivariate group Lasso succeeds for problem sequences $(n,p,s)$ such that $\theta (n,p,s)$ exceeds a critical level ${\theta }_u$, and fails for sequences such that $\theta (n,p,s)$ lies below a critical level ${\theta }_{\ell }$. For the special case of the standard Gaussian ensemble, we show that ${\theta }_{\ell }={\theta }_u$ so that the characterization is sharp. The sparsity-overlap function $\psi (B^{\ast })$ reveals that, if the design is uncorrelated on the active rows, ${\ell }_1/{\ell }_2$ regularization for multivariate regression never harms performance relative to an ordinary Lasso approach and can yield substantial improvements in sample complexity (up to a factor of $K$) when the coefficient vectors are suitably orthogonal. For more general designs, it is possible for the ordinary Lasso to outperform the multivariate group Lasso. We complement our analysis with simulations that demonstrate the sharpness of our theoretical results, even for relatively small problems.

Published in at http://dx.doi.org/10.1214/09-AOS776 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (9)

• High-dimensional graphs and variable selection with the Lasso
• Simultaneous analysis of Lasso and Dantzig selector
• Consistency of the group Lasso and multiple kernel learning
• The composite absolute penalties family for grouped and hierarchical variable selection
• Asymptotic properties of bridge estimators in sparse high-dimensional regression models
• Lasso-type recovery of sparse representations for high-dimensional data
• The Benefit of Group Sparsity
• Sparse Additive Models
• On the ${\ell }_1-{\ell }_q$ Regularized Regression

Cited by in corpus (67)

• A Survey on Multi-Task Learning
• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• Robust Inference on Average Treatment Effects with Possibly More Covariates than Observations
• A Selective Review of Group Selection in High-Dimensional Models
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Subspace Methods for Joint Sparse Recovery
• Multi-Stage Multi-Task Feature Learning
• Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses
• Simultaneous Variable and Covariance Selection with the Multivariate Spike-and-Slab Lasso
• On the Theory of Transfer Learning: The Importance of Task Diversity
• OMP Based Joint Sparsity Pattern Recovery Under Communication Constraints
• The Landmark Selection Method for Multiple Output Prediction
• Union Support Recovery in Multi-task Learning
• Tight conditions for consistency of variable selection in the context of high dimensionality
• Learning the Conditional Independence Structure of Stationary Time Series: A Multitask Learning Approach
• Improving Noise Robustness in Subspace-based Joint Sparse Recovery
• Adaptive Lasso and group-Lasso for functional Poisson regression
• Exponential Family Matrix Completion under Structural Constraints
• Improving M-SBL for Joint Sparse Recovery using a Subspace Penalty
• Sparse quadratic classification rules via linear dimension reduction
• Conditioning of Random Block Subdictionaries with Applications to Block-Sparse Recovery and Regression
• Learning Heteroscedastic Models by Convex Programming under Group Sparsity
• Tight conditions for consistent variable selection in high dimensional nonparametric regression
• Accuracy guaranties for ${\ell }_1$ recovery of block-sparse signals
• Asymptotic Analysis of Complex LASSO via Complex Approximate Message Passing (CAMP)
• Optimal variable selection in multi-group sparse discriminant analysis
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• A Likelihood Ratio Framework for High Dimensional Semiparametric Regression
• Two-stage Sampling, Prediction and Adaptive Regression via Correlation Screening (SPARCS)
• Maximin Analysis of Message Passing Algorithms for Recovering Block Sparse Signals
• Joint Estimation and Inference for Data Integration Problems based on Multiple Multi-layered Gaussian Graphical Models
• The geometry of least squares in the 21st century
• Improved Support Recovery Guarantees for the Group Lasso With Applications to Structural Health Monitoring
• Distributed Multitask Learning
• Prototype selection for parameter estimation in complex models
• High-Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition
• A Max-Product EM Algorithm for Reconstructing Markov-tree Sparse Signals from Compressive Samples
• An explicit mean-covariance parameterization for multivariate response linear regression
• Interaction pursuit in high-dimensional multi-response regression via distance correlation
• Multiple Support Recovery Using Very Few Measurements Per Sample
• Collaborative Multi-sensor Classification via Sparsity-based Representation
• The EAS approach to variable selection for multivariate response data in high-dimensional settings
• Simultaneous Grouping and Denoising via Sparse Convex Wavelet Clustering
• Structured Regularization for conditional Gaussian Graphical Models
• High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms
• Calibrated Multivariate Regression with Application to Neural Semantic Basis Discovery
• Group Model Selection Using Marginal Correlations: The Good, the Bad and the Ugly
• Regularization for supervised learning via the "hubNet" procedure
• Joint association and classification analysis of multi-view data
• Chi-square and normal inference in high-dimensional multi-task regression
• Nonconvex penalized multitask regression using data depth-based penalties
• Grouped Variable Selection via Nested Spike and Slab Priors
• Multiple Regression for Matrix and Vector Predictors: Models, Theory, Algorithms, and Beyond
• Interaction Pursuit Biconvex Optimization
• A Multiple Hypothesis Testing Approach to Low-Complexity Subspace Unmixing
• The Product of Gaussian Matrices is Close to Gaussian
• Support Recovery of Sparse Signals in the Presence of Multiple Measurement Vectors
• Robust Low-Complexity Randomized Methods for Locating Outliers in Large Matrices
• Ultra-high Dimensional Multiple Output Learning With Simultaneous Orthogonal Matching Pursuit: A Sure Screening Approach
• Generalized Co-sparse Factor Regression
• A New Greedy Algorithm for Multiple Sparse Regression
• Regularized Loss Minimizers with Local Data Perturbation: Consistency and Data Irrecoverability
• High Dimensional Multivariate Regression and Precision Matrix Estimation via Nonconvex Optimization
• Sparse Signal Recovery in the Presence of Intra-Vector and Inter-Vector Correlation
• Jointly Sparse Signal Recovery via Deep Auto-Encoder and Parallel Coordinate Descent Unrolling
• Fine-Gray competing risks model with high-dimensional covariates: estimation and Inference
• Robust Lasso with missing and grossly corrupted observations