Online Lewis Weight Sampling

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. Prior works have extended this important primitive to other settings, such as the online coreset and sliding window models [BDM + 20] (FOCS 2020). However, these results are only for p ∈ 1, 2, and results for p = 1 require a suboptimal Õ(d 2 /ε 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 Õ(d/ε 2 ) rows for p ∈ (0, 2) and Õ(d p/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 Õ(d p/2 /ε 2 ) rows for p > 2. Previously, such a sampling scheme was only known to have a sample complexity of Õ(d p/2 /ε 5 ) [CP15], whereas a bound of Õ(d p/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.

• An earlier version of this work appears in SODA 2023, which includes an error in the result about adversarially robust ℓp subspace embeddings. The current version removes this result. The other results in this paper are unaffected.