Strong rules for discarding predictors in lasso-type problems

By Robert Tibshirani, Jacob Bien, Jerome H. Friedman, Trevor J. Hastie, Noah R. Simon, Jonathan E. Taylor. 2010

686 citations recorded by the source corpus.

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.

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

Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso (2017, neutral): “The base code for this is written in Fortran, and warm starts—plus additional tricks like active set optimization and screening rules (Tibshirani et al., 2012)—make this implementation highly efficient.”
Extension of SBL Algorithms for the Recovery of Block Sparse Signals With Intra-Block Correlation (2012, methodology): “Since each iteration is a Group-Lasso type problem, the optimal value of can be automatically selected in the Group Lasso framework [18].”
Safe Screening for Multi-Task Feature Learning with Multiple Data Matrices (2015, methodology): “The idea of screening has been shown to be very eﬀective in scaling the data and improving the eﬃciency of many popular sparse models, e.g., Lasso (El Ghaoui et al., 2012, Wang et al., 2013b, Wang et al., Xiang et al., 2011, Tibshirani et al., 2012), nonnegative Lasso Wang and Ye (2014), group Lasso”
Generalized Additive Model Selection (2015, methodology): “Strong rule for β j : Discard In the implementation of GAMSEL we adopt the approach recommended by the authors in section 7 of Tibshirani et al. (2012), which takes advantage of both active set methods and strong rules screening.”
Blitz: A Principled Meta-Algorithm for Scaling Sparse Optimization (2015, background): “• STRONG (Tibshirani et al., 2012): Like BLITZ but features are prioritized according to the " Strong Rule.”
Elastic Net Regularization Paths for All Generalized Linear Models (2021, methodology): “Here we describe one major computational trick that was not covered in that paper: the application of strong rules (Tibshirani, Bien, Friedman, Hastie, Simon, Taylor, and Tibshirani 2012).”
Coordinate Descent Methods for the Penalized Semiparametric Additive Hazards Model (2012, background): “Tibshirani et al. (2010) recently showed how to construct such a set.”
Frank-Wolfe with Subsampling Oracle (2018, background): “They are particularly effective when combined with variable screening rules such as (Tibshirani et al., 2012; Fercoq et al., 2015).”
Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions (2017, methodology): “For example, key practical speedups have been developed for coordinate descent for the lasso that enable this method to attain state-of-the-art performance at the right problem sizes, such as clever updating rules and screening rules (e.g., Friedman et al. 2010; El Ghaoui et al. 2012; Tibshirani et ”
The Statistics of Streaming Sparse Regression (2014, background): “[56] Robert Tibshirani, Jacob Bien, Jerome Friedman, Trevor Hastie, Noah Simon, Jonathan Taylor, and Ryan J Tibshirani.”
Benefit and harm of intensive blood pressure treatment: Derivation and validation of risk models using data from the SPRINT and ACCORD trials (2017, methodology): “Elastic net regularization is a statistical approach designed to select models in the context of collinearity, which produces challenges for older stepwise selection approaches [13,16].”
Handbook of Big Data (2016, background): “For certain loss functions and penalties, information from nearby λ values can be used to exclude certain parameters from consideration, thereby reducing the effective size of the problem (El Ghaoui et al., 2012; Tibshirani et al., 2012; Wang et al., 2013; Xiang et al., 2014).”