Online Lewis Weight Sampling
David P. Woodruff, Taisuke Yasuda · Society for Industrial and Applied Mathematics eBooks · 2023
The seminal work of Cohen and Peng [CP15] (STOC 2015) introduced Lewis weight sampling to the theoretical computer science community, which yields fast row sampling algorithms for approximating d-dimensional subspaces of ℓp up to (1 + ε) relative error. Several works have extended this important primitive to other settings, including the online coreset and sliding window models [BDM+20] (FOCS 2020) as well as the adversarial streaming model [BHM+21] (NeurIPS 2021). However, these results are only for p ∈ {1, 2}, and results for p = 1 require a suboptimal Õ(d2/ε2) samples. In this work, we design the first nearly optimal ℓp subspace embeddings for all p ∈ (0, ∞) in the online coreset, sliding window, and the adversarial streaming models. In all three models, our algorithms store Õ(d/ε2) rows for p ∈ (0, 2) and Õ(dp/2/ε2) rows for p ∈ (2, ∞). This answers a substantial generalization of the main open question of [BDM+20], and gives the first results for all p ∉ {1, 2} and achieves nearly optimal sample complexities for all p. Towards our result, we give the first analysis of “one-shot” Lewis weight sampling of sampling rows proportionally to their Lewis weights, which gives a sample complexity of Õ(dp/2/ε2) rows for p > 2. Previously, such a sampling scheme was only known to have a sample complexity of Õ(dp/2/ε5) [CP15], whereas a bound of Õ(dp/2/ε2) is known if a more sophisticated recursive sampling algorithm is used [MMWY21, LT91]. Note that the recursive sampling strategy cannot be implemented in an online setting, thus necessitating an analysis of one-shot Lewis weight sampling. Perhaps surprisingly, our analysis crucially uses a novel connection to online numerical linear algebra, even for offline Lewis weight sampling. As an application, we obtain the first one-pass streaming coreset algorithms for (1 + ε) approximation of important generalized linear models, such as logistic regression and p-probit regression. Our upper bounds are parameterized by a complexity parameter μ introduced by [MSSW18], and we also provide the first lower bounds showing that a linear dependence on μ is necessary. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.08268