Quantum Algorithms for the Pathwise Lasso

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 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.

54 pages. v2: several improvements, typos fixed, references added, fixed a bug in Theorem 28, exponentially improved the complexity dependence on the number of observations $n$ for a random Gaussian input matrix; v3: new lower bounds added, published version at Quantum Journal

References in corpus (45)

• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Quantum Computing in the NISQ era and beyond
• Quantum algorithm for solving linear systems of equations
• High-dimensional graphs and variable selection with the Lasso
• Interpretable machine learning: definitions, methods, and applications
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Quantum random access memory
• Hamiltonian Simulation by Qubitization
• Efficient quantum algorithms for simulating sparse Hamiltonians
• A note on the group lasso and a sparse group lasso
• A significance test for the lasso
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Data Fitting
• Piecewise linear regularized solution paths
• Architectures for a quantum random access memory
• Near-ideal model selection by ${\ell }_1$ minimization
• Compressed Sensing using Generative Models
• Prediction by linear regression on a quantum computer
• Exponential improvement in precision for simulating sparse Hamiltonians
• Quantum gradient descent for linear systems and least squares
• Quantum Algorithm for Linear Regression
• Improved Techniques for Training Score-Based Generative Models
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Lecture notes on ridge regression
• Complexity Analysis of the Lasso Regularization Path
• Invertible generative models for inverse problems: mitigating representation error and dataset bias
• Forward-Backward Selection with Early Dropping
• Quantum Regularized Least Squares
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization
• Quantum matching pursuit: A quantum algorithm for sparse representations
• Robust quantum minimum finding with an application to hypothesis selection
• Hybrid Quantum-Classical Algorithm For Robust Optimization via Stochastic-Gradient Online Learning
• Quantum speedup of leverage score sampling and its application
• On Model Selection Consistency of Lasso for High-Dimensional Ising Models

Cited by in corpus (1)

• Hybrid Quantum-Classical Algorithm For Robust Optimization via Stochastic-Gradient Online Learning