Title: Turnstile $\ell_p$ leverage score sampling with applications Authors:  Alexander Munteanu - TU Dortmund (Germany) [presenting]
Simon Omlor - TU Dortmund (Germany)
Abstract: The turnstile data stream model offers the most flexible framework where data can be manipulated dynamically, i.e., rows, columns, and even single entries of an input matrix can be added, deleted, or updated multiple times in a data stream. A novel algorithm is developed for sampling rows $a_i$ of a matrix $A\in\mathbb{R}^{n\times d}$, proportional to their $\ell_p$ norm when $A$ is presented in a turnstile data stream. The algorithm not only returns the set of sampled row indexes, but it also returns slightly perturbed rows $\tilde{a}_I \approx a_i$, and approximates their sampling probabilities up to $\varepsilon$ relative error. When combined with preconditioning techniques, the algorithm extends to $\ell_p$ leverage score sampling over turnstile data streams. With these properties in place, it allows the simulation of subsampling constructions of coresets for important regression problems to operate over turnstile data streams with very little overhead compared to their respective off-line subsampling algorithms. For logistic regression, this framework yields the first algorithm that achieves a $(1+\varepsilon)$ approximation and works in a turnstile data stream using polynomial sketch/subsample size, improving over $O(1)$ approximations or $\exp(1/\varepsilon)$ sketch size of previous work.