2021/07/14 by Alexander Munteanu, Munteanu, Alexander, Simon Omlor +3 · 2 citations
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2107.06615
openalex publication_date 2021/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 poly(μdlog n) weighted points, where μ 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.