Screening Rules for Sparse GLM Fits

Why Screen Predictors Along a Lasso Path?

A lasso fit can be sparse, but fitting every predictor at every penalty value may still be expensive when the design has many columns. Along a decreasing sequence of penalty values, many predictors have scores far below the amount needed to enter the model. A screening rule uses information from a fit at a larger penalty to identify predictors that appear unlikely to be needed at the next fit.

The sequential strong rule is useful because its calculation is simple and often removes many predictors from the next optimization problem. Its name should not be read as a guarantee: unlike a safe screening rule, it can exclude a predictor that should be active. The remedy is to check the full Karush–Kuhn–Tucker (KKT) conditions after fitting and restore any excluded predictor that fails them.

Scores and the Lasso KKT Conditions

Write the objective at penalty $\lambda>0$ as a smooth convex loss plus an $\ell_1$ penalty:

Q_\lambda(\beta)=L(\beta)+\lambda\sum_{j=1}^p|\beta_j|.

Here $L$ is the negative log-likelihood, optionally divided by $n$, and the intercept, if present, is unpenalized. Let $g_j(\beta)=\partial L(\beta)/\partial\beta_j$ be the $j$th loss gradient, also called the negative score. The scaling of $L$ and $\lambda$ must match: changing from a total to an average negative log-likelihood changes the numerical penalty scale.

Theorem: Suppose $L$ is convex and differentiable, and the objective is the lasso objective above. A coefficient vector $\hat\beta$ minimizes $Q_\lambda$ if and only if, for each penalized coordinate $j$, $$ g_j(\hat\beta)+\lambda z_j=0,\qquad z_j= \begin{cases} \operatorname{sign}(\hat\beta_j),&\hat\beta_j\ne0,\\ \text{some value in }[-1,1],&\hat\beta_j=0. \end{cases} $$ Equivalently, $g_j(\hat\beta)=-\lambda\operatorname{sign}(\hat\beta_j)$ when $\hat\beta_j\ne0$, and $|g_j(\hat\beta)|\leq\lambda$ when $\hat\beta_j=0$. For an unpenalized intercept, its loss gradient must equal zero.

Proof. The subdifferential of $|b|$ is $\{\operatorname{sign}(b)\}$ for $b\ne0$, and $[-1,1]$ for $b=0$. The convex subgradient optimality condition for minimizing $L(\beta)+\lambda\sum_j|\beta_j|$ is therefore that zero belong to the sum of the gradient of $L$ and the penalty subdifferential. Coordinate by coordinate, this is exactly the displayed condition. For a convex function, this condition is both necessary and sufficient for a global minimum. $\square$

Deriving the Sequential Strong Rule

Suppose a fit at $\lambda_{\mathrm{old}}$ is available, and the next penalty is smaller, $\lambda_{\mathrm{new}}<\lambda_{\mathrm{old}}$. For a predictor inactive at the new fit, the KKT condition requires its new gradient magnitude to be at most $\lambda_{\mathrm{new}}$. The sequential strong rule estimates whether that condition is likely to hold by comparing the old gradient with a cutoff:

Definition: The sequential strong rule screens predictor $j$ at $\lambda_{\mathrm{new}}$ when $$ \left|g_j\!\left(\hat\beta(\lambda_{\mathrm{old}})\right)\right| <2\lambda_{\mathrm{new}}-\lambda_{\mathrm{old}}. $$ If the right-hand side is nonpositive, this rule screens no predictors. Predictors not screened are retained in the optimization problem.

The cutoff has a simple score-based motivation. Imagine that the gradient magnitude can change by no more than the penalty decrement $\lambda_{\mathrm{old}}-\lambda_{\mathrm{new}}$ between the two fits. Then the triangle inequality gives

|g_j(\hat\beta(\lambda_{\mathrm{new}}))| \leq |g_j(\hat\beta(\lambda_{\mathrm{old}}))| +\lambda_{\mathrm{old}}-\lambda_{\mathrm{new}}.

Thus, if the old magnitude is less than $\lambda_{\mathrm{new}}-(\lambda_{\mathrm{old}}-\lambda_{\mathrm{new}})$, the new magnitude must be less than $\lambda_{\mathrm{new}}$. Rearranging that sufficient bound gives $2\lambda_{\mathrm{new}}-\lambda_{\mathrm{old}}$, the strong-rule cutoff. The key limitation is that the presumed bound on gradient change is not guaranteed for general GLM paths. It motivates the rule; it does not prove that every screened predictor is inactive.

