High-dimensional graphs and variable selection with the Lasso
By Nicolai Meinshausen, Peter Buhlmann. 2006
3,959 citations recorded by the source corpus.
The pattern of zero entries in the inverse covariance matrix of a multivariate normal distribution corresponds to conditional independence restrictions between variables. Covariance selection aims at estimating those structural zeros from data. We show that neighborhood selection with the Lasso is a computationally attractive alternative to standard covariance selection for sparse high-dimensional graphs. Neighborhood selection estimates the conditional independence restrictions separately for each node in the graph and is hence equivalent to variable selection for Gaussian linear models. We show that the proposed neighborhood selection scheme is consistent for sparse high-dimensional graphs. Consistency hinges on the choice of the penalty parameter. The oracle value for optimal prediction does not lead to a consistent neighborhood estimate. Controlling instead the probability of falsely joining some distinct connectivity components of the graph, consistent estimation for sparse graphs is achieved (with exponential rates), even when the number of variables grows as the number of observations raised to an arbitrary power.
Subfields: Artificial Intelligence, Statistics and Probability, Statistical Learning Theory, Mathematical Optimization
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
- Yoshua Bengio
- Percy Liang
- Michael I. Jordan
- Quoc V. Le
- Sergey Levine
- Mohit Bansal
- Francis R. Bach
- Tong Zhang
In Statistics and Probability
- Peter Buhlmann
- Martin J. Wainwright
- Sara A. van de Geer
- Cun-Hui Zhang
- Jianqing Fan
- Nicolai Meinshausen
- Francis R. Bach
- Robert Tibshirani
In Statistical Learning Theory
- Francis R. Bach
- Martin J. Wainwright
- Tong Zhang
- Peter Buhlmann
- Cun-Hui Zhang
- Bin Yu
- Nicolai Meinshausen
- Michael I. Jordan
In Mathematical Optimization
- Robert Tibshirani
- Martin J. Wainwright
- Peter Buhlmann
- Sara A. van de Geer
- Stefan Wager
- Trevor J. Hastie
- Bin Yu
- Han Liu
Citations in the corpus
- Best Subset Selection via a Modern Optimization Lens (2015, background): “…and Tsybakov (2009), Candès and Plan (2009), Donoho (2006), Efron et al. (2004), Greenshtein and Ritov (2004), Knight and Fu (2000), Meinshausen and Bühlmann (2006), Wainwright (2009), Zhang and Huang (2008), Zhao and Yu (2006)] in terms of algorithms and understanding of its theoretical…”
- A Kernel Test for Three-Variable Interactions (2013, methodology): “If the graphical model is assumed to be Gaussian, then second order interaction statistics may be used to construct an undirected graph [11, 12].”
- CAM: Causal Additive Models, high-dimensional order search and penalized regression (2013, methodology): “We first perform neighborhood selection with additive models, following the general idea in [17] for the linear Gaussian case.”
- Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm (2005, methodology): “Recently, for undirected graphs the Lasso has been proposed as a computationally efficient algorithm for estimating high-dimensional conditional independence graphs where the growth in dimensionality is as in (A2) (see Meinshausen and Bühlmann, 2006). However, the Lasso approach can be inconsistent,”
- Sparse additive models (2007, background): “Codewords/patch 8.14, RSS 0.1894 Codewords/patch 8.08, RSS 0.0913 is sparsistent : b References include Wainwright (2006), Meinshausen and P.”
- Stability selection (2008, methodology): “Xwk /T.Y −Xw−kβ̂λ,W ,−k/| λ, .33/ where β̂λ,W ,−k is the solution to expression (13) with the constraint that β̂λ,W ,−kk = 0, which is comparable with the analysis in Meinshausen and Bühlmann (2006).”
- Nearly unbiased variable selection under minimax concave penalty (2010, background): “Under a strong irrepresentable condition on the normalized Gram matrix Σ≡X′X/n, Meinshausen and Buhlmann (2006), Tropp (2006), Zhao and Yu (2006) and Wainwright (2006) proved that the LASSO is variable selection consistent P{Â=Ao}→ 1 with Â≡ {j : β̂j 6= 0},(1.4) provided that minβj 6=0 |βj |/λ is…”
- Robust Lasso With Missing and Grossly Corrupted Observations (2011, background): “The first property guarantees that (6) is strictly convex, leading to the unique solution of the convex program, while the second property requires the separation between two components of Σ, one related to the set T and the other to the set T c must be sufficiently small.”
- 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, background): “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 adaptive lasso [34], relaxed lasso [22], sure independence screening [12] and graphical model based me”
- High-dimensional Ising model selection using ℓ1-regularized logistic regression (2010, background): “The Annals of Statistics 2010, Vol. 38, No. 3, 1287–1319 DOI: 10.1214/09-AOS691 © Institute of Mathematical Statistics, 2010 HIGH-DIMENSIONAL ISING MODEL SELECTION USING 1-REGULARIZED LOGISTIC REGRESSION”
- On the conditions used to prove oracle results for the Lasso (2009, background): “In [15] and [23], it is proved that the irrepresentable condition is sufficient and essentially necessary for variable selection, i.”
- Shrinkage estimation and selection for multiple functional regression (2011, background): “Several subsequent works (Meinshausen and Buhlmann, 2006; Zhao and Yu, 2006) have shown that Lasso is in general not consistent for model selection unless some nontrivial conditions on the covariates are satisfied.”
- Non-Concave Penalized Likelihood with NP-Dimensionality (2009, methodology): “In this section we discuss the choice of penalty functions in regularization methods and characterize the non-concave penalized likelihood estimator as well as its global optimality.”
- Non-negative least squares for high-dimensional linear models: consistency and sparse recovery without regularization (2012, background): “in [35, 52, 54, 61] to study the (ordinary) lasso from the point of view of support recovery.”