# Celer: a Fast Solver for the Lasso with Dual Extrapolation

arXiv: https://arxiv.org/abs/1802.07481 · HTML: https://mlsanity.com/paper/1802.07481/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2018.

## Built on by (most cited first, 30 of 31)

- [Datamodels: Predicting Predictions from Training Data](https://mlsanity.com/paper/2202.00622/) (2022)
- [LassoBench: A High-Dimensional Hyperparameter Optimization Benchmark Suite for Lasso](https://mlsanity.com/paper/2111.02790/) (2021)
- [Unbalanced Optimal Transport through Non-negative Penalized Linear Regression](https://mlsanity.com/paper/2106.04145/) (2021)
- [Benchopt: Reproducible, efficient and collaborative optimization benchmarks](https://mlsanity.com/paper/2206.13424/) (2022)
- [Implicit differentiation for fast hyperparameter selection in non-smooth convex learning](https://mlsanity.com/paper/2105.01637/) (2021)
- [abess: A Fast Best Subset Selection Library in Python and R](https://mlsanity.com/paper/2110.09697/) (2021)
- [Beyond L1: Faster and Better Sparse Models with skglm](https://mlsanity.com/paper/2204.07826/) (2022)
- [Smooth Bilevel Programming for Sparse Regularization](https://mlsanity.com/paper/2106.01429/) (2021)
- [Smooth over-parameterized solvers for non-smooth structured optimization](https://mlsanity.com/paper/2205.01385/) (2022)
- [Differentially Private Coordinate Descent for Composite Empirical Risk Minimization](https://mlsanity.com/paper/2110.11688/) (2021)
- [Anytime Model Selection in Linear Bandits](https://mlsanity.com/paper/2307.12897/) (2023)
- [Meta-Learning Hypothesis Spaces for Sequential Decision-making](https://mlsanity.com/paper/2202.00602/) (2022)
- [Representational Similarity via Interpretable Visual Concepts](https://mlsanity.com/paper/2503.15699/) (2025)
- [Hybrid ISTA: Unfolding ISTA With Convergence Guarantees Using Free-Form Deep Neural Networks](https://mlsanity.com/paper/2204.11640/) (2022)
- [Lifelong Bandit Optimization: No Prior and No Regret](https://mlsanity.com/paper/2210.15513/) (2022)
- [High Dimensional Bayesian Optimization using Lasso Variable Selection](https://mlsanity.com/paper/2504.01743/) (2025)
- [The Hessian Screening Rule](https://mlsanity.com/paper/2104.13026/) (2021)
- [Continuation Path with Linear Convergence Rate](https://mlsanity.com/paper/2112.05104/) (2021)
- [Efficient Algorithms for Regularized Nonnegative Scale-invariant Low-rank Approximation Models](https://mlsanity.com/paper/2403.18517/) (2024)
- [Enhanced Cyclic Coordinate Descent Methods for Elastic Net Penalized Linear Models](https://mlsanity.com/paper/2510.19999/) (2025)
- [OmiTrans: generative adversarial networks based omics-to-omics translation framework](https://mlsanity.com/paper/2111.13785/) (2021)
- [Best Subset Selection with Efficient Primal-Dual Algorithm](https://mlsanity.com/paper/2207.02058/) (2022)
- [On Inductive Biases for Machine Learning in Data Constrained Settings](https://mlsanity.com/paper/2302.10692/) (2023)
- [Safe Screening for Unbalanced Optimal Transport](https://mlsanity.com/paper/2307.00247/) (2023)
- [Dynamic Incremental Optimization for Best Subset Selection](https://mlsanity.com/paper/2402.02322/) (2024)
- [Efficient Low-rank Identification via Accelerated Iteratively Reweighted Nuclear Norm Minimization](https://mlsanity.com/paper/2406.15713/) (2024)
- [Efficient Solvers for SLOPE in R, Python, Julia, and C++](https://mlsanity.com/paper/2511.02430/) (2025)
- [Renet: Principled and Efficient Relaxation for the Elastic Net via Dynamic Objective Selection](https://mlsanity.com/paper/2602.11107/) (2026)
- [Sparse Additive Model Pruning for Order-Based Causal Structure Learning](https://mlsanity.com/paper/2602.15306/) (2026)
- [Data-driven configuration tuning of glmnet for balancing accuracy and computational efficiency](https://mlsanity.com/paper/2602.17922/) (2026)

## Abstract (arXiv)

Convex sparsity-inducing regularizations are ubiquitous in high-dimensional machine learning, but solving the resulting optimization problems can be slow. To accelerate solvers, state-of-the-art approaches consist in reducing the size of the optimization problem at hand. In the context of regression, this can be achieved either by discarding irrelevant features (screening techniques) or by prioritizing features likely to be included in the support of the solution (working set techniques). Duality comes into play at several steps in these techniques. Here, we propose an extrapolation technique starting from a sequence of iterates in the dual that leads to the construction of improved dual points. This enables a tighter control of optimality as used in stopping criterion, as well as better screening performance of Gap Safe rules. Finally, we propose a working set strategy based on an aggressive use of Gap Safe screening rules. Thanks to our new dual point construction, we show significant computational speedups on multiple real-world problems.