Online Lewis Weight Sampling

The seminal work of Cohen and Peng introduced Lewis weight sampling to the theoretical computer science community, yielding fast row sampling algorithms for approximating d-dimensional subspaces of ℓp up to (1+ε) error. Several works have extended this important primitive to other settings, including the online coreset and sliding window models. However, these results are only for p∈1,2, and results for p=1 require a suboptimal tilde O(d2/ε2) samples. In this work, we design the first nearly optimal ℓp subspace embeddings for all p∈(0,∞) in the online coreset and sliding window models. In both models, our algorithms store tilde O(d1lor(p/2)/ε2) rows. This answers a substantial generalization of the main open question of [BDMMUWZ2020], and gives the first results for all pnotin1,2. Towards our result, we give the first analysis of "one-shot'' Lewis weight sampling of sampling rows proportionally to their Lewis weights, with sample complexity tilde O(dp/2/ε2) for p>2. Previously, this scheme was only known to have sample complexity tilde O(dp/2/ε5), whereas tilde O(dp/2/ε2) is known if a more sophisticated recursive sampling is used. The recursive sampling cannot be implemented online, thus necessitating an analysis of one-shot Lewis weight sampling. Our analysis uses a novel connection to online numerical linear algebra. 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 [MSSW2018], and we show the first lower bounds showing that a linear dependence on μ is necessary.