Almost Linear Constant-Factor Sketching for _1 and Logistic Regression

Code

• github.com/tim907/oblivious_sketching_varreglogreg
  OfficialIn papernone★ 0

Abstract

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 O(d^1+c) for _1 regression and O( d^1+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 ( d)-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 (d(n)/)^O(1/) for _1 and to ( d(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.

Tasks

Reproductions