2025/07/08 by Gabriel P. Langlois, Langlois, Gabriel P., Jérôme Darbon +1 · 1 citation
Computer Science · Engineering · Mathematics · #34A60 #37N40 #46N10 #62J07 #65K05 #90C25 #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #G.1.6 #I.5.4 #Machine Learning (cs.LG) #Numerical methods in inverse problems #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2507.05562
openalex publication_date 2025/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.