# Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regression

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 44 references that are in the map.
- First posted on arXiv 31 Mar 2023.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Variance-based regularization with convex objectives](https://mlsanity.com/paper/1610.02581/) (2016)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more](https://mlsanity.com/paper/1802.07382/) (2018)
- [Input Sparsity and Hardness for Robust Subspace Approximation](https://mlsanity.com/paper/1510.06073/) (2015)
- [Dimensionality Reduction for Tukey Regression](https://mlsanity.com/paper/1905.05376/) (2019)
- [p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets](https://mlsanity.com/paper/2203.13568/) (2022)
- [Dimensionality Reduction for Sum-of-Distances Metric](https://mlsanity.com/paper/1912.12003/) (2019)
- [Exponentially Improved Dimensionality Reduction for ℓ1: Subspace Embeddings and Independence Testing](https://mlsanity.com/paper/2104.12946/) (2021)
- [Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching](https://mlsanity.com/paper/1504.01076/) (2015)
- [Stochastic Optimization for Non-convex Inf-Projection Problems](https://mlsanity.com/paper/1908.09941/) (2019)

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

- [Optimal Sketching Bounds for Sparse Linear Regression](https://mlsanity.com/paper/2304.02261/) (2023)
- [Scalable Learning of Item Response Theory Models](https://mlsanity.com/paper/2403.00680/) (2024)
- [Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentation](https://mlsanity.com/paper/2406.00328/) (2024)
- [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)
- [A Provably Accurate Randomized Sampling Algorithm for Logistic Regression](https://mlsanity.com/paper/2402.16326/) (2024)
- [Private Sketches for Linear Regression](https://mlsanity.com/paper/2511.07365/) (2025)
- [Scalable Learning of Multivariate Distributions via Coresets](https://mlsanity.com/paper/2603.19792/) (2026)

## Abstract (arXiv)

We improve upon previous oblivious sketching and turnstile streaming results for ℓ1 and logistic regression, giving a much smaller sketching dimension achieving O(1)-approximation and yielding an efficient optimization problem in the sketch space. Namely, we achieve for any constant c>0 a sketching dimension of tildeO(d1+c) for ℓ1 regression and tildeO(μ d1+c) for logistic regression, where μ is a standard measure that captures the complexity of compressing the data. For ℓ1-regression our sketching dimension is near-linear and improves previous work which either required Omega(log d)-approximation with this sketching dimension, or required a larger operatornamepoly(d) number of rows. Similarly, for logistic regression previous work had worse operatornamepoly(μ d) factors in its sketching dimension. We also give a tradeoff that yields a 1+varepsilon approximation in input sparsity time by increasing the total size to (dlog(n)/varepsilon)O(1/varepsilon) for ℓ1 and to (μ dlog(n)/varepsilon)O(1/varepsilon) for logistic regression. Finally, we show that our sketch can be extended to approximate a regularized version of logistic regression where the data-dependent regularizer corresponds to the variance of the individual logistic losses.