# Optimal Sketching Bounds for Sparse Linear Regression

arXiv: https://arxiv.org/abs/2304.02261 · HTML: https://mlsanity.com/paper/2304.02261/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 65 references that are in the map.
- First posted on arXiv 5 Apr 2023.

## Builds on (most cited first, 17 of 17)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Lower bounds for oblivious subspace embeddings](https://mlsanity.com/paper/1308.3280/) (2013)
- [Optimal terminal dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1810.09250/) (2018)
- [p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets](https://mlsanity.com/paper/2203.13568/) (2022)
- [Approximate Sparse Linear Regression](https://mlsanity.com/paper/1609.08739/) (2016)
- [Adaptive Feature Selection: Computationally Efficient Online Sparse Linear Regression under RIP](https://mlsanity.com/paper/1706.04690/) (2017)
- [Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regression](https://mlsanity.com/paper/2304.00051/) (2023)
- [Principal Component Analysis and Higher Correlations for Distributed Data](https://mlsanity.com/paper/1304.3162/) (2013)
- [Exponentially Improved Dimensionality Reduction for ℓ1: Subspace Embeddings and Independence Testing](https://mlsanity.com/paper/2104.12946/) (2021)
- [Tight Bounds for ℓp Oblivious Subspace Embeddings](https://mlsanity.com/paper/1801.04414/) (2018)
- [Sparse PCA from Sparse Linear Regression](https://mlsanity.com/paper/1811.10106/) (2018)
- [Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching](https://mlsanity.com/paper/1504.01076/) (2015)

## Built on by (most cited first, 6 of 6)

- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)
- [Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves](https://mlsanity.com/paper/2505.23431/) (2025)
- [Hardness of High-Dimensional Linear Classification](https://mlsanity.com/paper/2603.19061/) (2026)
- [Beyond Worst-Case Dimensionality Reduction for Sparse Vectors](https://mlsanity.com/paper/2502.19865/) (2025)
- [Scalable Learning of Multivariate Distributions via Coresets](https://mlsanity.com/paper/2603.19792/) (2026)
- [Dimension Reduction for Curves: Simplified and Generalized](https://mlsanity.com/paper/2607.03112/) (2026)

## Abstract (arXiv)

We study oblivious sketching for k-sparse linear regression under various loss functions such as an ℓp norm, or from a broad class of hinge-like loss functions, which includes the logistic and ReLU losses. We show that for sparse ℓ2 norm regression, there is a distribution over oblivious sketches with Theta(klog(d/k)/varepsilon2) rows, which is tight up to a constant factor. This extends to ℓp loss with an additional additive O(klog(k/varepsilon)/varepsilon2) 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 ℓ2 norm, we observe an upper bound of O(k log (d)/varepsilon + klog(k/varepsilon)/varepsilon2) 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(μ2 klog(μ n d/varepsilon)/varepsilon2) rows suffice, where μ 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 μ. 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 |Ax-b|22+λ|x|1 over x∈ℝd. We show that sketching dimension O(log(d)/(λ varepsilon)2) suffices and that the dependence on d and λ is tight.