Quantum Algorithms for the Pathwise Lasso
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...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2025-03-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2025-03-25-1674/pdf/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849393379720298496 |
|---|---|
| author | Joao F. Doriguello Debbie Lim Chi Seng Pun Patrick Rebentrost Tushar Vaidya |
| author_facet | Joao F. Doriguello Debbie Lim Chi Seng Pun Patrick Rebentrost Tushar Vaidya |
| author_sort | Joao F. Doriguello |
| collection | DOAJ |
| description | 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 simple quantum minimum-finding subroutine from Dürr and Hoyer (arXiv'96) in order to obtain the joining time at each iteration. We then improve upon this simple quantum algorithm and obtain a quadratic speedup both in the number of features $d$ and the number of observations $n$ by using the approximate quantum minimum-finding subroutine from Chen and de Wolf (ICALP'23). In order to do so, we approximately compute the joining times to be searched over by the approximate quantum minimum-finding subroutine. As another main contribution, we prove, via an approximate version of the KKT conditions and a duality gap, that the LARS algorithm (and therefore our quantum algorithm) is robust to errors. This means that it still outputs a path that minimises the Lasso cost function up to a small error if the joining times are only approximately computed. Furthermore, we show that, when the observations are sampled from a Gaussian distribution, our quantum algorithm's complexity only depends polylogarithmically on $n$, exponentially better than the classical LARS algorithm, while keeping the quadratic improvement on $d$. Moreover, we propose a dequantised version of our quantum algorithm that also retains the polylogarithmic dependence on $n$, albeit presenting the linear scaling on $d$ from the standard LARS algorithm. Finally, we prove query lower bounds for classical and quantum Lasso algorithms. |
| format | Article |
| id | doaj-art-7b09cc57745d4d4f88f40af908288eeb |
| institution | Kabale University |
| issn | 2521-327X |
| language | English |
| publishDate | 2025-03-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj-art-7b09cc57745d4d4f88f40af908288eeb2025-08-20T03:40:25ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2025-03-019167410.22331/q-2025-03-25-167410.22331/q-2025-03-25-1674Quantum Algorithms for the Pathwise LassoJoao F. DoriguelloDebbie LimChi Seng PunPatrick RebentrostTushar VaidyaWe 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 simple quantum minimum-finding subroutine from Dürr and Hoyer (arXiv'96) in order to obtain the joining time at each iteration. We then improve upon this simple quantum algorithm and obtain a quadratic speedup both in the number of features $d$ and the number of observations $n$ by using the approximate quantum minimum-finding subroutine from Chen and de Wolf (ICALP'23). In order to do so, we approximately compute the joining times to be searched over by the approximate quantum minimum-finding subroutine. As another main contribution, we prove, via an approximate version of the KKT conditions and a duality gap, that the LARS algorithm (and therefore our quantum algorithm) is robust to errors. This means that it still outputs a path that minimises the Lasso cost function up to a small error if the joining times are only approximately computed. Furthermore, we show that, when the observations are sampled from a Gaussian distribution, our quantum algorithm's complexity only depends polylogarithmically on $n$, exponentially better than the classical LARS algorithm, while keeping the quadratic improvement on $d$. Moreover, we propose a dequantised version of our quantum algorithm that also retains the polylogarithmic dependence on $n$, albeit presenting the linear scaling on $d$ from the standard LARS algorithm. Finally, we prove query lower bounds for classical and quantum Lasso algorithms.https://quantum-journal.org/papers/q-2025-03-25-1674/pdf/ |
| spellingShingle | Joao F. Doriguello Debbie Lim Chi Seng Pun Patrick Rebentrost Tushar Vaidya Quantum Algorithms for the Pathwise Lasso Quantum |
| title | Quantum Algorithms for the Pathwise Lasso |
| title_full | Quantum Algorithms for the Pathwise Lasso |
| title_fullStr | Quantum Algorithms for the Pathwise Lasso |
| title_full_unstemmed | Quantum Algorithms for the Pathwise Lasso |
| title_short | Quantum Algorithms for the Pathwise Lasso |
| title_sort | quantum algorithms for the pathwise lasso |
| url | https://quantum-journal.org/papers/q-2025-03-25-1674/pdf/ |
| work_keys_str_mv | AT joaofdoriguello quantumalgorithmsforthepathwiselasso AT debbielim quantumalgorithmsforthepathwiselasso AT chisengpun quantumalgorithmsforthepathwiselasso AT patrickrebentrost quantumalgorithmsforthepathwiselasso AT tusharvaidya quantumalgorithmsforthepathwiselasso |