Papers › Almost Linear Constant-Factor Sketching for ℓ₁ and Logistic Regression
Almost Linear Constant-Factor Sketching for ℓ₁ and Logistic Regression
Alexander Munteanu, Simon Omlor, David Woodruff
We improve upon previous oblivious sketching and turnstile streaming results for ℓ₁ 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 Õ(d¹⁺ᶜ) for ℓ₁ regression and Õ(μd¹⁺ᶜ) for logistic regression, where μ is a standard measure that captures the complexity of compressing the data. For ℓ₁-regression our sketching dimension is near-linear and improves previous work which either required Ω(logd)-approximation with this sketching dimension, or required a larger poly(d) number of rows. Similarly, for logistic regression previous work had worse poly(μd) factors in its sketching dimension. We also give a tradeoff that yields a 1+ε approximation in input sparsity time by increasing the total size to (dlog(n)/ε)^(O(1/ε)) for ℓ₁ and to (μdlog(n)/ε)^(O(1/ε)) 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.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Methods
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections