A fast algorithm for solving the lasso problem exactly without homotopy using differential inclusions
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915562607607808 |
|---|---|
| author | Langlois, Gabriel P. Darbon, Jérôme |
| author_facet | Langlois, Gabriel P. Darbon, Jérôme |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_05562 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A fast algorithm for solving the lasso problem exactly without homotopy using differential inclusions Langlois, Gabriel P. Darbon, Jérôme Optimization and Control Machine Learning Functional Analysis 90C25, 65K05, 37N40, 46N10, 34A60, 62J07 G.1.6; I.5.4 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. |
| title | A fast algorithm for solving the lasso problem exactly without homotopy using differential inclusions |
| topic | Optimization and Control Machine Learning Functional Analysis 90C25, 65K05, 37N40, 46N10, 34A60, 62J07 G.1.6; I.5.4 |
| url | https://arxiv.org/abs/2507.05562 |