High-dimensional support union recovery in multivariate regression

Part of Advances in Neural Information Processing Systems 21 (NIPS 2008)

Bibtex Metadata Paper


Guillaume R. Obozinski, Martin J. Wainwright, Michael Jordan


We study the behavior of block (cid:96)1/(cid:96)2 regularization for multivariate regression, where a K-dimensional response vector is regressed upon a fixed set of p co- variates. The problem of support union recovery is to recover the subset of covariates that are active in at least one of the regression problems. Study- ing this problem under high-dimensional scaling (where the problem parame- ters as well as sample size n tend to infinity simultaneously), our main result is to show that exact recovery is possible once the order parameter given by θ(cid:96)1/(cid:96)2(n, p, s) : = n/[2ψ(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 size of the union of supports, and ψ(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 block (cid:96)1/(cid:96)2 regularization for multivariate regression never harms performance relative to a naive (cid:96)1-approach, and can yield substantial improvements in sample complexity (up to a factor of K) when the regression vectors are suitably orthogonal rela- tive to the design. We complement our theoretical results with simulations that demonstrate the sharpness of the result, even for relatively small problems.