# Oblivious sketching for logistic regression

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 51 references that are in the map.
- First posted on arXiv 14 Jul 2021.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Coresets for Scalable Bayesian Logistic Regression](https://mlsanity.com/paper/1605.06423/) (2016)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [Training (Overparametrized) Neural Networks in Near-Linear Time](https://mlsanity.com/paper/2006.11648/) (2020)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [Coresets for Near-Convex Functions](https://mlsanity.com/paper/2006.05482/) (2020)
- [Online Row Sampling](https://mlsanity.com/paper/1604.05448/) (2016)
- [Dimensionality Reduction for Tukey Regression](https://mlsanity.com/paper/1905.05376/) (2019)
- [Streaming Coresets for Symmetric Tensor Factorization](https://mlsanity.com/paper/2006.01225/) (2020)
- [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)
- [Random Projections and Sampling Algorithms for Clustering of High-Dimensional Polygonal Curves](https://mlsanity.com/paper/1907.06969/) (2019)
- [Random projections for Bayesian regression](https://mlsanity.com/paper/1504.06122/) (2015)
- [Subspace Embeddings Under Nonlinear Transformations](https://mlsanity.com/paper/2010.02264/) (2020)
- [The One-Way Communication Complexity of Dynamic Time Warping Distance](https://mlsanity.com/paper/1903.03520/) (2019)

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

- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets](https://mlsanity.com/paper/2203.13568/) (2022)
- [Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regression](https://mlsanity.com/paper/2304.00051/) (2023)
- [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)
- [Feature Space Sketching for Logistic Regression](https://mlsanity.com/paper/2303.14284/) (2023)
- [No Dimensional Sampling Coresets for Classification](https://mlsanity.com/paper/2402.05280/) (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)
- [Networked Information Aggregation for Binary Classification](https://mlsanity.com/paper/2605.01082/) (2026)
- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [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)
- [Efficient NTK using Dimensionality Reduction](https://mlsanity.com/paper/2210.04807/) (2022)
- [The Space Complexity of Approximating Logistic Loss](https://mlsanity.com/paper/2412.02639/) (2024)
- [Private Sketches for Linear Regression](https://mlsanity.com/paper/2511.07365/) (2025)
- [Deterministic Coreset for Lp Subspace](https://mlsanity.com/paper/2601.00361/) (2026)
- [Scalable Learning of Multivariate Distributions via Coresets](https://mlsanity.com/paper/2603.19792/) (2026)

## Abstract (arXiv)

What guarantees are possible for solving logistic regression in one pass over a data stream? To answer this question, we present the first data oblivious sketch for logistic regression. Our sketch can be computed in input sparsity time over a turnstile data stream and reduces the size of a d-dimensional data set from n to only operatornamepoly(μ dlog n) weighted points, where μ is a useful parameter which captures the complexity of compressing the data. Solving (weighted) logistic regression on the sketch gives an O(log n)-approximation to the original problem on the full data set. We also show how to obtain an O(1)-approximation with slight modifications. Our sketches are fast, simple, easy to implement, and our experiments demonstrate their practicality.