A fast algorithm for solving the lasso problem exactly without homotopy using differential inclusions
This provides a faster, more accurate solution for lasso problems, which are widely used in statistics and machine learning for feature selection and regularization.
The authors developed an exact algorithm for solving the lasso problem using differential inclusions, transforming it into an integrable projected dynamical system. Numerical experiments show it outperforms state-of-the-art methods in efficiency and accuracy.
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.