On the conditions used to prove oracle results for the Lasso

By Sara A. van de Geer, Peter Buhlmann. 2009

748 citations recorded by the source corpus.

Oracle inequalities and variable selection properties for the Lasso in linear models have been established under a variety of different assumptions on the design matrix. We show in this paper how the different conditions and concepts relate to each other. The restricted eigenvalue condition (Bickel et al., 2009) or the slightly weaker compatibility condition (van de Geer, 2007) are sufficient for oracle results. We argue that both these conditions allow for a fairly general class of design matrices. Hence, optimality of the Lasso for prediction and estimation holds for more general situations than what it appears from coherence (Bunea et al, 2007b,c) or restricted isometry (Candes and Tao, 2005) assumptions.

Subfields: 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 Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Sparse Partially Linear Additive Models (2014, neutral): “5.1 SYNTHETIC PROBLEM To illustrate the use of SPLAM, we generate N = 2000 points from the model y = 2 sin(2x1)+ x22 + exp(−x3)+ x4 − 3x5 + 2.5x6 + 10x7 + 2x8 − 7x9 + 5x10 + , where ∼ N (0, 1).”
Robust Lasso With Missing and Grossly Corrupted Observations (2011, background): “in [10] ,[33] and [34]. In the absence of a vector f in the equation (10) and in the set C, this condition returns to the restricted eigenvalue deﬁned in [10]. As discussed in more detail in [10] and [35], restricted eigenvalue is among the weakest assumption on the design matrix such that the solut”
On asymptotically optimal confidence regions and tests for high-dimensional models (2013, background): “-wise error rate. 2.3.2. Discussion of the assumptions. The compatibility condition in (A1) is weaker than many others which have been proposed such as assumptions on restricted or sparse eigenvalues [48]: a relaxation by a constant CONFIDENCE REGIONS FOR HIGH-DIMENSIONAL MODELS 11 factor has recent”
Multi-Stage Multi-Task Feature Learning (2012, neutral): “Please refer to [19, 25, 27] for more details about the incoherence condition, the RIP condition, the sparse eigenvalue condition and their relationships.”
Exponential Screening and optimal rates of sparse estimation (2010, background): “B¨uhlmann and van de Geer (2009) review a long list of such assumptions, including the restricted isometry (RI) property given, for example, in Candes (2008) and the restricted eigenvalue (RE) condition of Bickel et al. (2009) described in Section 4.”
How Correlations Influence Lasso Prediction (2012, background): “slightly different assumptions, can be found in [1], [5], [16], and [25].”
On the uniform convergence of empirical norms and inner products, with application to causal inference (2013, background): “1 has very useful applications, in particular to l1-regularization or to exact recovery using basis pursuit [9] where results often rely on bounds for compatibility constants [29, 30] or restricted eigenvalues [6].”
Confidence intervals for high-dimensional inverse covariance estimation (2014, background): “Irrepresentability condition). There exists 2(0;1] such that max e2Sc k eS ( SS ) 1k 1 1 : (3) Condition(A1)is an analogy of the irrepresentable condition for variable selection in linear regression [34]. If we dene the zero-mean edge random variables ([26]) as Y (i;j) := X iX j E(XX); then the matr”
A General Theory of Concave Regularization for High-Dimensional Sparse Estimation Problems (2011, methodology): “ts sign-restricted version have appeared in [41], where invertibility factorbased ℓq error bounds of the form (19) below have been proven to sharpen earlier results for the Lasso and Dantzig selector [9, 43, 3, 44, 39] when q ∈ [1,2]. Such error bounds are of optimal order [41, 30]. Of special inter”
Causal Dantzig: Fast inference in linear structural equation models with hidden variables under additive interventions (2017, positive): “By Van De Geer and Bühlmann [2009], for all t ≥ 0, with probability exceeding 1− 2 exp(−t), 1 ne ∣∣(Xe•k)t(Ye −Xβ)− E [(Xe•k)t(Ye −Xei•β)]∣∣ ≤ σε √ Var(Xe k) (√ 4t ne + 4t ne ) .”
Restricted Eigenvalue Properties for Correlated Gaussian Designs (2010, methodology): “(b) As previously discussed, it is known (Bickel et al., 2009; van de Geer, 2000; van de Geer and Buhlmann, 2009) that if X T X/n satisfies the RE condition, then the ℓ 2 error of the Lasso under the sparse linear model with Gaussian noise satisfies the bound β − β * 2 = O( k log p n ) with high…”
Asymptotically Honest Confidence Regions for High Dimensional Parameters by the Desparsified Conservative Lasso (2014, neutral): “1 in van de Geer and Bühlmann (2009). For any (non-zero) p× 1 vector v such that ‖vSc‖1 ≤ 3 √ s ‖vS‖2 one has v′Av − v′Bv ≤ |v′Av − v′Bv| = |v′(A−B)v| ≤ ‖v‖1 ‖(A−B)v‖∞ ≤ δ ‖v‖ 2 1 = δ ( ‖vS‖1 + ‖vSc‖1 )2 ≤ δ16s ‖vS‖22 .”
BAYESIAN LINEAR REGRESSION WITH SPARSE PRIORS (2014, background): “ey are typically stronger than conditions in terms of compatibility numbers or sparse singular values. The lemma is embodied in Lemma 2 in [32], and is closely related to the inequalities obtained in [46]. For ease of reference we provide a proof in the supplementary material [15]. Lemma 1. φ(S)2 ≥φ”