mlsanityData to 14 Oct 2026

Oblivious sketching for logistic regression

arXiv 2107.06615 ↗First posted 14 Jul 2021cs.DS cs.LG stat.MLcited by 18

Not on the map. Why?

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.

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

18 of 51 references.

References · 18

  1. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  2. 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
  3. 2016Coresets for Scalable Bayesian Logistic Regressioncited by 79
  4. 2018On Coresets for Logistic Regressioncited by 67
  5. 2016Coresets and Sketchescited by 63
  6. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  7. 2016New Frameworks for Offline and Streaming Coreset Constructionscited by 38
  8. 2020Coresets for Near-Convex Functionscited by 38
  9. 2016Online Row Samplingcited by 15
  10. 2019Dimensionality Reduction for Tukey Regressioncited by 12
  11. 2020Streaming Coresets for Symmetric Tensor Factorizationcited by 9
  12. 2013Principal Component Analysis and Higher Correlations for Distributed Datacited by 7
6 more
  1. 2021Exponentially Improved Dimensionality Reduction for ℓ1: Subspace Embeddings and Independence Testingcited by 7
  2. 2018Tight Bounds for ℓp Oblivious Subspace Embeddingscited by 6
  3. 2019Random Projections and Sampling Algorithms for Clustering of High-Dimensional Polygonal Curvescited by 5
  4. 2015Random projections for Bayesian regressioncited by 4
  5. 2020Subspace Embeddings Under Nonlinear Transformationscited by 4
  6. 2019The One-Way Communication Complexity of Dynamic Time Warping Distancecited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 4; 2024: 6; 2025: 2; 2026: 3.

18 papers.

Sort:

  1. 2022Online Lewis Weight Samplingcited by 15
  2. 2022p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresetscited by 11
  3. 2023Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regressioncited by 8
  4. 2023Optimal Sketching Bounds for Sparse Linear Regressioncited by 6
  5. 2024Scalable Learning of Item Response Theory Modelscited by 6
  6. 2023Feature Space Sketching for Logistic Regressioncited by 4
  7. 2024No Dimensional Sampling Coresets for Classificationcited by 4
  8. 2024Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentationcited by 3
  9. 2024Turnstile ℓp leverage score sampling with applicationscited by 3
  10. 2026Networked Information Aggregation for Binary Classificationcited by 3
  11. 2023Gradient Coding with Iterative Block Leverage Score Samplingcited by 2
  12. 2025Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curvescited by 2
6 more
  1. 2024A Provably Accurate Randomized Sampling Algorithm for Logistic Regressioncited by 1
  2. 2022Efficient NTK using Dimensionality Reductioncited by 0
  3. 2024The Space Complexity of Approximating Logistic Losscited by 0
  4. 2025Private Sketches for Linear Regressioncited by 0
  5. 2026Deterministic Coreset for Lp Subspacecited by 0
  6. 2026Scalable Learning of Multivariate Distributions via Coresetscited by 0