Near-ideal model selection by ℓ1 minimization

By E.J. Candes, Yaniv Plan. 2008

234 citations recorded by the source corpus.

We consider the fundamental problem of estimating the mean of a vector y=Xβ+z, where X is an n×p design matrix in which one can have far more variables than observations, and z is a stochastic error term -— the so-called “p>n” setup. When β is sparse, or, more generally, when there is a sparse subset of covariates providing a close approximation to the unknown mean vector, we ask whether or not it is possible to accurately estimate Xβ using a computationally tractable algorithm. We show that, in a surprisingly wide range of situations, the lasso happens to nearly select the best subset of variables. Quantitatively speaking, we prove that solving a simple quadratic program achieves a squared error within a logarithmic factor of the ideal mean squared error that one would achieve with an oracle supplying perfect information about which variables should and should not be included in the model. Interestingly, our results describe the average performance of the lasso; that is, the performance one can expect in an vast majority of cases where Xβ is a sparse or nearly sparse superposition of variables, but not in all cases. Our results are nonasymptotic and widely applicable, since they simply require that pairs of predictor variables are not too collinear.

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

Best Subset Selection via a Modern Optimization Lens (2015, background): “There has been a substantial amount of impressive work on Lasso [Bickel, Ritov 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…”
The Lasso Problem and Uniqueness (2012, unknown): “For example, see Osborne et al. (2000 b ), Fuchs (2005), Wainwright (2009), Candes & Plan (2009).”
Robust Subspace Clustering (2013, unknown): “e solution to the noiseless projected problem (1) ∈argmin [(1 )[ ‘ 1 subject to y∥=Y (1 ∥ (1);(8.12) this is the solution to the projected problem as → 0+. With this, we proceed until (8.13) as in [10,11]. Since ^(1) is optimal for the reduced problem, 1 2 [y−Y(1)^(1)[ 2 ‘ 2 +[^(1)[ ‘ 1 ≤ 1 2 [y−Y(1”
Sparse Partially Linear Additive Models (2014, unknown): “(and others of its kind) make potentially strong (and unveriable) assumptions on the design matrix (e.g., the restricted isometry property [25], the compatibility condition [26, 27], small coherence [28], etc. See [29]). Since SPLAM’s design matrix consists of derived features, such assumptions beco”
Non-negative least squares for high-dimensional linear models: consistency and sparse recovery without regularization (2012, unknown): “bility condition’ [44, 45], which yields a bound on kβb− β∗k1 and an improved rate for the ℓ2-prediction error in the ﬂavour of sparsity oracle inequalities previously derived for the lasso, see e.g. [3, 7, 9, 44]. These works show that the lasso may adapt to the underlying sparsity, since, under ap”
SLOPE is Adaptive to Unknown Sparsity and Asymptotically Minimax (2015, methodology): “One can view the resolvent solution as a sophisticated type of a dual certificate method, better known as primal-dual witness method [22, 48, 55] in the statistics literature.”
Compressed Sensing with Coherent and Redundant Dictionaries (2010, unknown): “Standard results then require that the measurement matrix satisfy a strict incoherence property [41, 12], as even the RIP imposes this.”
Panning for Gold: Model-free Knockoffs for High-dimensional Controlled Variable Selection (2016, background): “Despite its simplicity, we have not seen this test proposed previously in the literature, although it nearly matches the usual randomization test when the covariates are independent of one another.”
A SIGNIFICANCE TEST FOR THE LASSO (2013, background): “…& Teboulle (2009), Friedman et al. (2010), Becker, Bobin & Candes (2011), Boyd et al. (2011), Becker, Candes & Grant (2011); and for theoretical work see, e.g., Greenshtein & Ritov (2004), Fuchs (2005), Donoho (2006), Candes & Tao (2006), Zhao & Yu (2006), Wainwright (2009), Candes & Plan (2009).”
Distributed Spectrum Sensing for Cognitive Radio Networks by Exploiting Sparsity (2010, background): “, [5], [7] and [20], prompted us to avoid this search through the use of convex reformulations of (6) that are particularly suitable when the vector of unknowns is sparse, and the locations of the nonzero entries in are unknown.”
Controlling the false discovery rate via knockoffs (2014, background): “, [5, 7, 30, 32]), and so even in a nonasymptotic setting, we will typically see”
Pivotal estimation via square-root Lasso in nonparametric regression (2011, methodology): “[23] studies plug-in estimators and a trade-off penalty choice between fit and penalty in the parametric case with homoscedastic Gaussian errors under random support assumption (similarly to [19]) using coherence condition.”
Structured Compressed Sensing: From Theory to Applications (2011, background): “are small enough, we will be able to recover the majority of K-sparse signals xfrom their measurements y. Probabilistic results that rely on coherence can also be obtained for the BPDN algorithm (13) [45]. The main difference between the guarantees that rely solely on coherence and those that rely o”