Sparsity oracle inequalities for the Lasso

By Florentina Bunea, Alexandre B. Tsybakov, Marten H. Wegkamp. 2007

480 citations recorded by the source corpus.

This paper studies oracle properties of $\ell_1$-penalized least squares in nonparametric regression setting with random design. We show that the penalized least squares estimator satisfies sparsity oracle inequalities, i.e., bounds in terms of the number of non-zero components of the oracle vector. The results are valid even when the dimension of the model is (much) larger than the sample size and the regression matrix is not positive definite. They can be applied to high-dimensional linear regression, to nonparametric adaptive regression estimation and to the problem of aggregation of arbitrary estimators.

Subfields: Artificial Intelligence, Statistics and Probability, Statistical Learning Theory

How researchers see this paper

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

In Artificial Intelligence

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

SIMULTANEOUS ANALYSIS OF LASSO AND DANTZIG SELECTOR (2008, methodology): “Lasso estimators have also been studied in the nonparametric regression setup [2–4, 12, 13, 19] and [5].”
Sparse additive models (2007, background): “…where many components β j are zero. b The good empirical success of this estimator has been recently backed up by results conﬁrming that it has strong theoretical properties; see (Bunea et al., 2007; Greenshtein and Ritov, 2004; Meinshausen and Yu, 2006; Wainwright, 2006; Zhao and Yu, 2007).”
Nearly unbiased variable selection under minimax concave penalty (2010, background): “Candés and Tao (2007) proposed a Dantzig selector and provided elegant probabilistic upper bounds for the l2 loss for the estimation of β. However, while the Dantzig selector and LASSO have been found to perform similarly in simulation studies [Efron, Hastie and Tibshirani (2007), Meinshausen, Rocha”
Robust Lasso With Missing and Grossly Corrupted Observations (2011, neutral): “[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15]).”
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 [7, 21], oracle inequalities and estimation of a highdimensional parameter [6, 11, 12, 24, 33, 34, 47, 51] or variable selection [17, 30, 49, 53].”
High-dimensional additive modeling (2008, neutral): “5 | i − j | ; i, j = 1 , . . . , p .”
On the conditions used to prove oracle results for the Lasso (2009, neutral): “Keywords and phrases: Coherence, compatibility, irrepresentable condition, Lasso, restricted eigenvalue, restricted isometry, sparsity.”
Some sharp performance bounds for least squares regression with L1 regularization (2009, methodology): “Among earlier work, prediction accuracy bounds for Lasso were derived in [2, 3] and [5] under mutual incoherence conditions (introduced in [9]) that are generally regarded as stronger than the sparse eigenvalue conditions employed by [4].”
Statistical significance in high-dimensional linear models (2012, background): “Results along these lines have been established by Bunea, Tsybakov and Wegkamp (2007), van de Geer (2008) who covers generalized linear models as well, Zhang and Huang (2008), Meinshausen and Yu (2009), Bickel, Ritov and Tsybakov (2009) among others.”
Exponential Screening and optimal rates of sparse estimation (2010, background): “Nevertheless, this last condition is not used in the proof in Bunea et al. (2007b), and the result trivially extends to the framework that we consider here.”
Least angle and ℓ1 penalized regression: A review (2008, background): “(Meinshausen and Yu 2008; Zhang and Huang 2007; Bunea et al. 2007; van de Geer 2008); for a high-dimensional setting and a suitable sequence θn, often under much fewer restrictions than needed for model selection consistency.”
Group Lasso for high dimensional sparse quantile regression models (2011, methodology): “…such as the ℓ 2 -estimation error and the model selection property of the ℓ 1 -penalized estimator for high dimensional linear regression models (Bunea et al., 2007a,b; Zhao and Yu, 2007; Zhang and Huang, 2008; Wainwright, 2009; Meinshausen and Yu, 2009; Bickel et al., 2009), for high…”
Some theoretical results on the Grouped Variables Lasso (2008, background): “SOIs have already been investigated for other estimators ([5], [8], [14], [20] and [6]).”