PaperlayerView exact revision on arXiv

Source-linked AI summary

The sparsity and bias of the Lasso selection in high-dimensional linear regression

Cun-Hui Zhang, Jian Huang

arXiv:0808.0967v1math.ST

TL;DR

Existing LASSO theory emphasizes exact recovery under strong conditions and separated nonzero coefficients, whereas this paper addresses high-dimensional regression with many small coefficients. It analyzes LASSO selection under a sparse Riesz condition and shows rate consistency in model sparsity and bias. The results also yield convergence of mean-response and coefficient losses at the best possible rates under the stated conditions.

  • Problem

    Prior LASSO results required strong irrepresentable conditions and coefficients separated from zero for exact support recovery, leaving the setting of many small nonzero coefficients less directly addressed.

  • Method

    The paper analyzes LASSO model selection under a sparse Riesz condition, measuring selected-model sparsity, bias, and missing large coefficients.

  • Results

    The LASSO selects the correct order of model dimensionality, controls selected-model bias, and selects coefficients larger than the bias-determined threshold.

  • Takeaways & Limitations

    Rate-consistent LASSO selection supports convergence of mean-response error and regression-coefficient loss at the best possible rates under the given conditions.

  • Takeaways & Limitations

    The theoretical justification of data-driven penalty selection such as cross-validation remains unclear for model-selection purposes.

Abstract

from arXiv · show

Meinshausen and Buhlmann [Ann. Statist. 34 (2006) 1436--1462] showed that, for neighborhood selection in Gaussian graphical models, under a neighborhood stability condition, the LASSO is consistent, even when the number of variables is of greater order than the sample size. Zhao and Yu [(2006) J. Machine Learning Research 7 2541--2567] formalized the neighborhood stability condition in the context of linear regression as a strong irrepresentable condition. That paper showed that under this condition, the LASSO selects exactly the set of nonzero regression coefficients, provided that these coefficients are bounded away from zero at a certain rate. In this paper, the regression coefficients outside an ideal model are assumed to be small, but not necessarily zero. Under a sparse Riesz condition on the correlation of design variables, we prove that the LASSO selects a model of the correct order of dimensionality, controls the bias of the selected model at a level determined by the contributions of small regression coefficients and threshold bias, and selects all coefficients of greater order than the bias of the selected model. Moreover, as a consequence of this rate consistency of the LASSO in model selection, it is proved that the sum of error squares for the mean response and the $\ell_α$-loss for the regression coefficients converge at the best possible rates under the given conditions. An interesting aspect of our results is that the logarithm of the number of variables can be of the same order as the sample size for certain random dependent designs.

1. Introduction.

The paper studies LASSO selection when high-dimensional regression contains many small, potentially nonzero coefficients. Under a sparse Riesz condition, it establishes rate-consistent selection in sparsity and bias rather than requiring exact recovery of every nonzero coefficient.

  • Motivation: High-dimensional applications can have p much larger than n, while only a smaller number of covariates are important, motivating penalized regression and variable selection.The LASSO uses an L1 penalty and supports variable selection in such settings.
  • Motivation: The paper broadens sparsity beyond exact zeros by allowing most coefficients to be small, with their absolute values summing below a prescribed level.This removes the requirement that all nonzero coefficients be uniformly separated from zero.
  • Main contribution: Under a sparse Riesz condition, the LASSO selects a model with the correct order of sparsity and controls its bias at the order achieved under orthonormal designs.The condition limits eigenvalue ranges for covariance matrices of subsets of covariates.
  • Main contribution: The selected model includes variables whose coefficients exceed a threshold determined by the controlled bias, while exact recovery of all nonzero coefficients is not the target under general sparsity.This target is appropriate when many small coefficients are present.
  • High-dimensional identifiability: When p > n, sparse Riesz conditions provide uniqueness of representations among sufficiently sparse coefficient vectors despite potentially many models fitting the same data.The stated uniqueness applies to coefficient vectors with sparsity at most q*/2.

2. Rate consistency of the LASSO in sparsity and bias.

The paper replaces exact recovery of every nonzero coefficient with rate-consistent selection under approximate sparsity, using the sparse Riesz condition. The LASSO achieves controlled model size and bias while retaining sufficiently large coefficients, including in high-dimensional settings.

  • Goal under approximate sparsity: Approximate sparsity permits many small nonzero coefficients, so selection targets a sparse model that fits Xβ well and includes the largest coefficients.The selected model need not contain every nonzero coefficient.
  • Rate consistency: The LASSO selects a model with the correct order of sparsity and controls selected-model bias at the order of small-coefficient contributions and orthonormal-design threshold bias.These conclusions hold under the stated sparsity, sparse Riesz, Gaussian-error, and penalty-level configurations.
  • Sparse Riesz condition: The sparse Riesz condition bounds covariance eigenvalues for subsets of a fixed size and supports rate consistency without requiring the strong irrepresentable condition.It is described as easier to interpret and less restrictive in practice than the strong irrepresentable condition.
  • Penalty choice: Model-selection guarantees apply along the LASSO path for λ ≥ max(λ∗, λn,p), but theoretical justification remains unclear for cross-validation when selecting λ for model-selection purposes.The paper identifies λn,p as a good choice when λn,p ≥ λ∗, assuming information about q and the sparse-spectrum parameters.
  • Large-coefficient recovery: The LASSO selects all variables whose coefficients exceed an explicit threshold determined by the controlled bias of the selected model.This selection guarantee does not depend on the values of the remaining coefficients.
  • High-dimensional designs: For suitable random dependent designs, the sparse Riesz rank can scale as a0n/{1 ∨ log(p/n)}, allowing p as large as exp(an).The result is stated to hold with large probability as (n,p)→(∞,∞).

