Sharper Bounds for $\ell_p$ Sensitivity Sampling
This work provides improved theoretical guarantees for sampling algorithms in large-scale machine learning, addressing a long-standing bottleneck in sensitivity sampling for $\ell_p$ norms beyond $p=2$, which is incremental but advances the field.
The paper tackles the problem of improving sample complexity bounds for sensitivity sampling in $\ell_p$ subspace embeddings, achieving a bound of roughly $\mathfrak S^{2-2/p}$ for $2<p<\infty$, which improves over the general $\mathfrak S d$ bound. It also shows new results for root leverage score sampling and combined sampling methods, yielding the best known sample complexity for structured matrices with small $\ell_p$ sensitivity.
In large scale machine learning, random sampling is a popular way to approximate datasets by a small representative subset of examples. In particular, sensitivity sampling is an intensely studied technique which provides provable guarantees on the quality of approximation, while reducing the number of examples to the product of the VC dimension $d$ and the total sensitivity $\mathfrak S$ in remarkably general settings. However, guarantees going beyond this general bound of $\mathfrak S d$ are known in perhaps only one setting, for $\ell_2$ subspace embeddings, despite intense study of sensitivity sampling in prior work. In this work, we show the first bounds for sensitivity sampling for $\ell_p$ subspace embeddings for $p > 2$ that improve over the general $\mathfrak S d$ bound, achieving a bound of roughly $\mathfrak S^{2-2/p}$ for $2<p<\infty$. Furthermore, our techniques yield further new results in the study of sampling algorithms, showing that the root leverage score sampling algorithm achieves a bound of roughly $d$ for $1\leq p<2$, and that a combination of leverage score and sensitivity sampling achieves an improved bound of roughly $d^{2/p}\mathfrak S^{2-4/p}$ for $2<p<\infty$. Our sensitivity sampling results yield the best known sample complexity for a wide class of structured matrices that have small $\ell_p$ sensitivity.