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

By Cun-Hui Zhang, Jian Huang. 2008

896 citations recorded by the source corpus.

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 l α -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.

Subfields: Artificial Intelligence, 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 Artificial Intelligence

In Statistics and Probability

Citations in the corpus

An Overview of Multi-Task Learning in Deep Neural Networks (2017, neutral): “[Zhang and Huang, 2008] use (cid:96) 1 /(cid:96) ∞ regularization, while [Argyriou and Pontil, 2007] use a mixed (cid:96) 1 /(cid:96) 2 norm.”
Best Subset Selection via a Modern Optimization Lens (2015, methodology): “…used to “bridge” the gap between the convex 1 penalty and the combinatorial 0 penalty [Candès, Wakin and Boyd (2008), Fan and Li (2001), Frank and Friedman (1993), Friedman (2008), Mazumder, Friedman and Hastie (2011), Zhang (2010a, 2010b), Zhang and Huang (2008), Zou (2006), Zou and Li (2008)].”
CAM: Causal Additive Models, high-dimensional order search and penalized regression (2013, background): “Assumption (B2,ii) can be ensured by assuming max j | A j | ≤ M 1 < ∞ and e.g. group restricted eigenvalue assumptions for the design matrix (with the given basis); see Zhang and Huang (2008) and van de Geer et al. (2011) for the case without groups.”
Stability selection (2008, methodology): “…lasso, we can do without the irrepresentable condition (12) but need only a condition on the sparse eigenvalues of the design (Candes and Tao, 2007; van de Geer, 2008; Meinshausen and Yu, 2009; Bickel et al., 2009), which was also called the sparse Riesz condition in Zhang and Huang (2008).”
Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming (2010, background): “ submatrices of the large p × p Gram matrix to be bounded from above and below. The suﬃciency of (3.13) for Condition RE follows from [2], and many suﬃcient conditions for (3.13) are provided by [2], [19], and [7]. 3.2. Finite-Sample and Asymptotic Bounds on Estimation Error. We now present the main”
On asymptotically optimal confidence regions and tests for high-dimensional models (2013, background): “tly exceeds sample size. The vast majority of work has been pursued for point estimation such as consistency for prediction [7, 21], oracle inequalities and estimation of a high-dimensional parameter [6, 11, 12, 24, 33, 34, 47, 51] or variable selection [17, 30, 49, 53]. Other references and exposit”
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 ”
Multi-Stage Multi-Task Feature Learning (2012, neutral): “Such a condition is very common in the analysis of sparse regularization (Zhang and Huang, 2008; Zhang, 2009) and it is slightly weaker than the RIP condition (Candes and Tao, 2005; Huang and Zhang, 2010; Zhang, 2012).”
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 GUARANTEES FOR INDIVIDUALIZED TREATMENT RULES (2011, positive): “ In this section, we present a generalization of Theorem 4.3 where J may depend on n and the sparsity of any θ ∈RJ is measured by the number of “large” components in θ as described in Zhang and Huang [36]. In this case, J, Φ and the prediction error minimizer θ∗ are denoted as J n,Φn and θ∗, respect”
Estimation for High‐Dimensional Linear Mixed‐Effects Models Using ℓ1‐Penalization (2010, background): “Works dealing with various aspects around (2) include Bunea et al. (2007), van de Geer (2008), Zhang and Huang (2008), Meinshausen and Yu (2009) and Bickel et al. (2009).”
SparseNet: Coordinate Descent With Nonconvex Penalties (2011, background): “3 Multi-stage Local Linear Approximation Zou & Li (2008), Zhang (2009) and Candes et al.”
Tuning parameter selection in high dimensional penalized likelihood (2013, background): “Zhang and Huang (2006) studied the sparsity and bias of the Lasso estimator and established the consistency rate, and Lv and Fan (2009) established the weak oracle property of the regularized least-squares estimator with general concave penalty functions.”
Some sharp performance bounds for least squares regression with L1 regularization (2009, background): “We shall refer to such a condition as sparse eigenvalue condition (also see [1, 19]).”
The adaptive and the thresholded Lasso for potentially misspecified models (and a lower bound for the Lasso) (2011, methodology): “We refer to [34] for examples where Condition D is met.”
Controlling the false discovery rate via knockoffs (2014, background): “(1.5) For sparse linear models, the Lasso is known to be asymptotically accurate for both variable selection and for coefﬁ-cient or signal estimation (see for example [3, 5, 21, 22]), and so even in a non-asymptotic setting, we will typically see ˆ β ( λ ) including many signal variables and few…”