Union support recovery in high-dimensional multivariate regression

By Guillaume Obozinski, Martin J. Wainwright, Michael I. Jordan. 2008

322 citations recorded by the source corpus.

In the problem of multivariate regression, a K-dimensional response vector is regressed upon a common set of p covariates, with a matrix B* isin RopfptimesK of regression coefficients. We study the behavior of the group Lasso using lscr1/lscr2 regularization for the union support problem, meaning that the set of s rows for which B* is non-zero is recovered exactly. Studying this problem under high-dimensional scaling, we show that group Lasso recovers the exact row pattern with high probability over the random design and noise for scalings of (n, p, s) such that the sample complexity parameter given by thetas(n, p, s) := n/[2psi(B*) log(p - s)] exceeds a critical threshold. Here n is the sample size, p is the ambient dimension of the regression model, s is the number of non-zero rows, and psi(B*) is a sparsity-overlap function that measures a combination of the sparsities and overlaps of the K-regression coefficient vectors that constitute the model. This sparsity-overlap function reveals that, if the design is uncorrelated on the active rows, block lscr1/lscr2 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 regression vectors are suitably orthogonal. For more general designs, it is possible for the ordinary Lasso to outperform the group Lasso.

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

In Statistics and Probability

Citations in the corpus

A Survey on Multi-Task Learning (2017, background): “Several studies [230], [231], [232] investigate conditions to well recover true features for multi-task feature selection methods.”
Robust Lasso With Missing and Grossly Corrupted Observations (2011, neutral): “[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15]).”
Group Lasso for high dimensional sparse quantile regression models (2011, methodology): “Bach (2008), Nardi and Rinardo (2008), Huang and Zhang (2010), Wei and Zhang (2010), Obozinski et al. (2010) Lounici et al. (2010) studied the statistical properties of the group Lasso estimator for linear regression models.”
On Learning Discrete Graphical Models using Group-Sparse Regularization (2011, methodology): “We now describe the graph selection procedure we study for the m-ary pairwise model.”
Precise Undersampling Theorems (2010, background): “In the noisy case, Wainwright [22] and Obozinski et al. [ 41 ] derive formal expressions for various algorithms which match experiments, however, for the support reconstruction property, not the recovery property.)”
Learning with structured sparsity (2009, background): “In [19], the authors consider a special case of group Lasso in the multi-task learning scenario, and show that the number of samples required for recovering the exact support set is smaller for group Lasso under appropriate conditions.”
The Benefit of Group Sparsity (2009, background): “The work most related to ours is [7], where the authors considered a special case of group Lasso in the multi-task learning scenario, and showed that the number of samples required for recovering the exact support set is smaller for group Lasso under appropriate conditions.”
Taking Advantage of Sparsity in Multi-Task Learning (2009, background): “Examples in which this estimation problem is relevant range from multi-task learning [1, 8, 20, 24] and conjoint analysis (see, for example, [13, 18] and references therein) to longitudinal data analysis [10] as well as the analysis of panel data [14, 28], among others.”