Timezone: »

 
Spotlight
Oblivious Sketching for Logistic Regression
Alexander Munteanu · Simon Omlor · David Woodruff

Thu Jul 22 07:30 AM -- 07:35 AM (PDT) @
in Probabilistic Methods 3 »
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 $\operatorname{poly}(\mu d\log n)$ weighted points, where $\mu$ 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.
Keywords: Algorithms

Author Information

Alexander Munteanu (TU Dortmund)
Simon Omlor (TU Dortmund)
David Woodruff (Carnegie Mellon University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors