LASSO-TYPE RECOVERY OF SPARSE REPRESENTATIONS FOR HIGH-DIMENSIONAL DATA

By Nicolai Meinshausen, Bin Yu. 2008

909 citations recorded by the source corpus.

The Lasso [28] is an attractive technique for regularization and variable selection for high-dimensional data, where the number of predictor variables p is potentially much larger than the number of samples n. However, it was recently discovered [23, 38, 39] that the sparsity pattern of the Lasso estimator can only be asymptotically identical to the true sparsity pattern if the design matrix satisfies the so-called irrepresentable condition. The latter condition can easily be violated in applications due to the presence of highly correlated variables. Here we examine the behavior of the Lasso estimators if the irrepresentable condition is relaxed. Even though the Lasso cannot recover the correct sparsity pattern, we show that the estimator is still consistent in the ‘2-norm sense for fixed designs under conditions on (a) the number sn of non-zero components of the vector n and (b) the minimal singular values of the design matrices that are induced by selecting of order sn variables. The results are extended to vectors in weak ‘q-balls with 0 < q < 1. Our results imply that, with We would like to thank Noureddine El Karoui and Debashis Paul for pointing out interesting connections to Random Matrix theory. Some results of this manuscript have been presented at the Oberwolfach workshop “Qualitative Assumptions and Regularization for High-Dimensional Data”. Nicolai Meinshausen is supported by DFG (Deutsche Forschungsgemeinschaft) and Bin Yu is partially supported by a Guggenheim fellowship and grants NSF DMS-0605165 (06-08), NSF DMS-03036508 (03-05) and ARO W911NF05-1-0104 (05-07).

Subfields: Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

SIMULTANEOUS ANALYSIS OF LASSO AND DANTZIG SELECTOR (2008, background): “The corresponding, slightly stronger, assumption in [18] is stated in asymptotic form, for s = sn → ∞, as lim inf n φmin(sn logn) > 0.”
Sparse additive models (2007, background): “(2007), Greenshtein and Ritov (2004), Zhao and Yu (2007), Meinshausen and Yu (2006) and Wainwright (2006). The non-parametric regression model Yi=m.”
Stability selection (2008, methodology): “The same distinction can be made with two-stage procedures like adaptive Lasso (Zou, 2006) or hard-thresholding (Candes and Tao, 2007; Meinshausen and Yu, 2009), where variables are thresholded.”
Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming (2010, background): “r cone programming. Mathematical Programming, (126):1–29, 2011. [12] B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. Ann. Statist., 28(5):1302–1338, 2000. [13] N. Meinshausen and B. Yu. Lasso-type recovery of sparse representations for high-dimensional da”
Nearly unbiased variable selection under minimax concave penalty (2010, methodology): “For recent advances in the LASSO or LASSO-like estimations of Xβ and β, we refer to Greenshtein and Ritov (2004), Candés and Tao (2007), Bunea, Tsybakov and Wegkamp (2007), van de Geer (2008), Zhang and Huang (2008) and Meinshausen and Yu (2009).”
Robust Lasso With Missing and Grossly Corrupted Observations (2011, background): “However, this parameter actually controls the sparsity level of the regression vector with respect to the fraction of corruption.”
On asymptotically optimal confidence regions and tests for high-dimensional models (2013, background): “The vast majority of work has been pursued for point estimation such as consistency for prediction [21, 7], oracle inequalities and estimation of a high-dimensional parameter [12, 11, 50, 45, 33, 6, 34, 24] or variable selection [30, 53, 17, 48].”
High-dimensional additive modeling (2008, methodology): “inear or generalized linear models where the number of covariates pis much larger than sample size n. The theoretical properties of penalization approaches like the lasso [28] are now well understood [3, 14, 23, 24, 33] and this knowledge has led to several extensions or alternative approaches like ”
On the conditions used to prove oracle results for the Lasso (2009, background): “Such oracle results have been derived by, among others, [4, 19, 21, 2, 16], and for the related Dantzig selector by [11] and [13].”
Performance bounds for parameter estimates of high-dimensional linear models with correlated errors (2016, neutral): “See also [6, 28, 48, 49] for related conditions.”
Lower bounds on the performance of polynomial-time algorithms for sparse linear regression (2014, background): “The RE condition (10) and related quantities have been studied extensively in past work on basis pursuit and the Lasso (e.g. Bickel et al., 2009; Meinshausen and Yu, 2009; Raskutti et al., 2011); see the paper (Van De Geer and Bühlmann, 2009) for an overview of the different types of RE parameters.”
On Model Selection Consistency of the Elastic Net When p >> n (2008, background): “Key words and phrases: Elastic irrepresentable condition, Elastic Net, irrepresentable condition, Lasso, model selection consistency.”
Asymptotic analysis of high-dimensional LAD regression with Lasso (2016, background): “Thus Lemma 6 is the direct result of the rate consistency of the LS-Lasso in Meinshausen and Yu (2009).”
Confidence intervals for low dimensional parameters in high dimensional linear models (2011, neutral): “…and Bühlmann, 2006; Tropp, 2006; Zhao and Yu, 2006; Candès and Tao, 2007; Zhang and Huang, 2008; Bickel et al., 2009; Koltchinskii, 2009; Meinshausen and Yu, 2009; van de Geer and Bühlmann, 2009; Wainwright, 2009a; Zhang, 2009; Ye and Zhang, 2010; Koltchinskii et al., 2011; Sun and…”