The Hessian Screening Rule

Johan Larsson, Jonas WallinNeurIPS 2022

Introduction

When dealing with high-dimensional data—where the number of features ($p$) far exceeds the number of observations ($n$)—researchers often rely on sparse regression techniques like the Lasso to identify important predictors. However, solving this optimization problem across a sequence of decreasing penalty strengths (a "regularization path") is computationally expensive.

To accelerate this process, "screening rules" are employed to identify and discard predictors guaranteed or highly likely to have a coefficient of zero at the next step. Unfortunately, existing rules (like the Strong Rule) often become overly conservative when features are highly correlated, failing to discard enough predictors and bogging down the solver. The Hessian Screening Rule introduces a novel heuristic to overcome this by leveraging second-order information to discard irrelevant predictors before the model is even fit.

Methodology

The Hessian Screening Rule moves beyond the simple first-order gradient approximations used by traditional methods. It achieves this through several key innovations:

  • Second-Order Approximation: Instead of assuming linear gradient changes, the method uses a quadratic Taylor expansion involving the Hessian matrix (the matrix of second derivatives) to capture how predictors interact.
  • Active Set Efficiency: Calculating a full $p \times p$ Hessian is computationally prohibitive in high dimensions. The authors bypass this "curse of dimensionality" by only computing the Hessian for the active set (predictors currently in the model), which is typically very small.
  • Sequential Updates: Using the sweep operator and Schur complements, the algorithm incrementally updates the Hessian and its inverse as predictors enter or leave the model, avoiding costly recalculations.
  • Hessian Warm Starts: Beyond screening, the Hessian provides a highly accurate initial guess (warm start) for the coefficients at the next penalty step, drastically reducing the work required by the coordinate descent solver.
  • Safety Mechanisms: While the screening rule is technically a heuristic, the framework incorporates KKT optimality checks and "Gap Safe" screening to guarantee that the final solution remains mathematically exact.

Key Results and Insights

The authors evaluated the Hessian Screening Rule on simulated datasets with varying correlation levels ($\rho = 0, 0.4, 0.8$) and diverse real-world datasets for both regression and classification tasks.

Overcoming Correlation

Most screening rules fail under high correlation because they evaluate features in isolation. The Hessian naturally accounts for these interactions, allowing for much more aggressive and accurate screening. In high-correlation settings ($\rho = 0.8$), the Hessian rule maintains a working set with orders of magnitude fewer predictors compared to state-of-the-art competitors like Celer, Blitz, or the Strong Rule.

Number of predictors in the working set across different correlation levels.

Efficiency in Passes and Massive Speedups

A significant portion of the method's speedup stems from the "Hessian warm start." By accurately predicting coefficient movement, the algorithm starts much closer to the optimal solution. This frequently allows the solver to reach convergence in just 1-2 passes over the data, compared to the 10-30 passes required by standard warm starts.

Number of passes required for convergence using Hessian vs. Standard warm starts.

Consequently, the Hessian method achieves massive speedups on real-world data. For example, on the madelon dataset, it was 5x faster than the runner-up, and on the YearPredictionMSD dataset, it slashed computation time from over 500 seconds to just 78 seconds.

Limitations and Future Work

While highly effective, the approach has a few limitations:

  • Memory Overhead: Storing the Hessian and its inverse requires $O(|A|^2)$ memory. While the active set ($A$) is usually small, this could become a bottleneck for very dense models.
  • Sequential Constraint: The rule is optimized for sequential path-following and may be less effective for solving the Lasso at a single, isolated penalty value compared to dynamic rules.
  • Non-Smooth Objectives: Extending this framework to non-convex penalties (like SCAD) or non-differentiable losses remains an open challenge, though "approximate homotopy" presents a promising direction for future research.

Summary updated

BibTeX
@inproceedings{larsson2022hessian,
  author = {Johan Larsson and Jonas Wallin},
  title = {{The Hessian Screening Rule}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
}
Figure