The same idea can be seen locally in a smooth loss. Along a path segment where the active set and coefficient signs stay fixed, the change in coefficients is governed by the loss Hessian on the active coordinates. The resulting change in an inactive coordinate’s gradient depends on cross-curvature between that coordinate and the active set. There is no general guarantee that this change is bounded by the penalty decrement in every coordinate and every GLM. Changes in active set or signs further limit what a local calculation can establish.

Worked Example: Screening With an Orthogonal Gaussian Design

Let $Y=X\beta+\varepsilon$, with independent errors $\varepsilon_i\sim N(0,1)$, and use the average squared-error loss $L(\beta)=\|y-X\beta\|^2/(2n)$. Take $n=4$ and columns $x_1=(1,1,-1,-1)^\mathsf{T}$, $x_2=(1,-1,1,-1)^\mathsf{T}$, and $x_3=(1,-1,-1,1)^\mathsf{T}$. Set $y=0.8x_1+0.25x_2-0.1x_3$. These columns are mutually orthogonal and each has squared length $4$, so the loss gradient at $\beta=0$ is $-X^\mathsf{T}y/4=(-0.8,-0.25,0.1)$.

At $\lambda_{\mathrm{old}}=0.8$, $\hat\beta=0$ satisfies the KKT conditions: every gradient magnitude is at most $0.8$. At $\lambda_{\mathrm{new}}=0.5$, the strong-rule cutoff is $2(0.5)-0.8=0.2$. Predictor 3 is screened because $0.1<0.2$; predictor 2 is retained because $0.25$ is not less than $0.2$, and predictor 1 is retained as well.

For this orthogonal design, the new solution can be checked directly by soft-thresholding each $x_j^\mathsf{T}y/4$ at $0.5$. The coefficients are $\hat\beta=(0.3,0,0)$. The gradients are $(-0.5,-0.25,0.1)$: the active coefficient has gradient $-0.5$, and the two zero coefficients have gradient magnitudes below $0.5$. The screened predictor satisfies its KKT condition in this example.

Using the Rule for GLM Paths

In a GLM, the score is evaluated at the current fitted means and linear predictors. For example, with a canonical-link logistic model and an average negative log-likelihood, the gradient for predictor $j$ is $-\sum_i x_{ij}(y_i-\hat\mu_i)/n$. The rule uses the absolute value of that gradient; it does not require Gaussian residuals or a squared-error objective. The likelihood, offsets, weights, and penalty scaling must all be handled consistently in the gradient calculation.

Worked Example: A Logistic Intercept-Only Starting Fit

Consider four independent Bernoulli outcomes $y=(0,0,1,1)$ and two predictor columns $x_1=(-1,-1,1,1)^\mathsf{T}$ and $x_2=(1,-1,1,-1)^\mathsf{T}$. At the intercept-only fit, the estimated success probability is $2/4=0.5$. The average-loss gradient for predictor $j$ is $-\sum_i x_{ij}(y_i-0.5)/4$.

For $x_1$, the sum before dividing by four is $(-1)(-0.5)+(-1)(-0.5)+(1)(0.5)+(1)(0.5)=2$. Thus $g_1=-2/4=-0.5$. For $x_2$, the corresponding sum is $(1)(-0.5)+(-1)(-0.5)+(1)(0.5)+(-1)(0.5)=0$, so $g_2=0$.

The largest gradient magnitude is $0.5$, so the all-zero slope vector satisfies the lasso KKT conditions at $\lambda_{\mathrm{old}}=0.5$. If the next penalty is $0.3$, the cutoff is $2(0.3)-0.5=0.1$. Predictor 2 is screened because $0<0.1$; predictor 1 is retained because $0.5$ is not below $0.1$. This is a screening decision based on the logistic score, not a claim that predictor 2 is certainly inactive at the next fit.

KKT Checks and Restoring Screened Predictors

After solving the reduced problem, calculate the gradient for every predictor, including those screened out. For an excluded predictor, its coefficient is currently zero, so its KKT condition is $|g_j(\hat\beta)|\leq\lambda$. If it fails, the reduced solution cannot be the full lasso solution. Add the violating predictor to the candidate set, refit, and check all predictors again. Continue until every active and inactive coordinate satisfies the KKT conditions, allowing for a stated numerical tolerance.

This check is an optimality test, not another heuristic. Under the convexity and differentiability conditions stated above, satisfying all KKT conditions certifies a global minimizer. The fitted coefficient vector need not be unique if the objective is not strictly convex, but any vector satisfying the conditions is a minimizer.

Worked Example: A Screened Predictor Fails the KKT Check

Consider a Gaussian lasso objective $L(\beta)=\tfrac12\beta^\mathsf{T}G\beta-c^\mathsf{T}\beta$, up to an additive constant, with

