# Quantum Algorithms for the Pathwise Lasso

arXiv: https://arxiv.org/abs/2312.14141 · HTML: https://mlsanity.com/paper/2312.14141/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 130 references that are in the map.
- First posted on arXiv 21 Dec 2023.

## Builds on (most cited first, 20 of 20)

- [Improved Techniques for Training Score-Based Generative Models](https://mlsanity.com/paper/2006.09011/) (2020)
- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Interpretable machine learning: definitions, methods, and applications](https://mlsanity.com/paper/1901.04592/) (2019)
- [Invertible generative models for inverse problems: mitigating representation error and dataset bias](https://mlsanity.com/paper/1905.11672/) (2019)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [A framework to characterize performance of LASSO algorithms](https://mlsanity.com/paper/1303.7291/) (2013)
- [The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation](https://mlsanity.com/paper/1804.01973/) (2018)
- [Quantum SDP-Solvers: Better upper and lower bounds](https://mlsanity.com/paper/1705.01843/) (2017)
- [A significance test for the lasso](https://mlsanity.com/paper/1301.7161/) (2013)
- [Algorithms for Fitting the Constrained Lasso](https://mlsanity.com/paper/1611.01511/) (2016)
- [Forward-Backward Selection with Early Dropping](https://mlsanity.com/paper/1705.10770/) (2017)
- [Lecture notes on ridge regression](https://mlsanity.com/paper/1509.09169/) (2015)
- [Efficient Implementations of the Generalized Lasso Dual Path Algorithm](https://mlsanity.com/paper/1405.3222/) (2014)
- [Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints](https://mlsanity.com/paper/2110.13086/) (2021)
- [Quantum Regularized Least Squares](https://mlsanity.com/paper/2206.13143/) (2022)
- [Pathwise Coordinate Optimization for Sparse Learning: Algorithm and Theory](https://mlsanity.com/paper/1412.7477/) (2014)
- [Robust quantum minimum finding with an application to hypothesis selection](https://mlsanity.com/paper/2003.11777/) (2020)
- [On Model Selection Consistency of Lasso for High-Dimensional Ising Models](https://mlsanity.com/paper/2110.08500/) (2021)
- [Hybrid Quantum-Classical Algorithm For Robust Optimization via Stochastic-Gradient Online Learning](https://mlsanity.com/paper/2304.02262/) (2023)

## Built on by (most cited first, 2 of 2)

- [Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent](https://mlsanity.com/paper/2411.03925/) (2024)
- [Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit](https://mlsanity.com/paper/2510.06925/) (2025)

## Abstract (arXiv)

We present a novel quantum high-dimensional linear regression algorithm with an ℓ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"urr 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.