Strong Rules for Discarding Predictors in Lasso-Type Problems
Top Cited Papers
- 3 November 2011
- journal article
- Published by Oxford University Press (OUP) in Journal of the Royal Statistical Society Series B: Statistical Methodology
- Vol. 74 (2), 245-266
- https://doi.org/10.1111/j.1467-9868.2011.01004.x
Abstract
Summary. We consider rules for discarding predictors in lasso regression and related problems, for computational efficiency. El Ghaoui and his colleagues have proposed ‘SAFE’ rules, based on univariate inner products between each predictor and the outcome, which guarantee that a coefficient will be 0 in the solution vector. This provides a reduction in the number of variables that need to be entered into the optimization. We propose strong rules that are very simple and yet screen out far more predictors than the SAFE rules. This great practical improvement comes at a price: the strong rules are not foolproof and can mistakenly discard active predictors, i.e. predictors that have non‐zero coefficients in the solution. We therefore combine them with simple checks of the Karush–Kuhn–Tucker conditions to ensure that the exact solution to the convex problem is delivered. Of course, any (approximate) screening method can be combined with the Karush–Kuhn–Tucker conditions to ensure the exact solution; the strength of the strong rules lies in the fact that, in practice, they discard a very large number of the inactive predictors and almost never commit mistakes. We also derive conditions under which they are foolproof. Strong rules provide substantial savings in computational time for a variety of statistical optimization problems.Keywords
Other Versions
Funding Information
- National Science Foundation (DMS-9971405, DMS-0906801)
- National Institutes of Health (N01-HV-28183)
This publication has 14 references indexed in Scilit:
- The solution path of the generalized lassoThe Annals of Statistics, 2011
- Near-ideal model selection by ℓ1 minimizationThe Annals of Statistics, 2009
- Sure Independence Screening for Ultrahigh Dimensional Feature SpaceJournal of the Royal Statistical Society Series B: Statistical Methodology, 2008
- Pathwise coordinate optimizationThe Annals of Applied Statistics, 2007
- High-dimensional graphs and variable selection with the LassoThe Annals of Statistics, 2006
- Just relax: convex programming methods for identifying sparse signals in noiseIEEE Transactions on Information Theory, 2006
- Recovery of Exact Sparse Representations in the Presence of Bounded NoiseIEEE Transactions on Information Theory, 2005
- Least angle regressionThe Annals of Statistics, 2004
- Atomic Decomposition by Basis PursuitSIAM Journal on Scientific Computing, 1998
- Regression Shrinkage and Selection Via the LassoJournal of the Royal Statistical Society: Series B (Methodological), 1996