Source-linked AI summary
Support union recovery in high-dimensional multivariate regression
Guillaume Obozinski, Martin J. Wainwright, Michael I. Jordan
TL;DR
The paper studies support-union recovery in high-dimensional multivariate regression, where related responses may share relevant covariates. It analyzes multivariate group Lasso under random designs and shows that recovery probability is governed by a sparsity- and overlap-dependent sample-complexity threshold.
Problem
High-dimensional multivariate regression may have partially shared sparsity patterns, motivating recovery of the union of covariate supports rather than each response's support separately.
Method
The paper studies the probability of correct row selection by multivariate group Lasso for Gaussian random designs and noise, using a sample-complexity parameter involving n, p, s, and the sparsity-overlap function ψ(·).
Results
Recovery succeeds above an upper threshold and fails below a lower threshold determined by the design covariance matrix and the sample-complexity parameter.
Takeaways & Limitations
The analysis characterizes when block regularization consistently recovers the relevant rows in high-dimensional multivariate regression.
Takeaways & Limitations
The analysis assumes hard sparsity and exact support recovery, leaving soft-sparsity models and alternative losses such as prediction error for future work.
Abstract
from arXiv · showhide
In multivariate regression, a $K$-dimensional response vector is regressed upon a common set of $p$ covariates, with a matrix $B^*\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^*$ 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 $θ(n,p,s):=n/[2ψ(B^*)\log(p-s)]$. Here $n$ is the sample size, and $ψ(B^*)$ 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 $θ(n,p,s)$ exceeds a critical level $θ_u$, and fails for sequences such that $θ(n,p,s)$ lies below a critical level $θ_{\ell}$. For the special case of the standard Gaussian ensemble, we show that $θ_{\ell}=θ_u$ so that the characterization is sharp. The sparsity-overlap function $ψ(B^*)$ 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.
1. Introduction.
The paper studies row-support recovery in high-dimensional multivariate regression using ℓ1/ℓ2 block regularization, and characterizes when the multivariate group Lasso succeeds or fails. Its sample-complexity analysis captures how design structure, sparsity, and overlap among regressions affect performance relative to separate Lasso fits.
- Problem setting: Multivariate regression uses a shared design matrix for K responses, represented by a p × K coefficient matrix B∗.
- Problem setting: The support-union objective selects the rows of B∗ that are nonzero for at least one response, rather than estimating each individual support separately.When the recovered union is small, individual supports can subsequently be estimated by least squares and thresholding.
- Method: The multivariate group Lasso applies ℓ1/ℓ2 block regularization to make row selection computationally tractable while exploiting partially shared sparsity patterns.The paper analyzes this convex relaxation instead of the computationally intractable direct row-selection problem.
- Main results: The sample-complexity parameter n/[2ψ(B∗)log(p −s)] governs consistent row selection, with ψ(B∗) measuring sparsity and overlap across regression coefficient vectors.The parameter reflects the rate at which n must grow with p and the sparsity structure.
- Main results: Above a critical threshold θu, correct row-selection probability converges to one; below θℓ, the multivariate group Lasso fails with high probability.
- Main results: For suitably orthogonal coefficient vectors under standard Gaussian designs, ℓ1/ℓ2 regularization can reduce sample complexity by a factor of K, whereas correlated designs can favor separate ordinary Lasso fits.In the orthogonal case, ψ(B∗) = s/K; for suitably correlated designs, the group-Lasso sample complexity can be larger than the ordinary Lasso’s.
2. Main results and some consequences.
The multivariate group Lasso has high-dimensional guarantees for exact row-support recovery, with thresholds governed by the sparsity-overlap function and sharp characterization under standard Gaussian designs. Its relative advantage over the ordinary Lasso depends on the active-row covariance and coefficient-vector geometry.
- Theory and setting: The estimator is analyzed for Gaussian random designs and Gaussian noise, with support recovery defined as recovering the nonzero rows of B*.The analysis also establishes uniqueness in the regime of interest.
- Theory and setting: The sparsity-overlap function ψ(B*) defines the effective sample-complexity scale for support recovery and ℓ∞/ℓ2 estimation.The relevant rescaled sample size is θ = n/[2ψ(B*)log(p−s)].
- Threshold results: Theorem 1 gives high-probability achievability: the group Lasso has no false inclusions, controls rowwise error, and exactly recovers the row support under additional minimum-signal conditions.The result is stated for regularization sequences satisfying the paper’s assumptions.
- Threshold results: Theorem 2 gives the converse: below a critical rescaled sample size, no group-Lasso solution achieves both the correct row support and the required rowwise error bound.The result is a high-probability failure statement for the specified problem sequences.
- Threshold results: For standard Gaussian designs, the threshold is sharp at θ = 1: θ > 1 + δ yields success with high probability, while θ < 1 −δ yields failure.The sufficient and necessary thresholds coincide because the relevant covariance and incoherence quantities equal one.
- Consequences: When the active-row design covariance is uncorrelated, group-Lasso row selection is never worse than ordinary Lasso and can require K times fewer samples for suitably orthogonal coefficient vectors.For identical regressions, the analysis finds no benefit over separate Lasso problems; more general designs can favor ordinary Lasso.
3. Proof of Theorem 1.
The proof of Theorem 1 constructs a primal–dual witness for the multivariate group Lasso and shows its support conditions hold with high probability under the stated scaling.
- The proof constructs primal and dual matrices satisfying the SOCP’s KKT conditions, thereby certifying recovery of the support union.
- The constructed solution is unique under the theorem’s conditions, despite general high-dimensional instances potentially having nonunique group-Lasso solutions.
- Positive definiteness of the active empirical covariance makes the restricted problem strictly convex and gives a unique active-block optimum.
- Setting the estimated coefficients outside S to zero reduces the construction to a restricted problem on the active rows.
- The proof separately controls events ensuring no active row is zero and all inactive rows satisfy the dual feasibility condition.
- Under Theorem 1’s conditions, the required events hold with probability tending to one, yielding the stated error and support-recovery guarantees.
4. Proof of Theorem 2.
The proof of Theorem 2 derives necessary conditions by analyzing dual feasibility and the maximum inactive-row fluctuation, showing failure below the theorem’s threshold regime.
- If the dual feasibility event fails, no multivariate group-Lasso solution can have the correct row support.
- The inactive-row maximum is decomposed into concentration and expectation terms, with Gaussian concentration controlling deviations.
- A Gaussian comparison argument lower-bounds the expected inactive-row maximum using the conditional covariance structure.
- Combining the lower bound with concentration yields failure when the sample-complexity parameter lies below the lower threshold θℓ.
5. Discussion.
The discussion summarizes the threshold characterization, its dependence on sparsity and support overlap, and the asymptotic scope and open extensions of the analysis.
- Theorems 1 and 2 establish success or failure according to whether this parameter is above or below a design-covariance-dependent threshold.
- The analysis assumes n, p −s, and s all tend to infinity, although the requirement s → +∞ can be weakened with weaker ℓ2/ℓ∞ guarantees.
- Open questions include block regularization under soft sparsity and evaluation by ℓ2 or prediction error instead of exact support recovery.
APPENDIX A: PROOF OF COROLLARY 2
The appendix bounds failure in a multistage procedure by combining row-support recovery with the conditional failure probability of recovering individual supports.
- The overall multistage failure probability is bounded by row-support failure plus failure of the second stage conditional on correct row recovery.
- Under Theorem 1, row-support recovery fails with probability tending to zero, so the first-stage term vanishes.
- It therefore suffices to bound the unconditional probability that the second-stage ROLS estimate fails on the true support.
- Gaussian noise and tail bounds provide control of the ROLS estimation error, which supports the thresholding guarantee.
- The threshold procedure retains all nonzero coefficients and sets entries corresponding to zero coefficients to zero.
APPENDIX B: PROOF OF LEMMA 2
The appendix establishes uniqueness of the group-Lasso solution by expressing the problem as a second-order cone program and applying KKT conditions, dual feasibility, and restricted-program uniqueness.
- Conic reformulation: The original convex program with q = 2 can be rewritten using the usual second-order cone.The reformulation enables conic duality and KKT analysis.
- Duality and KKT conditions: Strong duality applies because the original program is convex and strictly feasible, so primal and dual solutions satisfy the KKT conditions.The conic dual uses the self-duality of the second-order cone.
- Duality and KKT conditions: Any solution satisfying Lemma 2 also satisfies the conic KKT conditions through equivalence of the stationarity and complementary-slackness requirements.The appendix connects the lemma’s conditions to the conic formulation’s KKT system.
- Support restriction: For inactive covariates j ∈ S^c, strict dual feasibility ∥ẑ_j∥2 < 1 forces every primal solution to have eβ_j = 0.Thus any primal solution is supported entirely on S and solves the restricted convex program.
- Uniqueness: The restricted convex program has a unique solution because S^T X_S is strictly positive definite with probability one, making the original solution unique.The argument combines support restriction with uniqueness on the active set.
APPENDIX C: CHARACTERIZATION OF THE SPARSITY-OVERLAP FUNCTION
This appendix proves properties of the sparsity-overlap characterization by relating spectral quantities to the norms of the matrix formed from dual variables, with orthogonality yielding a diagonal simplification.
- Lemma 1: The appendix begins by setting up Z* and its column-wise components to prove Lemma 1.The proof analyzes the dual matrix through its columns and spectral norm.
- General bounds: Bounds on the spectral norm follow from upper and lower comparisons with the matrix’s eigenvalues.These eigenvalue bounds provide the general control needed in the characterization.
- Orthogonal case: Under orthogonality, Z*T Z* is diagonal, so its largest eigenvalue equals the largest squared column norm ∥Z*(k)∥2.Orthogonality reduces the spectral calculation to the largest column contribution.
APPENDIX D: GROUP LASSO VERSUS ORDINARY LASSO
The appendix compares row-selection performance of the group and ordinary Lasso through their respective complexity quantities, showing how the ordinary Lasso benchmark is governed by the largest response-specific support term.
- Efficiency comparison: The appendix analyzes the relative efficiency of group versus ordinary Lasso using the quantities introduced before Corollary 3.The comparison is framed through the sparsity-overlap function and ordinary-Lasso row-selection complexity.
- Ordinary-Lasso benchmark: The ordinary Lasso performance is governed by max_k s_k log(p − s_k), which is at least max_k s_k log(p − s).Here s_k denotes the support size associated with response k, while s is the union support size.
- Efficiency comparison: The proof proceeds by relating the ordinary-Lasso complexity to ψ(B*) through row-wise quantities involving the dual matrix Z*.The remaining derivation uses the ith row of Z* and Cauchy–Schwarz.
APPENDIX E: INEQUALITIES WITH BLOCK-MATRIX NORMS
This appendix records norm relations for block matrices, emphasizing that the introduced matrix-norm families generally differ but coincide under a useful conjugate-exponent condition.
- Norm relations: The matrix norms |||·|||p,q and ∥·∥ℓa/ℓb are distinct in general.The appendix then identifies a special case in which they coincide.
- Lemma 7: Lemma 7 states the coincidence condition for 1 ≤ p ≤ ∞ when r satisfies 1/r + 1/p = 1.The result is expressed using conjugate exponents.
- Lemma 7: The proof of Lemma 7 works row by row by denoting the ith row of A by a_i.This row-wise representation is the basis for the norm identity.
- Further inequalities: The appendix concludes by stating additional bounds and relations for products of block matrices.These results are collected in Lemma 8 for matrices A and Z and positive parameters p and r.
APPENDIX F: SOME CONCENTRATION INEQUALITIES FOR RANDOM MATRICES
Appendix F collects concentration bounds for Gaussian random matrices and adapts them to general Gaussian ensembles under eigenvalue and scaling conditions.
- The appendix focuses on extreme-eigenvalue concentration for Gaussian random matrices when s/n → 0.
- For a standard Gaussian matrix U, the bounds concern its smallest and largest singular values.
- The Gaussian results extend to matrices with independent rows distributed as N(0,Λ), with constants controlled by eigenvalue bounds on Λ.
- The appendix also assumes XT X is invertible when bounding the relevant matrix difference.
- If the eigenvalues of Λ are bounded below by Cmin > 0, the inverse covariance and normalized Gram-matrix norms receive corresponding high-probability bounds.
APPENDIX G: PROOF OF LEMMA 3
Appendix G uses a rowwise error condition to establish that the estimated active rows remain nonzero and their normalized directions are well defined.
- If ∥∆i∥2 ≤ 1/2, then the estimated coefficient row bβi is nonzero for every active row i ∈ S.
- Under the same condition, each active estimated direction is defined by bZi = bβi/∥bβi∥2.
- The proof invokes the mean-value theorem for a perturbation involving z and δ.
APPENDIX H: PROOF OF LEMMA 4
Appendix H proves Lemma 4 by combining random-matrix concentration, spectral-norm bounds, and componentwise estimates to control the relevant error terms.
- The proof bounds Mn in spectral norm using the triangle inequality and decomposes the analysis into terms such as A1 and A2.
- Random-matrix concentration yields high-probability control of the inverse estimated covariance and related matrix differences.
- The normalized active-row estimate satisfies ∥Z∗S − bZS∥ℓ∞/ℓ2 = o(1) with probability exceeding 1 − c1 exp(−c0K log s).
- The proof combines bounds (67), (68), and (69) with the decomposition (65) to obtain ψ(B∗) = Θ(s).
- The resulting claims hold with probability greater than 1 − c1 exp(−c0K log s).
- A χ2 concentration lemma and a union bound provide an additional probabilistic ingredient used in the argument.