Answers are grounded in this paper and cite their sources.
The seminal work of Cohen and Peng (STOC 2015) introduced Lewis weight sampling to the theoretical computer science community, which yields fast row sampling algorithms for approximating d -dimensional subspaces of \(ₚ\) up to \((1+ε)\) relative error. Prior works have extended this important primitive to other settings, such as the online coreset and sliding window models . However, these results are only for \(p∈\{1,2\}\) , and results for \(p=1\) require a suboptimal \(Õ(d²/ε²)\) samples. In this work, we design the first nearly optimal \(ₚ\) subspace embeddings for all \(p∈(0,∞)\) in the online coreset and sliding window models. In both models, our algorithms store \(Õ(d/ε²)\) rows for \(p∈(0,2)\) and \(Õ(dp/2/ε²)\) rows for \(p∈(2,∞)\) . This answers a substantial generalization of the main open question of Braverman et al. (2020), 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/ε²)\) rows for \(p > 2\) . Previously, such a sampling scheme was only known to have a sample complexity of \(Õ(dp/2/ε⁵)\) , whereas a bound of \(Õ(dp/2/ε²)\) is known if a more sophisticated recursive sampling algorithm is used. 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 online 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 Munteanu et al. (2021), and we also provide the first lower bounds showing that a linear dependence on \(μ\) is necessary.
No takes yet. Share an insight, caveat, or question.
Woodruff et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: