A fast algorithm for solving the lasso problem exactly without homotopy using differential inclusions
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The group fused Lasso for multiple change-point detection
We present the group fused Lasso for detection of multiple change-points shared by a set of co-occurring one-dimensional signals. Change-points are detected by approximating the original signals with a constraint on the …
Change Point DetectionA Fast Method for Lasso and Logistic Lasso
We propose a fast method for solving compressed sensing, Lasso regression, and Logistic Lasso regression problems that iteratively runs an appropriate solver using an active set approach. We design a strategy to update t…
compressed sensingregressionStability of a Generalized Debiased Lasso with Applications to Resampling-Based Variable Selection
Suppose that we first apply the Lasso to a design matrix, and then update one of its columns. In general, the signs of the Lasso coefficients may change, and there is no closed-form expression for updating the Lasso solu…
Variable SelectionA Fast and Flexible Algorithm for the Graph-Fused Lasso
We propose a new algorithm for solving the graph-fused lasso (GFL), a method for parameter estimation that operates under the assumption that the signal tends to be locally constant over a predefined graph structure. Our…
parameter estimationA path algorithm for the Fused Lasso Signal Approximator
The Lasso is a very well known penalized regression model, which adds an $L_{1}$ penalty with parameter $\lambda_{1}$ on the coefficients to the squared error loss function. The Fused Lasso extends this model by also put…
regression