Phase transitions for high-dimensional joint support recovery

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 set-up 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( umobs, \pdim, \spindex, \overlap) umobs{(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 .