Source-linked AI summary
Strong rules for discarding predictors in lasso-type problems
Robert Tibshirani, Jacob Bien, Jerome Friedman, Trevor Hastie, Noah Simon, Jonathan Taylor, Ryan J. Tibshirani
TL;DR
Lasso-type problems can be accelerated by discarding predictors that are likely to receive zero coefficients, but existing SAFE rules are conservative. The paper proposes stronger global and sequential rules, uses KKT checks to recover exactness, and reports substantial speed improvements despite rare rule violations.
Problem
Lasso-type optimization can be computationally expensive, motivating rules that discard predictors known or expected to have zero solution coefficients.
Method
The paper proposes strong global and sequential screening rules for lasso-type penalties and combines them with KKT-condition checks to verify the solution.
Results
The rules discard many variables, violations rarely occur in practice, and KKT-checked screening can substantially improve speed while yielding the exact solution.
Takeaways & Limitations
Strong screening rules provide a practical computational tool for lasso, elastic net, logistic regression, graphical lasso, and other convex optimization problems.
Takeaways & Limitations
The strong rules are not foolproof: their slope condition can be violated, particularly when p ≈ N and λ is small in the overfit regime.
Abstract
from arXiv · showhide
We consider rules for discarding predictors in lasso regression and related problems, for computational efficiency. El Ghaoui et al (2010) propose "SAFE" rules that guarantee that a coefficient will be zero in the solution, based on the inner products of each predictor with the outcome. In this paper we propose strong rules that are not foolproof but rarely fail in practice. These can be complemented with simple checks of the Karush- Kuhn-Tucker (KKT) conditions to provide safe rules that offer substantial speed and space savings in a variety of statistical convex optimization problems.
1 Introduction
The paper targets computational savings in lasso-type models by discarding predictors likely to have zero coefficients. It proposes strong rules that discard many variables, rarely violate practice, and work across several convex optimization problems when paired with KKT checks.
- Motivation: The lasso’s ℓ1 penalty produces exact zero coefficients, enabling variable selection and potentially substantial computational savings when those variables are discarded beforehand.The reduced problem uses only predictors outside the discarded set.
- Contribution: Strong rules discard more predictors than SAFE rules but can mistakenly exclude variables with nonzero solution coefficients.KKT conditions are used afterward to ensure the final coefficients are correct.
- Practical use: Sequential application along a grid of λ values substantially reduces computational time while retaining the exact solution after KKT validation.The paper presents this as the main practical use of the strong rules.
- Empirical behavior: Violations of the proposed rules are rare in practice, especially when p ≫ N.The paper reports that violations are virtually nonexistent in this regime.
- Scope: The rules are simple and apply to the elastic net, lasso-penalized logistic regression, and graphical lasso.The paper also develops rules for more general convex optimization problems.
2 Review of the SAFE rules
SAFE rules use a dual argument to identify predictors that are guaranteed to have zero lasso coefficients. Their safety comes with lower screening power than the strong sequential rule.
- Basic SAFE rule: The basic SAFE rule discards predictor j when its predictor-outcome inner product satisfies a bound involving λ.The rule is defined for a fit at tuning parameter λ.
- Optimality link: The primal-dual relationship links θ̂ to Xβ̂ − y, while each coefficient’s sign determines whether the corresponding dual coordinate equals ±λ or lies in [−λ, λ].A strict interior condition on the dual coordinate implies a zero coefficient.
- Dual argument: SAFE derives a screening condition from a dual feasible point and a lower bound on the dual objective.The bound is added without changing the dual optimum.
- Comparison: SAFE rules never discard predictors with truly nonzero coefficients, but they discard far fewer predictors than the strong sequential rule.This is the central safety-versus-screening trade-off described in the review.
3 Strong screening rules
The strong screening rules discard predictors using bounds on predictor–response inner products, with the sequential rule exploiting previously computed solutions along a decreasing λ path. They discard more variables than SAFE rules in practice, while KKT checks protect against occasional erroneous exclusions.
- Basic and strong sequential rules: The basic strong rule discards predictor j when its predictor–response inner product falls below a λ-dependent threshold.
- Basic and strong sequential rules: The strong rule generally discards more variables than SAFE when predictors are standardized, while ordering is less clear without standardization.With widely varying marginal variances, SAFE can outperform the basic strong rule, but the sequential strong rule remains the clear winner.
- Basic and strong sequential rules: The sequential strong rule uses the residual from a previous fit at λ0 to screen predictors for a smaller λ.Its buffer λ0−λ accounts for possible increases in the residual inner product along the path.
- Motivation for the strong rules: In four simulated lasso scenarios, the strong sequential rule discarded almost all predictors with zero coefficients, and no rule violations occurred.The scenarios varied N, p, predictor-matrix sparsity, and population feature correlation along decreasing λ paths.
- Motivation for the strong rules: The rule is motivated by bounding the slope of each inner product c_j(λ) by 1 between successive λ values.If c_j(λmax) is below 2λ1−λmax, the bound implies it cannot reach the critical level by λ1.
- Motivation for the strong rules: The slope condition can fail briefly, especially when p≈N and λ is small, so KKT checks are needed unless a sufficient design condition guarantees safety.Simulations found violations rare in practice and virtually nonexistent when p≫N.
4 Some analysis of the strong rules
The strong sequential rule can fail when the slope bound is violated, but a sufficient design condition guarantees the bound and simulations find violations rare, especially when p >> N.
- 4.2 A sufficient condition for the slope bound: A sufficient condition based on diagonal dominance guarantees the slope bound and prevents violations of both strong rules.For full-rank X with N ≥ p, diagonal dominance of (X^T X)^−1 yields the guarantee.
- 4.2 A sufficient condition for the slope bound: The diagonal-dominance condition holds for orthonormal designs, equi-correlation designs with r ≥ 0, and the Haar-basis model.The Haar-basis construction also arises in the one-dimensional fused lasso.
- 4.3 Connection to the irrepresentable condition: The slope condition resembles the irrepresentable condition, but it concerns the lasso-selected active set rather than the true model.Because the selected set is induced by the optimization procedure, its distribution is difficult to analyze directly.
5 Screening rules for the elastic net
For the elastic net, the paper applies SAFE and strong screening rules along decreasing λ paths; the strong sequential rule leaves few excess predictors and produced no violations in the reported scenarios.
- 5 Screening rules for the elastic net: The elastic-net screening rules use the same strong global and sequential rules as the lasso under the glmnet parametrization.The parametrization is ((1−α)λ, αλ) rather than (λ2, λ1).
- 5 Screening rules for the elastic net: No violations occurred in the three elastic-net scenarios, so no discarded predictor had a nonzero coefficient at the actual solution.The simulations use standard independent Gaussian data with n = 100 and p = 1000.
- 5 Screening rules for the elastic net: The strong sequential rule performed extremely well, leaving only a small number of excess predictors at each stage.The reported screening comparison concerns the number of predictors left after filtering.
- 5 Screening rules for the elastic net: Figure 7 compares screening rules across three mixing-parameter values by plotting predictors remaining after screening along decreasing λ paths.The plots also show the proportion of variance explained.
6 Screening rules for logistic regression
The paper extends strong screening rules to penalized logistic regression, deriving global and sequential rules and illustrating them on a sparse newsgroup classification problem.
- Logistic screening rules: The authors derive logistic-regression analogues of the strong global and sequential screening rules.The derivation begins from the logistic subgradient equation and defines a global rule using the response mean and λmax.
- Newsgroup example: The newsgroup example uses binary responses and predictors indicating tri-gram presence, with only 0.05% nonzero entries in the predictor matrix.The example compares the new global and sequential rules; the logistic global SAFE rule was not computed with the authors’ R implementation.
- Algorithmic context: Gaussian screening rules can also be applied within weighted least-squares iterations used by some penalized logistic-regression algorithms.This provides an alternative to applying the logistic-specific rules directly.
7 Strong rules for general problems
The paper generalizes strong screening rules from the lasso to convex problems, including the graphical lasso and group lasso, with row-and-column screening for blockwise optimization.
- General convex problems: A general strong rule follows from a subgradient equation f′(β) + λ · sk = 0 when subgradient variables satisfy a norm bound.The construction applies either globally or sequentially and reduces to the lasso rules when A = 1.
- Graphical lasso: For the graphical lasso, elementwise screening can be adapted to discard entire rows and columns because the optimization proceeds blockwise.The resulting sequential rule discards a row and column while retaining the diagonal element; no violations occurred in the reported example with N = 100 and p = 300.
- Group lasso: The same framework yields a strong sequential rule for group lasso by applying the screening condition to each design-matrix block.Here Xℓ denotes the block associated with the features in group ℓ.
8 Implementation and numerical studies
The implementation combines strong and ever-active sets with KKT checks, reducing the optimization problem substantially while preserving exactness after violations are repaired.
- Screening workflow: The strong sequential strategy solves on an eligible set and checks KKT conditions for all predictors, adding violators and repeating as needed.The strong set can be much smaller than p, although violations in the initial strong-set check are fairly common.
- Combined implementation: The glmnet implementation uses warm starts, an ever-active set, and repeated KKT checks while traversing decreasing λ values.The combined procedure alternates checks over the strong set and then all predictors, adding violations to the eligible or ever-active sets.
- Strong versus ever-active sets: The strong set contains more predictors than the ever-active set, while violations occur more often in the ever-active set in the correlated-feature example.The comparison is attributed to high feature correlation and the structure of the signal variables.
- Numerical studies: A speedup factor of five or more occurs in some benchmark problems, and the new strategy never seems to slow computation.The authors compare the strategy with the standard glmnet algorithm across Tables 1–3.
- Space savings: Strong sequential rules can also save space by computing screening inner products offline and optimizing in memory using only the retained predictors.This approach is proposed for large datasets.
9 Discussion
The paper concludes that strong global and sequential rules, combined with KKT checks, can accelerate convex optimization while still producing exact solutions, but one related rule lacks a correctness proof.
- Discussion: Combined strong rules and KKT checks offer substantial speed improvements while yielding the exact solution for statistical convex optimization problems such as the lasso.The authors planned to include the rules in a future version of glmnet.
- Caveat: The discussed sequential SAFE variant has no proof of correctness, although the authors found no numerical example in which it fails.The authors explicitly state that they do not know whether the rule is infallible.