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

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.