{"id":2015,"date":"2026-04-20T13:34:33","date_gmt":"2026-04-20T11:34:33","guid":{"rendered":"https:\/\/lorentzen.ch\/?p=2015"},"modified":"2026-04-20T15:47:30","modified_gmt":"2026-04-20T13:47:30","slug":"gap-safe-screening-rules-for-the-lasso-landed-in-scikit-learn","status":"publish","type":"post","link":"https:\/\/lorentzen.ch\/index.php\/2026\/04\/20\/gap-safe-screening-rules-for-the-lasso-landed-in-scikit-learn\/","title":{"rendered":"Gap Safe Screening Rules for the Lasso landed in scikit-learn"},"content":{"rendered":"\n

In this post, we explore the topic of gap safe screening rules from convex optimisation and their impact on Lasso<\/a> and ElasticNet<\/a> in scikit-learn<\/a>.<\/p>\n\n\n\n

The Lasso in convex optimisation<\/h2>\n\n\n\n

As ordinary least squares<\/a> the Lasso<\/a> model consists of predictions X\\cdot\\beta<\/span><\/code> with feature matrix X \\in \\mathbb{R}^{n, p}<\/span><\/code> and fitted coefficients \\beta<\/span><\/code>. Given observations y<\/span><\/code>, the coefficients are estimated by solving the convex optimisation problem<\/p>\n\n\n\n

\\beta^\\star = \\argmin_\\beta \\left( P(\\beta)=\\frac{1}{2n} \\lVert y-X\\beta\\rVert_2^2 + \\alpha \\lVert\\beta\\rVert_1 \\right)<\/pre><\/div>\n\n\n\n
This is called the primal formulation<\/em> of the Lasso. For simplicity, we ignore an intercept (bias) term and assume that X<\/span><\/code> and y<\/span><\/code> are mean centered.<\/p>\n\n\n\n
The major tool we need in this post is the dual formulation<\/em>:<\/p>\n\n\n\n
\\nu^\\star = \\argmax_{\\{\\nu: \\lVert X'\\nu\\rVert_\\infty \\leq n\\alpha\\} } \\left( D(\\nu)=-\\frac{1}{2n} \\lVert \\nu\\rVert_2^2 + \\frac{1}{n} y\\cdot \\nu \\right)<\/pre><\/div>\n\n\n\n
This is an optimisation problem in terms of the dual variable \\nu<\/span><\/code> which has to be in the dual feasible set \\{\\nu: \\lVert X'\\nu\\rVert_\\infty \\leq n\\alpha\\}<\/span><\/code>.<\/p>\n\n\n\n
Now the wonderful theory of convex optimisation states:<\/p>\n\n\n
\n
Weak Duality<\/strong><\/p>\n\n\n\n
D(\\nu) \\leq P(\\beta^\\star)<\/pre><\/div>\n\n\n\n
for all feasible \\nu<\/span><\/code>, and with optimal \\beta^\\star<\/span><\/code>.<\/p>\n\n\n\n
Duality Gap<\/strong><\/p>\n\n\n\n
G(\\beta, \\nu) =P(\\beta) - D(\\nu) \\geq P(\\beta) - P(\\beta^\\star)\\geq 0<\/pre><\/div>\n\n\n\n
for feasible \\nu<\/span><\/code>.<\/p>\n\n\n<\/div>\n\n
\n
Strong Duality<\/strong><\/p>\n\n\n\n
D(\\nu^\\star) = P(\\beta^\\star)<\/pre><\/div>\n\n\n\n
This implies<\/p>\n\n\n\n
y - X\\beta^\\star = \\nu^\\star<\/pre><\/div>\n\n\n<\/div>\n\n\n
Both weak and strong duality hold for the Lasso. Weak duality acts as a lower bound for the optimal primal value. The duality gap<\/strong> is therefore a conservative proxy for how close a current iteration is from the optimum. It is a very good stopping criterion for algorithms. Other optimisation problems would wish to have such a good guarantee when to stop iterating.<\/p>\n\n\n\n
Screening rules in coordinate descent<\/h2>\n\n\n\n
The main algorithm to solver the Lasso is coordinate descent as implemented in many packages:<\/p>\n\n\n\n