Strong rules for discarding predictors in lasso‐type problems

Authors: Tibshirani, Robert; Bien, Jacob; Friedman, Jerome; Hastie, Trevor; Simon, Noah; Taylor, Jonathan; Tibshirani, Ryan J.

Source: Journal of the Royal Statistical Society: Series B (Statistical Methodology), Volume 74, Number 2, 1 March 2012 , pp. 245-266(22)

Publisher: Wiley-Blackwell

Buy & download fulltext article:

OR

Price: $48.00 plus tax (Refund Policy)

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.

Document Type: Research Article

DOI: http://dx.doi.org/10.1111/j.1467-9868.2011.01004.x

Affiliations: Stanford University, USA

Publication date: March 1, 2012

Related content

Tools

Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content

Text size:

A | A | A | A
Share this item with others: These icons link to social bookmarking sites where readers can share and discover new web pages. print icon Print this page