Optimal Sketching Bounds for Sparse Linear Regression

Abstract

We study oblivious sketching for $k$-sparse linear regression under various loss functions such as an ${\ell }_p$ norm, or from a broad class of hinge-like loss functions, which includes the logistic and ReLU losses. We show that for sparse ${\ell }_2$ norm regression, there is a distribution over oblivious sketches with $\Theta (k\log (d/k)/{\epsilon }^2)$ rows, which is tight up to a constant factor. This extends to ${\ell }_p$ loss with an additional additive $O(k\log (k/\epsilon )/{\epsilon }^2)$ term in the upper bound. This establishes a surprising separation from the related sparse recovery problem, which is an important special case of sparse regression. For this problem, under the ${\ell }_2$ norm, we observe an upper bound of $O(k\log (d)/\epsilon +k\log (k/\epsilon )/{\epsilon }^2)$ rows, showing that sparse recovery is strictly easier to sketch than sparse regression. For sparse regression under hinge-like loss functions including sparse logistic and sparse ReLU regression, we give the first known sketching bounds that achieve $o(d)$ rows showing that $O({\mu }^{2}k\log (\mu nd/\epsilon )/{\epsilon }^2)$ rows suffice, where $\mu$ is a natural complexity parameter needed to obtain relative error bounds for these loss functions. We again show that this dimension is tight, up to lower order terms and the dependence on $\mu$. Finally, we show that similar sketching bounds can be achieved for LASSO regression, a popular convex relaxation of sparse regression, where one aims to minimize $\Vert Ax-b{\Vert }_2^2+\lambda \Vert x{\Vert }_1$ over $x\in {\mathbb{R}}^d$. We show that sketching dimension $O(\log (d)/(\lambda \epsilon {)}^2)$ suffices and that the dependence on $d$ and $\lambda$ is tight.

arXiv commentAISTATS 2023

References in corpus (6)

• Sketching as a Tool for Numerical Linear Algebra
• Variable Selection is Hard
• On Coresets for Logistic Regression
• Lower Bound for RIP Constants and Concentration of Sum of Top Order Statistics
• $p$-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets
• On tails of symmetric and totally asymmetric $\alpha$-stable distributions