R= \begin{pmatrix} 1&0.9&0.2\\ 0.9&1&-0.2\\ 0.2&-0.2&1 \end{pmatrix}, \qquad G= \begin{pmatrix} 1&0.9&2\\ 0.9&1&-2\\ 2&-2&100 \end{pmatrix}, \qquad c= \begin{pmatrix}1\\-1\\0.1\end{pmatrix}.

Here $G=DRD$, where $D=\operatorname{diag}(1,1,10)$. The correlation matrix $R$ is positive definite: its leading principal minors are $1$, $1-0.9^2=0.19$, and $1+2(0.9)(0.2)(-0.2)-0.9^2-0.2^2-(-0.2)^2=0.038$, all positive. Consequently $G$ is positive definite as well, since it is obtained by an invertible diagonal rescaling. This is a strictly convex quadratic loss.

At $\lambda_{\mathrm{old}}=1$, $\beta=0$ is a solution: its gradient is $-c=(-1,1,-0.1)^\mathsf{T}$, whose coordinate magnitudes are all at most $1$. At $\lambda_{\mathrm{new}}=0.9$, the strong-rule cutoff is $2(0.9)-1=0.8$. Predictor 3 is screened because its old gradient magnitude is $0.1<0.8$. Predictors 1 and 2 are retained.

Solve the reduced problem with $\beta_3=0$. The candidate $(\beta_1,\beta_2)=(1,-1)$ has gradient components $g_1=1-0.9-1=-0.9$ and $g_2=0.9-1-(-1)=0.9$, exactly the required active-coordinate gradients for signs $+1$ and $-1$. But the omitted coordinate has $g_3=2(1)-2(-1)-0.1=3.9$. Since $3.9>0.9$, its KKT condition fails. The strong rule has made a false exclusion.

Restore predictor 3 and solve the full problem. The coefficient vector $(4,-4,-0.15)$ has the signs $(+1,-1,-1)$. Multiplication gives $G\beta=(0.1,-0.1,1)^\mathsf{T}$, so $g=G\beta-c=(-0.9,0.9,0.9)^\mathsf{T}$. These are precisely $-0.9$ times the three coefficient signs. The full KKT conditions hold, and strict convexity makes this the unique minimizer. The example also shows why penalty scaling and predictor scaling matter: the screening cutoff is applied to gradients in the units of the chosen objective.

Practical Screening Workflow and Common Pitfalls

Fit the larger-penalty model.
Save its coefficients, gradients, active set, and the exact loss and penalty scaling.

Apply the sequential cutoff.
For each predictor, compare its old gradient magnitude with $2\lambda_{\mathrm{new}}-\lambda_{\mathrm{old}}$. If the cutoff is nonpositive, screen none using this rule.

Fit the reduced problem.
Use the retained predictors to obtain a candidate solution at the new penalty.

Check the full KKT conditions.
Evaluate gradients for every predictor. Restore violations, refit, and repeat until all coordinates satisfy their conditions.

A common mistake is to treat a screened predictor as if it had been proved inactive. The incorrect reasoning is: “Its old score is below the strong-rule cutoff, so its new coefficient must be zero.” The cutoff follows from a plausible score-change bound, but that bound is not guaranteed for every GLM path. The correction is to regard screening only as a computational shortcut and perform the full KKT check before accepting the fit.

Other errors include comparing gradients from an average loss with a penalty defined for a total loss, forgetting that an intercept is unpenalized, and checking only predictors that were retained. Each can invalidate the claimed optimality check. In software, tolerances should be chosen relative to the objective scale; a check such as $|g_j|\leq\lambda+\epsilon$ for zero coefficients is a numerical approximation, not an exact inequality.

Key takeaway: The sequential strong rule uses the previous fit’s scores to make a fast, motivated guess about which predictors can be omitted at the next penalty. It does not certify those omissions. Full KKT checks and restoration of any violations are what make the final convex lasso fit valid.

Check Your Understanding

Use the definitions and calculations above to answer these questions.

For $\lambda_{\mathrm{old}}=0.7$ and $\lambda_{\mathrm{new}}=0.45$, what is the sequential strong-rule cutoff?
Why does the strong-rule inequality not prove that a screened predictor is inactive at the new fit?
At a lasso solution, what gradient condition must hold for a zero coefficient? What condition holds for a nonzero coefficient?
After a reduced fit, an omitted predictor has gradient magnitude $0.62$ at $\lambda=0.5$. What does the KKT check imply?
Why must the gradient and penalty use the same total-versus-average likelihood scaling?