Lasso and Ridge are important minimization problems in machine learning and statistics. They are versions of linear regression with squared loss where the vector θ ∈ Rd 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 ε-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.

, , , ,
Leibniz International Proceedings in Informatics
Quantum Software Consortium , Quantum algorithms and applications
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Algorithms and Complexity

Chen, Y., & de Wolf, R. (2023). Quantum algorithms and lower bounds for linear regression with norm constraints. In International Colloquium on Automata, Languages, and Programming (pp. 38:1–38:21). doi:10.4230/LIPIcs.ICALP.2023.38