Source-linked AI summary
Mind the duality gap: safer rules for the Lasso
Olivier Fercoq, Alexandre Gramfort, Joseph Salmon
TL;DR
The paper addresses the computational cost of solving many high-dimensional Lasso problems while retaining safe variable screening. It introduces GAP SAFE rules based on duality gaps and converging safe regions, then evaluates them with coordinate descent. The rules identify optimal active sets in finite time and deliver substantial computational savings on standard datasets.
Problem
Solving many high-dimensional Lasso problems remains computationally costly, motivating faster screening methods that safely discard irrelevant variables.
Method
GAP SAFE rules use duality-gap computations to create converging safe regions and unify sequential and dynamic screening strategies.
Results
The rules identify optimal active sets in finite time and achieve up to 3x speedup at duality gap 10^-4, including 11x on Leukemia at accuracy 10^-8.
Takeaways & Limitations
Safe screening becomes increasingly precise during optimization and can substantially reduce computation time for Lasso paths.
Takeaways & Limitations
The evaluation excludes unsafe strong rules and the sequential rule of Wang et al. because their practical requirements differ from the proposed safe strategy.
Abstract
from arXiv · showhide
Screening rules allow to early discard irrelevant variables from the optimization in Lasso problems, or its derivatives, making solvers faster. In this paper, we propose new versions of the so-called $\textit{safe rules}$ for the Lasso. Based on duality gap considerations, our new rules create safe test regions whose diameters converge to zero, provided that one relies on a converging solver. This property helps screening out more variables, for a wider range of regularization parameter values. In addition to faster convergence, we prove that we correctly identify the active sets (supports) of the solutions in finite time. While our proposed strategy can cope with any solver, its performance is demonstrated using a coordinate descent algorithm particularly adapted to machine learning use cases. Significant computing time reductions are obtained with respect to previous safe rules.
1. Introduction
The Lasso is widely used for sparse high-dimensional regression, but solving many large problems remains computationally demanding. This paper introduces GAP SAFE rules that use duality gaps to improve safe screening during optimization and reports practical speedups over prior safe rules.
- Motivation: Safe screening discards features guaranteed to be zero in the optimal Lasso solution, reducing the computational burden while preserving safety.Unlike unsafe strong rules, safe rules guarantee that screened coefficients are zero in the targeted optimum.
- Prior screening strategies: Static safe rules screen once before optimization, whereas sequential and dynamic strategies improve screening across tuning parameters or as optimization progresses.Sequential rules exploit neighboring regularization parameters, while dynamic rules interlace screening with solver iterations.
- Contribution: GAP SAFE rules use duality-gap computations to unify sequential and dynamic safe screening strategies.The framework is based on convex optimization arguments and defines new safe rules for the Lasso.
- Contribution: The paper defines converging safe rules whose safe-region diameters shrink to zero, enabling increasingly precise tests and finite-time identification of the optimal active set.The rules are built on dual-gap computations and can be applied with a coordinate-descent solver.
2. Safe rules
Safe rules construct regions containing the unknown dual optimum and screen variables guaranteed to be zero. Smaller regions improve screening, while dynamic rules refine these regions during optimization using dual-feasible iterates.
- Safe regions: Safe rules use a region containing the dual optimum to identify variables guaranteed to have zero Lasso coefficients.The screening test is based on the region’s support function and partitions variables into safe active and safe zero sets.
- Safe regions: Narrower safe regions can screen out more variables because nested regions produce nested safe active sets.For a fixed center, sphere tests also improve as their radius decreases.
- Static and dynamic rules: Static sphere and dome tests perform screening before optimization, whereas dynamic rules use iterates to construct regions that narrow as the algorithm progresses.Dynamic rules require dual-feasible points derived from current residuals.
- Dynamic safe rules: The dynamic dual iterate is proportional to the current residual and converges to the dual optimum when the primal iterates converge.Safe screening does not disrupt primal convergence and can reduce the distance to the target solution.
- Dynamic safe rules: Earlier dynamic screening becomes inefficient below a problem-dependent regularization threshold, and the threshold cannot be evaluated in advance because it depends on the unknown dual optimum norm.The screening may stop even at a larger regularization parameter than the critical threshold.
3. New contributions on safe rules
The paper introduces GAP SAFE regions based on duality gaps, whose diameters converge to zero under convergent optimization and enable finite-time active-set identification. The framework supports dynamic and sequential screening, including when prior solutions are only approximate.
- 3.1. Support discovery in finite time: Converging safe regions identify the Lasso equicorrelation set exactly after finitely many iterations.The estimated support converges to the equicorrelation set and equals it from some finite iteration onward.
- 3.3. GAP SAFE rules : sequential for free: The framework is solver-independent provided the safe-region sequence converges, covering methods such as coordinate descent, Forward-Backward, and primal-dual algorithms.The paper separately proposes coordinate descent for its Lasso application.
- 3.2. GAP SAFE regions: leveraging the duality gap: GAP SAFE regions use current primal and dual estimates in place of unknown oracle solutions, making their radii shrink with the duality gap.Choosing the unknown optimal primal and dual points would yield zero radius; available iterates provide the practical construction.
- 3.2. GAP SAFE regions: leveraging the duality gap: GAP SAFE spheres and domes are converging safe regions whenever the primal and dual sequences converge.The dome inherits convergence because it is included in the GAP SAFE sphere.
- 3.2. GAP SAFE regions: leveraging the duality gap: The GAP SAFE radius converges to zero, whereas the compared dynamic-rule radii converge to positive limits.This gives GAP SAFE regions increasingly precise tests as optimization proceeds.
- 3.3. GAP SAFE rules : sequential for free: GAP SAFE screening is sequential by nature and can warm-start a new tuning parameter from an approximate solution at the previous one.Unlike earlier sequential rules, it remains safe without exact prior primal and dual optima.
4. Experiments
Experiments show that GAP SAFE screening improves variable elimination and computation time across dense and sparse Lasso problems, while screening also reduces stopping-criterion costs.
- 4.1. Coordinate Descent: The implementation combines Scikit-learn coordinate descent with Cython and separate dense and sparse data representations.Dynamic screening tests are performed every 10 passes through the full active set.
- 4.1. Coordinate Descent: Screening reduces dual-gap evaluation from O(np) to O(nq), where q is the number of retained variables.This makes screening beneficial for evaluating the stopping criterion as well as for coordinate updates.
- 4.3. Gains in the computation of Lasso paths: The experiments exclude strong rules and the sequential rule of Wang et al. because the former are not safe and the latter requires an unavailable exact dual solution.The authors report that the latter requirement could prevent solver convergence in their experiments.
- 4.2. Number of screened variables: GAP SAFE tests screen more variables as optimization proceeds, especially for small λ where other rules initially screen none.The GAP SAFE dome provides only marginal improvement over the sphere on Leukemia.
- 4.3. Gains in the computation of Lasso paths: Up to 11x faster computation was obtained with GAP SAFE sphere than competing methods on Leukemia at accuracy 10^-8.Across datasets, speedups reached 3x at duality gap 10^-4, with larger gains when p is larger relative to n.
- 4.3. Gains in the computation of Lasso paths: Other safe rules showed little speedup because they often retain all active variables across a wide λ range while still incurring screening costs.Their advantage is limited to larger λ values and diminishes afterward.
5. Conclusion
The paper introduces converging GAP SAFE rules based on duality gaps and demonstrates their practical benefits for accelerating Lasso solvers. The framework is applied with coordinate descent on dense and sparse datasets, with extensions proposed for generalized linear models and group-Lasso.
- 5. Conclusion: The paper introduces converging safe rules and uses duality gaps to construct GAP SAFE sphere and dome tests.Their safe regions have diameters converging to zero.
- 5. Conclusion: Coordinate descent experiments on standard dense and sparse datasets demonstrate important practical benefits for Lasso optimization.
- 5. Conclusion: Future work will extend the framework to generalized linear models and group-Lasso.
A.1. Dome test
The dome test uses a safe region parameterized by a center, radius, relative distance ratio, and unit normal vector, then evaluates feature-specific support functions for screening.
- A.1. Dome test: The dome safe region is parameterized by center c, radius r, ratio α, and unit normal vector w.These parameters are defined from y, λ, θ, and the radius quantities Rλ(θ) and qRλ(θ).
- A.1. Dome test: The dome test computes μ_C(x_j) as the maximum of the support functions for x_j and -x_j.This yields the feature-screening quantity used by the rule.
- A.1. Dome test: Optimizing over the introduced dome is sufficient because a set and its closed convex hull have the same support function.The paper therefore does not improve the result by optimizing over the corresponding ball intersection region.
A.2. Proof of Theorem 1
Because the safe regions converge to the dual optimum, the screening tests eventually identify every inactive variable and thus recover the active set in finite time.
- A.2. Proof of Theorem 1: The converging safe regions eventually screen every inactive variable whose dual correlation is strictly below one.The proof bounds the correlation deviation by the shrinking region diameter.
- A.2. Proof of Theorem 1: The result follows because the dual optimum remains inside every safe region while the regions’ diameters converge to zero.This establishes finite-time identification of the active variables or, equivalently, inactive variables.
A.3. Proof of Proposition 3
The section details the proof of Proposition 3 by applying an initial fact, handling a dot product, and concluding with an observation.
- The proof begins by invoking a stated fact to establish the proposition's intermediate relation.
- The derivation uses expressions involving the residual norm, the L1 norm, and the dual variable.
- A term involving the difference between consecutive regularization parameters and the dual vector is introduced in the proof.
- The proof separately analyzes the resulting dot product.
- The section ends by recording an observation that completes the proof argument.
A.4. Elastic-Net
The paper extends its screening tests to the Elastic-Net estimator by reformulating the Elastic-Net problem as a Lasso problem.
- The previously proposed screening tests can be adapted to the Elastic-Net estimator.
- The Elastic-Net objective combines a squared-error term, an L1 penalty weighted by λα, and an L2 penalty weighted by λ(1 − α).
- The Elastic-Net problem can be reformulated as a Lasso problem.
- The reformulation augments the design matrix and response, after which the Lasso tests can be adapted.