Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints

Yanlin Chen, Ronald de Wolf

Lasso and Ridge are important minimization problems in machine learning and statistics. They are versions of linear regression with squared loss where the vector $\theta \in {\mathbb{R}}^d$…