Online Lewis Weight Sampling
This work addresses a theoretical bottleneck in online and streaming algorithms for subspace approximation and generalized linear models, offering significant improvements over prior bounds and enabling new practical applications.
The paper tackles the problem of designing nearly optimal ℓ_p subspace embeddings for all p in (0,∞) in online coreset and sliding window models, achieving sample complexity of Õ(d^{1∨(p/2)}/ε²) rows, which answers a generalization of an open question and provides first results for p∉{1,2}. It also improves the analysis of one-shot Lewis weight sampling to Õ(d^{p/2}/ε²) for p>2, enabling applications like one-pass streaming coresets for logistic regression and p-probit regression.
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 $\ell_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\in\{1,2\}$, and results for $p=1$ require a suboptimal $\tilde O(d^2/ε^2)$ samples. In this work, we design the first nearly optimal $\ell_p$ subspace embeddings for all $p\in(0,\infty)$ in the online coreset and sliding window models. In both models, our algorithms store $\tilde O(d^{1\lor(p/2)}/ε^2)$ rows. This answers a substantial generalization of the main open question of [BDMMUWZ2020], and gives the first results for all $p\notin\{1,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(d^{p/2}/ε^2)$ for $p>2$. Previously, this scheme was only known to have sample complexity $\tilde O(d^{p/2}/ε^5)$, whereas $\tilde O(d^{p/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.