mlsanityData to 14 Oct 2026

Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints

arXiv 2110.13086 ↗First posted 25 Oct 2021quant-ph cs.CC cs.DScited by 11

Not on the map. Why?

Abstract (arXiv)

Lasso and Ridge are important minimization problems in machine learning and statistics. They are versions of linear regression with squared loss where the vector θ∈ℝd of coefficients is constrained in either ℓ1-norm (for Lasso) or in ℓ2-norm (for Ridge). We study the complexity of quantum algorithms for finding varepsilon-minimizers for these minimization problems. We show that for Lasso we can get a quadratic quantum speedup in terms of d by speeding up the cost-per-iteration of the Frank-Wolfe algorithm, while for Ridge the best quantum algorithms are linear in d, as are the best classical algorithms. As a byproduct of our quantum lower bound for Lasso, we also prove the first classical lower bound for Lasso that is tight up to polylog-factors.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 16 of its 52 references that are in the map. First posted on arXiv 25 Oct 2021.

Builds on

16 of 52 references.

References · 16

  1. 2016Quantum Recommendation Systemscited by 70
  2. 2018The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulationcited by 30
  3. 2017Quantum SDP-Solvers: Better upper and lower boundscited by 27
  4. 2018Convex optimization using quantum oraclescited by 19
  5. 2018Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimensioncited by 18
  6. 2020Quantum Differentially Private Sparse Regression Learningcited by 18
  7. 2018Quantum algorithms and lower bounds for convex optimizationcited by 15
  8. 2020Quantum algorithms for escaping from saddle pointscited by 10
  9. 2019Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solvingcited by 8
  10. 2020Quantum Boostingcited by 8
  11. 2020Improved Quantum Boostingcited by 7
  12. 2020No quantum speedup over gradient descent for non-smooth convex optimizationcited by 6
4 more
  1. 2013An Equivalence between the Lasso and Support Vector Machinescited by 4
  2. 2019Quantum Sparse Support Vector Machinescited by 3
  3. 2020Quantum algorithms for matrix scaling and matrix balancingcited by 2
  4. 2021Improved quantum lower and upper bounds for matrix scalingcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 4; 2024: 2; 2025: 3; 2026: 2.

11 papers.

  1. 2023Improved machine learning algorithm for predicting ground state propertiescited by 22
  2. 2023Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameterscited by 7
  3. 2023Do you know what q-means?cited by 6
  4. 2024Quantum Algorithms and Lower Bounds for Finite-Sum Optimizationcited by 4
  5. 2023Quantum Algorithms for the Pathwise Lassocited by 2
  6. 2024Quantum Speedup for Spectral Approximation of Kronecker Productscited by 1
  7. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  8. 2026Sublinear Time Quantum Algorithm for Attention Approximationcited by 1
  9. 2025Quantum Algorithms for Projection-Free Sparse Convex Optimizationcited by 0
  10. 2025Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuitcited by 0
  11. 2026Improved Quantum Algorithms for Reinforcement Learning Under a Generative Modelcited by 0