3. The LASSO estimation.

The paper derives estimation consequences from LASSO rate consistency under high-dimensional sparsity and sparse Riesz conditions. It establishes sharp convergence rates for mean-response prediction and regression-coefficient losses.

  • High-dimensional regime: The analysis allows p, q, and q∗ to depend on n, including regimes with p ≫ n > q∗ > q → ∞.The result is developed for penalty levels satisfying the theorem’s prescribed configuration conditions.
  • Estimation consequences: Under the theorem’s conditions, the LASSO estimation error is bounded through the selected-model dimension and bias terms.The proof controls the selected-model size, projection error, and coefficients excluded from the selected model.
  • Estimation consequences: The convergence rates for mean-response error and ℓ_α coefficient loss are sharp under the stated conditions.The rates match the corresponding rates for orthogonal designs, while the α = 2 risk inflation factor is optimal.
  • Proof strategy: The proof uses Gaussian-noise bounds and the Karush–Kuhn–Tucker conditions to control stochastic projection terms.The inequality controlling the selected-set size enables application of the sparse Riesz condition.

4. The sparse Riesz condition.

This section characterizes the sparse Riesz condition and gives sufficient conditions for deterministic and random designs. For Gaussian random dependent designs, the condition can hold in regimes where p grows exponentially with n.

  • Random design matrices: For random designs, the rows are i.i.d. while covariates within each row may remain dependent.The analysis treats both Gaussian sequences and bounded covariates under a population Riesz condition.
  • Condition: The sparse Riesz condition bounds eigenvalues of covariance matrices for all covariate subsets up to a specified rank.Its general form requires the eigenvalues for subsets of size at most m to lie between c∗(m) and c∗(m).
  • Deterministic design matrices: An ℓ_α Gershgorin-type correlation bound is sufficient for the sparse Riesz condition.For standardized covariates, the resulting spectrum bounds are c∗ = 1 − δ and c∗ = 1 + δ.
  • Deterministic design matrices: For δ = 1/3, C = c∗/c∗ = 2, and Theorem 1 applies when 10q + 1 ≤ q∗ and η1 = 0.These are the specific sufficient values stated in the paper’s remark.
  • Scope boundary: The population Riesz condition alone does not guarantee uniformly positive finite-sample sparse eigenvalue bounds for every subset size.In particular, c∗(n + 1) = 0.
  • Random design matrices: For Gaussian random designs, the sparse Riesz condition holds with large probability for q∗ = a0n/{1 ∨ log(p/n)} under the stated growth conditions.This permits p as large as exp(an) in the applicable random-design setting.

5. Proof of Theorem 1.

The proof partitions variables into sets representing selected, ideal, large, small, and unselected coefficients, then combines KKT identities with sparse-Riesz bounds. It derives simultaneous control of model size, projection bias, and omitted coefficients.

  • KKT analysis: The KKT conditions yield equations linking selected coefficients to the response, design cross-products, noise, and the LASSO penalty.The proof then rewrites the unselected-coordinate conditions using the projection onto the span of selected covariates.
  • Variable decomposition: The proof partitions the variables into six sets to separate selected variables, ideal-model variables, and coefficient groups relevant to the bias analysis.The sets A1 through A6 support decompositions used throughout the proof.
  • Proof objectives: The proof targets upper bounds for selected-model dimension, projection bias, and the coefficients outside the ideal model.These quantities are linked through the selected set A1 and its associated projection P1.
  • Proof steps: Step 1 cancels cross-products and bounds a quadratic error expression by a linear function involving noise, omitted coefficients, and projection bias.This prepares the bounds used in Step 2.
  • Proof steps: Step 2 converts the intermediate inequality into bounds for q1, the orthogonal residual component, and the coefficients outside the ideal model.The argument uses Cauchy–Schwarz inequalities and penalty-dependent quantities B1 and B2.
  • Proof steps: Step 3 establishes probabilistic bounds and extends the conclusions to all admissible penalty levels using continuity of the LASSO coefficient path.The sparse Riesz bounds and the theorem’s configuration conditions then yield the theorem’s assertions.

6. Related results and final remarks.

The paper contrasts its rate-consistent model-selection guarantees under the sparse Riesz condition with prior sign-consistency and estimation results. It highlights milder assumptions, allowance for many small coefficients, and a remaining gap caused by LASSO estimation bias.

  • Related results: Prior work established sign-consistency under the strong irrepresentable condition, while related studies also derived prediction and coefficient-loss convergence rates under sparse-eigenvalue or random-design assumptions.The paper distinguishes these results from its focus on properties of the selected model.
  • Comparison with sign-consistency results: The paper studies LASSO-selected model sparsity, bias, and missing large coefficients under milder conditions than prior sign-consistency results.It uses the sparse Riesz condition rather than the strong irrepresentable condition.
  • Comparison with sign-consistency results: Many small nonzero coefficients are allowed when their absolute values sum to O(qλ/n).This differs from sparsity formulations requiring only a small number of nonzero coefficients separated from zero.
  • Design conditions: The sparse Riesz and strong irrepresentable conditions do not generally imply each other, but sparse Riesz is easier to interpret and less restrictive practically.The paper also gives sufficient conditions for sparse Riesz designs, including deterministic and random covariates.
  • Main comparison: For correlated designs satisfying sparse Riesz, LASSO model-selection performance is comparable to orthonormal designs in sparsity, bias, and missing-large-coefficient rates.The result concerns rate consistency rather than exact recovery of every nonzero coefficient.
  • Remaining limitation: LASSO can select all coefficients larger than √(qλ/n), yet miss coefficients between √(qλ/n) and λ/n.The gap is attributed to interference from the LASSO estimator’s model-selection bias and cannot be removed for large q.
Loading 0808.0967v1…