Spotlight
Phase transitions for highdimensional joint support recovery
Sahand N Negahban · Martin J Wainwright
We consider the following instance of transfer learning: given a pair of regression problems, suppose that the regression coefficients share a partially common support, parameterized by the overlap fraction $\overlap$ between the two supports. This setup suggests the use of $1, \infty$regularized linear regression for recovering the support sets of both regression vectors. Our main contribution is to provide a sharp characterization of the sample complexity of this $1,\infty$ relaxation, exactly pinning down the minimal sample size $n$ required for joint support recovery as a function of the model dimension $\pdim$, support size $\spindex$ and overlap $\overlap \in [0,1]$. For measurement matrices drawn from standard Gaussian ensembles, we prove that the joint $1,\infty$regularized method undergoes a phase transition characterized by order parameter $\orpar(\numobs, \pdim, \spindex, \overlap) = \numobs{(4  3 \overlap) s \log(p(2\overlap)s)}$. More precisely, the probability of successfully recovering both supports converges to $1$ for scalings such that $\orpar > 1$, and converges to $0$ to scalings for which $\orpar < 1$. An implication of this threshold is that use of $1, \infty$regularization leads to gains in sample complexity if the overlap parameter is large enough ($\overlap > 2/3$), but performs worse than a naive approach if $\overlap < 2/3$. We illustrate the close agreement between these theoretical predictions, and the actual behavior in simulations. Thus, our results illustrate both the benefits and dangers associated with block$1,\infty$ regularization in highdimensional inference.
Author Information
Sahand N Negahban (University of California, Berkeley)
Martin J Wainwright (UC Berkeley)
More from the Same Authors

2017 Poster: Kernel Feature Selection via Conditional Covariance Minimization »
Jianbo Chen · Mitchell Stern · Martin J Wainwright · Michael Jordan 
2016 Poster: Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences »
Chi Jin · Yuchen Zhang · Sivaraman Balakrishnan · Martin J Wainwright · Michael Jordan 
2012 Poster: Iterative ranking from pairwise comparisons »
Sahand N Negahban · Sewoong Oh · Devavrat Shah 
2012 Poster: Privacy Aware Learning »
John Duchi · Michael Jordan · Martin J Wainwright 
2012 Poster: CommunicationEfficient Algorithms for Statistical Optimization »
Yuchen Zhang · John Duchi · Martin J Wainwright 
2012 Poster: No voodoo here! Learning discrete graphical models via inverse covariance estimation »
PoLing Loh · Martin J Wainwright 
2012 Oral: No voodoo here! Learning discrete graphical models via inverse covariance estimation »
PoLing Loh · Martin J Wainwright 
2012 Spotlight: Iterative ranking from pairwise comparisons »
Sahand N Negahban · Sewoong Oh · Devavrat Shah 
2012 Oral: Privacy Aware Learning »
John Duchi · Michael Jordan · Martin J Wainwright 
2012 Poster: Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions »
Alekh Agarwal · Sahand N Negahban · Martin J Wainwright 
2012 Poster: Finite Sample Convergence Rates of ZeroOrder Stochastic Optimization Methods »
John Duchi · Michael Jordan · Martin J Wainwright · Andre Wibisono 
2011 Poster: A More Powerful TwoSample Test in High Dimensions using Random Projection »
Miles Lopes · Laurent Jacob · Martin J Wainwright 
2011 Poster: Highdimensional regression with noisy and missing data: Provable guarantees with nonconvexity »
PoLing Loh · Martin J Wainwright 
2011 Oral: Highdimensional regression with noisy and missing data: Provable guarantees with nonconvexity »
PoLing Loh · Martin J Wainwright 
2010 Spotlight: Distributed Dual Averaging In Networks »
John Duchi · Alekh Agarwal · Martin J Wainwright 
2010 Poster: Distributed Dual Averaging In Networks »
John Duchi · Alekh Agarwal · Martin J Wainwright 
2010 Oral: Fast global convergence rates of gradient methods for highdimensional statistical recovery »
Alekh Agarwal · Sahand N Negahban · Martin J Wainwright 
2010 Poster: Fast global convergence rates of gradient methods for highdimensional statistical recovery »
Alekh Agarwal · Sahand N Negahban · Martin J Wainwright 
2009 Poster: Informationtheoretic lower bounds on the oracle complexity of convex optimization »
Alekh Agarwal · Peter Bartlett · Pradeep Ravikumar · Martin J Wainwright 
2009 Poster: Lower bounds on minimax rates for nonparametric regression with additive sparsity and smoothness »
Garvesh Raskutti · Martin J Wainwright · Bin Yu 
2009 Spotlight: Lower bounds on minimax rates for nonparametric regression with additive sparsity and smoothness »
Garvesh Raskutti · Martin J Wainwright · Bin Yu 
2009 Spotlight: Informationtheoretic lower bounds on the oracle complexity of convex optimization »
Alekh Agarwal · Peter Bartlett · Pradeep Ravikumar · Martin J Wainwright 
2009 Poster: A unified framework for highdimensional analysis of $M$estimators with decomposable regularizers »
Sahand N Negahban · Pradeep Ravikumar · Martin J Wainwright · Bin Yu 
2009 Oral: A unified framework for highdimensional analysis of $M$estimators with decomposable regularizers »
Sahand N Negahban · Pradeep Ravikumar · Martin J Wainwright · Bin Yu 
2008 Poster: Highdimensional union support recovery in multivariate regression »
Guillaume R Obozinski · Martin J Wainwright · Michael Jordan 
2008 Poster: Phase transitions for highdimensional joint support recovery »
Sahand N Negahban · Martin J Wainwright 
2008 Spotlight: Highdimensional union support recovery in multivariate regression »
Guillaume R Obozinski · Martin J Wainwright · Michael Jordan 
2008 Poster: Model Selection in Gaussian Graphical Models: HighDimensional Consistency of \ell_1regularizedMLE »
Pradeep Ravikumar · Garvesh Raskutti · Martin J Wainwright · Bin Yu 
2007 Spotlight: Estimating divergence functionals and the likelihood ratio by penalized convex risk minimization »
XuanLong Nguyen · Martin J Wainwright · Michael Jordan 
2007 Poster: Estimating divergence functionals and the likelihood ratio by penalized convex risk minimization »
XuanLong Nguyen · Martin J Wainwright · Michael Jordan 
2007 Poster: Loop Series and Bethe Variational Bounds in Attractive Graphical Models »
Erik Sudderth · Martin J Wainwright · Alan S Willsky 
2006 Poster: Inferring Graphical Model Structure using $\ell_1$Regularized PseudoLikelihood »
Martin J Wainwright · Pradeep Ravikumar · John Lafferty 
2006 Spotlight: Inferring Graphical Model Structure using $\ell_1$Regularized PseudoLikelihood »
Martin J Wainwright · Pradeep Ravikumar · John Lafferty