无需同伦法即可精确求解lasso问题，速度快精度高。
A fast algorithm for solving the lasso problem exactly without homotopy using differential inclusions
- 用微分包含新方法重构对偶lasso，转化为可积投影动力系统轨迹计算
- 算法在机器精度下精确求解，支持正则化路径计算，速度优于现有方法
- 适用于需要高精度解的优化场景，如变量选择与稀疏建模
本文证明，通过新颖的微分包含技术，可在不使用同伦法的情况下精确求解经典的lasso问题。具体而言，我们发现微分包含理论中的选择原则能将对偶lasso问题转化为计算一个可积投影动力系统轨迹的问题。该分析导出一个精确算法，数值上可达机器精度，且便于计算正则化路径，运行极为快速。此外，我们证明该可积投影动力系统解的延续性自然导出严格的同伦算法。数值实验表明，本算法在效率和精度上均超越当前最优方法。未来，该方法有望推广至更广泛的多面体约束优化问题，求解精确或近似解。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。