Oblivious Sketching for Logistic Regression

Alexander Munteanu, Simon Omlor, David Woodruff
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:7861-7871, 2021.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-munteanu21a, title = {Oblivious Sketching for Logistic Regression}, author = {Munteanu, Alexander and Omlor, Simon and Woodruff, David}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {7861--7871}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/munteanu21a/munteanu21a.pdf}, url = {https://proceedings.mlr.press/v139/munteanu21a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Oblivious Sketching for Logistic Regression %A Alexander Munteanu %A Simon Omlor %A David Woodruff %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-munteanu21a %I PMLR %P 7861--7871 %U https://proceedings.mlr.press/v139/munteanu21a.html %V 139 %X 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.
APA
Munteanu, A., Omlor, S. & Woodruff, D.. (2021). Oblivious Sketching for Logistic Regression. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:7861-7871 Available from https://proceedings.mlr.press/v139/munteanu21a.html.

Related Material