# A fast algorithm for solving the lasso problem exactly without homotopy using differential inclusions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 52 references that are in the map.
- First posted on arXiv 8 Jul 2025.

## Builds on (most cited first, 7 of 7)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Sparse Regression: Scalable algorithms and empirical performance](https://mlsanity.com/paper/1902.06547/) (2019)
- [Black-box tests for algorithmic stability](https://mlsanity.com/paper/2111.15546/) (2021)
- [A Survey of Numerical Algorithms that can Solve the Lasso Problems](https://mlsanity.com/paper/2303.03576/) (2023)
- [Sparse linear regression from perturbed data](https://mlsanity.com/paper/2003.14389/) (2020)
- [IMRO: a proximal quasi-Newton method for solving l1-regularized least square problem](https://mlsanity.com/paper/1401.4220/) (2014)
- [The Homotopy Method Revisited: Computing Solution Paths of ℓ1-Regularized Problems](https://mlsanity.com/paper/1605.00071/) (2016)

## Abstract (arXiv)

We prove in this work that the well-known lasso problem can be solved exactly without homotopy using novel differential inclusions techniques. Specifically, we show that a selection principle from the theory of differential inclusions transforms the dual lasso problem into the problem of calculating the trajectory of a projected dynamical system that we prove is integrable. Our analysis yields an exact algorithm for the lasso problem, numerically up to machine precision, that is amenable to computing regularization paths and is very fast. Moreover, we show the continuation of solutions to the integrable projected dynamical system in terms of the hyperparameter naturally yields a rigorous homotopy algorithm. Numerical experiments confirm that our algorithm outperforms the state-of-the-art algorithms in both efficiency and accuracy. Beyond this work, we expect our results and analysis can be adapted to compute exact or approximate solutions to a broader class of polyhedral-constrained optimization problems.