Quantum Algorithms for the Pathwise Lasso

arXiv:2312.14141v2 Announce Type: replace-cross
Abstract: We present a novel quantum high-dimensional linear regression algorithm with an $\ell_1$-penalty based on the classical LARS (Least Angle Regression) pathwise algorithm. Similarly to available classical algorithms for Lasso, our quantum algorithm provides the full regularisation path as the penalty term varies, but quadratically faster per iteration under specific conditions. A quadratic speedup on the number of features $d$ is possible by using the quantum minimum-finding routine from D\"urr and Hoyer (arXiv'96) in order to …

abstract algorithm algorithms arxiv cs.lg faster iteration lasso least linear linear regression math.oc novel path per quant-ph quantum regression replace stat.ml type